Fencing and Leases
A lease is a time-limited right that lets one machine hold a role until a set moment, after which the right ends on its own. A fencing token is a rising number handed out with each lease, used to reject work from holders whose lease has ended.
Define the problem
A leader can freeze for a while and then wake up. While it sleeps, the group may elect a replacement.
The old leader wakes believing it still leads. Two leaders now issue orders, and the orders can conflict.
Stopping the old leader is impossible from outside. The system must instead make its late work harmless.
How a lease works
A lease grants a role for a fixed stretch of time. When the time runs out, the right ends without any message.
The holder renews the lease while it works. Renewal is a short message sent well before the expiry moment.
In this design the lease lasts 10 seconds and the holder renews every 3 seconds. A healthy holder therefore renews with 7 seconds to spare.
Expiry needs no agreement. Leases assume machine clocks stay close, and a lease system states that assumption instead of hiding it.
How a fencing token works
Each new lease carries a fencing token. The token is a number that rises with every grant.
Suppose one lease carries token 41. The next lease carries token 41 + 1, which is token 42.
Every piece of work from a holder carries its token. The store compares the token on the work with the highest token it has seen.
Work with an older token is rejected. Work with the current token goes ahead.
A stale holder, fenced out
Holder A leads under token 41. Holder A freezes, and its lease expires while it sleeps.
The group elects holder B. Holder B receives a new lease with token 42, and the store notes the higher token.
Holder B writes its first change. The store accepts it, because the token is current.
Holder A wakes and sends the write it prepared before freezing. The store sees token 41, below the recorded 42, and rejects the write.
No message ever reached holder A. Fencing worked because the store, not the stale holder, enforced the rule.
Trade-offs
Short leases replace a bad holder quickly. They also expire during brief network trouble and cause extra elections.
Long leases ride out brief trouble. They also leave a frozen holder's role empty for longer.
Fencing adds a check to every write. That small cost buys safety against the rarest and worst failure in this category.
A lease bounds how long a stale holder can act, and a fencing token makes its late work powerless.
A stale holder, fenced out
| Step | Event | Token |
|---|---|---|
| 1 | Lease granted to holder A | 41 |
| 2 | Holder A pauses, lease expires | 41 |
| 3 | New lease granted to holder B | 42 |
| 4 | Holder A wakes, sends old work | 41 |
| 5 | Store rejects the old work | 41 |
Exercise
A store has recorded fencing token 42. What happens to work arriving with token 41?