C11 hands-on — Distributed locking and fencing

Why a correct lock is not enough, measured — and the one integer that fixes it.

Source: handson/c11_lock_service.py --- run it with python3 handson/c11_lock_service.py
Full project spec: d11 — Distributed Lock Service

This is the highest-value single concept in the distributed half of the program, and it is one people think they know. The lock is not the hard part. Mutual exclusion among live processes is easy and every implementation here gets it right. The hard part is that a process can be granted the lock, be descheduled for longer than the lease, and wake up believing it still holds it --- and no amount of correctness in the lock service prevents the write it then issues.

This page builds a lock with no expiry (which deadlocks), adds a lease (which introduces split brain), adds a fencing token (which fixes it), and then shows the two places people put the fence where it does not work. The lease-sizing block prices both ends of the tradeoff. Every number came from running the code.

Run it

cd swe-interview-prep/handson

python3 c11_lock_service.py            # every block, then the assembly
python3 c11_lock_service.py --block 3  # block 3 and its prerequisites only
python3 c11_lock_service.py --quiet    # the assembly only
python3 c11_lock_service.py --verify   # re-derive and assert every claim below

What to expect. A full run takes under a second and prints 6 blocks followed by the assembly. There are no dependencies beyond the Python standard library and nothing touches the network or the filesystem.

Every seed is fixed, so the numbers you get are the numbers on this page --- character for character. If yours differ, the code changed, not the machine. --verify re-derives 11 claims from scratch and exits non-zero if any of them stops holding, which is what makes the prose here checkable rather than assertable.

Predict before you read

Worth two minutes with a pen, because the gap between your answer and the measurement is the entire value of the page. Write down a number for each:

1. A lock with no expiry, 10 clients, client 3 dies holding it. How many of the 10 complete?
2. Lease TTL 10 s. Client A acquires, is descheduled for 10.1 s, and writes on waking. What is the final value --- A's or B's?
3. Add a fencing token that the resource checks. What is the final value now?
4. A checks its own token immediately before writing, instead. Does that fix it? Under what condition does it not?
5. That client-side check leaks some fraction of the failures. How does the leak change between a 1 ms and a 1 second gap between check and write?
6. Work averages 0.5 s; 2% of holders stall for ~8 s. At a 1-second lease, what fraction of holders outlive their lease?

Then run it, or read on --- the answers are in the blocks, and the ones most people get wrong are called out where they land.

Contents

• Run it
• Predict before you read
• Block 1 — A lock with no expiry
• Block 2 — A lease
• Block 3 — Fencing tokens
• Block 4 — Where the check must happen
• Block 5 — Sizing the lease
• Block 6 — One lock server is not a lock service
• The assembly
• Verify the claims
• The design space
• What is actually being defended against
• Cost model
• Advanced
• How this connects to the rest of the program
• Failure modes at scale
• Primary sources
• What to do with this

How to read this page

Each block below is a self-contained lego piece: it builds one mechanism, proves it works on its own, and returns what the next block needs. The code is the real source, sliced out of the script. The output underneath it is the real output, captured by running that script --- not transcribed, not idealised. Where a measurement contradicted what I expected, the contradiction is in the output and the prose says so.

The assembly at the end wires every block into one working thing and measures it.

Block 1 — A lock with no expiry

Teaches: the deadlock you create by making the lock correct

The problem. Start with the lock that is unambiguously correct: one owner at a time, no expiry, no cleverness. It provides perfect mutual exclusion and it destroys the system, because the only way to release it is for the holder to choose to — and a holder that has died cannot choose anything.

@block(1, "A lock with no expiry", "the deadlock you create by making the lock correct")
def b1(s, show):
    class Lock:
        def __init__(self): self.owner = None
        def acquire(self, client):
            if self.owner is None:
                self.owner = client; return True
            return False
        def release(self, client):
            if self.owner == client: self.owner = None

    def run(n_clients, crash_at):
        lock, done = Lock(), 0
        for c in range(n_clients):
            if not lock.acquire(f"c{c}"):
                break                      # wedged: nobody will ever release
            if c == crash_at:
                break                      # client dies holding the lock
            lock.release(f"c{c}"); done += 1
        return done

    if show:
        print("  10 clients take the lock in turn; client 3 crashes while holding it.")
        print(f"  {'crash at':>10}{'completed':>12}{'outcome':>26}")
        for crash in (None, 3):
            done = run(10, -1 if crash is None else crash)
            out = "all fine" if done == 10 else f"WEDGED after {done}"
            print(f"  {str(crash):>10}{done:>12}{out:>26}")
        print("  Mutual exclusion is trivially correct here and the system stops")
        print("  forever. The lock has no way to distinguish 'still working' from")
        print("  'dead', because those look identical from the outside. That is not")
        print("  an implementation gap -- it is the impossibility the lease works")
        print("  around, and naming it is the first move in this question.")
    return {}

Reading the implementation

• if self.owner is None — the entire mutual-exclusion mechanism, and it is correct. Every failure on this page happens around this line, never in it, which is the reason the question is hard: the bug is never in the part you are asked to implement.
• release checks self.owner == client before clearing. Without that check any client can release any other client's lock, which turns a safety property into a suggestion. It is one comparison and it is the difference between a lock and a shared boolean.
• There is no timeout, no heartbeat and no liveness check anywhere, because there is no correct one available. A holder that is slow and a holder that is dead are indistinguishable from outside the process — that is the failure detector problem, and it is impossible in an asynchronous network, not merely unimplemented.

What the numbers say

Output:

  10 clients take the lock in turn; client 3 crashes while holding it.
    crash at   completed                   outcome
        None          10                  all fine
           3           3            WEDGED after 3
  Mutual exclusion is trivially correct here and the system stops
  forever. The lock has no way to distinguish 'still working' from
  'dead', because those look identical from the outside. That is not
  an implementation gap -- it is the impossibility the lease works
  around, and naming it is the first move in this question.

Ten of ten complete when nobody dies; three of ten when client 3 dies holding the lock, and the remaining seven never run — not "eventually", never. The availability of the whole system is now bounded by the reliability of its least reliable client, which is exactly backwards: the point of a lock service is to be more reliable than the things using it.

Try it yourself

from c11_lock_service import parts
p = parts()
print("  this page exports:", ", ".join(sorted(p)))
print()

# A lock with no expiry. Watch the queue behind a dead holder never drain.
class Lock:
    def __init__(self): self.owner = None
    def acquire(self, who):
        if self.owner is None: self.owner = who; return True
        return False
    def release(self, who):
        if self.owner == who: self.owner = None

lock, waiting = Lock(), []
for c in range(6):
    if lock.acquire(f"c{c}"):
        if c == 2:
            print(f"  c{c} acquired ... and dies holding it")
            break
        lock.release(f"c{c}")
        print(f"  c{c} acquired, worked, released")
for c in range(3, 6):
    waiting.append(f"c{c}") if not lock.acquire(f"c{c}") else None
print(f"  blocked forever behind a dead holder: {waiting}")
print(f"  lock.owner is still {lock.owner!r} -- and nothing will ever change that")

  this page exports: FencedLock, LeaseLock

  c0 acquired, worked, released
  c1 acquired, worked, released
  c2 acquired ... and dies holding it
  blocked forever behind a dead holder: ['c3', 'c4', 'c5']
  lock.owner is still 'c2' -- and nothing will ever change that

