There's a famous Redlock algorithm ([1], [2]) by antirez (Salvatore Sanfilippo) that describes how to implement distributed locks using several Redis instances for redundancy. It provides (to a certain degree) both reliability and availability by requiring a quorum of available Redis instances to mark a key as locked.
It works great in practice, but has a drawback: it only supports a single lock holder at any moment of time, i.e. it implements mutual exclusion. For one of my projects, I needed to be able to support either multiple readers or a single writer, i.e. an RW-lock.
Turns out, Redlock can be extended to support that.
The idea behind Redlock is simple: generate a random-generated lock token and store it in in a key in Redis. Each lock acquisition attempt gets a new token and attemps to write into a key in all Redis instances. If the node was able to do a conditional write of that token into a Redis key (on at least a quorum of instances), then the locking attempt was successful.
To extend this algorithm to support multiple readers, we'll have the following storage:
w_{LockKey} that stores the random-generated token if the writer part of the lock is acquired.
Its expiry date is set to automatically release the lock upon reaching TTL.r_{LockKey} that stores sorted of random-generated tokens for readers.
The key for the sorted set is the expiration time of a particular token.To acquire a write lock, the following steps need to be performed:
r - a random-generated stringw_{LockKey} exists: lock acquisition failedr_{LockKey}r_{LockKey} is non-empty: lock acquisition failedr into w_{LockKey}, using expiration time as sort keyw_{LockKey} predicated on it being equal to rTo release the lock, delete the key w_{LockKey} (if its value is equal to r).
The following LUA script implements locking:
local r_key = KEYS[1]
local w_key = KEYS[2]
local tok = ARGV[1]
local now = tonumber(ARGV[2]) -- milliseconds since Unix epoch
local ttl_ms = tonumber(ARGV[3]) -- in milliseconds
redis.call('ZREMRANGEBYSCORE', r_key, 0, now)
if redis.call('ZCARD', r_key) > 0 then
return 2 -- key is read-locked
end
if redis.call('GET', w_key) ~= false then
return 3 -- key is write-locked
end
redis.call('SET', w_key, tok, 'PX', ttl_ms)
return 1 -- write lock acquired
Unlocking is done by DELEX w_{LockKey} IFEQ {r}
To acquire a read lock, the following steps need to be performed:
r - a random-generated stringnow - current timestamp, represented as milliseconds since Unix epochw_{LockKey} exists: lock acquisition failedr with sort key now into r_{LockKey}r from r_{LockKey}The following LUA script implements locking:
local r_key = KEYS[1]
local w_key = KEYS[2]
local tok = ARGV[1]
local exp_at = tonumber(ARGV[2]) -- now + ttl, expressed as milliseconds since Unix epoch
local get_result = redis.call('GET', w_key)
if get_result ~= false then
return 2 -- key is write-locked
end
redis.call('ZADD', r_key, exp_at, tok)
return 1 -- read lock acquired
Unlocking is done with ZREM r_{LockKey} {r}.
I've tested this algorithm using randomized testing with model-based verification, and it found no errors.
Correctness is based on the same idea as the original Redlock: any two concurrent lock acquisition attemps will meet on at least one Redis instance (because quorum is strictly greater than the number of Redis instances), and the state stored in r_{LockKey} and w_{LockKey} will ensure that at most one of attempts succeed.
In the worst case, both lock attemps will fail and require retries with randomized delays.
In this algorithm, readers can easily starve writers.
If this is an issue, then it possible to extend this algorithm with fairness.
The basic idea is that we store a FIFO queue of lock attempts in a separate redis key fair_{LockKey}. That queue is only used during locking process if:
Once the queue is drained, the lock becomes unfair.