CSE Roadmap

Common tier · about 4 hours · 7 parts

Part 4 of 7 · 3 min read

Locks

Why a lease alone is not safe.

A lock as an entry. To take a lock named /locks/orders, a client creates an ephemeral entry with that name. If the create succeeds, the client holds the lock. If it fails, the entry exists, so someone else holds it. The client watches the entry and tries again when it vanishes. When the holder finishes (or its session ends), the entry goes, and the lock is free.

A lock as a lease. To stop a dead client from holding a lock forever, a lock has an expiry. A holder must keep renewing it (through the session). This time-limited right is a lease (Level 5).

The danger: the paused client. A client takes the lock, then freezes for a long time (a long garbage collection pause, a stalled virtual machine, a network delay). Its lease expires, and another client takes the lock and starts writing to the shared resource. The first client wakes up and still believes it holds the lock. It writes too. Both write, and the resource is corrupted. This is a real bug that has hit real systems.

No clock check by the client can fix it: the pause may come right after the check.

The fix: fencing tokens. Each time the service grants a lock, it also returns a number that rises every time: the fencing token. The client sends the token with every request to the protected resource. The resource remembers the highest token it has seen and rejects anything lower.

Step Event
1 Client 1 gets the lock with token 33, then pauses
2 The lease expires. Client 2 gets the lock with token 34 and writes, with token 34
3 Client 1 wakes up and writes with token 33
4 The resource has seen 34, so it rejects 33

The resource must take an active part in the check. It is not enough for the client to check its own status. A service should not trust that its clients behave well. If a storage service cannot check tokens, a workaround is to put the token in the name of the object. Some check must exist.

Consensus services provide the number for free. In ZooKeeper, the transaction id or the version of an entry always rises, so either can serve as a fencing token.

A worked example (made up). Lock tokens so far: 101, 102, 103. A client with token 103 writes version 5 of a file. A paused client with token 102 wakes up and sends version 6. The storage rejects it, since 102 is below 103. The file stays correct.

Common mistake

Believing that a lease keeps two holders apart. A lease only makes the old holder lose the lock after a while. It does not stop a slow holder from acting. Only a check at the resource, with a fencing token, does that.

Check yourself: 1. Why does the lock entry vanish if the client crashes? 2. Why can a client not protect itself with a clock check? 3. What does the resource do with a fencing token?