Right, I know what the docs say, however, it's fine to use this for cache invalidation (but maybe not other use-cases) in production.

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.