Lease Locks: Fencing Tokens, Shared Locks and Deadlock Victims

Lease Locks: Fencing Tokens, Shared Locks and Deadlock Victims

You've joined Platform Coordination, the team that runs leasekeeper, a small Chubby-style lock service for the batch fleet. A job takes a named lock with a time-limited lease, works while it holds the lock, and renews the lease before it runs out. Every grant carries a fencing token. The storage service in front of the data (FencedStore) refuses any write whose token is lower than one it has already accepted, so a job that stalled past its lease cannot overwrite the job that took over.

Last Tuesday that safety net failed and two nightly jobs wrote the same export. The incident review is Part 1. Three roadmap items follow it, and the third one overturns a design assumption the code makes today.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh service and returns one result per operation. Every operation is [name, ts, ...args]. ts is an integer number of seconds and never decreases from one operation to the next. Errors are returned as "error: <code>" strings, never raised.

• An unknown operation name returns "error: unknown operation" (the name is checked first). A non-integer ts (booleans are not integers), a wrong number of arguments, or an operation that is not a list of at least a name and a ts returns "error: invalid arguments".
• For an operation's own arguments, invalid arguments means: a client id, lock name, key or value that is not a non-empty string, a ttl that is not an integer, or a token that is not an integer >= 1. invalid ttl means an integer ttl outside 1..86400. All type checks come before any range check.
• inspect lists holders by token, lowest first, and queue oldest first. A lock nobody has used returns {"holders": [], "queue": []}. Until Part 2, every mode is "exclusive".
• repeat is a load helper for the performance tests and is already implemented. template is an operation without its ts, for example ["acquire", "job{i}", "L{i%100}", 60]. It runs the template count times (1 <= count <= 100000, step >= 0); run i (counting from 0) executes at ts + i*step, with these placeholders replaced inside every string argument: {i}, {i+A}, {i%K}, {i+A%K} (the last means (i+A) % K). It returns {"ops": count, "results": tally}: a string result counts under that string, a list result under its first element, anything else under "other". A key "aborted" (only present when non-zero) counts the clients that Part 3 lists as aborted. A bad count, step or template (including a nested repeat) is invalid arguments.

The lease rules

These rules are the contract for every Part.

1. Time. There is no clock and nothing runs in the background. The state of the service is always "as of the current operation's ts": before an operation is handled, every lease with expires_at <= ts has been retired. This applies to every operation with a known name and an integer ts, including ones that then fail validation.
2. Leases. A lease granted at time g for ttl seconds has expires_at = g + ttl and is usable while ts < expires_at. At ts == expires_at it is gone: renew fails, release answers not holder, and another client can take the lock. renew sets expires_at = ts + ttl (measured from the renew, not from the old expiry, so it can also shorten the lease) and changes nothing else.
3. Hand-over instant. When a lease is retired, the lock passes to the next waiter *at the instant the lease ended*: for a lapse that is its expires_at, for a release it is the release's ts. It is not the ts of whichever operation happened to notice. The new lease is [e, e + ttl) using the waiter's own requested ttl. If that lease has already lapsed by the current ts, it is retired at its own expires_at and the next waiter is promoted at that instant, and so on until the lock is held by a lease that is still valid or nobody waits. Lapses are processed in the order they happened.
4. Queue. Waiters are FIFO. An acquire is granted on the spot only if the lock is free and nobody is queued; otherwise it joins the end of the queue and returns its position (1 = next in line, counting itself).
5. Fencing tokens. Each lock has its own counter. Every grant, immediate or from the queue, takes the next number, starting at 1. A token is never issued twice for the same lock, never goes down, and the counter survives periods when nobody holds or awaits the lock. renew keeps the token.
6. Storage. write to lock L is accepted if token >= the highest token this store has accepted for L (0 if none), so a holder can write several keys under one token. An accepted write records that token and the value; a rejected write (stale token) changes nothing. The store does not know who holds what: it never looks at leases, and L does not need to exist in the lock table. read returns the last accepted value for (lock, key), or null.
7. Release. A holder's release returns "released": its lease ends now and rule 3 runs with the release's ts. A client that is *waiting* for the lock gets "withdrawn": its request leaves the queue and those behind it move up. Anyone else, including a client whose lease already lapsed under rule 1, gets not holder.
8. One lock per client (until Part 3). Batch jobs are single-lock clients: acquire returns client busy if the client holds a lease on any lock or is waiting for any lock, including the lock named in the request.

Part 1: Incident review INC-5127

Goal: make the service follow the lease rules above. Find out why it doesn't.

Two exports jobs wrote exports/daily within the same minute even though fencing was on. This is the replay of the audit log (ttls in seconds), next to what production answered and what the rules require:

[["acquire", 0, "etl-a", "exports/daily", 30],
 ["acquire", 5, "etl-b", "exports/daily", 20],
 ["acquire", 8, "etl-c", "exports/daily", 15],
 ["write", 20, "exports/daily", "part-1", "a:rows 1-100", 1],
 ["renew", 30, "etl-a", "exports/daily", 30],
 ["write", 31, "exports/daily", "part-1", "b:rows 1-100", 2],
 ["write", 32, "exports/daily", "part-1", "a:rows 101-200", 1],
 ["inspect", 55, "exports/daily"],
 ["read", 56, "exports/daily", "part-1"]]

should return

[["granted", 1, 30], ["queued", 1], ["queued", 2], "ok", "error: not holder", "ok",
 "error: stale token",
 {"holders": [["etl-c", "exclusive", 3, 65]], "queue": []},
 "b:rows 1-100"]

Follow-up reports from other teams (each one is a deviation from the rules, none is a diagnosis):

• INC-5131: "job-7 took a lock that had sat idle overnight and its very first write was refused as stale."
• INC-5133: "The audit log shows two different jobs holding the same lock with the same fencing token, one after the other."
• INC-5138: "A job released its lock after its lease had run out and the next job in line got a second lease it should not have had."
• INC-5140: "The job that holds the lock can write one key but its second write with the same token is refused."
• INC-5144: "etl-b's lease is shown starting at the time somebody next looked at the lock, not when etl-a's lease ended."

tests/ contains tests for some of these; hidden tests cover every lease rule, including leases that lapse in chains and a lock that sees long idle gaps.

Part 2: Shared and exclusive locks

Goal: the config service needs many readers or one writer. acquire gets an optional last argument, the lock mode.

["acquire", ts, client, lock, ttl] and ["acquire", ts, client, lock, ttl, mode], where mode is "shared" or "exclusive" (default "exclusive"). Any other mode value is invalid arguments (a type-style error, so it is reported before an out-of-range ttl). Everything in the lease rules still applies; these rules refine rules 3, 4, 5 and 7.

1. Compatibility. A lock is held either by one exclusive lease or by any number of shared leases. A request is *compatible* with the current holders if the lock has no holders, or the request and all holders are shared.
2. Immediate grant. An acquire is granted on the spot only if the queue is empty and the request is compatible. Otherwise it joins the end of the queue. In particular a shared request never overtakes a queued request, so a writer waiting behind readers can't be starved by newer readers.
3. Queue grants. Whenever the holders of a lock change (a release, a lapse, a withdrawn queue entry), look at the head of the queue: while the head is compatible with the current holders, grant it and look at the next one; stop at the first request that is not compatible. So consecutive shared requests at the head are granted together, and an exclusive request at the head is granted only once no one holds the lock. Every grant here follows rule 3's hand-over instant, so a writer behind several readers starts at the instant the *last* reader's lease ended.
4. Tokens and leases. Every grant gets its own token, in the order the requests are granted. Each shared holder has its own lease and is renewed, released and retired on its own. inspect lists holders by token, lowest first, each as [client, mode, token, expires_at].
5. Withdrawing. A waiting client's release removes its request; if that makes the head of the queue compatible (a writer that was blocking readers), rule 3 runs with the release's ts.
6. Rule 8 is unchanged: still one lock per client.

Example

[["acquire", 0, "r1", "cfg", 50, "shared"],
 ["acquire", 1, "r2", "cfg", 20, "shared"],
 ["acquire", 2, "w1", "cfg", 30],
 ["acquire", 3, "r3", "cfg", 10, "shared"],
 ["inspect", 4, "cfg"],
 ["inspect", 50, "cfg"],
 ["inspect", 80, "cfg"]]

returns

[["granted", 1, 50], ["granted", 2, 21], ["queued", 1], ["queued", 2],
 {"holders": [["r1", "shared", 1, 50], ["r2", "shared", 2, 21]], "queue": [["w1", "exclusive"], ["r3", "shared"]]},
 {"holders": [["w1", "exclusive", 3, 80]], "queue": [["r3", "shared"]]},
 {"holders": [["r3", "shared", 4, 90]], "queue": []}]

r3 is compatible with the readers but waits because w1 is ahead of it. r2 lapses at 21 and r1 at 50, so w1 starts at 50 (not 21, not 80) and holds [50, 80); r3 is then granted at 80.

Part 3: Transactions and deadlock victims

Goal: jobs now run as multi-step transactions that acquire several locks one after another. That allows deadlocks (A holds L1 and waits for L2 while B holds L2 and waits for L1), and renewing leases does not help because both keep renewing. When an acquire leaves a client stuck in a wait cycle, abort the youngest transaction on the cycle.

This replaces rule 8 and the single-lock design behind it (ClientIndex maps a client to one lock).

