Leases, Fencing Tokens & Distributed Locks

Part 0. Start here

The problem: a job that must run exactly once

A nightly billing job must run on exactly one worker. It writes the day's 50,000 invoices in 10 chunks of 5,000. Worker A holds a 10-second lease on the job (a lock that expires unless it is renewed) and renews it every 3 seconds. These are our example's numbers; they are also exactly the settings in the example of the AWS DynamoDB Lock Client's README (withLeaseDuration(10), withHeartbeatPeriod(3)).

At second 4, A stops for 15 seconds. It might be a stop-the-world garbage-collection pause, or its VM being paused for a live migration; the length is our assumption. Its renewals stop too, because the thread that sends them lives in the same frozen process. At second 13 the lease runs out and worker B takes the job. At second 19, A wakes up with chunk 2 already built in its buffers, still believing it owns the job, and sends it. The billing store charges each invoice it records, so if that write lands, 5,000 customers are billed twice.

The big picture

Synthesizing vector architecture diagram...

What to notice: A never learns it lost the lease until the store tells it. The lock service decided who should work; the store's check is what kept the data correct.

What you'll be able to do after this page

1. Explain the difference between a lock, a lease and a fencing token, and the three rules that tie them together (Part 1).
2. Walk through acquiring, renewing and releasing a lease, and say which state lives in the log and which lives only in the leader's memory (Part 2).
3. Say which clock times a lease, why offset between machines usually doesn't matter but rate does, and what a margin can and can't cover (Part 3).
4. Trace a paused holder being stopped by a fencing token, including why the new holder raises the fence before it reads (Part 4).
5. Write the fence as a conditional write in DynamoDB, SQL and S3, and build a lease on a DynamoDB item without trusting anyone's clock (Part 5).
6. Explain how a crashed holder's claim is found and cleaned up, and compute the earliest safe takeover (Part 6).
7. Treat leader election and single-writer failover as leases with epochs (Part 7).
8. Explain what happens when the lock service itself fails over, why an async Redis failover is different, and what the Redlock argument was about (Part 8).
9. Decide when you don't need a lock at all (Part 9).
10. Trace an acquire, a renewal and a fenced write from your code through the network, the lock service and its log to the store (Part 10).
11. Map all of this to AWS services, and name the look-alikes that are not fences (Part 11).

You may have arrived from a step that relies on this: step 2.2 of the distributed unique ID generator loop (a worker froze for 40 seconds), step 2.4 of the job scheduler loop (a paused worker finished a job someone else re-ran), step 2.5 of the message queue loop (a stale worker deleted a message another worker holds), or step 2.4 of the ride-sharing loop (a late accept after the offer expired). This page is the "why" behind all four.

---

Part 1. The core mental model

Three words get used loosely in design reviews: lock, lease and fencing token. They mean different things, and most bugs in this area come from treating one as another. This Part pins them down, then introduces the example we follow for the rest of the page.

Lock, lease, fence

Synthesizing vector architecture diagram...

What to notice: the check sits at the resource, not at the worker or the lock service. The lock service only hands out numbers; the resource is where an old holder is actually stopped.

Three rules the design never breaks

Not every "lease" is this lease

Two loops use the word for something else. The rate limiter loop (step 2.3) leases blocks of quota to gateways: a time-bounded grant of capacity, not of exclusive ownership, so nobody needs to be fenced. The URL shortener loop (step 1.2) "leases" blocks of counter values with an atomic add and no expiry at all. Neither needs this page's machinery.

The example we follow

Real systems hold thousands of leases, which is too many to watch. So one small story runs through the whole page: the billing job changes hands. Every trace on this page was produced by running a private reference simulator of this setup (true time, per-machine clocks, a 3-node lock service, the store), not worked out by hand.

The story in five beats: A holds the job (Part 2), A freezes (Parts 3 and 4), B takes over (Part 4), B dies holding it (Part 6), and the lock service loses its leader while C holds it (Part 8). Each Part shows only its own slice of events; the full 24-event table is in Part 12.

---

Part 2. Acquire, renew, release: the happy path

A crashed holder of a plain lock blocks everyone forever. The obvious fix, "a lock plus a timeout in the client", doesn't work: the timeout lives in the holder, so when the holder dies nobody else knows the timeout passed, and when the holder pauses its timeout pauses too. The expiry must be known to the grantor. This Part walks through the three operations that make that work.

Acquire

