After a year or so of dormancy I’m finally inspired to write a blog post. This is my first post ever, so please excuse the coarseness. Plausibly enough, this one will be about Memcached, specifically how I implemented a client for TV.com, where I currently work.
The existing client was written in 2003 in PHP, which means it’s been around since the beginning, and is implemented at the highest level of the application stack (slow!). It also means that none of the advancements that have been made were available to us. The modulo hashing it uses was really crippling us, since every time we added or removed a mcd server from the pool, all existing keys would invalidate and our databases would get clobbered. Because of some of the infrastructure changes we were making, that would have happened quite often. More on this below.
Andrei Zmievski’s PHP libmecached library (which wraps the c libmemcached library) went stable right around the time we were considering this, so we jumped at the chance. This client was the obvious choice for several reasons:
- consistent key hashing
- atomic add/cas operations
- asynchronous get/set requests
- a modern command set for interfacing with memcached
Before I get in to the details of implementing the new client, I want to take a minute to talk about consistent key hashing.
Consistent hashing has been around for quite a while (pdf). It offers significant advantages over modulo hashing if the membership of your pool is uncertain. To illustrate, I graphed what happens with both forms of hashing when pool membership changes from the expected 16 ports (represented by the vertical bar).
You can immediately see that with consistent hashing you get a predictable, linear degradation as membership fluctuates.
Implementing the Client
The common concern everyone has to deal with when working with memcached is how to abstract away the race conditions endemic to concurrent systems. There are lots of solutions to this, most of which involve mutual exclusions. The problem with that, though, is that locking involves some small amount of overhead (which is why Terry wanted its use to be proactive). Getting and setting the semaphore incurs a (for the vast majority of cases) negligible cost of around 5ms, and only when a key is about to expire.
One of the solutions talked about on the memcached mailing list was probabilistic timeout, thought up by the folks with too much smarts and possibly not enough to do over at IMVU. The idea is this: ask mcd to expire your key some time in the future (perhaps 24 hours), but store the real ttl and the expire-at date along with the data.
$mcd_value = array(
'value' => $value,
'expire_on' => time() + $ttl,
'ttl' => intval($ttl)
);
$this->set($key, $mcd_value, 86400);Then, when you go to retrieve the key, apply the function ƒ(x) = 100 / x + 1 to the percentage of elapsed time to the TTL. The result is the probability that the key should expire (see Figure C).
//how much time is left until value expires
$time_delta = $result['expire_on'] - time();
//what percentage are we to reaching the TTL?
$normal_delta = ($time_delta / $result['ttl']) * 100;
//the probability of clearing the cache goes to 100
//as the delta approaches 0
$probability = round(100 / (abs($normal_delta) + 1));
$clear_value = (mt_rand(1, 100) <= $probability);
Figure C
Note that the scale of 100 was chosen somewhat arbitrarily. This is something that one could tune depending on circumstances, perhaps by creating predefined values for keys with different levels of expected use (e.g. high=1000, med=100, low=10). However, a goal of this method is to be easy to use and applicable to the common case.
If we decide that we need to expire this key, we can return Memcached::RES_NOT_FOUND to the user, who should regenerate the data and refresh the cache. In the majority of cases, this will allow us to “pre-expire” keys before they should actually expire, so there’s not a great onslaught of queries to the database every time a TTL is met.
There is of course, a race condition in this code. What happens if 4 clients all request a key which has 1% of its time left (which for a key with an hour TTL represents about 19-36 seconds, depending on how you round) before it expires? 100 / 1 +1 = 50, so each of those 4 clients has a 50% chance of clearing the key. Those are pretty good odds, so we have to expect that a certain number of clients are going to query the database.
If you’re interested in seeing how this client looks, I’ve got it up on github here. I’d like to invite any criticism you might have. The code has to fit an existing ecosystem, so I know parts of it are far from ideal.
