一貫性ハッシュ

一貫性ハッシュは、具体的な問題を解決します。⁠メンバーが変化した際に、どのようにして大多数のキーが元の所属を維持するか？ ここで言う「一貫性」は、マッピングの変化の性質を記述するものであり、データベースの線形一貫性とは異なる概念です。

まず、2つのレイヤーを分けて考えましょう。マッピングアルゴリズムは「現在どこに置くべきか」に答え、移行プロトコルは「元の場所から搬送する際に、読み書きが正しく行われることを保証」します。ハッシュ関数やメンバーリストを変更しただけでは、データは自動的に搬送されません。

なぜ単純な剰余演算だと広範囲の再マッピングが起こりやすいか

bucket = hash(key) % N とします。3つのバケットから4つのバケットに増やした場合、同じハッシュ値の剰余が変化する可能性があります。例えば、5はバケット2からバケット1に、6はバケット0からバケット2に移動しますが、1はバケット1のままです。すべてのキーが移動するわけではありませんが、変化の規模は新しいバケットが受け入れるデータ量よりもはるかに大きくなります。

ハッシュ値が一様分布し、バケット番号が不変であると仮定すると、N から N+1 への増加分において、連続する N(N+1) 個の整数のうち、同じ剰余を保つのは N 個だけです。したがって、約 N/(N+1) のキーが所属を変更することになります。理想的な均衡あるスケールアウトでは、新しいバケットが約 1/(N+1) のキーを受け取るだけで済むはずです。これが縮小すべきギャップです。ここで計算しているのはキーの数であり、オブジェクトのサイズが異なる場合、バイト量はその比率と一致しません。

ハッシュリング：所属は時計回りで最初に出会うトークンで決まる

ハッシュ空間を、始点と終点が繋がった円として想像してください。ノードはリング上のトークンを保持し、キーのハッシュ値が時計回りに遭遇する最初のトークンがその所属を決定します。最大値を超えると最小値に戻ります。前のトークンを p、現在のトークンを q とすると、通常、区間は (p, q] と表記されます。

計算を容易にするため、以下では 0 から 99 の小さな空間を使用します：A、B、C のトークンはそれぞれ 20、60、90 です。D のトークン 40 が追加されると、元々 B に属していた (20, 40] の範囲が D に移り、他の主要な所属は変わりません。

クエリでは、ソートされたトークンの配列を保持し、二分探索によってキーのハッシュ値以上の最初のトークンを見つけます。存在しない場合は、配列の先頭要素を選択します。異なるクライアントが異なる所属を計算しないように、キーのエンコーディング、ハッシュアルゴリズム、トークンのソート順序、および端点のルールを統一する必要があります。

この例では単一のデータコピーの主要な所属のみを扱っています。レプリケーションシステムでは、後続のレプリカを選択し、同じ物理ノードに属するトークンをスキップし、ラックやアベイラビリティゾーンでの分離を満たす必要があります。メンバーの変化はレプリカセットに影響を与える可能性があり、主要な所属が変化しなくても、レプリカを補充する必要がある場合があります。

境界、ラップアラウンド、物理レプリカの重複排除をコードで実装

以下の実装は、変更範囲をすべて確認するために 0–99 のハッシュ位置を直接受け取ります。リングは初期化時にソートされ、クエリでは二分探索で位置を特定します。同じトークンは拒否され、異なるクライアントが異なるルールで衝突を処理することを防ぎます。

from bisect import bisect_left

class Ring:
    def __init__(self, entries):
        self.entries = sorted(entries)
        self.positions = [position for position, _ in self.entries]
        if (not self.positions or len(set(self.positions)) != len(self.positions)
                or any(not 0 <= p < 100 for p in self.positions)):
            raise ValueError("空ではなく、重複がなく、0–99 の範囲にあるトークンが必要です")
        self.node_count = len({node for _, node in self.entries})

    def replicas(self, position, count=1):
        if not 0 <= position < 100 or not 1 <= count <= self.node_count:
            raise ValueError("位置または物理レプリカ数が無効です")
        start = bisect_left(self.positions, position)
        result = []
        for step in range(len(self.entries)):
            node = self.entries[(start + step) % len(self.entries)][1]
            if node not in result:
                result.append(node)
                if len(result) == count:
                    return result
        raise AssertionError("有効なリングには十分な物理レプリカが必要です")

