Distributed Locking Mechanics: Lease Expiration, Redlock, and ZooKeeper Fencing Tokens

Why You Need This in Real Life

Two background worker nodes, Worker A and Worker B, poll an unassigned billing job queue. Worker A acquires a distributed lock in Redis with a 10-second Time-To-Live (TTL) lease: SET lock:job_42 worker_a NX PX 10000.

Worker A begins writing financial records to a shared storage cluster. But mid-process, Worker A experiences a Garbage Collection (GC) Stop-The-World pause lasting 12 seconds.

While Worker A is frozen in GC pause:

The 10-second Redis TTL lease expires on the server.
Worker B polls Redis, finds lock:job_42 free, and acquires the lock.
Worker B begins updating the shared storage cluster.
Worker A’s GC pause ends. Unaware that its lease expired, Worker A executes its pending write!

Worker A and Worker B write conflicting data simultaneously, corrupting storage records.

Distributed locking is deceptively difficult. To prevent race conditions, you must understand lease TTL expiration, Martin Kleppmann’s famous critique of Redis Redlock, ZooKeeper Ephemeral Sequential Nodes, and Fencing Tokens.

Part 1: Why Naive Distributed Locks Break

A naive distributed lock in Redis uses single-key atomic commands:

Acquire Lock: SET resource_name my_random_id NX PX 30000
Release Lock: EVAL "if redis.call('get',KEYS[1]) == ARGV[1] then return redis.call('del',KEYS[1]) else return 0 end" 1 resource_name my_random_id

The Three Failure Modes

Process Pauses (GC / Page Faults): As demonstrated in our opening scenario, a client process can freeze after acquiring the lock, causing the TTL lease to expire while the client still thinks it owns the lock.
Clock Skew Delays: If Redis server system clocks drift due to NTP steps, a 30-second TTL can expire in 15 physical seconds.
Unsynchronised Asynchronous Replication: If Client A acquires a lock on a Redis Master, and the Master crashes before replicating the key to a Slave node, the promoted Slave node will grant the exact same lock to Client B!

Part 2: The Redis Redlock Algorithm & Kleppmann’s Critique

To solve master node crash failures, Salvatore Sanfilippo (antirez) created Redlock. Redlock uses $N=5$ independent Redis master nodes.

Redlock Acquisition Protocol

Client fetches current timestamp $T_1$ in milliseconds.
Client attempts to acquire the lock sequentially on all 5 Redis instances using matching keys and random values.
If Client acquires the lock on a majority ( $3$ out of $5$ ) nodes within a total elapsed time less than the TTL, the lock is considered acquired.

Martin Kleppmann’s Famous Critique (2016)

Distributed systems researcher Martin Kleppmann published a detailed analysis demonstrating that Redlock is unsafe for systems requiring correctness:

Redlock relies on physical system clock assumptions. If one of the 5 Redis nodes experiences clock drift or NTP stepping, the safety invariants break.
Redlock cannot protect storage backends if a process experiences a GC pause after acquiring the majority of locks.

Worker A                                   Redis Master Cluster                  Storage Server
   |                                                |                                  |
   |-- 1. Acquire Lock (Majority 3/5) ------------->|                                  |
   |   (Lock Granted, TTL = 10s)                    |                                  |
   |                                                |                                  |
   |== [ 15s STW GC PAUSE! Lease Expires! ] ========|                                  |
   |                                                |                                  |
   |                                      Worker B acquires Lock                       |
   |                                      Worker B writes to Storage ----------------->|
   |                                                                                   |
   |-- 2. Resume Write (Unaware lease expired!) -------------------------------------->|
   |   (CORRUPTS STORAGE!)                                                             |

Part 3: The True Solution: Fencing Tokens

To guarantee safety when process pauses or network delays occur, the storage system receiving the write must enforce lock validation using a Fencing Token.

A Fencing Token is a monotonically increasing integer sequence number returned by the lock service whenever a lock is granted.

Worker A                    Lock Service                    Storage Service
   |                             |                                 |
   |-- 1. Acquire Lock --------->|                                 |
   |<-- Grant (Token = 33) ------|                                 |
   |                                                               |
   |== [ STW GC Pause! Lease Expires! ] ===========================|
   |                                                               |
   | Worker B                    |                                 |
   |-- Acquire Lock ------------>|                                 |
   |<-- Grant (Token = 34) ------|                                 |
   |                             |                                 |
   | Worker B writes to Storage (Token = 34) --------------------->| (Accepts Write! Current = 34)
   |                                                               |
   | Worker A resumes write (Token = 33) ------------------------->|
   |                                                               | (REJECTS WRITE! Token 33 < 34!)

The Fencing Rule

The target storage system remembers the highest fencing token it has processed ( $34$ ). When Worker A attempts to write using an outdated token ( $33$ ), the storage system rejects the write request, rendering Worker A’s late operation harmless!

Part 4: Distributed Locks with ZooKeeper Ephemeral Nodes

ZooKeeper provides production-grade distributed locking built on top of consensus (ZAB protocol) and Ephemeral Sequential Nodes.

ZooKeeper Lock Execution Steps

Client creates an ephemeral sequential znode under a lock directory: /locks/lock_node_0000000033.
Client lists all child nodes under /locks/.
If the client’s znode has the lowest sequence number, the client owns the lock!
If not, the client registers a Watcher notification on the immediately preceding znode (lock_node_0000000032).
When the preceding znode is deleted (lock released or client disconnects), ZooKeeper notifies the waiting client, avoiding thundering herd problems.

Lock Directory: /locks/
├── lock_0000000031 (Active Lock Owner)
├── lock_0000000032 (Waiting - Watches 31)
└── lock_0000000033 (Waiting - Watches 32)

Because ZooKeeper znodes are ephemeral, if a client node crashes or suffers a network partition, ZooKeeper automatically deletes the client’s znode, releasing the lock safely.

Next Steps

Having covered distributed consensus, locking, and fencing tokens, we will enter Module 4 (High-Availability Traffic Control & Resilience): starting with Distributed Rate Limiters in Part 10.

References & Further Reading

Mitzenmacher, M. (2001). The Power of Two Choices in Randomized Load Balancing. IEEE TPDS, 12(10), 1094–1104.
HAProxy Technologies. HAProxy Architecture Guide — Layer 4 vs Layer 7 Load Balancing. HAProxy Docs.
CNCF Envoy Project. Envoy Proxy Load Balancing Policies & Architecture. Envoy Docs.