Consistent Hashing を Python で作ってみた

2026年6月3日4 min

backendpython

最近読み進めているシステム設計の面接試験に Consistent Hashing（コンシステントハッシュ法）の章が出てきたので、Python で書いて動作をみてみました。

なぜ `hash(key) % N` ではダメなのか

N 台のキャッシュサーバにキーを分散したいとき、いちばん素朴な方法は剰余を取ることです。

server = hash(key) % N

均等には分散できるのですが、これには大きな弱点があります。サーバを 1 台増減すると分母が変わり、ほとんど全部のキーの割り当て先がズレてしまいます。これだとノードを 1 台足すたびにキャッシュがほぼ全ミスになり、DB へ問い合わせが殺到します。

リング上を時計回りに探す

コンシステントハッシュは、ハッシュ空間を巨大なリングに見立てます。

サーバ名もキーも同じハッシュ関数で数値に変換し、リング上の座標とみなす
キーは、時計回りに進んで最初に出会ったサーバに割り当てる

リングを一直線に伸ばしたイメージ:

  0 ─────●───────────●──────────●──────────► 2^32
        cache1      cache2      cache0
                ↑
            product:42 はここ → 時計回り最寄りの cache2 へ

この仕組みのうれしいところは、ノードを 1 台足しても、そのノードが新しく担当する円弧の分のキーしか動かないことです。残りのキーの割り当ては一切変わりません。

実装

リングの実体は円ではなく、ハッシュ値を昇順に並べたソート済み配列です。末尾まで行ったら先頭に戻ることで円環を表現します。時計回りの最寄りは、キーのハッシュ値以上の最小値を探すことなので、bisect で二分探索すれば O(log N) で探せます。

import bisect
import hashlib


def hash_value(key: str) -> int:
    # サーバ名もキーも同じ関数でリング上の座標に変換する。
    # MD5 の出力 128bit のうち先頭 32bit だけ使い、0〜約42億に収める。
    # 暗号強度は目的ではなく、リング上の位置として散らばればよい。
    h = hashlib.md5(key.encode()).hexdigest()
    return int(h[:8], 16)


class ConsistentHashRing:
    def __init__(self, replicas: int = 100):
        # replicas: 1 台のサーバをリング上に何個の点として置くか（仮想ノード）
        self.replicas = replicas
        self._ring: dict[int, str] = {}   # { ハッシュ値: サーバ名 }
        self._keys: list[int] = []        # ハッシュ値を昇順に並べた配列（二分探索用）

    def add_server(self, server: str) -> None:
        # 1 台につき replicas 個の点を打つ。名前に添字を混ぜて別々の位置に散らす。
        for i in range(self.replicas):
            self._ring[hash_value(f"{server}#{i}")] = server
        self._keys = sorted(self._ring)   # 常にソート済みを維持

    def get_server(self, key: str) -> str:
        h = hash_value(key)
        # 「h 以上の最小値」の位置を二分探索。末尾を超えたら % で先頭へ折り返す。
        idx = bisect.bisect_left(self._keys, h) % len(self._keys)
        return self._ring[self._keys[idx]]

仮想ノード

実サーバをリング上に 1 点だけ置くと、間隔が運任せになって担当範囲が偏ります。そこで add_server では 1 台を cache0#0, cache0#1, … と添字付きで何個もの点に分身させてリング全体に散らします。これを仮想ノードと呼びます。

各サーバを 3 点ずつに「分身」させてリングに置く（c0_* = cache0, c1_* = cache1, c2_* = cache2）:

  0 ──c1_0──c0_0──c2_0──c1_1──c0_1──c2_1──c1_2──c0_2──c2_2── 42億

  c1_0 / c1_1 / c1_2 は名前が違うだけで全部 cache1 の点。物理サーバは 1 台のまま。

点を増やすほど間隔が均され、各サーバの担当量が 1/N に近づきます。

動かしてみる

仮想ノードで分散はどれだけ均等になるか

3 台のサーバに 30,000 個のキーを割り当て、各サーバの担当割合を replicas（仮想ノード数）を変えて比べます。

for replicas in [1, 10, 100, 500]:
    ring = ConsistentHashRing(replicas=replicas)
    for s in ["cache0", "cache1", "cache2"]:
        ring.add_server(s)

    counts = {s: 0 for s in ["cache0", "cache1", "cache2"]}
    for i in range(30000):
        counts[ring.get_server(f"product:{i}")] += 1

結果（理想は各サーバ 33.3% ずつ）:

replicas = 1
  cache0: ██████··································  16.0%
  cache1: ███████████████████████·················  56.8%
  cache2: ███████████·····························  27.2%

replicas = 10
  cache0: █████████·······························  23.0%
  cache1: █████████████···························  32.3%
  cache2: ██████████████████······················  44.7%

replicas = 100
  cache0: ████████████████························  39.6%
  cache1: ████████████····························  30.9%
  cache2: ████████████····························  29.5%

replicas = 500
  cache0: ██████████████··························  34.6%
  cache1: █████████████···························  32.6%
  cache2: █████████████···························  32.8%

replicas=1（仮想ノードなし）だと cache1 が 56.8% も抱えてしまっています。点を増やすほど、値が近づいていき replicas=500 ではほぼ理想の三等分になりました。

ノードを 1 台足したとき、何割のキーが動くか

ノードを 3 台 → 4 台に増やしたときに割り当て先が変わったキーの数を、シンプルにサーバーの台数でモジュロを取る (% N) 方式と比べます。

コンシステントハッシュ : 7185 / 30000 移動 (23.9%)   ← 理論値 ≒ 1/4 = 25%
% N 方式            : 22584 / 30000 移動 (75.3%)   ← ほぼ全滅

% N 方式は分母が 3 → 4 に変わった瞬間に剰余の結果が総入れ替えになり、約 75% のキーが移動しています。

一方コンシステントハッシュは 23.9% しか動いてません。これは新しく入った cache3 が担当する円弧（リング全体の約 1/4）に乗っていたキーだけが移動し、それ以外は元のサーバに留まるためです。理論値の 1/4 = 25% ともよく一致しています。

おわりに

剰余 1 行を、リング + 二分探索 + 仮想ノードに置き換えるだけで、スケールアウト時の挙動がここまで変わるのは面白いですね。

なぜ hash(key) % N ではダメなのか