system-design · intermediate

Distributed Locking & Lease Expiry — Mutual Exclusion and Fencing Tokens

The Central Question

Consider a high-concurrency payment gateway (checkoutlab.com) that processes millions of recurring monthly subscription renewals.

At midnight, a background worker process attempts to charge a user's credit card for $99.

Due to an intermittent network retry or duplicate message delivery, Worker Node A and Worker Node B process the exact same user renewal job simultaneously on separate servers.

If both workers execute the payment charge concurrently without mutual exclusion, the customer is double-charged $198, triggering financial compliance violations, chargeback fees, and user churn.

In a single monolithic process, thread synchronization mechanisms (such as Java synchronized, Go sync.Mutex, or POSIX locks) prevent concurrent thread execution using shared process memory.

However, Worker Node A and Worker Node B reside on separate physical virtual machines with separate CPU registers and RAM memory. Local in-process locks cannot synchronize actions across network boundaries.

To enforce mutual exclusion across separate network servers, distributed systems use Distributed Locks and Lease Expirations.

This lesson answers one central question: How do distributed systems enforce mutual exclusion across distinct application nodes using atomic lease acquisitions (Redis SETNX / Lua scripts & ZooKeeper ephemeral nodes), and how do engineers protect data integrity against GC pauses and clock skew using monotonic Fencing Tokens?

Why Distributed Locks Differ from Single-Process Locks

A single-process lock relies on hardware memory barriers and operating system kernel primitives. A distributed lock relies on network consensus protocols across independent nodes:

flowchart TD
  LockTypes[Locking Primitives Comparison] --> SingleProc[Single-Process Lock]
  LockTypes --> DistProc[Distributed Lock]
  
  SingleProc --> SPDesc["Operating System / RAM Mutex.<br/>Synchronizes threads on ONE physical machine.<br/>Zero network overhead ($O(1)$ CPU instruction)."]
  DistProc --> DPDesc["Network Consensus / Lease Engine.<br/>Synchronizes nodes across MULTIPLE machines.<br/>Must handle network partitions, GC pauses, & clock skew!"]

Figure 1: Taxonomy contrasting single-process mutexes against distributed locks.

Single-Process Mutex vs. Distributed Lock

The Lease Expiry Mechanism: Preventing Permanent Deadlocks

If a worker node acquires a distributed lock and then immediately suffers a power failure, kernel panic, or unhandled exception before releasing the lock, the resource remains locked forever unless the lock possesses an automatic expiration deadline.

To prevent permanent deadlocks, all production distributed locks are implemented as Leases with an explicit Time-To-Live (TTL) expiration:

$$\text{Lease Validity Window} = T_{\text{acquire}} + \text{TTL} - \Delta_{\text{clock drift}}$$

sequenceDiagram
    autonumber
    actor WorkerA as Worker Node A
    participant LockStore as Distributed Lock Store (Redis)
    actor WorkerB as Worker Node B
    
    WorkerA->>LockStore: 1. Acquire Lock (TTL = 10s, Owner = UUID-A)
    LockStore-->>WorkerA: 2. Lock Granted (Expires at T + 10s)
    
    Note over WorkerA: Worker A suffers GC Pause or Crash! (t = 10s)
    
    Note over LockStore: Lease Expires Automatically at T + 10s!
    
    WorkerB->>LockStore: 3. Acquire Lock (TTL = 10s, Owner = UUID-B)
    LockStore-->>WorkerB: 4. Lock Granted to Worker B! (Deadlock Averted)

Figure 2: Sequence diagram demonstrating automatic lease expiration averting a permanent deadlock.

Correct Implementation: Atomic Redis Lock Acquisition and Release

Implementing a distributed lock correctly in Redis requires strict atomicity for both acquisition and release:

flowchart TD
  LockLifecycle[Redis Lock Lifecycle] --> Acquire[1. Atomic Acquisition]
  LockLifecycle --> Release[2. Atomic Release]
  
  Acquire --> AcqCmd["SET lock_key uuid_token NX PX 10000<br/>NX: Set if Not Exists<br/>PX 10000: Set 10,000ms TTL"]
  Release --> RelCmd["Execute Redis Lua Script<br/>Checks if lock value == uuid_token<br/>Only deletes key if UUID matches!"]

