Java言語Consitent Hashアルゴリズム学習ノート（コード例）
本論文で研究したのは主にConsinenthashingアルゴリズムコードである。
コンセンサス・ハッシュ（Consinent Hash）
協議の概要
整合性ハッシュアルゴリズムは1997年にマサチューセッツ工科大学によって提案されました。設計目標はインターネットのホットスポット（Hot pot）問題を解決するためで、初心とCARPは非常に類似しています。一致したハッシュは、CARPが使用する簡単なハッシュアルゴリズムによってもたらされる問題を修正し、DHCTがP 2 P環境で本当に適用されるようにする。
ハッシュ・アルゴリズム
一致したハッシュは、動的に変化するCache環境において、ハッシュアルゴリズムが満たすべき4つの適応条件を提示する。
平衡性
平衡性とは、ハッシュの結果ができる限りすべてのキャッシュに分散されることであり、これにより、キャッシュ空間をすべて利用することができる。多くのハッシュアルゴリズムはこの条件を満たすことができる。
単調性（Monotonity）
単調さとは、いくつかのコンテンツが、ハッシュによってそれぞれのキャッシュに割り当てられた場合、また新しいキャッシュがシステムに追加されることを意味する。ハッシュの結果は、既存の割り当てられたコンテンツが新しいキャッシュにマッピングされてもよく、古いキャッシュセットの他のバッファにマッピングされないことを保証することができるはずである。
単純なハッシュアルゴリズムは、最も単純な線形ハッシュのような単調な要求を満たすことができない場合が多い。
x→ax＋b mod（P）
上式では、Pはキャッシュ全体のサイズを表しています。キャッシュサイズが変化すると（P 1からP 2まで）すべてのハッシュ結果が変化し、単調さの要求を満たさないことが分かります。
ハッシュ結果の変化は、キャッシュ空間が変化すると、すべてのマッピング関係がシステム内で更新される必要があることを意味する。P 2 Pシステムでは、バッファの変化は、Peerがシステムに加入するか、または終了するかに相当し、この場合はP 2 Pシステムで頻繁に発生するので、大きな計算と転送負荷をもたらす。単調さとは、ハッシュアルゴリズムがこの状況の発生を回避できることを要求することである。
分散性(Spread)
分散環境においては、端末はキャッシュをすべて見られないかもしれないが、その一部しか見られない。端末がハッシュプロセスによってキャッシュにコンテンツをマッピングすることを望む場合、異なる端末が見ているキャッシュ範囲が異なる可能性があるため、ハッシュの結果が一致せず、最終的な結果は同じコンテンツが異なる端末によって異なるキャッシュ領域にマッピングされることである。この場合は明らかに避けるべきであり、同じ内容が異なるバッファに保存され、システムの記憶効率を低下させるためである。分散性の定義は、上記のような状況が発生する深刻さである。良いハッシュアルゴリズムは、できるだけ不一致の場合の発生を避けることができるべきであり、つまり、分散をできるだけ低くすることができる。
負荷(Load)
負荷問題は実際には別の角度から分散性問題を見ている。異なる端末が同じコンテンツを異なるバッファにマッピングすることができる以上、特定のバッファについては、異なるユーザによって異なるコンテンツにマッピングされることもある。分散性と同様に、この場合も回避されるべきであり、良いハッシュアルゴリズムは、バッファの負荷をできるだけ低減することができるべきである。
表面的には、整合性ハッシュは分散バッファの問題であるが、バッファリングをP 2 PシステムのPeerと見なし、マッピングされたコンテンツを様々な共有リソース（データ、ファイル、メディアストリームなど）と見なすと、両者は実際に同じ問題を記述していることがわかる。
ルートアルゴリズム
一致したハッシュアルゴリズムでは、各ノード（P 2 PシステムのPeerに対応）がランダムに割り当てられたIDを有する。コンテンツをノードにマッピングするとき、コンテンツのキーワードとノードのIDを用いて、一致するハッシュ演算を行い、キー値を得る。一致ハッシュは、キーパッド値とノードIDが同じ値にあることを要求する。最も簡単なキーパッド値とIDは、0000から9999までの整数セットのような1次元であってもよい。
キーの値からコンテンツを格納すると、そのキーの値に最も近いIDを持つノードにコンテンツが格納されます。例えばキーパッド値1001のコンテンツは、システム内にID 1000、1010、1100のノードがあり、そのコンテンツは1000ノードにマッピングされる。
クエリに必要なルーティングを構築するために、一致ハッシュは、各ノードに、自身のノードの中で最小のID値よりも大きい上りノードと、下りノード（ID値が自身のノードの中で一番大きい値よりも小さい）の位置情報（IPアドレス）を格納するように要求する。ノードがコンテンツを検索する必要がある場合、コンテンツのキー値に基づいて、クエリ要求を上りまたは下りノードに開始することができる。クエリ要求を受信したノードが、要求されたターゲットを所有していると発見した場合、クエリ要求を開始したノードに直接に確認を返すことができる。自分の範囲ではないと発見されたら、自分のアップリンク／下りノードに要求を転送することができます。
上記のルーティング情報を維持するためには、ノードがシステムに加入／終了する際に、隣接ノードは、速やかにルート情報を更新しなければならない。これにより、ノードは、直接接続された下りノード位置情報だけでなく、一定の深さ（nホップ）の間接的な下りノード情報を知って、ノードリストを動的に維持することが要求される。ノードがシステムを終了すると、その上りノードは直接に一番近い下りノードに接続しようと試み、接続が成功したら、新しい下りノードから下りノードリストを取得し、自身のノードリストを更新する。同様に、新しいノードがシステムに加入すると、まず自身のIDに基づいて下りノードのリストを見つけ、その後、上りノードに下りノードのリストを修正するように要求し、ルーティング関係を回復させる。
討論する
一致したハッシュは、動的なネットワークトポロジにおいて、格納およびルーティングをどのように分配するか、P 2 P環境において最も重要な問題を基本的に解決する。各ノードは、少量の隣接ノードの情報を維持し、ノードがシステムに加入／ログアウトする場合、関連する少量のノードのみがトポロジのメンテナンスに参加する。これらすべては、一致したハッシュを最初の実用的なDHCアルゴリズムにする。
しかし、コンセンサス・ハッシュのルーティング・アルゴリズムにはまだ不十分な点がある。クエリプロセスでは、クエリメッセージは、O（N）ステップ（O（N）を介してNに比例して表され、Nは、システム内のノードの総数を表している）を通じて照会されたノードに到達することができる。システム規模が非常に大きい場合、ノード数が百万を超える可能性があり、このようなクエリ効率は明らかに使用の必要性を満たすことが困難であることは想像に難くない。言い換えれば、ユーザが長い待ち時間に耐えても、検索中に発生する大量のメッセージは、ネットワークに不必要な負荷を与えてしまう。
ソースコード:
以上がJava言語Consinent Hashアルゴリズム学習ノート（コード例）の全部の内容であり、皆さんの役に立つことを願っています。興味のある方は引き続き当駅の他のテーマを参照してください。友達のサポートに感謝します。
コンセンサス・ハッシュ（Consinent Hash）
協議の概要
整合性ハッシュアルゴリズムは1997年にマサチューセッツ工科大学によって提案されました。設計目標はインターネットのホットスポット（Hot pot）問題を解決するためで、初心とCARPは非常に類似しています。一致したハッシュは、CARPが使用する簡単なハッシュアルゴリズムによってもたらされる問題を修正し、DHCTがP 2 P環境で本当に適用されるようにする。
ハッシュ・アルゴリズム
一致したハッシュは、動的に変化するCache環境において、ハッシュアルゴリズムが満たすべき4つの適応条件を提示する。
平衡性
平衡性とは、ハッシュの結果ができる限りすべてのキャッシュに分散されることであり、これにより、キャッシュ空間をすべて利用することができる。多くのハッシュアルゴリズムはこの条件を満たすことができる。
単調性（Monotonity）
単調さとは、いくつかのコンテンツが、ハッシュによってそれぞれのキャッシュに割り当てられた場合、また新しいキャッシュがシステムに追加されることを意味する。ハッシュの結果は、既存の割り当てられたコンテンツが新しいキャッシュにマッピングされてもよく、古いキャッシュセットの他のバッファにマッピングされないことを保証することができるはずである。
単純なハッシュアルゴリズムは、最も単純な線形ハッシュのような単調な要求を満たすことができない場合が多い。
x→ax＋b mod（P）
上式では、Pはキャッシュ全体のサイズを表しています。キャッシュサイズが変化すると（P 1からP 2まで）すべてのハッシュ結果が変化し、単調さの要求を満たさないことが分かります。
ハッシュ結果の変化は、キャッシュ空間が変化すると、すべてのマッピング関係がシステム内で更新される必要があることを意味する。P 2 Pシステムでは、バッファの変化は、Peerがシステムに加入するか、または終了するかに相当し、この場合はP 2 Pシステムで頻繁に発生するので、大きな計算と転送負荷をもたらす。単調さとは、ハッシュアルゴリズムがこの状況の発生を回避できることを要求することである。
分散性(Spread)
分散環境においては、端末はキャッシュをすべて見られないかもしれないが、その一部しか見られない。端末がハッシュプロセスによってキャッシュにコンテンツをマッピングすることを望む場合、異なる端末が見ているキャッシュ範囲が異なる可能性があるため、ハッシュの結果が一致せず、最終的な結果は同じコンテンツが異なる端末によって異なるキャッシュ領域にマッピングされることである。この場合は明らかに避けるべきであり、同じ内容が異なるバッファに保存され、システムの記憶効率を低下させるためである。分散性の定義は、上記のような状況が発生する深刻さである。良いハッシュアルゴリズムは、できるだけ不一致の場合の発生を避けることができるべきであり、つまり、分散をできるだけ低くすることができる。
負荷(Load)
負荷問題は実際には別の角度から分散性問題を見ている。異なる端末が同じコンテンツを異なるバッファにマッピングすることができる以上、特定のバッファについては、異なるユーザによって異なるコンテンツにマッピングされることもある。分散性と同様に、この場合も回避されるべきであり、良いハッシュアルゴリズムは、バッファの負荷をできるだけ低減することができるべきである。
表面的には、整合性ハッシュは分散バッファの問題であるが、バッファリングをP 2 PシステムのPeerと見なし、マッピングされたコンテンツを様々な共有リソース（データ、ファイル、メディアストリームなど）と見なすと、両者は実際に同じ問題を記述していることがわかる。
ルートアルゴリズム
一致したハッシュアルゴリズムでは、各ノード（P 2 PシステムのPeerに対応）がランダムに割り当てられたIDを有する。コンテンツをノードにマッピングするとき、コンテンツのキーワードとノードのIDを用いて、一致するハッシュ演算を行い、キー値を得る。一致ハッシュは、キーパッド値とノードIDが同じ値にあることを要求する。最も簡単なキーパッド値とIDは、0000から9999までの整数セットのような1次元であってもよい。
キーの値からコンテンツを格納すると、そのキーの値に最も近いIDを持つノードにコンテンツが格納されます。例えばキーパッド値1001のコンテンツは、システム内にID 1000、1010、1100のノードがあり、そのコンテンツは1000ノードにマッピングされる。
クエリに必要なルーティングを構築するために、一致ハッシュは、各ノードに、自身のノードの中で最小のID値よりも大きい上りノードと、下りノード（ID値が自身のノードの中で一番大きい値よりも小さい）の位置情報（IPアドレス）を格納するように要求する。ノードがコンテンツを検索する必要がある場合、コンテンツのキー値に基づいて、クエリ要求を上りまたは下りノードに開始することができる。クエリ要求を受信したノードが、要求されたターゲットを所有していると発見した場合、クエリ要求を開始したノードに直接に確認を返すことができる。自分の範囲ではないと発見されたら、自分のアップリンク／下りノードに要求を転送することができます。
上記のルーティング情報を維持するためには、ノードがシステムに加入／終了する際に、隣接ノードは、速やかにルート情報を更新しなければならない。これにより、ノードは、直接接続された下りノード位置情報だけでなく、一定の深さ（nホップ）の間接的な下りノード情報を知って、ノードリストを動的に維持することが要求される。ノードがシステムを終了すると、その上りノードは直接に一番近い下りノードに接続しようと試み、接続が成功したら、新しい下りノードから下りノードリストを取得し、自身のノードリストを更新する。同様に、新しいノードがシステムに加入すると、まず自身のIDに基づいて下りノードのリストを見つけ、その後、上りノードに下りノードのリストを修正するように要求し、ルーティング関係を回復させる。
討論する
一致したハッシュは、動的なネットワークトポロジにおいて、格納およびルーティングをどのように分配するか、P 2 P環境において最も重要な問題を基本的に解決する。各ノードは、少量の隣接ノードの情報を維持し、ノードがシステムに加入／ログアウトする場合、関連する少量のノードのみがトポロジのメンテナンスに参加する。これらすべては、一致したハッシュを最初の実用的なDHCアルゴリズムにする。
しかし、コンセンサス・ハッシュのルーティング・アルゴリズムにはまだ不十分な点がある。クエリプロセスでは、クエリメッセージは、O（N）ステップ（O（N）を介してNに比例して表され、Nは、システム内のノードの総数を表している）を通じて照会されたノードに到達することができる。システム規模が非常に大きい場合、ノード数が百万を超える可能性があり、このようなクエリ効率は明らかに使用の必要性を満たすことが困難であることは想像に難くない。言い換えれば、ユーザが長い待ち時間に耐えても、検索中に発生する大量のメッセージは、ネットワークに不必要な負荷を与えてしまう。
ソースコード:
package heritrix;
import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash<T> {
//
private final HashFunction hashFunction;
//
private final int numberOfReplicas;
private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<T> nodes){
this.hashFunction = hashFunction;
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes){
add(node);
}
}
public void add(T node){
for (int i = 0; i < numberOfReplicas; i++){
circle.put(hashFunction.hash(node.toString() + i), node);
}
}
public void remove(T node){
for (int i = 0; i < numberOfReplicas; i++){
circle.remove(hashFunction.hash(node.toString() + i));
}
}
//
public T get(Object key){
if(circle.isEmpty()){
return null;
}
// hash
int hash = hashFunction.hash(key);
// hash
if(!circle.containsKey(hash)){
SortedMap<Integer, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
}以上がJava言語Consinent Hashアルゴリズム学習ノート（コード例）の全部の内容であり、皆さんの役に立つことを願っています。興味のある方は引き続き当駅の他のテーマを参照してください。友達のサポートに感謝します。