Distributed Lock Service System Design

A distributed lock service is a small, highly-available, strongly-consistent coordination primitive that lets independent processes across a fleet acquire and release named locks, register watches on shared state, and elect leaders without each application reinventing fragile coordination protocols. The design problem is famously tricky: locking across a network is fundamentally different from locking within a process, because the network can lose a message, a holder can die without releasing, or a stale holder can resurface long after others have given up on it. The canonical industrial deployments are Google’s Chubby (Burrows, OSDI 2006 — the original “lock service” paper, used inside Google for GFS master election, Bigtable tablet management, and BNS service-naming), Apache ZooKeeper (Hunt et al. ATC 2010 — Yahoo!‘s open-source descendant of Chubby’s design, used in Hadoop, Kafka, HBase, Solr), and etcd (CoreOS / Red Hat — Raft-backed, used by Kubernetes itself for cluster state and leader election). All three implement the same model at heart: a small replicated state machine (5-7 nodes via Raft or Paxos) holding a hierarchical filesystem-like namespace where files become locks, ephemeral nodes become liveness signals, watches notify on change, and lease semantics auto-release on client disconnect. Building a correct distributed lock is hard enough that the answer in production is almost always don’t: use one of these services. This note covers what they do, why a typical “Redis-based lock” gets it wrong (Kleppmann’s famous 2016 critique), and how to use the service correctly for the standard use cases — leader election, configuration coordination, group membership, distributed cron.

1. Why This System Appears in Interviews

The distributed lock service is the textbook test for whether a candidate has internalized the core distributed-systems lesson: the network is not reliable, the clock is not synchronized, and a process you cannot reach is not necessarily dead. Every “let’s just use a Redis SETNX with a TTL” answer reveals a candidate who hasn’t fully grappled with split-brain — and the interviewer can probe deeper for the fencing token that makes the lock truly safe. Beyond this trap question, the topic exercises:

• Replicated state machines via Raft or Paxos High-Level — the lock service is the most concrete and useful application of consensus.
• Lease semantics — leases are how you recover from a holder that has died without holding a meeting. The lease is the single most important idea in this entire space.
• Watch / notify primitives — the change-detection mechanism that turns a polling pattern (wasteful) into an event-driven one.
• Hierarchical namespace — files-and-directories model, but with a twist (ephemeral and sequential nodes) that makes it different from a normal filesystem.
• Failure-domain reasoning — why 5 or 7 nodes (not 2, not 3, not 100), why they should be in different availability zones, why writes go to the leader, why reads can be local-but-stale.

A senior interviewer can spend 45 minutes on just the lock-service primitives and the canonical recipes (leader election, double-checked-locking, group membership) and never run out of follow-ups. This note covers each in narrative depth.

2. Requirements

2.1 Functional Requirements

1. Lock acquisition. Acquire a named lock. The lock has an owner (which client holds it) and a lease (how long the lock is valid before auto-release).
2. Lock release. Explicit release by the owner. Implicit release on lease expiry or client disconnect.
3. Hierarchical namespace. Locks (and other coordinated state) are organized as a filesystem-like tree: /services/users/leader, /configs/featureflags/v3, /jobs/cron/nightly-etl. This grouping makes it easy to reason about subtrees (“watch all children of /services”).
4. Watch / notify. A client may register interest in a path; the service notifies the client when the path’s data or children change. The notification is one-shot (re-watch to keep watching) — this avoids livelock.
5. Atomic compare-and-swap. Conditional updates: “set this node’s value to V iff its current version is X.” This is how you implement counters, latches, and optimistic concurrency.
6. Ephemeral nodes. A node tied to the client’s session — auto-deleted when the session ends. Combined with sequential numbering, ephemeral sequential nodes are how leader election is implemented (lowest sequence wins).
7. Linearizable reads (optional). Reads observe the latest committed state. Without this, reads see slightly stale state from a follower and clients must tolerate that. ZooKeeper offers sync()-then-read for linearizable reads at higher cost; etcd offers quorum=true reads.
8. Group membership. A standard recipe: each member creates an ephemeral child in a known parent path; the children list is the group; ephemerals disappear when members fail.

2.2 Non-Functional Requirements

1. Strict consistency. Linearizable writes — every committed write is visible to every subsequent successful read in real time (modulo the optional sync-read above). This is the entire point.
2. High availability under minority failures. With 2f+1 replicas, the service tolerates f simultaneous failures. Practical deployments: 5 replicas (tolerates 2), 7 replicas (tolerates 3). Three is the minimum but tolerates only 1 and is widely considered too thin for production.
3. Acquire latency. Within a data center, lock acquisition typically completes in 10-100 ms depending on Raft commit latency. Cross-data-center deployments can take 100-500 ms (the price of cross-region replication).
4. Throughput. Tens of thousands of writes per second (the leader is the bottleneck — every write goes through Raft commit). etcd’s own performance documentation states that a three-member cluster on commodity cloud hardware “can complete more than 30,000 requests per second under heavy load,” and “finishes a request in less than one millisecond under light load” (etcd Performance docs). Its published benchmark shows the throughput climbing from 583 QPS with a single connection and single client to roughly 50,000 QPS with 100 connections and 1,000 concurrent clients — the gain coming entirely from request batching, since per-request commit latency is fixed by physics (see §8.3). Reads scale with replicas, more if you accept stale reads.
5. Durability. Every commit is durable on a quorum’s disks before being acknowledged. After a power loss to a minority, no commits are lost; after a power loss to a majority, the cluster is unavailable until majority is restored.

