Distributed Locks, Leases and Fencing Tokens: Why a Lock Is Not Enough

Version note: The code in this post was built and run with C# 14 and .NET 10.

Guess First

Bookstore's API (Application Programming Interface) runs on two instances, and both host a background job that computes the daily sales report every night and writes it to the DailySalesReport table. The team does not want the report computed twice, so it uses a lock in Redis: the job takes the lock when it starts and releases it when it is done. The lock expires on its own after a while, so if the instance running the job crashes, the lock does not hang forever.

One night instance-1 takes the lock and starts computing the report. Right then it enters a long GC (garbage collector) pause that outlasts the lock. The lock expires, instance-2 takes it, computes the report with current data and writes it. Then instance-1 wakes up. Which report is left in the table in the end? What did the lock protect here?

What Is the Lock For: Efficiency or Correctness?

In his 2016 post "How to do distributed locking", Martin Kleppmann splits the reasons for a distributed lock in two. A lock for efficiency prevents the same work from being done twice: computing the report twice costs some CPU (Central Processing Unit), a notification e-mail sent twice is a mild annoyance. If the lock occasionally fails, the cost is small. A lock for correctness prevents two processes from changing the same data concurrently and corrupting it: the same stock decremented twice, a file with two writers, an account closed twice. If the lock fails even once, the data is corrupted.

This distinction decides which tool to pick. For efficiency, a simple lock on a single Redis instance is more than enough, as long as everyone on the team knows the lock is "approximate". For correctness, as we are about to see, a lock on its own is never enough; the protected resource itself has to take part.

Leases: Locks With a Time Limit

A lock or SemaphoreSlim inside a single process disappears together with the process if its owner crashes. In a distributed lock the owner can crash and the lock can hang forever. That is why distributed locks are almost always leases: a lock granted for a certain time that expires on its own when the time is up. Gray and Cheriton's 1989 paper "Leases" defined the idea for cache consistency. In Redis you take one with a single command: SET writes the key only if it does not exist (NX) and for a given time (PX, milliseconds). For this experiment I started my own temporary Redis container:

docker run -d --rm --name ds10-redis-tmp -p 127.0.0.1:16390:6379 redis:7-alpine

$ redis-cli SET lock:daily-sales instance-1 NX PX 30000
OK
$ redis-cli SET lock:daily-sales instance-2 NX PX 30000

$ redis-cli PTTL lock:daily-sales
29999
$ redis-cli GET lock:daily-sales
instance-1

The first SET succeeds. The second returns an empty line: that is how nil looks in non-interactive redis-cli, meaning the lock was not acquired. PTTL says the lock will live for about 30 more seconds, and GET says the owner is instance-1. Releasing needs care: if you delete the lock blindly with DEL, you may delete a lock that expired while you were paused and now belongs to someone else. The right way is to compare the value and delete only if it is still yours, atomically, in a single Lua script:

using StackExchange.Redis;

namespace Bookstore.Jobs;

public sealed record Lease(string Owner, long Token);

public sealed class RedisLease(IDatabase redis, string name)
{
    // SET name owner NX PX ttl, then a fencing token from a counter
    public async Task<Lease?> TryAcquireAsync(string owner, TimeSpan ttl)
    {
        bool acquired = await redis.StringSetAsync(name, owner, ttl, When.NotExists);
        if (!acquired) return null;
        long token = await redis.StringIncrementAsync($"{name}:token");
        return new Lease(owner, token);
    }

    // Delete only if we still own it (compare-and-delete in one script)
    public async Task<bool> ReleaseAsync(Lease lease)
    {
        const string script = "if redis.call('GET', KEYS[1]) == ARGV[1] then return redis.call('DEL', KEYS[1]) else return 0 end";
        RedisResult result = await redis.ScriptEvaluateAsync(script, [name], [lease.Owner]);
        return (long)result == 1;
    }
}

A GC Pause and Two Owners

A lease brings its own problem: it expires by the lock service's clock, independently of its owner. If the owner pauses, it carries on unaware that the lock is gone. A small store that writes the report to an SQLite table:

using Microsoft.Data.Sqlite;

namespace Bookstore.Jobs;

public sealed class ReportStore(SqliteConnection db)
{
    public async Task InitAsync()
    {
        await using SqliteCommand cmd = db.CreateCommand();
        cmd.CommandText = """
            DROP TABLE IF EXISTS DailySalesReport;
            CREATE TABLE DailySalesReport (Id INTEGER PRIMARY KEY, Content TEXT NOT NULL, LastToken INTEGER NOT NULL);
            INSERT INTO DailySalesReport VALUES (1, 'empty', 0);
            """;
        await cmd.ExecuteNonQueryAsync();
    }

    public async Task<bool> SaveAsync(string content, long token, bool useFencing)
    {
        await using SqliteCommand cmd = db.CreateCommand();
        cmd.CommandText = useFencing
            ? "UPDATE DailySalesReport SET Content = $c, LastToken = $t WHERE Id = 1 AND $t > LastToken"
            : "UPDATE DailySalesReport SET Content = $c, LastToken = $t WHERE Id = 1";
        cmd.Parameters.AddWithValue("$c", content);
        cmd.Parameters.AddWithValue("$t", token);
        return await cmd.ExecuteNonQueryAsync() == 1;
    }

