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
45 min · senior
senior

You are designing a distributed lock service for a 50M DAU startup that requires coordination across multiple microservices to ensure data consistency and prevent race conditions. The system must handle high concurrency with low latency and guarantee correctness under network partitions and failures.

Constraints
  • P99 lock acquisition latency under 200ms
  • End-to-end encryption of lock metadata in transit and at rest
  • Support for automatic lock expiration and renewal to avoid deadlocks
  • Offline client support with eventual lock release
  • High availability with zero single points of failure
📋
Guided Steps
1/6
Step 1
Define the core use cases and scale requirements for distributed locks
What are the primary scenarios requiring distributed locks, and what scale and latency targets must the system meet?
💡 Hint
Consider concurrency levels, failure modes, and latency SLAs typical for 50M DAU systems.
Key Decision
Focus on high-concurrency coordination with P99 latency < 200ms, supporting millions of lock requests per second using a highly available consensus system like Apache ZooKeeper or etcd.
Interviewer Expectation
Mid-level: Identifies need for distributed locks and basic scale. Senior: Quantifies concurrency, latency targets, and explains why local locks or DB transactions alone fail at this scale.
⚠️Common Wrong Answer
Using a single relational database lock table - leads to bottlenecks and high latency under millions of concurrent requests.
Step 2
Choose the underlying technology for implementing distributed locks
Which technology will you use to implement the distributed lock service and why?
💡 Hint
Think about consensus protocols that guarantee linearizability and fault tolerance.
Key Decision
Use etcd with Raft consensus for strong consistency and leader election, enabling linearizable lock acquisition and automatic failover.
Interviewer Expectation
Mid-level: Names etcd or ZooKeeper. Senior: Explains Raft consensus benefits, linearizability guarantees, and why Redis SETNX or database locks are insufficient at scale.
⚠️Common Wrong Answer
Using Redis SETNX without consensus - causes split-brain and stale locks under network partitions.
Step 3
Design lock expiration and renewal mechanisms
How will the system handle automatic lock expiration and renewal to prevent deadlocks and stale locks?
💡 Hint
Consider TTLs with heartbeats and how to handle client crashes or network failures.
Key Decision
Implement TTL-based locks with client heartbeats updating TTL in etcd; if TTL expires without renewal, lock is released automatically.
Interviewer Expectation
Mid-level: Mentions TTL or lease. Senior: Details heartbeat frequency, TTL tuning to balance latency and failure detection, and how to avoid premature lock release.
⚠️Common Wrong Answer
No TTL or heartbeat - leads to permanent deadlocks if clients crash holding locks.
Step 4
Ensure security and encryption of lock metadata
How will you secure lock metadata in transit and at rest to meet encryption requirements?
💡 Hint
Think about TLS for communication and encryption options for persistent storage.
Key Decision
Use TLS 1.3 for all client-server and inter-node communication; enable etcd's built-in encryption at rest with AES-256 to protect lock metadata.
Interviewer Expectation
Mid-level: Mentions TLS. Senior: Explains mutual TLS authentication, key rotation, and encryption at rest configuration in etcd.
⚠️Common Wrong Answer
No encryption or only encrypting in transit - exposes sensitive lock state to attackers with storage access.
Step 5
Design APIs for lock acquisition, renewal, and release
Sketch the 3 core API endpoints clients will use to interact with the distributed lock service.
💡 Hint
Consider idempotency, error handling, and how clients detect lock ownership.
Key Decision
Define AcquireLock(lock_id, client_id, ttl), RenewLock(lock_id, client_id), and ReleaseLock(lock_id, client_id) endpoints with idempotent semantics and error codes for contention and expiration.
Interviewer Expectation
Mid-level: Lists endpoints. Senior: Explains idempotency, optimistic concurrency control, and how clients handle retries and failures.
⚠️Common Wrong Answer
Single endpoint without renewal - causes clients to lose locks unexpectedly or deadlocks.
Step 6
Handle failure scenarios and offline client support
How does the system behave under network partitions, client crashes, and offline clients holding locks?
💡 Hint
Think about lease expiration, fencing tokens, and client reconnection strategies.
Key Decision
Use fencing tokens returned on lock acquisition to prevent stale clients from acting; rely on TTL expiration to release locks held by offline clients; clients must re-acquire locks after reconnect.
Interviewer Expectation
Mid-level: Mentions TTL expiration. Senior: Explains fencing tokens to prevent split-brain effects and how offline clients are detected and handled gracefully.
⚠️Common Wrong Answer
No fencing tokens - stale clients can corrupt shared state after reconnecting.
🔌
API Design Challenge
Sketch 3 core API endpoints for the distributed lock service that clients will use to acquire, renew, and release locks.
Hints
  • How does a client request a lock and handle contention?
  • What mechanism allows clients to keep a lock alive?
  • How does the system confirm lock release and handle stale locks?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Clear explanation of why distributed locks are needed at scale with concurrency and latency targets
  • Use of a consensus-based system like etcd or ZooKeeper for strong consistency
  • TTL-based lock expiration with heartbeats to avoid deadlocks
  • Encryption in transit and at rest for lock metadata
  • API design covering lock acquisition, renewal, and release with idempotency
