Distributed Locking Service

ZooKeeper / etcd

Design a lock service that many teams use to make sure only one process at a time works on a job, a file or a leader role, which keeps working when machines crash or the network splits.

Overview

A distributed lock lets processes on different machines agree that only one of them does something at a time: runs tonight's billing job, writes a shared file, or acts as the leader of a service. Inside one process a mutex does this; across machines it is harder because any participant can crash, pause or lose the network at any moment, and nobody can tell a dead client from a slow one.

The design splits into two parts. A small lock service, replicated with a consensus protocol, decides who holds each lock and survives server failures. Sessions with leases free the locks of clients that stop responding. Then comes the honest part: a lease can expire while its holder is paused and still believes it holds the lock, so a lock that protects data must hand out fencing tokens that the protected resource checks. Why that is needed and how resources check tokens is covered in the Fencing topic; here we build the service that issues them.

Interviewers use this problem to test whether you know the difference between a lock that saves duplicate work and one that protects correctness, why a single Redis key or a failover pair is not enough for the second kind, and how systems such as ZooKeeper and etcd implement locks.

Questions to ask first

What do the locks protect? — Both kinds: saving duplicate work, and data that must not be corrupted
How many clients and locks? — 50,000 client sessions; about 100,000 locks held at once
How often are locks taken? — 5,000 grants a second on average, 15,000 at peak
How fast must a dead client's lock free up? — Within about 10 seconds
Fair order for waiters? — Yes, first come, first served
Across regions? — No: one region, three zones
Latency to take a free lock? — A few milliseconds inside the region (a target we chose)

What you will be able to do

Say which locks need consensus and fencing, and which do not.
Build lock grants on a replicated log, with the log index as the fencing token.
Size sessions, leases and keepalives, and say what happens in a leader failover.
Queue waiters fairly without waking every client on each release.
Compare a database row, a Redis key, Redlock and a ZooKeeper or etcd lock.

Key concepts

Consensus (Raft, ZAB)
Quorum of 3 out of 5
Sessions and leases
Keepalives
Fencing tokens from the log
FIFO waiters
Watch the predecessor
Redlock trade-offs
Efficiency vs correctness locks

Functional requirements

Open a session with a lease; keep it alive with keepalives
Acquire a named lock, waiting up to a timeout; get a fencing token with each grant
Release a lock; only the holder can
Release every lock of a session whose lease runs out
Grant a lock to waiters in the order they asked
Show who holds a lock and who is waiting

Non-functional requirements

Safety first: at most one session holds a lock at a time, as seen by the service
Tokens only grow, so a resource can reject an older holder
Keeps granting locks with up to 2 of 5 nodes down
A dead client's locks free up within about 10 seconds (the lease TTL we chose)
Taking a free lock costs a few milliseconds inside a region (a target we chose)

Interview questions

Why not just use SET NX with a TTL in Redis?
Does Redlock fix that?
How does the service free the lock of a client that crashed?
What happens when the lock service leader fails?
How do you implement fair locking without a thundering herd?
How would you do leader election with this service?
The lock service is the bottleneck. How do you scale it?