Fencing tokens

Deep dive

How it works

In: lock requests, and writes tagged with a token · Out: a token per grant; accept or reject per write · State: service: last token and current holder with expiry; resource: max_token (one u64) · Cost: O(1) per grant and per write

1. The lock service keeps a counter. Each grant to a new owner increments it and returns the value as the token (leases are the usual time limit).
2. A renewal by the live holder returns the same token; the owner has not changed.
3. The client sends its token with every write.
4. The resource compares: token < max_token rejects; otherwise it stores max_token = token and applies the write.
5. A paused holder wakes up with an old token; its write fails and it learns that it lost the lock.

A: grant(tok 1) ── pause ......................... write(1) ──► rejected (max = 2)
B:                   grant(tok 2) ── write(2) ──► ok, max = 2

Equal tokens are accepted so the same holder can write many times. Rejecting <= would break every second write.

Where tokens come from:

• ZooKeeper: every change gets a zxid, a total order across all changes (programmer's guide). Kleppmann suggests the zxid or the znode version number as fencing token.
• etcd: a 64-bit store revision increments on each key-space change; keys carry create_revision and mod_revision (API). The creation revision of the lock key is a usable token, since a later owner creates its key later.
• Raft / Paxos: the term (or ballot) of the leader is a token. Replicas reject messages from lower terms (Raft, Multi-Paxos).
• Kafka: the transaction coordinator bumps the producer epoch at InitPid so that a zombie producer is fenced (KIP-98). Followers use a leader epoch to cut logs (KIP-101).

Redlock is the cautionary case: Kleppmann's 2016 post argues it has no source of monotonic tokens, and so cannot be made safe against pauses (post).

Code

/// Lock service on a virtual clock (ticks). One lock; every new owner gets a higher token.
pub struct LockService {
    holder: Option<(u32, u64)>, // (client, expiry tick)
    token: u64,
}

impl LockService {
    pub fn new() -> Self { LockService { holder: None, token: 0 } }

    /// Grant the lock for `ttl` ticks. A renewal by the live holder keeps its token;
    /// any other grant (free or expired) bumps it.
    pub fn grant(&mut self, client: u32, ttl: u64, now: u64) -> Option<u64> {
        match self.holder {
            Some((h, exp)) if now < exp && h != client => return None,
            Some((h, exp)) if now < exp && h == client => {} // renewal: same token
            _ => self.token += 1,
        }
        self.holder = Some((client, now + ttl));
        Some(self.token)
    }
}

/// The protected resource. `fenced = false` models a store that ignores tokens.
pub struct Storage {
    fenced: bool,
    max_token: u64,
    pub value: String,
}

impl Storage {
    pub fn new(fenced: bool) -> Self { Storage { fenced, max_token: 0, value: String::new() } }

    /// Equal token = same holder writing again: allowed. Lower = stale: rejected.
    pub fn write(&mut self, token: u64, v: &str) -> Result<(), u64> {
        if self.fenced {
            if token < self.max_token { return Err(self.max_token); }
            self.max_token = token;
        }
        self.value = v.to_string();
        Ok(())
    }
}

/// A pauses past expiry, B takes over and writes, A wakes and writes with its old token.
fn scenario(fenced: bool) -> (Result<(), u64>, String) {
    let (mut lock, mut store) = (LockService::new(), Storage::new(fenced));
    let ta = lock.grant(1, 10, 0).unwrap();          // t=0: A gets token 1
    assert!(lock.grant(2, 10, 5).is_none());         // t=5: B refused, lease live
    let tb = lock.grant(2, 10, 12).unwrap();         // t=12: A's lease expired, B gets token 2
    assert!(tb > ta);
    store.write(tb, "B").unwrap();
    let late = store.write(ta, "A");                 // t=30: A wakes, still believes it holds the lock
    (late, store.value)
}

fn main() {
    let (late, v) = scenario(true);
    assert_eq!(late, Err(2));
    assert_eq!(v, "B");

    let (late, v) = scenario(false); // negative test: no check at the resource
    assert!(late.is_ok());
    assert_eq!(v, "A"); // B's data silently overwritten
    println!("fenced keeps B, unfenced corrupts to A");

    // Strictly increasing across 1000 grants (alternating owners, each after expiry).
    let mut lock = LockService::new();
    let mut prev = 0;
    for i in 0..1000u64 {
        let t = lock.grant((i % 2) as u32, 10, i * 20).unwrap();
        assert!(t > prev);
        prev = t;
    }
    assert_eq!(prev, 1000);

    // Renewal keeps the token, and the store accepts equal tokens.
    let (mut lock, mut store) = (LockService::new(), Storage::new(true));
    let t1 = lock.grant(1, 10, 0).unwrap();
    let t2 = lock.grant(1, 10, 5).unwrap();
    assert_eq!(t1, t2);
    store.write(t1, "x").unwrap();
    store.write(t2, "y").unwrap();
    assert_eq!(store.value, "y");
    println!("all asserts passed");
}

Complexity and constants

• Grant: O(1); the cost is the replicated write that makes the counter durable (a consensus round if the lock service is replicated).
• Write check: one integer compare and, on a higher token, one store of max_token. It must be persisted atomically with the write, or a restart forgets the maximum.
• State: 8 bytes per fenced resource (per key, per partition or per file, as you choose).

Efficiency

• Cost: the check is a compare of two u64 values per write: nothing next to the I/O it protects. The real cost is making max_token durable with the data (same page, same log record), so no extra fsync is needed. Bound: the write path itself.
• Levers:
  • keep max_token in the same record as the data — no second write or fsync (reasoning above) — any store you control
  • fence per partition or key range rather than per cluster — unrelated writers never contend on one counter — sharded storage
  • let the consensus log's term or index serve as the token — no extra counter or round — Raft or Paxos based locks
• Naive → standard → state of the art:
  • lock with no token, client checks "still valid?" before writing · racy: a pause between check and write defeats it
  • monotonic token checked at the resource · one compare per write
  • token carried in a conditional write (conditional writes) or an epoch fenced by the log · no separate fence state

Implementation notes

• Persist max_token atomically with the data; test restart recovery.
• Return the current maximum with the rejection so the client knows it lost the lock and can stop.
• If the resource cannot store a token but can accept a conditional write, use compare-and-set on a version: it fences the same way.
• Test the pause with a virtual clock and a seeded schedule, as in deterministic simulation testing; real sleeps hide the interleavings.
• Tokens from Lamport clocks work only if every grant passes through one total order; wall clocks do not.

Pitfalls

• Checking the lease before the write instead of fencing: the pause happens after the check.
• Tokens from a source that can go backwards after failover (a lock service restored from an old snapshot).
• Letting only some writers (or the new primary but not a background job) check the token: one unfenced path reopens the hole.
• Equal-token rule too strict: rejecting <= blocks the legitimate holder's second write.
• Two resources updated under one lock: each needs its own check, and a partial result needs two-phase commit or a compensation.

Variants and alternatives

In production

• Chubby: sequencers, a lock generation number the resource can verify (Burrows 2006).
• ZooKeeper and etcd: zxid and revisions as tokens; etcd's lock recipe is built on key revision.
• Kafka: producer epoch for transactional zombie fencing; leader epoch for log truncation.
• Pacemaker: STONITH to fence nodes sharing a disk.

Implementations

Sources

• Martin Kleppmann, How to do distributed locking, 2016. post
• Mike Burrows, The Chubby Lock Service for Loosely-Coupled Distributed Systems, OSDI 2006. paper
• Apache Kafka, KIP-98: Exactly Once Delivery and Transactional Messaging. KIP
• Apache Kafka, KIP-101: Alter Replication Protocol to use Leader Epoch rather than High Watermark for Truncation. KIP
• ClusterLabs, Pacemaker Explained, ch. 8 Fencing. docs
• Apache ZooKeeper, Programmer's Guide. docs · etcd, API. docs