Good to Have - 30%
  • Discussion of fencing tokens to prevent stale client actions
  • Handling offline clients and network partitions gracefully
  • High availability design with multi-node clusters and failover
  • Client retry and backoff mechanisms
Bonus - 10%
  • Detailed failure mode analysis tracing exact failure sequences
  • Trade-off discussion on TTL tuning and latency impact
Anti-patterns to Avoid
Using Redis SETNX without consensus - causes split-brain and stale locks under network partitions, leading to inconsistent lock state and potential data corruption.
Relying solely on database row locks - creates bottlenecks and high latency under millions of concurrent requests, reducing system scalability and availability.
✅
Model Answer
▼ Reveal

This design addresses the challenges of implementing distributed locks at scale for a 50M DAU system by leveraging etcd with Raft consensus to ensure strong consistency and fault tolerance. It uses TTL-based leases with client heartbeats to prevent deadlocks and stale locks, secures lock metadata with TLS 1.3 and AES-256 encryption at rest, and provides idempotent APIs for lock acquisition, renewal, and release. Fencing tokens prevent stale clients from acting after losing locks, and the system supports offline clients and network partitions gracefully.

Key Decisions
  • Use etcd with Raft consensus protocol to guarantee linearizable lock acquisition and fault tolerance.
  • Implement TTL-based leases with client heartbeats to automatically expire locks if clients crash or disconnect.
  • Secure all communication with TLS 1.3 and enable AES-256 encryption at rest in etcd to protect lock metadata.
  • Design idempotent APIs AcquireLock(lock_id, client_id, ttl), RenewLock(lock_id, client_id), and ReleaseLock(lock_id, client_id) with optimistic concurrency control.
  • Issue fencing tokens on lock acquisition to prevent stale clients from performing operations after losing the lock.
  • Support offline clients by relying on TTL expiration to release locks and requiring clients to re-acquire locks upon reconnection.
  • Deploy a multi-node etcd cluster to ensure high availability with no single point of failure.
  • Implement client-side retry and exponential backoff strategies to handle contention and transient failures gracefully.
  • etcd with Raft consensus protocol - provides linearizable distributed locks with leader election and fault tolerance
  • TTL-based leases with client heartbeats - prevents deadlocks by automatic lock expiration
  • TLS 1.3 for all communication and AES-256 encryption at rest in etcd - ensures lock metadata confidentiality and integrity
  • Fencing tokens on lock acquisition - prevents stale clients from performing operations after losing the lock
  • Idempotent API endpoints AcquireLock, RenewLock, ReleaseLock with optimistic concurrency control - supports reliable client interactions
  • Automatic failover and multi-node etcd cluster - guarantees high availability with no single point of failure
  • Client-side retry and backoff strategies - handle contention and transient failures gracefully
  • Offline client detection via TTL expiration and lock release - supports eventual consistency and recovery

Practice

(1/5)
1. In the photo feed generation flow, at step 4 the Feed Worker fetches stories from the Stories Service cache. What happens if the cache TTL for a user's stories has expired at this step?
easy
A. The Feed Worker asynchronously refreshes the cache but returns an empty stories section immediately
B. The Feed Worker triggers a synchronous fetch from the Stories DB and blocks until fresh stories are retrieved
C. The Feed Worker returns stale stories from a backup cache without fetching fresh data
D. The Feed Worker skips stories for that user and proceeds with only photo posts in the feed

