一貫性のあるハッシュ

コンピュータサイエンスにおいて、コンシステントハッシュ^{[1] [2]は、}ハッシュテーブルのサイズが変更されると、平均してキーのみを再マッピングする必要がある特殊なハッシュ手法です。ここで、はキーの数、はスロットの数です。対照的に、ほとんどの従来のハッシュテーブルでは、キーとスロット間のマッピングはモジュラー操作によって定義されているため、配列のスロット数が変わるとほぼすべてのキーが再マッピングされます。 ${\displaystyle n/m}$${\displaystyle n}$${\displaystyle m}$

一貫性ハッシュは、一部のシャードがクラッシュしたり利用できなくなったりした場合でも、キャッシュキーをシャード全体に均等に分散します。 ^[3]

「コンシステントハッシュ」という用語は、MITのDavid Karger らによって、特にWeb用の分散キャッシュで使用するために導入されました。^{[4] 1997年の}Symposium on Theory of Computingのこの学術論文では、変化するWebサーバーの集団にリクエストを分散する方法として「コンシステントハッシュ」という用語が導入されました。^[5]各スロットは、分散システムまたはクラスター内のサーバーによって表されます。サーバーの追加とサーバーの削除（スケーラビリティまたは停止中）では、スロット（つまりサーバー）の数が変わったときにアイテムを再シャッフルするだけで済みます。著者は、線形ハッシュと、それが順次サーバーの追加と削除を処理する能力について言及していますが、コンシステントハッシュでは、サーバーを任意の順序で追加および削除できます。 ^{[1]この論文は後に、}分散ハッシュテーブルなどのピアツーピアネットワークでファイルを追跡するという技術的な課題に対処するために再利用されました。^{[6] [7]}${\displaystyle num\_keys/num\_slots}$

テラデータは、1986年にリリースされた分散データベース^[要出典]でこの技術を使用していましたが、この用語は使用していませんでした。テラデータは、まさにこの目的を果たすためにハッシュテーブルの概念を今でも使用しています。アカマイテクノロジーズは、科学者のダニエル・ルーウィンとF・トムソン・レイトン（「コンシステントハッシュ」という造語の共著者）によって1998年に設立されました。アカ​​マイのコンテンツ配信ネットワークでは、^[8]コンシステントハッシュはサーバーのクラスター内で負荷を分散するために使用され、安定した結婚アルゴリズムはクラスター間で負荷を分散するために使用されます。^[2]

コンシステントハッシュ法は、大規模なWebアプリケーションにおける部分的なシステム障害の影響を軽減し、システム全体に障害の影響を及ぼさずに堅牢なキャッシュを提供するためにも使用されています。^{[9]コンシステントハッシュ法は、}分散ハッシュテーブル（DHT）の基礎でもあり、ハッシュ値を使用して分散ノードセット全体のキースペースを分割し、接続されたノードのオーバーレイネットワークを構築して、キーによる効率的なノード取得を提供します。

1996 年に設計されたランデブー ハッシュは、よりシンプルで汎用的な手法です^{[引用が必要]}。これは、非常に異なる最高ランダム重み (HRW) アルゴリズムを使用して、一貫性のあるハッシュの目標を達成します。

たとえば、負荷分散の問題では、 BLOB をクラスタ上のサーバの 1 つに割り当てる必要がある場合、標準のハッシュ関数を使用してその BLOB のハッシュ値を計算し、ハッシュの結果値が であると仮定して、サーバの数 (この場合は ) を使用したモジュラ演算を実行して、BLOB を配置できるサーバを決定します。したがって、この場合、BLOB は の後継であるサーバに配置されます。ただし、停止中またはスケーリング中にサーバが追加または削除された場合 ( が変更される場合)、再ハッシュにより各サーバのすべての BLOB を再割り当てして移動する必要がありますが、この操作はコストがかかります。 ${\displaystyle n}$${\displaystyle \beta}$${\displaystyle n}$${\displaystyle \zeta =\beta \ \%\ n}$${\displaystyle {\text{server ID}}}$${\displaystyle \zeta }$${\displaystyle n}$

