一貫性のあるハッシュが効率的なら、なぜ人々はどこでもそれを使用しないのですか？

Question

私はconsistent hashのいくつかの短絡を尋ねられました。しかし、私はそれが伝統的なハッシュ％Nハッシュより少しだけコストがかかると思います。タイトルが言及しているように、一貫したハッシュが非常に良い場合は、それを使用するだけです。

あなたはもっと知っていますか？誰が私に何かを教えてくれる？

Answer 1

consistent hashingを実装することは自明ではなく、ほとんどの場合、再マッピングがほとんどまたはまったくない、またはかなり高速に再マップできるハッシュテーブルがあります。

Answer 2

私が知っている一貫したハッシングの唯一の重大な欠点は、それを実装することが単純なハッシュより複雑であることです。より多くのコードとは、バグを導入する場所が増えたことを意味しますが、ここで自由に利用できるオプションがあります。

技術的には、一貫性のあるハッシュはCPUを消費します。ソートされたリストを参照してオブジェクトをマップするサーバーを決定すると、O（ログn）操作が実行されます.nはサーバーの数、サーバーあたりのスロット数、単純ハッシュはO（1）です。

実際、O（log n）は非常に速いので問題はありません。 （例：最悪の場合は8サーバX 1024スロット= 8192アイテム、多くの場合log2（8192）= 13比較）オリジナルの作者はそれをテストし、整合性のあるハッシングを使用してキャッシュサーバを計算することは、セットアップ。同様に、整合性のあるハッシュはソートされたサーバースロットのリストを格納するスペースを消費しますが、単純なハッシュはスペースを必要としませんが、必要な量はKbのオーダーでわずかです。

なぜそれがよく分かっていないのですか？私が推測しなければならないのは、学問的アイデアが産業界に伝播するのに時間がかかることがあるからだと言います。 （オリジナルの論文は1997年に書かれました）

Answer 3

mod Nに言及しているので、具体的にはハッシュテーブルについて話していると思います。私がその仮定で間違っていれば私を修正してください。すべての種類異なるものの

なぜなら、一貫性のあるハッシュ処理では、ハッシュテーブルが解決しなければならない問題を実際に解決できないからです。再ハッシュでは、おそらく大部分のハッシュテーブルはおそらく大部分の要素にかかわらず、要素の非常に大きな部分を再割り当てする必要があります。これはおそらく、テーブルのサイズを大きくするように再ハッシュすることになるからです。通常、テーブルのサイズは2次的に行われます。たとえば、テーブルが一杯になり始めると、ノードの量を倍にするなど、典型的なことです。

したがって、一貫したハッシング用語では、ノードを追加するだけではありません。私たちはノードの量を2倍にしています。つまり、ある意味で、最良の場合は、要素の半分を移動しています。確かに、一貫したハッシュ技法が動きを減らし、この理想に近づくことを試みることができますが、最良のケース改善は、全体の複雑さを変えない2倍の定数だけです。

ハッシュテーブルは、ほとんどのアプリケーションでキャッシュのパフォーマンスに関するものです。それらを速く動かすことへのすべての関心は、できるだけ速やかにコンピューティングに取り組み、可能な限り少ないメモリに触れさせることです。一貫性のあるハッシングを追加すると、おそらくこれを見ても2倍以上の減速になるでしょう。結局のところ、一貫したハッシングは悪化するだろう。

最後に、この問題は別の角度からは重要ではありません。再ハッシングを速くしたいと思っていますが、再ハッシュがまったくないことがずっと重要です。通常の実用的なシナリオでは、プログラマが再ハッシングによって問題を抱えていると判断した場合、正解はほとんどの場合、適切なサイズを選択することによって、再ハッシングを回避する（または少なくとも制限する）方法を見つけることです。これが典型的なシナリオであることを考えれば、起こってはならないもののかなりの側面構造を維持することは明らかに勝利ではなく、やはり全体的に遅くなります。

ハッシュテーブルの最適化作業のほとんどは、ハッシュをより速く計算する方法、または衝突の解決をより速く行う方法のいずれかです。これは、私たちがI/O操作をしなくてはならないため、マイクロ秒またはミリ秒単位で測定された時間スケールについて話し合っている場合に、通常は使用される一貫したハッシュに対して、はるかに小さい時間スケールで起こるものです。