A Distributed Mutex and Semaphore using Redis

Redis has some really neat atomic multi-operation commands that can be used to create a distributed mutex. Check out the documentation for the SETNX command for an example.

This example is based on polling and unfair: waiting processes are not guaranteed to be served on a first-come, first-served basis.

redis-semaphore

Using the pretty cool BLPOP command I’ve created the simple redis-semaphore gem which implements a blocking and fair semaphore and mutex. Here’s some pseudocode to explain how it works:

if GETSET(my_mutex_start, 1) != 1
  LPUSH(my_mutex, token)

BLPOP(my_mutex)
# Work here
work()
LPUSH(my_mutex, token)

The first two lines make sure the mutex is initialized only once. Using the atomic GETSET operation we set the key my_mutex_start to 1, and check to see if it already was 1 before we set it. If it was then another process already initialized the mutex (or is busy doing so). If it wasn’t, it’s up to us to initialize it: we push an element “token” to the my_mutex list.

This token is the key to the mutex: the process that removes the token from the list has locked the mutex. If the token is back on the list, the mutex is unlocked and another process can claim it and start working. This is accomplished in the next three lines.

BLPOP tries to pop the token off the my_mutex list. If the list is empty, it will block until another process pushes the token on it. Redis puts multiple BLPOP’s in a FIFO queue, so whoever calls BLPOP first, will be the first to actually get the token once it arrives.

Once the BLPOP returns, it means we have the token so we can do some work. Afterwards we push the token back on the list, unlocking the mutex.

Creating a semaphore instead of a mutex is as simple as pushing multiple tokens on the list during initialization. If you push on five then five processes will be able to lock the semaphore at a time.