    public async Task<string> ReadAsync()
    {
        await using SqliteCommand cmd = db.CreateCommand();
        cmd.CommandText = "SELECT Content || ' (token ' || LastToken || ')' FROM DailySalesReport WHERE Id = 1";
        return (string)(await cmd.ExecuteScalarAsync())!;
    }
}

Let us build the scenario exactly: the lease is 1 second, instance-1 enters a 1.5-second pause right after taking the lock (we imitate it with Task.Delay), and instance-2 tries the lock after 1.1 seconds. First without fencing:

using System.Diagnostics;
using Bookstore.Jobs;
using Microsoft.Data.Sqlite;
using StackExchange.Redis;

await using ConnectionMultiplexer mux = await ConnectionMultiplexer.ConnectAsync("127.0.0.1:16390");
IDatabase redis = mux.GetDatabase();
await using SqliteConnection db = new("Data Source=reports.db");
await db.OpenAsync();
ReportStore store = new(db);
Stopwatch clock = Stopwatch.StartNew();
void Log(string text) => Console.WriteLine($"{clock.ElapsedMilliseconds,5} ms  {text}");

foreach (bool useFencing in new[] { false, true })
{
    Console.WriteLine(useFencing ? "--- with fencing token ---" : "--- lease only ---");
    await redis.KeyDeleteAsync(["lock:daily-sales", "lock:daily-sales:token"]);
    await store.InitAsync();
    RedisLease lease = new(redis, "lock:daily-sales");
    clock.Restart();

    async Task Instance1()
    {
        Lease? mine = await lease.TryAcquireAsync("instance-1", TimeSpan.FromSeconds(1));
        Log($"instance-1 acquired lease, token {mine!.Token}");
        await Task.Delay(1500); // stop-the-world GC pause longer than the lease
        bool saved = await store.SaveAsync("report from instance-1 (stale data)", mine.Token, useFencing);
        Log($"instance-1 wakes up and writes -> {(saved ? "ACCEPTED" : "REJECTED")}");
        Log($"instance-1 release -> {await lease.ReleaseAsync(mine)}");
    }

    async Task Instance2()
    {
        await Task.Delay(1100);
        Lease? mine = await lease.TryAcquireAsync("instance-2", TimeSpan.FromSeconds(1));
        Log($"instance-2 acquired lease, token {mine!.Token}");
        bool saved = await store.SaveAsync("report from instance-2", mine.Token, useFencing);
        Log($"instance-2 writes -> {(saved ? "ACCEPTED" : "REJECTED")}");
        await lease.ReleaseAsync(mine);
    }

    await Task.WhenAll(Instance1(), Instance2());
    Log($"final row: {await store.ReadAsync()}");
}

--- lease only ---
    2 ms  instance-1 acquired lease, token 1
 1105 ms  instance-2 acquired lease, token 2
 1107 ms  instance-2 writes -> ACCEPTED
 1506 ms  instance-1 wakes up and writes -> ACCEPTED
 1508 ms  instance-1 release -> False
 1511 ms  final row: report from instance-1 (stale data) (token 1)

The lock did its job: instance-2 took the lock only after the lease expired. But what is left in the table is the old report instance-1 computed before its pause. instance-2's up-to-date write was overwritten by stale data that arrived 400 milliseconds later. instance-1's ReleaseAsync returns False; compare-and-delete worked correctly, but the write had already happened. Checking "do I still hold the lock?" before writing does not help either: the pause can fall exactly between the check and the write.

GC is not the only cause of pauses. Live migration of a virtual machine, memory being swapped back in, a long synchronous disk I/O (Input/Output), a SIGSTOP sent to the process, or just the write request being held up in the network all have the same effect. Kleppmann notes that HBase had exactly this problem and that GC pauses can sometimes last minutes. In the language of the second post: a lease ties safety to timing, and in a partially synchronous system timing assumptions sometimes break.

Fencing Tokens

The fix is to bring the protected resource into the picture. Every time the lock service grants the lock, it hands out a monotonically increasing number (a fencing token). The process holding the lock sends the token with every write. The resource remembers the largest token it has seen and rejects writes with a smaller one. In the example the token is a counter incremented with INCR in Redis, and the check is a single SQL (Structured Query Language) condition: WHERE Id = 1 AND $t > LastToken. In SQL Server the same condition is written as @token > LastToken. The same scenario with fencing turned on:

--- with fencing token ---
    0 ms  instance-1 acquired lease, token 1
 1104 ms  instance-2 acquired lease, token 2
 1105 ms  instance-2 writes -> ACCEPTED
 1503 ms  instance-1 wakes up and writes -> REJECTED
 1505 ms  instance-1 release -> False
 1505 ms  final row: report from instance-2 (token 2)

