Distributed Locks

The Coordination Problem

In distributed systems, multiple nodes often need to coordinate access to shared resources:

• Database updates: Only one node should update a record at a time
• Cache invalidation: Prevent multiple nodes from invalidating cache simultaneously
• Scheduled tasks: Ensure only one node runs a scheduled job
• Resource allocation: Coordinate access to limited resources

The Challenge: Traditional locks (like mutexes) only work within a single process. In distributed systems, we need locks that work across multiple nodes, handle network failures, and prevent deadlocks.

What is a Distributed Lock?

A distributed lock is a coordination mechanism that ensures only one process or node can hold a lock at a time across a distributed system. It provides mutual exclusion across network boundaries.

Key Requirements

1. Mutual Exclusion: Only one holder at a time
2. Deadlock Free: Locks are eventually released (via timeout/lease)
3. Fault Tolerant: Survives node failures
4. High Availability: Lock service must be available
5. Performance: Low latency, high throughput

Simple Analogy

Think of a distributed lock like a bathroom key at a restaurant:

• Only one person can have the key at a time
• If someone forgets to return the key, there’s a timeout mechanism (staff has a master key)
• Multiple people can request the key, but only one gets it
• The key must be returned for others to use it

Lease-Based Locks

Lease-based locks automatically expire after a timeout period. This prevents deadlocks from crashed nodes.

How It Works:

1. Node acquires lock with a lease time (e.g., 10 seconds)
2. Node must renew lock before lease expires
3. If node crashes, lock automatically expires
4. Other nodes can acquire lock after expiration

Benefits:

• Prevents deadlocks from crashed nodes
• Automatic cleanup
• No manual lock release needed if node crashes

Redis-Based Distributed Locks

Redis provides a simple way to implement distributed locks using the SET command with NX (only if not exists) and EX (expiration) options.

Basic Implementation

Key Points:

• Use unique value (like UUID) to verify ownership
• Set expiration to prevent deadlocks
• Check return value: OK means lock acquired, nil means already held

Distributed Lock Implementation

💡 Tip: Click dropdown to switch between languages

Python

Python

"distributed_lock.py

import redis
import uuid
import time
import threading
from typing import Optional

class DistributedLock:
    """Distributed lock using Redis"""

    def __init__(self, redis_client: redis.Redis, lock_key: str, lease_time: int = 10):
        self.redis = redis_client
        self.lock_key = lock_key
        self.lease_time = lease_time
        self.lock_value = str(uuid.uuid4())  # Unique value for ownership verification
        self.renewal_thread: Optional[threading.Thread] = None
        self.lock_held = False

    def acquire(self, timeout: int = 5) -> bool:
        """Acquire lock with timeout"""
        start_time = time.time()

        while time.time() - start_time < timeout:
            # Try to acquire lock: SET lock_key value NX EX lease_time
            result = self.redis.set(
                self.lock_key,
                self.lock_value,
                nx=True,  # Only set if not exists
                ex=self.lease_time  # Expire after lease_time seconds
            )

            if result:
                self.lock_held = True
                # Start renewal thread
                self._start_renewal()
                return True

            # Lock held by another, wait a bit
            time.sleep(0.1)

        return False  # Timeout

    def release(self) -> bool:
        """Release lock (only if we own it)"""
        if not self.lock_held:
            return False

        # Lua script to atomically check and delete
        # Only delete if value matches (we own the lock)
        lua_script = """
        if redis.call("get", KEYS[1]) == ARGV[1] then
            return redis.call("del", KEYS[1])
        else
            return 0
        end
        """

        result = self.redis.eval(lua_script, 1, self.lock_key, self.lock_value)

        if result:
            self.lock_held = False
            self._stop_renewal()
            return True

        return False  # Lock expired or held by another

    def _start_renewal(self):
        """Start thread to renew lock before expiration"""
        def renew():
            while self.lock_held:
                time.sleep(self.lease_time / 2)  # Renew at half lease time
                if self.lock_held:
                    # Extend expiration
                    self.redis.expire(self.lock_key, self.lease_time)

        self.renewal_thread = threading.Thread(target=renew, daemon=True)
        self.renewal_thread.start()

    def _stop_renewal(self):
        """Stop renewal thread"""
        self.renewal_thread = None

    def __enter__(self):
        """Context manager entry"""
        if not self.acquire():
            raise Exception("Failed to acquire lock")
        return self

    def __exit__(self, exc_type, exc_val, exc_tb):
        """Context manager exit"""
        self.release()

# Usage
redis_client = redis.Redis(host='localhost', port=6379)

