e-Book - Redis in Action

This book covers the use of Redis, an in-memory database/data structure server.
  • Foreword
  • Preface
  • Acknowledgments
  • About this Book
  • About the Cover Illustration
  • Part 1: Getting Started
  • Part 2: Core concepts
  • Part 3: Next steps
  • Appendix A
  • Appendix B
  • Buy the paperback

    11.2.3 Counting semaphores in Lua

    As we worked through our counting semaphores in chapter 6, we spent a lot of time
    trying to ensure that our semaphores had some level of fairness. In the process, we
    used a counter to create a sort of numeric identifier for the client, which was then
    used to determine whether the client had been successful. But because we still had
    race conditions when acquiring the semaphore, we ultimately still needed to use a
    lock for the semaphore to function correctly.

    Let’s look at our earlier implementation of the counting semaphore and think
    about what it may take to improve it using Lua.

    Listing 11.7The acquire_semaphore() function from section 6.3.2
    def acquire_semaphore(conn, semname, limit, timeout=10):
    
        identifier = str(uuid.uuid4())
    

    A 128-bit random identifier.

        now = time.time()
    
        pipeline = conn.pipeline(True)
    
        pipeline.zremrangebyscore(semname, '-inf', now - timeout)
    

    Time out old semaphore holders.

        pipeline.zadd(semname, identifier, now)
    

    Try to acquire the semaphore.

        pipeline.zrank(semname, identifier)
        if pipeline.execute()[-1] < limit:
    

    Check to see if we have it.

            return identifier
    
            conn.zrem(semname, identifier)
    

    We failed to get the semaphore; discard our identifier.

            return None
    

    In the process of translating this function into Lua, after cleaning out timed-out semaphores,
    it becomes possible to know whether a semaphore is available to acquire, so
    we can simplify our code in the case where a semaphore isn’t available. Also, because
    everything is occurring inside Redis, we don’t need the counter or the owner ZSET,
    since the first client to execute their Lua function should be the one to get the semaphore.
    The Lua version of acquire_semaphore() can be seen in the next listing.

    Listing 11.8The acquire_semaphore() function rewritten with Lua
    def acquire_semaphore(conn, semname, limit, timeout=10):
    
        now = time.time()
    

    Get the current timestamp for handling timeouts.

        return acquire_semaphore_lua(conn, [semname],
            [now-timeout, limit, now, str(uuid.uuid4())])
    

    Pass all of the required arguments into the Lua function to actually acquire the semaphore.

    acquire_semaphore_lua = script_load('''
    
    redis.call('zremrangebyscore', KEYS[1], '-inf', ARGV[1])
    

    Clean out all of the expired semaphores.

    if redis.call('zcard', KEYS[1]) < tonumber(ARGV[2]) then
    

    If we haven’t yet hit our semaphore limit, then acquire the semaphore.

        redis.call('zadd', KEYS[1], ARGV[3], ARGV[4])
    

    Add the timestamp to the timeout ZSET.

        return ARGV[4]
    end
    ''')
    

    This updated semaphore offers the same capabilities of the lock-wrapped
    acquire_fair_semaphore_with_lock(), including being completely fair. Further,
    because of the simplifications we’ve performed (no locks, no ZINTERSTORE, and no
    ZREMRANGEBYRANK), our new semaphore will operate significantly faster than the previous
    semaphore implementation, while at the same time reducing the complexity of
    the semaphore itself.

    Due to our simplification, releasing the semaphore can be done using the original
    release_semaphore() code from section 6.3.1. We only need to create a Lua-based
    refresh semaphore function to replace the fair semaphore version from section 6.3.3,
    shown next.

    Listing 11.9A refresh_semaphore() function written with Lua
    def refresh_semaphore(conn, semname, identifier):
        return refresh_semaphore_lua(conn, [semname],
    
            [identifier, time.time()]) != None
    

    If Lua had returned nil from the call (the semaphore wasn’t refreshed), Python will return None instead.

    refresh_semaphore_lua = script_load('''
    
    if redis.call('zscore', KEYS[1], ARGV[1]) then
        return redis.call('zadd', KEYS[1], ARGV[2], ARGV[1]) or true
    

    If the semaphore is still valid, then we update the semaphore’s timestamp.

    end
    ''')
    

    With acquire and refresh semaphore rewritten with Lua, we now have a completely
    fair semaphore that’s faster and easier to understand.

    Now that we’ve rewritten locks and semaphores in Lua and have seen a bit of what
    they can do to improve performance, let’s try to remove WATCH/MULTI/EXEC transactions
    and locks from two of our previous examples to see how well we can make them
    perform.