Designing a Distributed Lock Service: Fencing Tokens, Clock Drift, and Correctness Guarantees Beyond Redlock

Distributed locks feel deceptively simple. You need exactly one process to do something at a time: process a payment, send a notification, update a shared record. The code reads like a local mutex. The failure modes do not.

The gap between “it works in development” and “it is correct in production” is where most distributed lock implementations fall apart. Clock drift makes time-based expiry unreliable. Process pauses (garbage collection, VM migration, hypervisor preemption) cause lock holders to believe they still hold a lock they lost. Network partitions let two nodes each believe they are the sole lock holder. Each of these failure modes can cause your distributed lock to provide exactly zero safety guarantees while appearing to work correctly in most cases.

This article walks through why naive implementations fail, why Redlock does not solve the hard problems, what fencing tokens actually guarantee, and how to build a lock service that is correct rather than merely convenient.

The Failure Modes

Before choosing or building a lock implementation, name the failure modes precisely. There are three that matter.

Clock drift. Time-based lock expiry assumes clocks are synchronized. They are not. NTP corrects drift, but corrections are bounded to around 0.1-1ms per correction, and adjustments do not happen continuously. Under load, a server’s clock can drift hundreds of milliseconds from wall clock time. A lock with a 500ms TTL on a server that has drifted 300ms has an effective TTL somewhere between 200ms and 800ms. You cannot reason about expiry accurately.

Process pauses. A JVM GC pause, a hypervisor stealing CPU from a VM, an OS swapping a process out: all of these can pause your process for seconds without the process being aware of the gap. A process that holds a lock, pauses for 10 seconds due to GC, then resumes will behave as if the pause did not happen. It will attempt to use the lock it held before the pause, unaware that the lock expired and another process acquired it while it was paused.

Split brain. During a network partition, different nodes can observe different state. A lock stored in a primary Redis node that becomes unreachable during a partition is invisible to clients reading from a different partition. Two clients on opposite sides of the partition can both acquire what they believe to be the lock.

These are not theoretical concerns. They are the documented failure modes that determine whether your locking strategy is correct or merely optimistic.

Why Single-Node Redis Fails

A common first implementation uses Redis with SET key value NX PX ttl to acquire a lock and DEL key to release it. This works under ideal conditions. Under failure conditions, it provides no safety guarantees at all.

// This implementation is unsafe. Do not use in production.
async function acquireLock(
  redis: Redis,
  key: string,
  ttlMs: number
): Promise<string | null> {
  const token = crypto.randomUUID();
  const result = await redis.set(key, token, "NX", "PX", ttlMs);
  return result === "OK" ? token : null;
}

async function releaseLock(
  redis: Redis,
  key: string,
  token: string
): Promise<boolean> {
  // The check-and-delete must be atomic. This Lua script prevents
  // deleting a lock owned by a different client after expiry.
  const script = `
    if redis.call("GET", KEYS[1]) == ARGV[1] then
      return redis.call("DEL", KEYS[1])
    else
      return 0
    end
  `;
  const result = await redis.eval(script, 1, key, token);
  return result === 1;
}

The Lua script for atomic check-and-delete is necessary but not sufficient. If Redis restarts before the key is persisted to disk (which requires AOF with fsync always, at a serious performance cost), the lock disappears. If the process holding the lock pauses for longer than the TTL, the lock expires and another client acquires it. Both clients now believe they hold the lock.

Single-node Redis provides mutual exclusion under ideal conditions only. It is not a correct distributed lock. It is an advisory lock with a TTL.

Redlock: Why It Does Not Solve the Problem

Antirez (Salvatore Sanfilippo) designed Redlock to address the single-node failure mode by acquiring locks on a majority quorum of independent Redis nodes. The algorithm: acquire the lock on N nodes (typically 5), use a timeout shorter than the lock TTL for each acquisition attempt, and consider the lock held only if you acquired it on a majority within the overall TTL minus clock drift buffer.

