最後にもう一度、一貫性のあるハッシュについて長々と話します。

一貫性のあるハッシュについて見てきましたが、一貫性のないハッシュもあるはずです。私たちが普段話題にしているハッシュ アルゴリズムはすべて一貫性のないハッシュです。これについてはこれ以上説明する必要はありません。誰もがよく知っています。

彼を知らないなら、連れ出して殴り倒せ。

ハッシュ化は、一般的に大きな数を法として受け取り、それを異なるバケットに分配します。2、3、4、5 の 4 つの数字を含む 2 つのバケットしかないと仮定すると、2 を法としてバケット化した結果は次のようになります。

この時点で、バケットが少なすぎると考えられるため、新しいバケットを追加してハッシュ テーブルを拡張します。この時点で、すべての数値を 3 を法としてどのバケットに分割するかが必要であり、結果は次のようになります。

新しいバケットを追加した後、すべての数字の分布が変更されていることがわかります。これは、ハッシュ テーブルが拡張および縮小されるたびに、すべてのエントリの分布が再計算されることを意味します。この機能は、一部のシナリオでは受け入れられません。

では、コンシステント ハッシュとは何でしょうか? これはハッシュのアップグレード バージョンです。

分散システムにおける負荷分散の問題を解決するには、ハッシュ アルゴリズムを使用して、リクエストの一定部分を同じサーバーに送ることができます。つまり、対応するハッシュ アルゴリズムはサーバーの数に応じて設計されます。このようにして、各サーバーはリクエストの一定部分を処理し、これらのリクエストの情報を保持します。これが負荷分散の役割を果たします。

しかし、一般的なハッシュ アルゴリズムを使用すると、アルゴリズムのスケーラビリティが低いという大きな問題があります。新しいサーバーが追加されたりオフラインになったりすると、サーバーの数が変わり、ユーザー ID とサーバーのマッピング関係が無効になります。

これにより、サーバーを移行するためのリクエストが大量に発生します。たとえば、Redis サーバーはまだ 5 ですが、%5 以降は対応するサーバーにマップされます。

サーバーの数が 8 に増えると %8 となり、ハッシュ値が変わる可能性が高くなり、マッピングが元のサーバー上に存在しなくなる可能性があります。

サーバーがダウンすると、負荷分散マッピングが変更されます。サーバーが復元された後も、負荷分散マッピングは変更されます。

一貫性ハッシュアルゴリズム

コンシステントハッシュアルゴリズムもモジュロ方式を使用します。ただし、上記のモジュロ方式はサーバーの数を法としますが、コンシステントハッシュアルゴリズムは 2 の 32 乗を法とします。

つまり、コンシステント ハッシュ アルゴリズムはハッシュ空間全体を仮想リングに編成します。ハッシュ関数の値空間は 0 ~ 2^32 - 1 (32 ビットの符号なし整数) です。ハッシュ リング全体は次のようになります。

円全体は時計回りに配置されており、円の真上の点は 0 を表し、0 の右側の最初の点は 1 を表します。

2 番目のステップでは、ハッシュを使用して各サーバーをハッシュします。具体的には、ハッシュのキーワードとしてサーバーの IP またはホスト名を選択できます。このようにして、各サーバーはハッシュ リング内の位置で決定されます。たとえば、3 台のマシンがある場合、IP アドレス ハッシュを使用した後のリング空間内のサーバーの位置は次の図のようになります。

ここで、次のアルゴリズムを使用して、対応するサーバーへのデータ アクセスを特定します。

データ キーは同じハッシュ関数を使用して計算され、ハッシュ値を取得してリング上のデータの位置を決定します。

この位置から、リングに沿って時計回りに検索すると、見つかったサーバーが、検索すべきサーバーになります。

たとえば、ObjectA、ObjectB、ObjectC という 3 つのデータ オブジェクトがあるとします。ハッシュ計算後、リング空間におけるそれらの位置は次のようになります。

一貫性アルゴリズムによれば、Object -> NodeA、ObjectB -> NodeB、ObjectC -> NodeC

一貫性ハッシュアルゴリズムのフォールトトレランスとスケーラビリティ

ここで、ノード C がダウンしたとします。図から、A と B は影響を受けず、オブジェクト C のみがノード A に再配置されることがわかります。

したがって、コンシステント ハッシュ アルゴリズムでは、サーバーが利用できない場合、影響を受けるデータは、このサーバーとそのリング空間内の前のサーバー間のデータ (ここでは、ノード C とノード B 間のデータ) のみであり、他のデータは影響を受けないことがわかります。

次の図に示すように:

別のケースでは、図に示すように、サーバー ノード X をシステムに追加しました。

このとき、オブジェクト ObjectA と ObjectB は影響を受けず、オブジェクト C のみが新しいノード X に再配置されます。前述のように、コンシステント ハッシュ アルゴリズムでは、ノードを追加または削除するときにリング空間内のデータのごく一部を再配置するだけで済み、優れたフォールト トレランスとスケーラビリティを備えています。

データの偏りの問題

コンシステント ハッシュ アルゴリズム サービス ノードが少なすぎると、次の特殊なケースに示すように、ノードの分散が不均一になるため、データ スキュー (キャッシュされたオブジェクトのほとんどが特定のサーバーにキャッシュされる) が発生する可能性があります。

この時点で、大量のデータがノード A に集中しているのに対し、ノード B には少量のデータしかないことがわかります。

データの偏りの問題を解決するために、コンシステント ハッシュ アルゴリズムでは仮想ノード メカニズムが導入されています。つまり、各サーバー ノードに対して複数のハッシュが計算され、各計算結果の場所に仮想ノードと呼ばれるサービス ノードが配置されます。

具体的な操作は、図に示すように、サーバー IP またはホスト名の後に数字を追加することで実現できます。

データ配置アルゴリズムは変更されず、仮想ノードを実際のポイントにマッピングするという 1 つの手順のみを追加する必要があります。

そのため、仮想ノードを追加した後は、サービスノードが少ない場合でもデータを均等に分散できます。

一貫性のあるハッシュには多くの優れた機能があるのに、なぜ主流のハッシュ方法は一貫性がないのでしょうか?

主な理由の 1 つは、検索の効率です。通常のハッシュ クエリでは、1 回のハッシュ計算で対応するバケットを見つけることができ、アルゴリズムの時間計算量は O(1) です。ただし、コンシステント ハッシュでは、ソートされたバケットのリンク リストを形成してから、最後まで検索する必要があります。k 個のバケットのクエリ時間計算量は O(k) であるため、ハッシュは通常、一貫性のない方法で実装されます。

もう一つの言葉

コンシステント ハッシュが便利な理由は、それがアイデアでありソリューションだからです。通常、このアイデアは、Redis クラスターなど、多くの場所で使用されています。このソリューションは、クラスター ノードの動的な追加と削除にうまく対応できます。もう 1 つの例は、サブライブラリとサブテーブルです。これも考え方の 1 つです。