mmcached - a hierarchical extension to memcached

The problem with caching data

When using memcached for multiple sites we ran into the problem that:

1. we want to use the same memcached daemon for multiple sites
2. we want to be able to flush the cached keys of a certain site
3. we want to be able to flush certain categories of keys

Why would we want to flush different categories? An easy example is when you change a page template, in that case you want to flush everything that uses that template, but not all cached objects, configuration details, sessions etc.

We were able to use the same memcached daemons by prefixing all keys with the database name of the site. This is possible because every site is using an unique database. For example, the key config will become something like any_mms05/config.

Solving the requirement of flushing only parts of the cache, without deleting specific keys was a bit harder. I needed to change the code of memcached; open source comes to the rescue.

Adding hierarchy to memcached

I added hierarchy to the cached keys by splitting the keys on /-characters. Each key can have any number of /-characters, creating multiple levels of hierarchy.

For every element in the path of the key we store a timestamp. When the timestamp of a path-element (directory) is newer that the timestamp of the key (file) then the key is considered to be invalid.

For every cache lookup I split the key in its list of path-elements. For every level we check the timestamp of the different levels. This is done very fast (O(n) where n is the number of levels) by using a separate hash table, which is never flushed. The maximum timestamp is then compared against the timestamp of the cache entry.

For example database/object/thing/1004, will be have modification checks on database, database/object and database/object/thing.

Preventing keys to be flushed

One of the nice things of the memcached is that it is a very fast object store, much faster than a database. This makes it very attractive as a versatile data store. Of course memcached is a cache. So there is no guarantee that the data stored will be retained till the given expiration time. Memcached has an option to prevent flushing of data when memory is exhausted. However, this is a global switch. More useful would be to be able to specify on a item-by-item basis which stored elements might be flushed and which not.

I changed memcached so that you can specify if an item might be flushed, or should be kept till its expiration time (or till it is flushed manually). This is done by adding an exclamation character at the end of the key, for example: database/presence/queue!

Please note that database/presence/queue! and database/presence/queue are two different keys. The exclamation mark is part of the key name, this to prevent problems with existing code.

Of course, data will still be flushed when memcached is restarted, or when the key is deleted.

The code

You can download the modified memcached mmcached and a modified php memcache extension. The modified php extension has an additional function flush_dir($dir). This function can be used for invalidating keys stored below the given directory.

More information about memcached can be found at www.danga.com/memcached/
A manual page of the PHP extension memcache is at nl2.php.net/memcache