Fencing Tokens and Monotonic IDs: Making Distributed Locks Actually Safe

Terminology

What & Why

The Problem: Locks Alone Cannot Guarantee Safety

The previous post showed that distributed locks are advisory and that process pauses can cause lease expiration while the holder is still working. The lock server does its best, but it cannot control what happens after the lease expires. A paused client will resume and write to the shared resource, unaware that another client now holds the lock.

The core issue is that the lock server and the storage layer are separate systems. The lock server knows the lease expired, but the storage layer does not. Without a mechanism to connect these two systems, the storage layer will accept any write that arrives, regardless of whether the writer still holds a valid lock.

The Solution: Fencing Tokens

A fencing token is a monotonically increasing number that the lock server issues with each lock acquisition. Every time a client acquires the lock, it receives a token that is strictly greater than any previously issued token. The client must include this token with every write to the storage layer.

The storage layer tracks the highest token it has seen (max_seen). When a write arrives, the storage layer compares the write's token against max_seen. If the token is less than or equal to max_seen, the write is rejected. If it is greater, the write is accepted and max_seen is updated.

Why the Storage Layer Must Be the Final Arbiter

The lock server cannot enforce safety because it has no control over the network or the client's execution. Once a lease is granted, the lock server is out of the loop. The client might pause, the network might delay messages, or the client might simply ignore the lock expiration.

The storage layer, on the other hand, is the last stop before data is written. It sees every write request and can make a decision based on the fencing token. By making the storage layer responsible for rejecting stale writes, the system moves the safety guarantee to the only place that can actually enforce it.

How It Works

The Fencing Token Protocol

The complete protocol involves three actors: the lock server, the client, and the storage layer. The lock server maintains a monotonically increasing counter. Each lock acquisition increments the counter and returns the new value as the fencing token.

The key insight: Client A's write is rejected not because the lock server told the storage layer anything, but because the storage layer independently tracks the highest token it has seen. The lock server and storage layer do not need to communicate directly. The fencing token, carried by the client, is the communication channel.

Token Validation at the Storage Layer

The storage layer maintains a single variable per protected resource: max_seen. The validation logic is simple: accept if the incoming token is strictly greater than max_seen, reject otherwise.

This is the entire algorithm. There is no complex state machine, no consensus protocol, no quorum. Just a single comparison per write. The simplicity is the point: fencing tokens add minimal overhead while providing a strong safety guarantee.

The Complete Fencing Architecture

The architecture has three components, each with a clear responsibility. The lock server generates tokens, the client carries them, and the storage layer validates them.

Token Sequence and max_seen Tracking

As the lock server issues tokens over time, the storage layer's max_seen value ratchets upward. It never decreases. This monotonic property is what makes the system safe: once a higher token has been accepted, all lower tokens are permanently invalid.

Storage Validation: Accept or Reject

Walking through a sequence of writes to see which get accepted and which get rejected. The pattern is clear: any write with a token less than or equal to the current max_seen is rejected.

Connection to Linearizability

Fencing tokens create a total order on lock acquisitions. Because each token is strictly greater than the previous one, and the storage layer enforces this order, the system achieves a form of linearizability for the protected resource. Every accepted write corresponds to the most recent lock holder, and stale writes from previous holders are rejected.

This is the same principle behind leader epochs in consensus protocols like Raft. When a new leader is elected, it gets a higher term number (epoch). Followers reject messages from leaders with lower term numbers. The fencing token is the distributed lock equivalent of the Raft term number.

Complexity Analysis

Fencing tokens add minimal overhead to the system. The cost is dominated by the lock acquisition itself, not the token validation.

Token generation uses an atomic increment, which is $O(1)$ on a single node. Storage validation is a single comparison, also $O(1)$. The total per-operation overhead is constant, regardless of the number of clients or the contention level.

Compare this with the alternative of using a full consensus protocol for every write, which costs $O(N)$ network round trips for $N$ nodes. Fencing tokens achieve safety with $O(1)$ additional overhead by pushing the validation to the storage layer.

Implementation

Pseudocode for the fencing token protocol. The lock server, client, and storage layer each have a simple role.

// Lock Server
GLOBAL token_counter = 0

FUNCTION acquire_lock(resource, client_id, ttl):
    IF resource is not locked OR lease has expired:
        token_counter = token_counter + 1   // atomic increment
        SET lock(resource) = {holder: client_id, ttl: ttl}
        RETURN {acquired: true, token: token_counter}
    ELSE:
        RETURN {acquired: false}

// Client
FUNCTION do_work_with_lock(resource, lock_server, storage):
    result = lock_server.acquire_lock(resource, MY_ID, ttl)
    IF NOT result.acquired:
        RETURN FAILURE("could not acquire lock")

    TRY:
        data = compute_new_value()
        response = storage.fenced_write(resource, data, result.token)
        IF response == REJECTED:
            RETURN FAILURE("stale token, lock was lost")
        RETURN SUCCESS
    FINALLY:
        lock_server.release(resource, MY_ID)

// Storage Layer
GLOBAL max_seen = {}   // map from resource to highest accepted token

FUNCTION fenced_write(resource, data, token):
    current_max = max_seen.GET(resource, default=0)
    IF token <= current_max:
        RETURN REJECTED   // stale write
    max_seen[resource] = token
    WRITE(resource, data)
    RETURN ACCEPTED

The storage layer's fenced_write function is the critical piece. It must be atomic: the comparison, the update of max_seen, and the data write must all happen as a single indivisible operation. In a database, this can be implemented as a single transaction with a conditional update.

// Database implementation of fenced_write (pseudocode)
FUNCTION fenced_write_db(resource, data, token):
    BEGIN TRANSACTION
        SELECT max_token FROM fencing WHERE resource_id = resource FOR UPDATE
        IF token <= max_token:
            ROLLBACK
            RETURN REJECTED
        UPDATE fencing SET max_token = token WHERE resource_id = resource
        UPDATE resources SET value = data WHERE id = resource
    COMMIT
    RETURN ACCEPTED

Real-World Applications

Key Takeaways