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

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

[[380706]]

この記事はWeChatパブリックアカウント「Full-Stack Cultivation Road」から転載されたもので、著者はAbao兄弟です。この記事を転載する場合は、Full Stack Xiuxian Road の公開アカウントにご連絡ください。

一貫性ハッシュを理解するには、まず従来のハッシュと大規模分散システムにおけるその限界を理解する必要があります。簡単に言えば、ハッシュとはキーと値のペアのストレージであり、キーを指定すると、関連付けられた値を非常に効率的に見つけることができます。郵便番号に基づいて都市の通りの名前を検索するとします。最も単純な実装の1つは、この情報をハッシュ辞書の形式で保存することです。 。

データが 1 つのノードまたはマシンに保存するには大きすぎる場合、およびデータを保存するにはシステム内に複数のノードまたはマシンが必要な場合、問題はさらに興味深いものになります。たとえば、複数の Web キャッシュ ミドルウェアを使用するシステムなどです。では、どのキーがどのノードに保存されているかをどのように判断するのでしょうか? この問題の最も簡単な解決策は、ハッシュ係数を使用して判断することです。 キーが与えられたら、そのキーをハッシュし、それをシステム内のノードの数で割って、そのノードにキーを配置します。同様に、キーを取得するときは、キーをハッシュし、ノード数で割って、そのノードに移動して値を取得します。上記のプロセスに対応するハッシュ アルゴリズムは次のように定義されます。

  1.  node_number = hash( key ) % N # ここで、N はノードの数です。

次の図は、マルチノード システムにおける従来のハッシュ モジュラス アルゴリズムを示しています。これに基づいて、単純な負荷分散を実現できます。

1. 従来のハッシュ係数アルゴリズムの限界

従来のハッシュと大規模分散システムにおけるその限界を分析してみましょう。ここでは、前回の記事「Bloom filter development tool youworthy」で定義した SimpleHash クラスを直接使用し、3 つのキー semlinker、kakuqo、test に対してハッシュ操作を実行して、残りを取得します。具体的なコードは次のとおりです。

  1. パブリッククラスSimpleHash {
  2.     プライベートintキャップ;
  3.     プライベートintシード; 
  4.  
  5. パブリックSimpleHash( intキャップ、 intシード){
  6.         キャップを固定します。
  7.         this.seed = シード;
  8.     } 
  9.  
  10. 公共  intハッシュ(文字列値) {
  11.  int結果 = 0;
  12.  int len ​​= 値.長さ();
  13.  ( int i = 0; i < len; i++)の場合{
  14.             結果 = シード * 結果 + value.charAt(i);
  15.         }
  16.  (cap - 1) & 結果を返します。
  17.     } 
  18.  
  19. 公共 静的void main(String[] args) {
  20.         SimpleHash simpleHash = 新しい SimpleHash(2 << 12, 8);
  21.         システム.out.println ( "node_number=hash(\"semlinker\")%3->" ​​+
  22.           simpleHash.hash( "semlinker" ) % 3);
  23.         System.out.println ( "node_number=hash(\"kakuqo\") % 3 -> " +
  24.           simpleHash.hash( "kakuqo" ) % 3);
  25.         システム.out.println ( "node_number=hash(\"test\")%3->" ​​+
  26.           simpleHash.hash( "テスト" )%3);
  27.     }
  28.  }

上記のコードが正常に実行されると、コンソールに次の結果が出力されます。

  1.  node_number = ハッシュ( "semlinker" ) % 3 -> 1
  2.  node_number = hash( "kakuqo" ) % 3 -> 2
  3.  node_number = ハッシュ( "テスト" ) % 3 -> 0

上記の出力に基づいて、次のテーブルを作成できます。

1.1 ノード削減シナリオ

分散型マルチノード システムでは、障害はよく発生します。事前の通知なしにノードに障害が発生する場合があります。この場合、システムのパフォーマンスが低下するだけで、通常の機能には影響がないと予想されます。 元の例では、ノードに障害が発生すると何が起こるでしょうか? 元の例では、3 つのノードがあります。そのうちの 1 つに障害が発生したとします。このとき、ノードの数は 3 から 2 に変わります。このとき、テーブルの状態は次のように変わります。

