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

By /

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
  • Airbnb Interview Guide
  • Databricks Interview Guide
  • Coinbase Interview Guide
  • Uber Interview Guide
  • Stripe Interview Guide

    • 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:

    1. Record current time T1
    2. Try to acquire the lock on all N nodes with a short timeout (50ms per node)
    3. If majority (N/2+1=3) grant the lock and elapsed time < lock TTL, lock is acquired
    4. Effective TTL = initial TTL minus elapsed time minus clock drift margin
    5. 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

    1. Each client creates an ephemeral sequential node: /locks/mylock-0000000001, etc.
    2. Client checks if its node has the lowest sequence number. If yes: lock acquired.
    3. If not: watch the node with the next-lowest number. When deleted, re-check.
    4. 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

    1. All nodes attempt PUT /election/leader with a lease (TTL). Only one succeeds (Raft consensus).
    2. The winner is leader. It must renew the lease before expiry (keepalive).
    3. Followers watch /election/leader. On deletion, all race to acquire. One wins.
    4. 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

    1. What is the lock protecting? Correctness (etcd/ZooKeeper) vs. efficiency (Redis)?
    2. What is the lock TTL? How long can the operation take?
    3. What happens if the holder fails? TTL-based release vs. ephemeral session expiry.
    4. Fencing tokens: how does the protected resource reject stale lock holders?
    5. What if the lock service fails? Redlock vs. single Redis.

    {
    “@context”: “https://schema.org”,
    “@type”: “FAQPage”,
    “mainEntity”: [
    {
    “@type”: “Question”,
    “name”: “What is the difference between Redis locks and ZooKeeper/etcd for distributed locking?”,
    “acceptedAnswer”: { “@type”: “Answer”, “text”: “Redis distributed locks (SET NX EX) are simple and fast but provide weaker guarantees: single-node Redis is a single point of failure; clock drift and GC pauses can cause a lock holder to believe it holds the lock after TTL expiry. Redlock (5-node Redis quorum) addresses availability but remains controversial for correctness. ZooKeeper and etcd use consensus protocols (Paxos and Raft) with stronger guarantees: lock state is replicated to a quorum before acknowledging; ZooKeeper ephemeral nodes auto-delete on session expiry without TTL drift; etcd provides monotonically increasing revision numbers as fencing tokens. Rule: use Redis for efficiency (preventing duplicate work where occasional failures are tolerable); use ZooKeeper/etcd for correctness (preventing data corruption — financial systems, database leader election).” }
    },
    {
    “@type”: “Question”,
    “name”: “What is a fencing token and why is it critical for distributed locks?”,
    “acceptedAnswer”: { “@type”: “Answer”, “text”: “A fencing token is a monotonically increasing number returned with each lock grant. When the lock holder writes to a protected resource, the resource checks that the token exceeds the last seen value and rejects stale requests. The problem it solves: a lock holder gets GC-paused, its TTL expires, a new holder gets a higher token and proceeds, and then the original resumes believing it still holds the lock. Without fencing, two processes write simultaneously (split-brain). With fencing, the old holder is rejected because its token is lower. ZooKeeper zxid and etcd revision numbers serve as fencing tokens. Redis does not natively provide one — you must atomically increment an external counter and include it in the lock value.” }
    },
    {
    “@type”: “Question”,
    “name”: “How does leader election work using ZooKeeper ephemeral sequential nodes?”,
    “acceptedAnswer”: { “@type”: “Answer”, “text”: “Each candidate creates an ephemeral sequential znode under a common path, e.g., /election/candidate-0000000001. ZooKeeper guarantees globally unique monotonically increasing sequence numbers. Each client reads all children, checks if its node has the smallest sequence number — if yes, it is leader. If not, it watches the next-lowest node and waits. When the watched node is deleted (holder crashed, ephemeral node auto-deleted on session expiry), the watcher is notified and re-checks. This creates a fair queue — leadership passes in arrival order. Key properties: (1) ephemeral nodes auto-delete on crash — no stale locks, (2) watching the previous node prevents thundering herd, (3) sequence number serves as a natural fencing token.” }
    }
    ]
    }

    Scroll to Top