# 一貫性ハッシュ法 ## 定義 一貫性ハッシュ法（consistent hashing）は、ハッシュ関数の出力空間を固定の環状空間（リング）として扱い、データ項目とノードをリング上の位置に配置するパーティショニング手法である。Karger ら（1997, STOC）により Web キャッシュのホットスポット緩和を目的に提案された。ノードの追加・離脱時に影響を受けるのは隣接ノードのみであり、大部分のデータの再配置が不要という特性を持つ。[[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]] では、[[Dynamo]] のデータパーティショニングとレプリケーションの基盤技術として採用された。 Dynamo では基本的な一貫性ハッシュ法の課題（データと負荷の不均一分散、ノード性能の異種性への非対応）に対し、**仮想ノード**（virtual nodes）を導入して改善した。各物理ノードがリング上の複数位置（トークン）を担当することで、ノード障害時の負荷分散の均等化と、ノード性能に応じたトークン数の調整を可能にした。 さらに本番運用を通じて 3 つのパーティショニング戦略が比較された: 1. **戦略 1**: ノードごとに T 個のランダムトークン（初期方式。ブートストラップが遅く、マークル木の再計算コストが高い） 2. **戦略 2**: ノードごとに T 個のランダムトークン + 等サイズパーティション（中間方式） 3. **戦略 3**: ノードごとに Q/S 個のトークン + 等サイズパーティション（最終方式。負荷分散効率が最良で、メタデータを 3 桁削減） ## 横断的知見 - **分散キャッシュにおける一貫性ハッシュ法の役割**: Facebook memcache では、クラスタ内の memcached サーバへのキー配布に一貫性ハッシュ法を採用する(Karger ら 1997 の手法をそのまま参照)。Dynamo のようなレプリケーション戦略との差異は、memcache では**キャッシュデータの永続性を保証しない**点にある。サーバの障害や eviction はデータの損失ではなく単なるキャッシュミスとして扱われるため、整合性の厳密さよりも実装のシンプルさが優先されている。(Source: [[@2013__NSDI__Scaling Memcache at Facebook]]) - Dynamo と Cassandra は一貫性ハッシュ法を同一のリング構造で採用しているが、負荷不均衡への対処法が対照的である。Dynamo は各物理ノードに複数のトークンを割り当てる**仮想ノード方式**を採用し、ノード障害時の負荷分散の均等化とノード性能差への対応を実現した。一方 Cassandra は仮想ノードを使わず、リング上の負荷情報を解析して軽負荷ノードを重負荷ノード側に移動させる**動的リバランス方式**を採用した。Cassandra の著者はこの方式が「設計と実装を扱いやすくし、負荷分散の決定を非常に決定論的にする」と述べており、仮想ノードの複雑さを回避する実用的選択として位置づけている（Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]、[[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]]）。 - 注目すべきは、後年の Apache Cassandra（1.2 以降）は結局仮想ノード方式を採用しており、論文時点の設計判断が覆されていることである。これは運用規模の拡大に伴い、動的リバランスのオペレータ介入が負担になったためと考えられる（Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]）。 - **DDIA 2E(2026)は「一貫性ハッシュ法」を Dynamo/Cassandra の実装例1つに矮小化せず、複数アルゴリズムの一般クラスとして再定義する**: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]]は一貫性ハッシュ法を「(a) 各シャードへの写像がほぼ均等、(b) シャード数変化時の移動キー数が最小、の2性質を満たすハッシュ関数」と抽象的に定義したうえで、Cassandra/ScyllaDBの方式(Karger 1997の原型に近い)に加えて highest random weight(rendezvous hashing)や jump consistent hashing を「どれを選ぶかはアプリケーション次第」として並列に紹介する。本 concept がこれまで Dynamo・Cassandra・memcache の3実装から帰納的に積み上げてきた知見(仮想ノード方式 対 動的リバランス方式)は、DDIA のこの整理では「新しいノードが既存シャードの部分範囲を引き継ぐ(Cassandra/ScyllaDB型)」対「新しいノードが個々のキーを引き継ぐ(rendezvous/jump hashing型)」という異なる軸で再分類されており、本 concept の軸(仮想ノードの有無)とは独立した分類基準が存在することがわかる。(Source: [[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]], [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]], [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]]) - **Cassandra/ScyllaDBの「ノードあたり複数ハッシュ範囲」という具体的パラメータが判明した**: 本 concept はこれまで Cassandra が仮想ノード的な機構を持つことを Cassandra 論文(2010)から把握していたが、当時は「順序保存ハッシュ + 負荷ベースの動的リバランス」であり仮想ノード非採用だった。DDIA 2E 第7章は 1.2 以降の Cassandra が採用した仮想ノード方式について、ノードあたりのハッシュ範囲数が既定 16(Cassandra)・256(ScyllaDB)であるという具体的な数値を与えており、Cassandra 論文が仮想ノード非採用の理由として述べた「決定論的な負荷分散の実現」という設計哲学が、後継バージョンではより細粒度な範囲分割(256分割)によるランダム化された負荷均等化へ転換したことを示す。(Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]], [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]]) - **「consistent」の語義がDynamo系譜のソース群を横断して一貫して強調される**: DDIA 2E 第7章は「ここでの consistent はレプリカ一貫性(第6章)やACID一貫性(第8章)とは無関係で、キーが可能な限り同じシャードに留まる性質を指す」と明示的に注記する。本 concept の既存出典(Dynamo・Cassandra・memcache論文)はこの語義の混同を直接論じていないが、いずれも一貫性ハッシュ法を可用性・パーティション耐性の文脈で使う一方でCAP的な「一貫性」を犠牲にする設計(結果整合性)を採用しており、教科書レベルでの用語整理が実務上重要であることが示唆される。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]]) - **本ページがこれまで蓄積してきたDynamo/Cassandra/memcache/DDIAという「データストアのパーティショニング」という応用に加え、教科書『Computer Networks: A Systems Approach』第9章は、構造化ピアツーピアオーバーレイ(DHT)とCDNのredirectionという、ノード探索の手段が本質的に異なる2つの応用を示す**: 本ページの既存の横断的知見はいずれもストレージシステム(Dynamo・Cassandra・memcache)における一貫性ハッシュ法の応用を扱い、いずれもクライアントまたはコーディネータノードがリング上のマッピングを直接計算してデータの格納先を決める。第9章§9.4.2が説明するPastry型の構造化オーバーレイでは、ノードとオブジェクトを同じ大きなID空間へハッシュで配置する点はDynamoと同型だが、対象を探す手段が根本的に異なる——各ノードはリング全体のマッピングを知らず、共有プレフィックスの長さに基づくルーティングテーブルを頼りに、メッセージを1ホップずつ転送しながら目的のノードへ近づいていく(DHTのルーティング)。これに対し第9章§9.4.3が説明するCDNのredirectorは、各redirectorがサーバ集合とリング上の位置の対応をすべて把握しているため、メッセージを転送する必要がなく、URLを受け取った時点で独立に最近傍サーバを直接計算できる。教科書自身がこの対比を「ピアツーピアの場合と異なり、各redirectorはサーバ集合がユニットサークル上にどう写像されるかを知っているので、独立に最近傍を選べる」と明記しており、一貫性ハッシュ法という同一の数学的手法が「ルーティングによる探索(DHT)」と「集中管理された知識による直接計算(CDN)」という異なる実行モデルの両方で使われることを示す。本ページが記録するDynamo/CassandraのようなKVS(コーディネータが直接計算する点でCDN型に近い)と合わせると、一貫性ハッシュ法の応用は「各ノードが全体を知っているか(直接計算)」「知らないか(ルーティングで探索)」という、本ページの既存の軸(仮想ノードの有無)ともDDIAの軸(範囲ベース対rendezvous/jump)とも異なる第3の分類軸を持つことが分かる。(Source: [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 9 Applications]] §9.4.2, §9.4.3) - **『ウェブオペレーション』15章(2011年)は、CassandraのDynamo由来技術を紹介する中で「コンシステントハッシュ(consistent hashing)」という訳語・術語を、Karger(1997)やDynamo論文(2007)を明示的に引用することなく実務者の共通知識として使っており、本ページが既存知見として記録する「一貫性ハッシュ法の応用の広がり(DHT・CDN・キャッシュ・KVS)」に、2011年という早い時点での実務者向け書籍への浸透という証拠を追加する**: 15章はCassandraの「その他の哲学は、Dynamoの論文の考えと同じだ」という一文に続けて「コンシステントハッシュでデータの保存先を決定し(consistent hashing)」と説明するのみで、アルゴリズムの詳細(リング構造・仮想ノード)には立ち入らない。これは本ページが記録するDynamo論文(2007年、技術的詳細)・Cassandra論文(2010年、動的リバランス)という一次資料の記述密度とは対照的に、2011年の実務書の時点で一貫性ハッシュ法が「詳細な説明を要さない前提知識」として扱われていたことを示す一次証拠であり、この概念が2007年のDynamo論文発表からわずか4年で実務コミュニティに定着していたことを裏づける。(Source: [[@2011__OReillyJapan__ウェブオペレーション - Chapter 15 非リレーショナルデータベース]] §15.2.1) ## 未解決の問い - Dynamo の戦略 3（Q/S トークン + 等サイズパーティション）はノードの追加・離脱時にトークン再配置の調整が必要であり、メンバーシップ変更の頻度が高い環境でのオーバーヘッドは定量化されているか。 - **ホットキー問題への対応**: memcache では一貫性ハッシュ法によりキーが各サーバに配布されるが、特定のキーに極端なアクセスが集中するとそのキーを担当するサーバがボトルネックになる。Facebook はこの問題をキースペースのシャーディングでなく**プール内レプリケーション**で対処する。すべてのキーを複数サーバにレプリカを持たせ、クライアントは IP アドレスを元にレプリカを選択する。(Source: [[@2013__NSDI__Scaling Memcache at Facebook]])。DDIA 2E 第7章はこれとは異なる対処(ホットキー末尾へのランダムサフィックス付与による書き込み分散)を示すが、読み取り側のコスト増(全分割キーの読み取り・結合)は解決しておらず、memcache のプール内レプリケーション方式との使い分け基準は明確化されていない。 - 一貫性ハッシュ法はキーアクセスの均一分布を前提とするが、アクセス分布に大きな偏り（ホットキー）がある場合の対処として、Dynamo は「十分な数の人気キーが分散する」と仮定している。この仮定が成立しないワークロードでの性能劣化はどの程度か。 - 仮想ノード数の最適な決定方法（物理ノードの性能特性との対応付け）に関する定量的な指針は示されているか。DDIA 2E 第7章が示す Cassandra 16/ScyllaDB 256 という具体的なノードあたり範囲数の差は、この問いに対する実装ごとの経験的解の1事例と言えるが、選定根拠は明らかにされていない。 - Cassandra は論文時点で順序保存ハッシュ関数（order preserving hash function）を採用しているが、順序保存ハッシュは範囲クエリを可能にする一方でキーの分布が偏りやすいという既知の課題がある。後の Apache Cassandra が Murmur3 ハッシュ（非順序保存）を既定にした経緯から、順序保存の実用上のトレードオフはどこまで定量化されたか。 - **rendezvous hashing・jump consistent hashing と Cassandra/ScyllaDB型(範囲ベース)の実運用上の比較**: DDIA 2E 第7章はこの3方式を並列に紹介するのみで優劣を論じない。「新しいノードが既存範囲の部分を引き継ぐ」方式と「個々のキーを引き継ぐ」方式で、実際のリバランシング時のデータ転送量・メタデータサイズ・実装複雑性にどの程度の差があるか、定量比較した文献はあるか。 ## 関連 - ソース: [[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]]（Dynamo における一貫性ハッシュ法の適用と 3 戦略の比較）/ [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]（仮想ノード非採用、動的リバランス方式）/ [[@2013__NSDI__Scaling Memcache at Facebook]]（キャッシュ用途での採用・ホットキーにはレプリケーションで対応）/ [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]]（一貫性ハッシュ法の一般定義、Cassandra/ScyllaDBのノードあたり範囲数、rendezvous/jump consistent hashingの並列紹介）/ [[@2020__SystemsApproach__Computer Networks - A Systems Approach - Chapter 9 Applications]]（構造化P2Pオーバーレイ(DHT)のルーティングによる探索とCDN redirectorの直接計算という2つの応用）/ [[@2011__OReillyJapan__ウェブオペレーション - Chapter 15 非リレーショナルデータベース]]（2011年時点で実務者の前提知識として定着していたことを示す一次資料） - 概念: [[結果整合性]]（Dynamo の整合性モデル）/ [[ゴシッププロトコル]]（リング上のノード位置伝播）/ [[LSMツリー]] / [[分散キャッシュ]] / [[データパーティショニング]] / [[オーバーレイネットワーク]](構造化P2Pオーバーレイでの応用) / [[コンテンツ配信ネットワーク]](CARP・redirectorでの応用) - エンティティ: [[Dynamo]] / [[Amazon]] / [[Apache Cassandra]] / [[Facebook]] ## 出典 - [[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]]（一貫性ハッシュ法の Dynamo への適用、仮想ノードの導入、3 つのパーティショニング戦略の本番比較） - [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]（§5.1 Partitioning——仮想ノード非採用、順序保存ハッシュ、負荷ベースの動的リバランス） - [[@2013__NSDI__Scaling Memcache at Facebook]]（memcached サーバへのキー配布、ホットキーへのプール内レプリケーションによる対処） - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 7 Sharding]]（一貫性ハッシュ法の一般定義と2性質の明文化、Cassandra既定16/ScyllaDB既定256のノードあたり範囲数、rendezvous hashing・jump consistent hashingの紹介、"consistent"の語義注記） - Larry Peterson and Bruce Davie, *Computer Networks: A Systems Approach*, 6th edition, Chapter 9: Applications, §9.4.2 Peer-to-Peer Networks, §9.4.3 Content Distribution Networks. https://book.systemsapproach.org/applications.html - [[@2011__OReillyJapan__ウェブオペレーション - Chapter 15 非リレーショナルデータベース]] §15.2.1(2011年時点でCassandraの説明に前提知識として使われた「コンシステントハッシュ」という訳語)