The docs also say:
"While the time complexity for this operation is O(N), the constant times are fairly low. For example, Redis running on an entry level laptop can scan a 1 million key database in 40 milliseconds."
If you have so many keys that this is an issue for cache invalidation, you should be using memcached anyways. (Since it can be distributed, where in Redis distribution is left up to you to figure out)
I wasn't able to dig it up, but I know I read an article about some consulting group making a site for a major shoe company where they did exactly this.
Your hash method isn't the best way either though since it's more efficient to store everything in individual key-value pairs, and hashes cannot be nested.
Really the BEST way to do this in Redis is to use a set containing all they keys related to an object, then clear each of them out when destroying an item.
However, for this particular problem, the docs do say:
Don't use KEYS in your regular application code. If you're looking for a way to find keys in a subset of your keyspace, consider using sets.
I wonder why they don't suggest hashes?
keys post/83/*
No no no. This is slow and there is a large warning section in the notes (http://redis.io/commands/keys) about using this in production environments.
[Edit: Why is this bad? Think about if you have millions of keys in your environment. KEYS will need to iterate over a million keys to find the ones that match your pattern.]
As an alternative to using KEYS, Redis provides the hash object. Store everything abou an object in a hash (e.g.: "posts:83") and then just delete the hash object. Everything under it will be removed as well. If you need to know what's in the hash that is going to be deleted, use the HKEYS command (which has no such warning about performance).