Martin Kleppmann published a detailed critique of Redlock in 2016. The critique is worth reading in full, but the core argument is this: Redlock does not handle the process pause problem, and the process pause problem is the one that actually causes safety violations.

Redlock measures clock time to determine validity. A client that acquires a Redlock lock with a 10-second TTL, pauses for 15 seconds due to GC, then resumes will believe it holds the lock while having long since lost it. Another client will have acquired it. Both clients proceed as if they have exclusive access.

Kleppmann’s point is that Redlock provides a false sense of safety. It solves the quorum problem (tolerating individual Redis node failures) without solving the correctness problem (ensuring a paused lock holder does not proceed after its lock expires).

The fix Kleppmann proposes is not a better lock algorithm. It is fencing tokens.

Fencing Tokens: The Correctness Mechanism

A fencing token is a monotonically increasing integer returned when a lock is acquired. Every operation against the protected resource must include the fencing token. The resource server rejects any request with a token lower than or equal to the highest token it has already processed.

interface LockGrant {
  token: string;     // unique identifier for this grant
  fenceToken: number; // monotonically increasing integer
  expiresAt: number; // unix ms, best-effort advisory
}

The fencing token breaks the process-pause problem:

1. Client A acquires lock, receives fence token 42.
2. Client A pauses for 15 seconds. Lock expires. Client B acquires lock, receives fence token 43.
3. Client B writes to the resource with fence token 43. Resource records highest seen token: 43.
4. Client A resumes. Attempts to write with fence token 42. Resource rejects it because 42 < 43.

The resource itself enforces safety. The lock service provides ordering. Neither component needs a perfect clock.

This requires the resource to be fence-token-aware. A database, a storage bucket, a message queue: each must implement the token check. If the resource cannot enforce fence tokens, you need a different approach.

Building a Lock Service

A production lock service needs three things: atomic acquire with a monotonically increasing token, conditional release, and TTL-based expiry for dead-client cleanup.

The fence token must come from a durable, monotonically increasing counter. A database sequence works well. Redis INCR works if you accept that a Redis restart (without persistence) can reset the counter and repeat token values. For production use, a database sequence is safer.

import { Pool } from "pg";
import crypto from "crypto";

interface LockGrant {
  lockId: string;
  fenceToken: number;
  owner: string;
  expiresAt: Date;
}

interface LockService {
  acquire(
    lockId: string,
    owner: string,
    ttlMs: number
  ): Promise<LockGrant | null>;
  release(lockId: string, owner: string): Promise<boolean>;
  renew(lockId: string, owner: string, ttlMs: number): Promise<boolean>;
}

export function createLockService(pool: Pool): LockService {
  return {
    async acquire(lockId, owner, ttlMs): Promise<LockGrant | null> {
      const client = await pool.connect();
      try {
        await client.query("BEGIN");

        // Try to insert a new lock. If one already exists and has not expired,
        // the INSERT fails due to the conflict on lock_id.
        // If the existing lock has expired, delete it first.
        await client.query(
          `DELETE FROM distributed_locks
           WHERE lock_id = $1 AND expires_at < NOW()`,
          [lockId]
        );

        // nextval guarantees monotonically increasing values per sequence,
        // even across concurrent transactions.
        const result = await client.query<LockGrant>(
          `INSERT INTO distributed_locks
             (lock_id, fence_token, owner, expires_at)
           VALUES
             ($1, nextval('distributed_locks_fence_seq'), $2, NOW() + ($3 || ' milliseconds')::interval)
           ON CONFLICT (lock_id) DO NOTHING
           RETURNING lock_id, fence_token, owner, expires_at`,
          [lockId, owner, ttlMs]
        );

        await client.query("COMMIT");

        if (result.rowCount === 0) return null;

        return {
          lockId: result.rows[0].lock_id,
          fenceToken: Number(result.rows[0].fence_token),
          owner: result.rows[0].owner,
          expiresAt: result.rows[0].expires_at,
        };
      } catch (err) {
        await client.query("ROLLBACK");
        throw err;
      } finally {
        client.release();
      }
    },

    async release(lockId, owner): Promise<boolean> {
      const result = await pool.query(
        `DELETE FROM distributed_locks
         WHERE lock_id = $1 AND owner = $2`,
        [lockId, owner]
      );
      return (result.rowCount ?? 0) > 0;
    },

    async renew(lockId, owner, ttlMs): Promise<boolean> {
      const result = await pool.query(
        `UPDATE distributed_locks
         SET expires_at = NOW() + ($3 || ' milliseconds')::interval
         WHERE lock_id = $1 AND owner = $2 AND expires_at > NOW()`,
        [lockId, owner, ttlMs]
      );
      return (result.rowCount ?? 0) > 0;
    },
  };
}

