System requirements

Functional:

• Client can acquire locks (optionally with TTL). When client acquires a lock, no other clients can acquire the same lock
• Client can release locks

Non-Functional:

• Strong consistency: when one client acquires a lock, it is immediate visible to other clients
• High availability. The system is resilient to failures (hardware, network, client / server failures)
• System should prevent deadlocks
• System support up to 1M locks, with 100 concurrent clients for each lock, total 100k clients
• Latency of acquiring lock (if successful) and releasing locks < 5ms.

Capacity estimation

Storage

• We choose a redis based implementation. Each lock is a single key up to 128b. 1M key = 128Mb

Network

• Up to 100 qps per lock
• 100k clients 1 request/min = 100k / 60 = 2k qps

This is within the capacity of 1 redis cluster without sharding.

API design

lock(client_id, name, ttl=inf) // wait for lock to be acquired

try_lock(client_id, name, timeout=0, ttl=inf) // Return if lock is not acquired within timeout

boolean release_lock(client_id, name) // true if the lock was acquired by this client

boolean refresh_lock(client_id, name, ttl=inf)

Database design

Redis option:

• acquire lock: set(key, client_id, nx=true, ttl)
• release lock: in a LUA script to ensure atomicity

if (get(key) == clientid)

delete(key)

• We can use the Redlock protocol for additional reliability (quorum based locking)

Zookeeper option:

• Create a node that all clients agree with (e.g. /lock/<name>)
• When client try to acquire a lock, it creates a ephemeral sequential node
• Then it checks if it owns the lock with the lowest sequence number. If yes, the lock is acquired
• Otherwise, it sets a watch on the node, and waits until it get notified and verifies that it owns the node with the lowest sequence number

High-level design

The graph depicts the redis based option. Client calls redis API directly. In the case of releasing the lock, the script is wrapped in a LUA script to ensure atomicity.

Request flows

The request flow is pretty simple. The client initiates direct call to redis or zookeeper.

Detailed component design

For the redis option, for better reliability we should stand up N redis clusters/masters in high availability mode.

How to avoid deadlock:

• The client should acquire locks in order which will prevent deadlocks
• As a good practice, the client should acquire locks at the beginning of the process

The TTL can alleviate deadlocks.

Trade offs/Tech choices

Redis vs Zookeeper

• Redis is generally faster and easier to manage. The downside is that the single cluster mode it can go down and become available. In high availability mode it is not strongly consistent. Even in Redlock mode it is theoretically not strongly consistent.
• Zookeeper is strongly consistent. In addition, it has the benefit of fair allocation of locks.
• In addition, Zookeeper's monotonically increasing node number can serve as fencing tokens, that can prevent situations where a client is frozen perhaps due to garbage collection.

Failure scenarios/bottlenecks

Zookeeper's Paxos-like protocol is fault tolerant against server failures, network partitions. However, it is computationally more intensive. We can shard zookeeper if needed.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?