System Design Interview: Design a Distributed Lock Service

Problem and Scope

Design a distributed lock service deployed across three availability zones in one region. It manages 100,000 lockable resources, normally maintains 20,000 active locks, and handles 2,000 acquisitions per second at peak. The default lease is 30 seconds, clients renew every 10 seconds, and the p99 target for an uncontended acquisition is 200 milliseconds. The protected store or service can atomically compare fencing tokens and reject requests from an older holder.

The scale, lease duration, and latency are interview inputs, not performance claims for etcd, ZooKeeper, or another product. The scope includes exclusive locks, waiting, renewal, release, failover, and observability. Fine-grained database row locks, a full transaction coordinator, implementing consensus from scratch, and active-active cross-region locking are outside the primary design.

This is a representative senior backend, infrastructure, and system design question. Amazon's current SDE II interview guidance explicitly includes system design and evaluates practicality, accuracy, efficiency, reliability, optimization, and scalability. The central failure mode touches all of them: the service must recover a lock after a client fails without letting an old client that resumes later corrupt the new holder's data.

What the Interviewer Is Evaluating

First, can the candidate separate mutual-exclusion safety from failure cleanup? A lease answers when another holder may take over after the current holder disappears. It does not stop a client that paused for a long time from resuming and writing. A strict design also needs a fencing token and validation at the protected resource.

Second, is the consistency boundary explicit? Acquisition, renewal, and release must pass through one strongly consistent state machine. A minority partition cannot continue issuing locks. If three availability zones decide independently, a network partition can create two holders for the same resource.

Third, does capacity planning include renewal traffic? With 20,000 active locks renewed every 10 seconds, renewals alone produce about 2,000 operations per second. If the peak also has 2,000 acquisitions per second and a similar number of releases, the state machine needs roughly 6,000 commits per second, not merely the acquisition rate.

Fourth, do failure semantics reach the request level? The answer should cover an acquisition that commits but loses its response, a client paused beyond the lease, an old client releasing a new holder's lock, loss of quorum, and monotonic tokens across leader changes.

Finally, does the candidate know when not to use this service? Google Chubby was intended for coarse-grained coordination. If a database unique constraint, conditional update, single-consumer queue, or business idempotency key already solves the problem, a remote lock adds another synchronous failure point.

Clarifying Questions Before Answering

• Do we need exclusive or reader-writer locks? This design starts with exclusive locks. Reader-writer locks add

state, upgrade, and starvation semantics that should not be promised casually.

• Can the protected resource validate fencing tokens? This prompt assumes atomic comparison and storage of the latest

token. Without it, a lease only reduces the conflict window and cannot strictly exclude a zombie client.

• How fair must waiting be? The default is approximate FIFO. Absolute fairness reduces flexibility during recovery

and under variable workloads.

• How long may a client wait? waitTimeout is bounded and cancellable so waiting state cannot grow forever.
• Can the lease duration vary by workload? The default is 30 seconds with renewal every 10 seconds. Long jobs may

request a duration inside a bounded policy, but leases cannot be extended without limit.

• May acquisition be retried automatically? Only a retry carrying the same stable requestId is safe. Otherwise,

a lost response leaves an unknown result.

• What happens without quorum? Safety wins: reject new acquisitions and renewals. Each partition cannot issue locks.
• Must the protected operation still be idempotent? Yes. Fencing rejects an older epoch; business retries and

duplicate submissions still need a business idempotency key or transaction.

• Is low-latency cross-region locking required? The primary design is one region across availability zones. A hard

cross-region lock pays higher latency or loses availability during a partition and belongs in a follow-up.

30-Second Answer Framework

“I would store lock state in a strongly consistent state machine replicated across three availability zones. Every acquire, renew, and release is committed by a quorum. A successful acquire returns a leaseId, a 30-second expiration, and a monotonically increasing fencingToken. The client renews every 10 seconds and stops work when renewal is uncertain. Every protected operation carries the token; the resource stores the highest epoch it has accepted and rejects older tokens. The lease permits a new holder, while fencing rejects a resumed old holder. A deduplicated requestId handles a committed acquisition whose response is lost. Ordered waiters watch only their predecessor to avoid a herd. Twenty thousand locks create about 2,000 renewals per second; with acquisition and release, I would test roughly 6,000 state commits per second under persistence and failover.”

