Bird
Raised Fist0

Why Distributed Locks Are Needed and Why They Are Hard to Get Right

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Why Distributed Locks Are Needed and Why They Are Hard to Get Right
Understanding the necessity and complexity of distributed locks in large-scale systems
mediumDistributed CoordinationFreq: common
⚙️
Functional Requirements
  • Provide a mechanism to acquire and release locks across multiple distributed clients
  • Ensure mutual exclusion: only one client can hold a lock at a time
  • Support lock expiration or TTL to avoid deadlocks due to client failures
  • Allow clients to renew locks to extend ownership safely
  • Provide strong consistency guarantees to prevent split-brain scenarios
  • Expose APIs for lock acquisition, release, and status queries
📊
Non-Functional Requirements
  • Support at least 1 million lock operations per second (acquire/release) at peak
  • Achieve 99.99% availability with failover and recovery mechanisms
  • Ensure lock acquisition latency under 50ms P99 to avoid client timeouts
  • Handle network partitions gracefully without violating mutual exclusion
  • Scale horizontally to support 10x growth without redesign
❓
Clarifying Questions to Ask
  • What is the expected lock granularity (e.g., per resource, per user)?
  • Are locks reentrant or non-reentrant?
  • What is the expected lock TTL or expiration policy?
  • Is strong consistency or eventual consistency acceptable for locks?
  • What are the failure scenarios we must tolerate (e.g., client crash, network partition)?
  • Should the system support lock queuing or just immediate acquisition?
Out of Scope
✗ Implementing distributed consensus algorithms from scratch (e.g., Paxos internals)
✗ Designing client-side retry/backoff strategies in detail
✗ Lock usage patterns or business logic beyond locking primitives
✗ Security and authentication mechanisms for clients
📌
Assumptions
  • 1 million distributed clients concurrently acquiring locks
  • Each client performs 10 lock operations (acquire/release) per minute
  • Average lock metadata size is 200 bytes per lock
  • Lock TTL is 30 seconds on average
⚡
QPS Calculation
write qps1,000,000 clients × 10 ops/min ÷ 60 ≈ 166,667 ops/sec
peak write qpsAssuming 2× peak factor → 166,667 × 2 = 333,334 ops/sec
read qpsLock status queries assumed at 20% of write ops → 0.2 × 333,334 = 66,667 ops/sec
💾
Storage Estimate
daily storage333,334 ops/sec × 200 bytes × 86400 sec ≈ 5.76 TB/day
retention days1
with replication5.76 TB × 3 replicas = 17.28 TB/day
🖥️
Server Estimate
lock service nodesAssuming each node handles 10,000 ops/sec → 333,334 ÷ 10,000 = 34 nodes
storage nodesAssuming Cassandra nodes with 1 TB usable storage → 17.28 TB ÷ 1 TB = 18 nodes
🏗️
Architecture Diagram
Architecture Diagram
       +-------------+
       | Distributed |
       |   Clients   |
       +------+------+
              |
              v
       +------+-------+
       | Lock Service |
       |  (Redis +   |
       |  Redlock)   |
       +------+-------+
              |
              v
       +------+-------+
       |  Metadata    |
       |  Store       |
       | (Apache      |
       |  Cassandra)  |
       +--------------+
🧩
Components
Distributed Clients
Request lock acquisition and release; handle retries and TTL renewals
Why thisClients initiate lock requests and must handle failures gracefully
Why notNot a component choice but critical to clarify client responsibilities
Lock Service (Redis with Redlock algorithm)
Coordinates distributed locks with strong consistency and TTL enforcement
Why thisRedis supports fast in-memory operations with TTL; Redlock algorithm provides fault-tolerant distributed locking
Why notZooKeeper rejected due to higher latency and complexity at 333K ops/sec; etcd rejected for similar reasons
Metadata Store (Apache Cassandra)
Persist lock ownership metadata and history for audit and recovery
Why thisCassandra scales linearly for writes at high QPS and provides tunable consistency
Why notPostgreSQL rejected due to write bottlenecks at 333K ops/sec; MongoDB rejected for weaker consistency guarantees
Load Balancer
Distributes client lock requests evenly across Lock Service nodes
Why thisEnsures even load distribution and fault tolerance at scale using technologies like HAProxy or Envoy
Why notDNS round-robin rejected due to lack of health checks and uneven load distribution
Monitoring & Alerting System
Tracks lock service health, latency, and failure rates to trigger alerts
Why thisCritical for maintaining 99.99% availability and detecting deadlocks or split-brain using Prometheus and Grafana
Why notManual monitoring rejected due to scale and latency requirements; automated monitoring tools preferred
🔄
Data Flow
1
Distributed Client → Load Balancer
Client sends lock acquisition request
Load balancer routes request to healthy Lock Service node
2
Load Balancer → Lock Service (Redis)
Lock Service attempts to acquire lock using Redlock algorithm
Uses multiple Redis instances with TTL to ensure fault tolerance
3
Lock Service → Metadata Store (Cassandra)
Persist lock ownership metadata asynchronously
Ensures durable record of lock state for recovery and audit
4
Lock Service → Distributed Client
Respond with lock acquisition success or failure
Includes lock TTL and ownership info
5
Distributed Client → Lock Service
Client renews or releases lock before TTL expiry
Prevents deadlocks and extends lock ownership safely
6
Monitoring System → Operations Team
Alerts on lock service latency spikes or failures
Enables rapid incident response to maintain availability