textCopy
ACQUIRE(key K, lease length T)
  1. ask the lock service for a new lease with TTL T
  2. in one transaction: create K bound to that lease, only if K doesn't exist
  3. the service commits both through its log (a majority of nodes has them on disk)
  4. reply: lease id, and token = the revision at which K was created
  5. the leader's lease tracker starts timing T on its monotonic clock, from when it applied the grant
  6. the holder records sent_at (its monotonic clock, read before step 1)
     and its own stop time: sent_at + T - margin

For A at t = 0.0: the grant and the key creation commit at revision 7; the leader's tracker sets the deadline to 0.0 + 10 = 10.0; A's own stop time is 0.0 + 10 − 2 = 8.0.

What the lock service keeps, and where

The last row is the surprise. It is safe only because of what a new leader does after a failover (Part 8).

Renew and the holder's stop time

textCopy
RENEW LOOP (holder)                                  -- runs every T/3
  1. sent_at = monotonic now                          -- read BEFORE sending
  2. send keep-alive(lease id) to the leader
  3. leader: reset deadline = its now + T, in memory only; reply
  4. on success: stop_at = sent_at + T - margin
  5. on failure: retry (new leader if needed) until stop_at; then give up the lease locally

BEFORE EVERY ACTION (holder)
  if monotonic now >= stop_at: stop, don't act

Synthesizing vector architecture diagram...

What to notice: the acquire goes through the log to a majority; the keep-alive stops at the leader. The holder's stop time is always 2 s (the margin) before the service's deadline.

The first events of the story, as the simulator printed them:

Release

When the job is done, the holder revokes its lease. The key goes with it at once, so the next holder doesn't have to wait out the TTL. A release must be conditional on still owning the lock: revoking your own lease id only ever deletes keys bound to that lease, so a holder that lost the lock can't delete the next holder's key. The same rule applies to every lock store: Redis's documented release deletes the key only if it still holds the holder's random value; a plain delete is unsafe because a slow client can remove a lock someone else now holds.

textCopy
RELEASE(lease id)
  1. finish the work, including the store's final write (with the token)
  2. revoke(lease id)            -- deletes only keys bound to this lease
  3. the service commits the delete; the revision goes up

In the story, C releases at t = 52.0 and the key is deleted at once at revision 16 (Part 8).

Snapshot S1: A holds the job

Synthesizing vector architecture diagram...

After event 4: A holds token 7, the store's fence is 7, and chunk 1 is done.

---

Part 3. Time: whose clock decides?

A lease is a promise about time, and every machine has its own clock. Two questions decide whether the promise holds: which kind of clock times the lease, and whose clock is used when one machine judges another's lease.

Two clocks in every machine

Two different clock errors

In the lock-service design, the holder times its lease from its send and the leader times it from its apply, each on its own monotonic clock. Neither ever reads the other's clock, so offset doesn't matter at all; only rate does. Offset matters only when one machine's wall clock writes a deadline and another machine's clock reads it, which is exactly what a lease stored in a database does (Part 5). Then the margin must be bigger than the worst offset.

What the margin covers

The stop time is our first formula:

$$\text{stop time} \;=\; \text{time the last successful renewal was sent} \;+\; \text{lease} \;-\; \text{margin}$$

For A's renewal sent at 3.0: 3.0 + 10 − 2 = 11.0. For B's acquire sent at 13.5: 13.5 + 10 − 2 = 21.5.

The storage's clock must not decide

A tempting shortcut is to let the database judge expiry: "take over if lease_until < now()". In DynamoDB there is no now(): condition expressions offer comparisons and the functions attribute_exists, attribute_not_exists, attribute_type, begins_with, contains and size, and nothing that reads the current time. So :now is always some client's clock, and Part 5 deals with that. A single SQL database's now() is one clock, so using it for rows in that same database is fine: every judgement uses the same clock. It doesn't extend to anything outside that database.

Trace: B's wall clock steps back 3 s

B acquired at 13.5 (token 12, service deadline 23.5, stop time 21.5). At t = 16.0, B's wall clock is stepped back 3 s.

Synthesizing vector architecture diagram...

What to notice: the straight line is B's monotonic clock and the line that drops at 16 is its wall clock; the flat line is the stop reading 21.5. The monotonic clock crosses it at true 21.5, the wall clock only at true 24.5, one second after the lock service's deadline of 23.5.

---

Part 4. The pause, the zombie and the fencing token

Part 3 ended with the one thing no clock can catch: a pause between a check and an act. This Part shows the pause happening, the old holder coming back as a zombie (a process acting on a lock it no longer holds), and the fencing token stopping it.

Trace: A pauses, B takes over

