Fencing and Epochs

The shape

One process needs exclusive access to something: a lock on a row, a lease on a file, leadership of a cluster. It takes the lock, does its work, and hands it back. Whatever holds the lock right now is the holder. That is the happy path, and it is the only path most designs draw.

The problem is that a lock can expire without the holder finding out. Four ways that happens:

• The process freezes for a garbage collection pause.
• The virtual machine it runs on is paused so it can be moved to another host.
• The container hits its CPU quota and gets throttled to a crawl.
• The network stops delivering its packets, while the process keeps running and notices nothing.

In every one of these the holder is either not running or not reachable, and the clock keeps going anyway. The lease expires. Something else is given the lock. Then the first process comes back, still completely sure it holds the lock, and writes.

A process can keep believing it holds a lock long after it has lost it. You cannot prevent this. To prevent it, the process would have to notice something while it is not running. A process cannot do that. Making the lease longer does not help either. A longer lease just needs a longer pause to break it, and a pause has no upper limit.

So this pattern gives up on stopping the second holder from existing. It makes the stale one harmless instead.

The mechanism

Three parts, and the third is the one that gets left out.

1. Every lock comes with a number. The number goes up by one each time the lock is handed out. The first holder gets 1, the next gets 2, and it never goes back down.
2. Every write the holder sends carries that number. It travels inside the request. It is not a variable the process checks for itself before writing.
3. The thing being written to remembers the highest number it has seen, and refuses anything lower.

That third step is the whole pattern. The old holder wakes up and sends a write stamped 4. The database has already accepted a write stamped 5, so it refuses this one. Being told no is how the old holder finds out it is not the holder any more. There is no other way it could find out, because everything else it believes about the world is from before the pause.

The same idea, under four names

This is not a clever trick somebody invented for your system. Every mature system already does it, so you can name them rather than deriving the whole argument from scratch.

Kafka's history shows how hard this is to get right. It used to decide how far a follower should cut its log back by looking at the high watermark. In some failover sequences the leader and the follower ended up holding different data. Kafka publishes its design changes as numbered public proposals, and the one that fixed this, KIP-101, replaced the high watermark with the leader epoch. Leadership changing twice in quick succession then turned up more ways for the two logs to end up different, and a follow-up proposal, KIP-279, had to fix those. A team whose entire product is an ordered log needed two goes at this. Do not expect to get it right by guessing.

When the other side cannot check

Sometimes you do not own the thing you are protecting. It might be a payment API somebody else runs, or an SFTP server, or a printer, or a vendor's database. None of them are going to start checking a number you made up.

Chubby has a fallback for this, and it calls it a lock delay. If a lease is lost without the holder handing it back properly, nobody else gets that lock for a while, usually around a minute. The cost is a minute of downtime every time a lease is lost this way, and downtime is the only thing you have left to give up. The delay puts the two writers in order by time. The number puts them in order by comparison: the database sees the old number, and that write loses. Nothing on the other side can compare anything here, so the old write cannot be made to lose. Instead you wait until it has already happened.

After a minute, the old holder has woken up, found its lease expired and stopped. Or it has died. Either way its writes have already landed by the time the new holder sends its first one. You still get one writer at a time. You get it by waiting instead of by checking.

This is the weaker answer, because it rests on a guess: that a minute is longer than any pause you will ever hit. If a machine migration takes 90 seconds, the old holder wakes up after the new one has already started work. Both are writing. Nothing in the path can tell, so nothing reports an error. The number does not rest on a guess.

So do this on paper before you build anything. List every place the holder writes to. Next to each one, mark whether it can check a number. That list is the design. Everything that can check gets the number. Everything that cannot gets one of three things instead: a lock delay, or a design where doing the same thing twice is harmless, or a service of your own in front of it that does the checking.

The lease is 10 s. The holder promises to stop before it expires.

  a JVM full GC pause              1.5 s     survivable
  a container throttled by cgroup  8 s       marginal
  a VM paused for live migration   30 s      lease long gone
  a network path blackholed        minutes   lease long gone

Raise the lease to 60 s to cover the VM pause
  → failover now takes at least 60 s, always,
    for every real failure, forever

Raise it to 300 s to be safe
  → a genuinely dead leader costs 5 minutes of downtime

No lease length is both short enough to fail over quickly
and long enough to outlast a pause that has no upper limit.
The number removes the choice. Keep the lease short, accept
that two holders will sometimes exist, and let the database
throw the stale one's writes away.

What it costs

The mechanism itself is cheap. One integer on every request, one comparison at the other end. The costs are elsewhere.

Every place the holder writes has to take part. One that does not check is enough to lose the guarantee, so the pattern is only as good as the weakest thing in the path.

The number has to survive a restart. Whatever hands the locks out must not start counting from 1 again. If it does, it hands out a number it has used before, and every comparison after that is meaningless.

A refused write needs somewhere to go. A holder that gets told no should stop what it is doing and give up the lock, not retry. That handling on the client side matters as much as the check on the server side.

Where it shows up in the course

Getting it wrong

Checking inside the holder instead of at the database. "The process checks its lease is still valid before it writes" sounds like the same thing. It is not. A frozen process runs no checks while it is frozen. When it wakes up, it runs the check and the check passes, because the lease looked fine the last time it looked.

Letting the number restart from zero. If whatever hands out the locks can restart and reissue a number, the comparison at the other end is worthless.

Retrying after a rejection. Being told no means you are not the holder any more. Sending the same write again with the same number cannot work. Taking a fresh lock and sending it again without re-reading the current state is worse, because you will overwrite whatever the real holder did while you were gone.

Thinking a longer TTL fixes it. A longer TTL makes the failure rarer. It does not remove it. And a rare failure that corrupts data quietly is harder to find than a common one.

Numbering some writes and not others. The path you forgot is the one that corrupts the data. Write the list down. Do not assume you already know what is on it.