Distributed Locks, Leases and Fencing Tokens

A lock you hold may already be gone

A distributed lock built on etcd or ZooKeeper is really a lease: it expires if the holder stops renewing it, otherwise a crashed client would hold it forever. The danger is that the holder cannot know precisely when its lease expired. A client can acquire the lock, then pause (a long garbage-collection pause, a VM freeze, a slow disk), during which its lease expires and another client takes the lock. When the first client wakes up, it still believes it holds the lock and writes to the shared resource: now two clients act as owners. Checking 'do I still hold the lock?' just before writing does not fix this, because the pause can happen between the check and the write. The robust fix is a fencing token: the lock service hands out a number that increases with every acquisition (an etcd revision or ZooKeeper zxid works), the client sends it with each write, and the storage rejects any token lower than the highest it has seen.

Storage that enforces fencing tokens

Client 1 pauses after acquiring token 33. Client 2 gets token 34 and writes. Client 1's late write is rejected by the storage itself.

class Storage:
    def __init__(self):
        self.highest_token = 0
        self.data = None

    def write(self, token, value):
        if token < self.highest_token:
            return f"rejected {value!r} (token {token} < {self.highest_token})"
        self.highest_token = token
        self.data = value
        return f"stored {value!r} with token {token}"

s = Storage()
print(s.write(33, "from client 1"))   # client 1 holds the lock, then pauses (GC)
print(s.write(34, "from client 2"))   # lease expired; client 2 got the lock
print(s.write(33, "late write from client 1"))

Output:

stored 'from client 1' with token 33
stored 'from client 2' with token 34
rejected 'late write from client 1' (token 33 < 34)

Consensus does not protect what it does not own

The lock service can be perfectly linearizable and you can still corrupt data if the resource being protected does not check tokens. Fencing has to be enforced at the resource, for example with a conditional write or a version column.

Quick check: Where must a fencing token be checked to prevent writes from a paused former lock holder?

• In the client, before every write
• In the lock service, when the lease expires
• In the network load balancer
• In the storage or resource that receives the write