コンシステントハッシュ法

なぜ mod N では困るのか

複数のサーバーにキーを振り分ける最も素朴な方法は、ハッシュ値をノード数で割った余りを使う node = hash(key) % N です。N が固定なら高速で均等ですが、N が変わった瞬間に破綻します。

たとえば N=4 から N=5 へ1台増やすと、各キーの割り当ては hash(key) % 4 から hash(key) % 5 に変わります。余りの周期が変わるため、ほとんどのキーが別のノードへ移動します。分散キャッシュなら大半のエントリがキャッシュミスになり、シャーディングなら大量のデータ再配置（リシャーディング）が走ります。

リング構造：時計回りの担当決め

コンシステントハッシュ法では、ハッシュ関数の出力空間（たとえば 0 から 2^32 − 1）を**端と端をつないだ環（リング）**とみなします。ここに2種類の点を配置します。

• ノード: 各サーバーの識別子（IP やホスト名）をハッシュした値をリング上の位置とする。
• キー: データのキーをハッシュした値をリング上の位置とする。

割り当てルールは単純です。あるキーの位置から時計回りに進み、最初に出会ったノードがそのキーの担当になります。各ノードは「自分の手前のノードから自分まで」の円弧区間を受け持ちます。

リング（0 → 最大値 → 0 に戻る）

        [Node A]
       /         \
  key3            key1
   |                |
 [Node C] ------- [Node B]
       \         /
        key2 ─→ 時計回りで最初のノードが担当

key1 → Node B（key1 の右隣のノード）
key2 → Node C
key3 → Node A

この構造の利点は局所性です。ノードを1台追加すると、新ノードはリング上の1点に入り、その直前区間を担当していた1台からだけキーを引き取ります。他のノードの担当区間は一切変わりません。ノードを1台削除した場合も同様に、その担当ぶんが時計回りの次のノードへ吸収されるだけで、無関係なキーは動きません。

検索の実装：ソート済みリングを二分探索

リングは実装上、ノード位置をソートした配列（または平衡木）として持ちます。キーの担当ノードを引くには、キーのハッシュ値以上で最小のノード位置を探せばよく、二分探索で O(log N) で求まります。配列末尾を超えたら先頭へ折り返す（環なので）点だけ注意します。

import bisect, hashlib

class HashRing:
    def __init__(self):
        self.ring = {}       # 位置 -> ノード
        self.sorted_keys = []  # ソート済みの位置リスト

    def _hash(self, s):
        return int(hashlib.md5(s.encode()).hexdigest(), 16)

    def add_node(self, node):
        pos = self._hash(node)
        self.ring[pos] = node
        bisect.insort(self.sorted_keys, pos)

    def get_node(self, key):
        if not self.ring:
            return None
        h = self._hash(key)
        # h 以上で最小の位置を探す。末尾を超えたら先頭へ折り返す
        i = bisect.bisect_left(self.sorted_keys, h) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[i]]

bisect_left の結果を要素数で割った余りを取ることで、環の折り返し（最大値を超えたキーは先頭ノードへ）を自然に表現しています。

仮想ノード：偏りをならす

素朴なリングには弱点があります。ノードをランダムにハッシュ配置すると、区間の大きさが大きくばらつくことです。たまたま隣接して配置された2ノードの間は狭く、離れた区間を1台が抱えると、その1台に負荷が集中します。N が小さいほどこの偏りは顕著です。

解決策が仮想ノード（virtual node / vnode）です。1台の物理ノードを、NodeA#0, NodeA#1, ... のようにサフィックスを変えた複数の点としてリング上にばらまくのです。

• 物理ノード1台あたり仮想ノードを V 個（数十〜数百）配置する。
• 各仮想ノードは独立にハッシュされるので、リング全体に細かく散らばる。
• 1台の物理ノードの担当区間は、V 個の小区間の合計になる。

小さな区間を多数集めれば大数の法則により合計がならされ、各物理ノードの負荷は平均へ収束します。V が大きいほど分散は小さくなります（標準偏差はおおむね V の平方根に反比例）。

仮想ノードのもう一つの効能は離脱時の負荷分散です。仮想ノードがないと、1台が落ちたときその担当ぶんすべてが時計回りの次の1台に集中し、玉突きで過負荷を招きます。仮想ノードがあれば、落ちた物理ノードの V 個の区間はそれぞれ別の生存ノードへ散るため、負荷の引き継ぎが平準化されます。

応用：分散キャッシュとシャーディング

コンシステントハッシュ法が最初に広く知られたのは分散キャッシュの文脈です。memcached クライアントの ketama などが代表例で、キャッシュサーバーの増減時にヒット率の急落を防ぐのが狙いです。mod N ならサーバー1台の追加で全キャッシュが無効化されかねませんが、リング方式なら無効化されるのは約 1/N で済みます。

データを永続化するシャーディングでも同じ原理が使われます。Amazon Dynamo に始まる一連の分散データストア（Cassandra, ScyllaDB, Riak など）はリングを基盤にデータを分散します。さらにこれらはレプリケーションと組み合わせ、あるキーの担当ノードから時計回りに次の N 台へ複製を置く（preference list）ことで冗長性を確保します。原理の比較はレプリケーションとシャーディングやパーティショニングも参照してください。

限界と注意点

コンシステントハッシュ法は万能ではありません。第一に、ハッシュで散らすため範囲検索に弱い点です。連続したキー（時系列など）の範囲取得は全ノードに散ってしまい、レンジパーティショニングのような区間スキャンができません。第二に、ホットキーには無力です。特定の1キーへアクセスが集中する場合、担当する1ノードが過負荷になるのはリング方式でも変わりません（キー自体を分割する別の工夫が要ります）。

まとめ