Design a distributed lock service

Every distributed lock must have a lease, otherwise a crashed holder blocks everyone forever. But a lease creates a new problem: the holder cannot know for sure that its lease is still valid. A process can pause for longer than the lease (a long GC, a VM migration, a slow disk swap), or its packets can be delayed in the network. When it resumes, it continues acting as the holder while the lock service has already given the lock to someone else. Checking 'do I still hold it?' before writing does not help, because the pause can happen right after the check. The fix, described by Martin Kleppmann and used by Google Chubby (as sequencers), is a fencing token: a number that increases with each grant. The holder sends it with every write, and the protected resource remembers the highest token seen and rejects anything lower. In etcd, the key's revision serves as the token; in ZooKeeper, the zxid or the sequential node number. This moves the final safety check to the resource itself, which is the only place that can enforce it. If the resource cannot check tokens (e.g. an external payment API), use idempotency keys there instead.

A single Redis node with SET lock value NX PX 30000 is fast and simple, and release must check the value with a small Lua script so you do not delete someone else's lock. But Redis replication is asynchronous: if the primary fails after granting a lock and before replicating it, the promoted replica does not know about it and grants it again. Redlock tries to fix this by acquiring the lock on a majority of 5 independent Redis nodes within a time limit. Critics (notably Kleppmann) pointed out it depends on bounded clock drift and process pauses and provides no fencing token, so it is not safe for correctness; Redis's author disagreed, and the debate is worth knowing. The safe recommendation: for efficiency locks (avoid running a cache rebuild twice), single-Redis locks are fine. For correctness locks, use a consensus-based store such as etcd, ZooKeeper or Consul, where a grant is only acknowledged after a majority has written it to disk, so leader failover never loses a grant, plus fencing tokens. The cost is a few milliseconds per operation and a cluster of 3 or 5 nodes that needs careful operation.

If 500 workers wait for the same lock and all watch the lock key, a release wakes all 500, they all try to acquire, 499 fail and go back to waiting. This herd effect wastes CPU and spikes load on the lock service at exactly the wrong moment. The ZooKeeper recipe avoids it: each waiter creates an ephemeral sequential node (lock-0000041, lock-0000042, ...). The one with the lowest number holds the lock. Every other waiter watches only the node immediately before its own. When the holder releases or dies, exactly one waiter is woken. This also gives fairness (FIFO order) and handles a waiter that dies in the middle of the line, since its successor gets an event and re-checks. etcd's concurrency package implements the same idea using create revisions. Add a wait timeout so callers do not wait forever, and keep lock scopes narrow (lock per payment ID, not one global 'payments' lock) to avoid long queues.

Short leases (5 s) free locks quickly after a crash but cause false expiries during GC pauses or network blips, and more renewal traffic. Long leases (60 s) are robust to pauses but block progress for up to a minute after a crash. A common choice is 10-15 s with renewal every third of the lease, plus fencing tokens to make false expiries safe.

Locks add latency, a dependency and failure modes. Often a better design removes the need: idempotency keys with a unique constraint for payment processing, conditional updates (UPDATE ... WHERE version = v), or routing all work for a key to one Kafka partition so a single consumer owns it. Use a lock service mostly for leader election and coarse jobs, as Google's Chubby paper recommends (coarse-grained locks held for hours, not per-request locks).

Writing your own Raft implementation is rarely worth it. etcd and ZooKeeper are battle-tested; DynamoDB conditional writes with a lease timestamp and a version number can also implement leases with fencing for teams already on AWS. Building a 'lock service' in an interview mostly means wrapping one of these with a clean API, sessions and fencing.

All grants go through one Raft leader. Beyond ~30-50k writes/s, shard the lock namespace across several independent Raft groups (by hash of lock name), as each lock is independent. Also make renewals per session, not per lock.

If thousands of workers fight over one lock, the lock is the wrong tool. Split the work into finer-grained locks or partitions, or use a queue so work is assigned rather than contended.

Followers elect a new leader within a few seconds (election timeout ~1-3 s). Committed grants are on a majority, so none are lost. Lease timers restart on the new leader, which by convention extends leases rather than expiring them early, so holders are not unfairly dropped. Acquires during the election wait or retry.

The client cannot renew. Its library must assume the lock is lost when the lease deadline (measured on its own monotonic clock, minus a safety margin) passes, and stop work. Fencing tokens protect the resource even if the client is slow to notice.

No new grants or releases are possible (the system chooses consistency over availability). Existing holders keep working until their leases run out. Run 5 nodes across 3 AZs if you need to survive two node failures.