Step-by-Step Deep Dive

Start with invariants instead of a component diagram:

1. For one resource, the consistent state machine records at most one valid leaseId at a time.
2. Every newly acquired lock receives a larger fencing token.
3. The protected resource rejects a token lower than the highest token it has accepted.
4. Only a request matching the current leaseId may renew or release.
5. The service does not create a lock or claim renewal success without reaching a quorum.

These invariants separate “who the lock service considers the holder” from “whose work the resource will still accept.” The state machine decides the first; fencing at the side-effect boundary decides the second.

Step 1: Define the API and state.

Acquire(resource, requestId, leaseTtl, waitTimeout)
  -> { leaseId, fencingToken, expiresAt }

Renew(resource, leaseId)
  -> { expiresAt }

Release(resource, leaseId)
  -> { released }

resource is a normalized business identifier, not unbounded raw user input. leaseId is an unguessable identifier for this ownership epoch. fencingToken uses the globally monotonic revision of a committed consensus log, while each protected resource stores the highest token it has accepted. The deduplication result for requestId remains at least as long as the caller's retry window. Release is idempotent, but a release with an old leaseId cannot delete a new holder's lock.

A lock record contains the resource, leaseId, holder identity, fencing token, expiration, and an optional waiter reference. Idle lock records may be removed, but tokens cannot move backward. A global monotonic revision avoids resetting one resource's epoch to 1 after its idle record is deleted.

Step 2: Choose the strongly consistent replication boundary.

Use a proven consensus store or coordination system for the state machine; do not reimplement Raft or Paxos inside the application service. Place one replica in each of three availability zones. The leader returns success only after at least two replicas commit the command. Lock-state reads must be linearizable or handled by the leader; a lagging replica cannot declare a resource free.

The normal acquisition path validates parameters and the deduplication key, confirms that no lock exists or that the state machine has expired its lease, assigns a new leaseId and revision, commits them to a quorum, and returns. If the leader fails after commit but before its response arrives, a retry with the same requestId gets the original result from the new leader instead of creating a second lease.

When only one of three replicas remains reachable, the service rejects acquisitions and renewals. This reduces availability but preserves mutual exclusion. Letting the minority renew appears helpful, but after reconnection there is no safe way to treat both partitioned holders as valid.

Step 3: Use leases to recover failed holders.

The default lease is 30 seconds and the client renews every 10 seconds, leaving two renewal intervals for jitter and transient failures. Authoritative lease time is managed by the server-side coordination state machine. A client's local clock may decide when to attempt renewal, but it cannot prove ownership. After repeated renewal failures or an uncertain response, the client enters a quiescent state, starts no new work, and stops interruptible in-flight work as soon as possible.

A leader change must handle remaining lease time conservatively; a fast clock on the new leader cannot hand the lock to someone else too early. Production systems should reuse a tested lease implementation and include maximum clock skew, election time, and network retries in the lease budget. Cutting the lease to hundreds of milliseconds improves cleanup speed but turns ordinary jitter into frequent lock loss.

Step 4: Use fencing tokens to stop zombie clients.

Suppose client A acquires token 41 and then pauses for a long garbage collection. Its 30-second lease expires, client B acquires token 42, and B begins work. A resumes without knowing it lost the lock and sends a delayed write. If the store only knows that A once acquired the lock, the stale write can overwrite B's newer result.

Every protected request therefore carries its token. The store atomically remembers the highest epoch seen for each resource. After accepting token 42, it rejects every request with token 41. Multiple operations with the same token may still be legitimate; their ordering, idempotency, and version conflicts belong to the business protocol. The comparison rejects tokens lower than the latest epoch rather than blindly rejecting equal tokens.

The etcd documentation makes the same boundary explicit: a lease alone does not guarantee mutual exclusion over an external resource; that resource must validate a version. If the target cannot store or compare a token, the design cannot promise strict safety. Alternatives include a database conditional update, unique constraint, native transactional lock, single-writer queue, or a write proxy that can enforce the token.

Step 5: Handle waiting, fairness, and herds.

