· 開発

Jump Consistent Hash：表を持たずにシャード番号を決めるコンシステントハッシュと、その前提条件

シャードを10個から12個に増やすとき、hash mod n はキーの5/6を動かしますが、本当に動かす必要があるのは1/6です。Lamping・Veach の論文のコード、仕組み、バケットを増減したときに起きることをまとめました。

開発アルゴリズムデータ構造

キーバリューデータを10個のシャードに分けるいちばん簡単な方法は、キーのハッシュを10で割った余り h(key) mod 10 をシャード番号にすることです。データが増えてシャードを12個にすると式は h(key) mod 12 になり、ほとんどのキーが別のシャードに移ることになります。

どれくらい動くのでしょうか。ハッシュ値が均等に散らばっているとして数えてみると、二つの余りが一致するのは h mod 60 が0から9のときだけです（10と12の最小公倍数は60です。二つの余りが同じ値 r なら h ≡ r (mod 60) で、r は10未満でなければなりません）。60通りのうち10通り、つまり1/6だけがその場に残り、5/6は移動します。

John Lamping と Eric Veach の論文「A Fast, Minimal Memory, Consistent Hash Algorithm」（2014年6月9日に arXiv へ投稿）は同じ例を挙げ、12個のシャードに均等に分け直すのに本当に動かす必要があるのは、10個のシャードにあったデータの1/6だけだと指摘しています。この論文の Jump Consistent Hash は、その1/6だけが動くようにシャード番号を決める関数で、コードは5行ほどです。以下はこの論文だけを根拠にまとめました。性能の数値はすべて論文が2014年に報告したもので、この記事では測り直していません。

関数が約束する二つの性質

Jump Consistent Hash は64ビットのキーとバケット（シャード）の数を受け取り、[0, num_buckets) の範囲のバケット番号を返します。論文はこの関数が次の二つを満たすと説明しています。

  • バランス（balance）：各バケットにほぼ同じ数のキーが割り当てられる。
  • 単調性（monotonicity）：バケット数を増やすと、キーは既存のバケットから新しいバケットへだけ移り、既存のバケット同士でキーをやり取りしない。

コンシステントハッシュという考え方は Karger らが1997年にウェブキャッシュ向けに提案したもので、もともと四つの性質が定義されていました。残りの二つ（spread と load）はクライアントごとに異なるサーバー集合が見えうる状況を扱うもの、と論文は説明しています。Jump Consistent Hash はすべてのクライアントが同じバケット集合 [0, num_buckets) を見ると仮定しており、この制約があるからこそ成り立ちます。

論文に載っているコード

論文の図1が C++ の実装のすべてです。

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
  int64_t b = -1, j = 0;
  while (j < num_buckets) {
    b = j;
    key = key * 2862933555777941757ULL + 1;
    j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
  }
  return b;
}

表も、サーバー一覧も、事前に組み立てるデータ構造もありません。論文の言葉では「数個のレジスタに収まる以上のメモリを必要としない」ということです。このコードがなぜバランスと単調性を持つのかは、バケットを一つずつ増やしていく遅い版から見ると分かりやすくなります。

バケットを一つずつ増やして考える

キー k のバケット数 n のときの結果を ch(k, n) と書きます。バケットが一つなら答えは当然0です。二つになったら、偏らないようにキーの半分は0に残り、半分は新しいバケット1へ移る必要があります。一般に n 個から n+1 個に増やすとき、キーの n/(n+1) はその場に残り、1/(n+1) だけが新しいバケット n へ「ジャンプ」しなければなりません。そうすれば新しいバケットも1/(n+1)のキーを受け取り、既存のバケットはそれぞれ同じ割合だけを手放します。

論文は三つのキーの値がバケット数とともにどう変わるかを表で示しています（いちばん上の行がバケット数）。

バケット数 1 2 3 4 5 6 7 8 9 10 11 12 13 14
k1 0 0 2 2 4 4 4 4 4 4 4 4 4 4
k2 0 1 1 1 1 1 1 7 7 7 7 7 7 7
k3 0 1 1 1 1 5 5 7 7 7 10 10 10 10

値が変わるセルを見ると、変わる先はいつもその列の新しいバケット番号（バケット数 − 1）です。k3 はバケットが6個になると5へ、8個で7へ、11個で10へジャンプします。既存のバケットの間を行き来することはありません。

この規則をそのままコードにしたのが論文の線形時間版です。キーをシードにした擬似乱数生成器を用意し、j = 1 から num_buckets − 1 まで回して、[0, 1) の乱数が 1/(j+1) より小さければ結果を j に置き換えます。同じキーは常に同じ乱数列を生むので、同じキーには同じ答えが出ます。ただし、バケット数に比例する時間がかかります。

次のジャンプ先を一度に求める

