Fencing tokens and why locks are hard

A distributed lock lets only one worker touch a resource at a time. In distributed systems, a lock is a lease: it expires after a time-to-live, so that a crashed holder doesn't block everyone forever. The trouble starts when the holder is paused and doesn't know its lease has expired.

Walking through the failure

Client 1 did everything right. It acquired the lock and checked it before writing. The pause landed between the check and the write. No check on the client side can fix this, because a pause can happen between any two instructions.

The fix: a fencing token

The lock service returns a number with each grant. The client sends that number with every write. The storage system keeps the highest number it has seen and rejects anything lower.

// A sketch. The storage, not the client, enforces the lock.
async function writeWithFence(key: string, data: Buffer, token: number) {
  // Atomic check-and-set on the highest token seen for this key.
  const ok = await db.query(
    `UPDATE files SET data = $1, fence = $2
     WHERE key = $3 AND fence < $2`,
    [data, token, key],
  );
  if (ok.rowCount === 0) throw new Error(`stale fencing token ${token}`);
}

In the scenario above, Client 1 received token 33 and Client 2 received token 34. Client 2 writes with 34, and storage records 34. Client 1 wakes up and writes with 33. Storage rejects it. Correctness no longer depends on timing.

ZooKeeper's zxid or a znode's version can serve as the token. etcd's lease revision does the same job. Both come from a consensus log, so they are totally ordered.

The Redlock debate

In 2016, Martin Kleppmann published a critique of Redlock, an algorithm that takes a lock across five independent Redis nodes. He made two points:

1. Redlock produces no fencing tokens, so it cannot stop the pause scenario above.
2. Its safety depends on timing: bounded delays, bounded pauses, and clocks that don't jump.

Salvatore Sanfilippo (antirez), Redis's creator, replied that the clock assumptions are reasonable in practice. The working consensus that emerged:

• For efficiency, such as avoiding two workers doing the same costly but harmless job, one Redis instance with a TTL is fine.
• For correctness, use a consensus-backed system such as etcd or ZooKeeper, with fencing tokens enforced at the resource. Better still, use the database's own concurrency control, such as conditional writes, SELECT ... FOR UPDATE or version columns.

Common mistakes

• Checking the lock, then writing. A pause between the two breaks the lock. Enforce the check at the resource.
• Using a lock for correctness with no fence. The lock alone can't prevent a stale write.
• Trusting the client to enforce a token. The resource must do the rejecting.

Check yourself

1. Why can't client-side checks fix the pause problem? A pause can happen between any two instructions, including between the check and the write.

2. Who enforces a fencing token? The resource being written to. It rejects any write whose token is lower than one it has already seen.

Key takeaways

• A lock is a lease, and a lease can expire under a paused holder.
• A fencing token makes the resource reject stale holders, so safety stops depending on timing.
• Use fencing with a consensus-backed lock, or use conditional writes in the database.
• A single Redis lock is fine when a rare double run only wastes work.

Further learning

Kleppmann's post is the clearest statement of the locking problem, and antirez's reply is the best account of the other side.

Next, see what keeps an outage going after its trigger ends in metastable failures and retry storms.