Figure 3: Redis lock lifecycle detailing atomic SETNX acquisition and Lua script release.

1. Atomic Lock Acquisition Command

-- SET key value [NX] [PX milliseconds]
SET lock:order:89041 "uuid-a9b8-c7d6" NX PX 10000

• NX: Ensures the key is written only if it does not already exist (enforces mutual exclusion).
• PX 10000: Sets an automatic 10,000-millisecond (10-second) lease expiry TTL (prevents deadlocks).
• uuid-a9b8-c7d6: Generates a unique cryptographically secure random token per client request.

2. Safe Atomic Lock Release Lua Script

To prevent deleting another worker's active lock, release operations execute an atomic Redis Lua Script:

-- Atomic Lock Release Lua Script
-- KEYS[1]: The lock key name (e.g., "lock:order:89041")
-- ARGV[1]: The caller's unique UUID token (e.g., "uuid-a9b8-c7d6")
if redis.call("GET", KEYS[1]) == ARGV[1] then
    return redis.call("DEL", KEYS[1])
else
    return 0 -- Refuse to release lock owned by another worker!
end

The Hidden Vulnerability: GC Pauses and Clock Skew

Even with atomic SETNX acquisition and Lua script release, distributed locks based purely on time leases remain vulnerable to Garbage Collection (GC) Pauses and Process Stalls:

sequenceDiagram
    autonumber
    actor WorkerA as Worker Node A
    participant LockStore as Redis Lock Engine
    participant DB as PostgreSQL Database
    actor WorkerB as Worker Node B
    
    WorkerA->>LockStore: 1. SETNX lock:inventory (TTL = 10s)
    LockStore-->>WorkerA: 2. Granted (UUID-A)
    
    Note over WorkerA: Full GC Pause / Process Freeze! (Lasts 15 seconds)
    Note over LockStore: Lock TTL Expires at 10s!
    
    WorkerB->>LockStore: 3. SETNX lock:inventory (TTL = 10s)
    LockStore-->>WorkerB: 4. Granted (UUID-B)
    WorkerB->>DB: 5. UPDATE inventory SET stock = stock - 1 (Stock = 0)
    
    Note over WorkerA: Worker A resumes from GC Pause!
    WorkerA->>DB: 6. UPDATE inventory SET stock = stock - 1 (OVERWRITE! Stock = -1!)
    
    Note over DB: DATA CORRUPTION! Dual Writes executed concurrently!

Figure 4: Sequence diagram illustrating how a GC pause causes a lease expiration split-brain data corruption.

The Absolute Defense: Monotonic Fencing Tokens

To guarantee absolute data safety when a process stalls across lease expirations, Martin Kleppmann formalized the Fencing Token pattern.

A Fencing Token is a strictly monotonically increasing integer counter ($1, 2, 3, \dots$) issued by the lock service alongside every successful lock acquisition.

The storage resource enforces the Fencing Token Invariant:

$$T_{\text{incoming}} > T_{\text{last acknowledged}}$$

If a write arrives with a fencing token lower than or equal to the highest token previously processed, the storage service rejects the write:

sequenceDiagram
    autonumber
    actor WorkerA as Worker Node A
    participant LockStore as Lock Engine (Etcd/ZooKeeper)
    participant DB as PostgreSQL Storage Guard
    actor WorkerB as Worker Node B
    
    WorkerA->>LockStore: 1. Acquire Lock
    LockStore-->>WorkerA: 2. Granted (Fencing Token = 33)
    
    Note over WorkerA: Worker A suffers 15s GC Pause!
    Note over LockStore: Lease Expires!
    
    WorkerB->>LockStore: 3. Acquire Lock
    LockStore-->>WorkerB: 4. Granted (Fencing Token = 34)
    WorkerB->>DB: 5. WRITE Payload (Token = 34)
    DB-->>DB: 6. Update Last Token = 34. SUCCESS!
    
    Note over WorkerA: Worker A resumes from GC Pause!
    WorkerA->>DB: 7. WRITE Payload (Token = 33)
    DB-->>WorkerA: 8. REJECT WRITE! (Token 33 <= Current Token 34)

Figure 5: Sequence diagram illustrating Fencing Tokens rejecting stale writes from a paused worker node.

Complete Worked Example: CheckoutLab Flash Sale Inventory Engine

