Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

This post is a follow up to this question: http://stackoverflow.com/questions/10626904/php-atomic-memcache/10627226

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)

Any input would be greatly appreciated! Thank you.

share|improve this question
1  
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 Rizos May 25 '12 at 15:20
add comment

1 Answer

up vote 4 down vote accepted

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')

UPDATE: well, 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')
share|improve this answer
    
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 2:00
2  
@Kovo and vartec: Memcache:add is not atomic, but as noted in a comment here, there is a way around it –  Izkata May 27 '12 at 2: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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.