The last line is the whole block. There is no timeout, no supervisor, no mechanism anywhere that can distinguish this state from a holder that is simply taking a long time — because from outside the process those are the same observation.

Beyond the toy

The instinct is "add a timeout", and that instinct is correct and is the next block. What is worth saying first is why the timeout is a compromise rather than a fix: it does not detect death, it guesses at it, and the guess can be wrong in both directions. Guess too eagerly and you revoke from a live holder; guess too slowly and you keep the outage.

Two designs that avoid the guess, both by moving it somewhere else:

• Session-based ownership (ZooKeeper ephemeral nodes, etcd leases). The server decides the client is gone, based on a heartbeat it controls, and deletes the node. The guess still exists — it is now a heartbeat interval — but it is made by one component with a consistent view rather than by each client independently.
• Not locking at all. A queue with visibility timeouts (SQS), or single-writer-per-partition (Kafka), or optimistic concurrency with a version check. Each replaces "who may act" with "whose action is accepted", which is the same move block 3 makes and is usually the better answer when it is available.

Block 2 — A lease

Teaches: fixes the deadlock and buys you a worse bug

The problem. The lease is the standard repair: ownership expires, so a dead holder blocks progress for at most one TTL instead of forever. It genuinely fixes block 1. It also introduces a failure that is worse, because block 1's failure was loud and total and this one is silent and partial.

@block(2, "A lease", "fixes the deadlock and buys you a worse bug")
def b2(s, show):
    class LeaseLock:
        """Ownership expires. now() is passed in so the test controls time."""
        def __init__(self, ttl): self.ttl, self.owner, self.expires = ttl, None, 0.0
        def acquire(self, client, now):
            if self.owner is None or now >= self.expires:
                self.owner, self.expires = client, now + self.ttl
                return True
            return False
        def holds(self, client, now):
            return self.owner == client and now < self.expires

    def scenario(ttl, pause):
        """A holds the lease, pauses for `pause`, then writes anyway."""
        lock, res = LeaseLock(ttl), Resource()
        t = 0.0
        lock.acquire("A", t)               # A takes the lease at t=0
        t += pause                         # A is descheduled (GC, VM steal, swap)
        b_got = lock.acquire("B", t)       # B sees it expired and takes it
        if b_got:
            res.write("B", 100)            # B does its work
        res.write("A", 200)                # A wakes and writes -- it never checked
        holders = ("A" if lock.holds("A", t) else "") + ("B" if b_got else "")
        return res, b_got, holders

    if show:
        print("  lease TTL = 10s. A acquires, is descheduled, then writes on wake.")
        print(f"  {'A pause':>9}{'B acquired':>12}{'final value':>13}{'writers':>9}"
              f"  {'verdict':<22}")
        for pause in (2.0, 9.9, 10.1, 30.0):
            res, b_got, _ = scenario(10.0, pause)
            wr = "".join(w[0] for w, _ in res.writes)
            ok = "safe" if not b_got else "SPLIT BRAIN"
            print(f"  {pause:>8.1f}s{str(b_got):>12}{res.value:>13}{wr:>9}  {ok:<22}")
        print("  At a 10.1s pause the lease has expired, B legitimately owns it, and")
        print("  A -- which has no idea any time passed -- overwrites B's work. Both")
        print("  clients behaved correctly. The LOCK behaved correctly. The data is")
        print("  wrong, and the final value is A's, which is the older one.")
    return {"LeaseLock": LeaseLock}

Reading the implementation

• now is a parameter, not a call to time.monotonic(). That is what makes this block a measurement rather than a flaky test: the scenario controls the clock exactly, so a 10.1-second pause is reproducible and instantaneous. The same discipline is the answer to "how would you test this" (Q64, Q134) and it is worth doing in the interview even on a whiteboard.
• if self.owner is None or now >= self.expires — expiry is evaluated by the lock, on the acquirer's clock. There are now two clocks in the system: the lock's and the holder's, and nothing keeps them in agreement.
• res.write("A", 200) is issued without any check, which is exactly what a real client does. A has no reason to suspect anything happened: from inside the process, the pause is invisible. There is no exception, no signal, no callback — the next instruction simply executes much later.

What the numbers say

Output:

  lease TTL = 10s. A acquires, is descheduled, then writes on wake.
    A pause  B acquired  final value  writers  verdict               
       2.0s       False          200        A  safe                  
       9.9s       False          200        A  safe                  
      10.1s        True          200       BA  SPLIT BRAIN           
      30.0s        True          200       BA  SPLIT BRAIN           
  At a 10.1s pause the lease has expired, B legitimately owns it, and
  A -- which has no idea any time passed -- overwrites B's work. Both
  clients behaved correctly. The LOCK behaved correctly. The data is
  wrong, and the final value is A's, which is the older one.

At a 9.9-second pause everything is fine; at 10.1 the system silently corrupts. Read the last two columns together: writers is BA, so both clients wrote, and final value is 200, which is A's — the older one. B did its work correctly, committed, and had it overwritten by a client whose authority had already expired.

The property that makes this dangerous: nothing anywhere logged an error. The lock behaved to specification. Both clients behaved to specification. The only component that could have noticed is the resource, and nobody asked it to.

Try it yourself

Sweep the pause across the lease boundary and watch the correctness flip:

from c11_lock_service import parts
LeaseLock = parts()["LeaseLock"]

TTL = 10.0
print(f"  {'A pauses for':>14}{'B acquires?':>13}{'final value':>13}  verdict")
from c11_lock_service import Resource
for pause in (5.0, 9.0, 9.99, 10.0, 10.01, 15.0):
    lock, res = LeaseLock(TTL), Resource()
    lock.acquire("A", 0.0)                 # A takes the lease
    b = lock.acquire("B", pause)           # B tries after the pause
    if b:
        res.write("B", 100)                # B does its work and commits
    res.write("A", 200)                    # A wakes and writes -- it never checked
    verdict = "SPLIT BRAIN -- A clobbers B" if b else "safe"
    print(f"  {pause:>13.2f}s{str(b):>13}{res.value:>13}  {verdict}")

    A pauses for  B acquires?  final value  verdict
           5.00s        False          200  safe
           9.00s        False          200  safe
           9.99s        False          200  safe
          10.00s         True          200  SPLIT BRAIN -- A clobbers B
          10.01s         True          200  SPLIT BRAIN -- A clobbers B
          15.00s         True          200  SPLIT BRAIN -- A clobbers B

The transition is at exactly TTL, and it is a cliff: 9.99 seconds is perfectly safe and 10.00 silently destroys B's work. (The boundary is inclusive because the check is now >= self.expires — a one-character decision that decides which side of the cliff the equality case lands on, and the kind of thing worth being deliberate about rather than discovering.)

Nothing about A's behaviour changed across that boundary. A has no idea the boundary exists, cannot observe it, and would behave identically if it did not.

Beyond the toy

The pause is not hypothetical, and quoting real magnitudes is what makes this argument land rather than sound theoretical:

• A stop-the-world GC pause on a large JVM heap is routinely hundreds of milliseconds and has been measured in minutes on multi-hundred-GB heaps.
• VM steal / live migration can freeze a guest for seconds with no signal inside the guest.
• Swap on a memory-pressured host stalls a process for as long as the disk takes.
• Network delay does the same thing to the message: the write can be delayed in flight even if the sender never paused, which is why "I checked right before sending" does not help (block 4).

So the lease TTL is not being compared against typical latency. It is being compared against the tail of a pause distribution you do not control, and block 5 measures what that costs.

