I'm trying to understand the fair semaphore implementation from the Redis In Action book. I couldn't figure out how this implementation prevents a specific race condition. The implementation is as follows:
def acquire_fair_semaphore(conn, semname, limit, timeout=10):
identifier = str(uuid.uuid4())
czset = semname + ':owner'
ctr = semname + ':counter'
now = time.time()
pipeline = conn.pipeline(True)
pipeline.zremrangebyscore(semname, '-inf', now - timeout)
pipeline.zinterstore(czset, {czset: 1, semname: 0})
pipeline.incr(ctr)
counter = pipeline.execute()[-1]
pipeline.zadd(semname, identifier, now)
pipeline.zadd(czset, identifier, counter)
pipeline.zrank(czset, identifier)
if pipeline.execute()[-1] < limit:
return identifier
pipeline.zrem(semname, identifier)
pipeline.zrem(czset, identifier)
pipeline.execute()
return None
The main feature of this implementation (ignoring for now the timeout logic) is it atomically increments a counter, then inserts a new UUID into a sorted set, using the value of the counter it just incremented as the score, and then uses the rank of the UUID in the sorted set to determine if it acquired the semaphore.
However I see that this implementation has two pipeline.execute() calls, meaning it uses two separate transactions, which means, two concurrent requests to acquire the semaphore can have their 4 total transactions interleaved. Critically, the call to increment the counter is in the first transaction, while the call to insert the UUID into the sorted set is in the second transaction. So it should be possible to have an interleaved sequence of operations as follows:
A increments counter -> B increments counter -> B inserts into sorted set -> A inserts into sorted set
Suppose, before this sequence of steps, the semaphore has only 1 permit remaining to issue, and the counter has a value of 100. Then, A receives a counter value of 101, and B receives a counter value of 102. Then, when B inserts its UUID, it believes it has acquired the semaphore (because A hasn't inserted yet, so B receives a rank within the limit), then A inserts its UUID, it also believes it has acquired the semaphore (because A has a score lower than B so it receives the same rank as B received earlier).
Is there anything in this implementation that prevents this race condition?