DEV Community: Tan Nguyen Phuong

Consistent Hashing: Distributing Load Without a Full Reshuffle

Tan Nguyen Phuong — Mon, 31 Aug 2026 06:53:49 +0000

Consistent Hashing: Distributing Load Without a Full Reshuffle

Naive hashing (hash(key) % N) works fine until you add or remove a node — then N changes and almost every key maps to a different server. For a distributed cache or shard, that means a near-total cache miss storm or a mass data migration, right when you can least afford it.

Consistent hashing fixes this by mapping both nodes and keys onto the same ring, so a topology change only remaps the keys between the changed node and its neighbor.

The Ring

graph LR
    subgraph Ring["Hash Ring (0 to 2^32-1)"]
        NA((Node A))
        NB((Node B))
        NC((Node C))
        K1[key1] -.-> NB
        K2[key2] -.-> NC
        K3[key3] -.-> NA
    end

Each node is hashed onto the ring (often multiple times — see "Virtual Nodes" below). To find which node owns a key, hash the key and walk clockwise until you hit the first node.

Adding or Removing a Node

When node B leaves, only the keys that were mapped to B move — to B's clockwise neighbor. Every other key stays exactly where it was. That's the whole point: roughly 1/N of the keyspace moves per topology change, not the whole keyspace.

Virtual Nodes (Replicas)

Hashing raw node names onto the ring directly creates hot spots — some nodes end up owning much bigger arcs than others. The fix: hash each node multiple times, e.g. node-A#0, node-A#1, ..., node-A#149 (150 virtual nodes is a common default). More virtual nodes means smoother distribution, at the cost of a bigger in-memory ring.

Implementation

:::tabs

class ConsistentHash
{
    private array $ring = [];
    private array $sortedKeys = [];
    private int $replicas;

    public function __construct(int $replicas = 150)
    {
        $this->replicas = $replicas;
    }

    public function addNode(string $node): void
    {
        for ($i = 0; $i < $this->replicas; $i++) {
            $this->ring[$this->hash("$node#$i")] = $node;
        }
        $this->sortedKeys = $this->sortedRingKeys();
    }

    public function getNode(string $key): ?string
    {
        if (empty($this->sortedKeys)) {
            return null;
        }

        $hash = $this->hash($key);
        foreach ($this->sortedKeys as $ringKey) {
            if ($ringKey >= $hash) {
                return $this->ring[$ringKey];
            }
        }

        return $this->ring[$this->sortedKeys[0]];
    }

    private function sortedRingKeys(): array
    {
        $keys = array_keys($this->ring);
        sort($keys);
        return $keys;
    }

    private function hash(string $value): int
    {
        return crc32($value);
    }
}

import bisect
import zlib


class ConsistentHash:
    def __init__(self, replicas: int = 150):
        self.replicas = replicas
        self.ring: dict[int, str] = {}
        self.sorted_keys: list[int] = []

    def add_node(self, node: str) -> None:
        for i in range(self.replicas):
            self.ring[self._hash(f"{node}#{i}")] = node
        self.sorted_keys = sorted(self.ring.keys())

    def get_node(self, key: str) -> str | None:
        if not self.sorted_keys:
            return None

        h = self._hash(key)
        index = bisect.bisect_left(self.sorted_keys, h)
        if index == len(self.sorted_keys):
            index = 0

        return self.ring[self.sorted_keys[index]]

    @staticmethod
    def _hash(value: str) -> int:
        return zlib.crc32(value.encode())

:::

Common Pitfalls

Too few virtual nodes leads to uneven load, with hot spots on a handful of physical nodes. Using a weak or poorly-distributed hash function makes the same problem worse — prefer something like CRC32 or xxHash over a naive sum-of-bytes hash. Forgetting to remove all of a node's virtual nodes on removal leaves ghost entries that route traffic to a dead server. And rehashing the entire keyspace on every topology change defeats the whole purpose — only the ring should change, not every key's mapping.

When to Reach for This

Distributed caches doing client-side sharding, CDN edge selection, distributed hash tables, sharded databases, and load balancers that need session affinity without a central coordinator. If your cluster size is fixed and rarely changes, plain modulo hashing is simpler and perfectly fine.

Originally published at https://cslant.com/tips/consistent-hashing-distributing-load-without-a-full-reshuffle

Database Deadlocks: Detection, Diagnosis, and Prevention

Tan Nguyen Phuong — Thu, 27 Aug 2026 12:16:04 +0000

Database Deadlocks: Detection, Diagnosis, and Prevention

A deadlock happens when two or more transactions each hold a lock the other needs, and neither can proceed. Databases don't let this hang forever — they detect it and kill one of the transactions. Understanding how that detection works, and how to avoid triggering it in the first place, is a core skill for anyone writing high-concurrency database code.

The Classic Deadlock

Two transactions, two rows, opposite order:

-- Transaction A
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
-- ... pauses ...
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
COMMIT;

-- Transaction B (running concurrently)
BEGIN;
UPDATE accounts SET balance = balance - 50 WHERE id = 2;
-- ... pauses ...
UPDATE accounts SET balance = balance + 50 WHERE id = 1;
COMMIT;

If A locks row 1 and B locks row 2 at nearly the same time, A's second statement waits for B to release row 2, while B's second statement waits for A to release row 1. Neither can ever proceed.

Wait-For Graphs: How Databases Detect This

Most databases (PostgreSQL, MySQL/InnoDB, SQL Server) model lock waits as a directed graph: each transaction is a node, and an edge from T1 to T2 means "T1 is waiting on a lock held by T2." A deadlock exists exactly when this graph contains a cycle.

graph TD
    A[Transaction A] -->|waits for row 2| B[Transaction B]
    B[Transaction B] -->|waits for row 1| A[Transaction A]
    A -.cycle detected.-> C[Deadlock!]
    C --> D[Database picks a victim]
    D --> E[Victim transaction rolled back]
    E --> F[Survivor proceeds]

Periodically (or on every new lock wait, depending on the engine), the database walks this graph looking for cycles. When it finds one, it picks a victim — usually the transaction that has done the least work, or holds the fewest locks — and rolls it back, releasing its locks so the other transaction can continue.

What the Error Actually Looks Like

ERROR: deadlock detected
DETAIL: Process 1234 waits for ShareLock on transaction 5678; blocked by process 5678.
Process 5678 waits for ShareLock on transaction 1234; blocked by process 1234.
HINT: See server log for query details.

The application's job is to catch this specific error and retry the transaction — a deadlock victim is not a bug, it's the database correctly resolving an unavoidable conflict.

import time

def run_with_retry(fn, max_attempts=3):
    for attempt in range(max_attempts):
        try:
            return fn()
        except DeadlockDetected:
            if attempt == max_attempts - 1:
                raise
            time.sleep(0.05 * (2 ** attempt))  # exponential backoff

Deadlocks vs. Ordinary Lock Waits

An ordinary lock wait resolves itself once the holding transaction commits or rolls back — no cycle, no error, just a delay. A deadlock is fundamentally different: without intervention, it never resolves on its own, because every party in the cycle is waiting on another party in the same cycle. This is why detection has to be active (scanning for cycles), not passive (just waiting things out).

Prevention: Consistent Lock Ordering

The single most effective prevention technique is to always acquire locks in the same order across every transaction that touches the same set of resources. If both transactions above had updated row 1 before row 2, the second one to arrive would simply wait for the first to finish — no cycle possible.

-- Both transactions now lock in ascending id order — no deadlock possible
UPDATE accounts SET balance = balance - 100 WHERE id = LEAST(1, 2);
UPDATE accounts SET balance = balance + 100 WHERE id = GREATEST(1, 2);

In practice this often means sorting rows by primary key before issuing a batch of updates, or centralizing the lock-acquisition order in a single code path rather than leaving it to each caller.

Prevention: Keep Transactions Short

Long-running transactions hold locks longer, which widens the window during which a conflicting transaction can show up and create a cycle. Moving non-essential work (sending emails, calling external APIs, heavy computation) outside the transaction boundary shrinks that window significantly.

Prevention: Lower Isolation Where Safe

Higher isolation levels take more locks for longer. SERIALIZABLE is the most deadlock-prone; READ COMMITTED takes fewer, shorter-held locks. Not every operation needs the strongest guarantee — evaluate whether a lower isolation level is safe for a given transaction before defaulting to the strictest one everywhere.

Prevention: Smaller Lock Footprint

Locking an entire table when you only need a few rows multiplies the chance of collision. Use indexed WHERE clauses so the database can take row-level (not table-level) locks, and avoid SELECT ... FOR UPDATE over more rows than the transaction actually intends to modify.

Diagnosing Recurring Deadlocks

When deadlocks show up repeatedly in production, look at the database's deadlock log (PostgreSQL logs full lock and query detail when log_lock_waits is on; MySQL exposes SHOW ENGINE INNODB STATUS). The recurring pattern is almost always the same two code paths acquiring the same two resources in opposite order — find those two call sites and fix the ordering, rather than just adding retry logic and hoping.

Common Pitfalls

Treating deadlocks purely as something to retry around, without ever fixing the underlying lock-order conflict, just moves the cost to increased latency and wasted work under load. Assuming an ORM's default query patterns are deadlock-safe is risky — many ORMs issue related updates in whatever order model associations happen to be traversed, which can vary between requests. And forgetting to add retry logic entirely means a deadlock becomes a user-facing error instead of an invisible, automatically-recovered hiccup.

A deadlock isn't a failure of the database — it's the database correctly refusing to let two transactions wait on each other forever. The fix lives in your application's lock ordering, not in disabling detection.

Originally published at https://cslant.com/tips/database-deadlocks-detection-diagnosis-and-prevention

Distributed Locking with Redis: Understanding the Redlock Algorithm

Tan Nguyen Phuong — Mon, 24 Aug 2026 04:42:31 +0000

Distributed Locking with Redis: Understanding the Redlock Algorithm

A single Redis instance makes a fine lock for a single-process app, but the moment you have multiple services racing to acquire the same lock — and that Redis instance can fail — a naive SETNX isn't safe anymore. Redlock, proposed by Redis's creator, is an algorithm for acquiring a distributed lock across multiple independent Redis nodes so that no single node's failure or slowness can silently break mutual exclusion.

This is genuinely advanced material — understanding it requires comfort with distributed systems failure modes, not just Redis commands.

Why a Single Redis Lock Isn't Enough

A basic lock looks simple:

SET resource:order-42 my-random-value NX PX 30000

This sets the key only if it doesn't exist (NX), with a 30-second expiry (PX) so a crashed client doesn't hold the lock forever. The problem is that this single Redis node is a single point of failure. If it goes down before replicating the write to a replica, and the replica gets promoted to master, another client can acquire the "same" lock — because the new master never saw the key.

The Redlock Algorithm

Redlock solves this by using N independent Redis masters (the reference implementation uses 5), with no replication or coordination between them. A client wanting the lock does the following:

Get the current time in milliseconds.
Try to acquire the lock on all N instances sequentially, using the same key and a random value, with a small timeout per instance so a down node doesn't stall the whole process.
Compute elapsed time. The lock is considered acquired only if the client got the lock on a majority (N/2 + 1) of instances, and the total elapsed time is less than the lock's validity time.
If acquired, the effective validity time is the original TTL minus the elapsed time and clock drift.
If the lock wasn't acquired, release it on every instance immediately, whether or not that instance thought it succeeded.

