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.
I was searching to see if anyone had used Redis for semaphores and found your post. I had already been looking at the blocking list commands, and it's good to see someone thinking in the same way.
The only thing I'd change, based on the pseudocode, is that in the top IF, I would wrap that LPUSH in a MULTI and WATCH to make sure two connections don't LPUSH two "first" entries onto a new list.
Hey Matt,
Thanks you like it!
Actually, since we're using GETSET, it guarantees only one process will ever LPUSH the first entry. Since that command is atomic, only the first process to execute it will receive 0, all other processes will receive the 1 set by the first process, and thus won't execute the LPUSH.
Gret stuff, thanks!
I was searching for posts on Redis-based semaphores. Your idea for dynamically initializing it is slick! Thanks for writing this!
Unfortunatly this mutex is not failsafe, so if the client which holds the mutex dies, the mutex isn't freed. Other processes have to wait until the blocking operation times out, and after the timeout the mutex' state is undefined.
Hmmm, I agree with you.
I see the problem in your solution.
List that is used for blocking of execution may contain several items, let say N, in this case N processes can run simultaneously without locking. But execution of N+1… will be blocked.
Also second concurrent process can pass BLPOP without blocking even if it fails to set my_mutex_start. First process will be blocked even if it setup up my_mutex_start.
“Unfortunatly this mutex is not failsafe…”
we can use SETxx with specified expiration time.
Excellent article written by the author to express views and explanations related to the subject. Thanks for your great efforts.goto