# Using context manager
lock = DistributedLock(redis_client, "resource_lock", lease_time=10)

with lock:
    # Critical section
    print("Doing work with lock held")
    time.sleep(5)

# Lock automatically released

Java

"DistributedLock.java

import redis.clients.jedis.Jedis;
import redis.clients.jedis.params.SetParams;
import java.util.UUID;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

public class DistributedLock {
    private final Jedis jedis;
    private final String lockKey;
    private final int leaseTime;
    private final String lockValue;
    private boolean lockHeld = false;
    private ScheduledExecutorService renewalExecutor;

    public DistributedLock(Jedis jedis, String lockKey, int leaseTime) {
        this.jedis = jedis;
        this.lockKey = lockKey;
        this.leaseTime = leaseTime;
        this.lockValue = UUID.randomUUID().toString();
    }

    public boolean acquire(int timeoutSeconds) {
        long startTime = System.currentTimeMillis();

        while (System.currentTimeMillis() - startTime < timeoutSeconds * 1000) {
            // Try to acquire lock: SET lock_key value NX EX lease_time
            SetParams params = SetParams.setParams()
                .nx()  // Only set if not exists
                .ex(leaseTime);  // Expire after lease_time seconds

            String result = jedis.set(lockKey, lockValue, params);

            if ("OK".equals(result)) {
                lockHeld = true;
                startRenewal();
                return true;
            }

            // Lock held by another, wait a bit
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                return false;
            }
        }

        return false; // Timeout
    }

    public boolean release() {
        if (!lockHeld) {
            return false;
        }

        // Lua script to atomically check and delete
        String luaScript =
            "if redis.call('get', KEYS[1]) == ARGV[1] then " +
            "  return redis.call('del', KEYS[1]) " +
            "else " +
            "  return 0 " +
            "end";

        Long result = (Long) jedis.eval(
            luaScript,
            java.util.Collections.singletonList(lockKey),
            java.util.Collections.singletonList(lockValue)
        );

        if (result == 1) {
            lockHeld = false;
            stopRenewal();
            return true;
        }

        return false; // Lock expired or held by another
    }

    private void startRenewal() {
        renewalExecutor = Executors.newScheduledThreadPool(1);
        renewalExecutor.scheduleAtFixedRate(() -> {
            if (lockHeld) {
                jedis.expire(lockKey, leaseTime);
            }
        }, leaseTime / 2, leaseTime / 2, TimeUnit.SECONDS);
    }

    private void stopRenewal() {
        if (renewalExecutor != null) {
            renewalExecutor.shutdown();
        }
    }
}

// Usage
Jedis jedis = new Jedis("localhost", 6379);
DistributedLock lock = new DistributedLock(jedis, "resource_lock", 10);

if (lock.acquire(5)) {
    try {
        // Critical section
        System.out.println("Doing work with lock held");
        Thread.sleep(5000);
    } finally {
        lock.release();
    }
}

TypeScript

distributed-lock.ts

import Redis from 'ioredis';
import { v4 as uuidv4 } from 'uuid';

class DistributedLock {
    // Distributed lock using Redis
    private redis: Redis;
    private lockKey: string;
    private leaseTime: number;
    private lockValue: string;
    private lockHeld: boolean = false;
    private renewalInterval: NodeJS.Timeout | null = null;

    constructor(redis: Redis, lockKey: string, leaseTime: number = 10) {
        this.redis = redis;
        this.lockKey = lockKey;
        this.leaseTime = leaseTime;
        this.lockValue = uuidv4();
    }

    async acquire(timeoutSeconds: number = 5): Promise<boolean> {
        // Acquire lock with timeout
        const startTime = Date.now();

        while (Date.now() - startTime < timeoutSeconds * 1000) {
            // Try to acquire lock: SET lock_key value NX EX lease_time
            const result = await this.redis.set(
                this.lockKey,
                this.lockValue,
                'EX',
                this.leaseTime,
                'NX' // Only set if not exists
            );

            if (result === 'OK') {
                this.lockHeld = true;
                this.startRenewal();
                return true;
            }

            // Lock held by another, wait a bit
            await new Promise(resolve => setTimeout(resolve, 100));
        }

        return false; // Timeout
    }

    async release(): Promise<boolean> {
        // Release lock (only if we own it)
        if (!this.lockHeld) {
            return false;
        }

        // Lua script to atomically check and delete
        const luaScript = `
            if redis.call("get", KEYS[1]) == ARGV[1] then
                return redis.call("del", KEYS[1])
            else
                return 0
            end
        `;

        const result = await this.redis.eval(
            luaScript,
            1,
            this.lockKey,
            this.lockValue
        ) as number;

        if (result === 1) {
            this.lockHeld = false;
            this.stopRenewal();
            return true;
        }

        return false; // Lock expired or held by another
    }

