Concepts
Fencing tokens and leases
Intuition
Imagine you lend someone the key to a room for an agreed time: once the time is up, the key stops being valid and someone else can be given the room. The problem is that whoever kept the old key may not have noticed that the time ran out and may walk in anyway. The solution is for the room to require, on every entry, a numbered badge carrying the current shift number, and to refuse badges from old shifts.
How it works
A lease is a time-limited grant: the owner's hold is valid only while the term has not expired, and the owner must renew it periodically. In Chubby, a cell's master is elected by a majority of the replicas, which promise not to elect another one for a few seconds (the master lease), renewed as long as it keeps winning the vote; this is why the master can answer reads on its own, since no other master can exist while the lease is valid. The relationship between a client and a cell is also a session lease, extended by the replies to KeepAlives (12 s by default); if the local lease expires, the client enters jeopardy and waits out a grace period (45 s by default) before giving the session up as lost. The term alone, however, does not protect against delayed or out-of-order messages, which can make a process that has already lost the lock act improperly. That is why Chubby offers the sequencer: an opaque byte string containing the lock name, the mode, and a generation number, obtained right after acquisition. The client attaches it to its requests, and the resource server checks that it is still valid, rejecting whoever holds an old generation; this is the idea behind the fencing token. For servers that do not check sequencers, Chubby uses the lock-delay, an imperfect mechanism: if the lock is released because the owner failed or became unreachable, nobody can take it for a limited period of at most one minute (the value at the time). In ZooKeeper, the owner's presence is tied to the session through ephemeral znodes, which are removed when the session ends, and the lock uses ephemeral sequential znodes, in which whoever has the lowest number holds the lock.
In practice
Leader election and distributed locks show up like this in real systems: with Chubby, GFS uses a lock to designate its master and Bigtable uses it to elect the master; ZooKeeper has been used for leader election and failure detection in systems such as Hadoop and HBase. When designing a lock with a lease, do not rely on the deadline alone: have the protected resource validate the token or generation on every operation and, if that is not possible, use a delay after release as a partial defense. Also remember that Chubby's lock is advisory, so the protection only holds if the servers actually check the token.
Use it in a design
Practice the cases that rely on this concept in the System Design school.