Part 5 of 6 · 5 min read
Process pauses, leases and fencing
A paused node does not know it was paused, so it may act on a lease that expired.
Process pauses, leases and fencing
Think of a night guard who falls asleep for an hour and wakes up believing it is still the same minute. The relief guard has already taken over, but the first guard keeps locking and unlocking doors as if still on duty.
A lease is a lock with a time limit: the holder owns a resource until it expires, and must renew to keep it [leader election in module 5 uses the same idea]. The book asks how a leader knows it still holds the lease before it accepts a write. A loop that checks the lease and then handles a request has a flaw: it assumes little time passes between the check and the work. A node can be paused at any point for a long time, and does not notice.
Causes of pauses listed in the book:
- Stop-the-world garbage collection, sometimes for minutes.
- A virtual machine suspended and resumed, for example for live migration.
- A laptop lid closed.
- The operating system switching to another thread, or the hypervisor to another VM (steal time).
- Slow synchronous disk reads, including surprise reads such as lazily loaded classes, or a network disk.
- Swapping memory to disk, and in extreme cases thrashing.
- A Unix process stopped by SIGSTOP (Ctrl-Z) and resumed later.
The book compares this to thread safety on one machine: nothing can be assumed about timing. Real-time systems that guarantee response times exist (airbag controllers), but they are expensive and limit tools, so most servers must live with pauses. The book notes mitigations such as treating a garbage collection as a planned short outage by moving requests away first.
The majority decides. A node cannot trust its own view. The book gives stories: a node that can receive but not send looks dead to others, and a node frozen for a minute is declared dead and then wakes up healthy. So decisions use a quorum, a vote among several nodes [a minimum number of agreeing nodes, from Level 4]. Usually it is a majority of more than half. With 3 nodes one failure is tolerated, with 5 nodes two. Only one majority can exist at a time, so two conflicting decisions cannot both win. If a quorum declares a node dead, it is dead, even if it feels alive, and it must step down.
Fencing tokens. The book's bug, which affected HBase: client 1 gets a lease and then pauses. The lease expires. Client 2 gets the lease and writes a file. Client 1 wakes, still believes it holds the lease, and writes too. The file is corrupted.
The fix is a fencing token: every grant of the lock returns a number that rises with each grant. The client sends the token with every write. The storage service remembers the highest token it has seen and refuses lower ones.
Fencing token
A fencing token is a number that increases each time a lock or lease is granted, sent with every write so that the resource can reject writes from an old holder.
Example: client 1 holds token 33 and pauses. Client 2 gets token 34 and writes. When client 1 wakes and writes with 33, the storage service rejects it because it has already seen 34.
The check must be done by the resource itself. Relying on clients to check their own lock is not enough. With ZooKeeper as lock service, the transaction id (zxid) can serve as the token, because it only increases.
Byzantine faults. Everything so far assumes nodes are slow or crashed but not lying. A node that sends false or corrupted messages has a Byzantine fault. The book says most server systems can assume none, since all nodes belong to one organisation. Byzantine tolerance matters in aerospace, where radiation can corrupt memory, and in systems like blockchains where parties do not trust each other. Such protocols typically need more than two-thirds of nodes to behave correctly. Browsers are untrusted too, but the answer there is for the server to validate input, not a Byzantine protocol.
A worked example with tokens. The lock service grants token 33 to client 1 at second 0. Client 1 pauses for 20 s. The lease lasts 10 s, so at second 10 it expires. At second 12 client 2 gets token 34 and writes. At second 20 client 1 wakes and writes with 33. Storage's highest seen token is 34, so the write with 33 is refused. The file stays intact.
Interview angle
Answer in your head first, then open it.
Why are distributed systems harder than single machines?
Partial failure, unbounded network delay and unreliable clocks; a node cannot tell a slow peer from a dead one.
How do you choose a timeout?
Measure latency, balance fast detection against false alarms, prefer adaptive detectors.
Can you order events with timestamps?
Not across machines. Use logical clocks, or tight bounds as in Spanner.
What goes wrong with a lock that expires?
A paused holder keeps acting. Use fencing tokens checked by the resource.
What is a quorum?
A majority vote, which stops two conflicting decisions.
Check yourself:
- Why does a long GC pause make a leader dangerous?
- Who has to check the fencing token, the client or the storage service?
Words you will meet
| Word | Plain meaning |
|---|---|
| Partial failure | Some parts of a system broken while others work |
| Asynchronous network | No promise of delivery time or delivery at all |
| Timeout | A limit on waiting for a reply |
| Network partition | A network fault that cuts one part off from the rest |
| Congestion | Queues in the network growing because of load |
| Time-of-day clock | Calendar time, can jump |
| Monotonic clock | Only moves forward, used for durations |
| NTP | Protocol to set clocks from time servers |
| Clock drift | A clock running a little fast or slow |
| Last write wins | Keep the write with the newest timestamp |
| Logical clock | A counter that records order, not time |
| Confidence interval | The range in which the true time lies |
| Lease | A lock with an expiry time |
| Quorum | A minimum number of agreeing nodes, usually a majority |
| Fencing token | An increasing number that lets a resource reject old holders |
| Byzantine fault | A node that sends false or arbitrary messages |