Java で実装された一貫性ハッシュアルゴリズムの詳細な研究

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

コンシステントハッシュアルゴリズムについては、これまでのブログ記事で何度も触れてきました。記事「MemCache の超詳細解釈」の「コンシステントハッシュアルゴリズム」セクションでは、コンシステントハッシュアルゴリズムを使用する理由と、コンシステントハッシュアルゴリズムのアルゴリズム原理について詳しく説明しています。

アルゴリズムの具体的な原理は、ここで再度掲載されています。

まず、長さ 2 ³²の整数リング (このリングはコンシステントハッシュリングと呼ばれます) を構築し、ノード名のハッシュ値 (分布は [0, 2 ³² -1]) に従ってこのハッシュリングにサーバーノードを配置し、次にキー値 (分布も [0, 2 ³² -1]) に従ってデータのハッシュ値を計算し、最後にこのキー値のハッシュ値に最も近いサーバーノードを時計回りにハッシュリングで検索して、キーからサーバーへのマッピング検索を完了します。

このアルゴリズムは、通常の剰余ハッシュアルゴリズムのスケーラビリティが低いという問題を解決し、サーバーがオンラインまたはオフラインのときに、できるだけ多くのリクエストが元々ルーティングされたサーバーにヒットするようにすることができます。

もちろん、完璧なものはありません。コンシステントハッシュアルゴリズムは通常のハッシュアルゴリズムよりもスケーラブルですが、同時にそのアルゴリズムの実装はより複雑です。この記事では、Java コードを使用してコンシステントハッシュアルゴリズムを実装する方法について説明します。始める前に、コンシステントハッシュアルゴリズムのいくつかの中心的な問題について検討してみましょう。

データ構造の選択

一貫性のあるハッシュアルゴリズムで考慮すべき最初の問題は、長さ 2 ³²の整数リングを構築し、ノード名のハッシュ値に従ってこのハッシュリング上にサーバーノードを配置することです。

では、実行時の複雑さを最小限に抑えるには、整数リングにどのようなデータ構造を使用すればよいのでしょうか?まず、時間計算量について一つ説明させてください。時間計算量と時間効率の一般的な関係には、次のような経験則があります。

O(1) < O(log ₂ N) < O(n) < O(N * log ₂ N) < O(N ² ) < O(N ³ ) < 2N < 3N < N!

一般的に言えば、最初の 4 つはより効率的で、真ん中の 2 つは平凡で、最後の 3 つは比較的効率が悪いです (N が大きい限り、このアルゴリズムは機能しません)。さて、前のトピックを続けましょう。データ構造はどのように選択すればよいでしょうか? 実行可能な解決策はいくつかあると思います。

1. 解決策1: 並べ替え + リスト

最初に思いついたアイデアは、データ構造に追加するすべてのノード名のハッシュ値を計算して配列に入れ、何らかのソートアルゴリズムを使用して小さい順にソートし、最後にソートされたデータをリストに入れるというものです。配列ではなくリストを使用する理由は、ノードの拡張を考慮するためです。

その後、ルーティングされるノードは、ハッシュ値がそれより大きいリスト内の最初のサーバーノードを見つけるだけで済みます。たとえば、サーバーノードのハッシュ値は [0,2,4,6,8,10] で、ルーティングされるノードは 7 です。7 より大きい最初の整数、つまり 8 を見つけるだけで済みます。これが、最終的にルーティングする必要があるサーバーノードです。

今のところ前のソートを無視すると、このソリューションの時間計算量は次のようになります。

（１）最良のケースは、最初にそれを見つけることであり、その場合の時間計算量はO(1)である。

（２）最悪のケースは、それが最後に見つかった場合であり、時間計算量はO(N)である。

平均すると、時間の計算量は O(0.5N+0.5) です。先頭の係数と定数を無視すると、時間の計算量は O(N) です。

しかし、以前のソートを考慮すると、さまざまなソートアルゴリズムの時間計算量を示す図がインターネット上で見つかりました。

