コンシステントハッシュアルゴリズムの詳細な説明

サーバー負荷分散を行う際には、ラウンドロビン、HASH、最小接続、応答時間、加重など、さまざまな負荷分散アルゴリズムから選択できます。その中でもハッシュアルゴリズムは最もよく使われるアルゴリズムです。

一般的なアプリケーションシナリオは次のようになります。キャッシュサービスを提供する N 台のサーバーがあり、各サーバーに要求を均等に分散するためにサーバーの負荷を分散する必要があり、各マシンがサービスの 1/N を担当します。

よく使用されるアルゴリズムは、ハッシュ結果の余り (hash() mod N) を取得することです。つまり、マシンに 0 から N-1 までの番号を付け、カスタム hash() アルゴリズムに従って、各要求の hash() 値を N で割った余り i を取得し、番号 i のマシンに要求を配布します。しかし、このアルゴリズムには致命的な問題があります。マシンがクラッシュすると、そのマシンに届くはずのリクエストを正しく処理できなくなります。このとき、障害が発生したサーバーをアルゴリズムから削除する必要があります。このとき、(N-1)/N サーバーのキャッシュデータを再計算する必要があります。新しいマシンが追加された場合は、N/(N+1) サーバーのキャッシュデータを再計算する必要があります。これは通常、システムにとって許容できないスラッシングです (大量のキャッシュ無効化やデータの移動が必要になるため)。では、影響を受けるリクエストをできるだけ少なくするために、負荷分散戦略をどのように設計すればよいのでしょうか?

コンシステントハッシュアルゴリズムは、Memcached、Key-Value Store、Bittorrent DHT、LVS で使用されています。コンシステントハッシュは、分散システムにおける負荷分散に最適なアルゴリズムであると言えます。

1. コンシステントハッシュアルゴリズムの説明

以下では、Memcached の Consistent Hashing アルゴリズムを例として使用します (Memcached の分散アルゴリズムを参照)。

ハッシュアルゴリズムの結果は一般的にunsigned int型なので、ハッシュ関数の結果は[0,232 -1]の間で均等に分布するはずです。232個の点を使って円を均等に切る場合、まずハッシュ(キー)関数に従ってサーバー(ノード)のハッシュ値を計算し、それを0から232までの円に分配します。

同じ hash(key) 関数を使用して、データを保存するキーのハッシュ値を見つけ、それを円にマッピングします。次に、データがマップされている場所から時計回りに検索を開始し、最初に見つかったサーバー (ノード) にデータを保存します。

一貫性ハッシュ原理の概略図

1. 新しいノードを追加します。新しく追加されたノードとリング上の反時計回り方向の最初のノード間のデータのみが影響を受けます (追加されたノードの時計回り方向の最初のノードの情報は、追加されたノードに移行する必要があります)。

2. ノードの削除: 元々削除されたノードとリング上の反時計回り方向の最初のノード間のデータのみが影響を受けます (削除されたノードの情報は時計回り方向の最初のノードに移行する必要があります)。したがって、コンシステントハッシュは、負荷分散におけるノードの追加と削除によって発生するハッシュ値の変動の問題を効果的に解決できます。

サーバー追加時の一貫性ハッシュ図

仮想ノード: 仮想ノードを導入する理由は、サーバー (ノード) の数が少ない場合 (たとえば、サーバーが 3 台しかない場合)、ハッシュ (キー) によって計算されたノードのハッシュ値がリング上に均等に分散されず (スパース)、各ノードに負荷が不均衡になる問題が依然として発生するためです。仮想ノードは実際のノードのレプリカと見なすことができ、本質的には実際のノードと同じです (ただしキーが異なります)。仮想ノード導入後、実際のサーバ（ノード）の数を一定の割合（例えば200倍）で拡張し、そのハッシュ（キー）値を計算してリング上に均等に分散します。負荷分散を実行すると、仮想ノードに該当するハッシュ値は、実際には実際のノードに該当します。全ての実ノードが同じ割合で仮想ノードに複製されるため、ノード数が少ない場合にリング上でハッシュ値を均等に分散させる問題が解決されます。

仮想ノードが一貫性のあるハッシュ結果に与える影響

上図からわかるように、ノード数が 10 で、実際のノードごとの仮想ノード数が実際のノード数の 100 ～ 200 倍の場合でも、結果は非常にバランスが取れています。

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

記事「Consistent Hashing」では、Consistent Hashing の Java 実装について非常に簡潔に説明しています。

 java.util.Collectionをインポートします。
 java.util.SortedMapをインポートします。
 java.util.TreeMapをインポートします。 
 
公共 クラスConsistentHash<T> { 
 
 プライベート 最終的なハッシュ関数ハッシュ関数; 
 プライベート ファイナル レプリカの数int ; 
 プライベート 最終的なSortedMap<Integer, T> 円 =新しいTreeMap<Integer, T>(); 
 
 パブリックConsistentHash(HashFunction hashFunction, int numberOfReplicas,
     コレクション<T>ノード) { 
   これは.hashFunction = hashFunction です。 
    this .numberOfReplicas = numberOfReplicas; 
 
    ( T ノード: ノード) {
     ノードを追加します。
   }
 } 
 
 公共  void add(Tノード) { 
    ( int i = 0 ; i < レプリカ数; i++) {
     ノードをハッシュ関数でハッシュします。
   }
 } 
 
 公共  void削除(T ノード) { 
    ( int i = 0 ; i < レプリカ数; i++) {
     円を削除します(hashFunction.hash(node.toString() + i));
   }
 } 
 
 パブリックT get(オブジェクトキー) { 
    （circle.isEmpty()）の場合{ 
     戻る ヌル;
   } 
    intハッシュ = hashFunction.hash(キー); 
   もし(!circle.containsKey(ハッシュ)) {
     SortedMap<Integer, T> tailMap = circle.tailMap(hash);
     ハッシュ = tailMap.isEmpty() ?circle.firstKey() : tailMap.firstKey();
   } 
   戻り値:circle.get(hash);
 } 
 
 }