Synthesizing vector architecture diagram...

What to notice: A's only check (at 3.9) passed, and it was true when A made it. Everything that saved the data happened at the store: B raised the fence at 13.6, so A's write at 19.05 met a fence of 12.

Where the token is checked

At the resource, on every write and on the release of anything the resource holds for the job. The holder's own "am I still inside my lease?" check is an optimization: it stops a healthy holder from sending writes that would be refused anyway, and keeps overlap rare. It can never be the safety mechanism, because a pause can land right after it.

textCopy
FENCED WRITE (at the store, one atomic conditional write)
  accept only if  fence <= :token          -- reject lower
  then            fence = :token, apply the data change
  a rejected write means: you have lost the lock; stop and discard local state

Why equal is accepted: the current holder writes many times with the same token (A wrote with 7 at 0.5 and 1.0; B wrote with 12 at 13.6, 14.0 and 20.0), so "equal" means "the current holder". The gold answer in the drill The GC Pause That Corrupted Shared Storage rejects token <= last_seen; that is right only when each token makes exactly one write.

Raise the fence first

B's first act, at 13.6, was one conditional write that raised the fence to 12 and returned the old row, before B read anything or did any work. That order matters.

Snapshots S2 and S3: the zombie is stopped

Synthesizing vector architecture diagram...

S2, after event 10: A is frozen with a write it still believes in; B holds token 12 and has already raised the fence.

Synthesizing vector architecture diagram...

S3, after event 12: A's write was refused and A let go. The row is exactly as B left it.

The same fence on S3

The drill's resource is S3, which has no "greater than" condition: a conditional PutObject can only say "only if this key doesn't exist" (If-None-Match: *) or "only if the object's ETag is still the one I read" (If-Match). The fence still works with two changes: each holder writes its output under a key that includes its token, and it commits by rewriting one small manifest object with If-Match on the ETag it last saw. Raising the fence first means the new holder rewrites the manifest with its token before it does anything else. The simulator's trace (ETags labelled E0, E1, … in order):

Readers trust only what the manifest names, so A's stray object changes nothing. S3 gives compare-and-set on "the version I read", not a numeric fence; the token in the manifest body is what tells a reader (and an auditor) which holder wrote each chunk. When several conditional writes race on the same key, S3 lets the first to finish succeed and fails the rest with 412.

The same rule in other systems

The stock exchange loop (step 1.4) does the same thing to a journal: the spare engine fences the 2-of-3 journal with epoch e+1 before it replays, so the old primary can't append anything the spare didn't see.

What fencing does not protect

Fencing protects exactly the resources that check the token, and nothing else. An email provider, a payment provider's API or a partner's webhook will happily accept A's late call. For those, the only safety net is an idempotency key stored with the side effect, so a duplicate call is recognised and dropped; the Idempotency & Effectively-Once Processing loop primitive covers that. This is also the answer to the first question of the drill The GC Pause That Corrupted Shared Storage: an expiring TTL lock can't protect storage because the paused holder doesn't know its lock expired, so the storage must refuse its writes by token.

---

Part 5. Conditional writes are the check

A fence is useless if the check and the write are two steps: a zombie could pass the check, pause, and write after the new holder raised the fence. The check and the write must be one atomic conditional write in the store. This Part shows it in DynamoDB, SQL and S3, then builds the loops' favourite pattern: a lease that lives in a DynamoDB item, with no lock service at all.

DynamoDB

When the fence and the data are in one item, a single UpdateItem or PutItem with a ConditionExpression does it, and a failed condition returns ConditionalCheckFailedException. Our invoices are separate items, so each batch goes in a TransactWriteItems with a ConditionCheck on the fence item plus the invoice puts. A transaction holds at most 100 actions, and no two may touch the same item, so each carries 1 check + 99 puts:

• one chunk of 5,000 invoices: 5,000 ÷ 99 = 50.5, so 51 transactions;
• the whole run of 10 chunks: 10 × 51 = 510 transactions.

jsonCopy
{
  "TransactItems": [
    { "ConditionCheck": {
        "TableName": "billing",
        "Key": { "pk": { "S": "billing:2026-09-28" } },
        "ConditionExpression": "fence <= :t",
        "ExpressionAttributeValues": { ":t": { "N": "7" } } } },
    { "Put": {
        "TableName": "invoices",
        "Item": { "pk": { "S": "inv#2026-09-28#05001" }, "amount": { "N": "4200" } } } }
  ]
}

A's request at 19.05 (token 7 against fence 12) fails as a whole, with no invoice written:

jsonCopy
{
  "__type": "TransactionCanceledException",
  "CancellationReasons": [
    { "Code": "ConditionalCheckFailed", "Message": "The conditional request failed" },
    { "Code": "None" }
  ]
}

The raise itself is one UpdateItem on the fence item: SET fence = :t, #s = :running, owner_token = :t, claimed_since = :now with ConditionExpression: fence <= :t, asking for the old values back (ReturnValues: ALL_OLD).

SQL

In one transaction, lock the fence row first, then write the data:

sqlCopy
BEGIN;
UPDATE billing_fence SET fence = :t
 WHERE job_id = 'billing:2026-09-28' AND fence <= :t;   -- 1 row: go on; 0 rows: we lost, ROLLBACK
INSERT INTO invoices (...) VALUES (...);                 -- the chunk
COMMIT;

The UPDATE takes the row lock, so a concurrent raise waits until we commit and then re-checks its WHERE against the committed fence (at READ COMMITTED; at stricter isolation the second raise fails with a serialization error and retries). A's transaction at 19.05 updates 0 rows and rolls back.

S3

If-None-Match: * creates an object only if the key doesn't exist; If-Match: <ETag> replaces it only if it is still the version we read. A's manifest commit at 19.05:

httpCopy
PUT /render/billing/manifest.json HTTP/1.1
Host: example-bucket.s3.amazonaws.com
If-Match: "E2"

HTTP/1.1 412 Precondition Failed

What each store can compare

Shared limit: every fence raise and every ConditionCheck (and, when the lease is kept on the same item, every claim and renewal) touches the one fence item. A DynamoDB partition gives at most 1,000 write units a second, and one item always lives in one partition. Our 510 transactions a night are nothing, but a fence item shared by a busy stream of writers can become the hot key.

A lease built on a DynamoDB item

Many loops skip the lock service and keep the lease itself in a DynamoDB item. The item:

Claim, renew and release, as UpdateItem requests:

jsonCopy
{ "Claim": {
    "ConditionExpression": "attribute_not_exists(holder) OR lease_until < :claimant_now_minus_margin",
    "UpdateExpression": "SET holder = :me, lease_until = :my_now_plus_lease, rvn = :new_rvn, epoch = if_not_exists(epoch, :zero) + :one" },
  "Renew": {
    "ConditionExpression": "holder = :me AND epoch = :e",
    "UpdateExpression": "SET lease_until = :my_now_plus_lease, rvn = :new_rvn" },
  "Release": {
    "ConditionExpression": "holder = :me AND epoch = :e",
    "UpdateExpression": "REMOVE holder SET lease_until = :zero" } }

Release clears holder; it never deletes the item, because the item carries the epoch. The problem is the claim's condition: :claimant_now_minus_margin comes from the claimant's clock, while lease_until came from the holder's. That is the "one clock writes, another reads" case from Part 3.

The Lock Client's clock-free rule avoids comparing clocks at all: the claimant reads rvn, waits a full lease on its own monotonic clock, and claims only if rvn is unchanged (condition rvn = :seen). The Lock Client never stores absolute times in DynamoDB, only the lease duration. Kubernetes' Lease-based election uses the same idea: a candidate times expiry from when it last observed a change to the lease record.

Trace: D replaces B, and D's clock is 3 s fast

We replay the start of the story on a DynamoDB lock item, with worker D in B's place. A's clock is correct: it acquired at 0.0 (lease_until 10.0, rvn v1) and renewed at 3.0 (lease_until 13.0, rvn v2), then paused at 4.0. A's own stop time is still 3.0 + 10 − 2 = 11.0: that is when A's right to act ends. D's wall clock reads 3 s ahead of true time. D polls the item once a second, at 0.5, 1.5, 2.5 and so on.

Synthesizing vector architecture diagram...

What to notice: only the no-margin bar starts before A's bar ends. That half second is an overlap a pause doesn't even need; the other two rules leave a gap.

TTL is not a deadline, and it resets epochs

DynamoDB's Time to Live looks like a lease that frees itself, and it isn't one:

• TTL deletes expired items typically within a few days, not at the expiry time. Until then the item is still there and can be read and updated, so every reader must filter by the expiry attribute itself.
• Never put TTL on an item that carries the epoch counter. When the item is deleted, the next claim's if_not_exists(epoch, :zero) + :one starts again at 1. From the simulator: A claims with epoch 1, D with 2, a release by clearing holder keeps 2, the next claim gets 3; then TTL deletes the item and the next claim gets epoch 1 again, a token the store has already seen. Keep the counter on an item that is never deleted, and release by clearing holder.
• Restores bring old epochs back. A point-in-time restore of the lock table returns every epoch to its old value, so before using a restored table, jump every epoch by a large amount (the ID generator loop, step 3.2, adds an offset of 1,000,000).
• A multi-Region strongly consistent (MRSC) global table has no TTL at all.

