Only one worker at a time: locks, leases, fencing tokens

Many designs say: "Only one server may run this job at a time." Or they say: "Only one worker may change this record at a time." The interviewer asks: "How do you make sure of that? What if the server that holds the lock freezes?"

A weak answer says "use a Redis lock with a timeout" and stops. A strong answer says why the lock was needed: to save work, or to protect data. It then says how a holder can lose the lock without knowing. For data that must stay correct, it adds a number that the data itself checks, or it avoids the lock.

At SDE-2 level you should know the lock with a time limit. At SDE-3 level you should explain how it fails and give the fix.

Think of one key to a meeting room, kept at the reception. A person takes the key and the others wait. If the person leaves with the key, nobody can enter again. So reception writes "return by 4 pm". After 4 pm reception gives the key to someone else. But the first person is still inside, asleep. Now two people are in the room. A door that checks a numbered pass fixes this: the newer person has a higher number, and the door refuses the older number.

A lock across servers

A lock inside one program is easy. A distributed lock is shared by programs on many servers, so only one holds it at a time. The lock lives in a shared place: a database row or a Redis key (lesson 37). There are two reasons to use one:

• To save work. If two workers run the same job, effort is wasted. This is harmless.
• To protect data. If two workers run at once, data is damaged. This is the hard case.

The lease

Lesson 37 gave a lock with a time limit: if the holder crashes, the key ends by itself. That lock is a lease: the right to hold the lock until a set time. The holder can also extend the lease while it works. If it fails to extend, it must stop. When the holder releases the lock, it checks that the key still holds its own value, in one step (lesson 37).

The lease length is a trade-off. A long lease means that after a crash nobody can run for a long time. A short lease ends while a healthy holder is still working.

Four ways a lock fails

1. A pause. The holder checks "I hold the lock" and then freezes. The cause can be a long memory clean-up in the program, a machine that runs short of memory, or a paused virtual machine. The freeze outlasts the lease. The holder wakes up and still believes that it holds the lock. This is the gap of lesson 22 again: check, then act. Checking again just before the write does not remove it, because a pause can come right after the check.
2. A late message. The holder sends its write while the lease is valid. The network delays it, and it arrives after the lease has ended.
3. Clocks. The lock server decides when the lease ends by its own clock. Clocks differ and can jump (lesson 49). A holder should measure its own time with the monotonic clock. But no clock helps against a pause. The Redis documentation says that Redis uses the wall clock for expiry, so a clock change can let two workers hold the lock.
4. A failed lock server. One lock server is a single point of failure: if it stops, nothing can get the lock. If you add a follower, copying is asynchronous (lesson 39). The leader grants a lock and dies before copying it. The follower is promoted (lesson 41), and it grants the same lock to another worker. Now two hold it.

So a holder cannot know for sure that it still holds the lock. A lock alone cannot guarantee one writer. The data must help.

The fencing token

A fencing token is a number that grows each time the lock is granted. The data it protects remembers the highest token it has seen, and refuses a smaller one.

1. A gets the lock with token 33. A pauses.
2. The lease ends. B gets the lock with token 34 and writes. The data now remembers 34.
3. A wakes and writes with token 33. The data refuses it, because 33 is less than 34.

The check and the write must be one atomic step (lesson 22):

UPDATE totals SET amount = 42000, last_token = 33
WHERE restaurant_id = 77 AND last_token <= 33;

If 0 rows change, the holder has lost the lock and must stop. The test uses "less than or equal", so the same holder can write many times with its token.

Two conditions make this work:

• The token must never repeat. Take it from a counter that grows in one atomic step, such as a database row token = token + 1 or Redis INCR. If the counter is on an asynchronous follower, a failover can hand out the same number twice. Keep it where a write reaches a majority of copies (lesson 48), or in the database that holds the data.
• The data must check the token. A database row that you control can. A service that ignores your number cannot, for example an SMS provider. For such work, make the action safe to repeat when you can (set a value, do not add to it), or accept the rare double.

Do you need a lock at all?

A lock is often the last choice. A conditional update, a version check or a unique constraint (lesson 22) lets the database decide, with no lock to lose. A fixed rule on the key can give each key one owner (lesson 43).

SwadKart, a food app, runs a nightly job. For each restaurant it reads the day's total, adds new sales and saves the new total. Each restaurant has its own lock.

