16

コンシステント ハッシュに関する情報はネット上にたくさんあり、いくつかの言語での実装が利用可能です。トピックのウィキペディアのエントリは、同じ目標を持つ別のアルゴリズムを参照しています。

ランデブーハッシュ

このアルゴリズムはより単純に見え、不均一な負荷の問題に対処するためにリングの周りにレプリカ/仮想を追加する必要はありません。記事に記載されているように、O(n) で実行されるように見えますが、これは n が大きい場合に問題となりますが、O(log n) で実行するように構成できることを示す論文を参照しています。

この分野の経験を持つ人々への私の質問は、HRW ではなく一貫したハッシュを選択する理由、またはその逆を選択する理由です。これらのソリューションのいずれかがより適切な選択であるユースケースはありますか?

どうもありがとう。

4

2 に答える 2

9

2 つのアプローチのどちらかを選択する必要があり、最終的に HRW ハッシュを採用した人物として言えば、私の使用例は、再割り当ての要件がまったくない単純な負荷分散の 1 つでした。再開する。既存のデータの再調整は必要ありません。

1) Consistent Hashing には、ノードと vnode の永続的なハッシュマップが必要です (または、少なくとも賢明な実装では、要求ごとにすべてのオブジェクトを構築できます....しかし、実際にはそうしたくありません!)。HWR はそうではありません (ステートレスです)。マシンがクラスターに参加したりクラスターから離れたりするときに何も変更する必要はありません - 心配する同時実行性はありません (ただし、クライアントはクラスターの状態をよく把握しており、どちらの場合も同じです)

2) HRW の方が説明と理解が容易です (そしてコードが短くなります)。たとえば、これは Riverbed Stingray TrafficScript に実装された完全な HRW アルゴリズムです。(MD5 よりも優れたハッシュ アルゴリズムを選択できることに注意してください。このジョブにはやり過ぎです)

$nodes = pool.listActiveNodes("stingray_test");

# Get the key
$key = http.getFormParam("param");

$biggest_hash = "";
$node_selected = "";

foreach ($node in $nodes) {
   $hash_comparator = string.hashMD5($node . '-' . $key);

   # If the combined hash is the biggest we've seen, we have a candidate
   if ( $hash_comparator > $biggest_hash ) {
      $biggest_hash = $hash_comparator;
      $node_selected = $node;
   }
}

connection.setPersistenceNode( $node_selected );
​

3) HRW は、ノードを失ったり獲得したりした場合に均等な分配を提供します (適切なハッシュ関数を選択した場合)。Consistent Hashing はそれを保証するものではありませんが、十分な数の vnode があれば問題にはならないでしょう。

4) Consistent Routing の方が高速な場合があります。通常の操作では、順序は Log(N) である必要があります。ここで、N はノード数 * vnode のレプリカ係数です。ただし、多くのノードを持っていない場合 (私は持っていませんでした)、HRW はおそらく十分に高速です。

4.1) あなたが言及したように、ウィキペディアは log(N) 時間で HWR を実行する方法があると述べています。やり方がわからない！5 ノードでの O(N) 時間に満足しています.....

最終的に、HRW のシンプルさとステートレスな性質により、私は HRW を選択しました....

于 2014-07-07T14:00:25.383 に答える