コンシステントハッシュ法とは?仕組み・仮想ノード・再配置の最小化を実装と実験で徹底解説

1. 素朴な hash(key) mod N の何が問題か

複数台のサーバーにデータやリクエストを振り分けたいとき、最初に思いつく方法は「キーをハッシュ化し、サーバー台数 N で割った余りでサーバーを決める」という hash(key) mod N 方式だろう。実装は1行で済み、キーの分布さえ一様なら各サーバーへの割り当ても一様になる。

しかしこの方式には、実運用で致命的になりうる欠点が1つある。サーバー台数 N が変わった瞬間、ほぼ全てのキーの担当サーバーが変わってしまうのである。hash(key) mod 10 と hash(key) mod 11 は、同じ hash(key) に対してほとんどの場合まったく異なる余りを返す。キャッシュサーバーであればキャッシュヒット率が一瞬でゼロ近くまで落ち、分散データベースであれば大量のデータの物理的な移動(リシャーディング)が発生する。サーバーを1台増やしただけで、あるいは1台落ちただけで、システム全体が総入れ替えに近い状態になるというのは、スケールアウトが日常的な現代の分散システムでは受け入れがたいコストである。

この崩壊ぶりを実際に測ってみる。10台構成から11台構成に変えたとき、hash(key) mod N で担当サーバーが変わるキーの割合を、10万件のキーで実測した。

import hashlib

def h64(data: bytes) -> int:
    """blake2bダイジェストの先頭8バイトを符号なし64bit整数として返す。"""
    d = hashlib.blake2b(data, digest_size=8).digest()
    return int.from_bytes(d, "little")

def mod_assignment(keys, n_nodes):
    return [h64(k) % n_nodes for k in keys]

keys = [f"key-20260720-{i}".encode() for i in range(100_000)]
before = mod_assignment(keys, 10)
after = mod_assignment(keys, 11)
moved = sum(1 for b, a in zip(before, after) if b != a)
print(moved, moved / len(keys))

実測結果は次の通り。

10万件中9万件超、実に9割以上のキーが担当サーバーを変えている。これは偶然でも実装ミスでもなく、mod N 方式の数学的な必然である。ハッシュ値が一様であれば、余りが変わらず同じサーバーに留まるキーはおおよそ \(1/11\) しかなく、残りの \(1-1/11\approx90.9\%\) は必ずどこかに移動する。実測値90.90%は理論値90.91%とほぼ完全に一致しており、この崩壊が理論通りに起きていることが確認できる。

「サーバー台数が変わるたびにキャッシュや分散データがほぼ全滅する」というこの欠点を解消するために考案されたのが、本記事の主題である**コンシステントハッシュ法(consistent hashing)**である。この概念を最初に定式化したのは David Karger らが1997年のSTOC(ACM Symposium on Theory of Computing)で発表した論文 “ Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web "(Karger, Lehman, Leighton, Levine, Lewin, Panigrahy, STOC 1997)である。もともとはWebキャッシュのホットスポット問題を解決するための理論的な枠組みとして提案されたものだが、その後memcachedの分散クライアント、DynamoDB、Cassandra、Envoy/HAProxyのロードバランサーなど、現代の分散システムのインフラ層に深く根付くことになる。

2. コンシステントハッシュの仕組み: リングと時計回りの割り当て

コンシステントハッシュの基本アイデアは単純である。「サーバー台数で割った余り」という不安定な写像をやめ、ノードとキーの両方を同じハッシュ空間上の円環(リング)に配置し、キーはリング上を時計回りに進んで最初に出会ったノードが担当する、というルールに置き換える。

具体的な手順は次の通りである。

1. ハッシュ関数の出力域(例えば \([0, 2^{64})\) )を、両端がつながった円環とみなす。
2. 各ノード(サーバー)の識別子をハッシュ化し、その値をリング上の位置とする。
3. 各キーもハッシュ化し、同じリング上に位置を求める。
4. キーの位置から時計回りに探索し、最初に見つかったノードをそのキーの担当ノードとする。

