Designing a Distributed Lock Service: Lease-Based Coordination, Fencing Tokens, and Consensus-Backed Locking at Scale

A distributed lock sounds simple. One process holds it, the rest wait. The moment you add network partitions, process pauses, and clock drift, simple becomes subtle. Getting this wrong produces silent data corruption, not loud crashes. That is why the implementation details matter more here than in almost any other coordination primitive.

Why Single-Node Locks Break

On a single node, a mutex works because memory is shared. All threads contend on the same synchronization primitive, the operating system scheduler provides fairness, and if the process dies the lock disappears cleanly with the process.

In a distributed system, three things collapse this model:

Process pauses. A JVM garbage collection pause, a kernel swap, or a long page fault can stop a process for hundreds of milliseconds or more. During that pause, the lock’s TTL may expire. A second node acquires the lock. The first node resumes and proceeds as if it still holds the lock. Both nodes now write to the same resource.

Network partitions. The lock holder is alive, but cannot reach the storage backend. Does it still hold the lock? The node thinks yes. The storage backend says no.

Clock skew. TTL-based locks rely on wall clocks. NTP drift of even a few hundred milliseconds is enough to cause premature expiration on one node and stale extension on another.

None of these are edge cases. Every system running at scale hits all three on a long enough timeline.

Lease-Based Locking

The standard mitigation for process pauses is the lease: a lock with a fixed expiration time set at acquisition. If the holder crashes or hangs, the lease expires automatically. No explicit release is required.

A basic lease-based lock over Redis using ioredis looks like this:

import Redis from "ioredis";
import { randomUUID } from "crypto";

const client = new Redis({ host: "localhost", port: 6379 });

async function acquireLock(
  resource: string,
  ttlMs: number
): Promise<string | null> {
  const token = randomUUID();
  // SET NX PX is atomic: only sets if key does not exist, with millisecond TTL
  const result = await client.set(resource, token, "NX", "PX", ttlMs);
  return result === "OK" ? token : null;
}

async function releaseLock(resource: string, token: string): Promise<boolean> {
  // Use a Lua script to make check-and-delete atomic
  const script = `
    if redis.call("get", KEYS[1]) == ARGV[1] then
      return redis.call("del", KEYS[1])
    else
      return 0
    end
  `;
  const result = await client.eval(script, 1, resource, token);
  return result === 1;
}

The token is critical. Without it, a slow process could release a lock it no longer holds. The check-and-delete Lua script is atomic inside Redis, so the read-then-delete cannot race with another acquire.

This works well when Redis is a single instance. The problem is what happens when Redis itself fails.

The Redlock Controversy

Salvatore Sanfilippo designed Redlock to tolerate Redis node failures by acquiring the lock on a majority of N independent Redis instances. The algorithm:

1. Record the current time.
2. Attempt to acquire the lock on all N instances with a short per-node timeout.
3. If a majority (floor(N/2) + 1) granted the lock and the total elapsed time is less than the lock TTL, the lock is held.
4. To release, delete the key on all instances.

In 2016, Martin Kleppmann published a detailed critique. The core argument: Redlock does not provide the safety guarantees it claims, because it relies on timing assumptions that process pauses and clock skew can violate.

The scenario Kleppmann describes is not exotic:

1. Client 1 acquires the lock on a majority of nodes. The effective TTL is, say, 10 seconds.
2. Client 1 enters a 15-second GC pause. The lock expires across all nodes.
3. Client 2 acquires the lock on a majority of nodes.
4. Client 1 resumes, still believes it holds the lock, and writes to the shared resource.
5. Client 2 is also writing. Corruption.

Sanfilippo’s counter-argument: the scenario requires an unusually long GC pause, and in practice operators configure JVM heaps to avoid this. He also argues Redlock is designed for use cases where the lock is advisory, not for mutual exclusion on safety-critical writes.

Both are right about different things. Redlock is practical for many distributed coordination problems where occasional brief split-brain is tolerable. It is not appropriate when you need strict mutual exclusion with fencing guarantees. Understanding that boundary is the job of whoever is picking the primitive.

Fencing Tokens

The correct solution to stale lock holders corrupting shared state is to make the shared resource reject stale writes. Kleppmann’s proposal: the lock service issues a monotonically increasing fencing token with each successful acquisition. The token is passed to the resource on every write. The resource rejects writes with a token lower than the highest it has seen.

interface LockGrant {
  token: string;
  fencingToken: number; // monotonically increasing per resource
  expiresAt: number;
}