instance-1 woke up again and tried to write again, but the table had seen a larger token (2); the UPDATE affected zero rows and the write was rejected. The final report is instance-2's. The strength of fencing is that it needs no timing assumption at all: however long the pause, a write with an old token does not get through.

There are two conditions. First, the token must really increase monotonically. The INCR in the example runs on a single Redis node; if Redis fails over to a replica with asynchronous replication, the last increments may be lost, the counter may go back and the same token may be handed out twice. A reliable token comes from a source replicated with consensus: zxid or a znode version in ZooKeeper, a revision in etcd, or a sequence in the same database as the protected resource. Second, the resource itself must be able to do the check. A database table, a file system or your own API can; for an external service that cannot check a token (an e-mail provider, say), fencing is not possible and you need an idempotency key there.

The Redlock Debate

Salvatore Sanfilippo (antirez), the creator of Redis, proposed the Redlock algorithm to counter the single point of failure of one Redis node: send lock requests to five independent Redis masters in turn, and if you get acknowledgements from a majority (at least three) within a short time, consider the lock acquired, with its validity reduced by the time spent.

Kleppmann's 2016 critique has two main arguments. First, Redlock does not produce fencing tokens; it uses a random value, and random values cannot be ordered. Second, its safety rests on timing assumptions: bounded network delay, bounded process pauses and bounded clock error. If one node's clock jumps forward, the lock expires early and another client can gather a majority; the pause scenario above applies just the same. Kleppmann's conclusion: for efficiency a single Redis is enough and Redlock is needlessly heavy; for correctness you need a consensus-based system such as ZooKeeper plus fencing tokens.

In his reply, "Is Redlock safe?", antirez disagreed. In his view, a resource strong enough to check tokens could also use the random lock value for a check-and-set; a pause after acquiring the lock is a problem for every lock system, not specific to Redlock; and the clock problem can be managed with a configuration that does not step the system clock back and forth and by using a monotonic clock. Reading both sides is instructive, but the practical lesson lies in what they share: a lock does not guarantee correctness on its own; the protected resource must be able to reject writes from a stale lock holder.

Coordinating Through the Database's Own Mechanisms

In most .NET applications the protected resource is already a database, and the most robust coordination happens inside it. For the report example the simplest solution can be a unique constraint: if (JobName, RunDate) is unique in a JobRuns table, only one of the two instances can insert the row for that night; the other gets a unique constraint violation and exits. For jobs that modify data, optimistic concurrency is fencing itself: SQL Server's rowversion column is a token that increases on every update, and a WHERE RowVersion = @original condition rejects a write based on a stale read. The EF (Entity Framework) Core series shows how to catch this with DbUpdateConcurrencyException in "Concurrency in EF Core: Tokens, rowversion and DbUpdateConcurrencyException".

For queue-like work, row locks are an option too: SELECT ... FOR UPDATE SKIP LOCKED in PostgreSQL and the UPDLOCK, READPAST hints in SQL Server let several workers share jobs without picking up the same one; because the lock is bound to the transaction, it is released automatically when the transaction ends or the connection drops. Whichever method you choose, as long as the write itself carries a condition (a unique key, a version, a token), the pause problem goes away. The upcoming Backend › Background Jobs and Scheduled Jobs series will cover these tools through job schedulers.

Common Pitfalls

Releasing a lock with DEL. You delete a lock that expired and passed to someone else, letting a third process take it too. Release atomically, comparing the value.

Choosing the lease length from the job's duration. "The job takes 20 seconds, 30 is enough" ignores pauses. Whatever the lease length, a longer pause is possible; if you need correctness, fencing is required.

Treating lease renewal as the fix. A background timer that renews the lease stops when the process pauses, too. Renewal keeps leases from expiring needlessly during long jobs; it does not solve the pause problem.

Trusting a resource that does not check the fencing token. Sending a token that the resource ignores is the same as not sending it. The check must be in the same atomic operation as the write.

Confusing an efficiency lock with a correctness lock. If computing the report twice is harmless, a lock is enough and fencing is needless complexity. But if data gets overwritten or processed twice, you are talking about correctness.

A Small Experiment

★☆☆ Reduce instance-1's pause from 1500 milliseconds to 800 milliseconds. In the run without fencing, what is the final row? Why?

★★☆ Add a JobRuns table with a unique constraint on (JobName, RunDate) to ReportStore. Remove the Redis lock entirely and run both instances at the same time. Which one writes the report, and which error does the other get?

★★★ Take the token from a counter table in SQLite instead of Redis (UPDATE Counters SET Value = Value + 1 RETURNING Value). How does this change fix the problem of the token going back on a Redis failover? Which new assumption does it introduce?

In this post we saw once more the cost of trusting clocks and timing. In the last post of the series we look at how real systems live with these problems: CRDTs (Conflict-free Replicated Data Types), whose merges never produce conflicts, how Spanner waits out clock uncertainty with TrueTime, CockroachDB's HLC (hybrid logical clock) and uncertainty interval, and the "documentation is not behavior" lesson from Jepsen's tests.