Design a lock and coordination service

A lock and coordination service is a small, strongly consistent store that many processes use to agree on who holds a lock, who leads a group and what the current configuration is. It replicates every change through a consensusconsensus: Agreement among a group of servers on one ordered log of values, reached by majority vote, so that every committed value survives the failure of any minority of the servers. More in “Consensus in practice: what Raft gives you” group of about five servers, so it keeps working while a minority of them fail. Clients hold sessions that they keep alive with heartbeats; locks and membership keys belong to a session and vanish when it expires; watches tell clients when something changes; and every grant carries a fencing tokenfencing token: A number that rises every time a lease or leadership changes hands. The storage refuses a write that carries a lower token than one it has already accepted. More in “Failover, split brain and fencing” that the protected resource checks. Interviewers ask you to design a lock service to hear what pauses, partitions and failovers do to it. Chubby, ZooKeeper and etcd are the best-known examples.

Requirements and estimate: keepalives, not locks, load the cell

A company runs 2,000 services, each with about 60 processes spread over three zones of one region. Schedulers need one active leader per job, deploy tools take maintenance locks, every process announces that it is alive, and routing tables live in small configuration keys. Before you design a lock and coordination service for them, ask:

• What will clients use it for: locks, leader electionleader election: Choosing one process out of several to do a job alone, usually through a coordination service, with a lease so that a crashed leader is replaced without anyone's help. More in “Leader election, leases and fencing tokens”, membership or configuration?
• How many client processes are there, and how often does a lock change hands?
• How quickly must a dead holder’s lock reach the next process?
• Must every read see the latest write?
• One region or several, and what should a client do when it cannot reach the service?

The answers here: 120,000 client processes, 5,000 locks that change hands about ten times a day each, a dead holder replaced within about 15 seconds, reads of lock state that are never stale, and one region with three zones.

Functional requirements: open and keep alive a session; acquire and release a lock, waiting in a queue; ephemeral keys that vanish with their session; watches on keys and prefixes; small keys with conditional writes; a fencing token with every grant. Non-functional requirements: never two holders as far as a resource that checks tokens can tell; survive the loss of any one zone; acquire within about 20 ms inside the region; and clients that stop acting as holders before the service can give their lock away.

The first estimate:

# A first load estimate for the lock and coordination service of this lesson. Every input is an assumption to
# replace with numbers from your own fleet: the process count from your deploy system, handovers from the service's
# own logs, and watchers from how your client libraries use watches.
SERVICES = 2_000
PROCESSES_PER_SERVICE = 60      # one session each, 20 in each of 3 zones
ZONES = 3
TTL_S = 12                      # session lease
RENEWALS_PER_TTL = 3            # renew three times per lease, so one lost reply is not fatal
LOCKS = 5_000                   # locks and leader elections in use
HANDOVERS_PER_DAY = 10          # times a lock changes holder on a normal day
ENTRY_BYTES = 200               # a session, lock or membership key with its metadata
CONFIG_KEYS, CONFIG_BYTES = 10_000, 4_000

clients = SERVICES * PROCESSES_PER_SERVICE
keepalives = clients * RENEWALS_PER_TTL / TTL_S
writes = LOCKS * HANDOVERS_PER_DAY / 86_400
entries = clients + LOCKS + clients        # sessions, locks, one membership key per process
state_mb = (entries * ENTRY_BYTES + CONFIG_KEYS * CONFIG_BYTES) / 1e6

per_zone = PROCESSES_PER_SERVICE // ZONES
lost = SERVICES * per_zone                 # the sessions of the zone that fails
survivors = PROCESSES_PER_SERVICE - per_zone
events = lost * survivors                  # each survivor watches its own service's members

print(f"clients: {SERVICES:,} services x {PROCESSES_PER_SERVICE} processes = {clients:,} sessions")
print(f"keepalives: each renewed every {TTL_S // RENEWALS_PER_TTL} s = {keepalives:,.0f} a second, all at the leader")
print(f"normal writes: {LOCKS:,} locks x {HANDOVERS_PER_DAY} handovers a day = {writes:.1f} a second")
print(f"state: {entries:,} entries x {ENTRY_BYTES} B + {CONFIG_KEYS:,} config keys x {CONFIG_BYTES:,} B = {state_mb:.0f} MB")
print(f"one zone fails: {lost:,} sessions expire within {TTL_S} s = {lost / TTL_S:,.0f} expiry writes a second")
print(f"  about {round(LOCKS / ZONES):,} locks change holder; {events:,} membership watch events reach the survivors")

clients: 2,000 services x 60 processes = 120,000 sessions
keepalives: each renewed every 4 s = 30,000 a second, all at the leader
normal writes: 5,000 locks x 10 handovers a day = 0.6 a second
state: 245,000 entries x 200 B + 10,000 config keys x 4,000 B = 89 MB
one zone fails: 40,000 sessions expire within 12 s = 3,333 expiry writes a second
  about 1,667 locks change holder; 1,600,000 membership watch events reach the survivors

The locks are the smallest load, well under one write a second. Keepalives, 30,000 a second, all land on the leader, and the loss of one zone turns into 3,333 expiry writes a second and 1.6 million watch events. The whole state fits in memory on every server.

Follow one lock through the cell:

The choices still open, each with its plain meaning:

• A replicated log: every change becomes an entry that a majority of servers stores before any server applies it.
• Sessions with keepalives: a client proves that it is alive by renewing a leaselease: A time-limited right to act, as a leader or as the holder of a lock. The holder may act only while the lease lasts, and no successor starts before it has expired. More in “Failover, split brain and fencing” on its session.
• Ephemeral keys: keys that the service deletes when the session that created them ends.
• Waiter queues: each waiting client owns one entry and watches the entry just ahead of it.
• Fencing tokens: a number that grows with every grant, which the protected resource checks.
• Watches: notifications of changes to a key or a prefix, resumable from a revision.
• A grace period: time a client waits without acting before it gives up on its session.
• Proxies: servers that carry many clients’ sessions to the cell as a few.

The deep dives that decide whether this design works:

1. What does each call write to the log, and where does the fencing token come from?
2. How long should a session last, and what must a client do when it stops hearing from the service?
3. What happens to sessions and locks when the leader fails?
4. How do 200 clients wait for one lock without a stampede, and what if the reply to an acquire is lost?
5. How are reads kept up to date without sending every read through the log?
6. How does one cell serve 120,000 processes, and where does it stop scaling?

An answer is judged on requirements and estimates, the replicated state machine, sessions and expiry, client behaviour during failures, fencing, and scaling.

The holder’s create revision is its fencing token Pro: opens with a Pro, Premium or Ultimate pass