// The storage backend checks this before accepting any mutation
async function writeWithFencing(
  resourceId: string,
  data: unknown,
  fencingToken: number
): Promise<void> {
  // Pseudo-code for a database-backed resource
  const result = await db.query(
    `UPDATE resources
     SET data = $1, last_fencing_token = $2
     WHERE id = $3 AND last_fencing_token < $2`,
    [JSON.stringify(data), fencingToken, resourceId]
  );
  if (result.rowCount === 0) {
    throw new Error(
      `Stale lock holder: fencing token ${fencingToken} rejected`
    );
  }
}

etcd provides fencing tokens naturally through its revision counter. Every write to etcd increments a global revision. When you acquire a lock, you know the revision at which you won. Passing that revision to the downstream resource gives you a monotonic guard.

Redis’s Redlock does not provide fencing tokens. Each UUID token is not ordered, so the resource cannot distinguish a current holder from a stale one based on token value alone. This is the fundamental structural limitation Kleppmann identifies.

ZooKeeper: Ephemeral Sequential Nodes

ZooKeeper’s locking model is different in both mechanism and guarantees. A ZooKeeper distributed lock uses ephemeral sequential nodes:

1. Each client creates a node at /locks/resource/lock- with the EPHEMERAL and SEQUENTIAL flags. ZooKeeper appends a monotonically increasing sequence number, producing /locks/resource/lock-0000000042.
2. The client lists all children of /locks/resource/ and checks if its node has the lowest sequence number.
3. If yes, it holds the lock.
4. If no, it watches the node immediately preceding its own. When that node is deleted (because the previous holder released or crashed), it repeats from step 2.

The EPHEMERAL flag is what handles crashes. If the client’s session expires, ZooKeeper automatically deletes the ephemeral node. No TTL tuning required.

Sequence numbers are globally ordered per ZooKeeper node. This means the sequence number doubles as a fencing token. The client with sequence 42 knows it acquired the lock after the client with sequence 41. Downstream resources can use these numbers to reject stale writes.

The watch-the-predecessor pattern also avoids a thundering herd. When the current lock holder releases, only the single client watching it is notified, not every waiter.

etcd: Lease-Based Locks with Revision-Ordered Waiters

etcd takes a similar approach but built on its own primitives. A lock acquisition flow using etcd3 in TypeScript:

import { Etcd3 } from "etcd3";

const etcd = new Etcd3({ hosts: "http://localhost:2379" });

async function acquireEtcdLock(
  lockName: string,
  ttlSeconds: number
): Promise<{ lease: import("etcd3").Lease; fencingToken: number }> {
  // Create a lease that keeps the lock alive while the process is running
  const lease = etcd.lease(ttlSeconds);

  const key = `locks/${lockName}`;

  // Atomically put the key only if it does not exist (compare-and-swap)
  const txn = await etcd
    .if(key, "Create", "==", 0)
    .then(etcd.put(key).value("locked").lease(lease))
    .else(etcd.get(key))
    .commit();

  if (txn.succeeded) {
    // txn.responses[0] is the put response; its revision is our fencing token
    const header = txn.responses[0] as unknown as { header: { revision: string } };
    const fencingToken = Number(header.header.revision);
    return { lease, fencingToken };
  }

  // Lock is held by someone else: watch for deletion and retry
  await new Promise<void>((resolve) => {
    const watcher = etcd.watch().key(key).create();
    watcher.then((w) => {
      w.on("delete", () => {
        w.cancel();
        resolve();
      });
    });
  });

  // Retry after the key is deleted
  return acquireEtcdLock(lockName, ttlSeconds);
}

async function releaseEtcdLock(lease: import("etcd3").Lease): Promise<void> {
  // Revoking the lease deletes all keys attached to it
  await lease.revoke();
}

The revision number from etcd’s put response is a cluster-wide monotonically increasing integer. It serves as a natural fencing token. A downstream resource that tracks the last-seen revision can reject any write carrying an older revision.

etcd’s lease keep-alive heartbeats the lease automatically on a background interval. If the process crashes, the lease eventually expires (within ttlSeconds) and the key is deleted. If the process hangs for longer than ttlSeconds, same outcome. The risk of an overly generous TTL is the same as with Redis: a slow process may hold the lock past when the next waiter expected it.

Leader Election as a Special Case

Leader election is distributed locking with a single, stable lock and automatic re-election on failure. The pattern is identical: multiple candidates compete for one lock, the winner is the leader, losers watch and wait to retry on expiration or deletion.

The practical difference is in the application semantics. A transactional lock is held for milliseconds. A leader election lock is held until the leader crashes, voluntarily steps down, or loses its lease. The TTL must be long enough to absorb transient delays (network hiccup, brief CPU contention) but short enough to recover within an acceptable window when the leader actually fails.

A common production setup for Kubernetes-style leader election:

• TTL: 15 seconds
• Renew deadline: 10 seconds (leader must renew before this elapses)
• Retry period: 2 seconds (how often candidates poll/retry)