The schema:

CREATE TABLE distributed_locks (
  lock_id    TEXT PRIMARY KEY,
  fence_token BIGINT NOT NULL DEFAULT nextval('distributed_locks_fence_seq'),
  owner      TEXT NOT NULL,
  expires_at TIMESTAMPTZ NOT NULL
);

CREATE SEQUENCE distributed_locks_fence_seq START 1 INCREMENT 1;

CREATE INDEX idx_distributed_locks_expires
  ON distributed_locks (expires_at);

The resource that the lock protects needs to track and enforce the fence token:

interface ProtectedWrite {
  fenceToken: number;
  data: unknown;
}

// Stored per resource: the highest fence token successfully written.
async function writeWithFenceCheck(
  pool: Pool,
  resourceId: string,
  write: ProtectedWrite
): Promise<{ accepted: boolean; reason?: string }> {
  const result = await pool.query(
    `UPDATE protected_resources
     SET data = $3, last_fence_token = $2
     WHERE resource_id = $1
       AND ($2 > last_fence_token OR last_fence_token IS NULL)
     RETURNING resource_id`,
    [resourceId, write.fenceToken, write.data]
  );

  if ((result.rowCount ?? 0) === 0) {
    return {
      accepted: false,
      reason: "fence token too low: a newer lock holder has already written",
    };
  }

  return { accepted: true };
}

This is the critical path. Without this check, fencing tokens are useless. The lock service provides ordering; the resource enforces it.

Lock Renewal and Heartbeats

A fixed TTL creates a tradeoff: too short and legitimate lock holders lose their lock during slow operations; too long and a dead client holds the lock for too long before cleanup.

The solution is heartbeat-based renewal. The lock holder sends periodic renewals while it is active. If the process dies, renewals stop and the lock expires naturally. If the process is slow but alive, it renews successfully and keeps the lock.

async function withLock<T>(
  lockService: LockService,
  lockId: string,
  owner: string,
  ttlMs: number,
  fn: (grant: LockGrant) => Promise<T>
): Promise<T> {
  const grant = await lockService.acquire(lockId, owner, ttlMs);
  if (!grant) throw new Error(`Failed to acquire lock: ${lockId}`);

  const renewalInterval = Math.floor(ttlMs * 0.4);
  let cancelled = false;

  // Renew at 40% of TTL to give buffer before expiry.
  const renewalHandle = setInterval(async () => {
    if (cancelled) return;
    const renewed = await lockService.renew(lockId, owner, ttlMs);
    if (!renewed) {
      // Lock was lost. Signal the caller by cancelling the interval.
      // The fn() call will likely fail on its next resource write
      // due to the fence token check.
      cancelled = true;
      clearInterval(renewalHandle);
    }
  }, renewalInterval);

  try {
    return await fn(grant);
  } finally {
    cancelled = true;
    clearInterval(renewalHandle);
    await lockService.release(lockId, owner).catch(() => {
      // Ignore release errors. TTL expiry will clean up.
    });
  }
}

