Design a Distributed Lock Service

Problem Statement

Design a distributed lock service (like Google Chubby or Apache ZooKeeper) that provides mutual exclusion across distributed processes. The service must ensure that at most one client holds a lock at any time, survive node failures without losing lock state, support lock TTLs to prevent deadlocks from crashed clients, and issue fencing tokens to prevent split-brain scenarios.

Requirements

Functional

• Acquire a named lock with a TTL (e.g., lock "payment-processor" for 30 seconds)
• Release a lock explicitly or automatically on TTL expiration
• Issue a monotonically increasing fencing token with each lock acquisition
• Support lock waiting: client can block until the lock becomes available (with timeout)

Non-Functional

• Safety: At most one client holds a given lock at any time (mutual exclusion)
• Liveness: Locks are eventually released even if the holder crashes (TTL)
• Availability: Service continues operating if a minority of nodes fail (Raft quorum)
• Latency: Lock acquire/release in <10ms within the same data center

Core Architecture

1. Consensus Layer (Raft) -- The lock service runs on a cluster of 5 nodes using the Raft consensus protocol. Lock state is replicated to a majority (3/5) before an acquire is acknowledged. The Raft leader handles all lock operations; followers redirect clients to the leader. This ensures that lock state survives any 2 node failures.

2. Lock Manager -- Maintains a hash map of lock_name -> (owner_client_id, fencing_token, expiry_time). Acquire: if lock is free or expired, assign to requester with a new fencing token (monotonically increasing counter) and set expiry = now + TTL. If lock is held, either reject immediately or add the client to a wait queue. Release: clear the lock entry and notify the first waiter.

3. Fencing Token Issuer -- Each lock acquisition returns a fencing token (e.g., 42, 43, 44...). Clients include this token in all operations on the protected resource. The resource server rejects operations with a token lower than the highest it has seen. This prevents a scenario where a client holds a lock, pauses (GC, network), the lock expires, another client acquires it, and the original client resumes and corrupts data.

4. Session and Heartbeat Manager -- Each client maintains a session with the lock service via periodic heartbeats (every 5 seconds). If the server receives no heartbeat for 3 intervals (15 seconds), the session is expired and all locks held by that client are released. This prevents deadlocks from silently crashed clients beyond the TTL mechanism.

Database Choice

No external database -- the lock state is the Raft replicated state machine itself. The Raft log is persisted to local SSD on each node for durability across restarts. The state machine (lock hash map) is kept in-memory for fast access. Periodic snapshots of the state machine are written to disk to bound Raft log size. Prometheus for operational metrics (lock contention, acquire latency, session count).

Key API Endpoints

POST /api/v1/locks/\{lock_name\}/acquire
  -> Body: \{ client_id: "worker-7", ttl_ms: 30000, wait_timeout_ms: 5000 \}
  -> Returns: \{ acquired: true, fencing_token: 42, expires_at: "..." \}

POST /api/v1/locks/\{lock_name\}/release
  -> Body: \{ client_id: "worker-7", fencing_token: 42 \}
  -> Returns: \{ released: true \}

POST /api/v1/locks/\{lock_name\}/renew
  -> Body: \{ client_id: "worker-7", fencing_token: 42, ttl_ms: 30000 \}
  -> Returns: \{ renewed: true, new_expires_at: "..." \}

Scaling Insight

Fencing tokens are the solution to the distributed lock's biggest problem: the "client pause" scenario. A client acquires a lock (token=42), then pauses for a full GC. The lock TTL expires, another client acquires the lock (token=43) and begins work. The first client resumes, believing it still holds the lock. Without fencing tokens, both clients corrupt the shared resource. With fencing tokens, every write to the resource includes the token, and the resource server rejects token=42 because it has already seen token=43. This makes the system safe even when clocks are unreliable and clients are unpredictable.

Key Tradeoffs

Original DosiBridge notes for Design a Distributed Lock Service

This section is written specifically for this page, not copied from a general system-design checklist. The useful way to study Design a Distributed Lock Service is to connect the concept to a production service where growth exposes the first weak assumption in the original design. That framing changes the design discussion from definitions to operating choices.

What makes this topic distinct

• Core Entity: For Design a Distributed Lock Service, decide the core entity before choosing tools; otherwise the design looks clean but fails when distributed changes.
• Read/Write Path: For Design a Distributed Lock Service, decide the read/write path before choosing tools; otherwise the design looks clean but fails when lock changes.
• Contention Point: For Design a Distributed Lock Service, decide the contention point before choosing tools; otherwise the design looks clean but fails when service changes.
• Abuse Path: For Design a Distributed Lock Service, decide the abuse path before choosing tools; otherwise the design looks clean but fails when distributed changes.
• Recovery Workflow: For Design a Distributed Lock Service, decide the recovery workflow before choosing tools; otherwise the design looks clean but fails when lock changes.

Design a Distributed Lock Service correctness boundary

For this problem, separate the user-visible action from background work. The correctness boundary is the smallest state transition that must not be duplicated, lost, or reordered. Naming that boundary makes the solution more original than a stock API/database/cache template.

Design a Distributed Lock Service scaling bottleneck

The first bottleneck should be described in the language of this system: a hot timeline, a contested seat, a busy wallet ledger, a media-processing queue, or a search index update delay. That bottleneck decides which component deserves the deepest interview discussion.

Production review question

If Design a Distributed Lock Service suddenly receives 10x traffic, which entity becomes contested first, and what queue, lock, shard, or cache protects that entity without hiding correctness bugs?

Practical metric to track

Track distributed-service health as a named dashboard or review item: combine one user-facing metric, one saturation metric, and one correctness metric. For Design a Distributed Lock Service, this keeps the discussion grounded in behavior that can be measured after deployment instead of generic advice that sounds good in an interview but never gets verified.

Sources

• Design a Distributed Lock Service -- Reference
• Source: System-Design-Overview