This book covers the use of Redis, an in-memory database/data structure server.

open all | close all

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]

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.


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