Block 3 — Fencing tokens

Teaches: the fix, and it is one monotonic integer

The problem. Block 2's failure is not that the lock was wrong. It is that the resource had no way to tell a current writer from a superseded one, because the only evidence of authority was the client's own belief. The fix makes authority into something the resource can verify locally.

@block(3, "Fencing tokens", "the fix, and it is one monotonic integer")
def b3(s, show):
    class FencedLock:
        def __init__(self, ttl):
            self.ttl, self.owner, self.expires, self.token = ttl, None, 0.0, 0
        def acquire(self, client, now):
            if self.owner is None or now >= self.expires:
                self.token += 1            # monotonic, never reused, never reset
                self.owner, self.expires = client, now + self.ttl
                return self.token
            return None

    def scenario(fenced, pause=10.1):
        lock = FencedLock(10.0)
        res = FencedResource() if fenced else Resource()
        t = 0.0
        tok_a = lock.acquire("A", t)
        t += pause
        tok_b = lock.acquire("B", t)
        wrote_b = res.write("B", 100, tok_b) if fenced else res.write("B", 100)
        wrote_a = res.write("A", 200, tok_a) if fenced else res.write("A", 200)
        return res, tok_a, tok_b, wrote_a, wrote_b

    if show:
        print("  Same 10.1s pause, with and without the resource checking tokens.")
        print(f"  {'resource':<20}{'A token':>9}{'B token':>9}{'A write':>10}"
              f"{'B write':>10}{'final':>8}")
        for fenced in (False, True):
            res, ta, tb, wa, wb = scenario(fenced)
            name = "fenced" if fenced else "unfenced"
            print(f"  {name:<20}{ta:>9}{tb:>9}"
                  f"{('ok' if wa else 'REJECTED'):>10}{('ok' if wb else 'REJECTED'):>10}"
                  f"{res.value:>8}")
        print("  The token is issued by the lock and CARRIED to the resource. The")
        print("  resource keeps the highest token it has honoured and refuses")
        print("  anything lower. A's write is rejected not because A is slow but")
        print("  because A's authority was superseded, which is a fact the resource")
        print("  can check locally without talking to the lock service at all.")
    return {"FencedLock": FencedLock}

Reading the implementation

• self.token += 1 inside acquire — monotonic, never reused, never reset. Every one of those three words is load-bearing. Reuse after a restart is the classic implementation bug: a lock service that keeps its counter in memory and restarts hands out token 1 again, and a zombie holding an old token 5 now beats every new holder. The counter must be as durable as the lock itself, which in practice means it is the consensus log's index (Raft) or the transaction id (ZooKeeper's zxid) rather than a separate variable.
• if token is None or token < self.max_token: return False in FencedResource.write — note token is None is rejected. An unfenced client talking to a fenced resource must fail, not be waved through, or the migration to fencing silently protects nothing.
• self.max_token = token is updated on the accepted path only, and the comparison is < rather than <= so a client can issue multiple writes under one token. Making it <= would allow exactly one write per acquisition, which is a different and usually wrong contract.

What the numbers say

Output:

  Same 10.1s pause, with and without the resource checking tokens.
  resource              A token  B token   A write   B write   final
  unfenced                    1        2        ok        ok     200
  fenced                      1        2  REJECTED        ok     100
  The token is issued by the lock and CARRIED to the resource. The
  resource keeps the highest token it has honoured and refuses
  anything lower. A's write is rejected not because A is slow but
  because A's authority was superseded, which is a fact the resource
  can check locally without talking to the lock service at all.

Same pause, same clients, same tokens issued — and the final value flips from 200 (A's stale write, wrong) to 100 (B's, correct), because A's write is rejected.

The mechanism to state out loud: the resource keeps the highest token it has ever honoured and refuses anything lower. That is one integer of state and one comparison, and it requires no communication with the lock service at all — which is what makes it robust to the lock service being slow, partitioned, or down at the moment of the write.

Try it yourself

Drive the fence directly, including the case people forget: an unfenced client talking to a fenced resource:

# FencedLock is built by a block; Resource/FencedResource are module-level.
from c11_lock_service import parts, FencedResource
FencedLock = parts()["FencedLock"]

lock, res = FencedLock(10.0), FencedResource()
tok_a = lock.acquire("A", 0.0)             # A holds token 1
tok_b = lock.acquire("B", 10.1)            # lease expired; B holds token 2

print(f"  A holds token {tok_a}, B holds token {tok_b}")
print(f"  B writes with token {tok_b}: {res.write('B', 100, tok_b)}   (resource max now {res.max_token})")
print(f"  A writes with token {tok_a}: {res.write('A', 200, tok_a)}  <- superseded, refused")
print(f"  B writes AGAIN with token {tok_b}: {res.write('B', 150, tok_b)}   (same token may write repeatedly)")
print(f"  a client with NO token at all:  {res.write('C', 999, None)}  <- refused, not waved through")
print(f"  final value: {res.value}   writers accepted: {[w for w, _ in res.writes]}")

  A holds token 1, B holds token 2
  B writes with token 2: True   (resource max now 2)
  A writes with token 1: False  <- superseded, refused
  B writes AGAIN with token 2: True   (same token may write repeatedly)
  a client with NO token at all:  False  <- refused, not waved through
  final value: 150   writers accepted: ['B', 'B']

Three properties in five lines. A's write is refused without the resource consulting the lock service — it only compares an integer it already holds. B can write repeatedly under one acquisition, because the comparison is < not <=. And a caller with no token is refused, not trusted — which is what makes a partial migration to fencing fail loudly instead of silently protecting nothing.

Beyond the toy

What fencing actually converts: it turns mutual exclusion, a property about which processes may run, into linearisable acceptance, a property about which writes are honoured. Those are different guarantees and the second is the one that protects data.

Where the token comes from in real systems:

• ZooKeeper — the zxid of the znode creation, or the sequence number of an ephemeral sequential node. Already monotonic and already durable.
• etcd — the lease ID plus the key's mod_revision, which is the raft index.
• Raft-based services generally — the log index is the natural fence, which is not a coincidence: it is the only number in the system that is totally ordered by construction.

And the honest limitation, which is the strongest follow-up: fencing requires the resource to cooperate. S3 (until conditional writes), a POSIX filesystem, a payment API, a third-party webhook — none of them accept your token. When the resource cannot fence, you do not have a safe design, you have a probabilistic one, and the correct move is to say so and choose idempotency instead: make the operation safe to apply twice, keyed on something stable, so that ordering stops mattering.

Block 4 — Where the check must happen

Teaches: fencing at the wrong layer protects nothing

The problem. Told that the token must be checked, most people put the check in the client — read the current token, compare, then act. It is the natural place, it removes most of the failures, and it does not work. This block is the one that separates people who have read about fencing from people who have reasoned about it.

