Bird
Raised Fist0

Redis-Based Distributed Lock - Redlock Algorithm Design

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Redis-Based Distributed Lock - Redlock Algorithm Design
45 min · senior
senior

You are building a distributed lock service for a 50 million daily active user (DAU) startup that requires coordination across multiple microservices to prevent race conditions on shared resources. The system must guarantee strong consistency of locks, tolerate partial failures, and maintain a P99 latency under 200ms. Locks must be encrypted in transit and at rest to comply with security policies. The system should handle network partitions gracefully and avoid deadlocks or lock starvation.

Constraints
  • Support at least 10,000 lock/unlock operations per second with P99 latency < 200ms
  • Encrypt all lock tokens and communication using TLS and AES-256 encryption
  • Use at least 5 independent Redis nodes to implement the Redlock algorithm for fault tolerance
  • Ensure lock expiry and renewal to avoid deadlocks in case of client crashes
  • Handle network partitions without violating mutual exclusion guarantees
📋
Guided Steps
1/5
Step 1
Choosing the Lock Coordination Mechanism
Which distributed locking algorithm and Redis deployment architecture will you use to ensure strong consistency and fault tolerance?
💡 Hint
Consider how to achieve consensus across multiple Redis nodes and tolerate node failures without split-brain.
Key Decision
Use the Redlock algorithm implemented over 5 independent Redis nodes with unique lock tokens and majority quorum to guarantee mutual exclusion and fault tolerance.
Interviewer Expectation
Mid: Names Redlock and multiple Redis instances. Senior: Explains why single Redis or Redis Sentinel fail under network partitions and how Redlock quorum avoids split-brain.
⚠️Common Wrong Answer
Using a single Redis instance with SETNX - leads to single point of failure and possible lock loss during failover.
Step 2
Lock Token Generation and Security
How will you generate and secure lock tokens to prevent unauthorized release or hijacking of locks?
💡 Hint
Think about cryptographically strong random tokens and encrypting tokens in transit and at rest.
Key Decision
Generate cryptographically secure UUIDv4 tokens per lock acquisition, encrypt tokens using AES-256 before storing in Redis, and use TLS for all client-server communication.
Interviewer Expectation
Mid: Mentions UUID tokens and TLS. Senior: Details AES-256 encryption of tokens at rest in Redis and token validation on release to prevent hijacking.
⚠️Common Wrong Answer
Using predictable tokens or no encryption - leads to security vulnerabilities and unauthorized lock release.
Step 3
Lock Expiry and Renewal Strategy
How will you handle lock expiry and renewal to avoid deadlocks and ensure locks do not remain indefinitely held if clients crash?
💡 Hint
Consider TTL on locks and a safe renewal protocol that prevents race conditions.
Key Decision
Set a TTL on each lock key in Redis (e.g., 30 seconds), require clients to renew locks before expiry by re-acquiring with the same token, and use Lua scripts to atomically check token ownership before renewal.
Interviewer Expectation
Mid: Mentions TTL and renewal. Senior: Explains atomic Lua scripts for safe renewal and how to handle renewal failures to avoid deadlocks.
⚠️Common Wrong Answer
No TTL or renewal - leads to deadlocks if clients crash and locks never expire.
Step 4
Handling Network Partitions and Failures
How will your design handle network partitions or Redis node failures without violating mutual exclusion guarantees?
💡 Hint
Think about quorum-based consensus and how to detect and recover from partial failures.
Key Decision
Require acquiring locks on a majority (quorum) of Redis nodes within a time threshold; if quorum not reached, fail lock acquisition. Use Redlock’s timing constraints to avoid split-brain and ensure safety during partitions.
Interviewer Expectation
Mid: Understands quorum concept. Senior: Explains timing constraints, clock drift assumptions, and why majority quorum prevents split-brain and stale locks.
⚠️Common Wrong Answer
Accepting locks from fewer than majority nodes - leads to multiple clients holding the lock simultaneously, violating mutual exclusion.
Step 5
API Design for Lock Operations
Design the 3 core API endpoints for clients to acquire, release, and renew locks. What parameters and responses do they include?
💡 Hint
Consider idempotency, token validation, TTL, and error handling in your API design.
Key Decision
Define endpoints: AcquireLock(resource_id, ttl) → returns encrypted token or error; ReleaseLock(resource_id, token) → success/failure; RenewLock(resource_id, token, ttl) → success/failure. Use token validation and atomic Redis Lua scripts for correctness.
Interviewer Expectation
Mid: Lists endpoints with basic parameters. Senior: Details token validation, atomicity via Lua scripts, error codes for lock contention, and TTL management.
⚠️Common Wrong Answer
Designing release without token validation - allows unauthorized clients to release locks, breaking safety.
🔌
API Design Challenge
Sketch 3 core API endpoints for the distributed lock service that clients will use to acquire, release, and renew locks.
Hints
  • How does the client request a lock with a timeout and unique token?
  • How does the client release a lock safely ensuring only the owner can release it?
  • How does the client renew a lock to extend its TTL before expiry?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of Redlock algorithm with majority quorum over multiple Redis nodes
  • Secure lock token generation and encryption with AES-256 and TLS
  • Lock expiry with TTL and atomic renewal to avoid deadlocks
  • Handling network partitions with quorum and timing constraints