3. Capacity Estimation

A lock service is small relative to the systems it coordinates. Consider its load in a typical cluster:

3.1 Workload Profile

Suppose a Kubernetes cluster of 10,000 pods uses etcd (for cluster state) plus runs application-level coordination:

• Pod state changes (create, delete, update): ~1000 writes/second at deploy time, ~10/second steady state.
• Lock acquisitions for periodic jobs: 100/minute = 1.67/second.
• Leader-election leases for ~50 elected services: each lease renews every 5 seconds → 10/second.
• Configuration reads (feature flags, etc.): 10,000 reads/second total across the fleet.

Total: ~10K reads/s, hundreds of writes/s. Easily within a single 5-node etcd cluster’s capacity.

3.2 Storage Sizing

Each Kubernetes object in etcd: ~5-50 KB serialized, with multiple historical versions retained:

10,000 pods × 30 KB avg × 10 historical versions = 3 GB
plus 50,000 other objects × 5 KB × 10 versions  = 2.5 GB
plus headroom and Raft log                       = ~10 GB

etcd’s default storage quota (--quota-backend-bytes) is 2 GiB, and its documentation recommends 8 GiB as the practical maximum — the server logs a startup warning if the configured quota exceeds that ceiling, and performance degrades as the backing B+ tree grows (etcd system limits). When the quota is hit, etcd raises a NOSPACE alarm and refuses further writes until space is reclaimed, so periodic compaction (discarding historical revisions older than a bound) plus defragmentation (returning freed pages to the filesystem) is mandatory operational hygiene, not optional tuning.

3.3 Why 5 Nodes (Not 3, Not 7)

The choice of replica count is governed by the consensus quorum math. With N replicas:

• Quorum size = ⌊N/2⌋ + 1
• Tolerates ⌊(N-1)/2⌋ simultaneous failures

N	Quorum	Tolerates
3	2	1
5	3	2
7	4	3

Three nodes tolerate one failure, which sounds adequate but is brittle: a single network partition isolating one node, plus a coincident failure of another, leaves the cluster unavailable. Five nodes tolerate two simultaneous failures — survives one node down for maintenance plus an unexpected failure. This is the production sweet spot for most deployments. Seven nodes add expensive consensus overhead (every write must reach four nodes, more cross-AZ network) for a marginal availability gain; reserved for very-large deployments where two zones routinely fail simultaneously.

Even-numbered counts (4, 6) are strictly worse than the next-lower odd: 4 has the same tolerance as 3 but a larger quorum (3 instead of 2), so it’s strictly slower with no availability benefit. Always odd.

4. API Design

The three production lock services have similar APIs. etcd’s modern API is the cleanest example.

4.1 etcd v3 Lock and Lease API

# Create a lease (TTL in seconds)
LeaseGrant(ttl=30) → lease_id=0xabc123

# Keep-alive: refresh the lease before TTL expires
LeaseKeepAlive(lease_id=0xabc123) → ack (refreshes TTL)

# Acquire a lock (etcd's Lock RPC creates an ephemeral key tied to the lease)
Lock(name="/locks/order-processor", lease_id=0xabc123) → key="/locks/order-processor/abc123"

# Unlock (delete the key)
Unlock(key="/locks/order-processor/abc123") → ack

# Atomic put with compare-and-swap
Txn:
  if Compare(key="/state/leader", target=Version, value=42):
    then Put(key="/state/leader", value="me")
  else fail

# Watch a key range
Watch(key="/configs/", range_end="/configs0") → stream of events

# Get with revision, for snapshot reads
Range(key="/configs/featureflag", revision=12345) → value, latest_revision

A lease is the atomic mechanism that ties a session to held locks. Releasing a lease (or letting it expire) atomically releases everything the lease owns.

4.2 ZooKeeper API

create(path="/locks/order-processor/lock-", data=ip:port, flags=EPHEMERAL_SEQUENTIAL)
  → returns "/locks/order-processor/lock-0000000017"

getChildren("/locks/order-processor", watch=true) → ["lock-0000000017", "lock-0000000018"]

# Standard leader election: I become leader iff my created node has the smallest sequence number
exists("/locks/order-processor/lock-0000000016", watch=true)  # watch the predecessor

# Watch fires → check children again
delete("/locks/order-processor/lock-0000000017")

ZooKeeper’s API is more primitive (no built-in lock RPC) and the lock pattern is built on top via ephemeral sequential nodes. This means clients implement the recipes (see §8.1) — the upside is flexibility, the downside is bug surface.

4.3 Chubby API (per the 2006 paper)

Open(path="/ls/celltest/some-lock", flags=Lock|Read|Write)
TryAcquire(handle, mode=Exclusive|Shared)
Release(handle)
SetContents(handle, data)
GetContentsAndStat(handle)
Acl(handle, ...)

Chubby’s API exposed POSIX-file-style operations and (importantly) session-based notifications — when the session breaks, the client knows and must take responsibility for what its handles owned.

5. Data Model

5.1 The Hierarchical Namespace

All three services expose a tree:

/
├── services/
│   ├── users/
│   │   ├── leader        ← elected leader's identity
│   │   └── replicas/
│   │       ├── 1         ← ephemeral; auto-deleted on disconnect
│   │       ├── 2
│   │       └── 3
│   └── orders/
│       └── leader
├── locks/
│   ├── nightly-etl       ← exclusive lock; only one client holds at a time
│   └── deploy-coordinator
└── configs/
    └── featureflags/
        ├── v3
        └── v4

Each node has:

• Path (the key).
• Data (a small blob; etcd’s default --max-request-bytes is 1.5 MiB and ZooKeeper’s default jute.maxbuffer caps a single znode at roughly 1 MiB — both can be raised, but the documentation warns that large values inflate the latency of every other request, so values are expected to be tiny (etcd system limits)).
• Stat (metadata: version, ctime, mtime, owner, ephemeral-or-not, children count).

5.2 Node Types

• Persistent. Survives client disconnect. Used for configuration data and persistent locks.
• Ephemeral. Tied to a client session; auto-deleted when the session ends. The single most important property — this is what makes “lock holder dies, lock auto-releases” possible.
• Sequential. When you create /locks/foo/lock-, the service appends a monotonic counter, producing /locks/foo/lock-0000000017. Combined with ephemeral, this gives you a globally-ordered, auto-cleaning queue — exactly what leader election needs.

5.3 Sessions and Leases

A client has a session with the service. The session is kept alive by periodic heartbeats (every few seconds, well within the session timeout). If the heartbeats stop (client crashes, network partitions), the session expires after a timeout (typically 10-60 seconds), and all ephemeral nodes owned by that session are atomically deleted. This is the auto-release mechanism.

In etcd’s model, the session is replaced by leases: each lease has a TTL; clients keep-alive periodically; if they stop, the lease expires and all keys attached to it are deleted. Same idea, slightly different vocabulary.

6. High-Level Architecture

