Design a Distributed Lock with Fencing Tokens

System Design Interview•~30 min read•hard

When multiple microservices access a shared resource (such as executing payments, generating sequence numbers, or writing to shared storage), local process mutexes fail. Design a distributed lock service that guarantees mutual exclusion, handles client crashes, and prevents split-brain writes caused by JVM Stop-The-World (STW) pauses and clock drift.

1. Understand Requirements & Scope

Background financial invoice reconciliation worker holding a distributed Redis lock (Redlock) with a 30-second TTL. Failure cascade dynamic: 50k Mut. → Row X-Lock → Spinlock Thrash → Deadlock Graph → 💥 DB Freeze.

Functional Requirements:

Mutual exclusion: Exactly one worker can hold the lock for a given resource at any instant.
Deadlock-free: Locks must automatically expire via a lease Time-To-Live (TTL) if a worker crashes.
Fault tolerance: If a lock server node dies, locks must remain consistent without granting duplicates.
Fencing: Protect downstream storage from delayed writes issued by workers whose locks expired during GC pauses.

2. Back-of-the-Envelope Capacity Estimation

• Latency: Lock acquisition and release should complete in under 5 ms.

• High availability: The lock manager must survive single-node infrastructure outages.

• Clock drift: System must remain safe even if physical system clocks jump or drift by seconds.

3. High-Level Architecture Flow

Production-hardened distributed locking requires mutually exclusive lock acquisition, auto-release safety leases, monotonic fencing tokens to prevent split-brain storage writes during GC pauses, and atomic Lua release verification.

[Client A]                   [Lock Service (Redis)]          [Storage Engine (DB)]
    |                                   |                                     |
    |--- 1. Acquire Lock -------------->|                                     |
    |<-- 2. Granted (Fencing Token 33) -|                                     |
    |                                   |                                     |
   (Long GC Pause - 15s)                |                                     |
    |                                   |                                     |
    |                             [Lock Expires]                              |
    |                                   |                                     |
[Client B]                              |                                     |
    |--- 3. Acquire Lock -------------->|                                     |
    |<-- 4. Granted (Fencing Token 34) -|                                     |
    |                                   |                                     |
    |--- 5. Write Data (Token 34) ------------------------------------------->|
    |                                   |                                  (COMMITTED: Token 34)
    |                                   |                                     |
[Client A wakes up]                     |                                     |
    |--- 6. Write Data (Token 33) ------------------------------------------->|
                                                                           (REJECTED: 33 < 34!)

Fig 1. Architecture data flow and component topology.

4. Production Implementation & Code

-- Atomic Redis Lock Acquisition with 30s TTL
SET resource_name my_random_secret_token NX PX 30000

-- Atomic Release Script (prevents deleting another worker's lock after expiration)
if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
else
    return 0
end

Hardened Implementation Sequence

Client sends POST /acquire-lock with resource ID, client ID, and lease TTL (e.g., 10 seconds).
The lock manager atomically grants the lock and returns a monotonically increasing Fencing Token (e.g. Token 34).
Client performs work and passes the Fencing Token in all write headers to downstream storage.
The storage layer tracks the highest observed token ($T_{max}$). If a write arrives with $T < T_{max}$, the write is rejected immediately.
If the client experiences a 10s GC pause and its lease expires, Client B acquires the lock with Token 35. When Client A wakes up and attempts to write with Token 34, Storage rejects it.

5. Key Decisions & Operational Mitigations

Architectural Decisions & Trade-Offs

•Ingress Admission: Naive unconstrained buffering causes queue bloat and GC exhaustion. Mitigation: Bounded ingress gate with fast non-blocking shedding.
•Resource Strategy: Static capacity allocations collapse under brownouts. Mitigation: Dynamic adaptive limits scaling to real-time physical bounds.
•Outage Impact: Cascading lock convoys and memory saturation. Mitigation: Isolated failure domains keep P99 latency flat and protected.

Operational Hazards & Mitigations

•Cascading Failure: Worker 1 acquires lock, starts processing, but hits an unexpected 35-second database freeze. The Redis lock TTL expires at t=30s. Worker 2 acquires the lock and begins writing. Worker 1 recovers at t=35s and completes its write, silently corrupting shared state.
•Breakdown Chain: 50k Mut. → Row X-Lock → Spinlock Thrash → Deadlock Graph → 💥 DB Freeze
•Shedding Failure: Without fast rejection at the boundary, queued dead work triggers multi-second GC pauses, CPU thrashing, and cascading 504 Gateway Timeouts.

Interactive Knowledge Check • Question 1 of 3↓

Interactive Practice Quiz•Question 1 of 3

advanced

Core Architectural Principles of Distributed Locking & Redlock Algorithm

What is the primary benefit of applying Distributed Locking & Redlock Algorithm in production systems?