一貫性のあるハッシュは、クラスタ全体でサーバが追加または削除されるときに、すべての BLOB を再割り当てしなければならないという問題を回避するために設計されました。中心的な考え方は、BLOB とサーバの両方を単位円 (通常はラジアン) にマップするハッシュ関数を使用することです。たとえば、(ここで はBLOB のハッシュ、またはIP アドレスやUUIDなどのサーバの識別子) です。次に、各 BLOB は、円上に時計回りの順序で表示される次のサーバに割り当てられます。通常、バイナリ検索アルゴリズムまたは線形検索を使用して、その特定の BLOB を配置する「スポット」またはサーバを見つけます。または複雑度はそれぞれ、時計回りに行われます。各反復では、 (ここで はクラスタ内のサーバの値)という操作が実行され、BLOB を配置するサーバが検索されます。これにより、BLOB がサーバに均等に分散されます。ただし、さらに重要なのは、サーバに障害が発生して円から削除された場合、障害が発生したサーバにマップされた BLOB のみを時計回りの順序で次のサーバに再割り当てする必要があることです。同様に、新しいサーバーが追加されると、そのサーバーは単位円に追加され、そのサーバーにマップされた BLOB のみを再割り当てする必要があります。 ${\displaystyle 2\pi }$${\displaystyle \zeta =\Phi \ \%\ 360}$${\displaystyle \Phi }$${\displaystyle O(\log N)}$${\displaystyle O(N)}$${\displaystyle \zeta \ \leq \ \Psi }$${\displaystyle \Psi }$

重要なのは、サーバーが追加または削除された場合、BLOB の大部分は以前のサーバー割り当てを維持し、サーバーの追加によって再配置されるのは BLOB の一部のみであるということです。クラスター内のキャッシュ サーバー間で BLOB を移動するプロセスはコンテキストによって異なりますが、一般的には、新しく追加されたキャッシュ サーバーは「前任者」を識別し、マッピングがこのサーバーに属する (つまり、ハッシュ値が新しいサーバーのハッシュ値よりも小さい) すべての BLOB をそこから移動します。ただし、Web ページ キャッシュの場合、ほとんどの実装では、キャッシュされた BLOB が十分に小さいと仮定すると、移動やコピーは行われません。リクエストが新しく追加されたキャッシュ サーバーにヒットすると、キャッシュ ミスが発生し、実際のWeb サーバーへのリクエストが行われ、BLOB は将来のリクエストのためにローカルにキャッシュされます。以前に使用されたキャッシュ サーバー上の冗長 BLOB は、キャッシュ削除ポリシーに従って削除されます。^[10]${\displaystyle n^{th}}$${\displaystyle 1/n}$

および をそれぞれ BLOB およびサーバーの一意の識別子に使用されるハッシュ関数とします。実際には、バイナリ検索ツリー(BST) はクラスターまたはハッシュリング内で を動的に維持するために使用され、BST 内で後続または最小値を見つけるためにツリー トラバーサルが使用されます。 ${\displaystyle h_{b}(x)}$${\displaystyle h_{s}(x)}$${\displaystyle {\text{server ID}}}$

クラスターへの挿入${\displaystyle x}$

を、かつとなる BLOB のハッシュ値とします。を挿入するには、の BST 内での後続を見つけます。がすべての より大きい場合、BLOB は最小値でサーバーに配置されます。${\displaystyle \beta }$${\displaystyle h_{b}(x)=\beta \ \%\ 360}$${\displaystyle x\in \mathrm {BLOB} }$${\displaystyle h_{b}(x)=\zeta }$${\displaystyle x}$${\displaystyle \zeta }$${\displaystyle {\text{server ID}}}$${\displaystyle \zeta }$${\displaystyle {\text{server ID}}}$${\displaystyle {\text{server ID}}}$

クラスターから削除${\displaystyle x}$

BST内での後継者を探し、返された からBLOBを削除します。 に後継者がない場合は、 の最小値からBLOBを削除します。^[11]${\displaystyle \zeta }$${\displaystyle {\text{server ID}}}$${\displaystyle \zeta }$${\displaystyle {\text{server ID}}}$

クラスタにサーバーを挿入する

が、となるサーバ識別子のハッシュ値であるとします。 がの後継であるサーバから、ハッシュ値が より小さいすべての BLOB を移動します。 がすべての の中で最大である場合、関連する BLOB を のうち最小の から に移動します。^[12]${\displaystyle \Phi }$${\displaystyle h_{s}(x)=\Phi \ \%\ 360}$${\displaystyle x\in \{{\text{IP address, UUID}}\}}$${\displaystyle h_{s}(x)=\theta }$${\displaystyle \theta }$${\displaystyle {\text{server ID}}}$${\displaystyle \theta }$${\displaystyle \theta }$${\displaystyle {\text{server ID}}}$${\displaystyle {\text{server ID}}}$${\displaystyle \theta }$

クラスターからサーバーを削除する

BSTでの後継サーバーを探し、 のBLOBをその後継サーバーに移動します。 に後継サーバーがない場合は、 の最小のサーバーにBLOBを移動します。^[13]${\displaystyle \theta }$${\displaystyle \theta }$${\displaystyle \theta }$${\displaystyle {\text{server ID}}}$

クラスタ内のサーバが均一に分散されていないために発生する、ラジアン内の複数のノードの偏りを回避するために、複数のラベルが使用されます。これらの重複ラベルは「仮想ノード」と呼ばれます。つまり、クラスタ内の単一の「実際の」ラベルまたはサーバを指す複数のラベルです。クラスタ内の特定のサーバに使用される仮想ノードまたは重複ラベルの量は、その特定のサーバの「重み」と呼ばれます。^[14]

実際に負荷分散にコンシステント ハッシュを効果的に使用するには、基本的な手法にいくつかの拡張が必要です。上記の基本的なスキームでは、サーバーが故障すると、そのすべての BLOB が時計回りの順序で次のサーバーに再割り当てされ、そのサーバーの負荷が 2 倍になる可能性があります。これは望ましくない場合があります。サーバーが故障したときに BLOB がより均等に再配分されるようにするには、各サーバーを単位円上の複数の場所にハッシュできます。サーバーが故障すると、単位円上の各レプリカに割り当てられた BLOB が時計回りの順序で別のサーバーに再割り当てされ、BLOB がより均等に再配分されます。もう 1 つの拡張は、1 つの BLOB が「ホット」になり、何度もアクセスされ、複数のサーバーでホストする必要がある状況に関係します。この状況では、単位円を時計回りの順序でトラバースすることにより、BLOB を複数の連続したサーバーに割り当てることができます。 2 つの BLOB が単位円内で互いに近くハッシュされ、両方が同時に「ホット」になった場合、より複雑な実際的な考慮事項が生じます。この場合、両方の BLOB は単位円内の連続するサーバーの同じセットを使用します。この状況は、サーバーを単位円にマッピングするために各 BLOB が異なるハッシュ関数を選択することで改善できます。^[2]

1996 年に設計されたランデブー ハッシュは、より単純でより一般的な技術であり、可能なオプションセットの中から 1 つのオプションセットについて完全に分散された合意を可能にします。実際、コンシステント ハッシュはランデブー ハッシュの特殊なケースであることが示されています。その単純さと汎用性のため、ランデブー ハッシュは現在、多くのアプリケーションでコンシステント ハッシュの代わりに使用されています。 ${\displaystyle k}$${\displaystyle n}$

キー値が常に単調に増加する場合は、コンシステントハッシュよりも、単調なキーを持つハッシュテーブルを使用する代替アプローチの方が適している可能性があります。^[要出典]

これはキーの再配布にかかる平均コストであり、一貫性ハッシュの複雑さは、リング上の次のノードを見つけるためにノード角度間のバイナリ検索が必要であるという事実から生じます。 ^{[引用が必要]}${\displaystyle O(K/N)}$${\displaystyle O(\log N)}$

一貫性のあるハッシュの使用例としては、次のようなものが知られています。

• カウチベースの自動データパーティショニング^[15]
• OpenStackのオブジェクトストレージサービスSwift ^[16]
• AmazonのストレージシステムDynamoのパーティションコンポーネント^[17]
• Apache Cassandraにおけるデータ分割^[18]
• ScyllaDBにおけるデータ分割^[19]
• ヴォルデモートにおけるデータ分割^[20]
• Akkaの一貫性ハッシュルータ^[21]
• Riak、分散型キーバリューデータベース^[22]
• Gluster、ネットワーク接続ストレージファイルシステム^[23]
• アカマイコンテンツ配信ネットワーク^[24]
• Discordチャットアプリケーション^[25]
• SpiceDBの分散キャッシュへのgRPCリクエストの負荷分散^[26]
• コードアルゴリズム^[27]
• MinIOオブジェクトストレージシステム^[28]

• Moitra, Ankur (2016年2月10日). 「Advanced Algorithms, 6.854」(PDF) .マサチューセッツ工科大学. 2021年4月13日時点のオリジナルよりアーカイブ(PDF) . 2021年10月8日閲覧。
• Roughgarden, Tim; Valiant, Gregory (2021年3月28日). 「The Modern Algorithmic Toolbox, Introduction to Consistent Hashing」(PDF) .スタンフォード大学. 2021年7月25日時点のオリジナルよりアーカイブ(PDF) . 2021年10月7日閲覧。

• 一貫性ハッシュの理解
• 一貫性のあるハッシュ化、マイケル・ニールセン、2009 年 6 月 3 日
• コンシステント・ハッシング、ダニー・ルーウィン、そして Akamai の誕生
• ジャンプ コンシステント ハッシュ: 高速でメモリが最小限のコンシステント ハッシュ アルゴリズム
• ランデブーハッシュ：コンシステントハッシュの代替
• さまざまな言語での実装:
  • Ｃ
  • C++
  • C#
  • アーラン
  • 行く
  • ジャワ
  • PHP の
  • ルビー
  • パイソン
  • Python（再び）
  • パール
  • パール6