下図はノードA/B/C/Dが並ぶリングに新しいノードEを追加した様子である。

ここが mod N との決定的な違いである。ノードEを追加しても、Eの直前のノード(この図ではC)からEまでの弧が担当していたキーだけがEに移動し、その他のキーの担当関係は一切変わらない。これは、E以外のノードの位置がリング上でまったく動いていないことから直感的にも理解できる。ノードを削除する場合も対称的で、そのノードが担当していた範囲だけがリング上の次のノードに吸収され、他のノードには影響しない。

「ノードの追加・削除が、そのノードの隣接領域にしか影響しない」という、この局所性こそがコンシステントハッシュの核心である。Karger論文のタイトルにある “Random Trees” という言葉が示す通り、ノードをリング上にランダムに配置することで、ノード数 n に対しどのノードの担当範囲も期待値としておよそ \(1/n\) に収まり、かつ変更の影響が局所化される、という2つの性質を同時に得られることが理論的に示されている。

3. 実験: 再配置されるキーは本当に約 \(1/n\) で済むのか

理屈の上では、ノードを10台から11台に増やしたとき、新ノードが奪うキーの割合は新ノードの担当範囲(リング全体のおよそ \(1/11\) )に等しく、それ以外の10台の担当範囲は変わらないはずである。つまり移動するキーの割合の理論値は \(1/11\approx9.09\%\) となる。これを第1節と同じ10万件のキー、同じ乱数シードで実測して検証する。

import bisect

class HashRing:
    """blake2bベースの単純なコンシステントハッシュリング。仮想ノード数vを指定可能。"""

    def __init__(self, node_ids, v=1):
        self.v = v
        self.ring_points = []  # (position, node_id) のリスト、position昇順にソート
        for node_id in node_ids:
            for vi in range(v):
                pos = h64(f"{node_id}#{vi}".encode())
                self.ring_points.append((pos, node_id))
        self.ring_points.sort(key=lambda t: t[0])
        self.positions = [p for p, _ in self.ring_points]

    def lookup(self, key: bytes) -> str:
        pos = h64(key)
        idx = bisect.bisect_right(self.positions, pos)
        if idx == len(self.positions):
            idx = 0  # リングの終端を超えたら先頭(=時計回りに一周)に戻る
        return self.ring_points[idx][1]

nodes10 = [f"node-{i}" for i in range(10)]
nodes11 = [f"node-{i}" for i in range(11)]
ring_before = HashRing(nodes10, v=200)  # ketamaと同水準の仮想ノード200本
ring_after = HashRing(nodes11, v=200)

before = [ring_before.lookup(k) for k in keys]
after = [ring_after.lookup(k) for k in keys]
moved = sum(1 for b, a in zip(before, after) if b != a)
print(moved, moved / len(keys))

実測結果は次の通り。

実測9.11%は理論値9.09%とわずか0.02ポイントの差で一致した。mod N 方式が90.90%ものキーを動かしていたのと比べると、同じ「10台→11台」という変更に対して移動するキーはおよそ10分の1で済んでいる。下図は両者を並べたものである。

理論的には、ノード数を n から n+1 に増やす一般のケースで、コンシステントハッシュが動かすキーの割合はおよそ \(1/(n+1)\) 、つまりノード数が多いほど1台追加あたりの影響はさらに小さくなる。逆にノード数が少ないうちは(\(n\) が小さいうちは)動くキーの割合もそれなりに大きくなるが、それでも mod N の \(1-1/(n+1)\) と比べれば常に圧倒的に小さい。この「変更の影響がノード数にほぼ反比例して局所化される」という性質こそが、コンシステントハッシュが分散キャッシュや分散データベースの標準技術になった理由である。

4. 負荷の偏りと仮想ノード

