Distributed Locking

In a single-process application, threads coordinate access to shared resources using simple memory constructs like mutexes or semaphores. However, when an application is distributed across hundreds of independent server instances, local memory locks are useless. If multiple servers attempt to charge a user's credit card or claim an items stock concurrently, double charges and race conditions occur. Distributed Locking provides a cluster-wide coordination boundary, ensuring that only one node can modify a specific resource at any given instant.

1. Learning Objectives

• Understand the difference between database locks, distributed locks, and local thread locks.
• Explain the Redlock algorithm mechanics and its resilience assumptions.
• Implement lock lease safety features: Time-to-Live (TTL) and automatic renewal watchdogs.
• Detail how to prevent split-brain and clock skew failures in locking datastores.
• Write a thread-safe Distributed Lock Manager simulator with auto-renewal in Java, Python, and C++.

2. Prerequisites

Before learning about distributed locks, ensure you understand:

• Race Conditions: How concurrent writes cause data corruption.
• Redis Basics: Understanding keys, values, and TTL commands.
• Consensus (ZooKeeper/Raft): General knowledge of leader election.

3. Why This Topic Matters

Without cluster-wide locking, scaling out compute tiers introduces data integrity hazards.

For example, during a flash sale, if Node 1 and Node 2 simultaneously verify stock for the last ticket, both read "1 ticket available". Both proceed to deduct stock, resulting in double-selling. Distributed locking restricts access: Node 1 acquires the lock lock:ticket_102 first, forcing Node 2 to wait until Node 1 commits its write, ensuring consistency.

4. Real-world Analogy

Think of a shared conference room in a co-working space:

• No coordination (Race condition): Anyone can walk in at any time. Two teams walk in at 2 PM, arguing over who gets to use the whiteboard.
• Distributed Lock (Booking Key): There is a centralized digital calendar. To use the room, a team must log in and book the slot. The booking has a duration limit (TTL) of 1 hour. If the team needs more time, they must extend the booking before it expires. If the team leaves early, they delete the booking (unlock). If the team's laptop crashes and they leave without cleaning up, the system frees the room automatically after 1 hour (lease expiry), preventing permanent deadlock.

5. Core Concepts

• Mutual Exclusion (Mutex): Only one node can hold the lock at any given time.
• Lease Time-to-Live (TTL): A safety expiration time attached to a lock. If the worker crashes, the lock expires naturally, preventing deadlocks.
• Watchdog Renewal: A background thread that periodically extends the lock lease time while the main worker thread is still actively running.
• Fencing Token: An auto-incrementing ID generated by the lock manager. Databases check the token; if a late worker tries to write with a stale token, the database rejects the write, resolving network partition delays.

6. Visualization

Distributed Lock Lease and Watchdog Sequence

7. How It Works: Lock Lifecycle

1. Acquisition: Worker calls Redis: SET lock_key worker_UUID NX PX 10000. NX creates the key only if it does not exist; PX 10000 sets a 10-second TTL.
2. Lease Tracking: The worker launches a background watchdog thread. Every 3 seconds, the watchdog resets the TTL back to 10 seconds.
3. Critical Section execution: The worker processes the shared resource (e.g. updating bank balance).
4. Release validation: When complete, the worker calls a Lua script to release the lock. The Lua script verifies that the value of the key matches worker_UUID before deleting it, preventing a slow worker from deleting a lock owned by another node.

8. Internal Architecture

9. Request Lifecycle

• 1. Ingress Request: Node A receives a payment request with ticket ID 405.
• 2. Lock Check: Node A queries the Redis cluster, executing SET lock:ticket:405 UUID_A NX PX 5000. Redis returns true. Lock is active.
• 3. Processing: Node A launches the watchdog thread and proceeds to execute payment API.
• 4. Concurrent Collision: Simultaneously, Node B receives the same request and executes SET lock:ticket:405 UUID_B NX PX 5000. Redis returns false. Node B immediately rejects the request with a "409 Conflict" code.
• 5. Release: Node A completes payment, terminates the watchdog, and runs Lua code: if redis.call("get",KEYS[1]) == ARGV[1] then return redis.call("del",KEYS[1]) else return 0 end to safely delete the key.

10. Deep Dive: The Redlock Algorithm

A single Redis master node is a single point of failure. If it crashes, locks are lost. The Redlock Algorithm addresses this by coordinating locks across 5 independent Redis master nodes:

1. The client captures the current timestamp.
2. The client attempts to acquire the lock in all 5 instances sequentially, using the same key and UUID. The timeout for each single instance call is kept small (e.g. 5-50ms) to prevent blocking if a node is down.
3. The client calculates how much time it took to acquire all locks. If it successfully acquired the lock in at least 3 nodes (majority), and the total elapsed time is less than the lock validity time, the lock is acquired.
4. The lock validity time is recalculated: initial_validity_time - elapsed_time.
5. If the client fails to acquire the lock in the majority of nodes, it immediately executes an unlock script in all 5 instances to clean up partially set keys.

11. Production Example

• Uber: Uses Redis-based distributed locking (using Redisson client library in Java) to coordinate matching algorithms, preventing two matching engines from assigning the same driver to different riders concurrently.
• Kubernetes: Uses ZooKeeper/etcd distributed locking (Leases) to coordinate Leader Election among control plane nodes, ensuring only one manager instance is active as the scheduler master.

12. Advantages

• Strong Resource Protection: Strictly guarantees mutual exclusion, preventing race conditions.
• Fault-Tolerant Deadlock Prevention: Lease TTLs ensure locks release naturally even if servers crash.
• Decoupled Compute: Allows application nodes to scale out horizontally without sharing database locks.

13. Limitations

• Susceptible to Network Pauses: If a JVM experiences a Stop-the-World garbage collection pause *after* acquiring the lock, the lock lease might expire in Redis before the worker finishes processing, allowing another node to acquire it concurrently.
• Clock Skew Vulnerability: Redlock relies on physical system times. If NTP clocks drift between nodes, validity calculations can fail.

14. Trade-offs

Weigh lock safety against system throughput:

• Redis (AP Model): Prioritizes performance. High throughput, low latency locks, but carries a small risk of duplicate locks during network partitions.
• ZooKeeper (CP Model): Prioritizes consistency. Ephemeral node sessions guarantee strict correctness, but write throughput is lower due to consensus roundtrips.

15. Performance Considerations

• Acquisition Wait Time: Configure short lock attempt timeouts. If a key is locked, waiting nodes should poll with exponential backoff rather than spamming Redis.
• Watchdog CPU Cost: Running hundreds of background thread checks can consume CPU resources. Limit watchdog pools.

16. Failure Scenarios: Slow Worker Invalidation

The Slow Worker Failure:
Node A acquires a 5-second lock to write to the database. Node A experiences a 6-second GC pause.
- During the pause, the lock expires in Redis.
- Node B acquires the lock and begins writing to the database.
- Node A wakes up and writes to the database, overwriting Node B's changes.
Mitigation: Implement Fencing Tokens. The lock manager returns an auto-incrementing ID (e.g. token=123) with the lock. The database checks the token; if a write arrives with token 123 after token 124 has already committed, the database rejects it.

17. Best Practices

• Always Use Lua Scripts for Deletions: Never release a lock using a simple delete query. Always verify the owner token in a Lua script to prevent deleting other workers' locks.
• Size TTL Appropriately: Keep lease TTLs larger than the average execution time of the critical section.

18. Common Mistakes

• Missing Watchdogs: Assuming a static TTL is enough. If a database query slows down, a static lock can expire, allowing concurrent processing.
• Locking Too Aggressively: Locking entire tables or large catalogs instead of granular row keys (e.g., locking the entire inventory instead of the specific item_id).

19. Implementation: Distributed Lock Manager with Watchdog

The following code implements a Distributed Lock Manager simulator featuring auto-renewal watchdogs and safe token verification releases:

20. Interview Questions

21. Practice Exercises

22. Challenge Problem

23. Summary

Distributed locking coordinates exclusive access to shared resources across independent nodes. While Redis SETNX is fast, it requires watchdog threads to renew leases and Lua scripts for safe releases. For strict correctness, consensus systems like ZooKeeper combined with database fencing tokens protect against clock skew and GC pause vulnerabilities.

24. Cheat Sheet

25. Quiz

26. Further Reading

• Redis Distributed Locks documentation (Redlock specification).
• How to do a distributed lock by Martin Kleppmann (detailed analysis of Redlock safety limits).
• Is Redlock safe? by Salvatore Sanfilippo (Redis creator's response to critiques).

27. Next Lesson Preview

Distributed locking coordinates access, but we must also manage how data converges across regions. In the next lesson, we explore Data Consistency Strategies, reviewing read-your-own-writes mechanisms, monotonic reads, eventual consistency models, and the mathematical quorum validation criteria.