ソートアルゴリズムは、安定しているが時間計算量が高いか、時間計算量は低いが不安定であることがわかります。最適なマージソート方法の時間計算量は依然として O(N * logN) であり、パフォーマンスをわずかに消費しているようです。

2. 解決策2: トラバーサル + リスト

ソートはパフォーマンスを集中的に使用する操作なので、ソートしないことは可能ですか?はい、さらに、2 番目の解決策があります。

このソリューションでは、List をそのまま使用しますが、走査することができます。

（１）サーバノードはソートされず、そのハッシュ値はすべてリストに直接入れられる

（２）経路を持つノードのハッシュ値を計算します。「時計回り」が指定されているので、リストをトラバースして、ルーティングするノードよりもハッシュ値が大きいノードとの差を計算して記録します。ルーティングするノードよりもハッシュ値が小さいノードは無視します。

（３）すべての差を計算した後、最も小さい差が最終的にルーティングする必要があるノードになります。

このアルゴリズムでは、時間の複雑さを見てみましょう。

1. 最良のケースは、ルーティングノードのハッシュ値よりも大きいハッシュ値を持つサーバーノードが1つだけの場合です。時間計算量は、定数項を無視するとO(N)+O(1)=O(N+1)です。つまり、O(N)

2. 最悪のケースは、すべてのサーバーノードのハッシュ値がルーティングノードのハッシュ値よりも大きい場合です。時間計算量は、最初の係数を無視すると、O(N)+O(N)=O(2N)です。つまり、O(N)

したがって、合計時間計算量は O(N) です。実際、このアルゴリズムは少し改善することができます。位置変数 X が与えられた場合、新しい差が元の差よりも小さい場合は、X は新しい位置に置き換えられ、それ以外の場合は X は変更されません。これにより、トラバーサルのラウンドが 1 つ減りますが、改善されたアルゴリズムの時間計算量は依然として O(N) です。

全体的に見ると、このソリューションはソリューション 1 よりも優れているようです。

3. 解決策3: 二分探索木

リストデータ構造とは別に、バイナリ検索ツリーを使用するデータ構造もあります。ツリーについてよくわからない人は、この記事でツリー構造を簡単に見てみましょう。

もちろん、不均衡が生じる可能性があるため、単純にバイナリ検索ツリーを使用することはできません。バランス型二分探索木には、AVL 木、赤黒木などがあります。ここでは赤黒木を使用します。赤黒木を選択する理由は 2 つあります。

1.赤黒木の主な機能は順序付けられたデータを保存することであり、これは実際には最初の解決策の考えと一致していますが、その効率は非常に高いです。

2. JDKは赤黒木、TreeMap、TreeSetのコード実装を提供する

さらに、TreeMap を例にとると、TreeMap 自体は、赤黒木で fromKey より大きい値のセットを検索する機能をサポートする tailMap(K fromKey) メソッドを提供しますが、データ構造全体をトラバースする必要はありません。

赤黒木を使用すると、検索の時間計算量を O(logN) に削減でき、これは上記の 2 つのソリューションよりもはるかに効率的です。

この主張を検証するために、私はテストを行いました。大量のデータから、中央値より大きい最初のデータを探しました。たとえば、データが 10,000 個ある場合、5,000 より大きい最初のデータを探しました (平均的な状況をシミュレート)。 O(N) 時間計算量と O(logN) 時間計算量の実行効率の比較を見てみましょう。

	50000	100000	500000	1000000	4000000
配列リスト	1ミリ秒	1ミリ秒	4ミリ秒	4ミリ秒	5ミリ秒
リンクリスト	4ミリ秒	7ミリ秒	11ミリ秒	13ミリ秒	17ミリ秒
ツリーマップ	0ミリ秒	0ミリ秒	0ミリ秒	0ミリ秒	0ミリ秒

それ以上大きいとメモリがオーバーフローするため、4000000 データのみテストされます。 TreeMap はデータ検索効率の点ではるかに優れていることがわかります。実際、データサイズを大きくしてもテストは同じです。赤黒木のデータ構造により、N より大きい最小データは、わずか数回から数十回の検索で見つかることがわかります。