Assumptions (made up to teach with):

• The lease is 30 seconds. Most runs end in 20 seconds. 99 of every 100 runs end within 20 seconds, so the p99 of lesson 4 is 20 seconds. The slowest 1 in 100 takes 90 seconds.
• 1,000 restaurants run each night, at 2 lock grants per second.
• The token counter starts at 33. Restaurant 77 has a total of Rs 40,000.

Step 1: no fence (the predict box).

• t = 0: worker A gets the lock, token 33. At t = 5 it reads Rs 40,000 and plans to save Rs 40,000 + Rs 2,000 = Rs 42,000.
• t = 8: A checks that it holds the lock. It does, with 22 seconds left.
• t = 10: A freezes for 45 seconds.
• t = 30: the lease ends. At t = 31 worker B gets the lock, token 34. B reads Rs 40,000, adds Rs 3,000 and saves Rs 43,000 at t = 33.
• t = 55: A wakes. It does not know that its lease ended, so it saves Rs 42,000.

The final total is Rs 42,000. The true total is 40,000 + 2,000 + 3,000 = Rs 45,000. Rs 3,000 is lost, and no error appears. The check at t = 8 did not help, because the freeze came after it.

Step 2: with a fence. A's write is last_token <= 33, but the row holds last_token = 34 after B's write. 0 rows change, so A knows it lost. A takes the lock again with a new token, reads Rs 43,000, adds Rs 2,000 and saves Rs 45,000. The total is right.

Step 3: how many runs outlive the lease? 1,000 x 1% = 10 restaurants a night take 90 seconds. With a plain 30-second lease, about 10 restaurants a night get a second holder. One fix is to extend the lease while the work goes on. A common choice (our advice, not a standard) is to extend every 10 seconds, which is lease / 3. A healthy slow run keeps its lock. A frozen run stops extending, so the lock is free 30 seconds after the last extension.

Step 4: the lease length after a crash. A holder that crashes leaves its lock for at most one lease. With 30 seconds, work waits at most 30 seconds. With a 10-minute lease (600 seconds), it waits 600 / 30 = 20 times longer.

Step 5: the lock server fails over. The lock server copies asynchronously with a delay of 0.4 seconds (lesson 40). At 2 grants per second, 2 x 0.4 = 0.8 grants are not yet copied at any moment. A failover at that moment loses 0.8 grants on average, and the new leader can grant the same lock or the same token again. This is rare. It is why the counter should sit where a write reaches a majority. That costs time: a write that waits for a far copy takes 32 ms instead of 1 ms (lesson 47).

• A lease lock solves work done twice, and a lock held forever by a crashed holder. It costs safety: a pause or a failover can give two holders. I would use it alone only when a double run is harmless.
• A fencing token solves a stale holder writing late. It costs a counter that never repeats, a check inside every write, and a refusal that the holder must handle. It does not work when the data cannot check the token. I would add it whenever a double write damages data.
• No lock solves all of this when one conditional update is enough (lesson 22). It costs a rule that fits in one statement. I would try it first.
• A short lease solves fast recovery after a crash. It costs more extensions and more runs that outlive it. I would choose the lease from the slowest normal run and extend it.

"A lock with a time limit guarantees only one holder." It does not. A holder that freezes for 45 seconds keeps working after a 30-second lease. Two workers then write.

"I check that I still hold the lock just before I write, so it is safe." The check and the write are two steps. A pause between them is enough, as in the example at t = 8.

"More lock servers make the lock fully safe." More servers help when a lock server fails. One design, Redlock, asks a majority of five separate Redis servers for the lock. It still does not stop a paused holder from writing late. The Redis documentation itself says to use fencing tokens with any distributed lock.

1. Name four ways a lease lock can fail. What is a fencing token?
2. A lock has a 20-second lease. 99% of runs end in 12 seconds and the slowest 1% take 50 seconds. There are 5,000 locks a night. (a) How many runs outlive the lease? (b) A holder with token 71 freezes. Another gets token 72 and writes, so the row holds 72. What happens to the first holder's write with WHERE last_token <= 71? (c) After a crash, how long can work wait with a 20-second lease, and with a 15-minute lease? How many times longer is the second?
3. A team sends SMS reminders. A Redis lock makes sure that only one server sends them. A server freezes and a reminder is sent twice. The SMS provider cannot check tokens. What do you suggest?