5分でコンシステントハッシュについて学ぶ

理論

コンシステント ハッシュ アルゴリズムは、一般的に使用される分散アルゴリズムです。その主な目的は、分散システム内のキーに従ってデータをハッシュし、ハッシュ結果をリングにマッピングし、データ ノードの数に応じてリングを複数の間隔に分割することです。各ノードは、リング上の特定の間隔内でデータを処理する責任を負います。

通常のハッシュ化の問題

分散クラスターでは、マシンの追加や削除、またはマシンに障害が発生した後にクラスターから自動的に離脱することが、クラスター管理の最も基本的な機能です。一般的に使用される hash(object)%N モジュロ方式を使用する場合、ノードが追加または削除された後、マッピング関係を変更するために再度移行する必要があります。そうしないと、元のデータが見つからない可能性があります。

例えば

ビジネスとトラフィックが増加するにつれて、Redis クエリ サービス ノードが 3 に拡張され、クエリ リクエストのバランスをとるために、各リクエストは同じ Redis にあり、hv = hash(key) % 3 という方法を使用して計算されます。各クエリ要求はハッシュ値によって計算され、値 0、1、2 はそれぞれサービス ノード番号に対応します。計算された hv 値は対応するノードによって処理されます。

写真

しかし、ここで問題があります。サービスの増減があった場合には、その時点でキーの再計算が必要となります。たとえば、サービスが削減される場合は、hv = hash(key) % 2 に従って計算する必要があり、サービス ノードが追加される場合は、hv = hash(key) % 4 に従って計算する必要があります。このモジュラス ベースの変更により、元のマッピング関係のほとんどが変更され、データのクエリができなくなります。

写真

現時点では、唯一の選択肢はデータ移行ですが、これは非常に面倒であり、一貫性のあるハッシュ アルゴリズムの方が明らかに優れた選択肢です。

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

コンシステント ハッシュでもモジュロ方式が使用されますが、違いはモジュロ演算が 2^32 の固定値に対して実行されることです。

一貫性のあるハッシュ アルゴリズムを使用した後、ハッシュ テーブル スロットの数 (サイズ) の変更には、平均して K/n 個のキーワードの再マッピングのみが必要になります (K はキーワードの数、n はスロットの数)。すべてのマッピング関係を再マッピングする必要はありません。

Hshリング

一貫性ハッシュ アルゴリズムの結果値を 2^32 を法としてリングに仮想化することができ、リング上のスケールは、次の図に示すように、0 から 2^32 - 1 の間の値に対応します。

写真

ノードがリングに入る

下の図では、3 つのノード (A/B/C) がハッシュされ、下のリングに配置されています。通常、サーバーの IP または一意のエイリアスに基づいてハッシュ計算を実行します。

写真

では、データはどのようにマッピングされるのでしょうか?キー値がハッシュされた後、結果がハッシュ リングにマッピングされ、結果値が時計回り方向に最も近いノードまで検索され、そのノードに値が格納されます。

以下のように表示されます。

写真

ハッシュ計算後、k1、k2、k3 はハッシュ リング内に配置され、時計回り方向に最も近いノードが検索されます。たとえば、k1 に最も近いノードは A であり、ノード A は k1 のデータ値を格納するノードです。

新しいノードの追加

新しいポイント D が追加され、ノードの数は 4 に増加します。このとき、k2 に最も近いノードは D なので、D に移行します。k1 と k3 は影響を受けません。

写真

ノードの削除

ノード B を削除した後、ノード B に格納されている k2 は、最も近いノード C を見つけるために再マップされます。このとき、k2 のデータはノード C に格納され、k1 と k3 は影響を受けません。

写真

不均衡の問題

ノードを追加および削除すると、このメソッドはノードの後の時計回りのノードに影響しますが、他のノードには影響しないことがわかります。

ただし、生成されるハッシュ値の分布は均一ではないため、次の図に示すように、k4とk5が追加されます。ノード B がダウンすると、k2 と k4 もノード C に移行され、ほとんどのリクエストがノード C に送られます。数値が大きい場合、ノード C への負荷が急激に増加し、不均衡になります。

写真

では、この問題をどう解決すればよいのでしょうか?

それは仮想ノードを通じて

仮想ノード

仮想ノードは、実際のノードのコピーとして理解できます。実際には実際のノードはそれほど多くなくても、ハッシュ リング上のノードの数が増えるほど、ノードがより均等に分散されるため、複数の仮想ノードが 1 つの実際のノードにマップされます。

写真

上図では、3 つの実ノード A、B、C が 9 つの仮想ノードにマッピングされています。ハッシュ後にキー値がA-1、A-2、A-3付近の仮想ノードに落ちた場合、最終的には実ノードAにマッピングされます。仮想ノードがもっと多ければバランスが取れると思いますか？

実ノード A が削除されると、A に対応する仮想ノードも削除されます。ただし、マルチ仮想ノード方式では、より多くの実ノードをマップできるため、残りのノードがノード変更の要求圧力にうまく対応できるようになります。

以下のように表示されます。

写真

簡単に説明します。図では、実ノード A が削除されると、対応する仮想ノードも削除されます。このとき、k1 は C-1 に再マップされ、k3 は B-3 に再マップされます。つまり、実際のノード B と C に移行されます。削除されたノードは、他のノードに均等に分散されることがわかります。

この図には、いくつかの仮想ノードがリストされているだけです。仮想ノードの数が増えるほど、バランスが取れます。

さて、コンシステント ハッシュ アルゴリズムの今日の紹介はこれで終わりです。