もちろん、明確に言えば、すべての利点には欠点があります。私が実施した別のテストによると、赤黒木を維持するために、TreeMap のデータ挿入効率は 3 つのデータ構造の中で最も悪く、挿入は 5 ～ 10 倍遅くなります。

ハッシュ値の再計算

サーバーノードを表すには、「192.168.1.1」、「192.168.1.2」などの文字列を使用し、文字列に基づいてハッシュ値を取得する必要があります。次に、ハッシュ値を再計算する必要があるという重要な問題があります。この問題は、String の hashCode() メソッドをテストしているときに発見されました。ハッシュ値を再計算する必要がある理由を見てみましょう。

 /**
 * StringのhashCode()メソッドの計算結果を表示する
* @author 5月のCangjie http://www.cnblogs.com/xrq730/
 *
 */  
公共 クラスStringHashCodeTest
 {
公共 静的  void main(String[] args)
    {
        System.out.println( "192.168.0.0:111 のハッシュ値: " + "192.168.0.0:1111" .hashCode());
        System.out.println( "192.168.0.1:111 ハッシュ値: " + "192.168.0.1:1111" .hashCode());
        System.out.println( "192.168.0.2:111 のハッシュ値: " + "192.168.0.2:1111" .hashCode());
        System.out.println( "192.168.0.3:111 のハッシュ値: " + "192.168.0.3:1111" .hashCode());
        System.out.println( "192.168.0.4:111 のハッシュ値: " + "192.168.0.4:1111" .hashCode());
    }
 }

クラスタリングを行う場合、クラスタポイントの IP アドレスが連続した形式で存在するのが普通です。実行結果を見てみましょう:

 192.168.0.0:111のハッシュ値: 1845870087  
 192.168.0.1:111のハッシュ値: 1874499238  
 192.168.0.2:111のハッシュ値: 1903128389  
 192.168.0.3:111のハッシュ値: 1931757540  
 192.168.0.4:111のハッシュ値: 1960386691

これは大きな問題です。区間[0,2 ³² -1]では、5つのHashCode値がこのような小さな区間にのみ分布しています。これは何を意味するのでしょうか？ [0,2 ³² -1] には 4294967296 個の数字がありますが、間隔は 122516605 しかありません。確率的な観点から見ると、ルーティングされるサーバーの 97% がクラスターポイント "192.168.0.1" にルーティングされることになりますが、これはひどいことです。

もう一つ悪い点があります。指定された間隔は非負ですが、String の hashCode() メソッドは負の数を生成します (「192.168.1.0:1111」を信頼できない場合は試してみてください)。しかし、この問題は簡単に解決できます。絶対値を取るのが一つの解決策です。

要約すると、String によって書き換えられた hashCode() メソッドは、一貫性のあるハッシュアルゴリズムでは実用的な価値がなく、HashCode を再計算するアルゴリズムを見つける必要があります。ハッシュ値を再計算するためのアルゴリズムは、CRC32_HASH、FNV1_32_HASH、KETAMA_HASH など多数あります。KETAMA_HASH は、MemCache が推奨するデフォルトの一貫性ハッシュアルゴリズムです。他のハッシュアルゴリズムも使用できます。たとえば、FNV1_32_HASH アルゴリズムは計算効率が高くなります。

一貫性ハッシュアルゴリズム実装バージョン1: 仮想ノードなし

コンシステントハッシュアルゴリズムはシステムのスケーラビリティを向上させますが、負荷分散が不均一になる可能性もあります。解決策は、実際のノードの代わりに仮想ノードを使用することです。最初のコードバージョンは、仮想ノードのないシンプルなバージョンです。

仮想ノードを使用しない一貫性ハッシュアルゴリズムの Java コード実装を見てみましょう。

 /**
 * 仮想ノードを使用しない一貫性ハッシュアルゴリズム
* @author 5月のCangjie http://www.cnblogs.com/xrq730/
 *
 */  
