3

循環ハッシュアルゴリズムは、静的なターゲットのセットが与えられた場合に一貫性を提供します。例えば：

  1. 私は最初のターゲットのセットを持っています、それらをと呼びましょうA、BそしてC。
  2. 私は鍵を持っています、それを呼びましょうx
  3. 循環ハッシュ関数があります。それを呼び出しましょうhash(key, targets)
  4. 私が電話するときhash(x, [A,B,C])、x常にハッシュしますA

十分明白なようです。A私が常に与えられるという事実はx、円形ハッシュを使用するときに私が期待する一貫性を表しています。ただし、新しいノードを追加するとどうなるかを考えてみましょうD。

  1. 私のターゲットセットは、、、、およびを含むように再調整されAますBCD
  2. キーを再適用xしますhash(x, [A,B,C,D])
  3. サークルのバランスが崩れているので、もう手に入る保証はありAません

私は何かが足りないのですか、それとも運が悪いのですか？hash(x, [B,A,D,C])ノードの並べ替えを開始した場合（例）、または既存のノードリストの途中に新しいノードを挿入した場合（例） 、問題はさらに悪化しますhash(x, [A,AA,B,C,D])。循環ハッシュのアカデミックな側面を少し調べましたが、このタイプの「スケーリングの一貫性」は、その主要な懸念事項の1つではないようです。たぶん私は間違ったタイプのハッシュアルゴリズムを使用しているだけですか？

4

4 に答える 4

1

あなたの問題には非常に簡単な解決策があります。これがどのように機能するかの例です。

3 つの実際のターゲット (つまり、物理マシン) があると仮定します: A、B、C。次に、9 つの仮想ターゲット: 1、2、3、4、5、6、7、8、9 を導入し、仮想ターゲットからの静的マッピングを確立します。次のような実際のターゲットに:

1, 2, 3 -> A
4, 5, 6 -> B
7, 8, 9 -> C

いくつかのキーの値を読み書きする必要がある場合、最初にハッシュ関数を使用してキーを仮想ターゲットにマップし、次に上記の静的マッピングを使用して仮想ターゲットを実際のターゲットにマップします。実際のターゲットが複数の仮想ターゲットにサービスを提供すると、それらを個別のハッシュ マップに格納する必要があるため、実際のターゲット B には、サービスを提供する 3 つの仮想ターゲットに対して 3 つの個別のハッシュ マップがあります。

ここで、新しい実際のターゲット D を追加します。まず、静的マッピングのバランスを取り直します。たとえば、次のようにします。

1, 2, 3 -> A
4, 5 -> B
7, 8 -> C
6, 9 -> D

次に、仮想ターゲットを提供するハッシュ マップを6実際のターゲットBから新しい実際のターゲットに転送しますD。また、仮想ターゲットを提供するマップを9からに転送CしDます。この操作は、転送される値の数が複雑O(n)になります。これnは、各実際のターゲットが個別のハッシュ マップで各仮想ターゲットにサービスを提供するためです。

適切な負荷分散を行うには、仮想ターゲットの数を実際のターゲットの最大可能数の見積もりよりも数倍 (たとえば 10 倍) 大きくする必要があります。

言い換えれば、ソリューションの主なアイデアは、仮想ターゲットの数が変わらない仮想ターゲットにキーをマッピングするためにハッシュ関数が使用されるということです。次に、静的マッピングを使用して仮想ターゲットを実際のターゲットにマップします。この静的マッピングは、実際のターゲットが追加または削除されると変更されます。

于 2013-03-08T18:40:36.517 に答える
0

わかりました、私はそれを手に入れたと思います。

最終的にハッシュ アルゴリズムをシンプルに保ち、「チェックサム」(ある種の) を使用して x が常に同じターゲットにキーを設定するようにしました。新しいターゲットが追加され、システムが再調整されると、既存のすべてのターゲットに再調整について通知するだけです。このように、x がハッシュ先にハッシュされるべきではないターゲットにハッシュされた場合、ターゲットは正しいターゲットに委任できます。

すべての返信に感謝します。皆さんが提供した明確さがなければ、この解決策にたどり着かなかったかもしれません.

乾杯、

ジョン

于 2013-03-09T05:06:16.367 に答える
0

ハッシュ関数の許容出力範囲を拡大すると、一部の入力が異なる出力にハッシュされるのは当然のことです (そうでなければ、範囲を拡大しても意味がありません)。それ以外の場合の唯一の方法は、ハッシュ関数が以前のすべての結果 (またはブルーム フィルターのように圧縮された可能性のある損失の多い同じ形式) を格納する場合です。前に見た。

于 2013-03-08T03:19:28.573 に答える
0

あなたの質問全体を一貫した方法で解釈できなかったので、あなたが本当に聞きたかったことを推測し、それに基づいて答えます。

想定される問題: 多数のオブジェクト (文字列など) と多数のマシンがあり、ワークロードをマシン間で分散するために各オブジェクトをマシンに割り当てたいとします。マシンがマシンのプールに参加または脱退するとき、オブジェクトからマシンへの割り当てをあまり再シャッフルしたくありません (「スケーリングの一貫性」)。

xオブジェクトをハッシュしてプール内のマシンをマップすると言ったところに誤解があると思います[A,B,C]。私の理解では、関連する 3 つの中間ステップがあるということです。

  1. 各オブジェクトのハッシュ値を計算します。ハッシュ出力空間が、0 から 2 32 − 1 までのすべての整数のような大きなものであるとします。

  2. 各マシンに (同じ数値空間で) 値を割り当てます。この値は、寿命の間一定に保たれます。これらの数値をランダムに分散させたいと思うでしょう。

  3. ここで、各オブジェクトを最も近い上向きのマシンに属するように割り当てます。つまり、オブジェクトのハッシュが x の場合、そのオブジェクトはマシン M に属し、M の値は x より大きい最小の数になります。

例：

  1. それぞれのハッシュが 0 から 999 の範囲にある 4 つの文字列オブジェクトがあります: abc=314、def=125、ghi=802、jkl=001。

  2. X=010、Y=357、Z=768 の 3 台のマシンがあります。

  3. オブジェクト abc=314 はどのマシンに属していますか? 上から数えて、最も近いマシンは Y=357 です。
    オブジェクト ghi=802 はどのマシンに属していますか? 上から数えて、最も近いマシンは X=010 です。

于 2013-03-08T03:55:25.240 に答える