ノードの削減により、キーとノードのマッピング関係が変化することは明らかです。この変更は新しいキーには影響しませんが、既存のキーに対してノード マッピング エラーが発生します。「semlinker」を例に挙げます。変更前、システムには 3 つのノードがあり、キーに対応するノード番号は 1 でした。障害が発生すると、ノード数は 2 に減少し、キーに対応するノード番号は 0 になりました。

1.2 ノード追加シナリオ

分散型マルチノード システムでは、休日のプロモーションなどのシナリオでは、突然のトラフィックに対処するためにサービス ノードの容量を拡張する必要があります。 元の例の場合、ノードを追加すると何が起こるでしょうか? 元の例では、ノードは 3 つあります。容量拡張のために 1 つのノードを一時的に追加するとします。このとき、ノードの数は 3 から 4 に変わります。このとき、テーブルのステータスは次のように変わります。

当然、ノードの増加はキーとノードのマッピング関係にも変化をもたらします。この変更は新しいキーには影響しませんが、既存のキーに対してノード マッピング エラーを引き起こします。「semlinker」を例にとると、変更前のシステムには 3 つのノードがあり、キーに対応するノード番号は 1 でした。ノードを追加すると、ノード数は 4 に増加し、キーに対応するノード番号は 2 になりました。

クラスター内のノード数が変わると、以前のマッピング ルールが変わる可能性があります。クラスター内の各マシンによって提供されるサービスが同じであれば、影響はありません。ただし、分散キャッシュのようなシステムでは、マッピング ルールの失敗は、前のキャッシュの失敗を意味します。同時に多数のキャッシュ障害が発生すると、「キャッシュ アバランシェ」が発生し、壊滅的な結果を招く可能性があります。

この問題を解決するには、残りのノード上の既存のキーをすべて再配布する必要がありますが、これは非常にコストのかかる操作であり、実行中のシステムに悪影響を与える可能性があります。もちろん、既存のすべてのキーを再配布するという解決策に加えて、一貫性のあるハッシュ アルゴリズムを使用するという、もう 1 つのより良い解決策があります。

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

コンシステント ハッシュ アルゴリズムは、1997 年に MIT によって提案されました。これは、サーバーを削除または追加するときに、既存のサービス要求と要求処理サーバー間のマッピング関係をできるだけ変更しない特殊なハッシュ アルゴリズムです。一貫性のあるハッシュは、分散ハッシュ テーブル (DHT) 内の単純なハッシュ アルゴリズムの動的スケーリングの問題を解決します。

2.1 コンシステントハッシュアルゴリズムの利点

  • スケーラビリティ。一貫性のあるハッシュ アルゴリズムにより、サーバーを追加または削減してもデータ ストレージの変更が最小限に抑えられるため、従来のハッシュ アルゴリズムと比較してデータ移動のコストが大幅に削減されます。
  • データの急速な増加に適応します。データの分散には、一貫性のあるハッシュ アルゴリズムが使用されます。データが増え続けると、一部の仮想ノードに大量のデータが含まれ、仮想ノード上のデータの分散が不均一になる可能性があります。このとき、より多くのデータを含む仮想ノードを分割できます。この分割では、元の仮想ノードを 2 つに分割するだけで、すべてのデータを再ハッシュして分割する必要はありません。

仮想ノードを分割した後も物理サーバーの負荷が不均衡な場合は、サーバー間で一部の仮想ノードのストレージ分散を調整するだけで済みます。これにより、データの増加に応じて物理サーバーの数を動的に拡張でき、従来のハッシュ アルゴリズムを使用してすべてのデータを再配布するよりもコストが大幅に削減されます。

2.2 コンシステントハッシュアルゴリズムとハッシュアルゴリズムの関係

一貫性のあるハッシュ アルゴリズムは、ハッシュ アルゴリズムに基づいて提案されています。動的に変化する分散環境では、ハッシュ アルゴリズムはバランス、単調性、分散といういくつかの条件を満たす必要があります。

  • バランス: これは、ハッシュ結果が各ノードに均等に分散され、アルゴリズムの観点から負荷分散の問題が解決されることを意味します。
  • 単調性: ノードを追加または削除しても、システムの通常の動作には影響がないことを意味します。
  • 分散化: データは分散クラスター内の各ノードに分散して保存される必要があり (ノード自体にバックアップがある場合があります)、各ノードがすべてのデータを保存する必要はありません。