公共 クラスConsistentHashingWithoutVirtualNode
 {
 /**
     * ハッシュリングに追加するサーバーのリスト
     */  
プライベート 静的文字列[] サーバー = { "192.168.0.0:111" , "192.168.0.1:111" , "192.168.0.2:111" ,
 "192.168.0.3:111"、"192.168.0.4:111 " } ; 
    
 /**
     * キーはサーバーのハッシュ値を表し、値はサーバーの名前を表します
     */  
プライベート 静的SortedMap<Integer, String> sortedMap =
新しいTreeMap<Integer, String>(); 
    
 /**
     * プログラムを初期化し、すべてのサーバーをsortedMapに格納します。
     */  
静的 
    {
 ( int i = 0 ; i < servers.length; i++)の場合
        {
 intハッシュ = getHash(servers[i]);
            System.out.println( "[" + servers[i] + "] がコレクションに追加され、そのハッシュ値は " + hash);
            sortedMap.put(ハッシュ、サーバー[i]);
        }
        システム出力のprintln();
    } 
    
 /**
     * FNV1_32_HASHアルゴリズムを使用してサーバーのハッシュ値を計算します。ここではhashCodeを書き換える方法は使用されず、最終的な効果は同じです。
     */  
プライベート 静的  int getHash(文字列 str)
    {
ファイナル 整数p = 16777619 ;
 intハッシュ = ( int )2166136261L;
 ( int i = 0 ; i < str.length(); i++)の場合
            ハッシュ = (ハッシュ^str.charAt(i)) * p;
        ハッシュ += ハッシュ << 13 ;
        ハッシュ ^= ハッシュ >> 7 ;
        ハッシュ += ハッシュ << 3 ;
        ハッシュ ^= ハッシュ >> 17 ;
        ハッシュ += ハッシュ << 5 ; 
        
 // 計算値が負の場合は絶対値を取る 
ハッシュ < 0の場合
            ハッシュ = Math.abs(ハッシュ);
ハッシュを返します。
    } 
    
 /**
     * ルートを送信するノードを取得します
     */  
プライベート 静的文字列 getServer(文字列ノード)
    {
 // ルーティングを持つノードのハッシュ値を取得します 
 intハッシュ = getHash(ノード);
 // ハッシュ値より大きいすべてのマップを取得します 
        ソートマップ<整数、文字列> サブマップ =
                ソートされたマップの末尾のマップ(ハッシュ)。
 // 最初のキーは時計回りに最も近いノードです 
        整数 i = subMap.firstKey();
 // 対応するサーバー名を返す 
 subMap.get(i)を返します。
    } 
    
公共 静的  void main(String[] args)
    {
        文字列[] ノード = { "127.0.0.1:1111" , "221.226.0.1:2222" , "10.211.0.1:3333" };
 ( int i = 0 ; i < nodes.length; i++)の場合
            System.out.println( "[" + nodes[i] + "] のハッシュ値は " +
                    getHash(nodes[i]) + "、node[" + getServer(nodes[i]) + "]"にルーティングされます);
    }
 }

実行して結果を確認できます:

 [ 192.168.0.0:111 ]がコレクションに追加され、そのハッシュ値は575774686です。  
 [ 192.168.0.1:111 ] がコレクションに追加され、そのハッシュ値は8518713です。  
 [ 192.168.0.2:111 ]がコレクションに追加され、そのハッシュ値は1361847097です。  
 [ 192.168.0.3:111 ]がセットに追加され、そのハッシュ値は1171828661です。  
 [ 192.168.0.4:111 ]がコレクションに追加され、そのハッシュ値は1764547046です。   
 
 [ 127.0.0.1:1111 ]のハッシュ値は380278925であり、ノード[ 192.168.0.0:111 ]にルーティングされます。
 [ 221.226.0.1:2222 ]のハッシュ値は1493545632であり、ノード[ 192.168.0.4:111 ]にルーティングされます。
 [ 10.211.0.1:3333 ]のハッシュ値は1393836017であり、ノード[ 192.168.0.4:111 ]にルーティングされます。

