Leases create a subtle danger. Client A acquires, then pauses (a long GC pause) past its lease. The lock expires, client B acquires, and now both think they hold it. When A wakes and writes, it corrupts shared state.
The fix (Martin Kleppmann's fencing): every successful acquire returns a monotonically increasing token. Downstream storage remembers the highest token it has seen and rejects any write carrying a smaller one, so the stale holder is fenced off.
acquire(name, client_id, ttl): on success return the new fencing token (an int that only ever goes up); on failure return None.import time
class LockManager:
def __init__(self, clock=time.time):
self.clock = clock
self._locks = {} # name -> {"client", "expiry", "token"}
self._counter = 0
def acquire(self, name, client_id, ttl):
"""On success return a new, ever-increasing fencing token; else None."""
now = self.clock()
cur = self._locks.get(name)
if cur is None or cur["expiry"] <= now:
# TODO: issue the next token by advancing the single self._counter
# field, then save an entry for name under keys "client",
# "expiry" and "token" holding client_id, an expiry ttl seconds
# past now, and that token. Answer with the token just issued.
pass
return None
def release(self, name, client_id):
cur = self._locks.get(name)
if cur and cur["client"] == client_id:
del self._locks[name]
return True
return False
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
Leases create a subtle danger. Client A acquires, then pauses (a long GC pause) past its lease. The lock expires, client B acquires, and now both think they hold it. When A wakes and writes, it corrupts shared state.
The fix (Martin Kleppmann's fencing): every successful acquire returns a monotonically increasing token. Downstream storage remembers the highest token it has seen and rejects any write carrying a smaller one, so the stale holder is fenced off.
acquire(name, client_id, ttl): on success return the new fencing token (an int that only ever goes up); on failure return None.Press Run Tests or ⌘↩ to check your solution.