3. 一貫性ハッシュアルゴリズムの原理

コンシステント ハッシュ アルゴリズムは、コンシステント ハッシュ リングと呼ばれるデータ構造を通じて実装されます。このリングの始点は 0、終点は 2^32 - 1 であり、始点と終点は接続されているため、このリングの整数分布範囲は、次の図に示すように [0, 2^32-1] になります。

3.1 ハッシュリングにオブジェクトを配置する

「semlinker」、「kakuqo」、「lolo」、「fer」という 4 つのオブジェクトがあり、それぞれ o1、o2、o3、o4 と省略され、ハッシュ関数を使用してこのオブジェクトのハッシュ値を計算すると、値の範囲は [0, 2^32-1] になります。

図中のオブジェクトのマッピング関係は次のとおりです。

  1. ハッシュ(o1) = k1; ハッシュ(o2) = k2;
  2. ハッシュ(o3) = k3; ハッシュ(o4) = k4;

3.2 サーバーをハッシュリングに配置する

次に、同じハッシュ関数を使用して、サーバーをハッシュ リングに配置します。ハッシュのキーとしてサーバーの IP またはホスト名を選択できるため、各サーバーはハッシュ リング上の位置を決定できます。ここでは、cs1、cs2、cs3 という 3 つのキャッシュ サーバーがあると仮定します。

図中のサーバーのマッピング関係は次のとおりです。

  1.  hash(cs1) = t1; hash(cs2) = t2; hash(cs3) = t3; # キャッシュサーバー

3.3 オブジェクトのサーバーの選択

オブジェクトとサーバーを同じハッシュ リングに配置した後、ハッシュ リングを時計回りに検索して、オブジェクトのハッシュ値に最も近いマシン (オブジェクトが属するマシン) を探します。 o2 オブジェクトを例にとると、順序ニードルで見つかった最も近いサーバーは cs2 なので、サーバー cs2 が o2 オブジェクトをキャッシュします。サーバー cs1 はオブジェクト o1 と o3 をキャッシュし、サーバー cs3 はオブジェクト o4 をキャッシュします。

3.4 サーバーの追加

ビジネス上のニーズにより、サーバー cs4 を追加する必要があるとします。同じハッシュ操作の後、サーバーは最終的に次の図に示すように t1 サーバーと t2 サーバーの間に配置されます。

写真

上記のシナリオでは、サーバー t1 と t2 間のオブジェクトのみを再配布する必要があります。上記の例では、o3 オブジェクトのみを再割り当てする必要があります。つまり、cs4 サーバーに再配置されます。以前に分析したところ、単純なモジュロ方式を使用すると、新しいサーバーが追加されたときにキャッシュの大部分が無効になる可能性があることがわかりました。ただし、一貫性のあるハッシュ アルゴリズムを使用した後は、再割り当てが必要なオブジェクトが少数で済むため、この状況は大幅に改善されます。

3.5 サーバーの削減

cs3 サーバーに障害が発生し、サービスがオフラインになっていると仮定します。このとき、元々 cs3 サーバーに保存されていたオブジェクト o4 を cs2 サーバーに再割り当てする必要があり、他のオブジェクトは元のマシンに保存されたままです。

3.6 仮想ノード

ここではコンシステント ハッシュの基本原則を紹介しましたが、新しいサーバーを追加するときにはまだいくつかの問題があります。新しく追加されたサーバー cs4 は、cs1 サーバーの負荷のみを共有します。cs4 サーバーの追加により、サーバー cs2 および cs3 の負荷圧力は軽減されません。 cs4 サーバーのパフォーマンスが元のサーバーと同じかそれ以上である場合、この結果は期待どおりではありません。

この問題に対処するには、仮想ノードを導入することで負荷の不均衡の問題を解決できます。つまり、各物理サーバーは仮想サーバーのグループに仮想化され、仮想サーバーはハッシュ リング上に配置されます。オブジェクトのサーバーを決定する場合は、まずオブジェクトの仮想サーバーを決定し、次に仮想サーバーを使用して物理サーバーを決定する必要があります。

図中、o1、o2はオブジェクト、v1～v6は仮想サーバー、s1～s3は物理サーバーを表しています。

4. 一貫性ハッシュアルゴリズムの実装