結果はほとんどの j で変わらず、ときどきジャンプするだけです。それなら変わる地点だけを計算すればよいことになります。論文の導出は次のとおりです。

  1. 一段で結果が変わらない確率は n/(n+1) です。何段かつなげると積が約分され、m ≤ n のとき ch(k, m) と ch(k, n) が等しい確率は m/n になります。たとえば 10/11 × 11/12 = 10/12 です。
  2. 直前のジャンプで結果が b になったとし、次のジャンプの直前の位置を j とします。任意の i > b について j ≥ i となる確率は ch(k, i) = ch(k, b+1) となる確率、つまり (b+1)/i です。
  3. 0と1の間で一様な乱数 r を一つ引き、「r ≤ (b+1)/i のとき j ≥ i」と決めればこの分布になります。不等式を i について解くと i ≤ (b+1)/r なので、j = floor((b+1)/r) です。

こうして次のジャンプ先を求め続け、その値が num_buckets 以上になったら止まり、最後にジャンプした先 b を答えとして返します。

図1のコードをこの導出に対応させて読むと次のようになります（この対応付けはこの記事の解釈です）。

  • key = key * 2862933555777941757ULL + 1 は64ビットの線形合同法（LCG）の1ステップです。キーそのものがシードで、反復のたびに状態が更新されます。論文はこの乗数について、連続する値を組にして使っても均等に分布するものだとして L’Ecuyer の LCG の表を引用しています。
  • (key >> 33) + 1 は状態の上位31ビットに1を足した値で、1から2³¹の間です。これを2³¹で割った値を r とすると、r は0より大きく1以下です。0にならないので、ゼロ除算は起きません。
  • (b + 1) * (2³¹ / ((key >> 33) + 1)) は (b+1)/r で、これを int64_t の j に代入するときに小数部が切り捨てられるので floor((b+1)/r) になります。
  • r ≤ 1 なので、新しい j は常に b+1 以上です。j は反復ごとに少なくとも1ずつ増えるので、ループは必ず終わります。

コスト：期待反復回数は ln n + 1 未満

論文の解析によると、バケット数 i でジャンプが起きる確率は 1/i なので、n より小さい位置へのジャンプ回数の期待値は i = 2 から n までの 1/i の和で、ln(n) より小さくなります。最後に n 以上へ進む反復がもう一回あるので、期待反復回数は ln(n) + 1 未満です。論文は、これが n 個のソート済みキーに対する二分探索の log₂(n) 回の比較より定数倍少ないと付け加えています。これは期待値であり、特定のキーで何回反復するかの上限を保証するものではありません。

ハッシュリングと比べると

Karger らのアルゴリズムは、バケットごとに単位円上へランダムな点をいくつも置き、キーを円上に写して時計回りに最初に出会う点のバケットを選びます。点が少ないとバケットの大きさが偏るので点を多く置く必要があり、そのぶんメモリを使います。論文は2014年当時に Intel Xeon E5-1650 で測った結果を次のように報告しています。

  • バケットあたり1000点のリングでも、バケットの大きさの99%信頼区間は平均の0.92倍から1.09倍でした。Jump Consistent Hash では0.99999998倍から1.00000002倍でした。
  • バケットあたり1000点、バケット1000個のとき、リングのデータは実装によって46MB（STL map）または7.6MB（ソート済みベクタ）でした。Jump Consistent Hash には保存するデータ構造がありません。
  • バケットが1000個以下のとき、Jump Consistent Hash はバケットあたり1000点のリングより3〜4倍速くなりました。

バケットを一つ追加するときの振る舞いも違います。論文によると、Jump Consistent Hash では新しいバケットが既存のすべてのバケットから同じ割合ずつキーを受け取ります。バケットが1000個なら、既存の各バケットがキー空間のほぼ正確に0.1%を手放します。リングでは新しいバケットの点が落ちた位置のバケットだけがデータを手放し、バケットあたり10点なら関わるのは多くても10個です。負荷の偏ったバケットを楽にするためにバケットを足したのに、そのバケットが関わらないこともある、ということです。

バケット数を変えると実際に起きること

増やすとき

n 個から n+1 個に増やすと、変わるキーはすべて新しいバケット n へ行きます。10個から12個に増やすとこの規則が2回適用されるので、変わるキーはすべて10番か11番のバケットへ行きます。先ほどの確率から ch(k, 10) と ch(k, 12) が等しい確率は10/12なので、移動するキーは2/12 = 1/6です。冒頭の mod の5/6と比べると、移動量は5分の1です。

減らすとき

逆に n 個から n−1 個に減らす場合は、単調性からすぐに分かります（この記事の導出）。n−1 個から n 個に増やしたときに変わったキーはすべてバケット n−1 へ行ったので、逆に減らすときは最後のバケット n−1 にあったキーだけが他のバケットへ散らばり、それ以外のキーはそのままです。

