Design a Distributed Locking Service

The ask

Services on many machines sometimes need one-at-a-time access to something. Examples are rebuilding a shared index or settling one account at a time. Two holders at once would corrupt the shared thing.

A lock is taken by name. The name stands for the protected resource, not for a machine. Any machine can ask, and exactly one holds the lock at any moment.

Holders crash and networks stall. The lock must free itself when a holder dies. It must also protect the resource from a holder that wakes up late.

Callers accept a wait or a refusal. Acquire can answer at once with no. Callers that need the lock retry later instead of queueing inside the service.

Estimate the scale

The service takes 10,000,000 lock acquisitions a day.

10,000,000 acquisitions / 86,400 seconds = 116 acquisitions per second on average.

The rate is small. Correctness is the entire difficulty. One wrong grant can corrupt the resource the lock exists to protect.

Lock names hash across 20 shards inside the service. Each shard then handles about 6 acquisitions per second on average, with strong agreement on every grant.

API and data

Acquire takes a lock name and the caller's identity. A successful answer returns a fencing token. A failed answer says the lock is held and suggests waiting before a retry.

Renew takes the lock name, the caller's identity and the fencing token. It extends the lease when all three match the record. Release takes the same fields and frees the lock early.

One lock record holds the name, the current holder, the lease expiry and the fencing token. The record lives on the shard that owns the name. There is one record per lock, never two.

The fencing token is a number that grows with every grant of that lock. The first grant carries a small token. Each later grant carries a larger one, and tokens are never reused.

High-level design

Lock names hash to shards, and each shard has one leader. The leader alone grants locks for its names. Followers copy every grant the leader makes.

A grant is written with consensus among the shard's copies before it counts. That agreement is what makes one record trustworthy. A leader that loses contact with its copies stops granting.

The caller talks to the shard leader for its lock name. One round trip grants, renews or releases. The caller then does its protected work and presents the fencing token with every write to the resource.

Shard leaders are few and their load is light. The worked rate per shard is about 6 grants per second. Headroom goes to bursts, not to steady load.

Leases and renewal

A lock lease lasts 10 seconds. The grant expires at that mark unless renewed. Expiry needs no message from the holder, so a crashed holder frees its lock automatically.

The holder renews every 3 seconds. Renewal sits well inside the lease. A holder can miss a renewal and still hold the lock.

Renewal fails when the record no longer matches. A failed renewal tells the holder it lost the lock. The holder must stop its protected work at once.

Short leases free locks quickly after crashes. They also add renewal traffic and punish slow holders. Ten seconds balances those pressures at the worked scale.

Deep dive: the paused holder

A holder can pause without crashing. A long runtime pause or a stalled network can freeze it past its lease. The service rightly gives the lock to the next caller.

The paused holder then wakes and writes to the resource. It still believes it holds the lock. Without a guard, two holders write at once, and the lock has failed at its one job.

The guard is the fencing token. Say the first holder carries token 41. The second holder receives token 42, one larger, and writes with it.

The resource remembers the largest token it has accepted, here 42. The woken holder presents 41, which is smaller. The resource rejects the write, and the stale holder learns it lost the lock.

Fencing only works when the resource checks. Every protected write carries its token. A resource that skips the check gets no protection, however good the lock service is.

When the lock service is down

A network partition can cut callers off from a shard leader. Those callers cannot acquire or renew. Their leases expire and their protected work stops.

That behaviour is the safe side of the trade. The service chooses correctness over availability. Work pauses rather than risking two holders.

Holders already inside their lease keep a shrinking window. Prudent holders stop writing before the lease ends when renewals fail. The fencing token guards any write that still slips out.

Copies inside the shard keep the record through single machine failures. Only a partition that isolates a caller from the shard stops that caller. The record itself survives.

Evaluation and trade-offs

A distributed lock buys one-at-a-time access across machines. The price is a dependency on the lock service for every protected action. Callers must design for the service being unreachable.

Leases trade freedom against safety. Longer leases forgive slow holders and delay crash recovery. Shorter leases recover fast and churn more renewals.

Many supposed lock needs are really queue needs. Work that can wait its turn belongs in a queue, where order is the mechanism. Locks fit work that must happen now or not at all.

The fencing token is the design's honest core. The lease alone cannot stop a paused holder. Token checks at the resource complete the guarantee.

One lock record