The renewal failure case is important: if the renewal fails, the process should stop accessing the protected resource. But since the fence token check is on the resource side, even if the process continues, the resource will reject its writes. The fence token is the final safety line.

Comparison of Approaches

Dimension	Single Redis	Redlock	ZooKeeper	etcd Leases + Fencing
Fault tolerance	None (single node)	Quorum (N/2+1)	Quorum	Quorum (Raft)
Clock dependency	High (TTL accuracy)	High (TTL across nodes)	Low (no wall clock for safety)	Low (revision numbers)
Fencing token support	No (must build externally)	No (must build externally)	Yes (zxid / ephemeral node version)	Yes (revision on key)
Correctness under process pause	No	No	Conditional (see note)	Yes (with revision-based fencing)
Operational complexity	Low	Medium	High	Medium
Latency	Sub-ms	1-5ms (5 round trips)	1-10ms	1-5ms
Best fit	Advisory locks only	Advisory locks with HA	Coordination-heavy systems	Production lock service

ZooKeeper provides ephemeral nodes and session management. When a ZooKeeper session expires (due to network partition or process death), the ephemeral node is deleted automatically. The zxid (ZooKeeper transaction ID) serves as a natural fencing token. The caveat is that session expiry takes time (session timeout, typically 2-20 seconds), so the window for a process to act on a stale lock exists. With zxid-based fencing on the resource side, safety is restored.

etcd leases expire when the client stops refreshing them (via the KeepAlive RPC). The etcd revision number on each key provides a natural fencing token. A compare-and-swap operation on the resource keyed by revision provides correctness.

Production Considerations

Lease cleanup. Expired locks must be cleaned up or they accumulate indefinitely. A background job scanning for expires_at < NOW() works, but add an index on expires_at or the scan will table-scan. Consider partitioning the locks table by expiry time if you have high lock churn.

Observability. Track: acquisition latency (p50, p99), acquisition failure rate per lock ID, renewal failure rate, and lock hold time. High hold times with renewal failures indicate a problem in the application (slow operations, process pauses). High acquisition failure rates indicate contention.

Owner identity. The owner string should include enough information to diagnose stuck locks in production: hostname, process ID, and a request trace ID. A stuck lock from worker-3.prod is debuggable; a stuck lock from uuid-abc123 is not.

Lock hierarchies. Multiple locks for coordinating different resources? Always acquire them in a consistent global order. Deadlock detection in a distributed system is genuinely hard; prevention by ordering is not.

Idempotent operations under locks. Locks reduce contention but do not eliminate it. If a lock holder crashes after writing but before releasing, the next holder will redo the operation. The protected operation should be idempotent or use a separate idempotency key to skip already-completed work.

Do not use TTL as your safety mechanism. TTL is for cleanup, not correctness. A paused process can resume after TTL expiry and attempt to write. If your safety depends on TTL accuracy, you do not have a correct distributed lock. Use fencing tokens.

When to Use a Distributed Lock

Distributed locks are appropriate when:

• You need exactly-once execution semantics for an operation across multiple process instances.
• The protected resource supports fence-token enforcement (or you can add it).
• The operation duration is bounded and shorter than your lease TTL.

Distributed locks are the wrong tool when:

• You need high-throughput coordination. At that scale, you want conflict-free data structures or partitioning, not serialization through a lock service.
• The protected operation is unbounded in duration. A lock with no upper bound on hold time is a potential deadlock waiting for a network partition.
• You are using the lock to coordinate state that belongs in a database transaction. Serializable transactions already provide the isolation you need. Adding a distributed lock on top introduces complexity without safety benefit.

Correctness in distributed systems is not about finding the right lock algorithm. It is about building systems where each component enforces its own invariants. The lock service provides ordering. The resource enforces it. Neither component trusts the other to get timing right.

Start with a database-backed lock service with fence tokens. Add a faster cache layer (Redis) for the hot path only after you have confirmed the fence token enforcement path works end to end. The database is slow compared to Redis, but it is correct. Build correct first, then optimize.