Let's examine how the CheckoutLab platform (checkoutlab.com) uses distributed locking and fencing tokens to manage high-concurrency ticket reservations:

flowchart TB
  subgraph Client Ingress
    Req[Purchase Request: Ticket #402]
  end
  
  subgraph Coordination & Storage Layer
    Req --> Worker[Inventory Worker Node]
    Worker -->|1. Acquire Lease + Fencing Token| LockEngine[(Etcd Consensus Cluster)]
    LockEngine -->>|2. Token = 10482| Worker
    
    Worker -->|3. Execute SQL Write with Token| DB[(PostgreSQL Database)]
    
    subgraph Storage Guard Validation
      DB --> Check{"Token 10482 > max_token?"}
      Check -->|YES| Commit[Commit Purchase & Update max_token = 10482]
      Check -->|NO| Rollback[ROLLBACK & Reject Stale Write!]
    end
  end
  
  style LockEngine fill:#d4edda,stroke:#28a745
  style DB fill:#cce5ff,stroke:#004085

Figure 6: Complete end-to-end architecture of CheckoutLab's ticket reservation locking engine.

PostgreSQL Fencing Token Validation DDL

-- PostgreSQL Table Schema with Fencing Token Protection
CREATE TABLE ticket_reservations (
    ticket_id BIGINT PRIMARY KEY,
    user_id BIGINT NOT NULL,
    last_fencing_token BIGINT NOT NULL DEFAULT 0,
    status VARCHAR(20) NOT NULL
);
-- Atomic SQL Reservation Transaction
UPDATE ticket_reservations
SET user_id = 89041,
    status = 'RESERVED',
    last_fencing_token = 10482
WHERE ticket_id = 402
  AND last_fencing_token < 10482; -- Fencing Guard Check!

Failure Modes and Engineering Mitigations

What You Should Remember

1. Distributed locks operate across network boundaries: Local process locks (mutexes) cannot protect shared resources across separate server containers.
2. Lease expirations prevent deadlocks: Always set an explicit TTL expiration on distributed locks to ensure automatic recovery if a worker crashes.
3. Lock acquisition and release must be atomic: Use SET ... NX PX for atomic acquisition and Lua scripts for owner-validated release.
4. Time leases cannot guarantee absolute safety: GC pauses, network delays, and NTP clock skew can cause leases to expire while workers are still processing.
5. Fencing tokens provide absolute protection: Use monotonically increasing fencing tokens ($T_{\text{incoming}} > T_{\text{last}}$) at the storage layer to reject stale writes from paused workers.

Lock Renewal Watchdog Threads

Glossary of Terms

Practice Scenario and Self-Assessment

Architecture Scenario

The pipeline uses 100 worker nodes to pick up video rendering jobs from a central database queue.

Each video rendering job takes between 30 seconds and 15 minutes to complete.

Questions:

1. Evaluate the dangers of setting a static 60-second lease TTL on the rendering job lock.
2. Design a Lease Heartbeat Auto-Renewal (Lock Extension) background thread mechanism to dynamically keep the lock alive while the video renders, and explain how Fencing Tokens protect the system if the worker hangs during rendering.

Interactive Self-Assessment

Worker A could accidentally delete Worker B's active lock if Worker A's lease expired while Worker A was delayed.

The DEL command causes Redis memory corruption on string keys.

DEL requires a full system reboot to execute.

DEL automatically drops foreign key constraints on PostgreSQL databases.

The database compares the incoming token against the highest token processed so far; since Worker A's token is lower than Worker B's token, the database rejects Worker A's stale write.

The fencing token accelerates the server CPU clock speed to un-freeze the paused process.

The fencing token re-routes network IP packets directly to the client browser.

The fencing token forces the JVM to cancel all future garbage collection pauses.

What to Learn Next

• CAP Theorem — Consistency, Availability, and Partition Tolerance: Revisit distributed systems availability principles.
• Strong vs Eventual Consistency — Trade-offs in Distributed Systems: Explore linearizability vs eventual convergence.
• Cache Eviction Policies — LRU, LFU, and FIFO: Master memory capacity eviction algorithms.

Track: Reliability and Operations

Next: Out-of-Order Event Processing

By Shubham Jain

All articles · Study paths

Shubham Jain · Learning Lab