ここでは、仮想ノードを使用しない一貫性のあるハッシュ アルゴリズムの実装のみを紹介します。

  1.  java.util.SortedMap をインポートします。
  2.  java.util.TreeMap をインポートします。 
  3.  
  4. パブリッククラス ConsistentHashingWithoutVirtualNode {
  5.     //ハッシュリングに追加するサーバーのリスト
  6.     プライベート静的文字列[]サーバー = { "192.168.0.1:8888" , "192.168.0.2:8888" ,
  7.  "192.168.0.3:8888" }; 
  8.  
  9.     //キーはサーバーのハッシュ値を表し、値はサーバーを表します
  10.     プライベート静的SortedMap< Integer 、 String> sortedMap = new TreeMap< Integer 、 String>(); 
  11.  
  12.     //プログラムの初期化、すべてのサーバーをsortedMapに格納
  13. 静的{
  14.  ( int i = 0; i < servers.length; i++) {
  15.  intハッシュ = getHash(servers[i]);
  16.             System.out.println ( "[" + servers[i] + "]がコレクションに追加され、そのハッシュ値は" + hash);
  17.             sortedMap.put(ハッシュ、サーバー[i]);
  18.         }
  19.     } 
  20.  
  21.     //ルートを送信するノードを取得します
  22.     プライベート静的文字列getServer(文字列キー) {
  23.         //キーのハッシュ値を取得する
  24. intハッシュ = getHash(キー);
  25.         //ハッシュ値より大きいすべてのマップを取得します
  26.         SortedMap< Integer 、 String> subMap = sortedMap.tailMap(hash);
  27.         サブマップが空の場合（）{
  28.             //キーより大きいハッシュ値がない場合、最初のノードから開始します
  29. 整数i = sortedMap.firstKey();
  30.             //対応するサーバーを返す
  31. sortedMap.get(i)を返します。
  32.         }それ以外{
  33.             //最初のキーは時計回りに最も近いノードです
  34. 整数i = subMap.firstKey();
  35.             //対応するサーバーを返す
  36. subMap.get(i)を返します。
  37.         }
  38.     } 
  39.  
  40.     //FNV1_32_HASHアルゴリズムを使用してサーバーのハッシュ値を計算します
  41.     プライベートスタティック  int getHash(文字列str) {
  42.         最終的なint p = 16777619;
  43. 整数ハッシュ = ( int ) 2166136261L;
  44.  ( int i = 0; i < str.length(); i++)の場合
  45.             ハッシュ = (ハッシュ^str.charAt(i)) * p;
  46.         ハッシュ += ハッシュ << 13;
  47.         ハッシュ ^= ハッシュ >> 7;
  48.         ハッシュ += ハッシュ << 3;
  49.         ハッシュ ^= ハッシュ >> 17;
  50.         ハッシュ += ハッシュ << 5; 
  51.  
  52.         // 計算値が負の場合は絶対値を取る
  53.         ハッシュ < 0 の場合
  54.             ハッシュ = Math.abs (ハッシュ);
  55. ハッシュを返します。
  56.     } 
  57.  
  58. 公共 静的void main(String[] args) {
  59.         文字列[]キー = { "semlinker" 、 "kakuqo" 、 "fer" };
  60.  ( int i = 0; i < keys.length; i++)の場合
  61.             System.out.println ( "[" + keys[i] + "] のハッシュ値は " + getHash(keys[i]) です
  62.                     + "、ノード[" + getServer(keys[i]) + "]"にルーティングされます);
  63.     } 
  64.  
  65.  }

上記のコードが正常に実行されると、コンソールに次の結果が出力されます。

  1.  [192.168.0.1:8888]がセットに追加され、そのハッシュ値は1326271016です。
  2.  [192.168.0.2:8888]がセットに追加され、そのハッシュ値は1132535844です。
  3.  [192.168.0.3:8888]がセットに追加され、そのハッシュ値は115798597です。 
  4.  
  5.  [semlinker]のハッシュ値は1549041406で、ノード[192.168.0.3:8888]にルーティングされます。
  6.  [kakuqo]のハッシュ値は463104755で、ノード[192.168.0.2:8888]にルーティングされます。
  7.  [fer]のハッシュ値は1677150790で、ノード[192.168.0.3:8888]にルーティングされます。

