# 一貫性ハッシュ法 ## 定義 一貫性ハッシュ法（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]]）。 ## 未解決の問い - Dynamo の戦略 3（Q/S トークン + 等サイズパーティション）はノードの追加・離脱時にトークン再配置の調整が必要であり、メンバーシップ変更の頻度が高い環境でのオーバーヘッドは定量化されているか。 - **ホットキー問題への対応**: memcache では一貫性ハッシュ法によりキーが各サーバに配布されるが、特定のキーに極端なアクセスが集中するとそのキーを担当するサーバがボトルネックになる。Facebook はこの問題をキースペースのシャーディングでなく**プール内レプリケーション**で対処する。すべてのキーを複数サーバにレプリカを持たせ、クライアントは IP アドレスを元にレプリカを選択する。(Source: [[@2013__NSDI__Scaling Memcache at Facebook]]) - 一貫性ハッシュ法はキーアクセスの均一分布を前提とするが、アクセス分布に大きな偏り（ホットキー）がある場合の対処として、Dynamo は「十分な数の人気キーが分散する」と仮定している。この仮定が成立しないワークロードでの性能劣化はどの程度か。 - 仮想ノード数の最適な決定方法（物理ノードの性能特性との対応付け）に関する定量的な指針は示されているか。 - Cassandra は論文時点で順序保存ハッシュ関数（order preserving hash function）を採用しているが、順序保存ハッシュは範囲クエリを可能にする一方でキーの分布が偏りやすいという既知の課題がある。後の Apache Cassandra が Murmur3 ハッシュ（非順序保存）を既定にした経緯から、順序保存の実用上のトレードオフはどこまで定量化されたか。 ## 関連 - ソース: [[@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]]（キャッシュ用途での採用・ホットキーにはレプリケーションで対応） - 概念: [[結果整合性]]（Dynamo の整合性モデル）/ [[ゴシッププロトコル]]（リング上のノード位置伝播）/ [[LSMツリー]] / [[分散キャッシュ]] - エンティティ: [[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 サーバへのキー配布、ホットキーへのプール内レプリケーションによる対処）