Documentation - Redise Pack

A guide to Redise Pack installation, operation and administration

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]
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.