一貫性のあるハッシュは難しいですか?これを読んで全て理解できました

[51CTO.com からのオリジナル記事] この記事では、コンシステント ハッシュとは何か、そしてそれがスケーラブルな分散システム アーキテクチャに必要なツールである理由について説明します。

[[235312]]

さらに、大規模なアルゴリズムを実装するために使用できるデータ構造についても検討します。最後に、実際の例を見てみましょう。

コンシステントハッシュとは正確には何ですか?

大学で学んだ昔ながらの素朴なハッシュ法を覚えていますか?ハッシュ関数を使用すると、コンピュータ プログラムに必要なリソースをメモリに効率的に保存できるため、メモリ内のデータ構造が均等に読み込まれるようになります。

また、リソース ストレージ戦略によって情報検索がより効率的になり、プログラムの実行速度も速くなるようにしました。

従来のハッシュ方式では、ハッシュ関数を使用して疑似乱数を生成し、それをメモリ空間のサイズで割って、ランダム識別子を使用可能な空間内の場所に変換します。

結果は次のようになります: location = hash(key) mod size。

図1

では、ネットワーク経由のリクエストを処理するのに同じ方法を使用しないのはなぜでしょうか?

さまざまなプログラム、コンピューター、またはユーザーが複数のサーバー ノードからリソースを要求するシナリオでは、負荷分散を確保し、一貫したパフォーマンスを維持するために、要求を利用可能なサーバー ノードに均等にマップするメカニズムが必要です。

少し戻って、サーバー ノードを 1 つ以上のリクエストをマップできるプレースホルダーとして考えてみましょう。

従来のハッシュ法では、メモリ位置の数が既知であり、この数は決して変化しないと常に想定されます。

たとえば、通常は 1 日以内にクラスターのサイズを拡大または縮小し、突然の障害にも対処する必要があります。しかし、上記のシナリオを考慮すると、サーバー ノードの数が一定のままであるという保証はありません。

そのうちの 1 つが突然故障したらどうなりますか?単純なハッシュ手法を使用すると、新しいマッピングはノード/メモリ位置の数に依存するため、以下に示すように、すべてのキーのハッシュ値を再計算する必要が生じます。

図2: 以前

図3: 後

ハッシュを再計算するだけの分散システム（各キーが移動する）の問題は、状態がすべてのノードに保存されることです。

たとえば、クラスターのサイズがわずかに変更されると、クラスター内のすべてのデータを再シャッフルするために大量の作業が発生する可能性があります。

クラスターが大きくなるにつれて、ハッシュの変更ごとに必要な作業がクラスターのサイズに比例して増加するため、これは持続不可能になります。このとき、一貫性ハッシュの概念が役に立ちます。

コンシステントハッシュとは正確には何ですか?それは次のように説明できます:

• これは、リソース要求者 (このホワイト ペーパーでは「要求者」と呼びます) とサーバー ノードを仮想リング構造 (HashRing という名前) で表します。
• 位置の数は固定されなくなりましたが、リングには最大数のポイントがあると考えられ、サーバー ノードはそのリング上のランダムな位置に配置できます。

もちろん、ハッシュ関数を使用してその乱数を再度選択することもできますが、利用可能な位置の数で割る 2 番目のステップは、もはや有限の数ではないためスキップされます。

• リクエストは、ユーザー、コンピューター、またはサーバーレス プログラムであり、従来のハッシュ方法のキーに似ており、同じハッシュ関数を使用して同じリング上に配置されます。

図4

では、どのリクエストがどのサーバー ノードで処理されるかをどのように決定するのでしょうか?リングの時計回りのトラバースが位置アドレスの昇順に対応するようにリングが順序付けられていると仮定すると、各要求は時計回りのトラバースで最初に出現するサーバー ノードによって処理されます。

つまり、要求されたアドレスよりも高いアドレスを持つ最初のサーバー ノードが、要求を処理する責任を負います。要求アドレスが最高アドレスのノードよりも高い場合、リングのトラバーサルは循環的に進行するため、要求アドレスは最低アドレスのサーバー ノードによって処理されます。次の図に示すように:

図5

理論上、各サーバー ノードはハッシュ リングの範囲を「所有」し、その範囲に入るすべての要求は同じサーバー ノードによって処理されます。

さて、サーバー ノードの 1 つ (たとえばノード 3) がダウンした場合、次のサーバー ノードの範囲が広くなり、その範囲に入ってくるすべての要求が新しいサーバー ノードに送られるようになるでしょうか?

その後、この間隔 (障害が発生したサーバー ノードに対応) のみを再割り当てする必要があり、ハッシュ リングと要求/ノードの割り当ての残りの部分は影響を受けません。

これは従来のハッシュ手法とは対照的です。ハッシュ テーブルのサイズの変更は、すべてのマッピングを実質的に混乱させます。

一貫性のあるハッシュにより、特定のリングの変更によって影響を受けるリクエストは、リング割り当て係数に比べてごくわずかです。 (リングの変更は、ノードの追加または削除により一部のリクエスト/ノード マッピングが変更されるために発生します。)

図6

一貫性のあるハッシュアルゴリズムを効率的に実装するにはどうすればよいでしょうか?

ハッシュ リングが何であるかがわかったので、それを機能させるには次の部分を実装する必要があります。

• ハッシュ空間からクラスター内のノードへのマッピングにより、特定のリクエストを担当するノードを見つけることができます。
• ノードに解決されたクラスターへのリクエストのコレクション。これにより、ノードの追加または削除によって影響を受けるハッシュを把握できるようになります。

マッピング

上記の最初の部分を完了するには、次の部分が必要です。

• リクエスト識別子を指定して、リング内の位置のハッシュ関数を計算します。
• どのノードがハッシュ要求に対応するかを判断する方法。

リクエストに対応するノードを把握するために、次の部分を含む単純なデータ構造を使用してそれを表現できます。

• リング内のノードに対応するハッシュの配列。
• リクエストに対応するノードを検索するために使用されるグラフ (ハッシュ テーブル)。

これは実際には順序付きグラフの基本的な表現です。上記の構造内のハッシュ値を担当するノードを見つけるには、次の操作を行う必要があります。

• 修正バイナリ検索を実行して、検索対象のハッシュ値と等しいかそれより大きい (≥) 配列内の最初のノード/ハッシュ値を検索します。
• グラフ内で既に見つかったノード/ハッシュに対応するノードを見つけます。

ノードを追加または削除する

記事の冒頭で説明したように、新しいノードが追加されると、さまざまなリクエストを含むハッシュ リングの一部をそのノードに割り当てる必要があります。

逆に、ノードが削除されると、そのノードに割り当てられたリクエストは別のノードによって処理される必要があります。

リングの変更によって影響を受けるリクエストをどのように見つけるのでしょうか? 1 つの解決策は、ノードに割り当てられたすべてのリクエストを反復処理することです。

各リクエストについて、発生したリング変更の範囲内にあるかどうかを判断し、必要に応じて別の場所に移動します。

ただし、これを実行するために必要な作業量は、ノードに割り当てられるリクエストの数に応じて増加します。ノード数が増加すると、発生するリング変更の数も増加する傾向があるため、状況はさらに悪化します。

最悪の場合、リングの変更は局所的な障害を伴うことが多いため、リングの変更に伴う一時的な負荷によって他のノードも同様に影響を受ける可能性が高まり、システム全体に連鎖的な問題が発生する可能性があります。

これに対処するために、リクエストの再配置を可能な限り効率的にしたいと考えています。理想的には、リング上のどこかで単一のハッシュ変更によって影響を受けるリクエストを簡単に見つけることができるデータ構造にすべてのリクエストを保存します。

影響を受けるハッシュ値を効率的に見つける

クラスターにノードを追加したり、クラスターからノードを削除したりすると、リングの一部のリクエストの割り当てが変更されます。これを「影響を受ける範囲」と呼びます。影響を受ける範囲の境界がわかっていれば、リクエストを正しい場所に移動できます。

影響を受ける区間の境界を見つけるには、追加または削除されたノードのハッシュ値 H から始めて、別のノードが見つかるまで、リングに沿って H から逆方向に (図では反時計回りに) 移動します。

このノードのハッシュ値をS（開始値）と呼びます。このノードへの反時計回りのリクエストは、影響を受けないようにこのノードに送信されます。

注意: これは、何が起こるかを単純に説明したものに過ぎません。実際には、1 より大きいレプリケーション係数と特殊なレプリケーション戦略 (特定のリクエストに対して使用できるノードはごく一部) を使用するため、構造とアルゴリズムはより複雑です。

見つかったノードと追加された (または削除された) ノードの間の間隔に配置ハッシュを持つリクエストは、移動する必要があるリクエストです。

影響を受ける範囲内のリクエストを効率的に見つける

1 つの解決策は、特定のノードに対応するすべてのリクエストを反復処理し、ハッシュ値がその範囲内にあるリクエストを更新することです。

JavaScript では次のようになります。

 for (const request of requests) {
  if ( (S, H, request.hash)を含む) {
    /* リクエストは変更の影響を受ける*/
    リクエストを再配置します。
  }
 }
関数  (lowerBound、upperBound、ハッシュ)を含む{
   定数 wrapsOver = upperBound < lowerBound;
   const aboveLower = ハッシュ >= lowerBound;
   const belowUpper = upperBound >= ハッシュ;
   if (wrapsOver) {
 aboveLower || belowUpperを返します。
   }それ以外{
 aboveLower && belowUpper;を返します。
   }
 }

リングは円形なので、S <= r <H のリクエストを探すだけでは不十分です。S が H より大きい可能性があるからです (つまり、間隔がリングの上部をラップすることになります)。関数 contains() はこの状況を処理します。

リクエストの数が少ない場合、またはノードの追加や削除がまれである場合は、ノード上のすべてのリクエストを反復処理すると機能します。

