Recipe: Semaphore #44

eric opened this Issue Aug 27, 2012 · 3 comments

3 participants

zk-ruby member

I haven't been able to find a description of an implementation of a semaphore that I like, so I'm going to try to work this one out.

An obvious use of a semaphore would be to restrict concurrent access to a resource (for things like preventing too many workers from hitting the same database or website).

My thoughts on the semaphore would be that it would take a name and a size. Any clients that attempt to acquire the semaphore that are more than the size limit will block until a slot is available.

I don't have a strong opinion between using acquire/release vs wait/signal for the method names.

There are two obvious ways to implement this:

1. The more efficient approach

Like a lock, have each client wait for the sequential znode below them and wait for the watcher to fire.

The problem with this is if you have a size of 10, and 20 clients, none of the clients above 10 will progress until the 10th one completes.

2. The more immediate approach

Watch for any changes to the parent znode and recalculate the clients position each time.

The downside of this is it will cause all clients to be awoken when any client releases. In reality, if there is not a large number of clients waiting, it should provide for a better experience.

I'm hoping there's another obvious solution I'm missing here.

After reading the code to the netflix curator recipe for a semaphore, it looks like they opted for approach 1, but didn't specifically call out the behavior:


as discussed in #zk-gem, the answer to the first is for all participants who are waiting to acquire a semaphore with a limit of N, to watch N nodes in front of it. When there are < N nodes in front, the semaphore has been acquired and you clear all watches.

The algorithm works like:

  • agree on the size of the semaphore (N)
  • Acquire a sequential ephemeral node under the semaphore path, the integer value of the node is I
  • (A) if there are < N count nodes with an I < the one we have, you hold the semaphore and continue
  • otherwise, set a watch on N nodes < your I and wait for deletion.
  • on deletion go to (A)

so with a semaphore size of 3:

node list:

 009 008 007 006 005 004 003 002 001 000

if you "hold" ephemeral 006
 009 008 007 006 005 004 003 002 001 000
                  ^   ^   ^
                  watch these

As soon as any of your watches fire, you check to make sure that there < N nodes lower than yours (because the holder of 003 may have dropped off for some reason).

 009 008 007 006 005 004 001 000
                  ^   ^  

There are more than 3 nodes with a lower number, so watch the nearest 3

 009 008 007 006 005 004 001 000
                  ^   ^   ^
                          set this watch

event fires, check again

 009 008 007 006 005 004
                  ^   ^

Ok! There are only 2 lower than us, and N = 3, so we hold the semaphore.

@yaauie yaauie added a commit that referenced this issue Nov 16, 2012
@yaauie yaauie Add support for semaphore pattern in Locker by supporting optional :m…
…ax_locks parameter on shared locks; solution to slyphon/#44

@slyphon I was able to implement the pattern you posted above as an optional :max_locks parameter on SharedLocker. I had to refactor a few things a fair bit to get it to be completely compatible with what you had previously, especially in ZK::NodeDeletionWatcher since watching one node (existing code) was a specific subset of watching multiple nodes.

I don't entirely expect you to merge in as-is, but hopefully this is a decent start. (Tested on MRI 1.9.3-p194 against zookeeper-3.4.4)


#56 has been merged, so this one is done ⛵️

@eric eric closed this Jul 4, 2013
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment