As an afterthought someone decided at the last minute, that maybe the architect (me) should be on the architectural review of a product.
Normally for social networking web development, I allow for a little short term inconsistency. This is because only one user has access to modify a thing and that user isn’t likely to do two things at the same time. Because of this, concurrency is almost never a problem and. even if the data gets clobbered, the database at least is consistent and your objects are quickly fixed.
The problem with this particular project is that since a paid good is involved and many users will race to the same data store—inconsistencies can occur and they’d be more harmful than a goto statement. The solution proposed was to build a Java service to keep these eight pieces of data consistent. There was also a release plan in order to estimate the resource allocation for the new service under live site load.
Though late to the meeting, I opened my mouth and said, “You don’t need a Java service to do this. You can do it all in PHP and memcache.”
Why they didn’t think it was possible
Long before I joined the company, there was a system to prevent stampeding by having a lock key in memcache. This didn’t work out so well.
Stampeding is what occurs have 100,000 concurrent users and a memcache key for a fairly popular piece of data (say the block list for your web application, or the ad unit for the banner ads) expires (because of a version increment or an expiration). Tons of concurrent processes will see the data is missing and will stampede the database with the same request. Databases are slow—which is why we have memcache in the first place—and your site experiences a very nasty hiccup every time this happens.
One problem was that it is buggy. It used a nonce/semaphore to look a lot like this example. Well like that but if written by someone who just learned object-oriented program, then the locking code was added by someone else who had just read a design patterns book and then the bugs were closed by someone else who was so lazy that they prefer to patch problems on the user interface layer. It looked that way because it was written that way.
I always say that the sites the founders worked on before this had a business plan that was the internet-equivalent of a drive-by shooting.
Our codebase reflected that attitude.
So the reason we got burned by concurrency issues in memcache wasn’t because that it’s fundamentally broken, it was simply because it was easier to rewrite than to pretend that jenga-ing this stuff with a patch on a patch on a patch was going to magically make the code more stable.
And the reason I removed it in the rewrite wasn’t because that it’s that difficult to write, but rather that we were using this locking for every single object that we stored in memcache, even the less busy ones. Anything built in would be abused similarly. Better to not give the developers any rope they can use to hang the site with.
(In the case of stampedes, I figured the key is very likely to be too “hot” anyway. Instead I built a system to allow easy storage of hot keys in the shared memory cache of the webserver, instead of using memcache and needing a network call.)
What was the bug?
None of this is typically understood by anyone else. The reason is simply that the average engineer has been working here 1/20th the time I have. And those that have been working here half the time—pretty much all the rest—only know that I pulled the locking code out.
The bug in our code (and the above link) is that there is a race gap between the memcache::get() and memcache::set(). This is perfectly fine if all you want to do is prevent a stampede since only a few, even on a slow system like PHP, would be in the winners circle of that race. This sort of thing is really bad in the above case.
So what is the solution? The solution is to use a memcache command that is more atomic. The one that fits the bill is memcache::add() which, if a key is already added returns a failure condition.
The codez
For you script kiddies, here is the code. I don’t know if it works since I wrote it without any unit testing. 🙂
// {{{ locked_mecache_update($memcache,$key,$updateFunction,$expiryTime,$waitUTime,$maxTries)
/**
* A function to do ensure only one thing can update a memcache at a time.
*
* Note that there are issues with the $expiryTime on memcache not being
* fine enough, but this is the best I can do. The idea behind this form
* of locking is that it takes advantage of the fact that
* {@link memcache_add()}'s are atomic in nature.
*
* It would be possible to be a more interesting limiter (say that limits
* updates to no more than 1/second) simply by storing a timestamp or
* something of that nature with the lock key (currently stores "1") and
* not deleitng the memcache entry.
*
* @package TGIFramework
* @subpackage functions
* @copyright 2009 terry chay
* @author terry chay <tychay@php.net>
* @param $memcache memcache the memcache object
* @param $key string the key to do the update on
* @param $updateFunction mixed the function to call that accepts the data
* from memcache and modifies it (use pass by reference).
* @param $expiryTime integer time in seconds to allow the key to last before
* it will expire. This should only happen if the process dies during update.
* Choose a number big enough so that $updateFunction will take much less
* time to execute.
* @param $waitUTime integer the amount of time in microseconds to wait before
* checking for the lock to release
* @param $maxTries integer maximum number of attempts before it gives up
* on the locks. Note that if $maxTries is 0, then it will RickRoll forever
* (never give up). The default number ensures that it will wait for three
* full lock cycles to crash before it gives up also.
* @return boolean success or failure
*/
function locked_memcache_update($memcache, $key, $updateFunction, $expiryTime=3, $waitUtime=101, $maxTries=100000)
{
$lock = 'lock:'.$key;
// get the lock {{{
if ($maxTries>0) {
for ($tries=0; $triesadd($lock,1,0,$expiryTime)) { break; }
usleep($waitUtime);
}
if ($tries == $maxTries) {
// handle failure case (use exceptions and try-catch if you need to be nice)
trigger_error(sprintf('Lock failed for key: %s',$key), E_USER_NOTICE);
return false;
}
} else {
while (!$memcache->add($lock,1,0,$expiryTime)) {
usleep($waitUtime);
}
}
// }}}
// modify data in cache {{{
$data = $memcache->get($key, $flag);
call_user_func($updateFunction, $data); // update data
$memcache->set($key, $data, $flag);
// }}}
// clear the lock
$memcache->delete($lock,0);
return true;
}
// }}}
(Yes, I this commenting is typical when I code, hope I could say the same for you.) The reason it’s a function is so that an engineer has to do work to use it. If they got it for free, they’d abuse it—or, at least that was the worry.
If you need to do locking on the database, then you would have the $updateFunction nest something that will handle a database update. You might want to up the $expiryTime too, but you probably won’t need to—I just chose 3 because Touge did in his original post. 🙂
nice! Although, i recommend you change your trigger_error from “Lock failed for key: ” to “memcache ran out of loops” just so that you can confuse people for years to come, whenever there is contention on a key. “OH SHIT! Memcache is breaking!”
@rahul Good point.
Rahul is alluding to the fact that the original version of the code used to have “ran out of loops” as the error. I remember trying to grep the codebase to find where it was (and then spending about thirty minutes trying to figure what it does and then the rest of the hour finding out that it never worked as it intended.)
Considering your scenario, this is definitely a great solution. Just as curiosity, did you place it live and how is the benchmarking on this so far?
P.S. I don’t entirely agree with PHP being slow, but depending with what system you are benchmarking with, you might be right.
I’m curious what will happen when we get the lock, cause previous thread has finished his work and fill cache with new data. Current thread and all that start waiting for lock will call $updateFunction. In case of 1000 concurrent request that will be 1000 calls.
Is it a good idea to check cache content after getting the lock.
Like this:
1a. Check cache (memcache::get($key))
1b. If actual return data
2. Get the lock, wait for the lock (memcache::add(“lock::$key”))
3a. Check cache again maybe there are actual data (memcache::get($key))
3b. I yes release the lock (memcache::delete(“lock::$key”))
3c. Return data
4. Get data ($updateFunction)
5. Cache data (memcache::set($key))
6. Release the lock (memcache::delete(“lock::$key”))
7. Return data
Point 3 is my magic 🙂
@Worthy. The point of using the form of locking I mentioned above is that it is atomic. Only one person can have the lock at a time as opposed to other ideas where there is a small gap in time between when the lock is created and the data is read.
In this example only one person can modify the data at once, note that you aren’t writing yourself in this example.
In the case you seem to imply (multiple concurrent reads, single writer), basically what goes on in my model is that since you are given the object state locked, you can compare it to your internal object state before the change. If they are the same, you can commit your change, if they are different, you have to rerun to change again.
Because of this, it is better to treat it as “data” instead of an object when saving to and from memcache.
Cool solution 🙂
This is what I looking for….
The locking mechanism for memcache… I just realize the add will return error if the key already exist… it’s really cool… thanks a lot !!!
Worthy is right, we experienced this EXACT condition ourselves. It turns out that from the time it takes to acquire the lock in one thread another thread could have locked AND saved new data into the key. Your lock method should re-fetch data that sits there as there is this very edge-case possibility. I am now looking into versioning, or better, memcache->cas(…) now for this very reason.
@Anonymous: Yes that can happen. In those cases you have to compare before committing else you will overwrite new data with old data (or you can just re-read and apply updates since you have the lock by then). That’s why my example has a call to user supplied update function which is passed in the (consistent) read data.
In the memcache protocol there are a number of flags that can be set along with the data. I believe libmemcached uses one of them as a incremented timestamp to enable the “check and set” feature you see in extensions like memcached in PHP. 🙂
I hope that helps.
I know this is a fairly old post, but I was just researching different options in implementing a load-balanced memcached solution, and was wondering if you were/are in a load-balanced environment in this situation. If you are not this makes perfect sense, if you are, then I am very confused?
At the time, I think we were loadbalancing memcache across 30 machines with ~1TB of total memcache.
The answer depends on the environment. In this case, balancing of the keys was done using the traditional method: consistent hashing using a ring: http://www.lexemetech.com/2007/11/consistent-hash… There was only one pool for each keytype (unlike facebook which has three pools across three datacenters).
What happens in normal cases is that the memcache "lock" key and the regular key will be on different parts of the pool, that is why in this example the memcache object is actually passed in. So the server hash is determined using the regular key and both it and the lock key are written to the same server. If a server in the pool goes down, it goes down consistently.
I hope that helps.
You can not rely on this locking technique. What if :
* your lock is deleted by memcached because there is no more room for new objects
* $memcache->delete($lock,0) fails. cached object will remain locked until lock expires.
But in 99.99% of the cases your locking implementation will work 😉
My recent post Load Test Whatever You Want With Apache JMeter
Good points. Both of them.
I'm counting that such a tiny lock is on a slab that should have more than enough room.
The expiryTime is hopefullypretty short.
German article on memcache mentions this.
@tychay: I'm working on building a similar locking scheme for the company I'm working for now. You allude to this sort of thing being dangerous to use for every memcache update. The obvious reasons would be the extra TCP roundtrip you need to get the lock and the fact that the minimum TTL you can set in memcache is 1s which is a long time compared to the time it would take to actually do the DB read and memcache update. Am I missing any reasons why this would be a bad thing to use more than very rarely? It's not necessary everywhere, but I can think of a lot of places where something like this could protect us from bad things happening after a memcache crash.
It's an extra call. If it's not needed, you shouldn't use it, that's all.
Cool, that's what I thought. Thanks Terry.
Just FYI, you can use memcached with CAS now.
We had a few cases where it took quite long to generate a cache, so when cache expired and many requests came in, it was really bad, db got overloaded, etc. We needed some locking scheme for memcache and we’ve written and used https://github.com/gsmlabs/LSDCache lib for this. First process (and only this one) creates lock, and until new cache is present (until lock is released actually), all other processes get stale values or wait 1 sec and then get new cache or stale value (depends on strategy, it’s fully configurable there). And it works pretty well under heavy load.