"Namespaced" cache expiring with memcached

We implemented page caching recently in Edicy with memcached. One of the biggest issues we were facing here was expiring the cache (no surprise - expring cache is never easy). That's because it is very expensive to track down which specific pages need to be flushed from cache when user changes something on site. For example, changing the label for one page in navigation menu, all the pages displaying this menu item must be cleared from cache. Basically, this cannot be tracked down in Edicy. So we needed to flush cache for the entire site when user changes something in there.

The problem

Bad luck. Memcached is just a flat key-value based hash in memory and if you keep data for multiple user "accounts" in there, you simply can't delete the data that belongs only to single specified account. Memcached allows to delete just one key or entire cache but nothing in between. Giving your cache keys specific names, such as "account-1/page-1", "account-1/page-2", ..., "account-n/page-n" and then finding the keys that start with "account-14" for flushing does not get you any closer. And that's because in memcached, there is no way to loop through all keys. So we had to clear the cache for ALL sites when one user changes at least one character on his site and we'd end up with a cache that does not cache pages on any site for longer than half a second.

There is a Rails plugin that implements delete_matched method for mem_cache_store which does not work by default in Rails (if you're intrested on how it works, go check the source). We quickly ran into problems with this plugin. First the way it manages the cache keys is going to be expensive when you have huge number of objects and second, if multiple application instances change the contents of cache keys value object simultaneously, you'll end up with incomplete key declaration list. And the last problem makes this plugin pretty useless.

The solution

Memcached wiki describes a workaround to "simulate" namespaces with memcached. It takes advantage of memcached feature that removes the oldest values from cache automatically when it's full. In the example above, reading and writing values for key "account-1/page-1" is done like this:
  1. We store extra integer for key prefix "account-1" in memcached by starting from "1", but basically any integer will do :)
  2. When reading or writing value for key "account-1/page-1", read value for key "account-1" and mix it into the key. For example, if value for key "account-1" is "253" re-write the requested key as "account-1-253/page-1".
  3. Access the object with key "account-1-253/page-1" in memcached instead.
And this is where things get interesting. To "remove" all keys for given account
  1. Increment value for key "account-1". This opreation is cheap in memcached. In our example, the value is now "254".
  2. When accessing the value for key "account-1/page-1" next time, the key will be replaced to "account-1-254/page-1" which does not exist in cache. And there you go - all keys for given account are now gone!
We wrote a Rails plugin called mem_cache_account_based_store which you can get from GitHub and plug into your Rails application just as any other cache store. This plugin wraps the simulation of namespaces and all you have to to is to provide account id for the plugin. Follow the instructions in plugin documentation to see how it is done.