# System Design Interview: Design a Distributed Lock and Leader Election System

Source: https://www.techinterview.org/post/3233462760/system-design-distributed-lock-leader-election/
Updated: 2026-04-17 · techinterview.org

## What Is a Distributed Lock?

A distributed lock ensures that only one node in a cluster executes a critical section at a time. Unlike a mutex within a single process, a distributed lock must work across multiple machines that can fail independently. The core challenge: what happens if the lock holder dies without releasing the lock? The system must detect failure and release the lock automatically.

Use cases: exactly-one job scheduler (only one node runs the cron job), leader election (one node is primary for writes), distributed rate limiting across API gateway nodes, preventing double-payments in financial systems.

- [Netflix Interview Guide](https://techinterview.org/netflix-software-engineer-interview/)

- [Airbnb Interview Guide](https://techinterview.org/airbnb-software-engineer-interview/)

- [Databricks Interview Guide](https://techinterview.org/databricks-interview-guide/)

- [Coinbase Interview Guide](https://techinterview.org/coinbase-software-engineer-interview/)

- [Uber Interview Guide](https://techinterview.org/uber-software-engineer-interview/)

- [Stripe Interview Guide](https://techinterview.org/stripe-software-engineer-interview/)

## Key Properties of a Distributed Lock

  - **Mutual exclusion**: at most one holder at any time

  - **Deadlock-free**: a lock must be releasable even if the holder crashes (use TTL)

  - **Fault-tolerant**: lock service stays available if some nodes fail

  - **No false releases**: a lock holder must not accidentally release another holder's lock (use fencing tokens)

## Redis-based Lock

Use Redis SET NX EX (set if not exists, with expiry):


```
token = uuid4()
acquired = redis.set(lock_key, token, nx=True, ex=30)  # 30s TTL

# Release atomically via Lua script executed on Redis server
lua = 'if redis.call(get,KEYS[1])==ARGV[1] then return redis.call(del,KEYS[1]) else return 0 end'
redis.run_script(lua, 1, lock_key, token)
```

The UUID token prevents a crashed holder's lock from being released by a new holder. The Lua script makes check-and-delete atomic.

## Redlock Algorithm (Multi-Node Redis)

Redlock uses N=5 independent Redis nodes. To acquire:

  - Record current time T1

  - Try to acquire the lock on all N nodes with a short timeout (50ms per node)

  - If majority (N/2+1=3) grant the lock and elapsed time < lock TTL, lock is acquired

  - Effective TTL = initial TTL minus elapsed time minus clock drift margin

  - If no majority: release on all nodes and retry with backoff

**Controversy**: Redlock has safety issues with clock drift and GC pauses. Use Redlock for efficiency (preventing duplicate work), not for correctness (preventing data corruption). For correctness, use ZooKeeper or etcd.

## ZooKeeper Ephemeral Sequential Nodes

  - Each client creates an ephemeral sequential node: /locks/mylock-0000000001, etc.

  - Client checks if its node has the lowest sequence number. If yes: lock acquired.

  - If not: watch the node with the next-lowest number. When deleted, re-check.

  - Ephemeral nodes deleted automatically when the client session expires. No TTL management needed.

Fair queue: clients acquire in order of arrival. Watching the previous node prevents the thundering herd problem.

## etcd Leader Election

  - All nodes attempt PUT /election/leader with a lease (TTL). Only one succeeds (Raft consensus).

  - The winner is leader. It must renew the lease before expiry (keepalive).

  - Followers watch /election/leader. On deletion, all race to acquire. One wins.

  - Fencing token: etcd returns a monotonically increasing revision number. Protected resources reject writes with a lower revision than already seen.

## Fencing Tokens

Problem: leader holds lock, gets GC-paused for 40s, lock expires, new leader elected, old leader resumes and thinks it still holds the lock. Without fencing, two leaders operate simultaneously.

Solution: every lock grant includes a fencing token (epoch number). Protected resources reject writes from any holder with a lower token. Old leader writes are rejected automatically.

## Interview Framework

  - What is the lock protecting? Correctness (etcd/ZooKeeper) vs. efficiency (Redis)?

  - What is the lock TTL? How long can the operation take?

  - What happens if the holder fails? TTL-based release vs. ephemeral session expiry.

  - Fencing tokens: how does the protected resource reject stale lock holders?

  - What if the lock service fails? Redlock vs. single Redis.