Distributed Locking & Idempotency

1. What Is It?

Distributed locking is the mechanism for ensuring that only one process across a distributed system performs a critical operation at a time. Without distributed locks, race conditions lead to data corruption: two servers simultaneously decrementing inventory both read "1 item left," both decide to sell it, and you end up oversold.

Idempotency is the property of an operation that can be applied multiple times with the same result as applying it once. In distributed systems, retries are unavoidable (network timeouts, transient failures), so every state-mutating operation needs to be safe to retry. An idempotent "charge customer" operation charges exactly once even if the client sends the request three times due to timeout and retry.

These two patterns are complementary: distributed locks prevent concurrent writes to shared state; idempotency makes retried writes safe.

2. How It Works

Distributed Locking

Option 1: Redis-Based Locking (Redlock)

Designed by Salvatore Sanfilippo ("Antirez"), the Redlock algorithm provides distributed locking using N independent Redis master nodes (no replication between them — typically 5).

Lock acquisition:

1. Get current timestamp T1
2. For each of N Redis nodes, attempt:
   SET resource_key <unique_random_value> NX PX <ttl>
   (with a short per-node timeout: 5–50ms)
3. Count successful SETs
4. Lock is HELD if:
   - Acquired on N/2+1 (majority, e.g., 3 of 5) nodes
   - AND (current_time - T1) < lock_ttl
   Effective lock time = ttl - (current_time - T1)
5. On failure: release all partially-acquired locks immediately

Lock release (atomic via Lua):

Copy
-- Only delete if the value matches our random value
if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
else
    return 0
end

The Redlock controversy: Martin Kleppmann's 2016 critique raised two key objections:

1. No fencing tokens: Redlock cannot generate monotonically increasing tokens, so it cannot prevent a paused client from writing after its lease expires (see Fencing Tokens below)
2. Unsafe timing assumptions: GC pauses, NTP clock jumps, and network delays can all cause a client to believe it holds the lock after the TTL has passed

Community consensus: Use Redlock for advisory locks (efficiency — prevent double-work when eventual correctness is acceptable). Do NOT use it for correctness-critical operations without a separate fencing mechanism.

Option 2: ZooKeeper Ephemeral Nodes

ZooKeeper provides a consensus-based (CP) distributed lock using ephemeral sequential znodes:

Parent path: /locks/resource_X

Each client creates: /locks/resource_X/lock_0000000003 (sequential, ephemeral)

Lock protocol:
1. Client creates sequential ephemeral znode under /locks/resource_X
2. Client reads all children and sorts by sequence number
3. If client's node has the LOWEST sequence number → lock ACQUIRED
4. Otherwise → watch the node immediately preceding in sequence
5. When the predecessor is deleted (lock released or session expired):
   → ZooKeeper notifies the watcher
   → Client checks again if it now has the lowest number

Why ephemeral: If the lock holder crashes, its ZooKeeper session eventually times out, and ZooKeeper automatically deletes the ephemeral node. No deadlock from crashed processes — zero manual cleanup.

Why watch predecessor only (not all): Prevents the "herd effect" — if all clients watch the root node, every lock release wakes up all waiting clients. Watching only the predecessor means each release wakes exactly one client.

Key advantage over Redlock: ZooKeeper's sequential node numbers are monotonically increasing — they serve naturally as fencing tokens.

Fencing Tokens: Why Locks Alone Aren't Enough

Problem scenario without fencing tokens:

t=0:   Client A acquires lock (TTL: 30s)
t=20s: Client A pauses (GC stop-the-world)
t=30s: Lock TTL expires
t=31s: Client B acquires the lock
t=31s: Client B writes to database (correct, lock held)
t=45s: Client A resumes — still thinks it holds the lock
t=45s: Client A writes to database (WRONG — overwrites B's correct data)

Fencing tokens solve this:

t=0:   Client A acquires lock, receives token=42
t=31s: Client B acquires lock, receives token=43
t=31s: Client B writes to DB with token=43. DB records: max_seen_token=43
t=45s: Client A resumes, tries to write to DB with token=42
t=45s: DB rejects: 42 < 43 (stale token) → Write rejected safely

How to get monotonically increasing tokens:

• ZooKeeper sequential znode numbers (natural fit)
• Database sequence (e.g., PostgreSQL nextval)
• etcd lease revision numbers

Mermaid: Distributed Locking with Fencing

-+ResetFullscreen

Optimistic vs Pessimistic Locking

Optimistic locking implementation:

Copy
-- Read the record with its version
SELECT id, quantity, version FROM inventory WHERE product_id = 42;
-- quantity=1, version=7

-- Perform business logic in application code
-- ...

-- Write back with version check (compare-and-swap)
UPDATE inventory
SET quantity = 0, version = version + 1
WHERE product_id = 42 AND version = 7;
-- If 0 rows affected: conflict detected → retry from the top

Compare-and-Swap (CAS): The atomic hardware primitive behind optimistic locking. Redis's SET key value NX (set if not exists) is CAS; DynamoDB's conditional writes (attribute_not_exists(pk)) are CAS. The principle: read-check-write as a single atomic operation.

Idempotency

Idempotency Keys

An idempotency key is a unique token the client generates per logical operation and includes with every request. The server stores the key → response mapping. On retry, the server returns the cached response instead of re-executing.

-+ResetFullscreen

Stripe's implementation:

• All POST endpoints accept Idempotency-Key header (recommended: V4 UUID)
• Keys expire after 24 hours
• Stores both successful and error responses
• Safe to retry on: connection failure, mid-operation crash, response timeout

Key generation rule: The idempotency key must be unique per logical operation. If the customer retries "buy item X at time T", that's the same operation — same key. If they place a new order later, that's a different operation — different key.

Idempotent Database Operations

PostgreSQL upsert (available since v9.5):

Copy
-- Idempotent insert: skip if already exists
INSERT INTO orders (order_id, user_id, total)
VALUES ('ord_123', 'usr_456', 99.00)
ON CONFLICT (order_id) DO NOTHING;

-- Idempotent upsert: update on conflict
INSERT INTO user_settings (user_id, theme)
VALUES ('usr_456', 'dark')
ON CONFLICT (user_id) DO UPDATE SET theme = EXCLUDED.theme;

DynamoDB conditional write:

Copy
table.put_item(
    Item={'pk': 'order_123', 'user_id': 'user_456', 'total': 99},
    ConditionExpression='attribute_not_exists(pk)'
    # Only writes if order_123 doesn't already exist
    # On retry: ConditionCheckFailedException (safe to ignore)
)

Message Delivery Semantics

Kafka exactly-once (v0.11+):

1. Idempotent producer: Broker assigns each producer a PID + sequence number. Duplicate sends (same PID + seq) are deduplicated at the broker.
2. Transactional producer: Atomic writes across partitions/topics. Consumers with isolation.level=read_committed only see committed transactions.

SQS FIFO deduplication: Messages with the same MessageDeduplicationId sent within a 5-minute window are deduplicated. Uses either content-based (SHA-256 of body) or explicit ID mode.

Two-Phase Locking (2PL) — Database Serializability

2PL is the database engine's mechanism for enforcing serializable transactions (used in PostgreSQL, MySQL InnoDB, Oracle, SQL Server):

Phase 1 (Expanding/Growing):
  Transaction can ACQUIRE locks (shared or exclusive)
  Transaction CANNOT release any lock

Phase 2 (Shrinking):
  Transaction can RELEASE locks
  Transaction CANNOT acquire new locks

In practice (Strict 2PL):
  All locks released atomically at COMMIT or ROLLBACK

The key insight: the order of "lock points" (the moment the last lock is acquired) across transactions defines the serialization order. No transaction can acquire a new lock after releasing one, so lock points don't interleave — producing a conflict-serializable schedule.

Deadlock example and detection:

T1 holds lock on Row A, waits for Row B
T2 holds lock on Row B, waits for Row A
→ Deadlock

Detection: wait-for graph (find cycles)
Resolution: abort one transaction (typically the younger one or the one with less work done)

3. Variants & Comparisons

Distributed Lock Implementations

4. When to Use It (and When NOT To)

Use Distributed Locks When:

• Leader election: Elect one worker from a pool of identical workers to run a cron job (prevent duplicate execution). Use ZooKeeper or etcd, not Redis.
• Preventing double-execution of expensive operations: Image resizing, email sending, batch jobs. Redis Redlock is fine here — at-most-once execution is the goal, and occasional failures are acceptable.
• Coordinating access to shared external resources: Updating a file in S3, calling a third-party API with strict rate limits.

Use Idempotency When:

• All mutating API endpoints: Any POST/PUT/DELETE that clients might retry. API design rule: every state-changing endpoint should accept and honor an idempotency key.
• Payment and financial operations: Stripe's approach — generate an idempotency key per payment intent, retry safely on network failure.
• Message queue consumers: Assume at-least-once delivery. Make every consumer handler idempotent: INSERT ... ON CONFLICT DO NOTHING, conditional DynamoDB writes, or check-before-write.

Anti-Patterns:

• Using Redlock for strong correctness guarantees: "I won the Redlock, so my write is safe" is false. A GC pause after acquiring the lock can expire the lease. Always combine with fencing tokens or use ZooKeeper.
• Not setting a TTL on distributed locks: A process that crashes without releasing a lock will deadlock all other processes waiting for it forever. Always set an appropriate TTL.
• Assuming retry = idempotent without implementing it: Retrying a non-idempotent operation (no idempotency key, no CAS check) causes duplicate charges, double inserts, or double sends.
• Using pessimistic locks for read-heavy operations: SELECT FOR UPDATE on a table that's 90% reads will lock out all readers under high traffic. Use MVCC (PostgreSQL default) or optimistic locking instead.

5. Real-World Usage

Stripe — Idempotency Keys for Payment APIs

Stripe's payment API is idempotent by design. Every POST endpoint (create charge, create payment intent, issue refund) accepts an Idempotency-Key header. Clients are expected to generate a unique UUID per logical payment attempt and retry on failure with the same key. Stripe stores the key → response mapping for 24 hours. This design means: no matter how many times a client retries due to network timeouts, each customer is charged exactly once. Stripe also uses exponential backoff + jitter in their retry recommendations to prevent thundering herd.

Amazon SQS FIFO — Deduplication for Exactly-Once Processing

SQS Standard queues deliver at-least-once — the same message can be delivered multiple times. SQS FIFO queues add a 5-minute deduplication window: messages with the same MessageDeduplicationId sent within 5 minutes are deduplicated at the queue level. This shifts the exactly-once guarantee from the consumer to the infrastructure. Producers sending order events use the order ID as the deduplication ID — even if the producer crashes and retries, only one order event is enqueued.

Kubernetes — etcd Distributed Locking

Kubernetes uses etcd (Raft-based) for all distributed coordination: leader election for controller managers, coordination during rolling deployments, and storing all cluster state with optimistic concurrency control (resource version numbers). etcd's revision numbers serve as natural fencing tokens — all Kubernetes resource updates include a resourceVersion that must match the current version in etcd for the write to succeed (compare-and-swap). This prevents split-brain and stale writes in the control plane.

6. Interview Cheat Sheet

5 Sentences to Show Deep Understanding

1. "Distributed locks based on TTL (Redis Redlock, ZooKeeper ephemeral nodes) have a fundamental vulnerability: a process can be paused longer than the lease duration, resume believing it holds the lock, and corrupt data. Fencing tokens solve this by having the lock service issue a monotonically increasing token that the storage layer enforces — stale tokens are rejected regardless of what the client believes."

2. "Idempotency is non-optional in distributed systems because retries are unavoidable. Every mutating operation that a client might retry must be safe to apply multiple times: at the API layer via idempotency keys, at the database layer via INSERT ON CONFLICT DO NOTHING or conditional writes, and at the message consumer layer via idempotent message handlers."

3. "The practical choice between Redis Redlock and ZooKeeper for distributed locking comes down to correctness vs. simplicity: Redlock is easier to operate (you already have Redis) but only provides advisory locks — if your application requires correctness under all failure scenarios, ZooKeeper's sequential ephemeral znodes with ZAB consensus is safer."

4. "Optimistic locking (version-based compare-and-swap) outperforms pessimistic locking (SELECT FOR UPDATE) under low contention because it avoids the lock wait entirely — multiple readers can proceed in parallel, and conflicts are only detected and handled at write time."

5. "Kafka's exactly-once semantics (v0.11+) combines idempotent producers (per-PID sequence number deduplication at the broker) with transactional writes (atomic multi-partition commits) — this moves the exactly-once guarantee from the application layer to the infrastructure layer, but consumers must still use isolation.level=read_committed to see only committed data."

Common Follow-Up Questions

Q: Why can't you use a single Redis node for a distributed lock instead of Redlock? A: If the Redis primary fails after writing the lock key but before replicating to the secondary, the secondary promotes and has no record of the lock. A second client can then acquire the same lock — two clients hold the lock simultaneously. Redlock uses N independent Redis primaries (no replication between them) to ensure that acquiring a majority requires the key to exist on N/2+1 independent nodes; losing one node doesn't lose the lock key.

Q: How would you implement a distributed rate limiter that counts exactly once across 10 servers? A: Two approaches: (1) Redis INCR + EXPIRE with a Lua script for atomic check-and-increment (shared counter across all servers); (2) a distributed counting system like HyperLogLog for approximate counting at massive scale. The Redis approach gives exact counts but adds one round-trip latency per request. The right tradeoff depends on whether the exact count matters (payment quotas → yes; analytics → approximate is fine).

Q: What is the difference between a distributed lock and a database transaction? A: A database transaction provides ACID guarantees within a single database cluster — all operations in the transaction are atomic, isolated, and durable within that database. A distributed lock is for coordinating access to any shared resource across multiple services that don't share a database, or for operations that span multiple systems. If all your shared state is in one database, use transactions and SELECT FOR UPDATE instead of a distributed lock — they're stronger and simpler.

Q: How do you handle idempotency for a multi-step operation? A: Use a distributed saga with idempotency at each step. Each step has its own idempotency key (e.g., {parent_key}:step1, {parent_key}:step2). If the saga is retried from the beginning, completed steps return their cached results immediately. If a step fails, the saga executes compensating transactions (reverse the completed steps) before retrying. Stripe's idempotency blog describes exactly this pattern for their multi-step payment flows.

Connections to Other Building Blocks

• Consensus (Raft/Paxos): ZooKeeper (ZAB) and etcd (Raft) use consensus to provide the strong consistency guarantees that make their distributed locks safe. Redlock does not use consensus — that's why it's less safe.
• Message Queues (Kafka/SQS): At-least-once delivery requires idempotent consumers. Kafka's exactly-once producer semantics reduce but don't eliminate the need for idempotent message processing.
• CAP Theorem: CP systems (ZooKeeper, etcd) are appropriate for distributed locks when correctness matters. AP systems (Redis) are appropriate for advisory locks where occasional failures are acceptable.
• Replication Strategies: Redlock's insistence on N independent Redis masters (not replicas) is a direct consequence of the CAP theorem — async replication creates windows where the lock key is not yet visible on a new primary after failover.
• Rate Limiter: The Redis-based rate limiter building block uses atomic Lua scripts — the same concurrency control technique as distributed locks applied to counter operations.