flowchart TB
    subgraph Cluster[5-Node Lock Service Cluster]
        L[Leader<br/>handles all writes]
        F1[Follower 1]
        F2[Follower 2]
        F3[Follower 3]
        F4[Follower 4]
        L <-->|Raft AppendEntries| F1
        L <-->|Raft AppendEntries| F2
        L <-->|Raft AppendEntries| F3
        L <-->|Raft AppendEntries| F4
    end

    subgraph LeaderInternals[Inside one node]
        ApiSrv[gRPC API server]
        WAL[(Write-Ahead Log<br/>fsync'd to disk)]
        StateMachine[Replicated State Machine<br/>= the namespace tree]
        Snapshot[(Snapshot file<br/>periodic)]
        Watcher[Watch dispatcher]
        ApiSrv --> WAL
        WAL --> StateMachine
        StateMachine --> Snapshot
        StateMachine --> Watcher
    end

    L -.uses.-> LeaderInternals

    Client1[Client App 1<br/>Kubernetes API server]
    Client2[Client App 2<br/>Order Service]
    Client3[Client App 3<br/>Cron Worker]

    Client1 -->|gRPC: Put, Lock, Watch| L
    Client2 -->|gRPC| L
    Client3 -->|gRPC| L

    L -->|notify watchers| Client1
    F1 -->|read-only RPCs<br/>stale OK| Client2

    LB[Load Balancer<br/>or DNS]
    Client1 --> LB
    LB --> L
    LB --> F1
    LB --> F2

What this diagram shows. The lock service is a small replicated state machine. Five nodes (typical) communicate via the Raft consensus protocol (or Paxos in older systems like Chubby). One is the elected Raft leader at any moment; all writes go to the leader, which appends them to its log and replicates to a quorum of followers before committing — meaning the write is acknowledged to the client only after a majority of nodes have it durably on disk. Reads can go to any node (faster, but possibly stale) or to the leader with a quorum-confirmation step (linearizable, slower). Each node’s state is the entire namespace tree, kept in memory for low-latency reads, with durable storage being the Raft log on disk plus periodic snapshots. Clients connect via gRPC; a load balancer or DNS round-robin routes them to any node, and the node redirects writes to the leader transparently. The watch dispatcher inside each node tracks which clients are watching which keys; on commit, the relevant clients get a one-shot notification. Failure of the leader: a follower wins a Raft election within the election timeout (typically 1-5 seconds) and becomes the new leader; clients reconnect transparently. Failure of up to (N-1)/2 = 2 nodes is tolerated; more, and writes pause until the cluster recovers majority.

7. Request Flow

7.1 Acquiring a Lock and Failing-Over

sequenceDiagram
    participant C1 as Client 1
    participant C2 as Client 2
    participant L as Lock Service Leader
    participant F as Followers (quorum)

    C1->>L: LeaseGrant(ttl=30)
    L->>F: Raft propose: lease_id=0x1, ttl=30
    F-->>L: ack (quorum)
    L->>L: commit
    L-->>C1: lease_id=0x1

    C1->>L: Lock("/locks/etl", lease=0x1)
    L->>F: Raft propose: put /locks/etl, owner=C1, lease=0x1
    F-->>L: ack
    L-->>C1: ack (lock held, key="/locks/etl/0x1")

    Note over C1: Client 1 begins its critical section.

    C2->>L: Lock("/locks/etl", lease=0x2)
    L->>L: see /locks/etl already held by C1<br/>queue C2's request
    Note over C2: C2 blocks until lock available.

    Note over C1: Client 1 crashes!<br/>Stops sending lease keep-alives.

    Note over L: After 30s of no keep-alive,<br/>lease 0x1 expires.
    L->>F: Raft propose: revoke lease 0x1<br/>delete /locks/etl
    F-->>L: ack
    L->>L: commit; notify watchers

    L-->>C2: ack (lock now held by C2)
    Note over C2: C2 enters critical section.

The TTL is the recovery time. Setting it too low (1 second) makes the lock fragile — a brief network blip and you lose it. Setting it too high (30 minutes) means the next acquirer waits a long time after a crash. Typical: 10-30 seconds.

7.2 Leader Election via Ephemeral Sequential Nodes (ZooKeeper Recipe)

sequenceDiagram
    participant A as Candidate A
    participant B as Candidate B
    participant C as Candidate C
    participant Z as ZooKeeper

    A->>Z: create("/election/n_", EPHEMERAL_SEQUENTIAL)
    Z-->>A: "/election/n_0000000001"
    B->>Z: create("/election/n_", EPHEMERAL_SEQUENTIAL)
    Z-->>B: "/election/n_0000000002"
    C->>Z: create("/election/n_", EPHEMERAL_SEQUENTIAL)
    Z-->>C: "/election/n_0000000003"

    A->>Z: getChildren("/election")
    Z-->>A: [n_1, n_2, n_3]
    Note over A: A's node is smallest → A is leader.

    B->>Z: getChildren("/election")
    Z-->>B: [n_1, n_2, n_3]
    Note over B: B is not smallest. Watch n_1 (predecessor).
    B->>Z: exists("/election/n_0000000001", watch=true)

    C->>Z: getChildren("/election")
    Z-->>C: [n_1, n_2, n_3]
    Note over C: C watches n_2.
    C->>Z: exists("/election/n_0000000002", watch=true)

    Note over A: A loses session (crash).
    Z-->>B: NotifyEvent: n_1 deleted!
    B->>Z: getChildren("/election")
    Z-->>B: [n_2, n_3]
    Note over B: B is now smallest → B is leader.

Critically, each non-leader watches only its predecessor, not the leader directly. This prevents the “herd effect”: if all 100 candidates watched the leader, every leader-loss event would trigger 100 simultaneous notifications and 100 reads — overwhelming the service. With predecessor-watch, exactly one notification fires per failover event. (See ZooKeeper Recipes documentation.)

8. Deep Dive

8.1 Why “Just Use Redis SETNX” Is Wrong — The Fencing Token

Martin Kleppmann’s 2016 blog post “How to do distributed locking” is required reading. The argument:

Consider this naive distributed lock:

# CLIENT-SIDE PSEUDOCODE — INCORRECT
def acquire_lock(name, ttl):
    while True:
        if redis.set(name, my_id, nx=True, ex=ttl):
            return  # acquired
        time.sleep(0.1)
 
def critical_section_with_lock():
    acquire_lock("file-lock", ttl=10)
    write_to_shared_storage()
    redis.delete("file-lock")

What goes wrong? Suppose Client A acquires the lock and starts working. Client A then experiences a long pause — garbage collection, swap, virtualization-induced freeze, anything 15 seconds long. The TTL expires. Client B acquires the lock. Now Client A wakes up, believes it still holds the lock, and writes to shared storage. Two clients have just simultaneously written to the “locked” resource. The lock provided no safety.

The fix: fencing tokens. The lock service issues a monotonically-increasing token along with the lock. Client A gets token 17. Client B gets token 18. The shared resource (database, file system) only accepts writes if the token is greater than the highest token it has ever seen. When stale Client A tries to write with token 17, the resource says “I already accepted token 18; rejecting your token-17 write.”

# CORRECT — with fencing token
def critical_section_with_lock():
    handle = lock_service.acquire("file-lock")    # returns lock + monotonic token
    storage.write(data, fence=handle.token)        # storage rejects stale tokens
    lock_service.release(handle)

All three production services expose a usable fencing token. Chubby makes this an explicit, named primitive: a lock holder calls GetSequencer() to obtain a sequencer — “an opaque byte-string that describes the state of the lock immediately after acquisition. It contains the name of the lock, the mode in which it was acquired (exclusive or shared), and the lock generation number” (Burrows 2006, §2.4, Chubby paper). The client passes the sequencer to the downstream resource server, which calls CheckSequencer() (or validates it against its own Chubby cache) and rejects the operation if the sequencer is no longer valid. The monotonic lock generation number is precisely the fencing value. ZooKeeper has no GetSequencer, but the per-znode czxid (creation zxid) — a globally-monotonic transaction identifier minted by ZAB — and the lock-acquisition order from sequential nodes serve the same role, as does etcd’s monotonic revision number. Redis’s basic SET-NX does not issue any monotonic token, so a vanilla “Redis distributed lock” cannot be safe in this stronger sense — Kleppmann’s central point: “the algorithm does not produce any number that is guaranteed to increase every time a client acquires a lock” (Kleppmann 2016). Redis’s Redlock proposal attempts to fix mutual exclusion with multi-instance acquisition, but Kleppmann shows it still has clock-skew and process-pause assumptions that break it (see §13). The distributed-systems consensus is: if you need correctness, use Chubby / ZooKeeper / etcd and enforce fencing tokens on the resource; if you can tolerate occasional safety violations and only need rough mutual exclusion, a single Redis instance is fine.

8.2 The Lease as the Single Most Important Idea

A lease is a time-bounded lock. The holder must renew before expiry; if it fails to renew, the lease auto-expires and any state attached to it is reclaimed. Without leases, you have an unsolvable problem: how do you know whether a holder is dead or just slow? You can’t. With leases, the question becomes: can the holder prove it’s alive fast enough? If yes, it keeps the lease. If no, the system reclaims and moves on.

The lease’s validity is enforced by the lock server’s clock, not the holder’s clock. Chubby is explicit about this: a Chubby session has a lease — “an interval of time extending into the future during which the master guarantees not to terminate the session unilaterally” — that the master advances when it answers a KeepAlive remote procedure call (RPC). The default lease extension is 12 seconds, though an overloaded master may use larger values to throttle KeepAlive traffic (Burrows 2006, §2.8, Chubby paper). Crucially, the client maintains its own local lease timeout that is a conservative under-approximation of the master’s, precisely because it cannot trust its clock relative to the master’s: “the client must make conservative assumptions both of the time its KeepAlive reply spent in flight, and the rate at which the master’s clock is advancing.” This is the production-grade form of the “subtract a safety margin” rule.

Chubby separates two timing mechanisms that are often conflated, and both numbers are verified from the paper. (1) The grace period, used during master fail-over: if the client’s local lease expires and it cannot reach a master, the session enters jeopardy; the client empties its cache and waits “a further interval called the grace period, 45s by default.” If a new master is reached and a KeepAlive succeeds within that window, the session survives the fail-over invisibly to the application; otherwise the session is declared expired and all its handles and locks are lost. (2) The lock-delay, used at lock release: when a lock becomes free because its holder failed (rather than releasing cleanly), the master refuses to hand the lock to a new claimant for a bounded delay — “Clients may specify any lock-delay up to some bound, currently one minute; this limit prevents a faulty client from making a lock… unavailable for an arbitrarily long time.” The lock-delay is Chubby’s defence for resources that cannot check sequencers: it buys time for in-flight delayed messages from the dead holder to drain before a new holder can act. Both trade a little availability for a lot of safety against the GC-pause / delayed-packet hazard of §8.1.

8.3 Why This Scales Reads but Not Writes

The lock service is a single Raft (or Paxos) group. Every write goes through the leader, which serializes writes through the Raft log. The leader’s write throughput is bounded by:

• Disk fsync latency. Each Raft commit must fsync the log to disk on a quorum of nodes. NVMe fsyncs are ~50 μs; spinning disk is 5-10 ms. This sets the floor.
• Network round-trip. Quorum acknowledgment requires reaching a majority of followers. Within a data center, ~1 ms; cross-DC, 10-100 ms.

In practice, etcd 3.5 on NVMe achieves around 10K-30K writes/second, with each write paying ~5-10 ms of latency. Beyond that, you’re stuck — you can’t shard a single Raft group across more leaders.

Reads scale much better. A read served by a follower (stale read) is just an in-memory lookup — millions of reads per second per node. Linearizable reads (served by the leader, with a Raft barrier to confirm the leader is still legitimate) are slower (~1-5 ms each) but still high-throughput. This is why lock services are used for low-write/high-read state: configuration, leader identity, group membership. They are not used for high-throughput data — that’s what databases are for.

8.4 Watches and the Notification Model

A watch is a one-shot subscription: you register watch on path /configs/featureflag-v3; when that path’s data or children change, you receive one notification, then the watch is implicitly canceled. To keep watching, you must re-register.

The one-shot design is deliberate. If watches were persistent, a busy path could overwhelm a slow client with notifications. With one-shot, the client gets the first event, processes it (likely re-reading the current state), then re-arms the watch for the next event. This naturally throttles to the client’s processing rate.

A subtle correctness property: between the client’s “read state, register watch” sequence, the state could change. ZooKeeper guarantees that a watch registered alongside a read sees any change after the read — no missed events. The client does:

data, version = getData("/x", watch=true)
# ... operate on data ...
# if /x is changed during operations, watch event fires.

In etcd, the equivalent is to read at a specific revision and watch from that revision forward.

8.5 The Split-Brain Problem and Fencing Tokens (Continued)

A network partition can split a cluster. Naively, both sides might think they’re the leader (Brain 1 is partitioned from Brain 2; each elects its own leader from the nodes it can see). The Raft/Paxos protocols prevent this: a leader is only legitimate if it has a quorum of live nodes. In a 5-node cluster split 3-2, the side with 3 nodes can elect a leader (it has quorum); the side with 2 cannot (no quorum); only one side has a writable leader. The minority side is read-only at best, fully unavailable typically.

But what if a stale leader from a previous term is partitioned and unaware its term has ended? It might still believe it’s the leader and serve writes. Raft’s fix: every write the leader commits must reach a quorum. The stale leader cannot reach quorum (because the partition cut it off from the majority). Its writes will not commit. So internally the lock service is safe.

The external safety concern is: a client that learns “I hold the lock from Leader A” and then continues operating after Leader A loses leadership. This is the same scenario as the GC pause earlier — the cure is the fencing token, which lets the downstream resource detect the staleness. The lock service emits a token; the resource validates the token. End-to-end safety requires both.

8.6 Why Use Cases Are Mostly Coordination, Not Storage

The lock service’s namespace looks like a tiny database. It is not a database. Specifically:

• Bounded total size. ZooKeeper expects total state in megabytes-to-low-gigabytes (the dataset must fit in heap). etcd defaults its storage quota to 2 GiB and recommends 8 GiB as the maximum. Past those bounds, performance degrades and etcd refuses writes until compacted.
• Bounded value size. Single values up to ~1 MiB (ZooKeeper) / 1.5 MiB request default (etcd).
• Bounded write rate. Tens of thousands of writes per second, not millions.
• No range queries beyond simple prefix. This is not a SQL database.

Production use cases:

• Leader election for stateful services (one primary among N replicas).
• Configuration coordination (feature flags, schema versions).
• Group membership and discovery (which workers are alive).
• Distributed cron / job locking (only one worker runs the nightly ETL).
• Cluster metadata (Kubernetes uses etcd for the entire cluster’s metadata — pods, services, configmaps, etc.).
• Distributed counters with low frequency (e.g., a global “next ID” counter incremented at human speed).

Production anti-uses:

• High-write-rate operational data (use a database).
• Large blobs (use object storage).
• Time-series telemetry (use a metrics system).

Misuse of ZooKeeper / etcd as a poor-man’s database is the most common failure mode in production deployments — leading to operational pain and eventually, crisis migrations to a real database.

9. Scaling Strategy

The lock service does not scale by adding leader replicas — that would defeat consensus. It scales by other axes:

9.1 Vertical Scaling

Faster disks (NVMe), more RAM (the namespace fits in memory), faster networking (intra-DC 10/25/40 Gbps). A modern 5-node etcd on good hardware can serve thousands of write QPS and millions of read QPS.

9.2 Read Scaling via Followers

For high-read workloads, send reads to followers. ZooKeeper natively serves reads from followers; etcd defaults to leader-served reads but supports follower reads via a flag. The trade is staleness — follower reads can be a few milliseconds behind. Most applications can tolerate this.

9.3 Multi-Cluster (Federated) Lock Services

When a single 5-7-node cluster is overwhelmed, the answer is multiple clusters, each owning a slice of the namespace. Kubernetes does this implicitly: each cluster’s etcd holds only that cluster’s state. Cross-cluster coordination requires either application-level logic or a higher-level coordinator.

9.4 Caching and Local Mirror

For read-heavy paths (say, configuration), clients can cache the value locally with a short TTL or a watch-based invalidation. The pattern: read once, watch for changes, serve from local cache. Per-pod caching reduces lock-service read load by orders of magnitude.

9.5 Geo-Distribution: The Hard Choice

A geographically distributed lock service forces a hard choice. Either:

• Replicas across regions. Linearizable consistency, but every commit pays cross-region RTT (50-200 ms). Acceptable for low-write workloads.
• One region authoritative. Other regions have read-only replicas. Writes from non-authoritative regions cross-region. Failover requires human or scripted intervention.
• Per-region clusters. Strong consistency within a region, eventual consistency cross-region. The compromise; common in geo-distributed Kubernetes federations.

Cross-region locks are fundamentally bottlenecked by the speed of light. Don’t fight it — design around it.

10. Real-World Example

Google’s Chubby (Burrows OSDI 2006). Inside Google, Chubby is the master coordination service. The Google File System (GFS) uses a Chubby lock “to appoint a GFS master server,” and Bigtable “uses Chubby in several ways: to elect a master, to allow the master to discover the servers it controls, and to permit clients to find the master” — Burrows names both explicitly (§1, Chubby paper). Internally, “a Chubby cell consists of a small set of servers (typically five) known as replicas,” and “the master must obtain votes from a majority of the replicas… Chubby itself usually has five replicas in each cell, of which three must be running for the cell to be up” — i.e. the classic 2f+1 = 5, f = 2 quorum (§2.1–2.2). Consensus is Paxos: “Asynchronous consensus is solved by the Paxos protocol.” The underlying durable store began as a replicated Berkeley DB and was later rewritten as “a simple database using write ahead logging and snapshotting” replicated by the Paxos log — the same WAL-plus-snapshot shape as the architecture diagram in §6 (§2.10). Clients connect via a library that handles consistent caching (kept fresh by master invalidations, not time-based TTLs) and master re-discovery on fail-over. The core insights — leases, sessions, ephemeral nodes, hierarchical namespace, watches/events, and sequencers — were all introduced or systematized in Chubby and copied by everyone who came after.

Apache ZooKeeper (Hunt et al. ATC 2010). Yahoo!‘s open-source lock service, designed by Patrick Hunt and others. Borrows heavily from Chubby’s API but ZooKeeper exposes the namespace operations directly (no built-in Lock RPC; locks are built via ephemeral sequential nodes). Backed by ZAB (ZooKeeper Atomic Broadcast), a Paxos-family atomic-broadcast protocol. Used by Hadoop (HDFS NameNode high availability), Apache Kafka (broker coordination and controller election), HBase (region-server discovery), Solr, and dozens of others. Kafka has since moved its metadata off ZooKeeper into its own built-in Raft store, KRaft: KRaft was marked production-ready for new clusters in Kafka 3.3 (KIP-833), ZooKeeper mode was deprecated in 3.5, and ZooKeeper support was removed entirely in Kafka 4.0 (released 2025). The book ZooKeeper: Distributed Process Coordination (Junqueira & Reed 2013) is the canonical reference.

etcd (CoreOS, now Red Hat / IBM, also a CNCF project). Built around 2013 with Raft (rather than Paxos/ZAB) for understandability. Heidi Howard’s analysis of Raft (Cambridge tech report, 2014) is widely cited. Used as the authoritative state store for Kubernetes — every kubectl command, every deployment, every pod lifecycle event flows through etcd. Also used by Patroni (PostgreSQL HA), CockroachDB (cluster bootstrap), and countless smaller deployments. The etcd v3 API (introduced 2016) cleaned up several rough edges of v2 and added native lease primitives; modern usage is exclusively v3.

Uncertain

Verify: that Chubby’s present-day implementation inside Google still matches the 2006 paper (five replicas, Paxos, 12 s lease, 45 s grace period, one-minute lock-delay). Reason: every architectural figure above is quoted directly from Burrows 2006, but Google has not published an updated Chubby paper, so any drift over ~20 years (e.g. cell sizing, lease defaults, migration to a newer consensus library) is invisible from outside. To resolve: a more recent Google publication or SRE write-up on Chubby — none located as of 2026-05. Treat the design as canonical and the exact current constants as as-of-2006. uncertain

11. Tradeoffs

Design Choice	Option A	Option B	When A wins	When B wins
Consensus algorithm	Raft (etcd)	ZAB / Paxos (ZooKeeper, Chubby)	Need understandable protocol, modern tooling	Battle-tested at extreme scale, library maturity
API style	Lock-built-in (etcd, Chubby)	Primitives + recipes (ZooKeeper)	Common-case ergonomics	Maximum flexibility, smaller server complexity
Replica count	3	5	Cost-constrained, low importance	Production critical, tolerates 2 simultaneous failures
Read consistency	Stale OK (followers)	Linearizable (leader + barrier)	Read-mostly load, application can tolerate ms staleness	Correctness requires reading exactly what’s been committed
Lease TTL	Short (5-10s)	Long (60s+)	Fast failover, willing to renew often	Network is unreliable, want fewer renewals
Use as data store	Yes, low-write KV	No, only coordination	Tiny, low-throughput, infrequent updates	Anything else (use a real DB)
Multi-region setup	Single global cluster	Per-region clusters	Geo-correlated workloads, can tolerate cross-region latency	Each region is independent, light cross-region needs

12. Pitfalls

1. Using the lock service as a database. The most common operational disaster. The cluster fills up, write latency spikes, the entire system degrades. Symptom: storage growth from many small keys. Cure: move data to a database; keep only coordination in the lock service.

2. No fencing token. Per Kleppmann’s argument: the lock alone does not protect a downstream resource if the lock holder pauses. Always pair the lock with a monotonic token that the resource validates.

3. Three-node clusters in production. Tolerates only one failure; a single node + a single network partition = unavailable. Five is the minimum for “real” production.

4. Even-numbered cluster sizes. Four or six nodes are strictly worse than the next-lower odd. Always odd.

5. No lease keep-alive thread. A holder that doesn’t renew loses the lock unexpectedly. The keep-alive must be on a dedicated thread or asyncio task — not interleaved with application work that can block the renewer.

6. Watch herd effect. Hundreds of clients watching the same path; on one event, all hundred fire. Use the predecessor-watch recipe (§8.1) for elections; for general data, use range watches.

7. Misusing ephemeral nodes for “permanent” data. Ephemeral nodes vanish on session loss. Forgetting this and storing essential state in an ephemeral node = data loss on next disconnect.

8. Too-short session timeout. Sub-second timeouts cause spurious disconnects on transient GC pauses. Most production deployments use 10-30 second sessions.

9. Too-long session timeout. Minute-long timeouts mean recovery from a crashed holder takes minutes — locks remain held, queues drain slowly.

10. Direct dependency without fallback. Every microservice that touches the lock service has the lock service in its critical path. If the lock service goes down (Raft minority loss), every dependent service falls over. Consider read-side caching, graceful degradation modes, and circuit breakers.

11. Migrating clusters by copying the data directory. Doesn’t work — the cluster identity is in the data. Migration requires backup-and-restore via the API.

12. Underestimating disk requirements. The Raft log needs fast fsync; spinning disks are too slow for production. Use NVMe SSDs.

13. Forgetting to compact. etcd retains historical revisions until compacted. Without periodic compaction, the database fills up and performance collapses.

13. Common Interview Variants and Follow-Ups

• “Implement a distributed semaphore on top of ZooKeeper.” Ephemeral sequential children of /sem/foo; you “have a permit” if your sequence is among the lowest N. Watch the (N+1)-th child to detect when a permit becomes available.

• “Implement a barrier.” A /barrier/start node; each participant creates an ephemeral child of /barrier/participants; all participants watch the children-count; when count reaches N, the barrier is open.

• “Why not just use a database for locking?” Databases don’t natively support ephemeral state (auto-release on disconnect) or efficient watches. You can build it (table with rows + heartbeat + change-data-capture for watches) but you’ve now built ZooKeeper poorly.

• “How would you migrate from ZooKeeper to etcd?” Run both for a while; mirror writes from one to the other; cut over reads first, then writes; verify under load. Kafka famously did this from ZooKeeper to KRaft (Kafka’s built-in Raft metadata store) over multiple major versions under KIP-500: KRaft reached production-ready in Kafka 3.3 (KIP-833), 3.x became “bridge releases” for migration, and ZooKeeper was removed entirely in Kafka 4.0.

• “What if the lock service itself has an outage?” Critical workloads should have fallback: serve cached state, refuse new operations, alert. Apps should have a “read-only mode” they fall into. The lock service is on the critical path — its downtime cascades. Plan for it.

• “Lock acquisition is slow under contention. How to make it faster?” Reduce contention by partitioning the lock — instead of one global lock, N locks each owning a hash range. Or use optimistic concurrency: try the operation, retry with a different key on conflict.

• “Compare this to Redis-based Redlock.” Redlock acquires the lock on a majority of independent Redis instances. Kleppmann argues this still has the clock-skew and process-pause safety problems and, more fundamentally, issues no monotonic fencing token; Antirez rebuts that a random token plus check-and-set suffices (see §14 for the resolved-as-far-as-possible debate). Even granting Redlock’s mutual exclusion, it is operationally inferior to Chubby / ZooKeeper / etcd (no built-in session-tied lease semantics on disconnect, no watches, no hierarchy, no native sequencer).

• “Implement a ‘fair’ lock (FIFO acquisition).” Ephemeral sequential nodes naturally provide FIFO: lowest sequence is next to acquire. Without sequential, every waiter races on each release and order is non-deterministic.

14. The Redlock Debate, Resolved as Far as the Public Record Allows

The most-cited controversy in this space is Kleppmann’s 2016 critique of Redis Redlock and Antirez’s same-year rebuttal. Having read both primary sources, here is the actual state of the disagreement — it is not fully resolved, but the points of agreement and disagreement are now precise.

Kleppmann’s argument has two prongs (Kleppmann 2016). First, the fencing-token prong: Redlock “does not produce any number that is guaranteed to increase every time a client acquires a lock,” so it cannot protect a downstream resource against a paused-then-resumed holder — this is a property no lock-only protocol provides, and it is the more fundamental objection. Second, the timing-assumptions prong: Redlock implicitly assumes a synchronous model where network delays, process pauses, and clock drift are all small relative to the lease TTL; he shows concrete failures when a Redis node’s clock jumps (premature expiry → two holders) or a client pauses in a kernel buffer (GitHub’s real 90-second packet delays are cited). His recommendation: for efficiency-only locks, a single Redis instance is fine; for correctness-critical locks, “please use a proper consensus system such as ZooKeeper” and “enforce use of fencing tokens on all resource accesses.”

Antirez concedes one point and contests the other (Antirez 2016, “Is Redlock safe?”). He agrees Redlock has no monotonic token but argues it is unnecessary: each acquisition carries a large random token usable for a check-and-set on the resource, and he contends “if you have such a system to avoid problems during race conditions, you probably don’t need a distributed lock at all.” On timing, he partly concedes (“Martin has a point about the monotonic [clock] API… [implementations] should use it”) but argues the algorithm’s re-check of remaining validity after acquiring the majority makes it robust to message delays. The exchange ended unresolved, with Antirez inviting Jepsen-style formal testing.

Uncertain

Verify: whether Redlock is “safe” for correctness-critical workloads. Reason: the two principals (Kleppmann, Antirez) read each other’s primary posts and still disagree; the disagreement is about the system model (synchronous vs partially-synchronous) and about whether random-token check-and-set substitutes for monotonic fencing — a modelling judgement, not a fact a single source settles. To resolve: a published Jepsen analysis of Redlock under adversarial clock/pause faults. The operationally safe reading: use ZooKeeper / etcd / Chubby for any lock guarding correctness, and fence the resource. uncertain

Uncertain

Verify: the relative performance of Raft (etcd) vs ZAB (ZooKeeper) at extreme scale, and whether Hazelcast’s CP subsystem or Aerospike’s strong-consistency mode are production-equivalent to ZooKeeper / etcd for critical-path locking. Reason: no head-to-head primary benchmark located; results are dominated by workload, tuning, and disk. To resolve: vendor-neutral benchmarks under matched hardware and a skewed workload. Both Raft and ZAB are mature and correct; the choice is usually ecosystem, not raw throughput. uncertain

15. See Also

• Major System Designs MOC — parent MOC
• SWE Interview Preparation MOC — grandparent MOC
• Raft — consensus algorithm used by etcd
• Paxos High-Level — consensus algorithm in Chubby’s lineage
• Two-Phase Commit — related coordination primitive (atomic commit, not consensus)
• Centralized Configuration System Design — etcd / Consul as config stores; close cousin
• Service Mesh System Design — uses the lock service for control-plane consensus
• API Gateway System Design — gateways often consume the lock service for hot-config reload
• Distributed SQL Database System Design — uses similar primitives for tablet placement
• Distributed Key Value Store System Design — built on similar consensus
• Vector Clocks — alternative coordination primitive (causality, not mutual exclusion)
• Gossip Protocol — eventually-consistent alternative for membership
• CRDTs Basics — a way to avoid distributed locks entirely for some workloads