For low-contention resources, failed callers can retry with exponential backoff and jitter. For a hot resource that needs waiting, assign increasing sequence numbers and let each waiter watch only its immediate predecessor. When a predecessor releases or expires, only the next waiter wakes instead of every client racing at once. ZooKeeper's lock recipe uses ephemeral sequential nodes and predecessor watches for this reason.

The queue provides approximate FIFO, not absolute fairness. Cancellation, timeout, and session expiration remove the wait node. If the response to node creation is lost, requestId finds the original node instead of adding another. Per-resource and per-tenant waiter limits prevent one hot lock from exhausting memory.

Step 6: Estimate capacity and partitioning.

Twenty thousand active locks renewed every 10 seconds create about 2,000 renewals per second. At a peak of 2,000 acquisitions per second, and assuming releases are roughly equal to acquisitions, the consensus state machine handles about 2,000 + 2,000 + 2,000 = 6,000 write commits per second. Enqueue, cancellation, expiration, and deduplication records add write amplification. Capacity tests should combine peak traffic, loss of one replica, and log compaction.

If 100,000 resources retain about 500 bytes of logical state each, the logical total is about 50 MB. Replicas, logs, indexes, waiters, and storage-engine overhead increase the real footprint substantially. Synchronous persistence, hot resources, and renewal volume are more likely bottlenecks here than the static record size.

Begin with one consensus group for the stated scale. Partition by a hash of the resource only if measurements show that one group misses the target. Sharding raises aggregate throughput but cannot split one extremely hot resource, and it complicates atomic locking across resources. This design does not promise multi-resource transactional locks. If callers must lock several resources, they use a fixed ordering and an overall timeout, or the domain is remodeled as one higher-level resource.

Step 7: Close the failure and operational loop.

• Leader failure: the new leader recovers committed state; requestId safely resolves requests with unknown responses.
• Network partition: only the quorum serves; the minority rejects, and fencing eventually rejects an old holder's write.
• Client pause: a new lock may be issued after expiration, while the resumed client fails resource-side token validation.
• Hot lock: measure wait length, acquisition latency, and hold time; cap the queue and consider a queue or partitioned job.
• Renewal storm: jitter client schedules and prioritize leases nearest expiration instead of renewing every lock together.
• Resource without token validation: explicitly downgrade to best-effort exclusion or prohibit strict money and inventory writes.

Core metrics include acquire, renew, and release p50/p95/p99; success, timeout, conflict, and unknown outcomes; active locks, waiters, expirations, renewal failures, leader election duration, consensus commit latency, fencing rejections, and hot resources. Audit logs capture resource, leaseId, token, caller, and result without sensitive payloads.

Validation goes beyond unit tests. State-machine model tests check single ownership and monotonic tokens. Fault injection covers a response lost after commit, a client paused beyond 30 seconds, a delayed old write, isolation of one replica, loss of the majority, leader changes, and waiter cancellation. The critical end-to-end assertion is: after the resource accepts B's token 42, A's token 41 can never change that resource again.

High-Quality Sample Answer

“I would start with the safety target: one resource has at most one valid lease in the strongly consistent lock state, and the protected resource never accepts an older holder's write. The service runs across three availability zones on a proven consensus store. Acquire, renew, and release require a quorum. With only a minority, the service rejects work instead of trading mutual exclusion for availability.

The API returns a leaseId, expiration, and monotonically increasing fencingToken. The default lease is 30 seconds and the client renews every 10 seconds. Its local clock only schedules renewal; if renewal is uncertain, the client stops work. A lease permits takeover after failure, but the resource is the actual safety boundary: every protected request carries the token, and the resource stores the highest epoch it has accepted and rejects older ones. If the token 41 client resumes after token 42 takes over, its stale write cannot land.

Every acquisition carries a requestId. If the service committed but lost its response, the caller retries with the same ID and receives the original lease rather than creating another. Renew and release must match the current leaseId, so an old client cannot release the new holder. For a contended lock, ordered waiters watch only their predecessor, providing approximate FIFO without a herd.

For capacity, 20,000 locks renewed every 10 seconds already produce about 2,000 writes per second. Adding 2,000 acquisitions and a similar release rate gives roughly 6,000 consensus commits per second. I would verify the 200-millisecond p99 while one replica is down and log compaction is running instead of quoting a vendor benchmark. I would start with one consensus group and shard by resource only if load tests prove it is necessary.

