Distributed Locking & Fencing Tokens
Distributed locks with TTLs (like basic Redis locks) cannot prevent data corruption during Stop-The-World GC pauses. Pairing the lease with a monotonically increasing Fencing Token forces the storage layer to reject zombie writes from expired lock holders 🛡️🔐.
class FencedDatabase:
def __init__(self):
self.highest_token = 0
self.state = {}
def write(self, fencing_token, key, val):
# Reject stale zombie client writes:
if fencing_token < self.highest_token:
raise PermissionError(f"Stale token {fencing_token} < {self.highest_token} 🛑")
self.highest_token = fencing_token
self.state[key] = val
db = FencedDatabase()
# Client 2 acquires lock with higher token:
db.write(fencing_token=34, key="user_1", val="ACTIVE")
# Client 1 wakes up from GC pause with old token:
try:
db.write(fencing_token=33, key="user_1", val="DELETED")
except PermissionError as err:
print(f"Protected: {err} 🛡️")
# 42. Distributed Locking & Fencing Tokens The most dangerous bug in distributed systems is the "zombie client". Client 1 acquires a lock for 10 seconds, hits an unexpected 15-second Java GC pause or Linux swap thrashing, its lock expires, Client 2 acquires it, and then Client 1 wakes up and commits corrupted data 🛑. ```python # The Fencing Token Invariant: # Every lock acquisition returns a monotonic counter: # Lock Server: Token 33 -> Client 1 # (Client 1 sleeps for 20s, lock expires) # Lock Server: Token 34 -> Client 2 (writes to DB with token 34) # Client 1 wakes up -> tries DB write with token 33 -> DB REJECTS! ``` ### Protection Architecture 1. **Monotonic Tokens**: The lock service (e.g. ZooKeeper `zxid`, etcd `revision`) increments a 64-bit integer upon every successful lease grant 🔐. 2. **Server-Side Enforcement**: The storage engine tracks the highest token it has ever observed. Any write carrying an older token is immediately rejected with an error. 3. **No Wall Clock Assumptions**: Safety relies entirely on integer ordering ($34 > 33$) rather than physical server clocks. --- ### Interactive Pop-Quiz 🧠 #### Why is a TTL-based distributed lock alone insufficient to guarantee mutual exclusion in distributed systems? - [ ] A client may experience a Stop-The-World GC pause or network stall, letting the lock expire while it still believes it holds it 🛑 - [ ] Linux file systems automatically convert TTL values to nanoseconds - [ ] Because Redis stores lock keys exclusively in volatile CPU registers - [ ] Because NTP synchronization forces locks to unlock every 60 seconds --- ### Practical Challenge 🎯 Implement `FencedStore` with `write(token, key, val)` and `read(key)`. If `token < self.max_token`, raise `ValueError('Stale token')`. Otherwise update `self.max_token = token` and save the key-value pair. Write key `'status'` with token 100 as `'INITIAL'`, then with token 105 as `'UPDATED'`. Attempt a write with token 99, catch the `ValueError`, and print the final value of `'status'`. <details> <summary>Solution</summary> ```python class FencedStore: def __init__(self): self.max_token = 0 self.data = {} def write(self, token, key, val): if token < self.max_token: raise ValueError("Stale token") self.max_token = token self.data[key] = val def read(self, key): return self.data.get(key) store = FencedStore() store.write(100, "status", "INITIAL") store.write(105, "status", "UPDATED") try: store.write(99, "status", "ZOMBIE") except ValueError: pass print(store.read("status")) ``` </details>