memcache cas lock race condition

from time import time, clock
import timeit

from google.appengine.api import apiproxy_stub_map
apiproxy_stub_map.apiproxy = apiproxy_stub_map.APIProxyStubMap()

# from google.appengine.api import datastore_file_stub
# app_id = 'test'
# ds_stub = datastore_file_stub.DatastoreFileStub( app_id , None )
# apiproxy_stub_map.apiproxy.RegisterStub( 'datastore_v3' , ds_stub )

from google.appengine.api import memcache # http://code.google.com/p/memcached/wiki/NewCommands
from google.appengine.api.memcache import memcache_stub
mc_stub = memcache_stub.MemcacheServiceStub()
apiproxy_stub_map.apiproxy.RegisterStub( 'memcache' , mc_stub )

# from google.appengine.api import taskqueue
# from google.appengine.api.taskqueue import taskqueue_stub
# tq_stub = taskqueue_stub.TaskQueueServiceStub( )
# apiproxy_stub_map.apiproxy.RegisterStub( 'taskqueue' , tq_stub )


# from google.appengine.api import urlfetch   # default is 5 second timeout
# from google.appengine.api import urlfetch_stub
# apiproxy_stub_map.apiproxy.RegisterStub( 'urlfetch',urlfetch_stub.URLFetchServiceStub() )


LOCKED = 1
FREE = 2
MAX_LOCK_SECONDS = 2

class MemcacheLock( object ):
    """ slightly slower but not a victim of race conditions
        http://neopythonic.blogspot.com/2011/08/compare-and-set-in-memcache.html
    """

    def __init__(self):
        self.memcacheClient = memcache.Client()     # required for CAS threadsafe methods
        if not self.memcacheClient.get( 'SimpleLock' ): # initialization as CAS can only update a value, does not work on None
            self.memcacheClient.set( 'SimpleLock', FREE )


    def acquire_lock( self ):
        if LOCKED == self.memcacheClient.gets( 'SimpleLock' ):
            return False
        else:
            if self.memcacheClient.cas( 'SimpleLock', LOCKED, MAX_LOCK_SECONDS ):    # thread safe way to acquire the lock, do not use a loop, instead immediate fail
                return True
            else:
                return False


    def release_lock( self ):
        lockStatus = memcache.get( 'SimpleLock' )
        if lockStatus == LOCKED:
            memcache.set( 'SimpleLock', FREE )
        elif lockStatus == FREE:
            print( "Trying to release an already freed lock, THEREFORE THERE IS A LOCK CONTENTION BUG" )
        else:
            print( "Trying to release a lock that is neither LOCKED nor FREE, Initialization Bug?" )


    @staticmethod
    def lock_status( ):
        return memcache.get( 'SimpleLock' )


class MemcacheLockFlawed( object ):

    @staticmethod
    def acquire_lock( ):
        """ susceptible to race conditions
        """
        if LOCKED == memcache.get( 'SimpleLock' ):    # lighter weight check than add to reject earlier
            return False
        else:
            memcache.set( 'SimpleLock' , LOCKED, MAX_LOCK_SECONDS ) # if item already exists returns false, otherwise sets the value
            return True

    @staticmethod
    def release_lock( ):
        """ remove the memcache lock, static method in order to enable exception handling code to release the lock without creating a counter object
        """
        memcache.set( 'SimpleLock' , FREE )
#        memcache.delete( 'SimpleLock' )
        return

    @staticmethod
    def lock_status( ):
        return memcache.get( 'SimpleLock' )


""" windows clock() Flawed then CAS
True acquired in 0.263648120208 ms
False not acquired in 0.110334493128 ms
Lock:  1  (lookup in 0.112900411573 ms)
released in 0.122522605741 ms
Lock:  2  (lookup in 0.109693013517 ms)

True acquired in 0.27519475321 ms
False not acquired in 0.113541891185 ms
Lock:  1  (lookup in 0.11097597274 ms)
released in 0.323305724051 ms
Lock:  2  (lookup in 0.108410054295 ms)
"""
def basic_benchmark( timer_func, lock ):
    start = timer_func()              # time.clock() is preferred for benchmarking in Windows
    print lock.acquire_lock( ), 'acquired in {} ms'.format( ( timer_func() - start) * 1000 )    # for some reason the first operation is slower

    start = timer_func()
    print lock.acquire_lock( ), 'not acquired in {} ms'.format( (timer_func() - start) * 1000 )

    start = timer_func()
    print 'Lock: ', lock.lock_status(), ' (lookup in {} ms)'.format( (timer_func() - start ) * 1000 )

    start = timer_func()
    lock.release_lock()
    print 'released in {} ms'.format( (timer_func() - start ) * 1000 )

    start = timer_func()
    print 'Lock: ', lock.lock_status(), ' (lookup in {} ms)'.format( (timer_func() - start ) * 1000 )


def basic_memcache_usage():
    memcacheClient = memcache.Client()     # required for CAS threadsafe methods
    print "No value in memcache: ", memcacheClient.gets( 'SimpleLock' )
    print "CAS returns False when the initial key returns None: ", memcacheClient.cas( 'SimpleLock', LOCKED, MAX_LOCK_SECONDS )
    print "Lock is therefore not set: ", memcache.get( 'SimpleLock' )

    memcache.set( 'SimpleLock', FREE )
    memcacheClient.gets( 'SimpleLock' )
    memcache.set( 'SimpleLock', FREE )
    print "CAS detects a change (invisible timestamp), rejects the update: ", memcacheClient.cas( 'SimpleLock', LOCKED, MAX_LOCK_SECONDS )
    memcache.delete( 'SimpleLock' )
    print


if __name__ == '__main__':
    basic_memcache_usage()

#    basic_benchmark( time , MemcacheLockFlawed() )
    basic_benchmark( clock , MemcacheLockFlawed() )                  # time.clock() is preferred for benchmarking in Windows
    print

    memcache.delete( 'SimpleLock' )
    basic_benchmark( clock , MemcacheLock() )