Design Distributed Locking

Inside one process, mutual exclusion is a solved problem. The operating system and the CPU give you atomic instructions over shared memory, and if a thread dies holding a mutex, the whole process usually dies with it. Spread the same workers across thirty machines and every one of those comforts disappears. There is no shared memory, only messages over a network that can delay, reorder or drop them. Clocks on different hosts disagree. A process can stop for half a minute in a garbage collection or a VM migration and then resume as if nothing happened.

So the lock state has to live in a separate service that every client can reach, and that service has to answer one question correctly under all of those conditions: who is allowed to act on this resource right now? Teams use the answer for very different things. Some want to avoid wasted work, such as two nodes rebuilding the same cache. Others protect correctness, such as two nodes debiting the same wallet. Those two uses tolerate failure very differently, and a good design treats them separately.

Assume 1,200 service instances across 150 teams use the service in one region. A typical instance performs about 15 lock operations per second, counting acquires, releases and renewals. Lock names average 60 bytes.

Locks are connection-oriented, so the interface is gRPC with a long-lived session stream rather than stateless REST. Most callers use a thin SDK that hides renewals and reconnects. The calls below show the wire shape.

The heart of the strict tier is a five-node Raft group running a small lock state machine. Every acquire, release and session expiry is a log entry. The leader appends it, waits for two followers to persist it, applies it to the in-memory map of locks, and answers. Because every node applies the same entries in the same order, any node that becomes leader has exactly the same view of who holds what. Snapshots of the map are taken every few minutes so a restarted node replays only a short tail of the log.

The fencing token comes for free from the log. Each lock name keeps a counter that the state machine increments on every grant, and since grants are serialized through Raft the counter is strictly increasing across leader changes. etcd exposes the same idea as a key's revision number, and ZooKeeper as the zxid or a sequential znode number.

Sessions are what make crashed clients go away. Rather than writing a heartbeat into the log 400 times a second, the leader tracks the last heartbeat time per session in memory. When a session misses its deadline, the leader commits a single ExpireSession entry that frees all of that session's locks at once and promotes the next waiter on each. A newly elected leader gives every session a fresh grace period before expiring anything, since it cannot know when old heartbeats arrived.

The fast tier is a set of independent Redis primaries, sharded by lock name. An acquire is SET name token NX PX 8000 and a release is a Lua script that deletes the key only if the value still matches. There is no replication wait and no quorum. If a Redis primary fails over before its replica copied the key, two clients may briefly hold the same lock. For a cache rebuild, that is an acceptable price for a one-millisecond acquire.

Follow worker A carefully. It acquires the lock with a 10-second lease and starts preparing a write. Then its JVM stops the world for 25 seconds. During that pause A sends no heartbeats, so the service correctly concludes A is gone, expires the session and grants the lock to B. Nothing in the lock service misbehaved. When A resumes, its code continues from the line after "lock acquired", and nothing forces it to check again before the write. Even if it did check, the check and the write are two steps, and a pause can land between them.

The fix moves the final decision to the place where the damage would happen. Each grant carries a token, and the protected store remembers the highest token it has accepted for that resource. A write carrying a lower token is refused. B's write raised the stored value to 90413, so A's write with 90412 fails, and A's SDK surfaces that as "lock lost". This is optimistic concurrency control layered under a pessimistic lock: the lock keeps contention orderly, the fence makes the rare overlap harmless.

When the resource cannot check a token, for example an external payment provider, the next best option is to send an idempotency key derived from the work item. The provider then deduplicates for you, and the lock becomes an efficiency measure rather than the only line of defence.

Redlock acquires the same key on a majority of five independent Redis nodes and treats the lock as held until the shortest expiry passes. It improves availability over a single Redis key, but it still decides expiry from wall-clock time on each node, so a clock jump on two nodes can produce two holders. More importantly, it hands out a random value rather than an increasing number, so the store has nothing to compare. Martin Kleppmann's 2016 critique makes this argument in detail and is worth naming in an interview.

Short leases free a dead client's locks quickly but expire healthy clients that hit a brief network blip. Long leases do the opposite. A 10-second session TTL with heartbeats every 3 seconds tolerates two lost heartbeats and recovers a crashed holder in about 10 seconds. Clients should also stop acting on their own once their local timer says the lease is about to run out, measured with a monotonic clock, even if they have not heard back from the service.