Design a Distributed Lock with Fencing Tokens
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.
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.
Core 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.
A distributed lock using an in-memory consensus cluster (e.g., Redis Redlock or ZooKeeper/etcd) coupled with Martin Kleppmann's Monotonically Increasing Fencing Tokens. Each lock acquisition increments a monotonic counter ($T$). Downstream storage enforces safety by rejecting writes containing a token smaller than the highest token observed, preventing split-brain writes during JVM garbage collection pauses.
Hardened Implementation Steps
- 1Client sends POST /acquire-lock with resource ID, client ID, and lease TTL (e.g., 10 seconds).
- 2The lock manager atomically grants the lock and returns a monotonically increasing Fencing Token (e.g. Token 34).
- 3Client performs work and passes the Fencing Token in all write headers to downstream storage.
- 4The storage layer tracks the highest observed token ($T_{max}$). If a write arrives with $T < T_{max}$, the write is rejected immediately.
- 5If 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.
Production Code Contrast & Implementation
[Client A] [Lock Service] [Storage]
| | |
|--- 1. Acquire Lock --------->| |
|<-- 2. Granted (Token 33) ----| |
| | |
(GC Pause - 10s) | |
| | |
| [Lock Expires] |
| | |
[Client B] | |
|--- 3. Acquire Lock --------->| |
|<-- 4. Granted (Token 34) ----| |
| | |
|--- 5. Write Data (Token 34) --------------------------->|
| (ACCEPTED: T_max=34)
[Client A wakes up] | |
|--- 6. Write Data (Token 33) --------------------------->|
(REJECTED: 33 < 34!)Architectural comparison of naive unconstrained allocations versus production-hardened mechanical sympathy.
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.
Alternatives Evaluated
- →Naive Approach: 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 th
- →Production-Hardened Pattern: Implement Monotonically Increasing Fencing Tokens (Martin Kleppmann design). Each lock grant increments a counter . The storage layer validates that i
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.
How does the system enforce physical resource boundaries under sudden downstream latency brownouts?
Extension Implementation Steps
- 1Track real-time latency gradients and inflight concurrency.
- 2Reject excess traffic at the ingress boundary within <0.1ms.
- 3Monitor P99 latency and verify autonomous recovery when downstream pressure subsides.
Follow-Up Trade-Offs
- ⚖Architectural Invariant: "Distributed lock leases do not guarantee safety without monotonically increasing fencing tokens validated at the persistence layer."
- ⚖Physical Resource Boundary: Dynamic admission control ensures worker threads never buffer dead requests during downstream brownouts.
Interactive Assessment & Knowledge Check
Test your understanding of the architecture decisions, data patterns, and trade-offs used in Design a Distributed Lock with Fencing Tokens.
Core Architectural Principles of Distributed Locking & Redlock Algorithm
What is the primary benefit of applying Distributed Locking & Redlock Algorithm in production systems?