A system design interview walkthrough

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.

Start the walkthrough30 min · 8 RESHADED stages

REQUIREMENTS. ARCHITECTURE. SCALE.

Difficulty: hardFocus: distributed-locking, split-brain-preventionFramework: RESHADED 8-step guide

Less boilerplate. More understanding.

01 Learn the idea02 Follow the visual03 Know the limits

RESHADEDRequirements → Estimation → Storage → High-level design → API → Detailed design → Evaluation → Discussion.

Define the boundaries.

Requirements · 4 minutes

SAY THIS: “Before proposing a topology for Design a Distributed Lock with Fencing Tokens, I’ll clarify the core functional requirements, burst characteristics, data volume, and availability SLOs to define rigid system boundaries.”

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.

What the system does

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.

What to agree on

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.

Size the critical path.

Estimation · 3 minutes

SAY THIS: “Let’s establish order-of-magnitude sizing for peak throughput, memory footprint, and network ingress to size the critical latency path before making technology choices.”

100k+PEAK THROUGHPUT

< 5 msTARGET LATENCY

10M+SCALE TARGET

At an illustrative 200 bytes per record/session, high-volume state requires dedicated primary in-memory partitions. Add replicas, allocator overhead, policy indexes, and headroom.

throughput = peak_qps × (1 + headroom_margin) state_ram ≈ active_entities × per_record_bytes × replication_factor

Always validate throughput and p99 latency targets under skewed traffic distributions and replica failovers.

Keep state shared and partitioned.

Storage · 3 minutes

SAY THIS: “I’ll separate low-latency ephemeral cache state from authoritative durable storage, ensuring strict consistency where needed and partitioning for scale.”

Cache / Ephemeral state

state:{partitionKey}:activeWindow

In-memory key-value cache (Redis Cluster / Memcached).
TTL expiration matching window validity bounds.
Hash tags to co-locate keys for atomic Lua scripts or transactions.

Durable / Authoritative store

Distributed NoSQL / relational database (DynamoDB, PostgreSQL).
Durable write-ahead log with replica failover.
Cache-aside pattern: read misses warm cache from durable store.
Asynchronous CDC / event streaming to telemetry sinks.

Local-only node state is not a shared cluster quota: N nodes could admit roughly N × the configured limits. Ensure state co-location and transactional boundaries align with partition keys.

Make the decision at ingress.

High-level design · 4 minutes

SAY THIS: “The gateway tier authenticates incoming traffic, validates payloads, and routes requests to decoupled services backed by partitioned caching and authoritative storage tiers.”

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 / Bacquire lock & token

→

Lock Servicemonotonic token dispenser

→

Storage Enginevalidate token > last_seen

↕ lease renewal & TTL management

Redis / ZooKeeper Leasesephemeral znode / NX PX lease

Storage rejects stale tokens (e.g. Token 33 < Token 34) caused by client GC pauses or network partitions.

FIG. 01 — MONOTONIC FENCING TOKEN VALIDATION & SPLIT-BRAIN PREVENTION

Use tight timeouts, circuit breakers, and rate-limiting middleware at ingress to protect downstream services from cascading collapse.

Define the contract.

API · 3 minutes

SAY THIS: “The API contract establishes idempotent mutation semantics, clear error taxonomy, and explicit status codes so upstream clients can safely retry.”

execute(requestId, payload, idempotencyKey) → { status, resourceId, metadata }

Success Path

Forward the request or return HTTP 200/201. Include standard tracking and rate/quota telemetry headers in the response.

Failure & Fallback

Use explicit HTTP status codes: 400 for invalid input, 429 for quota violations, and 503 with Retry-After during maintenance or partitions.

View example API payload contract

HTTP · APPLICATION CONTRACT

HTTP/1.1 200 OK
Content-Type: application/json
Cache-Control: max-age=300

{
  "status": "success",
  "data": { "id": "res_98a7f", "processedAt": "2026-11-11T12:00:00Z" }
}

Include idempotency keys on write endpoints to guarantee at-most-once processing across network retries.

Make state mutations atomic.

Detailed design · 7 minutes

SAY THIS: “For the critical execution path, we enforce idempotency and concurrency controls using atomic primitives, avoiding lock contention and split-brain states.”

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.

STRATEGY / PATTERN	WHY CHOOSE IT?	TRADE-OFF / COST
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	Coordinate partition dependencies
Production-Hardened Pattern	Implement Monotonically Increasing Fencing Tokens (Martin Kleppmann design). Each lock grant increments a counter . The storage layer validates that i	Coordinate partition dependencies

View reference production code implementation

LUA · REFERENCE IMPLEMENTATION

-- 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

Avoid client-side read-modify-write loops without concurrency control. Use atomic scripts, row-level locks, or conditional mutations at the storage tier to guarantee linearizability.

View sequence trace & failure interaction flow

INTERACTION TRACE · SEQUENCE DIAGRAM

[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!)

Stress-test the design.

Evaluation · 6 minutes

SAY THIS: “The biggest operational risks involve node failover, partition skew, network isolation, and cascading downstream backpressure. Here is how we mitigate each.”

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.

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.

Close with the trade-offs.

Discussion · 5 minutes

SAY THIS: “In closing, we optimized for sub-millisecond p99 latency and high availability under partition. We trade strict distributed linearizability for predictable throughput and operational simplicity.”

If the interviewer asks…

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.

Keep the conclusion focused

What guarantees are strictly enforced at runtime?
What happens during network partitions or node failures?
Which CAP trade-off was intentionally chosen and why?

The 30-second summary