Distributed Locking in Practice: Fencing Tokens, Redlock Fallacies, and Raft Leases

In multi-node software engineering, distributed locking is often treated as a solved problem: an engineer installs a popular Redis library, executes SET lock:resource random_val NX PX 10000, and wraps their critical section in an asynchronous block. If multiple Redis nodes are involved, they deploy the Redlock algorithm, assuming that acquiring a quorum of locks across independent Redis instances guarantees safety.

Yet in computer science theory and high-scale production systems, this confidence is dangerously misplaced. In an asynchronous network model—where network packets can be delayed arbitrarily, clocks drift unpredictably, and process threads can be suspended for seconds by Garbage Collection pauses or virtual machine hypervisor migration—a distributed lock service by itself cannot guarantee mutual exclusion.

When a client holding a time-bounded lease pauses, its lease naturally expires. A second client acquires the lock and begins writing. When the first client finally awakens, it remains completely unaware that its lock expired and proceeds to execute its write—silently overwriting valid data and corrupting storage. In this rigorous systems guide, we will analyze the mathematical realities of distributed locks, examine the historic Kleppmann-Antirez debate, implement monotonic fencing tokens, and compare Redis with consensus-backed engines like etcd, Consul, and PostgreSQL advisory locks.

1. The Asynchronous System Model: Why Clocks and Time Fail

To understand why distributed locks fail, we must define the physical environment in which our code runs. Real-world distributed systems operate under the Asynchronous System Model with Crash-Recovery:

• Unbounded Network Delays: A packet sent over TCP can arrive in 0.5 milliseconds, or it can be buffered in a congested switch or TCP retransmission queue for 45 seconds without the sender knowing.
• Unbounded Process Pauses: An application thread can be halted at any arbitrary instruction point. Pauses are triggered by stop-the-world Garbage Collection sweeps (Java, .NET, Go), OS virtual memory page faults, hypervisor vCPU descheduling on shared cloud instances, or SIGSTOP process freezing.
• Unreliable Physical Clocks: Hardware quartz oscillators drift over time due to thermal fluctuations. Network Time Protocol (NTP) synchronizes clocks across servers, but NTP can make backwards clock jumps, fail to sync, or be manipulated by leap seconds.

Because of these realities, no distributed algorithm can rely on wall-clock elapsed time for safety. If your algorithm requires that "Client A must finish its work within 10 seconds of acquiring the lock," it will inevitably fail when Client A is paused for 11 seconds between checking its timer and issuing its storage write.

2. The Redlock Controversy: Kleppmann vs. Antirez

In 2016, distributed systems researcher Martin Kleppmann (author of Designing Data-Intensive Applications) published a landmark critique of the Redis Redlock algorithm. Redlock attempts to achieve fault-tolerant locking by asking an odd number of independent Redis nodes (typically 5) to acquire a lock using SET NX PX. If a client acquires a majority (3 of 5) within a given timeout, it considers the lock held.

Kleppmann's Two Fatal Counter-Examples

1. The Stop-the-World Pause: A client acquires the lock on 3 Redis nodes. Before it can write to storage, its runtime hits a 15-second GC pause. During this pause, the Redis TTLs expire. Another client acquires the lock across 3 nodes and writes to storage. The first client resumes execution, believes it still holds the lock, and writes to storage. Mutual exclusion is violated; data is corrupted.
2. NTP Clock Jumps: If Node 3 experiences an NTP step-forward clock jump (e.g., due to a misconfigured time daemon), its TTL expires prematurely. A second client can now acquire a majority quorum simultaneously with the first client!

Salvatore Sanfilippo (Antirez), the creator of Redis, argued that in practice, process pauses are usually shorter than lock TTLs and that administrators can configure NTP to slew rather than jump. However, as Kleppmann conclusively demonstrated, relying on timing assumptions for correctness turns a safety property into an accidental probability.

3. The Only Mathematical Defense: Monotonic Fencing Tokens

How do we make distributed locking 100% safe against process pauses, network partitions, and zombie clients? The answer is Fencing Tokens.