Good to Have - 30%
  • Atomic Lua scripts for lock operations to ensure correctness
  • Well-designed API endpoints with token validation and error handling
  • Independent Redis nodes deployment to reduce correlated failures
  • Monitoring for latency and failure detection
Bonus - 10%
  • Detailed failure mode analysis for network partitions and client crashes
  • Discussion of clock drift assumptions and mitigation
  • Consideration of scaling Redis nodes and sharding locks by resource ID
Anti-patterns to Avoid
Single Redis instance for locking - causes single point of failure and lock loss during failover, risking system availability and correctness
No token validation on release - allows unauthorized lock release and breaks mutual exclusion, leading to race conditions
No TTL on locks - leads to deadlocks if clients crash and never release locks, causing resource starvation
Accepting locks from fewer than majority nodes - leads to multiple clients holding the lock simultaneously, violating mutual exclusion guarantees
✅
Model Answer
▼ Reveal

This design uses the Redlock algorithm implemented over 5 independent Redis nodes to provide a fault-tolerant distributed locking service. Locks are identified by cryptographically secure UUIDv4 tokens encrypted with AES-256 at rest and transmitted over TLS to ensure security. Each lock has a TTL (e.g., 30 seconds) to prevent deadlocks, with clients renewing locks atomically via Lua scripts before expiry. The system requires acquiring locks on a majority quorum of Redis nodes within timing constraints to handle network partitions and avoid split-brain scenarios. API endpoints for acquiring, releasing, and renewing locks validate tokens and use atomic Redis Lua scripts to maintain correctness and idempotency. Monitoring ensures the system meets the P99 latency SLA under high load.

Key Decisions
  • Use Redlock algorithm with majority quorum over 5 independent Redis nodes to ensure strong consistency and fault tolerance
  • Generate cryptographically secure UUIDv4 tokens, encrypt tokens at rest with AES-256, and use TLS for communication to secure locks
  • Set TTL on locks (e.g., 30 seconds) and require clients to renew locks atomically before expiry using Lua scripts to avoid deadlocks
  • Enforce quorum-based lock acquisition with timing constraints to handle network partitions and prevent split-brain
  • Design API endpoints with token validation and atomic operations to maintain correctness and security
  • Redlock algorithm over 5 independent Redis nodes - ensures fault tolerance and strong consistency via majority quorum
  • Cryptographically secure UUIDv4 lock tokens encrypted with AES-256 at rest and TLS in transit - prevents hijacking
  • Lock keys stored with TTL (e.g., 30s) and atomic renewal via Redis Lua scripts - avoids deadlocks and race conditions
  • Majority quorum acquisition with timing constraints to handle network partitions and prevent split-brain
  • Atomic Lua scripts for lock acquire, release, and renew operations - ensures correctness under concurrency
  • API endpoints with token validation and error handling to maintain idempotency and security
  • Use of Redis Cluster or standalone nodes with independent failure domains to avoid correlated failures
  • Monitoring and alerting on lock acquisition latency and failure rates to maintain P99 < 200ms SLA

Practice

(1/5)
1. In the request flow, at step 3 the API Gateway forwards the request to the BFF layer. What happens at step 4 inside the BFF before calling downstream microservices?
easy
A. BFF aggregates and transforms data from multiple microservices into a client-specific response
B. BFF caches the entire response from microservices before returning to client
C. BFF directly proxies the request without modification to microservices
D. BFF performs authentication and then sends request to a single microservice