Practice

(1/5)
1. A high-traffic web application experiences multiple clients simultaneously requesting the same expired cache key, causing a sudden spike in backend load. Which component or strategy best prevents this thundering herd problem?
easy
A. Implement a distributed lock or mutex around cache regeneration
B. Use a simple cache with a short TTL to ensure freshness
C. Increase backend server capacity to handle peak load
D. Use a CDN to cache all dynamic content indefinitely

Solution

  1. Step 1: Identify the cause of thundering herd

    Multiple clients request the same expired cache key simultaneously, causing backend overload.

  2. Step 2: Evaluate prevention strategies

    Distributed locks or mutexes ensure only one client regenerates the cache, preventing backend overload.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Distributed locking serializes cache regeneration, preventing thundering herd [check]
Hint: Distributed locks serialize cache rebuilds to prevent stampedes [OK]
Common Mistakes:
2. A high-throughput messaging system must decouple 1 million writes per second from fan-out delivery to thousands of clients. Which component best handles this decoupling to ensure durability and scalability?
easy
A. Use a distributed log system like Kafka partitioned by conversation ID
B. Use a relational database with row-level locking to queue messages
C. Use Redis as an in-memory queue with TTL for message expiration
D. Use direct synchronous HTTP calls from sender to all recipients

Solution

  1. Step 1: Identify the decoupling requirement

    Relational DB with row-level locking (Use a relational database with row-level locking to queue messages) cannot handle 1M writes/sec due to locking and durability overhead. Redis (Use Redis as an in-memory queue with TTL for message expiration) lacks durability guarantees and TTL causes message loss risk. Direct synchronous calls (Use direct synchronous HTTP calls from sender to all recipients) block sender and don't scale.

  2. Step 2: Evaluate Kafka's suitability

    Kafka partitions by conversation ID ensure ordering and durability, enabling scalable fan-out with consumer groups.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Kafka partitions -> durable, scalable decoupling [check]
Hint: Distributed logs decouple writes and fan-out reliably [check]
Common Mistakes:
3. In a Count-Min Sketch system, at step 3 the Update Worker hashes an incoming event key with the second hash function. What happens to the corresponding counter in the sketch at this step?
easy
A. The counter is reset to zero before incrementing
B. The counter at the hashed index is incremented by one
C. The counter is decremented to avoid overcounting
D. The counter is replaced with the maximum of current and new value

Solution

  1. Step 1: Understand Update Worker hashing

    Each hash function maps the event key to an index in the sketch array.

  2. Step 2: Increment counter at hashed index

    The Count-Min Sketch increments the counter at that index to record the event occurrence.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Update increments counters at hash indices to track frequencies [check]
Hint: Update increments counters at hash indices, never resets or decrements [check]
Common Mistakes:
4. A system requires handling 1 million writes per second with guaranteed durability and ordered processing per user session. Which database technology best fits this requirement?
easy
A. Use a distributed log-based system like Kafka partitioned by user session
B. Use a relational database with row-level locking to ensure order and durability
C. Use an in-memory key-value store like Redis without persistence enabled
D. Use a NoSQL document store with eventual consistency and no ordering guarantees

Solution

  1. Step 1: Identify ordering and durability needs

    Relational DBs with row-level locking can't handle 1M writes/sec efficiently; Redis without persistence loses durability; NoSQL eventual consistency lacks ordering guarantees.

  2. Step 2: Recognize Kafka's partitioning for ordering

    Kafka partitions by user session ensure ordered processing and durability at high throughput.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Kafka partitions -> ordered, durable, high-throughput writes [check]
Hint: Kafka partitions preserve order and durability at scale [check]
Common Mistakes:
5. A large-scale key-value store needs to quickly filter out non-existent keys before querying a slow backend database. Which component best handles this filtering to reduce backend load?
easy
A. Use a Bloom filter to probabilistically test key existence before backend query
B. Use a relational database index to speed up key lookups
C. Use a distributed cache like Redis to store all keys for exact lookup
D. Use a consistent hashing ring to route keys to backend shards

Solution

  1. Step 1: Identify the filtering requirement

    The system needs a fast, memory-efficient way to filter out keys that definitely do not exist before hitting the slow backend.

  2. Step 2: Evaluate component suitability

    Redis cache storing all keys (A) is expensive and not scalable for huge key sets. Relational DB indexes (C) still require backend queries. Consistent hashing (D) routes keys but does not filter non-existent keys. Bloom filters (B) provide fast probabilistic membership tests with low memory.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Bloom filters reduce backend queries by filtering non-existent keys [check]
Hint: Bloom filters quickly say no before expensive lookups [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard