Consistent Hash Ring for Shard Routing

A messaging app routes each conversation to a database shard with a consistent hash ring. Every shard owns several virtual node positions on a ring of integers; a key is owned by the first position at or after the key's hash, wrapping around to the smallest position after the end.

addNode(name, points) adds a shard with the given ring positions (its virtual nodes).
removeNode(name) removes the shard and all its positions.
getNode(keyHash) returns the owning shard name, or null if the ring is empty. If several positions are equal, the shard with the alphabetically smaller name wins.

Hashing is done by the caller, so the problem focuses on the ring itself. See Resharding and Moving Data Online.

Example 1

Input: ["HashRing","addNode","addNode","getNode","getNode","getNode","getNode","getNode","removeNode","getNode","getNode"]
[[],["db1",[10,50]],["db2",[30,70]],[5],[10],[11],[60],[80],["db1"],[5],[80]]
Output: [null,null,null,"db1","db1","db2","db2","db1",null,"db2","db2"]
Explanation: 80 is past the last position (70), so it wraps to db1's position 10. After db1 is removed, everything belongs to db2.

Solution and explanation

Show the solution

Time getNode O(log V); add/remove O(V log V) · Space O(V)

Store every virtual node as a (position, name) pair in a list sorted by position (then name). Lookup is a binary search for the first position ≥ the key's hash, wrapping to the first entry when the hash is past the end — O(log V). Adding a shard only takes over the arcs just before its new positions, so only those keys move; with modulo hashing almost every key would move. Many virtual nodes per shard smooth out the distribution.

Reference solution

class HashRing {
  constructor() {
    this.points = []; // [position, name], sorted
  }

  addNode(name, points) {
    for (const p of points) this.points.push([p, name]);
    this.points.sort((a, b) => a[0] - b[0] || (a[1] < b[1] ? -1 : a[1] > b[1] ? 1 : 0));
  }

  removeNode(name) {
    this.points = this.points.filter(([, n]) => n !== name);
  }

  getNode(keyHash) {
    if (this.points.length === 0) return null;
    let lo = 0, hi = this.points.length;           // first index with position >= keyHash
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.points[mid][0] < keyHash) lo = mid + 1; else hi = mid;
    }
    return this.points[lo % this.points.length][1];
  }
}

class HashRing {
  private points: [number, string][] = [];

  addNode(name: string, points: number[]): void {
    for (const p of points) this.points.push([p, name]);
    this.points.sort((a, b) => a[0] - b[0] || a[1].localeCompare(b[1]));
  }

  removeNode(name: string): void {
    this.points = this.points.filter(([, n]) => n !== name);
  }

  getNode(keyHash: number): string | null {
    if (this.points.length === 0) return null;
    let lo = 0, hi = this.points.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.points[mid][0] < keyHash) lo = mid + 1; else hi = mid;
    }
    return this.points[lo % this.points.length][1];
  }
}

import bisect

class HashRing:
    def __init__(self):
        self.points: list[tuple[int, str]] = []

    def add_node(self, name: str, points: list[int]) -> None:
        self.points.extend((p, name) for p in points)
        self.points.sort()

    def remove_node(self, name: str) -> None:
        self.points = [p for p in self.points if p[1] != name]

    def get_node(self, key_hash: int) -> str | None:
        if not self.points:
            return None
        i = bisect.bisect_left(self.points, (key_hash, ""))
        return self.points[i % len(self.points)][1]

<?php

class HashRing
{
    /** @var array<int, array{0: int, 1: string}> */
    private array $points = [];

    public function addNode(string $name, array $points): void
    {
        foreach ($points as $p) {
            $this->points[] = [$p, $name];
        }
        usort($this->points, fn ($a, $b) => [$a[0], $a[1]] <=> [$b[0], $b[1]]);
    }

    public function removeNode(string $name): void
    {
        $this->points = array_values(array_filter($this->points, fn ($p) => $p[1] !== $name));
    }

    public function getNode(int $keyHash): ?string
    {
        $n = count($this->points);
        if ($n === 0) {
            return null;
        }
        $lo = 0;
        $hi = $n;
        while ($lo < $hi) {
            $mid = intdiv($lo + $hi, 2);
            if ($this->points[$mid][0] < $keyHash) {
                $lo = $mid + 1;
            } else {
                $hi = $mid;
            }
        }
        return $this->points[$lo % $n][1];
    }
}

class HashRing {
    private final List<Object[]> points = new ArrayList<>();   // {Integer position, String name}

    public HashRing() {}

    public void addNode(String name, int[] positions) {
        for (int p : positions) points.add(new Object[]{p, name});
        points.sort(Comparator.<Object[]>comparingInt(a -> (Integer) a[0]).thenComparing(a -> (String) a[1]));
    }

    public void removeNode(String name) {
        points.removeIf(p -> p[1].equals(name));
    }

    public String getNode(int keyHash) {
        if (points.isEmpty()) return null;
        int lo = 0, hi = points.size();
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if ((Integer) points.get(mid)[0] < keyHash) lo = mid + 1; else hi = mid;
        }
        return (String) points.get(lo % points.size())[1];
    }
}

Common mistakes

Forgetting the wrap-around past the largest position.
Using > instead of ≥ for the owning position.
Unstable tie-breaking when positions collide.

Follow-up questions

Weight shards by giving bigger servers more virtual nodes.
Return the next N distinct shards for replication.

Example 1

Hints

Write and run your solution

Solution and explanation

Reference solution

Common mistakes

Follow-up questions

Example 1

Hints

Write and run your solution

Solution and explanation

Reference solution

Common mistakes

Follow-up questions

More Design & Data Structures problems