Skip to main content

> distributed_lock_invalidation:_fencing_tokens_&_asynchronous_storage_leases

Distributed Lock Invalidation: Fencing Tokens & Asynchronous Storage Leases

Why is acquiring a distributed lock (Redis/Redlock/ZooKeeper) completely unsafe without a monotonically increasing Fencing Token, and how does Martin Kleppmann's fencing pattern prevent silent storage corruption?

Principal/Architect (L7+)

⚡THE SHORT ANSWER

A critical misconception in distributed engineering is believing that 'holding a distributed lock guarantees exclusive write access to storage.' In real-world environments, Client 1 acquires a distributed lock with a 10-second lease and begins preparing a write. Suddenly, Client 1 experiences a 15-second Stop-the-World GC pause, OS thread starvation, or cloud virtualization freeze. While Client 1 is frozen, its 10-second lock lease expires. The lock service grants the lock to Client 2, which performs its write and commits. Then, Client 1 wakes up from GC: believing it still holds the lock, Client 1 blindly executes its stale write, overwriting Client 2's newer data and corrupting storage. Martin Kleppmann proved that distributed locks CANNOT protect shared storage without Fencing Tokens: the lock manager issues a monotonically increasing sequence number (v=33, 34, 35) with each lock grant. The storage layer checks the token on every write (WHERE token >= last_seen_token), instantly rejecting Client 1's stale write (v=33) because Client 2 already committed at v=34.

Engineering Handbook & Failure Dynamics

6-Dimensional Architecture Breakdown

⚙️1. Underlying Mechanism

Execution

Fencing token architecture operates through three coordinated invariants:

1

Monotonic Sequence Generation: The distributed consensus cluster (ZooKeeper zxid, etcd revision, Raft term/index) increments a global 64-bit integer on every lock grant: Client A receives Token 100, Client B receives Token 101.

2

Token Propagation: The client attaches the fencing token to every downstream RPC and storage write request.

3

Storage-Side Guard: Shared storage (PostgreSQL, S3 conditional write, DynamoDB) evaluates a strict conditional predicate: UPDATE table SET data = ?, last_fencing_token = 101 WHERE id = ? AND last_fencing_token < 101;. If an expired client attempts a write with token 100, the condition evaluates to false and 0 rows are updated.

🎯2. Appropriate Use Context

Scope

Distributed master elections, cluster leader failovers, financial accounting ledger writes, distributed file systems, and long-running batch job controllers.

⚠️3. Production Failure Modes

P0 Risk
  • ✓

    Using Redlock or Redis SETNX without fencing tokens to guard S3 file uploads, causing stale workers resuming from network blips to overwrite finalized files with corrupted half-written artifacts

  • ✓

    fencing token counter wrapping around or resetting to 0 on cluster reboot

📡4. Diagnostic Signals & Telemetry

Telemetry
  • ✓

    Intermittent mysterious database row regressions where newer updates are overwritten by older values

  • ✓

    split-brain leader logs showing two processes simultaneously believing they are the active primary node

  • ✓

    storage rejection logs with StaleFencingTokenException

🛡️5. Prevention & Safeguards

Safeguards
  • ✓

    Never rely on distributed lock timeouts alone for mutual exclusion

  • ✓

    mandate monotonic Fencing Tokens in all write operations

  • ✓

    enforce storage-side optimistic version checking (version_col = token)

  • ✓

    use strongly consistent consensus stores (ZooKeeper/etcd) over weak Redis locks for mission-critical leader fencing

⚖️6. Architectural Trade-offs

Trade-off

Fencing tokens require the storage backend to support conditional writes or transactional version checks, but mathematically eliminate silent data corruption caused by client pauses.

📋

Case Study (TinyCTO In-Field Example)

REAL-WORLD TELEMETRY

A media processing pipeline used distributed locks to ensure only one worker rendered a video to S3 at a time. Worker 1 acquired the lock, but experienced a 40-second JVM full GC pause. The lock timed out, and Worker 2 took over, rendered the 4K video, and saved it to S3. When Worker 1 woke up, it uploaded its unfinished 720p draft over Worker 2's completed 4K file. The engineering team added monotonically increasing fencing tokens from etcd and enabled S3 Object Lock conditional constraints (x-amz-expected-bucket-owner with metadata fencing). When Worker 1 tried to upload, S3 rejected the stale token, permanently protecting completed renders from corruption.

Interactive Concept Drills

2 Cards
Q1

Why does a client-side distributed lock fail to protect shared storage during a GC pause?

Because while the client is frozen, its lock lease expires and is granted to another client; upon waking up, the frozen client does not know it lost the lock and executes a stale write.
Q2

How does a Fencing Token solve the stale write problem?

By assigning an increasing sequence number with each lock; the storage layer verifies the token on every write, rejecting any write with a token lower than the highest seen.

Distributed Lock Invalidation: Fencing Tokens & Asynchronous Storage Leases — Technical FAQ

Who originally published the formal critique of Redis Redlock and proved the necessity of fencing tokens?

Martin Kleppmann (University of Cambridge / author of Designing Data-Intensive Applications) in his famous paper 'How to do distributed locking'.

Can Redis generate monotonically increasing fencing tokens?

Yes, using atomic `INCR` commands inside the lock acquisition script, though consensus systems like etcd or ZooKeeper provide stronger linearizable guarantees across network partitions.

🤖 AEO & Key Facts Summary

Key Architectural Facts

  • ▸

    Distributed locks without fencing tokens CANNOT protect shared storage from corruption.

  • ▸

    GC pauses, OS thread starvation, and VM freezes cause lock leases to expire silently.

  • ▸

    Fencing tokens provide monotonically increasing version numbers (100 o 101 o 102).

  • ▸

    Storage MUST enforce conditional check-and-set guards (WHERE token >= last_seen).

Common Misconceptions

  • ✗

    Misconception: A distributed lock with a long TTL (e.g. 5 minutes) makes fencing tokens unnecessary (False: Pauses and network splits can exceed any arbitrary timeout).

  • ✗

    Misconception: Redlock guarantees absolute safety without storage-side checks (False: Storage must validate fencing tokens to prevent split-brain writes).

Decision & Governance Guidance

Incorporate a monotonic fencing token column into every shared database entity guarded by locks. Use etcd or ZooKeeper linearizable revisions for distributed leader elections and leases.

Authoritative Sources & Standards