Distributed Locking & Monotonic Fencing

In a single-process application, mutual exclusion is solved via operating system mutexes or CPU atomic instructions (CMPXCHG). The CPU hardware bus arbitration guarantees that only one thread enters the critical section. In a distributed system, there is no shared memory, no hardware bus, and no synchronized clock.

Without storage-enforced monotonic fencing tokens, a distributed lock provides only an illusion of safety, guaranteeing data corruption under ordinary production operating conditions.

Martin Kleppmann (author of Designing Data-Intensive Applications) established the theoretical framework for distributed locks: you must explicitly categorize why you are locking.

Consider the classic failure trace documented by Martin Kleppmann in his critique of the Redlock algorithm. Client 1 acquires a lock to write to an object store, but is halted by an unexpected operating system pause.

1. 01Step 1: Lock Acquisition. Client 1 requests a lock on resource_customer_100 from Redis with a 10-second TTL. Redis successfully grants the lock.
2. 02Step 2: The Stop-the-World Pause. Client 1’s JVM triggers a major Garbage Collection pause (or the OS deschedules the container during heavy memory swapping) lasting 15 seconds.
3. 03Step 3: Lease Expiration. While Client 1 is frozen in GC, 10 seconds elapse. Redis automatically expires the lock lease on resource_customer_100 and frees the key.
4. 04Step 4: Lock Re-grant. Client 2 requests a lock on resource_customer_100. Redis grants the lock to Client 2 with a fresh 10-second lease.
5. 05Step 5: Client 2 Writes. Client 2 enters the critical section, writes version 2 of the customer record to storage, and safely releases the lock.
6. 06Step 6: Client 1 Awakens & Corrupts Data. Client 1’s GC cycle completes. Client 1 resumes execution at the exact line of code following lock acquisition! Client 1 has no idea that 15 seconds have passed, believes it still owns the lock, and writes its stale version 1 data to storage, completely overwriting and destroying Client 2’s committed updates!

To make distributed locks safe for correctness, mutual exclusion must be enforced by the storage layer using monotonically increasing Fencing Tokens.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

// PRODUCTION DISTRIBUTED LOCK WITH FENCING TOKEN & STORAGE VALIDATION
import { createHash, randomBytes } from 'crypto';

export interface FencedLockGrant {
  lockKey: string;
  lockToken: string;      // Unique random secret for safe release
  fencingToken: number;   // Monotonically increasing sequence number
  expiresAtMs: number;
}

export interface StorageRecord<T> {
  id: string;
  payload: T;
  lastFencingToken: number; // Highest fencing token committed
}

// 1. STORAGE LAYER: Monotonic Fencing Validator
export class FencedStorageEngine<T> {
  private records: Map<string, StorageRecord<T>> = new Map();

  // Storage validates fencing token on EVERY write
  public write(id: string, payload: T, clientFencingToken: number): { success: boolean; error?: string } {
    const existing = this.records.get(id);

    if (existing) {
      // INVARIANT: Reject any write carrying an older or equal fencing token!
      if (clientFencingToken <= existing.lastFencingToken) {
        return {
          success: false,
          error: `STALE_FENCING_TOKEN: Rejected token ${clientFencingToken}. Highest committed is ${existing.lastFencingToken}.`,
        };
      }
    }

    // Accept write and update highest committed fencing token
    this.records.set(id, {
      id,
      payload,
      lastFencingToken: clientFencingToken,
    });

    return { success: true };
  }

  public read(id: string): StorageRecord<T> | undefined {
    return this.records.get(id);
  }
}

// 2. COORDINATOR LAYER: Distributed Lock Manager with Atomic Monotonic Fencing Tokens
export class RedisDistributedLockManager {
  // CRITICAL DISTRIBUTED REALITY: Fencing tokens MUST be strictly monotonic and
  // generated server-side by the coordinator (e.g., Redis atomic INCR, ZooKeeper zxid,
  // or etcd cluster revision). A client-side memory counter clobbers across multiple app nodes.