FNV1_32_HASH アルゴリズムによって再計算されたハッシュ値は、元の String hashCode() メソッドよりもはるかに優れていることがわかります。実行結果から判断すると、問題はありません。3 つのポイントは、時計回りにハッシュ値に最も近いサーバーにルーティングされます。

仮想ノードを使用して一貫性のあるハッシュアルゴリズムを改善する

上記の一貫性のあるハッシュアルゴリズムの実装により、多くの分散環境で不適切なルーティングアルゴリズムによって発生するシステムのスケーラビリティの低下の問題はほぼ解決できますが、不均一な負荷という別の問題も発生します。

たとえば、ハッシュリング上に 3 つのサーバーノード A、B、C があり、それぞれ対応するサーバーに 100 件のリクエストがルーティングされます。ここで、ノード D が A と B の間に追加され、元々 B にルーティングされていたノードの一部が D にルーティングされるようになります。このようにして、A と C にルーティングされるリクエストの数は B と D にルーティングされるリクエストの数よりも大幅に多くなり、3 つのサーバーノードの元々の負荷分散が崩れます。負荷分散の目的はすべてのリクエストを対象サーバーに均等に分散することであるため、ある程度、これは負荷分散の意味を失います。

この問題の解決策は、仮想ノードを導入することです。その動作原理は、物理ノードを複数の仮想ノードに分割し、同じ物理ノードの仮想ノードをハッシュリング上で可能な限り均等に分散することです。このアプローチを採用することで、ノードを追加または削減する際の負荷不均衡の問題を効果的に解決できます。

物理ノードをいくつの仮想ノードに分割するかについては、以下の図をご覧ください。

横軸は福祉サーバーごとに拡張する必要がある仮想ノードの数を表し、縦軸は実際の物理サーバーの数を表します。物理サーバーの数が少ない場合は、より大きな仮想ノードが必要になりますが、逆に物理サーバーの数が多い場合は、より少ない仮想ノードを使用できます。たとえば、物理サーバーが 10 台ある場合、真の負荷分散を実現するには、各サーバーに 100 ～ 200 個の仮想ノードを追加する必要があります。

一貫性ハッシュアルゴリズム実装バージョン2: 仮想ノードあり

仮想ノードを使用して一貫性のあるハッシュアルゴリズムを改善する理論的根拠を理解した後、コードの開発に挑戦することができます。考慮すべきプログラミングの問題は次のとおりです。

1. 実際のノードは複数の仮想ノードにどのように対応しますか?

2. 仮想ノードが見つかった後、それを実際のノードに復元するにはどうすればよいですか?

これら 2 つの問題には、実際には多くの解決策があります。ここでは簡単な方法を使用します。仮想ノードに応じて各実ノードにサフィックスを追加し、ハッシュ値を取得します。たとえば、「192.168.0.0:111」は「192.168.0.0:111&&VN0」に、さらに「192.168.0.0:111&&VN4」に変更されます。VN は仮想ノードの略語です。復元するときは、先頭から「&&」の位置までの文字列を傍受するだけで済みます。

仮想ノードを使用した一貫性のあるハッシュアルゴリズムの Java コード実装を見てみましょう。

 /**
 * 仮想ノードによる一貫性ハッシュアルゴリズム
* @author 5月のCangjie http://www.cnblogs.com/xrq730/
 */  