ただし、ノードでのリクエスト数が増加すると、必要な作業量も増加します。さらに悪いことに、ノード数が増えると、自動スケーリングやフェイルオーバーが原因でリングの変更がより頻繁に発生する傾向があり、システム上で同期負荷再分散リクエストがトリガーされます。

最悪のシナリオでは、関連する負荷によって他のノードでの障害の可能性が高まり、システム全体に波及効果が生じる可能性があります。

この状況に対処するために、前に説明したものと同様の別のリング データ構造にリクエストを保存することもできます。このリングでは、ハッシュはそのハッシュ値のリクエストに直接マップされます。

次に、範囲内のリクエストを見つけるために次の操作を実行します。

• 間隔開始値 S 後の最初のリクエストを検索します。
• 範囲外のハッシュ値を持つリクエストが見つかるまで、時計回りに繰り返します。
• 範囲内のリクエストを再度検索します。

特定のハッシュ更新のために反復する必要があるリクエストの数は、平均して R/N です。ここで、R はノード間隔内のリクエストの数、N はリング内のハッシュ値の数であり、リクエストが均等に分散されていると仮定します。

上記の説明を実際の例とともに以下に示します。

A と B という 2 つのノードを持つクラスターがあるとします。各ノードの「配置ハッシュ値」をランダムに生成してみましょう（32 ビットのハッシュ値であると仮定）。

つまり次のようになります:

• 答え: 0x5e6058e5
• 0xa2d65c0 ...

これにより、0x0、0x1、0x2、... の数字が 0xffffffff まで連続して配置される仮想リング上にノードが配置されます。

ノード A のハッシュ値は 0x5e6058e5 なので、以下に示すように、すべてのリクエストを 0xa2d65c0+1 から 0xffffffff までと 0x0 から 0x5e6058e5 までの範囲にハッシュする役割を担います。

図7

一方、B は 0x5e6058e5+1 から 0xa2d65c0 までの範囲を担当します。したがって、ハッシュ空間全体が分散されます。

リング計算の結果が常に同じになるように、ノードからハッシュへのこのマッピングをクラスター全体で共有する必要があります。したがって、特定の要求を必要とするノードは、その要求がどこにあるかを知ることができます。

識別子「[email protected]」を持つリクエストを検索（または作成）するとします。

• 識別子のハッシュ値 H (例: 0x89e04a0a) を計算します。
• リングを調べて、ハッシュ値が H より大きい最初のノード (B) を見つけます。

したがって、B が要求を担当するノードになります。リクエストが再度必要になった場合は、上記の手順を繰り返し、必要な状態にある同じノードに再度ログインします。

この例は少し単純化しすぎており、実際にはノードごとにハッシュを 1 つ持つと、負荷がかなり不公平に分散される可能性があります。

この例では、B がリングの (0xa2d656c0-0x5e6058e5)/232 = 26.7% を担当し、A が残りを担当していることに気付いたかもしれません。理想的には、各ノードがリングの均等な部分を担当します。

これをより公平にする方法の 1 つは、次のように各ノードに対して複数のランダムなハッシュ値を生成することです。

図8

実際には、この結果はまだ不十分であることがわかったので、リングを 64 個の均等なサイズのセグメントに分割し、各ノードのハッシュ値が各セグメントのどこかに配置されることを確認しました。ただし、この詳細は重要ではありません。

目的は、負荷が均等に分散されるように、各ノードがリングの均等な部分を担当するようにすることです。 (ノードごとに複数のハッシュを持つことのもう 1 つの利点は、ハッシュをリングに徐々に追加したり、リングから徐々に削除したりできるため、負荷の急激な増加を回避できることです。)

ここで、C という新しいノードをリングに追加し、C のランダムなハッシュ値を生成するとします。

• 答え: 0x5e6058e5
• 0xa2d65c0 ...
• 0xe12f751c の続きを読む

0xa2d65c0+1 と 0xe12f751c の間のリング空間 (以前は A にハッシュされていました) は、現在 C に委任されています。以降のすべてのリクエストは、以前と同じノードにハッシュされ続けます。

この電力転送を処理するには、この間隔中にすでに A にあるすべての要求の状態をすべて C に転送する必要があります。

図9

これで、分散システムで負荷を均等に分散するためにハッシュが必要な理由がわかりました。ただし、リングの変更時にクラスター内で最小限の作業しか必要とされないようにするには、一貫性のあるハッシュが必要です。

さらに、ノードはリング上の複数の場所に存在する必要があり、これにより、負荷が統計的に均等に分散される可能性が高くなります。

リングの変更ごとにハッシュ リング全体を反復するのは非効率的です。分散システムが拡張し続けるにつれて、リングの変更によるパフォーマンスへの影響を最小限に抑えるために、何が変更されたかをより効率的に検出する方法が必要になります。この問題を解決するには、新しいインデックスとデータ型が必要です。

[51CTO オリジナル記事、パートナーサイトに転載する場合は、元の著者とソースを 51CTO.com として明記してください]