This gives roughly a 15-second worst-case failover window. Shorter TTLs mean faster failover but more churn from false positives.

Production Considerations

Lock granularity. Coarse locks serialize everything. A single lock on a user’s entire account blocks all concurrent operations for that user. Fine-grained locks (per-record, per-resource) allow concurrency but add coordination overhead. Design for the narrowest scope that actually prevents the conflict you are protecting against.

TTL tuning. TTL must be greater than the maximum expected lock-holder execution time under normal conditions, including tail latencies. Set it too short and healthy processes lose the lock mid-operation. Set it too long and a failed process blocks others for a long time. A rule of thumb: TTL should be at least 3x the P99 of your critical section execution time, with a floor based on your acceptable failover window.

Monitoring lock contention. Track: time-to-acquire distribution, lock hold duration, and lock acquisition failures. A spike in time-to-acquire with steady hold duration usually means more contention (more clients competing). A spike in hold duration usually means the critical section is slowing down, which could be a symptom of a downstream problem.

async function acquireWithMetrics(
  resource: string,
  ttlMs: number
): Promise<string | null> {
  const start = Date.now();
  let attempts = 0;

  while (Date.now() - start < ttlMs) {
    attempts++;
    const token = await acquireLock(resource, ttlMs);
    if (token !== null) {
      const waitMs = Date.now() - start;
      metrics.histogram("lock.wait_ms", waitMs, { resource });
      metrics.counter("lock.acquire_attempts", attempts, { resource });
      return token;
    }
    await new Promise((r) => setTimeout(r, 50 + Math.random() * 50));
  }

  metrics.counter("lock.acquire_timeout", 1, { resource });
  return null;
}

Debugging deadlocks. Distributed deadlocks are rare but real when multiple processes acquire overlapping sets of locks in different orders. Enforce a global lock ordering (sort resource names lexicographically and always acquire in that order) to eliminate circular wait. Log every lock acquisition and release with a correlation ID. When a contention spike appears, you can reconstruct the acquisition sequence from logs.

Lease renewal jitter. If many processes try to renew their leases at the same interval, they pile up on the lock backend simultaneously. Add random jitter to the renewal interval (typically 10-20% of the TTL) to spread the load.

Tradeoffs Comparison

	Redis Redlock	ZooKeeper	etcd	Consul	DB Advisory Locks
Consistency model	Approximate (timing-dependent)	Strong (ZAB consensus)	Strong (Raft consensus)	Strong (Raft consensus)	Serializable (per-session)
Fault tolerance	Majority of N nodes	Majority of ensemble	Majority of cluster	Majority of cluster	Depends on DB HA setup
Fencing tokens	No (UUIDs are unordered)	Yes (sequence numbers)	Yes (global revision)	Yes (session index)	Partial (advisory only)
Latency	Low (sub-ms on local network)	Medium (ZAB round trips)	Low-medium (Raft)	Low-medium (Raft)	Low (connection-local)
Operational complexity	Low (Redis already present)	High (JVM ensemble, ZK ops)	Medium (Kubernetes default)	Medium (Consul cluster)	Low (DB already present)
Lock expiry on crash	TTL-based	Session expiry (ephemeral)	Lease expiry	Session TTL	Session-bound (auto)
Thundering herd	Yes (all waiters poll)	No (watch predecessor)	Mitigated (watch key)	Mitigated (watch key)	Depends on driver
Sweet spot	Advisory coordination, low-stakes mutual exclusion	Strong ordering, fencing tokens, ZK already in stack	Kubernetes-native, strong fencing, control plane work	Consul already in stack	Single-database critical sections, low-volume locks

Database advisory locks (PostgreSQL’s pg_advisory_lock, MySQL’s GET_LOCK) are underused. If your critical section is already inside a database transaction and your volume is modest, they are the simplest option. They are session-scoped, so they release automatically on disconnect. They do not require a separate coordination service. The tradeoff is that you are using your primary database as a coordination service, which adds load and couples availability.

The Decision Frame

If your system already runs etcd or ZooKeeper for other purposes, use those. You get strong consistency and fencing tokens at no additional operational cost.

If you are already running Redis and your use case is advisory coordination (preventing duplicate job processing, rate-limiting coordination, cache stampede prevention), Redlock across three independent Redis instances is operationally pragmatic. Acknowledge the timing assumptions and design the protected resource to tolerate occasional split-brain if possible.

If you need strict fencing with no tolerance for split-brain, use etcd or ZooKeeper, pass the fencing token to the downstream resource, and have the resource reject stale writes. No lock service can fully protect you if the downstream resource does not also enforce ordering.

The lock service is only half the contract. The other half is in the writer.