graph TD
    A[Client wants lock] --> B[Record start time T1]
    B --> C[Try SET NX PX on Redis Node 1]
    B --> D[Try SET NX PX on Redis Node 2]
    B --> E[Try SET NX PX on Redis Node 3]
    B --> F[Try SET NX PX on Redis Node 4]
    B --> G[Try SET NX PX on Redis Node 5]
    C --> H{Count successes}
    D --> H
    E --> H
    F --> H
    G --> H
    H -->|Majority acquired AND time OK| I[Lock acquired]
    H -->|Majority failed OR time expired| J[Release lock on all nodes]
    J --> K[Retry after random backoff]

Why Majority Matters

Requiring a majority (not all N) means Redlock tolerates the failure of a minority of nodes — with 5 nodes, up to 2 can be down or unreachable and the lock still works correctly, the same fault-tolerance principle behind Raft and Paxos-based systems. It also prevents split-brain: two clients can't both get a majority of 5 nodes simultaneously, because any two majorities of 5 must overlap by at least one node.

The Random Value and Safe Release

Each client generates a unique random value for its lock attempt (not just any placeholder). Releasing the lock must check that the stored value still matches before deleting it, done atomically via a Lua script:

if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
else
    return 0
end

Without this check, a client could accidentally delete a lock it no longer owns — for example, if its own lock expired and a different client acquired it in the meantime.

Clock Drift: The Real Weakness

Redlock's correctness assumes clocks across the N nodes don't drift too far apart relative to the lock's TTL. If a node's clock jumps forward unexpectedly (a bad NTP sync, a VM pause-and-resume, manual clock changes), that node might expire a lock much earlier than the others believe, opening a window where two clients think they hold the lock simultaneously. This is the core of Martin Kleppmann's well-known critique of Redlock: it depends on real-time clock behavior in ways that are hard to fully guarantee.

Fencing Tokens: The Practical Fix

Even with Redlock done correctly, a paused client (GC pause, VM suspend, network partition) can wake up after its lock has expired and still act as if it holds it — writing to a shared resource after another client has already acquired the lock and moved on. The standard mitigation is a fencing token: a monotonically increasing number returned every time a lock is granted.

Client A acquires lock, gets token 33
Client A pauses (GC, network delay...)
Client A's lock expires
Client B acquires lock, gets token 34
Client B writes to storage, tagging the write with token 34
Client A wakes up, tries to write with token 33
Storage rejects it: 33 < 34 (already saw a higher token)

The protected resource itself — a database, a file store, an API — must be the one enforcing the token check. Redlock alone cannot make this guarantee; it can only reduce the likelihood of two clients believing they hold the lock at once.

When to Use Redlock (and When Not To)

Redlock is a reasonable choice for efficiency locks — cases where a duplicate execution is wasteful but not catastrophic, like preventing the same cron-triggered job from running twice, or coalescing duplicate cache-rebuild requests. It is a risky choice for correctness locks — cases where a duplicate execution corrupts data, like coordinating writes to a financial ledger. For those, use a system with strong consistency guarantees (a consensus-based lock service like ZooKeeper or etcd) combined with fencing tokens enforced by the resource itself, not just Redis.

Common Pitfalls

Using an even number of nodes defeats the majority-quorum logic that makes Redlock resilient — always use an odd number so a majority is unambiguous. Setting per-node acquisition timeouts too high means a single slow node can blow past your lock's TTL before you've even finished the acquisition phase. And treating Redlock as a strict correctness guarantee, rather than a best-effort mutual exclusion mechanism, is the mistake that leads to production incidents — pair it with fencing tokens whenever the operation it protects actually matters.

Redlock reduces the probability of a broken lock; it does not eliminate it. Design your protected operations to survive the case where the lock briefly fails.

Originally published at https://cslant.com/tips/distributed-locking-with-redis-understanding-the-redlock-algorithm