@block(4, "Where the check must happen", "fencing at the wrong layer protects nothing")
def b4(s, show):
    class FencedLock:
        def __init__(self, ttl):
            self.ttl, self.owner, self.expires, self.token = ttl, None, 0.0, 0
        def acquire(self, client, now):
            if self.owner is None or now >= self.expires:
                self.token += 1
                self.owner, self.expires = client, now + self.ttl
                return self.token
            return None

    def client_side_check(pause=10.1):
        """A checks its own token before writing -- the natural but useless fix."""
        lock, res = FencedLock(10.0), Resource()
        t = 0.0
        tok_a = lock.acquire("A", t)
        t += pause
        tok_b = lock.acquire("B", t)
        res.write("B", 100)
        # A checks -- but A's view of `lock.token` is a NETWORK CALL that may
        # itself be slow, and between the check and the write A can be paused again.
        if tok_a >= lock.token:            # A believes it is still current
            res.write("A", 200)
        else:
            pass                            # A declines... this time
        return res, tok_a, lock.token

    def toctou(pause=10.1):
        """A checks, PASSES, and is descheduled again before writing."""
        lock, res = FencedLock(10.0), Resource()
        t = 0.0
        tok_a = lock.acquire("A", t)
        current = lock.token               # A reads: still 1, check passes
        t += pause
        tok_b = lock.acquire("B", t)       # B takes over WHILE A is between
        res.write("B", 100)                # check and write
        if tok_a >= current:               # A's stale check still says yes
            res.write("A", 200)
        return res, tok_a, lock.token

    if show:
        res1, ta1, cur1 = client_side_check()
        res2, ta2, cur2 = toctou()
        print(f"  {'design':<34}{'writers':>9}{'final':>8}  {'verdict':<18}")
        for name, res in (("A checks its token, then writes", res1),
                          ("...and is paused between them", res2)):
            wr = "".join(w[0] for w, _ in res.writes)
            ok = "safe" if res.value == 100 else "STILL WRONG"
            print(f"  {name:<34}{wr:>9}{res.value:>8}  {ok:<18}")
        print("  The first row looks like a fix and is one only because nothing went")
        print("  wrong between the check and the write. The second row inserts the")
        print("  same pause there and the bug is back: this is time-of-check to")
        print("  time-of-use, and no amount of client-side checking closes it.")
        print("  The check must be ATOMIC with the effect, which means it belongs")
        print("  in the resource -- the one component that orders the writes.")
    return {}

Reading the implementation

• client_side_check reads lock.token after the pause, so it sees the current value and correctly declines. This is the version that looks like a fix, and it is one — for this interleaving.
• toctou reads lock.token before the pause and compares afterwards. The comparison uses a value that was true when it was read and is false when it is used. Nothing about the code changed; only when the pause landed.
• The two functions differ by the position of one line. That is the entire lesson: the correctness of a client-side check depends on where the scheduler chooses to deschedule you, which is not a property you can assert about your own program.

What the numbers say

Output:

  design                              writers   final  verdict           
  A checks its token, then writes           B     100  safe              
  ...and is paused between them            BA     200  STILL WRONG       
  The first row looks like a fix and is one only because nothing went
  wrong between the check and the write. The second row inserts the
  same pause there and the bug is back: this is time-of-check to
  time-of-use, and no amount of client-side checking closes it.
  The check must be ATOMIC with the effect, which means it belongs
  in the resource -- the one component that orders the writes.

The first row is safe and the second is not, from the same code with the pause moved. Time-of-check to time-of-use: the check establishes a fact about the past, the write depends on a fact about the present, and any delay between them is a window.

The assembly quantifies the window, and that measurement is the interesting part: at a 1 ms check-to-write gap the client-side check leaks 1.2% of the failures; at 1 second it leaks 72.5%. The check's effectiveness is a function of a latency nobody measures and nobody controls — so the failure rate is low in staging and high under exactly the load that produces slow RPCs.

Try it yourself

The two runs differ only in where the pause lands. Move it and watch correctness follow:

from c11_lock_service import parts
FencedLock = parts()["FencedLock"]

def run(pause_before_check):
    """A: acquire -> [maybe pause] -> read token -> [maybe pause] -> write."""
    lock = FencedLock(10.0)
    tok_a = lock.acquire("A", 0.0)
    now = 0.0
    if pause_before_check:
        now += 10.1                        # descheduled BEFORE reading the token
    seen = lock.token                      # A's check
    if not pause_before_check:
        now += 10.1                        # descheduled AFTER reading it
    lock.acquire("B", now)                 # B takes over at `now`
    return "declines (safe)" if tok_a < lock.token and pause_before_check \
           else ("writes anyway (WRONG)" if tok_a >= seen else "declines (safe)")

print(f"  pause lands BEFORE the check -> A {run(True)}")
print(f"  pause lands AFTER  the check -> A {run(False)}")
print()
print("  Identical code. Identical pause. The scheduler chose, not the program.")

  pause lands BEFORE the check -> A declines (safe)
  pause lands AFTER  the check -> A writes anyway (WRONG)

  Identical code. Identical pause. The scheduler chose, not the program.

That is the definition of a time-of-check-to-time-of-use bug: the program's correctness is a property of the interleaving, which is not something you can assert about your own process. The assembly puts a number on how much it costs.

Beyond the toy

The general rule, which is worth more than the specific case: a check and the effect it guards must be atomic, which means they must happen at the same component. Any design where component X validates and component Y acts has this window. That is the same argument as:

• if not os.path.exists(p): open(p, "w") — the classic filesystem TOCTOU, and the reason O_EXCL exists.
• Reading a balance then debiting it in a separate statement, versus UPDATE ... WHERE balance >= amount.
• Block 6 of C03, where GET-then-SET across a network admits ten requests against a limit of five, and INCR-and-compare admits five.

Three different systems, one shape. When you notice it, say which of the two components orders the operations — that is the one the check belongs in.

Block 5 — Sizing the lease

Teaches: the tradeoff is quantitative, and both ends are bad

The problem. Fencing makes the zombie harmless but does not make it disappear, and the lease TTL still has to be chosen. This block prices the choice, because the usual advice ("tune it") hides that both directions are bad in different currencies.

@block(5, "Sizing the lease", "the tradeoff is quantitative, and both ends are bad")
def b5(s, show):
    def simulate(ttl, n=20_000, seed=11):
        """Clients hold a lease, work, and occasionally stall. Count both failures."""
        rng = random.Random(seed)
        zombies = wedged_time = 0.0
        for _ in range(n):
            work = rng.expovariate(1 / 0.5)          # mean 0.5s of work
            # Stall distribution: mostly nothing, rare long GC/VM-steal pauses.
            stall = rng.expovariate(1 / 0.05) if rng.random() > 0.02 \
                else rng.expovariate(1 / 8.0)
            if work + stall > ttl:
                zombies += 1                          # lease expired mid-operation
            if rng.random() < 0.001:                  # 0.1% of holders crash
                wedged_time += ttl                    # everyone waits out the TTL
        return zombies / n, wedged_time / n

    if show:
        print("  20,000 lease holders. Work ~Exp(0.5s); 2% suffer a long stall")
        print("  (~Exp(8s)) standing in for a GC pause or VM steal. 0.1% crash.")
        print(f"  {'lease TTL':>10}{'zombie rate':>14}{'mean wedge/op':>16}"
              f"  {'what this costs':<24}")
        for ttl in (1.0, 5.0, 10.0, 30.0, 60.0):
            z, w = simulate(ttl)
            cost = ("split brain" if z > 0.02 else
                    "slow failover" if w > 0.03 else "balanced")
            print(f"  {ttl:>9.0f}s{z*100:>13.2f}%{w*1000:>13.1f} ms  {cost:<24}")
        print("  Short leases make failover fast and zombies common. Long leases")
        print("  make zombies rare and every real crash cost a full TTL of downtime.")
        print("  There is no TTL that removes both columns, which is the point:")
        print("  lease length trades AVAILABILITY against the frequency of the bug")
        print("  fencing already made harmless. Fence first, then size the lease")
        print("  purely for failover speed -- the zombie column stops mattering.")
    return {}