How Fencing Tokens Work

1. When a client requests a lock, the lock coordinator does not merely return a boolean OK. It grants the lock alongside a monotonically increasing integer token (e.g., Token #34).
2. If Client 1 pauses and its lease expires, Client 2 acquires the lock. The coordinator grants Client 2 a strictly higher token: Token #35.
3. Client 2 writes its payload to the storage layer (database, object store, or file system), passing token = 35. The storage layer records that the highest observed token is now 35, and commits the write.
4. Client 1 awakens from its GC pause and attempts to write to the storage layer, passing its stale token = 34.
5. The Storage Gatekeeper Check: The storage service evaluates:

   $$\text{If } \text{incoming\_token} \le \text{highest\_seen\_token} \implies \mathbf{REJECT}$$

   Because $34 \le 35$, the storage layer immediately aborts the write with a StaleTokenException!

The Fundamental Axiom: You cannot achieve distributed mutual exclusion at the lock service alone. The resource being protected must enforce fencing at its boundary.

4. Consensus-Backed Leases: etcd and Consul vs. Redis

If you require distributed locks, you must choose the right coordinator. There are two fundamentally different classes of lock managers:

Why etcd is strictly superior for safety: In etcd, every modification increments a global, monotonic 64-bit counter called revision. When an application acquires an etcd lease, the transaction's Header.Revision provides a mathematically verified, monotonically increasing fencing token out of the box, backed by Raft quorum consensus.

5. Production Implementation in C# and SQL

Below is a production-grade C# implementation demonstrating a distributed lock manager with monotonic fencing token generation and storage-side compare-and-swap (CAS) validation:

using System;
using System.Data;
using System.Threading;
using System.Threading.Tasks;
using Microsoft.Data.SqlClient;

public record LockGrant(string ResourceName, long FencingToken, DateTimeOffset LeaseExpiresAt);

public interface IDistributedLockService
{
    Task TryAcquireLockAsync(string resource, TimeSpan ttl, CancellationToken ct);
    Task ReleaseLockAsync(string resource, long fencingToken);
}

public sealed class FencedStorageManager
{
    private readonly string _dbConnectionString;

    public FencedStorageManager(string dbConnectionString)
    {
        _dbConnectionString = dbConnectionString;
    }

    /// <summary>
    /// Executes a fenced write against shared database state.
    /// Rejects any write attempted with an out-of-order or expired fencing token.
    /// </summary>
    public async Task ExecuteFencedWriteAsync(
        string accountId, 
        decimal newBalance, 
        long clientFencingToken, 
        CancellationToken ct)
    {
        using var conn = new SqlConnection(_dbConnectionString);
        await conn.OpenAsync(ct);

        using var cmd = conn.CreateCommand();
        // Atomic compare-and-swap update enforced by SQL constraint
        cmd.CommandText = @"
            UPDATE Accounts
            SET Balance = @NewBalance,
                LastFencingToken = @Token,
                UpdatedAt = SYSUTCDATETIME()
            WHERE AccountId = @AccountId 
              AND LastFencingToken 

6. The Decision Rubric: Efficiency vs. Correctness

When selecting a distributed lock mechanism, ask one foundational question: What happens if two nodes acquire the lock at the same time?

1. Case A: Efficiency Optimization (It only wastes compute)

   Example: You run a background job that generates a cached thumbnail image or scrapes weather data. If two workers run it simultaneously, you waste 500ms of CPU time, but the outcome is identical.

   Verdict: A simple single-instance Redis lock with SETNX or Redlock is completely acceptable. Speed and low latency trump theoretical correctness.

2. Case B: Safety-Critical Correctness (It corrupts money or data)

   Example: Processing bank account disbursements, issuing unique sequential invoice numbers, or orchestrating primary database failover.

   Verdict: Never use Redis. Use a Raft/Paxos-backed coordinator (etcd, Consul) or relational transactional locks (PostgreSQL Advisory Locks), and always enforce monotonic fencing tokens at the storage layer.