コンシステントハッシュ法とは - 分散システムでノードを増減してもキャッシュが崩れない仕組み
分散データ処理の必読書。パーティショニング章が対応。
コンシステントハッシュを図解で扱う定番。
ハッシュとデータ構造の基礎固めに。
当サイトは Amazon.co.jp を宣伝しリンクすることで紹介料を得る手段を提供する、Amazonアソシエイト・プログラムの参加者です。価格・在庫はリンク先の最新情報をご確認ください。
分散キャッシュやシャーディングされたデータベースを運用していると、必ずこの壁にぶつかります。「サーバーを1台増やしたら、キャッシュがほぼ全部無効になってしまった」。アクセスが一気にデータベースへ流れ込み、応答が悪化する。逆に1台落ちたときも同じことが起きます。この「ノードを増減するたびに、ほとんどのデータが別のノードへ移動してしまう」問題を、驚くほどスマートに解決するのがコンシステントハッシュ法（Consistent Hashing）です。この記事では、素朴な方式の限界から出発して、ハッシュリング・仮想ノード・実運用・発展アルゴリズムまでを順に組み立てていきます。
前提として、キーからバケットを求めるハッシュテーブルの仕組みを軽く押さえておくと理解が早いです。コンシステントハッシュは、その「ハッシュ関数で位置を決める」という発想を、複数のサーバーへの割り当てに応用したものだと考えると腹落ちします。
まず素朴な mod N の限界
キーを複数のノードに振り分ける、いちばん素直な方法を考えてみます。ノードが N 台あるとき、キーをハッシュして N で割った余り（剰余）でノードを決める方式です。
node_index = hash(key) % Nたとえばノードが3台（0, 1, 2）あり、あるキーのハッシュ値が 100 なら、100 % 3 = 1 で1番のノードに割り当てられます。均等にばらけますし、実装も一行で済みます。問題はノード数が変わったときです。
ここでノードを1台足して4台にすると、割り算の分母が 3 から 4 に変わります。同じキーのハッシュ値 100 は 100 % 4 = 0 となり、1番から0番へ移動します。これは特定のキーだけの話ではありません。分母が変わると剰余の対応関係が総崩れになり、ほとんどすべてのキーが別のノードへ再配置されます。
具体的に見てみましょう。ハッシュ値が0から11までのキーを、3台と4台で割り当てた比較です。
| ハッシュ値 | 3台のとき (%3) | 4台のとき (%4) | 移動するか |
|---|---|---|---|
| 0 | 0 | 0 | 変わらず |
| 1 | 1 | 1 | 変わらず |
| 2 | 2 | 2 | 変わらず |
| 3 | 0 | 3 | 移動 |
| 4 | 1 | 0 | 移動 |
| 5 | 2 | 1 | 移動 |
| 6 | 0 | 2 | 移動 |
| 7 | 1 | 3 | 移動 |
| 8 | 2 | 0 | 移動 |
| 9 | 0 | 1 | 移動 |
| 10 | 1 | 2 | 移動 |
| 11 | 2 | 3 | 移動 |
12個のうち動かないのは3個だけで、残り9個が移動します。分散キャッシュなら、この移動したキーはすべてキャッシュミスになり、一斉に元データを取りに行きます。多数のリクエストが同時に押し寄せる、いわゆるサンダリングハード（thundering herd）が起きて、バックエンドが悲鳴を上げるわけです。ノードを増やして楽をしたいのに、増やす瞬間に一番苦しくなる。これが mod N の根本的な弱点です。
ハッシュリングの原理
コンシステントハッシュの発想は明快です。ノードとキーを、同じひとつのハッシュ空間に写像する。この空間を、端と端がつながった円環（リング）として扱います。
原論文は David Karger、Eric Lehman、Tom Leighton、Matthew Levine、Daniel Lewin、Rina Panigrahy による「Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web」（STOC 1997、MIT）です。動機は当時の WWW でアクセスが集中するホットスポットを分散Webキャッシュで緩和することでした。著者のうち Daniel Lewin と Tom Leighton は1998年に Akamai を設立し、この技術は CDN の基礎になっています。
仕組みはこうです。まずノード（サーバー）の識別子をハッシュして、リング上のどこかの点に置きます。次にキーも同じハッシュ関数でリング上の点に写像します。そしてキーの位置からリングを時計回りにたどり、最初に出会ったノードにそのキーを割り当てる。ただそれだけです。
擬似コードにすると次のようになります。ノードの位置をソートして持っておき、キーのハッシュ以上で最小のノードを二分探索で探し、末尾を超えたら先頭へ回り込みます。
import bisect
class HashRing:
def __init__(self):
self.ring = [] # ソート済みの (ハッシュ値, ノード) のリスト
def add_node(self, node):
h = hash_fn(node)
bisect.insort(self.ring, (h, node)) # 位置順に挿入
def get_node(self, key):
h = hash_fn(key)
# ハッシュ値 h 以上で最初のノードを二分探索
i = bisect.bisect_left(self.ring, (h,))
if i == len(self.ring):
i = 0 # 末尾を超えたらリングの先頭へ回り込む
return self.ring[i][1]このリング構造の何が嬉しいのか。ノードを1台追加しても、影響を受けるのはリング上でそのノードの直前の区間にあるキーだけです。新しいノードは自分の位置に割り込み、「本来なら時計回りで次のノードが受け持っていたキーのうち、手前側の一部」だけを引き継ぎます。他の区間のキーは一切動きません。ノードを削除したときも同様で、消えたノードが持っていたキーが時計回りの次のノードへ移るだけです。
再配置されるキーの割合は、平均して全体の約 1/N にとどまります。総キー数を K、ノード数を N とすれば、移動するのは平均 K/N 個ということです。mod N がほぼ全キーを動かしていたのと比べると、決定的な差です。分散キャッシュにおけるこの性質は、大量アクセスをさばくレート制限や負荷分散の設計とも相性が良く、ノードの増減を運用中に安全に行える土台になります。
NOTE
リングのハッシュ空間の大きさは実装依存です。memcached クライアントの ketama は 2^32 の空間を使い、Riak は 2^160 を使います。「2^32 の円環」はあくまで一実装例であって、普遍の定数ではない点に注意してください。
仮想ノードで偏りをならす
リングは美しい仕組みですが、素のままだと弱点があります。ノードをリング上のランダムな点に1つずつ置くと、点の間隔がばらつくのです。あるノードは広い区間を受け持ち、別のノードは狭い区間しか持たない。結果として負荷が偏ります。ノードが少ないときほど、この偏りは顕著になります。さらに、ノードが1台落ちると、その負荷がまるごと隣の1台に乗ってしまう問題もあります。
これを解決するのが仮想ノード（virtual node、vnode）です。物理ノード1台を、リング上の複数の点として配置します。たとえば「node-A#1」「node-A#2」……のように識別子に連番を付けてそれぞれハッシュし、多数の点をリング全体にばらまくのです。点の数を増やすほど区間の合計は平均に近づき、仮想ノードを増やすほど負荷の偏りは小さくなります。ノードが落ちたときも、その持ち分が多数の隣接ノードへ分散して引き継がれるので、特定の1台に負荷が集中しません。
仮想ノードにはもうひとつ利点があります。ノードの性能差（heterogeneity）を吸収できることです。速いサーバーには仮想ノードを多く、遅いサーバーには少なく割り当てれば、性能に応じて負荷配分を調整できます。この仮想ノードの動機を明確に述べたのが、次に触れる Amazon Dynamo 論文（SOSP 2007）です。
運用上の数値感覚として、Apache Cassandra の num_tokens（1ノードあたりの仮想ノード数に相当）は 4.0 で既定16です（2.0時代の既定は256でした）。DataStax は「8 vnodes で負荷のばらつきが約10%に収まる」と記述しています。これは準一次の運用値ですが、仮想ノードをいくつにするかの目安になります。
実運用例
コンシステントハッシュは論文の中だけの話ではなく、現実の分散システムの土台になっています。
Amazon Dynamo（SOSP 2007、DeCandia らの論文）は、コンシステントハッシュと仮想ノードを採用した代表例です。可用性を最優先する分散キーバリューストアで、仮想ノードの必要性を論文中で明示しています。なお、現行製品の DynamoDB の内部実装が論文そのままかどうかは公開情報からは断定できないため、ここでは「Dynamo 論文が示した設計」として扱います。
Apache Cassandraは前述の num_tokens によって仮想ノードを制御し、リング上にデータを分散します。Riakは160ビットのリングを使う分散データベースです。データをどう分割して各ノードへ割り当てるかという観点は、単一ノード内のデータベースインデックスの設計とはまた別の、システム全体のシャーディング設計の話になります。
ketama / libketamaは memcached クライアント向けの実装です。Last.fm の Richard Jones が作ったもので、サーバー文字列を多数の32ビット値にハッシュして「continuum」と呼ぶリング上に配置します。ハッシュには MD5 を使います。重要なのは、これがmemcached 本体ではなくクライアント側の実装だという点です。memcached サーバーはお互いを知らず、どのサーバーにキーを置くかはクライアントライブラリが決めています。
Discordは Cassandra 上でホットパーティション対策にコンシステントハッシュを利用していると、エンジニアリングブログで述べています。アクセスが集中する一部のパーティションを、うまく分散させる用途です。
キーの設計、たとえばUUID や ULID といった分散IDをどう振るかも、リング上での分布に影響します。偏りのないハッシュ値になるキーを選ぶことは、負荷平準化の前提になります。
発展: Jump Hash / Rendezvous / Maglev
リング方式は万能ではなく、用途に応じた別のアルゴリズムがいくつも提案されています。計算量の表記はビッグオー記法で示します。
Jump Consistent Hashは John Lamping と Eric Veach（Google）による「A Fast, Minimal Memory, Consistent Hash Algorithm」（arXiv:1406.2294、2014）です。本体は約5行、追加メモリが実質不要で、分散が極めて均一という優れものです。時間計算量は期待 O(ln N)。ただし制約があります。バケットが 0..N-1 の連番でなければならず、任意のノードを途中で削除できません（末尾から減らすのは可能）。ノード集合が連番で表せるデータストア向きで、任意のサーバーが自由に増減するWebキャッシュにはリングや後述の HRW のほうが向きます。
Rendezvous Hashing（HRW、Highest Random Weight）は David Thaler と Chinya Ravishankar（University of Michigan、1996）による方式です。各ノードとキーの組について重み h(key, node) を計算し、その値が最大になるノードを選びます。リング構造が要らず実装が単純で、ノードの増減も自然に扱えます。欠点は、キーごとに全ノードを走査するため計算量が O(N) になることです。ノード数が多いと重くなります。
Maglev Hashingは Google のソフトウェアロードバランサ Maglev（NSDI 2016、Eisenbud ら）で使われるルックアップテーブル方式です。均等な分散と、障害時のコネクション維持（できるだけ既存の割り当てを崩さない最小攪乱）を両立するよう設計されています。
主な方式を比較すると次のとおりです。
| 方式 | キー探索の計算量 | 任意ノード削除 | 主な用途 |
|---|---|---|---|
| リング（仮想ノード） | O(log N) | 可能 | 分散キャッシュ、分散DB |
| Jump Consistent Hash | O(ln N) | 不可（末尾のみ） | シャード数が連番のデータストア |
| Rendezvous（HRW） | O(N) | 可能 | ノード数が少ない場面、実装の単純さ重視 |
| Maglev | テーブル参照は定数時間 | 可能 | ロードバランサ |
リング方式の O(log N) は、リング上の点をソート済み配列や平衡木（TreeMap）で持ち、二分探索でキーの割り当て先を求めるコストです。ここでの N はリング上の点数（仮想ノードを含む総数）を指します。
実装の勘所
最後に、自分で組むときや既存実装を読むときに押さえておきたい点を整理します。
ハッシュ関数の選び方。MD5、SHA-1、MurmurHash などが使われます。暗号強度は必須ではなく、むしろ出力が均等にばらけることと速いことが大事です。ketama が MD5 を使うのは分布の良さのためで、セキュリティ目的ではありません。
探索構造。リング上の点はソート済み配列に置いて二分探索するか、平衡二分探索木（Java なら TreeMap）で管理します。どちらも「あるハッシュ値以上で最小の点」を O(log N) で引ける構造です。末尾を超えたら先頭へ回り込む処理を忘れないようにします。
仮想ノードは前提。素のリングはランダム配置ゆえに必ず偏ります。実運用では仮想ノードを入れて平準化するのが基本だと考えてください。仮想ノードの数は、負荷のばらつき許容度とメモリ・探索コストのトレードオフで決めます。多すぎればリング上の点が増えてメモリと探索コストが上がり、少なすぎれば偏る、という関係です。
再配置は必ず起きる。ゼロにはできません。コンシステントハッシュが保証するのは「再配置を平均 K/N に抑える」ことであって、「再配置が起きない」ことではない点は誤解しないようにしましょう。
まとめ
コンシステントハッシュ法は、ノードの増減のたびに全データが移動してしまう mod N の弱点を、リングと時計回りの割り当てというシンプルな発想で解決します。要点を振り返ります。
mod Nはノード数が変わるとほぼ全キーが再配置され、キャッシュ全ミスとサンダリングハードを招く- ノードとキーを同じリングに写像し、時計回りで最初のノードに割り当てると、増減で動くのは平均
K/Nだけで済む - 素のリングは偏るため、仮想ノードで平準化し、性能差も吸収する
- Dynamo・Cassandra・Riak・ketama・Discord など、多くの分散システムの土台になっている
- 用途に応じて Jump Hash・Rendezvous（HRW）・Maglev といった発展手法を選ぶ
「ノードを足すたびにキャッシュが崩れる」という悩みに出会ったら、それはコンシステントハッシュの出番です。1997年の論文が今も現役で分散システムを支えている、息の長い技術です。