公共 クラスConsistentHashingWithVirtualNode
 {
 /**
     * ハッシュリングに追加するサーバーのリスト
     */  
プライベート 静的文字列[] サーバー = { "192.168.0.0:111" , "192.168.0.1:111" , "192.168.0.2:111" ,
 "192.168.0.3:111"、"192.168.0.4:111 " } ; 
    
 /**
     * 実際のノードリスト。サーバーのオンラインとオフラインのシナリオを考慮すると、追加と削除のシナリオがより頻繁になるため、ここではLinkedListを使用する方が良いでしょう。
     */  
プライベート 静的リスト<String> realNodes =新しいLinkedList<String>(); 
    
 /**
     * 仮想ノード、キーは仮想ノードのハッシュ値を表し、値は仮想ノードの名前を表します
     */  
プライベート 静的SortedMap<Integer, String> 仮想ノード =
新しいTreeMap<Integer, String>(); 
    
 /**
     * 仮想ノードの数はここではハードコードされています。デモンストレーションの目的で、1 つの実際のノードは 5 つの仮想ノードに対応します。
     */  
プライベート 静的 ファイナル 整数VIRTUAL_NODES = 5 ; 
    
静的 
    {
 // まず元のサーバーを実ノードリストに追加します 
 ( int i = 0 ; i < servers.length; i++)の場合
            realNodes.add(サーバ[i]); 
        
 // 仮想ノードを追加し、foreach ループを使用して LinkedList を走査すると、より効率的になります。  
 (文字列 str : realNodes)の場合
        {
 ( int i = 0 ; i < VIRTUAL_NODES; i++)の場合
            {
                文字列 virtualNodeName = str + "&&VN" + String.valueOf(i);
 intハッシュ = getHash(仮想ノード名);
                System.out.println( "仮想ノード [" + virtualNodeName + "] が追加されました。ハッシュ値は " + hash);
                仮想ノードをハッシュに格納します。
            }
        }
        システム出力のprintln();
    } 
    
 /**
     * FNV1_32_HASHアルゴリズムを使用してサーバーのハッシュ値を計算します。ここではhashCodeを書き換える方法は使用されず、最終的な効果は同じです。
     */  
プライベート 静的  int getHash(文字列 str)
    {
ファイナル 整数p = 16777619 ;
 intハッシュ = ( int )2166136261L;
 ( int i = 0 ; i < str.length(); i++)の場合
            ハッシュ = (ハッシュ^str.charAt(i)) * p;
        ハッシュ += ハッシュ << 13 ;
        ハッシュ ^= ハッシュ >> 7 ;
        ハッシュ += ハッシュ << 3 ;
        ハッシュ ^= ハッシュ >> 17 ;
        ハッシュ += ハッシュ << 5 ; 
        
 // 計算値が負の場合は絶対値を取る 
ハッシュ < 0の場合
            ハッシュ = Math.abs(ハッシュ);
ハッシュを返します。
    } 
    
 /**
     * ルートを送信するノードを取得します
     */  
プライベート 静的文字列 getServer(文字列ノード)
    {
 // ルーティングを持つノードのハッシュ値を取得します 
 intハッシュ = getHash(ノード);
 // ハッシュ値より大きいすべてのマップを取得します 
        ソートマップ<整数、文字列> サブマップ =
                仮想ノードのテールマップ(ハッシュ)
 // 最初のキーは時計回りに最も近いノードです 
        整数 i = subMap.firstKey();
 // 対応する仮想ノード名を返します。ここでの文字列は少し切り捨てられます。  
        文字列仮想ノード = subMap.get(i);
 virtualNode.substring( 0 、 virtualNode.indexOf( "&&" ) )を返します。
    } 
    
公共 静的  void main(String[] args)
    {
        文字列[] ノード = { "127.0.0.1:1111" 、 "221.226.0.1:2222" 、 "10.211.0.1:3333" };
 ( int i = 0 ; i < nodes.length; i++)の場合
            System.out.println( "[" + nodes[i] + "] のハッシュ値は " +
                    getHash(nodes[i]) + "、node[" + getServer(nodes[i]) + "]"にルーティングされます);
    }
 }

実行結果に注目してください:

仮想ノード[ 192.168.0.0:111&&VN0 ]が追加され、ハッシュ値は1686427075です。  
仮想ノード[ 192.168.0.0:111&&VN1 ]が追加され、ハッシュ値は354859081です。  
仮想ノード[ 192.168.0.0:111&&VN2 ]が追加され、ハッシュ値は1306497370です。  
仮想ノード[ 192.168.0.0:111&&VN3 ]が追加され、ハッシュ値は817889914です。  
仮想ノード[ 192.168.0.0:111&&VN4 ]が追加され、ハッシュ値は396663629です。  
仮想ノード[ 192.168.0.1:111&&VN0 ]が追加され、ハッシュ値は1032739288です。  
仮想ノード[ 192.168.0.1:111&&VN1 ]が追加され、ハッシュ値は707592309です。  
仮想ノード[ 192.168.0.1:111&&VN2 ]が追加され、ハッシュ値は302114528です。  
仮想ノード[ 192.168.0.1:111&&VN3 ]が追加され、ハッシュ値は36526861です。  
仮想ノード[ 192.168.0.1:111&&VN4 ]が追加され、ハッシュ値は848442551です。  
仮想ノード[ 192.168.0.2:111&&VN0 ]が追加され、ハッシュ値は1452694222です。  
仮想ノード[ 192.168.0.2:111&&VN1 ]が追加され、ハッシュ値は2023612840です。  
仮想ノード[ 192.168.0.2:111&&VN2 ]が追加され、ハッシュ値は697907480です。  
仮想ノード[ 192.168.0.2:111&&VN3 ]が追加され、ハッシュ値は790847074です。  
仮想ノード[ 192.168.0.2:111&&VN4 ]が追加され、ハッシュ値は2010506136です。  
仮想ノード[ 192.168.0.3:111&&VN0 ]が追加され、ハッシュ値は891084251です。  
仮想ノード[ 192.168.0.3:111&&VN1 ]が追加され、ハッシュ値は1725031739です。  
仮想ノード[ 192.168.0.3:111&&VN2 ]が追加され、ハッシュ値は1127720370です。  
仮想ノード[ 192.168.0.3:111&&VN3 ]が追加され、ハッシュ値は676720500です。  
仮想ノード[ 192.168.0.3:111&&VN4 ]が追加され、ハッシュ値は2050578780です。  
仮想ノード[ 192.168.0.4:111&&VN0 ]が追加され、ハッシュ値は586921010です。  
仮想ノード[ 192.168.0.4:111&&VN1 ]が追加され、ハッシュ値は184078390です。  
仮想ノード[ 192.168.0.4:111&&VN2 ]が追加され、ハッシュ値は1331645117です。  
仮想ノード[ 192.168.0.4:111&&VN3 ]が追加され、ハッシュ値は918790803です。  
仮想ノード[ 192.168.0.4:111&&VN4 ]が追加され、ハッシュ値は1232193678です。   
 
 [ 127.0.0.1:1111 ]のハッシュ値は380278925であり、ノード[ 192.168.0.0:111 ]にルーティングされます。
 [ 221.226.0.1:2222 ]のハッシュ値は1493545632であり、ノード[ 192.168.0.0:111 ]にルーティングされます。
 [ 10.211.0.1:3333 ]のハッシュ値は1393836017であり、ノード[ 192.168.0.2:111 ]にルーティングされます。

コードの実行結果から、各ポイントがルーティングされるサーバーは、問題なく、時計回りにハッシュ値が最も近いサーバーノードであることがわかります。

仮想ノード方式を採用することで、実ノードはハッシュリング上の特定のポイントに固定されるのではなく、ハッシュリング全体に大量に分散されます。これにより、サーバーがオンラインまたはオフラインであっても、全体的な負荷の不均衡は発生しません。

追記

この記事を書くにあたり、多くの知識を勉強しながら書きました。うまく書かれていなかったり、十分に理解できていない箇所が多々あるのは仕方ありません。また、コード全体が比較的粗雑で、さまざまな状況が考慮されていません。私はただいくつかのアイデアを述べているだけです。一方では、ネットユーザーが私の間違いを指摘してくれることを願っています。他方では、私自身の仕事と研究を通じて、上記のコードを引き続き改善していきます。

<<: Facebookの広告システムの背後にあるペーシングアルゴリズム

>>: データマイニングにおけるトップ10の古典的なアルゴリズム