    private startRenewal(): void {
        // Start interval to renew lock before expiration
        this.renewalInterval = setInterval(async () => {
            if (this.lockHeld) {
                await this.redis.expire(this.lockKey, this.leaseTime);
            }
        }, (this.leaseTime / 2) * 1000); // Renew at half lease time
    }

    private stopRenewal(): void {
        // Stop renewal interval
        if (this.renewalInterval) {
            clearInterval(this.renewalInterval);
            this.renewalInterval = null;
        }
    }
}

// Usage
const redis = new Redis({
    host: 'localhost',
    port: 6379
});

const lock = new DistributedLock(redis, "resource_lock", 10);

if (await lock.acquire(5)) {
    try {
        // Critical section
        console.log("Doing work with lock held");
        await new Promise(resolve => setTimeout(resolve, 5000));
    } finally {
        await lock.release();
    }
}

C++

"distributed_lock.cpp

#include <hiredis/hiredis.h>
#include <string>
#include <thread>
#include <chrono>
#include <uuid/uuid.h>

class DistributedLock {
private:
    redisContext* redis;
    std::string lockKey;
    int leaseTime;
    std::string lockValue;
    bool lockHeld;
    std::thread* renewalThread;

    void renewalLoop() {
        while (lockHeld) {
            std::this_thread::sleep_for(std::chrono::seconds(leaseTime / 2));
            if (lockHeld) {
                // Extend expiration
                redisCommand(redis, "EXPIRE %s %d", lockKey.c_str(), leaseTime);
            }
        }
    }

public:
    DistributedLock(redisContext* redis, const std::string& lockKey, int leaseTime = 10)
        : redis(redis), lockKey(lockKey), leaseTime(leaseTime), lockHeld(false), renewalThread(nullptr) {
        // Generate unique value
        uuid_t uuid;
        char uuid_str[37];
        uuid_generate(uuid);
        uuid_unparse_lower(uuid, uuid_str);
        lockValue = std::string(uuid_str);
    }

    bool acquire(int timeoutSeconds = 5) {
        auto startTime = std::chrono::steady_clock::now();

        while (std::chrono::steady_clock::now() - startTime < std::chrono::seconds(timeoutSeconds)) {
            // Try to acquire lock: SET lock_key value NX EX lease_time
            redisReply* reply = (redisReply*)redisCommand(
                redis,
                "SET %s %s NX EX %d",
                lockKey.c_str(),
                lockValue.c_str(),
                leaseTime
            );

            if (reply && reply->type == REDIS_REPLY_STATUS &&
                std::string(reply->str) == "OK") {
                freeReplyObject(reply);
                lockHeld = true;
                renewalThread = new std::thread(&DistributedLock::renewalLoop, this);
                return true;
            }

            freeReplyObject(reply);
            std::this_thread::sleep_for(std::chrono::milliseconds(100));
        }

        return false; // Timeout
    }

    bool release() {
        if (!lockHeld) {
            return false;
        }

        // Lua script to atomically check and delete
        std::string luaScript =
            "if redis.call('get', KEYS[1]) == ARGV[1] then "
            "  return redis.call('del', KEYS[1]) "
            "else "
            "  return 0 "
            "end";

        redisReply* reply = (redisReply*)redisCommand(
            redis,
            "EVAL %s 1 %s %s",
            luaScript.c_str(),
            lockKey.c_str(),
            lockValue.c_str()
        );

        bool result = false;
        if (reply && reply->type == REDIS_REPLY_INTEGER && reply->integer == 1) {
            lockHeld = false;
            if (renewalThread) {
                renewalThread->join();
                delete renewalThread;
                renewalThread = nullptr;
            }
            result = true;
        }

        freeReplyObject(reply);
        return result;
    }

    ~DistributedLock() {
        if (lockHeld) {
            release();
        }
    }
};

// Usage
redisContext* redis = redisConnect("localhost", 6379);
DistributedLock lock(redis, "resource_lock", 10);

if (lock.acquire(5)) {
    // Critical section
    std::cout << "Doing work with lock held" << std::endl;
    std::this_thread::sleep_for(std::chrono::seconds(5));
    lock.release();
}

C#

DistributedLock.cs

using StackExchange.Redis;
using System;
using System.Threading;
using System.Threading.Tasks;

public class DistributedLock {
    // Distributed lock using Redis
    private readonly IDatabase redis;
    private readonly string lockKey;
    private readonly int leaseTime;
    private readonly string lockValue;
    private bool lockHeld;
    private Timer renewalTimer;