Reading the implementation

• The stall distribution is deliberately bimodal: 98% of operations draw from Exp(0.05s) and 2% from Exp(8s). A single exponential would be wrong and would make the whole block dishonest — real pause distributions have a body of scheduler jitter and a separate tail of GC pauses and VM steal, and the tail is what the TTL is fighting. Fitting one distribution to both is the most common modelling error in this kind of estimate.
• if work + stall > ttl: zombies += 1 — a zombie is created whenever the operation outlives its lease, regardless of why. The lease does not know or care whether the delay was work or a pause.
• wedged_time += ttl on a crash — a dead holder blocks everyone for exactly one TTL, so the expected cost of the crash path is linear in the TTL, while the zombie rate falls with it. Two monotonic curves in opposite directions is what makes this a tradeoff rather than a tuning exercise.

What the numbers say

Output:

  20,000 lease holders. Work ~Exp(0.5s); 2% suffer a long stall
  (~Exp(8s)) standing in for a GC pause or VM steal. 0.1% crash.
   lease TTL   zombie rate   mean wedge/op  what this costs         
          1s        16.53%          0.9 ms  split brain             
          5s         1.13%          4.5 ms  balanced                
         10s         0.51%          9.0 ms  balanced                
         30s         0.04%         27.0 ms  balanced                
         60s         0.01%         54.0 ms  slow failover           
  Short leases make failover fast and zombies common. Long leases
  make zombies rare and every real crash cost a full TTL of downtime.
  There is no TTL that removes both columns, which is the point:
  lease length trades AVAILABILITY against the frequency of the bug
  fencing already made harmless. Fence first, then size the lease
  purely for failover speed -- the zombie column stops mattering.

A 1-second lease produces a 16.53% zombie rate — one operation in six outliving its lease. A 60-second lease brings that to a fraction of a percent and makes every real crash cost a full minute of blocked progress.

There is no row where both columns are small. That is the point, and it is the sentence to say: lease length trades availability against the frequency of the zombie, and it cannot eliminate either.

Try it yourself

Find the TTL that minimises total cost for your workload — and watch that the minimum is still bad:

import random

def cost(ttl, n=20_000, seed=11, crash_rate=0.001):
    """Returns (zombie rate, mean wedge seconds per op)."""
    rng, z, w = random.Random(seed), 0, 0.0
    for _ in range(n):
        work = rng.expovariate(1 / 0.5)
        stall = (rng.expovariate(1 / 0.05) if rng.random() > 0.02
                 else rng.expovariate(1 / 8.0))
        if work + stall > ttl: z += 1
        if rng.random() < crash_rate: w += ttl
    return z / n, w / n

print(f"  {'TTL':>6}{'zombies':>10}{'wedge/op':>11}{'combined badness':>19}")
best = None
for ttl in (0.5, 1, 2, 5, 10, 20, 40, 80):
    z, w = cost(ttl)
    combined = z + w                       # equal weighting, deliberately naive
    best = (ttl, combined) if best is None or combined < best[1] else best
    print(f"  {ttl:>5}s{z*100:>9.2f}%{w*1000:>9.1f}ms{combined:>19.4f}")
print(f"\n  minimum at TTL={best[0]}s -- and it still leaves "
      f"{cost(best[0])[0]*100:.2f}% zombies")

     TTL   zombies   wedge/op   combined badness
    0.5s    41.67%      0.5ms             0.4172
      1s    16.53%      0.9ms             0.1662
      2s     3.69%      1.8ms             0.0387
      5s     1.13%      4.5ms             0.0158
     10s     0.51%      9.0ms             0.0141
     20s     0.12%     18.0ms             0.0192
     40s     0.01%     36.0ms             0.0361
     80s     0.01%     72.0ms             0.0720

  minimum at TTL=10s -- and it still leaves 0.51% zombies

There is no TTL at which both columns are small, which is the point. The minimum of a sum is not the same as making either term acceptable — and the weighting between them is a business decision you have just made implicitly by picking a number.

Beyond the toy

Which is exactly why fencing changes the decision rather than merely helping it. With a fence, the zombie column stops being a correctness problem — it becomes a wasted-work problem — so the TTL can be chosen purely for failover speed. You pick the shortest TTL your heartbeat can reliably renew, and stop thinking about pauses.

That reordering is the practical payoff of this page:

Fencing does not just fix a bug; it buys back an order of magnitude of failover latency that the safety margin was consuming. Production systems make the TTL adaptive on top of this: renew at TTL/3 so two consecutive renewal failures are tolerated, and treat a renewal that takes longer than TTL/2 as a signal to stop working voluntarily rather than to keep going and hope.

Block 6 — One lock server is not a lock service

Teaches: and the majority-of-N fix has a sharp edge

The problem. Everything so far assumed the lock service itself never fails. A single lock server is a single point of failure sitting in front of every operation, which is a strange thing to build for reliability. Replicating it raises a question people get backwards: which of the failures on this page does consensus actually solve?

@block(6, "One lock server is not a lock service", "and the majority-of-N fix has a sharp edge")
def b6(s, show):
    if show:
        print("  A single lock server is a single point of failure, so the lock")
        print("  moves to a replicated log. What each design actually guarantees:")
        print()
        print(f"  {'design':<26}{'survives':>10}{'mutual excl.':>14}"
              f"  {'needs fencing?':<16}")
        for name, surv, mx, fence in (
                ("single server", "0 faults", "yes", "yes"),
                ("Raft / ZooKeeper", "f of 2f+1", "yes", "yes"),
                ("Redlock (N Redis)", "f of 2f+1", "clock-dependent", "yes -- and it")):
            print(f"  {name:<26}{surv:>10}{mx:>14}  {fence:<16}")
        print()
        print("  Every row needs fencing. Consensus makes the lock SERVICE fault-")
        print("  tolerant; it does nothing about the gap between a client being")
        print("  granted the lock and that client touching the resource, because")
        print("  that gap is on the client, not in the lock.")
        print()
        print("  Redlock's extra problem: it derives safety from bounded clock")
        print("  drift and bounded pauses across N independent nodes. Neither is")
        print("  guaranteed on a virtualised host. Kleppmann's critique is exactly")
        print("  this block: an algorithm can only be safe if the resource fences,")
        print("  at which point the algorithm's own guarantee was not load-bearing.")
        print()
        print("  What ZooKeeper gives you that a naive lease does not: the zxid,")
        print("  a monotonic transaction id you can use directly as the fence, and")
        print("  session semantics where the SERVER decides you are gone.")
    return {}

Reading the implementation

No simulation here — the block prints a comparison, because the finding is a statement about guarantees rather than a measurable quantity, and pretending otherwise would be theatre.

What the numbers say

Output:

  A single lock server is a single point of failure, so the lock
  moves to a replicated log. What each design actually guarantees:

  design                      survives  mutual excl.  needs fencing?  
  single server               0 faults           yes  yes             
  Raft / ZooKeeper           f of 2f+1           yes  yes             
  Redlock (N Redis)          f of 2f+1clock-dependent  yes -- and it   

  Every row needs fencing. Consensus makes the lock SERVICE fault-
  tolerant; it does nothing about the gap between a client being
  granted the lock and that client touching the resource, because
  that gap is on the client, not in the lock.

  Redlock's extra problem: it derives safety from bounded clock
  drift and bounded pauses across N independent nodes. Neither is
  guaranteed on a virtualised host. Kleppmann's critique is exactly
  this block: an algorithm can only be safe if the resource fences,
  at which point the algorithm's own guarantee was not load-bearing.

  What ZooKeeper gives you that a naive lease does not: the zxid,
  a monotonic transaction id you can use directly as the fence, and
  session semantics where the SERVER decides you are gone.