Solution

  1. Step 1: Understand BFF responsibilities at step 4

    At step 4, the BFF aggregates data from multiple microservices and transforms it into a response tailored to the client's needs.

  2. Step 2: Eliminate incorrect options

    BFF caches the entire response from microservices before returning to client is wrong because caching happens after response, not before calling microservices. BFF directly proxies the request without modification to microservices is incorrect as BFF modifies requests/responses rather than proxying blindly. BFF performs authentication and then sends request to a single microservice is incomplete; authentication usually happens earlier at API Gateway, and BFF calls multiple microservices, not just one.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    BFF aggregates and transforms data before responding [check]
Hint: BFF aggregates and transforms data before responding [check]
Common Mistakes:
2. A global CDN operator needs to prevent a misconfiguration from propagating incorrect BGP routes that could cause widespread internet outages. Which component is primarily responsible for detecting and containing such route leaks?
easy
A. Using a centralized DNS firewall to block suspicious IP prefixes
B. Implementing BGP route filters and prefix limits on edge routers
C. Relying on client-side validation of IP addresses before routing
D. Deploying a distributed cache to store valid routing tables

Solution

  1. Step 1: Identify BGP route filtering role

    BGP route filters and prefix limits on edge routers prevent invalid or excessive route announcements, containing route leaks.

  2. Step 2: Eliminate other options

    DNS firewalls (A) do not control BGP routing; client-side validation (C) is ineffective for routing control; distributed caches (D) do not enforce routing policies.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    BGP route filters contain route leaks at the network edge [check]
Hint: Edge routers enforce BGP filters to block bad routes [check]
Common Mistakes:
3. In a distributed cache using consistent hashing, at Step 4 the Cache Node receives a key lookup request. What happens if the node does not have the key locally?
easy
A. The node returns a cache miss immediately without forwarding
B. The node uses the consistent hash ring to forward the request to the correct node
C. The node queries a centralized metadata service for key location
D. The node broadcasts the request to all other cache nodes

Solution

  1. Step 1: Trace key lookup at Cache Node

    If the node lacks the key, it must find the correct node responsible for that key using the consistent hash ring.

  2. Step 2: Forwarding via consistent hash ring

    The node consults the hash ring to identify the node owning the key and forwards the request there; centralized metadata (The node queries a centralized metadata service for key location) adds latency and single point of failure; broadcasting (The node broadcasts the request to all other cache nodes) is inefficient.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Consistent hash ring lookup enables correct node forwarding [check]
Hint: Cache miss triggers consistent hash ring forwarding [check]
Common Mistakes:
4. In a MongoDB data model using the bucket pattern for time-series data, at step 3 of the write flow, the system checks if the current bucket document is full. What happens if the bucket is full at this step?
easy
A. A new bucket document is created and the write is appended there to maintain document size limits.
B. The write is rejected and the client must retry with a new bucket ID.
C. The existing bucket document is updated by splitting it into two smaller documents automatically.
D. The write is appended to the existing bucket document regardless of size, risking document growth beyond limits.

Solution

  1. Step 1: Understand bucket pattern write flow

    Writes append to a bucket document until size or time limits are reached.

  2. Step 2: Behavior when bucket is full

    System creates a new bucket document to avoid exceeding MongoDB's 16MB document size limit.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    New bucket created to respect document size limits [check]
Hint: Full bucket triggers new document creation to avoid size limit [check]
Common Mistakes:
5. At 10x scale, which component in the SLO error budget tracking system is most likely to become the bottleneck first, and why?
hard
A. The metrics aggregation service, because it maintains stateful counters and cannot shard error budget calculations easily
B. The dashboard visualization layer, because rendering 10x more data overwhelms client browsers
C. The raw event ingestion pipeline, because Kafka partitions can be increased indefinitely without limit
D. The alerting system, because it can batch alerts and scale horizontally without state

Solution

  1. Step 1: Identify stateful components that limit horizontal scaling

    The metrics aggregation service maintains counters and error budget state, which are hard to shard without losing accuracy.

  2. Step 2: Evaluate other components' scalability

    Dashboards (A) are client-side and less critical; Kafka (C) scales well with partitions; alerting (D) can batch and scale horizontally.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Stateful aggregation -> sharding limits -> bottleneck at scale [check]
Hint: Stateful aggregation limits sharding, causing first bottleneck at scale [OK]
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