上記では、仮想ノードを使用しないコンシステント ハッシュ アルゴリズムの実装についてのみ紹介しました。仮想ノードを使用したコンシステント ハッシュ アルゴリズムに興味がある場合は、「コンシステント ハッシュの原則と Java 実装の分析」の記事を参照してください。

V. 結論

この記事では、分散システムにおける従来のハッシュ係数アルゴリズムの限界を例を通して紹介し、この問題の解決策として一貫性ハッシュアルゴリズムを紹介します。コンシステント ハッシュ アルゴリズムは、1997 年に MIT によって提案されました。これは、サーバーを削除または追加するときに、既存のサービス要求と要求処理サーバー間のマッピング関係をできるだけ変更しない特殊なハッシュ アルゴリズムです。コンシステント ハッシュ アルゴリズムの役割と利点、およびその他の関連知識を紹介した後、コンシステント ハッシュ アルゴリズムの原理を図の形でわかりやすく紹介し、最後に仮想ノードを使用しないコンシステント ハッシュ アルゴリズムの Java 実装を示しました。

6. 参考資料

Baidu 百科事典 - 一貫性ハッシュ

Zhihu - インタビュー必須: 一貫性のあるハッシュ アルゴリズムとは何ですか?

Leo - 一貫性ハッシュの原理の分析

CSDN - 一貫性ハッシュの原理の分析と Java での実装

コードプロジェクト - 一貫性のあるハッシュ

<<:  私の友人はソーシャルメディアのアルゴリズムの推奨に「誘惑」され、過激なグループに参加しました

>>:  会話型AIが顧客体験を向上させる方法

ブログ    

推薦する

...

ディープラーニングのこれらの落とし穴に遭遇したことがありますか?ニューラルネットワークのよくある落とし穴11選とその対処法

ニューラルネットワークがうまく動作しない場合はどうすればいいでしょうか？この記事の著者は、データの前...

ChatGPT「おばあちゃんの抜け穴」がまた人気です！亡くなった祖母のふりをして、寝る前に物語を語り、Win11 のシリアル番号をだます

最近、有名なChatGPT「おばあちゃんの脆弱性」が再び人気になっています！この伝説の「Granny...

OpenOOD アップデート v1.5: 包括的かつ正確な分布検出コード ベースとテスト プラットフォーム、オンライン ランキングとワンクリック テストをサポート

分布外 (OOD) 検出は、オープン ワールド インテリジェント システムの信頼性の高い動作に不可欠...

時速22キロのスピードと50キロの荷重で、四足の車輪付きロボット「スイスマイル」は変形することを学んだ。

テスラと「レース」を敢行する四輪ロボットを見たことがありますか?以下に示すように、かなり高速であるよ...

ジャック・マー：世界の未来を決めるのは技術ではなく、技術の背後にある人々、理想、価値観だ

5月16日、天津梅江会議展示センターで第2回世界知能大会が開幕した。アリババグループ取締役会長のジャ...

MIT、筋肉信号を使ってドローンを制御するシステムを開発

MITの研究者たちは、人間とロボットのシームレスなコラボレーションに近づく可能性のある新しいシステム...

...

人工知能技術が教育業界に与える主な影響は何ですか?

今日、人工知能技術は社会のあらゆる分野にますます大きな影響を及ぼしており、教育も例外ではありません。...

MNISTとCIFAR 10を100%の精度で「解いた」と主張する人もいる

MNIST 認識の精度は 100% に達しましたか?最近、プレプリントプラットフォームarXivに掲...

機械学習プロジェクトでオプティマイザーを選択する方法

導入いくつかの一般的なオプティマイザーを紹介し、その長所と短所を分析し、オプティマイザーを選択するた...

ただ！ Stack Overflow セルフヘルプがオープン

執筆者：ユン・チャオ「今日は、Stack Overflow にとってエキサイティングな新時代の始まり...

責任あるAIの構築

現在、AI によって完全に有効化されたプロセスを備えている企業はわずか 25% であり、これらの企業...

クラウド管理と運用にAIを適用する方法

AI は、クラウドの管理と運用に大変革をもたらすものとして台頭しています。しかし、AI とクラウド ...

App Store 中国、検索アルゴリズムを最適化：名前による検索を復活

約1週間の不安が去った後、国内のiOSアプリ開発者はようやく落ち着くことができた。中国におけるApp...