真ん中のバケットは外せない

外せるのは常に最後の番号のバケットです。10個のうち3番のサーバーが落ちたからといって num_buckets を9にすると、3番のキーは引き続き3番に割り当てられ、散らばるのは9番にあったキーです。関数が返すのはサーバー名ではなく、0から数えた番号だからです。

この落とし穴は、結果をサーバー一覧の配列の添字に使うと表に出ます。servers[JumpConsistentHash(key, servers.size())] と書いておいて一覧の途中からサーバーを一つ消すと、その後ろのサーバーが一つずつ前に詰まります。関数の結果はほとんど変わらなくても番号とサーバーの対応が変わり、ほとんどのキーが違うサーバーへ行ってしまいます（この記事の導出）。

論文はこれをこのアルゴリズムの主な制約として明記しています。バケットには連番を振る必要があり、そのため分散ウェブキャッシュよりもデータストレージに向いている、というものです。ストレージではシャードがただ消えるわけにはいかないので、レプリカを置くか素早く置き換えるかでサーバー障害に対処し、データの再配置は容量を変えるときにだけ起きる、というのが論文の前提です。任意のサーバーを任意の順で追加・削除する必要があるなら、論文が関連研究に挙げる Karger らのリングや Thaler と Ravishankar のランデブー（rendezvous）ハッシュのように、任意のバケット ID を扱える方式が合っています。論文によると、ランデブーハッシュの元の版はバケットごとに h(key, bucket) を計算して最大のものを選ぶので、バケット数に比例する時間がかかります。

使う前に確かめること

  • num_buckets は1以上でなければなりません。 図1のコードは0や負の数を受け取るとループに入らず -1 を返します（コードを読めば分かる動作です）。そのまま配列の添字に使うと範囲外アクセスになるので、呼び出す前にはじいておきます。引数が int32_t なので、バケット数の上限は2³¹ − 1です。
  • キーは64ビット整数です。 64ビットに収まらないキーは先に64ビットのハッシュを求めて渡すよう論文は述べています。すでに整数のキーは、内部の LCG が反復ごとに混ぜ直すので別途ハッシュする必要はないと説明しています。ハッシュ関数が何を保証し、何を保証しないかはハッシュ関数とはで取り上げました。
  • すべてのクライアント、すべての実行で同じキーハッシュが出る必要があります。 このアルゴリズムは、同じキーを受け取ったすべてのクライアントが同じバケットを計算することを前提にしています。実行のたびにシードが変わるハッシュ（たとえば Python の str のハッシュランダム化）を渡すと、プロセスを再起動するたびにキーが別のシャードを指すようになります。
  • すべてのクライアントが同じ num_buckets を使う必要があります。 一部のクライアントだけが新しい値に切り替わっている間は、同じキーが二つのシャードを指すことがあります。関数が教えてくれるのはどのキーが移るかだけで、データの移動や切り替えの順序は運用側の仕事です。
  • ほかの言語に移すときは演算の幅を合わせます。 掛け算は2⁶⁴で割った余りだけを残す符号なし64ビット演算、>> 33 は符号なしの値のシフト、割り算は倍精度浮動小数点です。三つのどれかが違うと C++ の実装とは別のバケットが出ます。

たとえば Python の整数には大きさの上限がないので、掛け算のあとに64ビットのマスクを自分でかける必要があります。以下は図1を移植したこの記事のコードで、0以下のバケット数は例外にしています。

MASK64 = (1 << 64) - 1

def jump_consistent_hash(key: int, num_buckets: int) -> int:
    if num_buckets <= 0:
        raise ValueError("num_buckets must be positive")
    key &= MASK64
    b, j = -1, 0
    while j < num_buckets:
        b = j
        key = (key * 2862933555777941757 + 1) & MASK64
        j = int((b + 1) * ((1 << 31) / ((key >> 33) + 1)))
    return b

この記事を書くにあたって、CPython とコンパイルした図1の C++ コードに同じ28,001個の入力を与えたところ、この環境では結果がすべて一致しました。ただし、これは試した一つの環境での結果にすぎません。オペランドが小さな整数だというだけでは、言語が違っても割り算と整数への変換が同じ結果になるとは言えません。本番に入れる前に、実際に使う言語・コンパイラ・プラットフォームで、いろいろなキーとバケット数を使って C++ の実装と結果を照合してください。

参照した論文

Karger ら（1997）、Thaler・Ravishankar（1997）、L’Ecuyer の論文は原文を開いておらず、この記事でそれらの研究について書いた内容はすべて上の論文の説明によるものです。論文は2026年10月19日に確認しました。

ブログへ