before = Ring([(20, "A"), (60, "B"), (90, "C")])
after = Ring([(20, "A"), (40, "D"), (60, "B"), (90, "C")])
assert before.replicas(20) == ["A"]  # 右端点は現在のトークンに属する
assert before.replicas(21) == ["B"]
assert before.replicas(99) == ["A"]  # 末尾を超えるとラップアラウンド
moved = [p for p in range(100) if before.replicas(p) != after.replicas(p)]
assert moved == list(range(21, 41))
assert all(after.replicas(p) == ["D"] for p in moved)
assert before.replicas(10, 2) == ["A", "B"]
assert after.replicas(10, 2) == ["A", "D"]
vnodes = Ring([(20, "A"), (40, "A"), (60, "B"), (90, "C")])
assert vnodes.replicas(10, 3) == ["A", "B", "C"]

D を追加した後、ちょうど 20 個の位置が移動し、4ノードの平均割り当てである 25 個ではありません。実際の移行量は D が挿入された位置によって決まります。レプリカ数が 2 の場合、位置 10 のマスターノードは A のままですが、セカンダリレプリカは B から D に変わります。したがって、主要な所属の変化のみをカウントすると、レプリカの補充作業を見逃すことになります。

最後の assert は、同じ物理ノードの2つの仮想トークンが2つの独立したレプリカとして機能しないことを保証します。この実装では物理ノードのみを重複排除しており、ラックやアベイラビリティゾーンを跨ぐ制約はありません。障害ドメインを分散させる必要がある場合、選択された後続ノードは配置ポリシーを満たし続ける必要があります。メンバーリストの更新やデータ複製はクエリ関数には含まれておらず、D が返されたからといって、D がすでにデータを保持していることを意味しません。

D が追加されたとき、実際にどのキーが所属を変更したのか？

以下では、リングをハッシュ位置で並べられたグリッドとして展開し、変更範囲を直接数えやすくしています。D は B の前に挿入され、(A, D] の範囲のみを管轄します。D の位置にちょうど一致するキーは D に、A の位置にちょうど一致するキーは A のままです。トークンを調整して変更されたグリッドの数と比較することで、理想的な均等な割り当てを、実際の挿入ごとに正確に満たす比率と誤認することを避けます。

仮想ノード：大きな区間を複数の小さな区間に分割する

各物理マシンにランダムなトークンを1つだけ配置すると、一台が非常に長い区間を占め、もう一台が非常に短い区間しか占めないという状況になりやすくなります。各マシンが複数のトークンを持つようにすることで、容量を多くの分散したシェアに分割できます。ノードの容量が異なる場合、異なる数またはサイズのシェアを割り当てることもできます。

仮想ノードは、ランダムな区間の大きさに起因するバイアスを低減しますが、リクエスト負荷の均一性は保証されません。あるキーがアクセスの大部分を占めている場合、そのハッシュがどれだけ一様であっても、1つのマスターノードにのみ割り当てられます。また、トークンが増えると、ルーティングメタデータ、区間の保守、および復旧タスクの数が増加します。

エンジニアリングの現場では、2つの異なる設計があります。1つは新しいマシンを追加する際に新しいトークンを生成する方法、もう1つは事前に大量の論理パーティションを構築し、その一部を新しいマシンに再割り当てする方法です。これらは移行の粒度を細かくしますが、メンバーの変化、トークンの安定性、およびメタデータの保守方法は異なります。ある製品のあるバージョンでの仮想ノードのデフォルト数を、アルゴリズムの定数として扱わないでください。

Rendezvous Hash：候補ノードが順に競合する

Rendezvous Hash（HRWとも呼ばれる）は、各候補ノードに対して決定論的なスコアを計算します：score = H(key, stable_node_id)。最大スコアを選択します。実装には、安定したノード識別子、曖昧さのない入力エンコーディング、およびスコアが同点の場合の決定論的なソートルールが必要です。

なぜメンバーの変化が一部のキーのみに影響を与えるのでしょうか？ノード X を削除する場合、元の勝者が X ではないキーについては、その候補スコアと勝者自体が変化しません。X を追加する場合、X が元の勝者を打ち負かすキーのみが所属を変更します。独立した一様スコアと同等のノード重みという理想的な仮定の下では、新しいノードが受け取る期待されるシェアは 1/(N+1) です。

