4

一貫性のある hashのいくつかの欠点を尋ねられました。しかし、従来の hash%N ハッシュよりも少しコストがかかるだけだと思います。タイトルが述べたように、コンシステント ハッシュが非常に優れているのであれば、それを使用しないのはなぜでしょうか?

もっと知っていますか？誰が教えてくれる？

4

4 に答える 4

2

私が認識しているコンシステント ハッシュの唯一の重大な欠点は、単純なハッシュより実装が複雑であることです。コードが増えるということは、バグを導入する場所が増えることを意味しますが、現在は自由に利用できるオプションがあります。

技術的には、コンシステント ハッシュはもう少し多くの CPU を消費します。ソートされたリストを調べて、オブジェクトをマップするサーバーを決定するのは O(log n) 操作です。ここで、n はサーバーの数 X サーバーあたりのスロットの数ですが、単純なハッシュは O(1) です。

ただし、実際には、O(log n) は非常に高速なので問題ありません。(たとえば、8 サーバー X サーバーあたり 1024 スロット = 8192 項目、log2(8192) = 最悪の場合でも最大 13 回の比較。) 元の作成者がテストしたところ、コンシステント ハッシュを使用してキャッシュ サーバーを計算するのに 20 マイクロ秒しかかからないことがわかりました。設定。同様に、コンシステント ハッシュは、サーバー スロットの並べ替えられたリストを格納するためにスペースを消費しますが、シンプル ハッシュはスペースを必要としませんが、必要な量は非常に小さく、KB のオーダーです。

なぜあまり知られていないのでしょうか。推測するなら、学術的なアイデアが産業界に広まるには時間がかかるからだと思います。(元の論文は 1997 年に書かれました。)

于 2012-04-25T20:37:32.537 に答える
1

コンシステント ハッシュの実装は簡単ではなく、多くの場合、再マッピングがほとんどまたはまったく必要ないか、かなり高速に再マッピングできるハッシュ テーブルがあります。

于 2011-06-28T09:44:28.900 に答える
0

mod Nについて言及しているので、特にハッシュテーブルについて話していると思います。ハッシュはあらゆる種類の異なるものに使用されるため、その仮定が間違っている場合は修正してください。

その理由は、コンシステント ハッシュでは、ハッシュ テーブルが緊急に解決しなければならない問題を実際には解決できないからです。再ハッシュの際、ハッシュ テーブルはおそらくその要素の非常に多くの部分、場合によってはそれらの大部分を再割り当てする必要があります。これはおそらく、テーブルのサイズを大きくするために再ハッシュを行っているためです。これは通常、2 次的に行われます。たとえば、テーブルがいっぱいになり始めたら、ノードの量を 2 倍にするのが非常に一般的です。

したがって、一貫したハッシュ用語では、ノードを追加するだけではありません。ノードの数を 2 倍にしています。つまり、どういうわけか、最良の場合、要素の半分を移動しています。確かに、一貫したハッシング手法は動きを減らし、この理想に近づこうとすることができますが、最良の場合の改善は定数の 2 倍にすぎず、全体的な複雑さは変わりません。

反対側からアプローチすると、ほとんどのアプリケーションでは、ハッシュ テーブルはすべてキャッシュ パフォーマンスに関するものです。それらを高速化するためのすべての関心は、可能な限りメモリを使用せずに、可能な限り高速に計算することにあります。これをどのように見ても、コンシステント ハッシュを追加すると、おそらく 2 倍以上の速度低下になるでしょう。最終的に、コンシステント ハッシュはさらに悪化します。

最後に、この問題全体は、別の角度から見ると重要ではありません。再ハッシュを高速にしたいのですが、再ハッシュをまったく行わないことがより重要です。通常の実用的なシナリオでは、再ハッシュが原因で問題が発生していることにプログラマーが気付いた場合、適切なサイズを最初に選択して、再ハッシュを回避する (または少なくとも制限する) 方法を見つけることが、ほぼ常に正しい答えです。これが典型的なシナリオであることを考えると、起こってはならないことに対してかなり実質的なサイドストラクチャーを維持することは明らかに勝利ではなく、全体的に遅くなります。

ハッシュテーブルの最適化作業のほぼすべては、ハッシュをより速く計算する方法、または衝突解決をより速く実行する方法のいずれかにあります。これらは、I/O 操作を実行する必要があるため、マイクロ秒またはミリ秒単位で測定される時間スケールについて話している場合に通常使用されるコンシステント ハッシュよりもはるかに短い時間スケールで発生するものです。

于 2015-01-15T06:14:23.773 に答える
0

その理由は、コンシステント ハッシュは、範囲スキャン クエリの読み取り側でより多くの作業を引き起こす傾向があるためです。

たとえば、特定の列で並べ替えられたエントリを検索する場合は、クエリをすべてのノードに送信する必要があります。これは、コンシステント ハッシュでは「隣接する」アイテムであっても別のノードに配置されるためです。

代わりに、使用パターンに一致するパーティショニングを使用することをお勧めします。同じデータを異なるパーティション/フォーマットのホストにレプリケートすることをお勧めします

于 2021-04-21T12:04:13.670 に答える