    public DistributedLock(IDatabase redis, string lockKey, int leaseTime = 10) {
        this.redis = redis;
        this.lockKey = lockKey;
        this.leaseTime = leaseTime;
        this.lockValue = Guid.NewGuid().ToString();
        this.lockHeld = false;
    }

    public async Task<bool> AcquireAsync(int timeoutSeconds = 5) {
        // Acquire lock with timeout
        var startTime = DateTime.UtcNow;

        while (DateTime.UtcNow - startTime < TimeSpan.FromSeconds(timeoutSeconds)) {
            // Try to acquire lock: SET lock_key value NX EX lease_time
            bool acquired = await redis.StringSetAsync(
                lockKey,
                lockValue,
                TimeSpan.FromSeconds(leaseTime),
                When.NotExists // Only set if not exists
            );

            if (acquired) {
                lockHeld = true;
                StartRenewal();
                return true;
            }

            // Lock held by another, wait a bit
            await Task.Delay(100);
        }

        return false; // Timeout
    }

    public async Task<bool> ReleaseAsync() {
        // Release lock (only if we own it)
        if (!lockHeld) {
            return false;
        }

        // Lua script to atomically check and delete
        const string luaScript = @"
            if redis.call('get', KEYS[1]) == ARGV[1] then
                return redis.call('del', KEYS[1])
            else
                return 0
            end";

        var result = await redis.ScriptEvaluateAsync(
            luaScript,
            new RedisKey[] { lockKey },
            new RedisValue[] { lockValue }
        );

        if (result.Type == ResultType.Integer && (int)result == 1) {
            lockHeld = false;
            StopRenewal();
            return true;
        }

        return false; // Lock expired or held by another
    }

    private void StartRenewal() {
        // Start timer to renew lock before expiration
        renewalTimer = new Timer(async _ => {
            if (lockHeld) {
                await redis.KeyExpireAsync(lockKey, TimeSpan.FromSeconds(leaseTime));
            }
        }, null, TimeSpan.FromSeconds(leaseTime / 2), TimeSpan.FromSeconds(leaseTime / 2));
    }

    private void StopRenewal() {
        renewalTimer?.Dispose();
        renewalTimer = null;
    }
}

// Usage
var redis = ConnectionMultiplexer.Connect("localhost:6379");
var db = redis.GetDatabase();
var lock = new DistributedLock(db, "resource_lock", 10);

if (await lock.AcquireAsync(5)) {
    try {
        // Critical section
        Console.WriteLine("Doing work with lock held");
        await Task.Delay(5000);
    } finally {
        await lock.ReleaseAsync();
    }
}

Challenges and Solutions

Network Partitions

Problem: Network partition can cause split-brain (multiple lock holders).

Solution: Use majority consensus (like Redlock algorithm) or accept that locks are best-effort.

Clock Skew

Problem: Different nodes have different clocks, affecting lease expiration.

Solution: Use logical clocks or ensure clock synchronization (NTP).

Lock Holder Crash

Problem: If lock holder crashes, lock might never be released.

Solution: Use lease-based locks with automatic expiration.

Performance

Problem: Lock acquisition adds latency.

Solution: Use local locks when possible, minimize lock hold time, use optimistic locking when appropriate.

Use Cases

Database Updates

Ensure only one node updates a record at a time. Prevents race conditions and data corruption.

Scheduled Tasks

Ensure only one node runs a scheduled job. Prevents duplicate execution across multiple nodes.

Cache Invalidation

Coordinate cache invalidation across nodes. Prevents multiple nodes from invalidating cache simultaneously.

Resource Allocation

Coordinate access to limited resources (like API rate limits, connection pools).

Trade-offs

Advantages:

• Provides mutual exclusion across nodes
• Prevents race conditions
• Coordinates distributed operations

Disadvantages:

• Adds latency
• Single point of failure (lock service)
• Complex to implement correctly
• Network partitions can cause issues

Key Takeaways

Mutual Exclusion

Ensures only one node holds lock at a time. Provides coordination across distributed systems.

Lease-Based

Locks automatically expire after lease time. Prevents deadlocks from crashed nodes. Requires renewal.

Ownership Verification

Use unique value (UUID) to verify lock ownership before release. Prevents releasing locks held by others.

Atomic Operations

Use Lua scripts or atomic Redis commands for lock acquisition and release. Ensures correctness.

---

Next Steps

• Learn Leader Election - another coordination mechanism
• Master Distributed Transactions - locks used in transactions
• Understand Circuit Breaker - coordination patterns for resilience