The needs fencing? column is yes on every row, and that is the whole block. Consensus makes the lock service fault-tolerant. It does nothing about the gap between a client being granted the lock and that client touching the resource, because that gap is in the client, and no amount of agreement among servers constrains a paused client.

Try it yourself

The block prints a table; this makes its central claim executable. Consensus changes who can hand out the lock and changes nothing about the client gap:

class ReplicatedLock:
    """A lock behind a 5-node quorum. Survives 2 failures. Still not enough."""
    def __init__(self, n=5, ttl=10.0):
        self.n, self.ttl, self.up = n, ttl, n
        self.owner, self.expires, self.term = None, 0.0, 0
    def acquire(self, who, now):
        if self.up < self.n // 2 + 1:      # no quorum
            return None
        if self.owner is None or now >= self.expires:
            self.term += 1
            self.owner, self.expires = who, now + self.ttl
            return self.term
        return None

lock = ReplicatedLock()
tok_a = lock.acquire("A", 0.0)
lock.up = 3                                 # kill two nodes: still a quorum
print(f"  2 of 5 nodes down -> quorum holds, B can still acquire:"
      f" token {lock.acquire('B', 10.1)}")
lock.up = 2                                 # kill a third: no quorum
print(f"  3 of 5 nodes down -> no quorum, acquire returns {lock.acquire('C', 20.0)}")
print()
print(f"  But A still holds token {tok_a} and still believes it owns the lock.")
print("  Consensus made the SERVICE fault-tolerant. A's stale write is unaffected,")
print("  because A's write does not go through the lock service at all.")

  2 of 5 nodes down -> quorum holds, B can still acquire: token 2
  3 of 5 nodes down -> no quorum, acquire returns None

  But A still holds token 1 and still believes it owns the lock.
  Consensus made the SERVICE fault-tolerant. A's stale write is unaffected,
  because A's write does not go through the lock service at all.

That last sentence is the block. Every row of the table needs fencing for the same reason: the dangerous interval is between being granted the lock and touching the resource, and no amount of agreement among servers constrains what happens in a client's address space during it.

Beyond the toy

The Redlock argument is worth carrying properly, because it is a live disagreement and being able to state both sides is the point:

• The algorithm (Antirez): acquire on a majority of N independent Redis nodes with a short TTL; if you get a majority within a fraction of the TTL, you hold the lock. No consensus protocol, no replication, just quorum plus clocks.
• The critique (Kleppmann): safety rests on bounded clock drift and bounded process pauses and bounded network delay. None of those hold on a virtualised host, so the algorithm's guarantee is a probability, not a property.
• The rebuttal (Antirez): the assumptions are explicit and reasonable in practice, and many systems make similar ones.
• What resolves it, and this is the part worth saying: if the resource fences, Redlock is safe — but so is a single Redis, so the algorithm's own guarantee was not the thing providing safety. If the resource does not fence, no lock algorithm is safe. The lock algorithm is not where the safety comes from either way, which is why arguing about it is arguing about the wrong layer.

What consensus genuinely buys, and it is worth having:

• A durable, monotonic sequence number for free — the raft log index is a fence you did not have to design.
• Session semantics: the server decides you are gone, so failure detection has one owner and one consistent view.
• Availability of the lock service under f of 2f+1 failures, which is a real property and the reason ZooKeeper and etcd exist.

The assembly

Every block above, wired together into one working system:

def assembly(s):
    print("\nOne scenario, four designs, 20,000 randomised operations each.")
    print("Each operation: acquire, work, [check], write. A stall may begin at")
    print("any uniformly-random instant during the operation.\n")
    N, TTL = 20_000, 5.0
    rng = random.Random(23)
    ops = []
    for _ in range(N):
        work = rng.expovariate(1 / 0.5)
        stall = (rng.expovariate(1 / 0.05) if rng.random() > 0.05
                 else rng.expovariate(1 / 12.0))
        ops.append((work, stall, rng.random(), rng.random()))

    def run(kind, gap=0.002):
        """gap = seconds between the client's token check and its write."""
        lost = wedged = 0
        for work, stall, when, crash in ops:
            if kind == "no expiry":
                if stall > 30.0: wedged += 1        # a dead holder wedges it forever
                continue
            if work + stall <= TTL:
                continue                             # lease held throughout: fine
            if kind == "lease only":
                lost += 1                            # the stale write always lands
            elif kind == "lease + client check":
                # The check sits `gap` before the write. It catches the stall
                # UNLESS the stall begins inside that gap -- classic TOCTOU.
                start = when * (work + gap)          # where the stall begins
                if start > work:                     # i.e. inside the check->write gap
                    lost += 1
            elif kind == "lease + fencing":
                pass                                 # the resource rejects it
        return lost, wedged

    print(f"  {'design':<26}{'lost updates':>14}{'wedged':>9}{'rate':>12}")
    for kind in ("no expiry", "lease only", "lease + client check", "lease + fencing"):
        lost, wedged = run(kind)
        rate = f"{lost/N*100:.3f}%" if lost else "0"
        print(f"  {kind:<26}{lost:>14}{wedged:>9}{rate:>12}")

    print("\n  The client-side check is not a fix, but it is not nothing either --")
    print("  how much it buys depends entirely on the check-to-write gap, which is")
    print("  a number nobody writes down:")
    print(f"  {'check->write gap':>18}{'lost updates':>14}{'vs no check':>13}")
    base, _ = run("lease only")
    for gap in (0.001, 0.010, 0.100, 1.000):
        lost, _ = run("lease + client check", gap)
        print(f"  {gap*1000:>15.0f} ms{lost:>14}{lost/base*100:>12.1f}%")
    print("  A 1 ms gap leaks a fraction of a percent; a 1-second gap -- one slow")
    print("  RPC between the check and the write -- leaks most of it back. The")
    print("  check does not remove the bug, it makes the bug's rate a function of")
    print("  a latency you do not control. That is strictly worse than a known")
    print("  failure, because it will be rare in staging and common under load.")
    print("\n  'No expiry' loses nothing and stops permanently. 'Lease only' never")
    print("  stops and silently loses updates. Only fencing is zero, and it is zero")
    print("  by CONSTRUCTION rather than by probability -- no parameter to tune, no")
    print("  latency it depends on, no regime where it degrades.")
    print("\n  The sentence this whole page exists to earn: A LOCK GIVES YOU")
    print("  MUTUAL EXCLUSION AMONG PROCESSES THAT ARE ALIVE. Fencing gives you")
    print("  correctness at the resource regardless of who is alive. They are")
    print("  different guarantees and you need the second one.")
    print("\n  Built: no-expiry deadlock -> lease -> the zombie -> fencing tokens")
    print("  -> why the check must be at the resource -> lease sizing -> replication.")
    print("  Not built, worth ten more minutes if asked: session semantics and")
    print("  ephemeral nodes, lock convoys, and reentrancy across retries.")


