# Consistent Hashing
Nodes and keys share one hash ring, and a key walks clockwise to the first node. A node leaving moves only its own arc.
**Time:** O(log n)
**Space:** O(n)
**Difficulty:** MEDIUM
*[Interactive widget: consistent-hashing-visualizer (Consistent Hashing Ring) — open the HTML page]*
Canonical: https://scaleengineer.com/algorithms/consistent-hashing
---
A cache fleet of four nodes routes every key with `hash(key) % 4`\. Add a fifth node and the formula turns into `hash(key) % 5`, and about four of every five keys suddenly belong somewhere else\. All of them miss at once, and the system behind the cache takes the full wave\. This remap storm fires on every scale\-out, every deploy, and every crashed node\.

Consistent hashing keeps the routing idea and drops the divisor\. Nodes and keys hash onto the same circle, and each key belongs to the first node it meets walking clockwise\. The figure above runs one with four nodes and twelve keys\. Press play: node D goes down, and only the keys in D's arc go looking for a new home\.

## The divisor is the problem

`hash(key) % N` has one flaw baked in: the N\. Every routing decision depends on the total node count, so any change to that count reshuffles every key\.

The figure below routes the twelve demo keys both ways, with the fleet already at four nodes and the moved keys highlighted\. Under `hash(key) % N`, `10` of the `12` keys change owner, and every highlighted chip is a cache miss\. On the ring, `3` of `12` move, exactly the keys in the arc the fourth node claims\. Switch the fleet back to three nodes and every highlight clears\.

*[Interactive widget: consistent-hashing-remap — open the HTML page]*

## Put nodes and keys on one ring

The ring removes the N from the formula\. Hash each node once and place it on a circle\. \(The figures use `0°` to `359°`\. Real systems use `0` to `2³²`\.\) Hash each key with the same function onto the same circle\. To find a key's owner, walk clockwise from the key and stop at the first node\. That node serves the key\.

No node's position depends on how many nodes exist, and that is the whole trick\. A key's walk can change only when the ring changes near the key: a node arriving or leaving inside its walking path\. Nothing else reaches the walk\.

The stretch of the circle a node answers for, from its predecessor clockwise to its own position, is its arc\. C's arc runs from B at `312°` around through `39°`, wrapping across the top of the ring\. The ring has no edges, so every walk eventually meets a node\.

Walk one lookup\. `doc:a1` hashes to `326°`\. Clockwise from there the walk crosses the top of the ring, where the count wraps from `359°` back to `0°`, and meets C at `39°`\. C owns the key\. The figure below replays this walk\. Type a key of your own and it takes its walk too\.

*[Interactive widget: consistent-hashing-visualizer — open the HTML page]*

## One node leaves, one arc moves

Now the payoff\. When D leaves the ring, only the keys inside D's arc lose their owner, because every other key still meets the same first node it met before\. The orphaned keys do what any lookup does: they keep walking clockwise, past D's empty spot, and stop at A\. Three keys move out of twelve\. The other nine never notice\.

Adding a node is the mirror image\. A new node claims the arc between its predecessor and itself, stealing that slice from its clockwise successor, the only node whose keys can move\. To watch both directions, scroll back to the first figure and click any node to remove or restore it: the counts on the node chips show one arc's share changing hands, and nothing else\.

A fair ring gives each node about `1/N` of the keys, so growing from N to N\+1 nodes moves about `1/(N+1)` of them\. The modulo column below comes from routing 1,000 keys; the ring column is the expected share:

| Fleet change | `hash(key) % N` | The ring |
| --- | --- | --- |
| 3 → 4 nodes | `78%` | `25%` |
| 4 → 5 nodes | `78%` | `20%` |
| 9 → 10 nodes | `91%` | `10%` |

## The code is a sorted list and a binary search

The whole routing structure fits in two parallel arrays\. `points` holds the node positions in sorted order, and `nodes` records who owns each point\. A lookup hashes the key, finds the first point at or past the key's hash with a binary search, and wraps the index around the end of the array\. That wrap is the ring closing\.

```python
import bisect

class HashRing:
	def __init__(self):
		self.points = []  # node positions, kept sorted
		self.nodes = []   # nodes[i] owns points[i]

	def _hash(self, value):
		h = 2166136261  # FNV offset basis
		for ch in value:
			h = (h ^ ord(ch)) * 16777619 % (1 << 32)
		return h

	def add_node(self, node):
		point = self._hash(node)
		index = bisect.bisect_left(self.points, point)
		self.points.insert(index, point)
		self.nodes.insert(index, node)

	def remove_node(self, node):
		index = self.nodes.index(node)
		self.points.pop(index)
		self.nodes.pop(index)

	def owner(self, key):
		index = bisect.bisect_left(self.points, self._hash(key))
		return self.nodes[index % len(self.nodes)]  # the ring closes
```

Adding or removing a node is one sorted insert or delete\. A lookup costs `O(log n)` in the number of points, the same probe loop as [binary search](/algorithms/binary-search) run over node positions instead of array cells\. The `_hash` here is FNV\. Any stable hash works in its place, but Python's own `hash()` is salted per process, so two runs would build two different rings\. The implementation panel below grows this skeleton with virtual nodes, which the next section motivates\.

## Real rings are lumpy

Hash positions are random, and four random points do not quarter a circle\. In the demo ring the arcs span `64°` to `108°`, and the twelve keys land 4, 3, 3, 2 across A, B, C, D\. More keys even out within an arc, but the arc sizes stay uneven, and the arc sizes set the shares\.

The fix is to stop betting on one point per node\. Each node plants many points on the ring, called virtual nodes, by hashing `A#0`, `A#1`, and so on\. The points of all four nodes interleave, the arcs shrink and average out, and the load converges on the fair share\. The figure below routes 4,000 keys for real\. With one point per node, the busiest node holds 2\.2 times the average while the quietest holds almost nothing\. With 128 points per node, every node sits within a few percent of the mean\.

*[Interactive widget: consistent-hashing-virtual-nodes — open the HTML page]*

The cost is memory, and it is small: 128 points per node is still only 512 sorted numbers here\. Virtual nodes also buy a second dial: give a bigger server more points and it takes a bigger share\.

## Where it earns its keep

Reach for the ring when keys must route to a changing set of owners and a remap is expensive:

- **Distributed caches\. **Memcached clients have shipped this as ketama hashing for years\. A crashed server costs its own arc of keys instead of the whole cache\.
- **Partitioned databases\. **DynamoDB and Cassandra place rows on the ring with virtual nodes, then replicate around it\.
- **Balancers\. **CDN edge selection and connection load balancing route by key so the same client keeps landing on the same machine\.

Skip the ring when the fleet is fixed and small: `hash(key) % N` is one line and everyone understands it\. Skip the ring also when the routing table must carry state: the ring decides placement and nothing more\.

The practice problems below are routing in miniature\. Build the bucket table first, then ask what happens to every key when the bucket count changes\. That question is the whole lesson\.

## Code examples

### Consistent-hash ring (Python)

```python
import bisect

class HashRing:
    """Consistent-hash ring: routes keys to the first node clockwise."""

    def __init__(self, replicas: int = 128) -> None:
        self.replicas = replicas
        self.points: list[int] = []   # sorted positions on the ring
        self.owners: list[str] = []   # owners[i] owns points[i]

    def _hash(self, value: str) -> int:
        h = 2166136261  # FNV offset basis; any stable hash works
        for ch in value:
            h = (h ^ ord(ch)) * 16777619 % (1 << 32)
        return h

    def add_node(self, node: str) -> None:
        for i in range(self.replicas):
            point = self._hash(f"{node}#{i}")
            index = bisect.bisect_left(self.points, point)
            self.points.insert(index, point)
            self.owners.insert(index, node)

    def remove_node(self, node: str) -> None:
        kept = [(p, o) for p, o in zip(self.points, self.owners) if o != node]
        self.points = [p for p, _ in kept]
        self.owners = [o for _, o in kept]

    def owner(self, key: str) -> str:
        if not self.points:
            raise ValueError("the ring has no nodes")
        index = bisect.bisect_left(self.points, self._hash(key))
        return self.owners[index % len(self.owners)]  # the ring closes

```

### Consistent-hash ring (JavaScript)

```javascript
/** Consistent-hash ring: routes keys to the first node clockwise. */
class HashRing {
  constructor(replicas = 128) {
    this.replicas = replicas;
    this.points = [];  // sorted positions on the ring
    this.owners = [];  // owners[i] owns points[i]
  }

  // FNV-1a with an avalanche step; any stable hash works.
  hash(value) {
    let h = 2166136261 >>> 0;
    for (const ch of value) {
      h ^= ch.codePointAt(0);
      h = Math.imul(h, 16777619) >>> 0;
    }
    h ^= h >>> 16;
    h = Math.imul(h, 0x7feb352d) >>> 0;
    h ^= h >>> 15;
    return h >>> 0;
  }

  // First index whose point is >= target; the caller wraps it.
  lowerBound(target) {
    let lo = 0;
    let hi = this.points.length - 1;
    while (lo <= hi) {
      const mid = (lo + hi) >> 1;
      if (this.points[mid] >= target) hi = mid - 1;
      else lo = mid + 1;
    }
    return lo;
  }

  addNode(node) {
    for (let i = 0; i < this.replicas; i += 1) {
      const point = this.hash(node + "#" + i);
      const index = this.lowerBound(point);
      this.points.splice(index, 0, point);
      this.owners.splice(index, 0, node);
    }
  }

  removeNode(node) {
    const kept = [];
    for (let i = 0; i < this.points.length; i += 1) {
      if (this.owners[i] !== node) kept.push([this.points[i], this.owners[i]]);
    }
    this.points = kept.map((pair) => pair[0]);
    this.owners = kept.map((pair) => pair[1]);
  }

  owner(key) {
    if (this.points.length === 0) throw new Error("the ring has no nodes");
    const index = this.lowerBound(this.hash(key)) % this.points.length;
    return this.owners[index];  // the ring closes
  }
}
```

### Consistent-hash ring (Java)

```java
import java.nio.charset.StandardCharsets;
import java.util.*;

public class ConsistentHash {
    private final int replicas;
    private final SortedMap<Long, String> ring = new TreeMap<>();

    public ConsistentHash(Collection<String> nodes, int replicas) {
        this.replicas = replicas;
        if (nodes != null) for (String n : nodes) addNode(n);
    }

    private static long hash(String s) {
        int h = 0x811C9DC5;
        for (byte b : s.getBytes(StandardCharsets.UTF_8)) {
            h ^= (b & 0xFF);
            h *= 0x01000193;
        }
        return Integer.toUnsignedLong(h);   // keep the ring unsigned
    }

    public void addNode(String node) {
        for (int i = 0; i < replicas; i++) {
            ring.putIfAbsent(hash(node + "#" + i), node);
        }
    }

    public void removeNode(String node) {
        ring.values().removeIf(n -> n.equals(node));
    }

    public String getNode(String key) {
        if (ring.isEmpty()) return null;
        SortedMap<Long, String> tail = ring.tailMap(hash(key));
        // tailMap is the clockwise arc; empty means we wrapped past the top
        return tail.isEmpty() ? ring.get(ring.firstKey()) : tail.get(tail.firstKey());
    }
}
```

### Consistent-hash ring (C)

```c
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define CH_MAX_NAME 64

typedef struct { uint32_t hash; char node[CH_MAX_NAME]; } RingEntry;

typedef struct {
    RingEntry *ring;      /* sorted ascending by hash */
    size_t len, cap;
    size_t replicas;
} ConsistentHash;

static uint32_t ch_hash(const char *s) {
    uint32_t h = 0x811C9DC5u;
    for (const unsigned char *p = (const unsigned char *)s; *p; ++p) {
        h ^= *p;
        h *= 0x01000193u;
    }
    return h;
}

/* First index with ring[i].hash >= h, else len. */
static size_t ch_lower_bound(const ConsistentHash *ch, uint32_t h) {
    size_t lo = 0, hi = ch->len;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (ch->ring[mid].hash < h) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

ConsistentHash *ch_create(size_t replicas) {
    if (replicas == 0) return NULL;
    ConsistentHash *ch = calloc(1, sizeof *ch);
    if (!ch) return NULL;
    ch->replicas = replicas;
    return ch;
}

void ch_free(ConsistentHash *ch) {
    if (!ch) return;
    free(ch->ring);
    free(ch);
}

/* Returns 0 on success, -1 on allocation failure. */
int ch_add_node(ConsistentHash *ch, const char *node) {
    for (size_t i = 0; i < ch->replicas; ++i) {
        char buf[CH_MAX_NAME + 24];
        snprintf(buf, sizeof buf, "%s#%zu", node, i);
        uint32_t h = ch_hash(buf);

        size_t pos = ch_lower_bound(ch, h);
        if (pos < ch->len && ch->ring[pos].hash == h) continue;  /* collision */

        if (ch->len == ch->cap) {
            size_t cap = ch->cap ? ch->cap * 2 : 64;
            RingEntry *tmp = realloc(ch->ring, cap * sizeof *tmp);
            if (!tmp) return -1;
            ch->ring = tmp;
            ch->cap = cap;
        }
        memmove(ch->ring + pos + 1, ch->ring + pos,
                (ch->len - pos) * sizeof *ch->ring);
        ch->ring[pos].hash = h;
        snprintf(ch->ring[pos].node, CH_MAX_NAME, "%s", node);
        ch->len++;
    }
    return 0;
}

void ch_remove_node(ConsistentHash *ch, const char *node) {
    size_t w = 0;
    for (size_t r = 0; r < ch->len; ++r) {
        if (strcmp(ch->ring[r].node, node) != 0) ch->ring[w++] = ch->ring[r];
    }
    ch->len = w;
}

/* Returns a pointer into the ring, or NULL if empty. Do not free. */
const char *ch_get_node(const ConsistentHash *ch, const char *key) {
    if (ch->len == 0) return NULL;
    size_t pos = ch_lower_bound(ch, ch_hash(key));
    if (pos == ch->len) pos = 0;             /* wrap */
    return ch->ring[pos].node;
}
```

### Consistent-hash ring (CPP)

```cpp
#include <algorithm>
#include <cstdint>
#include <string>
#include <vector>

class ConsistentHash {
public:
    explicit ConsistentHash(const std::vector<std::string>& nodes = {},
                            std::size_t replicas = 150)
        : replicas_(replicas) {
        for (const auto& n : nodes) addNode(n);
    }

    void addNode(const std::string& node) {
        for (std::size_t i = 0; i < replicas_; ++i) {
            uint32_t h = hash(node + "#" + std::to_string(i));
            auto it = std::lower_bound(ring_.begin(), ring_.end(), h,
                [](const Entry& e, uint32_t v) { return e.hash < v; });
            if (it != ring_.end() && it->hash == h) continue;   // collision: skip
            ring_.insert(it, Entry{h, node});
        }
    }

    void removeNode(const std::string& node) {
        ring_.erase(std::remove_if(ring_.begin(), ring_.end(),
            [&](const Entry& e) { return e.node == node; }), ring_.end());
    }

    std::string getNode(const std::string& key) const {
        if (ring_.empty()) return {};
        uint32_t h = hash(key);
        auto it = std::lower_bound(ring_.begin(), ring_.end(), h,
            [](const Entry& e, uint32_t v) { return e.hash < v; });
        if (it == ring_.end()) it = ring_.begin();             // wrap
        return it->node;
    }

private:
    struct Entry { uint32_t hash; std::string node; };

    static uint32_t hash(const std::string& s) {
        uint32_t h = 0x811C9DC5u;
        for (unsigned char c : s) { h ^= c; h *= 0x01000193u; }
        return h;
    }

    std::size_t replicas_;
    std::vector<Entry> ring_;   // sorted ascending by hash
};
```

### Consistent-hash ring (CSharp)

```csharp
using System;
using System.Collections.Generic;
using System.Text;

public class ConsistentHash
{
    private readonly int replicas;
    private readonly List<uint> sortedHashes = new();
    private readonly Dictionary<uint, string> nodeOf = new();

    public ConsistentHash(IEnumerable<string> nodes = null, int replicas = 150)
    {
        if (replicas <= 0) throw new ArgumentOutOfRangeException(nameof(replicas));
        this.replicas = replicas;
        if (nodes != null) foreach (var n in nodes) AddNode(n);
    }

    private static uint Hash(string s)
    {
        unchecked   // FNV-1a relies on 32-bit wraparound
        {
            uint h = 0x811C9DC5;
            foreach (byte b in Encoding.UTF8.GetBytes(s))
            {
                h ^= b;
                h *= 0x01000193;
            }
            return h;
        }
    }

    public void AddNode(string node)
    {
        for (int i = 0; i < replicas; i++)
        {
            uint h = Hash($"{node}#{i}");
            if (nodeOf.ContainsKey(h)) continue;           // collision: skip

            int idx = sortedHashes.BinarySearch(h);
            if (idx < 0) idx = ~idx;                       // ~ gives insertion point
            sortedHashes.Insert(idx, h);
            nodeOf[h] = node;
        }
    }

    public void RemoveNode(string node)
    {
        var doomed = new List<uint>();
        foreach (var kv in nodeOf) if (kv.Value == node) doomed.Add(kv.Key);

        foreach (uint h in doomed)
        {
            nodeOf.Remove(h);
            int idx = sortedHashes.BinarySearch(h);
            if (idx >= 0) sortedHashes.RemoveAt(idx);
        }
    }

    public string GetNode(string key)
    {
        if (sortedHashes.Count == 0) return null;

        int idx = sortedHashes.BinarySearch(Hash(key));
        if (idx < 0) idx = ~idx;
        if (idx == sortedHashes.Count) idx = 0;            // wrap around the ring
        return nodeOf[sortedHashes[idx]];
    }
}
```