  public async acquireLock(
    redisClient: any,
    resource: string,
    ttlMs: number
  ): Promise<FencedLockGrant | null> {
    const lockToken = randomBytes(16).toString('hex');
    const lockKey = `lock:${resource}`;
    const fencingCounterKey = `lock:fence:${resource}`;

    // Atomic acquisition & monotonic token assignment via Lua script:
    // 1. SET lockKey lockToken NX PX ttlMs
    // 2. If acquired, INCR fencingCounterKey and return token; else return nil
    const acquireLuaScript = `
      if redis.call("set", KEYS[1], ARGV[1], "NX", "PX", ARGV[2]) then
        local token = redis.call("incr", KEYS[2])
        return { ARGV[1], token }
      else
        return nil
      end
    `;

    const result = await redisClient.eval(acquireLuaScript, 2, lockKey, fencingCounterKey, lockToken, ttlMs);
    if (!result) return null;

    return {
      lockKey,
      lockToken: result[0],
      fencingToken: Number(result[1]),
      expiresAtMs: Date.now() + ttlMs,
    };
  }

  // ATOMIC RELEASE VIA LUA SCRIPT:
  // Must verify value matches lockToken before deleting to avoid releasing someone else's lock!
  public getReleaseLuaScript(): string {
    return `
      if redis.call("get", KEYS[1]) == ARGV[1] then
        return redis.call("del", KEYS[1])
      else
        return 0
      end
    `;
  }
}

1. 01Step 1: Lock Grant to Client 1. Client 1 acquires lock on /order/101 from the coordinator. The coordinator issues Fencing Token 33 with a 10s TTL.
2. 02Step 2: Client 1 GC Freeze. Client 1’s virtual machine pauses for 12 seconds due to host memory swapping. The 10s TTL expires in the coordinator.
3. 03Step 3: Lock Grant to Client 2. Client 2 requests the lock on /order/101. The coordinator grants the lock and issues monotonically incremented Fencing Token 34.
4. 04Step 4: Client 2 Commits with Token 34. Client 2 sends UPDATE orders SET status = "SHIPPED", fencing_token = 34 WHERE order_id = 101 AND 34 > fencing_token. The database verifies 34 > 0, commits the change, and stores lastFencingToken: 34.
5. 05Step 5: Client 1 Awakens with Stale Token 33. Client 1 awakens from its GC pause. Believing it is still the legitimate lock owner, it transmits UPDATE orders SET status = "CANCELLED", fencing_token = 33 WHERE order_id = 101 AND 33 > fencing_token.
6. 06Step 6: Database Storage Rejection. The database evaluates the atomic predicate: 33 > 34 evaluates to FALSE! The database rejects Client 1’s write with 0 rows affected. Client 2’s data remains pristine. Catastrophe averted!

1. 01The Accidental Lock Release Catastrophe: Client A acquires a lock with a 5s TTL. Due to a slow SQL query, Client A takes 7 seconds. At 5 seconds, Redis expires the lock. Client B acquires the lock. At 7 seconds, Client A finishes and blindly executes redis.del("lock_key")! Client A has just deleted Client B’s valid lock! Now Client C acquires the lock, resulting in two active workers. Solution: Always release locks via Lua script matching a unique secret token.
2. 02The Clock Jump Acceleration Bug: In Redlock, if 3 out of 5 Redis servers have their physical NTP clocks adjusted forward by 10 seconds, keys with a 5s TTL expire immediately. A client that just acquired the lock loses it within milliseconds, leading to multiple clients entering the critical section simultaneously.
3. 03Thundering Herd on Lock Release: 500 workers attempt to acquire the same lock in Redis via polling loops. When the lock owner releases it, all 500 workers hammer Redis with SET NX within 1ms, saturating Redis CPU and network buffers. Solution: Use ZooKeeper/etcd watches where only the next sequential waiter is notified.