---

Part 6. Crashes and orphaned locks

A holder that crashes can't release anything. The lock service's key frees itself when the lease runs out, but the store's row doesn't: it still says RUNNING, owned by a dead worker. If nobody is left to retry, the job never finishes. This Part is about finding and cleaning up those orphans (claims whose holder is gone) without ever breaking the fence.

Trace: B dies holding the job

Synthesizing vector architecture diagram...

What to notice: every arrow into RUNNING is a fence raise, and the sweeper's arrow is conditional on the exact owner and fence it saw. If a new holder raised the fence in between, the sweeper's write fails and does nothing.

Two kinds of lock, two kinds of cleanup

The marker must be findable. So it is written in the same conditional write that raises the fence (events 2, 9 and 19), with an attribute that puts the row in a sparse index: an index that holds only rows that have the attribute. No claim can exist without being in the index, and the sweeper reads the index instead of scanning the table.

The sweeper

textCopy
EVERY 10 s:
  for each row in the sparse index (claimed rows only):
    ask the lock service: is there a live key for this job?    -- no clock comparison
    if yes: skip
    if no, and not seen before: remember orphan_seen_at = now, owner and fence seen
    if no, and seen at least 5 s ago:
      conditional write: state = QUEUED, remove claimed_since
        only if state = RUNNING AND owner_token = :seen AND fence = :seen

The sweeper never compares timestamps from other machines: it asks the authority whether a lease is alive. It waits for a second sighting so that a holder caught between acquiring its key and raising the fence isn't swept by mistake. And it is only a liveness mechanism: the fence keeps the data safe even if the sweeper is wrong, because a wrongly re-queued job is taken by a new holder with a higher token, and the old holder's writes are then refused.

How soon can someone take over?

Our second formula:

$$\text{earliest safe takeover} \;=\; \text{last renewal the authority applied} \;+\; \text{lease}$$

B's last renewal reached n1 at 19.5, so the earliest safe takeover is 19.5 + 10 = 29.5. Add a claim margin only when the claimant judges expiry on its own clock (Part 5); here the lock service itself deleted the key, so no margin is needed.

A sweeper that doesn't storm

If our own renewal path fails (the lock service is unreachable for 30 s, or a bad deploy stalls every heartbeat thread), thousands of leases expire together although their holders are healthy. A naive sweeper then re-queues all of them at once, and every job restarts. The job scheduler loop (step 2.5) adds these rules:

Snapshot S4: the orphan

Synthesizing vector architecture diagram...

S4, after event 16: the lock is free, but the row still says RUNNING by 12, and nobody is left to retry. Only the sparse index makes this row findable.

---

Part 7. Leader election and single writers

Many loops need exactly one active instance of something: one pacer, one relay, one matching engine, one writing Region. That is a lock on a role instead of a job, and the same machinery applies.

A leader is a lease holder

Whoever holds the lease on the role's key is the leader, and the leader's fencing token is called its epoch (or generation, or term). Every write the leader makes carries its epoch, so anything from an old leader can be refused.

textCopy
CAMPAIGN(election prefix P)
  1. create key P/<me> bound to my lease            -- etcd: a key; ZooKeeper: an ephemeral sequential node
  2. the key with the lowest create revision (or sequence number) leads
  3. otherwise: watch only the key just before mine
  4. when that key is deleted: check again; if mine is now the lowest, I lead
  5. my epoch = my key's revision; stamp it on every write

Watching only your predecessor matters: if every candidate watched the leader's key, one deletion would wake all of them at once (a herd), and all would race to read the prefix. With predecessor watches, each deletion wakes exactly one candidate. etcd's own lock recipe works this way: a waiter waits for the deletion of keys with a lower create revision than its own.

An election has no orphan

The main story needed a sweeper because C was not waiting for the job. In an election, the waiters queue. Side trace from the simulator, starting from the moment A's key is gone:

Synthesizing vector architecture diagram...

What to notice: C watches only B's key. When B's key is deleted at 29.5, exactly one candidate wakes, and it leads with epoch 13, higher than any epoch B used.

etcd, ZooKeeper and Kubernetes compared