ここまでの実験ではリングの構築に v=200 という仮想ノード(virtual node)を使っていた。仮想ノードとは、1つの物理ノードをリング上の1点にではなく、複数点(識別子に#0, #1, …という接尾辞を付けて個別にハッシュ化した点)に配置するテクニックである。なぜこれが必要なのか、v=1(仮想ノードなし、物理ノード1台につきリング上1点のみ)で試すとすぐにわかる。

物理ノードをリング上にランダムに1点だけ配置すると、ノード間の間隔は完全にランダムに決まるため、間隔が広いノード(担当範囲が広い)と狭いノード(担当範囲が狭い)の差が非常に大きくなりやすい。これは「ランダムに10個の点を円周上に打ったとき、各点の間隔がどれだけばらつくか」という初等的な問題そのものであり、点の数が少ないうちは偏りが大きく出る。

10ノード・10万キーの条件で、仮想ノード数 \(v \in \{1, 10, 100, 1000\}\) を振り、各ノードが担当するキー数の変動係数(CV = 標準偏差 / 平均)を実測した。CVが小さいほど負荷が均等ということになる。

import statistics

nodes = [f"node-{i}" for i in range(10)]
for v in [1, 10, 100, 1000]:
    ring = HashRing(nodes, v=v)
    counts = {node: 0 for node in nodes}
    for k in keys:
        counts[ring.lookup(k)] += 1
    values = list(counts.values())
    mean = statistics.mean(values)
    cv = statistics.pstdev(values) / mean
    print(v, mean, cv, min(values), max(values))

実測結果は次の通り(平均は10ノードで割った10,000キー/ノード)。

\(v=1\) では、平均10,000キー/ノードのはずが、最小910キーのノードと最大32,508キーのノード(平均の3倍以上!)が同居しており、CVも0.94ときわめて大きい。これでは「10台に分散したから負荷が10分の1になる」という期待が根本から崩れてしまう。\(v\) を10、100、1,000と増やすごとにCVは0.38、0.058、0.028と急速に縮小し、\(v=1000\) では最小・最大の差も1割弱まで縮まっている。

図から分かる通り、CVは \(v\) の対数に対してほぼ単調に減少している。仮想ノードは1物理ノードをリング上の複数点に「薄く広く」ばら撒くことで、ランダムな間隔のばらつきを平均化し、大数の法則的に負荷を均していると理解できる。第3節で見た「再配置されるキーがおよそ \(1/n\) で済む」という性質は仮想ノードが無くても成り立つが、「各ノードの負荷がほぼ均等になる」という実用上重要な性質は、仮想ノードを十分な数だけ用意して初めて実用レベルに達する。この2つは似ているようで異なる性質であり、両方を実測で切り分けて確認できたことになる。

5. Python実装(全コード)

ここまで使ってきたコードを1本にまとめると次のようになる。ハッシュ関数には標準ライブラリの hashlib.blake2b を使い、リング上の探索には bisect によるソート済み配列への二分探索を用いている。

import bisect
import hashlib
import statistics


def h64(data: bytes) -> int:
    """blake2bダイジェストの先頭8バイトを符号なし64bit整数として返す。"""
    d = hashlib.blake2b(data, digest_size=8).digest()
    return int.from_bytes(d, "little")


class HashRing:
    """blake2bベースの単純なコンシステントハッシュリング。仮想ノード数vを指定可能。"""

    def __init__(self, node_ids, v=1):
        self.v = v
        self.ring_points = []
        for node_id in node_ids:
            for vi in range(v):
                pos = h64(f"{node_id}#{vi}".encode())
                self.ring_points.append((pos, node_id))
        self.ring_points.sort(key=lambda t: t[0])
        self.positions = [p for p, _ in self.ring_points]

    def lookup(self, key: bytes) -> str:
        pos = h64(key)
        idx = bisect.bisect_right(self.positions, pos)
        if idx == len(self.positions):
            idx = 0
        return self.ring_points[idx][1]

    def lookup_many(self, keys):
        return [self.lookup(k) for k in keys]


def mod_assignment(keys, n_nodes):
    return [h64(k) % n_nodes for k in keys]


def remap_ratio(before, after):
    moved = sum(1 for b, a in zip(before, after) if b != a)
    return moved, moved / len(before)


def load_cv(ring, node_ids, keys):
    counts = {node: 0 for node in node_ids}
    for k in keys:
        counts[ring.lookup(k)] += 1
    values = list(counts.values())
    mean = statistics.mean(values)
    return statistics.pstdev(values) / mean, counts

HashRing クラスは、コンストラクタで各ノードを v 個の仮想ノードとしてリングに配置し(__init__)、lookup でキーの位置から bisect_right で時計回りに最も近いリング上の点を探す、という2つの操作だけで完結している。実務のライブラリではハッシュ関数にMurmurHash3やxxHashなど高速なものを使い、リングの探索にもより高速なデータ構造を使うことが多いが、コンシステントハッシュの本質的な挙動を確認するにはこの数十行で十分である。

6. 実システムでの利用: Dynamo・Cassandra・ketama・Envoy/HAProxy

コンシステントハッシュは理論だけの技術ではなく、現代の主要なインフラで実際に採用され続けている。

Amazon Dynamo(2007): Amazonの社内向け分散キーバリューストアDynamoを解説した論文 “ Dynamo: Amazon’s Highly Available Key-value Store "(DeCandia et al., SOSP 2007)は、Section 4.2で素朴なコンシステントハッシュの課題を指摘している。「ノードのランダムな位置割り当てが非一様なデータ・負荷分布を生む」「基本アルゴリズムはノードの性能差を考慮しない」という2点である。この解決策として論文が導入したのが本記事で扱った**仮想ノード(virtual node)**であり、論文は「ノードが利用不能になった場合、そのノードが処理していた負荷は残りの利用可能なノードに均等に分散される」「新しいノードが追加されると、既存の各ノードからほぼ均等な量の負荷を引き受ける」という利点を挙げている。この設計思想は後継のマネージドサービスであるDynamoDBにも受け継がれている。

Cassandra: Apache Cassandra公式ドキュメント によれば、単一トークンのコンシステントハッシュは小規模クラスタでの段階的なスケーリングが難しく、これを解決するために1台の物理ノードに複数のトークン(vnode)を割り当てる方式を採用している。2.x系でのデフォルトは1ノードあたり256トークンで、3.x以降はより効率的な割り当てアルゴリズムにより少ないトークン数でも均等なバランスを実現できるようになった。

ketama(memcached): 分散memcachedクライアントの世界でコンシステントハッシュを広めたのが、Last.fmのRichard Jonesが2007年に発表した libketama である。同記事によれば、それ以前の実装では「サーバーをプールに追加・削除するたびに、あらゆるキーが別のサーバーにハッシュされ、キャッシュ全体が実質的に消去されていた」という問題があった。ketamaは各サーバーを継続的な円環(continuum)上の100〜200個の点にハッシュ配置することでこれを解決し、C言語のコアライブラリとPHP・Java向けのバインディングとして公開された。この「1ノードあたり100〜200点」という値は、後述するEnvoyのring hashロードバランサーが「ketama方式」として踏襲している。

Envoy / HAProxy: L7プロキシのEnvoyは ring hash(ketama)ロードバランサー を持ち、各ホストをリング上にハッシュ配置し、リクエストのプロパティをハッシュ化して時計回りに最も近いホストへルーティングする。リングサイズは minimum_ring_size(デフォルト1024)・maximum_ring_size(デフォルト800万)で調整でき、ホストの重みに比例した数だけリング上に配置することで重み付けにも対応する。HAProxyも balance uri と hash-type consistent の組み合わせで同種のコンシステントハッシュを実現しており、同一URIを同じバックエンドに送り続けてキャッシュ効率を高める用途に使われている。

7. 派生手法: Rendezvous・Jump・Maglevハッシュ

コンシステントハッシュにはリング構築とソート済み配列の維持というオーバーヘッドがあり、これを避けるための派生手法もいくつか実用化されている。**Rendezvous hashing(HRW: Highest Random Weight)**は、David ThalerとChinya Ravishankarが1996年に提案した手法で、リングを持たず、キーとノードの組ごとにハッシュから「重み」を計算し、重みが最大になるノードを担当ノードとするだけのシンプルな方式である。Jump Consistent Hashは、GoogleのJohn LampingとEric Veachが2014年の論文 “ A Fast, Minimal Memory, Consistent Hash Algorithm ” で発表した手法で、メモリを一切使わずわずか数行のループ計算だけでバケット番号を求められる代わりに、バケットが0からn-1まで連番で管理されている必要があり、ノードを名前で自由に追加・削除するような用途には向かない。Maglevハッシュは、GoogleのソフトウェアL4ロードバランサーMaglevを解説した論文 “ Maglev: A Fast and Reliable Software Network Load Balancer "(NSDI 2016)が採用する手法で、ハッシュ空間を固定長のルックアップテーブルに分割し、各バックエンドがほぼ均等な数のテーブル枠を持つよう構築することで、コンシステントハッシュ以上に均一な負荷分散と高速な参照を両立させている。

まとめ

コンシステントハッシュ法は、ノードとキーを同じハッシュ空間の円環上に配置し、キーを時計回りに最初に出会うノードへ割り当てるという単純なルールだけで、「ノード数が変わっても影響がそのノードの近傍だけに局所化される」という性質を実現する。今回の実測では、ノードを10台から11台に増やしたときに再配置されるキーの割合が、素朴な mod N 方式では90.90%(理論値90.91%)であったのに対し、コンシステントハッシュでは9.11%(理論値9.09%)と、理論通りおよそ10分の1に抑えられることを確認した。また、仮想ノード数を1から1,000まで増やすほど、ノード間の負荷の偏り(変動係数)が0.94から0.028まで縮小することも実測できた。Dynamo論文が導入した仮想ノード、ketamaが実用化した100〜200点のcontinuum、Cassandraの256トークン、Envoy/HAProxyのring hashは、いずれもこの「リング + 仮想ノード」という組み合わせの延長線上にある実装であり、半世紀近く前のハッシュ法の理論が、今も分散システムの負荷分散を裏で支え続けていることがわかる。

FAQ

Q1. 通常のハッシュ分散(mod N)と何が違う? mod N はノード数 N が変わると理論上ほぼ全てのキー(\(1-1/N\) の割合)が別のノードに移動する。コンシステントハッシュはノードとキーを同じリングに配置することで、ノード数が変わったときに移動するキーを新旧ノードの担当範囲の差分だけ(おおよそ \(1/N\) )に抑える。第1節・第3節の実測(90.90% vs 9.11%)がこの差を裏付けている。

Q2. 仮想ノードはいくつ必要? 今回の実測では \(v=100\) でCV 0.058、\(v=1000\) でCV 0.028だった。実運用のライブラリはketama・Envoyともに1ノードあたり100〜200点程度を標準としており、これは負荷の偏りを実用上十分小さく抑えつつ、リングのメモリ使用量や探索コストを過大にしない、経験的にバランスの良い水準といえる。負荷分散の均一性をさらに厳密に求める場合は、第7節で触れたMaglevハッシュのような専用手法を検討する価値がある。

Q3. ノードの重み付けはどうする? スペックが異なるノードを混在させたい場合、性能の高いノードほど多くの仮想ノードをリングに配置すればよい。Dynamo論文も「ノードが担当する仮想ノード数は物理インフラの異質性を踏まえて決める」としており、Envoyのring hashロードバランサーもホストの重みに比例した数だけリング上の点を生成することで重み付けに対応している。

Q4. どんな時に使うべき? ノード(サーバー、シャード、キャッシュサーバー)の台数が将来増減する可能性があり、かつ増減のたびに大量のデータ移動やキャッシュ全滅を避けたい場合に使うべき技術である。分散キャッシュのサーバー選択、分散データベースのパーティショニング、ロードバランサーでのバックエンド選択など、「同じキーはできるだけ同じ宛先に送り続けたいが、宛先集合は動的に変わる」という要件がある場面全般が対象になる。

他の分野の定番書は エンジニアにおすすめの技術書10選 にまとめている。