重み付けを単純に「ハッシュ値を重みで割ったものを最大にする」としてはなりません。それでは重みが大きいノードのスコアが低下してしまいます。明確な重み付けの構成としては、各ノードのハッシュ結果を Uᵢ∈(0,1) にマッピングし、Tᵢ = -ln(Uᵢ) / wᵢ を計算し、T が最小のノードを選択します。ここで wᵢ>0 です。P(Tᵢ>t)=exp(-wᵢt) であるため、各独立した候補の指数関数的な競争により、ノードが勝つ確率は wᵢ / Σw になります。これは与えられたランダムモデルに基づく導出であり、実際の実装ではハッシュの品質と浮動小数点の境界を処理する必要があります。

HRW はハッシュリングを必要としませんが、一貫したメンバーリストと重みは依然として必要です。単純な実装では、クエリごとに N 個のノードを走査する必要があり、計算コストは O(N) です。「リングがない状態」は「クラスターメタデータがないこと」を意味しません。

HRW の安定性は、古い候補スコアが変化しないことに由来する

以下では、("ab","c") と ("a","bc") の連結が同じ入力を生成しないようにするために、長さプレフィックス付きの UTF-8 フィールドエンコーディングを使用します。スコアには SHA-256 を使用し、スコアが衝突した場合は安定したノード ID で比較します。この例では同等の重み付けを示しており、上記の重み付けバリアントは含まれていません。

from hashlib import sha256

def encoded(key, node):
    fields = [part.encode("utf-8") for part in (key, node)]
    return b"".join(len(field).to_bytes(4, "big") + field for field in fields)

def winner(key, nodes):
    if not nodes:
        raise ValueError("候補ノードがありません")
    return max(nodes, key=lambda node: (sha256(encoded(key, node)).digest(), node))

assert encoded("ab", "c") != encoded("a", "bc")
for i in range(5000):
    key = f"order-{i}"
    old = winner(key, ["A", "B", "C"])
    added = winner(key, ["A", "B", "C", "D"])
    assert added == old or added == "D"
    assert winner(key, ["C", "B", "A"]) == old
    removed = winner(key, ["A", "C"])
    assert old == "B" or removed == old

スケールアウト時、古いノード A、B、C のスコアは変化せず、D は勝つか負けるかのいずれかであり、A のキーが理由もなく B に変わることはありません。B を削除する場合、元々 A や C に属していたキーは所属を維持します。デプロイのたびにノード ID を再生成したり、キーエンコーディングやハッシュシードを変更したりすると、この推論の前提が崩れ、マシンが1台も変わらなくても広範囲の再マッピングが発生する可能性があります。

5000 個のサンプルは、これらの性質が実装されているかを確認するために使用されます。期待される移行シェア 1/4 は、独立した一様スコアのモデルに由来するものであり、任意の 5000 個のビジネスキーにちょうど 1250 個の移行があることを意味するものではなく、移行バイト数やホットスポットリクエストの割合がちょうど 4 分の 1 であることを意味するものでもありません。

Jump Consistent Hash：バケット数だけを記録する

Jump Hash は、キーを連続番号のバケット 0…N-1 にマッピングします。決定論的なジャンププロセスを利用して最終的なバケットを見つけ、トークン配列を保存する必要はなく、期待される計算量は O(log N)、アルゴリズムの追加スペースは O(1) です。

重要な制約は、バケット番号が連続していることです。N から N+1 に増やす場合、追加されるのは末尾のバケット N です。縮小する場合、末尾のバケットが削除されます。これは、「任意の物理マシンが退出し、他のマシンの番号が変わらない」という問題を直接解決するものではありません。バケットと物理マシンの間にマッピングレイヤーを追加できますが、このメタデータと移行戦略は別途設計する必要があります。アルゴリズムと完全な実装については、Jump Hash 原論文を参照してください。

選択ガイド

上記の移行比率はすべて、均衡などの前提条件が必要です。リングに任意の位置に1つのトークンを追加する場合、移動量は実際の区間によって決まり、固定された 1/N ではありません。容量の重み変化、障害ドメインの調整、ホットスポットの処理も、追加の移行を引き起こします。

続きを読む：シャーディング戦略では、どのキーを選択するかを議論します。動的再バランスでは、安全に移行する方法を議論します。

参考文献

• Dynamo 原論文：パーティショニング、仮想ノード、およびレプリケーションの組み合わせ。
• Jump Consistent Hash 原論文：連続バケット番号におけるアルゴリズムと分析。

Keywords: consistent hashing, hash ring, vnode, rendezvous hashing, HRW, jump hash