Finally, model tests and fault injection cover lost responses after commit, client pauses, delayed packets, partitions, elections, and waiter cancellation. I would monitor acquisition and renewal latency, conflicts, expirations, queue length, elections, and fencing rejections. If the protected system cannot atomically compare a token, I would state that strict mutual exclusion is unavailable and prefer a database conditional update, unique constraint, or single-writer queue.”

Common Mistakes

• Storing only a key with a TTL → a paused old client can resume and write → issue a monotonic token for every acquisition and validate it at the resource.
• Letting every availability zone issue locks → a partition creates multiple holders → put every state change through one quorum-backed state machine.
• Treating the client clock as lease truth → clock skew and pauses cause false ownership → manage leases server-side and make uncertain clients stop.
• Retrying acquisition with a new request ID → the original may already be committed → use a stable requestId to retrieve the first result.
• Allowing release by resource name alone → an old request may delete the new holder → require the current leaseId for renew and release.
• Sizing only for 2,000 acquisitions per second → 2,000 renewals and similar releases are missing → test about 6,000 baseline state commits per second.
• Making every waiter watch the lock root → each release wakes the entire queue → make each waiter watch only its immediate predecessor.
• Sharding into many consensus groups immediately → operations and cross-resource semantics become complex first → measure one group, then shard from evidence.
• Using a distributed lock for every row → coordination becomes a high-frequency transaction path and bottleneck → prefer database atomic constraints for fine-grained concurrency.
• Claiming strict safety when the target cannot validate tokens → a lease cannot stop a delayed stale write → downgrade the guarantee or change the write boundary.

Follow-up Questions and Responses

Follow-up 1: Why is a fencing token necessary if the lock has a lease?

The lease only lets the lock service grant B a lock after 30 seconds. It cannot remove an operation that A already sent to an external system but that remains in a network or process queue. A may also resume after a long pause without knowing its lease expired. Once the resource accepts token 42, rejecting token 41 stops old-epoch work at the point where side effects happen. The reusable rule is: a lease decides when a new holder may be elected; fencing decides whether the old holder's work is still accepted.

Follow-up 2: What if the protected database cannot store a fencing token?

Look first for an equivalent atomic version condition such as UPDATE ... WHERE version = expected, a unique constraint, a transactional lock, or a database advisory lock. Writes can also pass through a proxy or single-consumer queue that validates the token. If none is possible, the guarantee is only best-effort exclusion; process pauses and delayed messages can still break correctness. Money and inventory workflows should not accept an ambiguous claim.

Follow-up 3: How would you design a global lock across regions?

The direct design gives each resource a home region and makes every region use one cross-region quorum. That adds long-distance write latency, and minority regions cannot acquire during a partition. Independent regional locks cannot be merged asynchronously because mutual-exclusion conflicts cannot be undone later. If regional availability matters more, partition resource ownership so one resource is writable in one region instead of inventing active-active global locking.

Follow-up 4: How would you choose the 30-second lease and 10-second renewal interval?

They are prompt inputs. Real values depend on the longest normal process pause, network p99, election time, clock-error budget, and acceptable failure-recovery time. A lease that is too short treats normal jitter as lock loss; one that is too long delays recovery from a failed holder. A 10-second renewal gives two additional opportunities inside a 30-second lease. Add random jitter so 20,000 clients do not create synchronized renewal spikes.

Follow-up 5: How would you support acquiring several locks at once?

The simplest boundary is that this service does not offer atomic cross-resource locking. Callers acquire normalized resource names in a fixed order with a short overall timeout, and release in reverse order after failure. This reduces deadlock but is not transactional atomicity. If the domain truly needs all-or-nothing acquisition, model the set as one higher-level resource or keep all keys in one consensus transaction and accept the throughput and complexity cost.

Follow-up 6: How would you prove the implementation never creates two valid holders?

Use a state-machine model to generate acquire, renew, release, expiration, and retry sequences, checking that each log position has at most one valid leaseId and that tokens increase. Then inject faults: lose the response after commit, pause A beyond the lease, let B acquire and write, and resume A with its old write; the resource must reject the old token. Also isolate the minority and majority, repeatedly change leaders, cancel waiters, and check every concurrent history against the invariants.