Google's Chubby lock service put the fence into the lock service itself: a holder can ask for a sequencer (the lock's name, its mode and a generation number) and hand it to the servers it writes to, which check it before acting. For servers that can't check sequencers, Chubby offers a lock-delay: when a holder vanishes, the lock can't be re-granted for a period up to a bound of one minute, which narrows the window for a zombie without closing it.

Single writers across a failover

Promoting a new writer while the old one may still be writing is the classic split brain. The recipe every loop uses:

textCopy
SINGLE-WRITER HANDOVER
  1. the writer holds a lease on "I am the writer" (a flag read from a majority of copies, or an MRSC item)
  2. the old writer stops when it can't renew, by its OWN monotonic clock
  3. the new writer waits out the lease plus a margin, by its OWN monotonic clock
  4. the new writer bumps the epoch IN THE STORE IT WILL WRITE, before its first write
  5. consumers compare (epoch, version) and refuse anything from a lower epoch

The payment loop (step 3.5) uses a 10 s lease and makes the new Region wait 15 s (the lease plus a 5 s margin) before its first ledger write. From the simulator, with the old writer's last good refresh at the moment of the flip (the worst case):

Synthesizing vector architecture diagram...

What to notice: the old writer's right ends at 10 at the latest, the new writer starts at 15: a gap of at least 5 s, never an overlap. If the old Region died at the flip, nothing is written for the whole 15 s.

Where the loops use this:

The maps loop (step 2.3) also numbers its weight updates as "epochs", but those only order updates; nobody holds anything, so nothing needs fencing.

---

Part 8. When the lock service itself fails

The lock service is a distributed system too. If a failover in it can hand the same lock to two holders, or hand out the same token twice, everything built on it breaks. This Part shows what survives a leader change, what a minority can't do, and why an asynchronously replicated cache is a different kind of lock service.

Where the grant lives

Grants, releases, expiry deletes and the revision counter are entries in the replicated log: the leader answers only after a majority of nodes has them on disk, so they survive the loss of any minority. (How the majority commit works is the Replication, Quorums & Read-Your-Writes loop primitive's subject, and Primitive #09: Consensus covers Raft.) Renewals are not in the log: the leader's lease tracker resets the deadline in memory.

Synthesizing vector architecture diagram...

What to notice: the solid path (grant) goes to the followers and waits for a majority; the dotted path (keep-alive) ends in n1's memory. If n1 dies, the grant survives on n2 and n3; the latest deadline does not.

Trace: the leader dies while C holds the job

C never stopped working: its failed renewal at 49.2 was well inside its stop time of 54.2, and the retry found the new leader. The new leader's rule, restarting at full length, means a failover can only make a lease longer, never shorter, so no holder is ever cut off early. The price is on the other side: had C died at 47.0 together with n1, its lock would have lasted until 59.1 instead of 56.2. etcd has an optional lease-checkpoint feature (the LeaseCheckpoint feature gate, off by default) that makes the leader persist each lease's remaining TTL now and then, so a new leader can use it instead of the full TTL.

Synthesizing vector architecture diagram...

S5, after event 22: the grant and the token survived on n2 and n3; only the deadline was rebuilt, and it was rebuilt longer.

What a minority can't do

This is the drill The Network Partition That Elected Two Leaders. If a partition cuts a 5-node lock service into 2 and 3 nodes, the 2-node side can't commit anything: a commit needs 3 of 5, and it has 2. So it can't grant, release or expire a lock, or advance the revision counter; an old leader stuck there accepts requests it can never commit, and they time out. The 3-node side elects a leader in a higher term and carries on, and when the partition heals the old leader sees the higher term, steps down, and discards its uncommitted entries. As for size: 3 nodes tolerate 1 failure and 5 tolerate 2 (a majority is 2 of 3 or 3 of 5). Five nodes cost more machines and a commit waits for two followers instead of one; for a lock service whose writes are grants and releases, not every renewal, that cost is usually small, and the extra failure it tolerates matters most during maintenance, when one node is already down on purpose.

What if the lock service is Redis?

A single Redis primary with SET key value NX PX 10000 is a lease: fast and simple. Its failover is the problem. Redis replicates to its replicas asynchronously, so a write the primary acknowledged may never reach the replica that gets promoted. We replay events 19 to 21 on a lock kept in a primary/replica cache, with the token from INCR on a counter key. The replication lag of about 100 ms and the promotion time are assumptions:

Synthesizing vector architecture diagram...

What to notice: the failover lost both the lock and the counter's last increment, so D got the same token as C, and the store can't tell them apart.

Redlock and the argument about it

Redlock, as the Redis documentation describes it, uses N = 5 independent Redis masters (no replication between them):

textCopy
REDLOCK ACQUIRE(key, random value, TTL)
  1. read the current time
  2. try SET key value NX PX TTL on all 5 masters in parallel, each with a short timeout
  3. held only if a majority (at least 3) succeeded AND the time elapsed is less than the TTL
  4. validity = the initial TTL minus the time elapsed
  5. on failure: release on all 5, even the ones that seemed to fail

Three things the Redis documentation itself says: if you care about correctness you should implement fencing tokens, which applies to any distributed lock; Redis does not use a monotonic clock for key expiry, so a wall-clock shift may result in a lock being acquired by more than one process; and after a crash a node must stay down a bit longer than the maximum TTL (a delayed restart) unless it persists with fsync on every write, or its restart can let a second majority form.

The clock problem, from the simulator:

Synthesizing vector architecture diagram...

What to notice: two majorities of 5 always share a node, and here that node's clock jump let it forget the first client. The safety argument depended on node 3's clock.

The verdict: Redlock, like every lock, needs a check at the resource for correctness. Use Redis (single or Redlock) for efficiency locks, where a rare double run only wastes work; for correctness locks, use a consensus-backed service or a strongly consistent database that hands out a token that only grows, and check it at the resource. Kleppmann recommends a consensus system such as ZooKeeper for this.

Across Regions

The same holds for any store: a lock needs one linearizable authority. The Multi-Region Failover loop primitive covers detection and promotion; this page's part is the lease, margin and epoch arithmetic in Part 7.

Restores

A lock service restored from a backup forgets every token it handed out after the backup was taken. From the simulator: C got revision 15 at 40.2; if the service were restored at t = 45 from a snapshot taken at revision 14, the next key created would get revision 15 again, and C and D would share a token exactly as in the cache failover. So every restore jumps the counter: etcd's snapshot restore takes --bump-revision (with --mark-compacted, so watchers don't read history that no longer matches). With a bump of 1,000,000, D's key gets revision 1,000,015. The DynamoDB lock table rule in Part 5 is the same idea.