1. Client rule (replaces rule 8). A client may hold any number of locks (one lease per lock) but waits for at most one lock at a time. acquire returns client busy only if the client is waiting for some lock, or already holds the lock it asks for. All other acquire behaviour and the order of its checks are unchanged.
2. Age. A client is *registered* the first time one of its acquire operations passes validation and the busy check and is granted, queued, or aborted as a deadlock victim. Its age is its registration number: the first client ever registered has age 1, the next has age 2, and so on. A client stays registered when it releases locks or its leases lapse. Only being aborted (rule 5) unregisters it; if it later acquires again it registers afresh with a new, larger age. Younger means larger age.
3. Wait-for graph. A client waiting for lock L has an edge to (a) every client that holds L, in any mode, and (b) every client queued ahead of it on L. A client that is not waiting has no outgoing edges. The graph is always the current lock table: leases that lapsed under rule 1 are not holders.
4. When to check. Only at the moment an acquire is placed in a wait queue. Grants, releases, renews and lapses never need a check: none of them can create a cycle.
5. Resolution. For the requester R that was just queued, repeat:
6. Let C be the set of clients that lie on at least one cycle passing through R, that is every client reachable from R that can also reach R (R itself is in C when a cycle exists). Every cycle in the graph passes through R, because each earlier request resolved its own. If there is no cycle, stop.
7. The victim is the member of C with the largest age.
8. Abort the victim: if it is waiting, remove its queue entry (and apply Part 2's queue-grant rule to that lock); then release every lock it holds, in ascending lock-name order (plain string comparison), applying the queue-grant rule after each one. Every lease granted this way starts at the ts of the acquire. Finally unregister the victim. Storage and fencing counters are untouched.
9. If the victim was R, stop. Otherwise go back to step 1: the aborts may already have granted R its lock, in which case R is no longer waiting and there is no cycle.
10. Response. If R itself was aborted: ["deadlock", victims]. Otherwise the usual ["granted", token, expires_at] or ["queued", position] (the position after all aborts), with the list of aborted clients, in abort order, appended as one extra element when at least one client was aborted. victims lists every client aborted by this request, in abort order, ending with R when R itself is aborted.
11. status. ["status", ts, client] returns {"age": age or null, "holds": [[lock, mode, token, expires_at], ...] sorted by lock name, "waiting": lock or null}. A client that is not registered returns {"age": null, "holds": [], "waiting": null}. Error: invalid arguments.

Example 1: the younger of two jobs is aborted

[["acquire", 0, "alice", "L1", 100],
 ["acquire", 1, "bob", "L2", 100],
 ["acquire", 2, "bob", "L1", 100],
 ["acquire", 3, "alice", "L2", 100],
 ["status", 4, "bob"],
 ["status", 4, "alice"],
 ["inspect", 4, "L1"]]

returns

[["granted", 1, 100], ["granted", 1, 101], ["queued", 1], ["granted", 2, 103, ["bob"]],
 {"age": null, "holds": [], "waiting": null},
 {"age": 1, "holds": [["L1", "exclusive", 1, 100], ["L2", "exclusive", 2, 103]], "waiting": null},
 {"holders": [["alice", "exclusive", 1, 100]], "queue": []}]

Alice's request at 3 closes the cycle alice -> bob -> alice. Bob has age 2 and alice age 1, so bob is aborted even though alice made the request. Releasing L2 grants it to alice (now token 2, from 3 to 103), so she is no longer waiting.

Example 2: a waiter ahead of the requester is on the cycle

[["acquire", 0, "H", "L", 100],
 ["acquire", 1, "Z", "M", 100],
 ["acquire", 2, "Y", "L", 100],
 ["acquire", 3, "H", "M", 100],
 ["acquire", 4, "Z", "L", 100]]

returns [["granted", 1, 100], ["granted", 1, 101], ["queued", 1], ["queued", 1], ["deadlock", ["Y", "Z"]]]. Z's request queues behind Y, so Z has edges to H (holder) and Y (ahead). H waits for Z's lock M, and Y waits for H, so C = {Z, H, Y}. Y (age 3) is the youngest and is aborted first; it holds nothing. Z is still on the cycle Z -> H -> Z, so the next round has C = {Z, H}: Z (age 2) is younger than H (age 1) and is the requester, so Z is aborted too and M passes to H.

Part 4: Scale

Goal: the hidden tests use repeat to drive up to about 20,000 operations over thousands of locks and clients, wait queues of hundreds of clients, and a lock with two thousand shared holders. Everything from Parts 1-3 must still hold, and the whole suite has a few seconds.

Work per operation must depend on what that operation actually touches: the leases that lapsed since the previous operation, the clients reachable from the new waiter in the wait-for graph. It must not depend on the total number of locks or clients, and it must not compare every pair of waiters in a queue. A service that looks at every lock on every operation, rebuilds the whole wait-for graph on every queued acquire, or lists an edge for each pair of queued waiters will time out.

Notes

• models.py, validation.py, errors.py and config.py are known-good.
• You may use the AI assistant freely; you are expected to verify what it produces.
• Later parts must not break earlier ones; hidden tests re-check earlier behaviour with Part 2 and Part 3 features in play.
• Parts 1-3 is a strong result. Part 4 is a stretch.