Solution

  1. Step 1: Trace Feed Worker behavior at cache miss

    When TTL expires, the cache is stale. The Feed Worker must avoid blocking feed generation.

  2. Step 2: Understand asynchronous cache refresh

    To maintain low latency, the Feed Worker returns empty stories immediately and triggers async cache refresh. Blocking fetch (B) would increase latency. Returning stale data (A) risks outdated content. Skipping stories silently (C) loses user experience.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Async cache refresh avoids blocking feed generation [check]
Hint: Async cache refresh avoids blocking feed generation [OK]
Common Mistakes:
2. In a consistent hashing system with virtual nodes, at Step 4 the request router receives a key and must find the responsible physical node. What happens at this step?
easy
A. The router hashes the key, finds the closest virtual node clockwise, then maps to its physical node
B. The router hashes the key and assigns it to a random physical node to balance load
C. The router queries a centralized metadata service for the node responsible for the key
D. The router hashes the key and assigns it to the first physical node in the list

Solution

  1. Step 1: Trace request router behavior at Step 4

    The router uses the key's hash to find the closest virtual node clockwise on the ring.

  2. Step 2: Map virtual node to physical node

    Each virtual node maps to a physical node; the router routes the request accordingly.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Consistent hashing uses clockwise virtual node lookup to find physical node [check]
Hint: Hash key -> closest clockwise virtual node -> physical node [check]
Common Mistakes:
3. In a system where a client writes a user profile update to DynamoDB, then a cache invalidation message is sent to Redis at step 4, what happens if the cache invalidation fails at step 4?
easy
A. DynamoDB write is rolled back automatically to maintain consistency
B. Redis automatically retries invalidation and blocks client until success
C. The cache remains stale until TTL expires or manual refresh
D. Client receives an error and retries the entire update operation

Solution

  1. Step 1: Trace cache invalidation at step 4

    Cache invalidation is asynchronous and best-effort; failure does not rollback DB writes.

  2. Step 2: Understand failure impact on cache state

    If invalidation fails, Redis cache remains stale until TTL expiry or next explicit refresh.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Failed cache invalidation -> stale cache until TTL or manual refresh [check]
Hint: Failed cache invalidation -> stale cache, DB write persists [check]
Common Mistakes:
4. At 10x scale, which component of the distributed task scheduler is most likely to become the bottleneck first, and why?
hard
A. The network load balancer, as it cannot handle the increased connection count
B. The cron scheduler, because it cannot generate enough scheduled events concurrently
C. The worker nodes, because CPU resources are exhausted processing tasks
D. The distributed priority queue, due to contention on priority ordering and lease renewals

Solution

  1. Step 1: Analyze cron scheduler scalability

    Cron schedulers are typically lightweight and can be sharded or distributed; unlikely to bottleneck first (A).

  2. Step 2: Analyze worker node resource limits

    Workers scale horizontally; CPU exhaustion (C) is mitigated by adding nodes.

  3. Step 3: Analyze network load balancer capacity

    Load balancers scale with standard techniques; connection count (D) is manageable.

  4. Step 4: Analyze distributed priority queue bottlenecks

    Priority queue faces contention on ordering, lease renewals, and coordination overhead, which grows non-linearly with scale, causing it to bottleneck first (B).

  5. Final Answer:

    Option D -> Option D

  6. Quick Check:

    Priority queue contention and lease overhead limit scale first [check]
Hint: Priority queue contention limits scale before others [check]
Common Mistakes:
5. At 10x scale, which component is most likely to fail first and why when estimating system bandwidth for a social media platform with rapidly growing DAU?
hard
A. Storage Estimator, because disk I/O cannot keep up with 10x data volume growth
B. Bandwidth Estimator, because network metrics aggregation scales linearly and hits memory limits
C. DAU Estimator, because tracking and aggregating active users in real-time becomes a bottleneck
D. QPS Estimator, because load balancer metrics become too noisy and inaccurate at high scale

Solution

  1. Step 1: Identify bottleneck at 10x DAU scale

    DAU Estimator must track millions of active users in real-time, requiring heavy aggregation and state management.

  2. Step 2: Eliminate other options

    Storage Estimator scales with disk but can be sharded; Bandwidth Estimator aggregates metrics but less stateful; QPS Estimator uses load balancer metrics which scale better.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Real-time DAU tracking state grows fastest, causing bottleneck [check]
Hint: Real-time DAU tracking state grows fastest at scale [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