---

Part 9. Do you need a lock at all?

A lock service is one more system to run, one more thing that can fail over, and a gap with no owner after every crash. Now that we know the resource's check is what really keeps the data safe, the honest question is whether the lock earns its place.

When the database is enough

If the data and the "lock" live in one ACID database, and the work fits in one transaction, use the database: a row lock (SELECT … FOR UPDATE) or a compare-and-set UPDATE … WHERE version = :v is both the authority and the fence, and there is no lease to expire. The hotel loop (step 1.4) holds rooms this way: the hold's expiry is judged on the database's clock (one clock, for rows in that database), a sweeper using SKIP LOCKED releases expired holds, and in the loop's words "the sweeper handles liveness (rooms come back); the conditions handle safety."

The catch is session-bound locks: an advisory lock, or a FOR UPDATE held open across minutes of work, is a lease on a database connection. If the worker pauses while the connection stays up, it still holds the lock; if the connection drops, the database releases the lock while the worker may still be working. It has the same zombie problem as any lease, so writes made outside that transaction still need a fence.

Four ways to let one worker win without a lock service

How much to lock

• Granularity: lock the smallest thing that must have one owner: a job, a partition, a row. A global lock serializes everything behind it.
• Throughput: keep-alives all land on the lock service's leader, so its load is holders ÷ renewal interval: 10,000 holders renewing every 3 s is 10,000 ÷ 3 ≈ 3,333 keep-alives a second, served from memory. Grants, releases and expiries are the expensive ones: each is a majority disk write.
• Ordering: a worker that needs several leases takes them in one fixed global order, so two workers can never wait on each other in a cycle.

The same job three ways

Three workers start chunk 2 (5,000 invoices) at the same moment. From the simulator:

An equal-terms comparison

For a deeper look at isolation levels and what FOR UPDATE really locks, see Primitive #21: Isolation levels.

---

Part 10. End to end: from your code to the disk

So far "acquire", "renew" and "write with the token" were single steps. In reality each crosses several layers, and a pause or a delay can happen in any of them. Knowing which layer does what explains why a grant costs a disk write on a majority of machines and a renewal doesn't, and why the only check nothing can bypass is the one at the store.

The layers

Synthesizing vector architecture diagram...

What to notice: the store sits beside the lock service, not behind it. The worker talks to both, and a pause anywhere in the worker process sits between them.

An acquire, traced down

