Atomic Memcache Operations in PHP

Question

This post is a follow up to this question: PHP Atomic Memcache on StackOverflow.

Considering I am using Memcache (no d at the end) on PHP 5.3.10, I implemented a custom locking system where a client will wait until a lock key is destroyed before it begins to modify a key on memcache.

So:

Client 1 connects, checks for an active lock on key 1, finds none, and gets the data
Client 2 connects a few microsecond after Client 1, requests the same data from key 1,
   but finds a lock
Client 2 enters a retry loop until Client 1 releases the lock
Client 1 saves new data to key 1, releases the lock
Client 2 gets the fresh data, sets a lock on key 1, and continues

This works 90% of the time. It would work 100% of the time if two requests are made far apart from each other (say 500ms). But lets say two requests are made at almost the same time (10 to 100 microseconds apart) the above solution fails, and both clients write to the same key, resulting in incorrect data.

I have tried many things, including a loop that varies in wait time every iteration:

while(/*lock key exists*/)
{
    usleep(mt_rand(1000,100000);
}

This helps only a little.

What would be the solution to this particular issue? These mecache processes must be atomic. I am willing to tolerate a 1% failure rate (since it means I just need to work a little harder to make it 0), but anything more is just too risky.

I've broken my head trying to figure this out. There is no possibility to upgrade to Memcached, and the value changes are not simple (they are not increments)

Migration voter (and everyone else): As I read it the question is somewhere in the grey area between ProgSE and Stack Overflow, which means that we can keep it here. — yannis, May 25 '12 at 15:20

score 6 · Accepted Answer · edited Aug 08 '14 at 20:29

Client 1 connects, checks for an active lock on key 1, finds none, and gets the data

You should not test for lock then create it, but rather attempt to create it with Memcache::add, which will either create lock or fail. It does so atomically, so you'll no longer have TOCTTOU race condition.

$mc= new Memcache;
$mc->connect('localhost', 11211);

while(!$mc->add('your_lock_key', 1))
{
    usleep(mt_rand(1000,100000);
}

manipulate_data(...)

$mc->delete('your_lock_key')

Upon further inspection, according to PHP's documentation add is atomic. But digging deeper, it results that it may be not atomic on memcache clusters with multiple memcache servers. There is however a solution to this:

$mc= new Memcache;
$mc->connect('localhost', 11211);

$locked = false;

$lock_key = $mc->get('your_lock_key');
if (!$lock_key) {
   $lock_key = uniqid();
   $mc->add('your_lock_key', $lock_key);
}

while(!$locked) {
   if($mc->cas($cas_token, 'your_lock_key', $lock_key) && 
      $mc->getResultCode() == Memcached::RES_SUCCESS) {
        $locked = true;
        break;
   } else {
     $other_key = $mc->get('your_lock_key');  //this is only to reset last access for CAS
   }
   usleep(mt_rand(1000,100000);
} 


manipulate_data(...)

$mc->delete('your_lock_key')

Thanks! I gave it a shot. Although it is cleaner, it still fails my test (10 connections executed at the same time, trying to access the same key, and modify it, then save it) :( — Kovo, May 26 '12 at 02:00
@Kovo and vartec: Memcache:add is not atomic, but as noted [in a comment here](http://www.php.net/manual/en/memcache.add.php#96278), there is a way around it — Izkata, May 27 '12 at 02:42
That did it! The solution that worked was a combo if this answer, plus Izkata's comment. I give the lock key a random value between 1 and 1,000,000,000. Then, right after setting it, I check it's value. If the values do not match, I return false. This has turned my 90% solution into a 100% solution. Of course I leave a 1% margin of error, but it seems like that would be an extremely rare case. Granted my test used 10 simultaneous connections. Perhaps a higher number may return different results. — Kovo, May 27 '12 at 17:52

Atomic Memcache Operations in PHP

1 Answers1