Hard · 12 steps · ~75 min

Design a distributed lock and leader election

Mutual exclusion that survives crashes, pauses and failovers.

Many machines must agree that exactly one of them does a job at a time: run the nightly report, own a shard, or be the leader. Design a lock and leader-election service that stays correct when holders crash, freeze for 40 seconds, get partitioned or when its own storage fails over, while handling tens of thousands of lease renewals a second.

Same problem as ZooKeeperetcdGoogle Chubby

How it works

• Acquire: a client gets a lease and a fencing token if the lock is free.
• Renew: the holder heartbeats before the lease expires.
• Elect: a leader is just the holder of a well-known lock, with a term that increases.

What you'll build

1. The API (acquire, renew, release) and the lock schema
2. A replicated, consensus-style store that survives losing the leader
3. A sharded namespace for 30,000 requests a second
4. A limiter and a breaker against herds and cold caches
5. Reasoning about leases, fencing tokens and durability

Steps

1. 1Design the API
2. 2Design the data model
3. 3Handle 500 lock requests/sec
4. 4Why a lease and not a plain lock?
5. 5Replicate the store for $1,100
6. 6Lose the leader
7. 7Fencing tokens
8. 8Scale writes to 30,000 requests/sec for $1,600
9. 9Why a consensus-backed store?
10. 10Retry storm after a release for $1,500
11. 11Write-behind caching for lease renewals?
12. 12Cold cache after a restart