2

ご存知かもしれませんが、コンシステント ハッシュは、DHT を扱う場合に優れたアイデアです。主なアイデアは、新しいノードが追加または削除されたときにあまり影響を受けないようにすることです。

元の論文から:

マシンが一連のキャッシュに追加または削除された場合、新しいキャッシュに移動する必要があると予想されるオブジェクトの割合は、キャッシュ間でバランスの取れた負荷を維持するために必要な最小値です。

解決策は素晴らしいですが、鍵の配布がうまくいかないという現象があります。これを解決するために、元のノードのレプリカがランダムに配布されます。そのソリューションは非常にうまく機能します。確認したい場合は、このチャートを見てください。

わかりました、うまくいくようです。しかし、誰も言及していないことを私は考えていました。

1 つのノードが追加 (または削除) されるとどうなりますか? さて、配置されたノードの「前」にあるすべてのキーを再ハッシュする必要があります。これらのキーは「すべて」のキーではないため、それは良いようです。しかし、たとえば 20 個のレプリカを配置することにした場合、20 個のノードで再ハッシュの手間がかかります。

レプリカが少ないと分散が悪化しますが、レプリカが多いと再ハッシュが必要な場合の負担が大きくなります。

この状況に適した解決策は何ですか? 何か不足していますか?

4

2 に答える 2

0

ええ、私はあなたがそれを間違った方法で見ていると思います。マシンには「ノード」という用語を使用し、キャッシュされるものには「オブジェクト」という用語を使用します。

平均して、ほぼすべてのノードが、追加される新しいノードの影響を受けます。これは悪くありません。利用可能なすべてのノードに再ハッシュの負荷が分散されます。

重要な部分は、ほとんどのオブジェクトが再ハッシュの影響を受けないことです。平均して、1/nodes オブジェクトのみを再割り当てする必要があります。平均して、各ノードは 1/nodes^2 ノードの移動に対処するだけで済みます。これにより、この影響が大幅に軽減されます。

于 2015-01-15T05:33:44.217 に答える
-1

「より良い」ハッシュ関数がそのトリックを行うときに、レプリカの数を増やすことで配布の問題を解決しようとしているようです。優れたハッシュ関数は、優れた分布を提供します (MD5、SHA などを参照してください)。

于 2011-04-16T18:23:14.917 に答える