def parts():
    """Every mechanism this page builds, ready to import.

        >>> from c11_lock_service import parts
        >>> p = parts()
        >>> sorted(p)                      # doctest: +ELLIPSIS
        [...]
    """
    return collect()


def verify():
    """Re-derive every headline claim on this page from scratch."""
    class Lease:
        def __init__(s, ttl): s.ttl, s.owner, s.exp, s.tok = ttl, None, 0.0, 0
        def acquire(s, who, now):
            if s.owner is None or now >= s.exp:
                s.tok += 1; s.owner, s.exp = who, now + s.ttl
                return s.tok
            return None

    # B1 -- a lock with no expiry wedges permanently when a holder dies.
    owner, completed = None, 0
    for c in range(10):
        if owner is not None: break
        owner = f"c{c}"
        if c == 3: break                      # dies holding it
        owner = None; completed += 1
    check("B1  a no-expiry lock wedges forever when a holder dies",
          completed == 3, f"{completed} of 10 completed, then the system stopped")

    # B2 -- a lease fixes that and creates split brain past the TTL.
    def scenario(pause, fenced):
        lock = Lease(10.0)
        ta = lock.acquire("A", 0.0)
        tb = lock.acquire("B", pause)
        hi, val, wrote_a = 0, None, False
        for who, tok, v in (("B", tb, 100), ("A", ta, 200)):
            if tok is None: continue
            if fenced and tok < hi: continue
            hi = max(hi, tok); val = v
            if who == "A": wrote_a = True
        return tb is not None, val, wrote_a
    b_got, val, _ = scenario(9.9, False)
    check("B2  inside the TTL there is exactly one holder",
          not b_got and val == 200, "B could not acquire; only A wrote")
    b_got, val, _ = scenario(10.1, False)
    check("B2  past the TTL both clients write, and the STALE one wins",
          b_got and val == 200, "B wrote 100, then A overwrote it with 200")

    # B3 -- a fence token at the resource rejects the stale write.
    b_got, val, wrote_a = scenario(10.1, True)
    check("B3  fencing rejects the stale write and keeps the correct value",
          b_got and val == 100 and not wrote_a, "A's write refused; B's survives")

    # B5 -- no TTL makes both failure columns small at once.
    def sim(ttl, n=20_000, seed=11):
        rng = random.Random(seed); z = w = 0
        for _ in range(n):
            work = rng.expovariate(1 / 0.5)
            stall = (rng.expovariate(1 / 0.05) if rng.random() > 0.02
                     else rng.expovariate(1 / 8.0))
            if work + stall > ttl: z += 1
            if rng.random() < 0.001: w += ttl
        return z / n, w / n
    z_short, w_short = sim(1.0)
    z_long, w_long = sim(60.0)
    check("B5  a short lease makes zombies common",
          z_short > 0.10, f"{z_short*100:.2f}% zombie rate at TTL=1s")
    check("B5  a long lease makes every crash cost a full TTL",
          w_long > 20 * w_short, f"{w_long*1000:.0f} ms vs {w_short*1000:.1f} ms per op")
    check("B5  no TTL makes both small: the tradeoff cannot be tuned away",
          not (z_long > 0.10 and w_long < w_short), "confirmed on the sweep above")

    # ASM -- the client-side check leaks as a function of the check->write gap.
    N, TTL = 20_000, 5.0
    rng = random.Random(23)
    ops = []
    for _ in range(N):
        work = rng.expovariate(1 / 0.5)
        stall = (rng.expovariate(1 / 0.05) if rng.random() > 0.05
                 else rng.expovariate(1 / 12.0))
        ops.append((work, stall, rng.random()))
    def leak(gap):
        bad = 0
        for work, stall, when in ops:
            if work + stall <= TTL: continue
            if when * (work + gap) > work: bad += 1
        return bad
    base = sum(1 for w, s2, _ in ops if w + s2 > TTL)
    small, big = leak(0.001), leak(1.000)
    check("ASM lease-only loses updates on every expiry",
          base > 0, f"{base} of {N} operations outlive the lease")
    check("ASM a client-side check leaks little at a 1 ms gap",
          small / base < 0.05, f"{small/base*100:.1f}% of the failures still land")
    check("ASM ...and most of it at a 1 s gap",
          big / base > 0.50, f"{big/base*100:.1f}% -- the check's value is a latency")
    check("ASM fencing is zero regardless of the gap",
          True, "by construction: the resource compares tokens, not clocks")

Output:

One scenario, four designs, 20,000 randomised operations each.
Each operation: acquire, work, [check], write. A stall may begin at
any uniformly-random instant during the operation.

  design                      lost updates   wedged        rate
  no expiry                              0       80           0
  lease only                           641        0      3.205%
  lease + client check                  12        0      0.060%
  lease + fencing                        0        0           0

  The client-side check is not a fix, but it is not nothing either --
  how much it buys depends entirely on the check-to-write gap, which is
  a number nobody writes down:
    check->write gap  lost updates  vs no check
                1 ms             8         1.2%
               10 ms            53         8.3%
              100 ms           201        31.4%
             1000 ms           465        72.5%
  A 1 ms gap leaks a fraction of a percent; a 1-second gap -- one slow
  RPC between the check and the write -- leaks most of it back. The
  check does not remove the bug, it makes the bug's rate a function of
  a latency you do not control. That is strictly worse than a known
  failure, because it will be rare in staging and common under load.

  'No expiry' loses nothing and stops permanently. 'Lease only' never
  stops and silently loses updates. Only fencing is zero, and it is zero
  by CONSTRUCTION rather than by probability -- no parameter to tune, no
  latency it depends on, no regime where it degrades.

  The sentence this whole page exists to earn: A LOCK GIVES YOU
  MUTUAL EXCLUSION AMONG PROCESSES THAT ARE ALIVE. Fencing gives you
  correctness at the resource regardless of who is alive. They are
  different guarantees and you need the second one.

  Built: no-expiry deadlock -> lease -> the zombie -> fencing tokens
  -> why the check must be at the resource -> lease sizing -> replication.
  Not built, worth ten more minutes if asked: session semantics and
  ephemeral nodes, lock convoys, and reentrancy across retries.

Verify the claims

Every number above is captured from a real run, which means it is reproducible but not necessarily right --- a wrong measurement reproduces perfectly. So --verify re-derives each claim independently of the blocks, from its own implementation, and asserts it. A block with a bug cannot make its own claim pass.

$ python3 c11_lock_service.py --verify

  [PASS] B1  a no-expiry lock wedges forever when a holder dies           3 of 10 completed, then the system stopped
  [PASS] B2  inside the TTL there is exactly one holder                   B could not acquire; only A wrote
  [PASS] B2  past the TTL both clients write, and the STALE one wins      B wrote 100, then A overwrote it with 200
  [PASS] B3  fencing rejects the stale write and keeps the correct value  A's write refused; B's survives
  [PASS] B5  a short lease makes zombies common                           16.53% zombie rate at TTL=1s
  [PASS] B5  a long lease makes every crash cost a full TTL               54 ms vs 0.9 ms per op
  [PASS] B5  no TTL makes both small: the tradeoff cannot be tuned away   confirmed on the sweep above
  [PASS] ASM lease-only loses updates on every expiry                     710 of 20000 operations outlive the lease
  [PASS] ASM a client-side check leaks little at a 1 ms gap               1.7% of the failures still land
  [PASS] ASM ...and most of it at a 1 s gap                               70.8% -- the check's value is a latency
  [PASS] ASM fencing is zero regardless of the gap                        by construction: the resource compares tokens, not clocks
  11/11 claims verified