Event 1: A acquires at t = 0.0.

Synthesizing vector architecture diagram...

What to notice: the leader answers after its own disk and one follower's; the third node is not waited for. The grant and the key creation are two log entries in etcd (the lease grant, then the create-key transaction); both follow this path.

A keep-alive, traced down

Event 4: A renews at 3.0. The library records sent_at, the request crosses the network, and the leader resets L1's deadline to 13.0 in memory and replies. There is no log append, no replication and no fsync (what those cost on each node is in Write-Ahead Log, fsync & Group Commit). Keep-alives cost the leader CPU and network only; a slow disk hurts them only indirectly, because etcd's documentation warns that long fsync latencies can make it miss heartbeats, causing request timeouts and temporary leader loss, and an election pauses renewals (Part 8).

A fenced write, traced down

Synthesizing vector architecture diagram...

What to notice: both requests hit the same one-step check. Nothing between A's pause and the store could stop A's request from being sent; the store is the one place it can't get past.

Who does what

The sidecar trap: if a separate process (a sidecar or agent) sends the heartbeats on the app's behalf, the heartbeats prove the sidecar is alive, not the app. A frozen app keeps its lease while doing nothing, and the fence becomes the only protection all the time.

---

Part 11. On AWS

The mechanism is the same on AWS; what changes is which piece plays the authority, which plays the fence, and which services only look like locks.

Managed services that use it

Running it yourself

Look-alikes that are not this mechanism

---

Part 12. What you've learned

Back to the billing job

A froze with 5,000 invoices in its buffer, and nobody was billed twice. Here is how each piece did its job:

• A held a lease timed on its monotonic clock, with a stop time 2 s before the service's deadline (S1, Parts 2 and 3). B's wall clock jumped and nothing changed, because no duration was timed on it.
• A paused past its lease. B took over with a higher token, and its first act was to raise the fence to 12, so A's late chunk arrived with 7 and was refused (S2 and S3, Part 4). The check was one conditional write in the store (Part 5).
• B died holding the job. The lock freed itself at 29.5; the claim on the row did not, but it was findable through the sparse index, and a sweeper re-queued it with a conditional write; C took over with token 15 (S4, Part 6).
• The lock service lost its leader. The grant and the token were safe in the majority log; the new leader rebuilt the lease longer, and C's retry found it (S5, Part 8).
• C finished, set DONE, left the sparse index and released the lock (S6: no holder, fence 15, row DONE).

The whole story, event by event

The cheat card

Failure checklist

• Does every protected write carry the token, and does the resource check it (reject lower, equal accepted)?
• Does a new holder raise the fence before it reads or writes?
• Are all durations (renewal timers, stop times) on a monotonic clock?
• Is any lease condition comparing a timestamp written by one machine's clock with another machine's clock, and is the margin bigger than the worst offset?
• Is every host's clock offset alarmed at a threshold well below the margin?
• Can the token counter ever go backwards: a TTL on the epoch item, a deleted lock item, a restore without a bump, an async failover?
• Is every claim marker findable through an index, written in the same write as the fence raise?
• Does the sweeper re-queue conditionally, and does it pause instead of storming when many leases expire at once?
• Are side effects outside your store (emails, payments, webhooks) protected by idempotency keys?
• Are heartbeats sent by the app process itself, not a sidecar?
• Is the lock's authority one linearizable store (not an async cache, not an MREC global table)?

Think-first drills

Interview questions

Where to go next

• The Idempotency & Effectively-Once Processing loop primitive (coming): protecting side effects the fence can't reach.
• The Replication, Quorums & Read-Your-Writes loop primitive (coming): how the majority commit behind every grant works. Meanwhile, Primitive #09: Consensus, Raft and Paxos.
• The Multi-Region Failover loop primitive (coming): detection and promotion around the single-writer handover in Part 7. Meanwhile, Primitive #24: Disaster recovery and multi-Region.
• Write-Ahead Log, fsync & Group Commit: what "a majority has it on disk" costs on each node.
• Primitive #15: Distributed unique ID generators: the machine-number lease and the ID fence in the ID generator loop.
• Drills: The GC Pause That Corrupted Shared Storage (answered in Parts 4 and 9) and The Network Partition That Elected Two Leaders (answered in Part 8).
• Loops: the ID generator (steps 1.4, 2.2, 2.5, 3.2), the job scheduler (steps 1.2, 1.3, 2.4, 2.5, 3.3), the message queue (steps 1.2, 2.5) and ride-sharing (steps 2.3, 2.4, 3.6).