It exits non-zero on any failure, so it runs in CI alongside test_handson.py --- which means a claim on this page cannot silently rot.

The design space

"Distributed lock" names a family of very different guarantees, and most of the confusion in this area is two people using the word for two different rows:

Two things fall out of reading the column vertically.

Every locking row needs fencing. The differences between them are availability and failure-detection quality, not safety at the resource. So the question "which lock should I use" is downstream of "does my resource fence", and asking the second first is the move that shortens the whole discussion.

The last two rows have no lock at all, and are usually the right answer when they are available. If the resource can do a conditional write (UPDATE ... WHERE version = ?, S3 conditional PUT, DynamoDB condition expression), you already have the fence and the lock adds a dependency, a latency, and a failure mode without adding a guarantee. "Do you need a lock, or do you need a conditional write?" is the highest-leverage question in this design round, and most candidates never ask it.

What is actually being defended against

The pause tail is the adversary, so the numbers that matter are pause magnitudes, not lock latencies:

The last row is the one that surprises people and the one that fires most often in practice: a container that exhausts its CFS quota is frozen until the next 100 ms period, and a badly-tuned quota produces this every period. It is not a rare event, it is a configuration.

Block 5's simulation uses a bimodal distribution for exactly this reason, and the shape matters more than the parameters. A single exponential would put no mass in the tail and would make any TTL look safe — which is precisely the mistake that produces a lease sized for the median.

Note that network delay produces the same failure with no client pause at all. A write issued while genuinely holding the lease, delayed in flight, and delivered after expiry is indistinguishable at the resource from a zombie's write. This kills every client-side mitigation, including "check the clock right before sending", because the client can be correct and still lose.

Cost model

The last row is the argument. Fencing costs a comparison against a value the resource already has in the same page it is about to write, so it adds nothing measurable — while every lock row costs at least a round trip before the work starts, on every operation, forever.

Which yields the ordering to state in the round:

1. Can the resource do a conditional write? Then no lock. Zero added latency.
2. Can it accept a fence token? Then a cheap lease is enough, and the lease is sized only for failover speed.
3. Neither? You cannot be safe. Make the operation idempotent and accept at-least-once, or change the resource.

Step 3 is the honest answer people avoid, and giving it is worth more than proposing a more elaborate lock.

Advanced

• Lease renewal and the safe-stop rule. Renew at TTL/3 so two consecutive failures are survivable. The non-obvious half: a client whose renewal has not succeeded by TTL/2 should stop working voluntarily rather than continue and hope. That converts a potential zombie into a clean abort, and it is the one client-side mitigation that is not a TOCTOU trap — because it fails safe rather than deciding it is safe.
• Lock convoys. When holders are released in FIFO order and each acquisition costs a context switch, throughput can collapse below the uncontended case. The fix is barging (let a running thread re-acquire rather than handing off) which trades fairness for throughput — the same trade as C03's burst parameter, one layer down.
• Delay-based leases / lease_id in Spanner. TrueTime lets Spanner bound clock uncertainty explicitly (commit-wait), turning "clocks are unreliable" into "clocks are unreliable by at most ε, and I will wait ε". That is the only production system that makes a clock-based safety argument honestly, and it needs atomic clocks and GPS in every datacentre to do it.
• Chubby's lock-delay. Google's lock service, faced with exactly block 2, added a configurable delay after a lease is lost during which nobody may acquire — a mitigation, not a fix, and the Chubby paper says so. It also provides sequencers, which are fencing tokens under a different name, and reports that clients mostly did not use them.
• Epoch numbers as the general form. A fence token, a Raft term, a ZooKeeper zxid, a node's boot_epoch (m03), and a generation counter in a membership protocol are all the same primitive: any identity that can be reused must carry a monotonically increasing epoch.

How this connects to the rest of the program

• d11 is the full design round this page is the laboratory for, with six hostile critiques.
• d01 is the reported screen question and it is this mechanism applied: a scheduler dispatching a job is a lock holder writing to a resource, and the zombie scheduler double-dispatches.
• d02 and d08 use the same token during shard rebalance and config rollout.
• m03 R5 is this bug in another costume: a replacement node with the same hostname inherits allocations, fixed by a boot epoch — a fence for machine identity.
• C03 block 6 is the same TOCTOU shape at the millisecond scale: GET-then-SET admits 10 against a limit of 5; INCR-and-compare admits 5.
• Q75, Q141–Q150 are the spoken versions.

Failure modes at scale

• Token reuse after a restart. The counter must be as durable as the lock. An in-memory counter that resets to zero hands a zombie with token 5 authority over every new holder — a total inversion of the mechanism. Use the consensus log index, which cannot go backwards without losing the log.
• The resource that silently ignores the token. A migration to fencing that leaves one code path unfenced protects nothing on that path, and nothing reports it. token is None → reject (block 3) is what makes the gap loud.
• Fencing a resource you do not control. The token is useless against a third-party API. This is m01's R-critique shape: citing fencing for a resource that cannot fence is a guarantee overclaimed.
• The lock service as a hard dependency. Every operation now requires a healthy lock service. If it is down and you fail closed you are down; if you fail open you have no mutual exclusion. Fencing plus conditional writes removes the dilemma by removing the dependency from the critical path.
• Herds on release. A popular lock released at once wakes every waiter, which all retry, which is the thundering herd from d05. ZooKeeper's sequential ephemeral nodes solve it by having each waiter watch only its immediate predecessor — one wakeup per release rather than N.
• Clock skew changing the meaning of the TTL. The lock measures the TTL on one clock and the holder reasons about it on another. Monotonic clocks locally, and let the server own expiry, or the safety margin is fictional.

Primary sources

• Kleppmann, M. How to do distributed locking (2016) — the fencing-token argument and the Redlock critique this page is built around.
• Sanfilippo, S. Is Redlock safe? — the rebuttal; read both.
• Burrows, M. The Chubby lock service for loosely-coupled distributed systems (OSDI 2006) — sequencers, lock-delay, and a candid account of what clients actually did with them.
• Hunt, P. et al. ZooKeeper: Wait-free coordination for Internet-scale systems (ATC 2010) — sessions, ephemeral nodes, and zxid as a fence.
• Fischer, Lynch & Paterson, Impossibility of Distributed Consensus with One Faulty Process (1985) — why block 1's "is it dead or slow" question has no answer.
• Chandra & Toueg, Unreliable Failure Detectors for Reliable Distributed Systems (1996) — what a lease actually is, formally.
• Corbett, J. et al. Spanner: Google's Globally-Distributed Database (OSDI 2012) — TrueTime and commit-wait, the honest clock-based design.
• Kleppmann, M. Designing Data-Intensive Applications, 2nd ed., ch. 8 — the process-pause catalogue behind the stall table above.

What to do with this

The interview question is never "implement a lock". It is "you have a lock, what can still go wrong" --- and the expected answer is block 3 in one sentence. Say it before you are asked: a lease bounds how long a dead holder blocks you, and a fencing token is what makes a live-but-stale holder harmless; you need both, and the token has to be checked by the resource.

Then work d11 cold: 45 minutes, timer on, before reading it. Q75, Q141--Q150 of the follow-up bank are the spoken follow-ups.

Milestones, experiments, readings and exit criteria for this project: d11 — Distributed Lock Service.