5

コンシステントハッシュ法を使用してノードの追加/削除を比較的安価な手順にする、memcachedで通常使用されるような分散キー/値システムについては話していません。

Pythonのdictやperlのハッシュのような標準のメモリ内ハッシュテーブルについて話しています。

コンシステントハッシュを使用する利点は、ハッシュテーブルのサイズ変更のコストを下げることにより、これらの標準データ構造にも当てはまるように思われます。リアルタイムシステム（およびその他の遅延の影響を受けやすいシステム）は、全体的なスループットがわずかに低下した場合でも、低コストの成長に最適化されたハッシュテーブルの恩恵を受ける/必要とします。

ウィキペディアは「インクリメンタルなサイズ変更」をほのめかしていますが、基本的にはサイズ変更のホット/コールド置換アプローチについて説明しています。安価な再ハッシュを実現するためにバケットルックアップにトライを使用する「拡張可能なハッシュ」に関する別の記事があります。

コンシステントハッシュ法を使用して成長コストを削減する、コア内の単一ノードのハッシュテーブルについて聞いたことがある人がいるかもしれません。または、この要件は、他のアプローチ（上記の2つのウィキペディアビット）を使用してより適切に満たされますか？

または...私の質問全体が間違っていますか？メモリページングの考慮事項により、複雑さはそれだけの価値がありませんか？つまり、コンシステントハッシュの余分な間接参照により、キー全体のごく一部のみを再ハッシュできますが、既存の各ページから読み取る必要がある可能性があるため、おそらくそれは問題ではありません。したがって、メモリレイテンシが主な要因であり、一部またはすべてのキーを再ハッシュすることは、メモリアクセスのコストと比較して重要ではありません。しかし、一方で、コンシステントハッシュを使用すると、すべてのキーの再マップが同じ宛先ページを持つため、次のようになります。キーが既存のページのいずれかに再マップする場合よりも、メモリのスラッシングが少なくなります。

編集：「data-structures」タグを追加し、「バケット」の代わりに「ページ」と言う最後の文を明確にしました。

4

1 に答える 1

4

これについて実際に聞いたことはありませんが、適切な一貫したハッシュの実装を選択するのは良い考えかもしれません。具体的には、Google などによるJump Consistent Hashingです。最初に Jump を使用する理由を説明し、次にローカル データ構造で Jump がどのように役立つかについて説明します。

ジャンプ コンシステント ハッシュ

Jump Consistent Hashing (略して Jump とします) がこの分野に適している理由はいくつかあります。Jump は、ノードが失敗しないことを前提としています。これは、ノードが失敗しないため、ローカル データ構造に最適です。これにより、Jump は単に[0, numBuckets)2 ～ 4 バイトのスペースしか必要としない、一連の数値へのマッピングにすることができます。

さらに、実装は簡単で高速です。また、リファレンス実装の浮動小数点除算を削除して、半分の整数除算に置き換えると、さらに高速になります。（ちなみに、これは可能です。）

これはすべて、次のバリエーションに使用できます...

コンカレントハッシュマップ

しかしまず、Java のConcurrent Hash Mapの概要を説明します。

Java の ConcurrentHashMap は、多数のバケットによってパラメータ化されます。このシャーディング係数は、マップの存続期間を通じて一定です。これらの各バケットは、それ自体が独自のロックを持つハッシュ マップです。

キーと値のペアをマップに挿入すると、キーがバケットの 1 つにハッシュされます。そのキーのロックが取得され、アイテムがバケットのハッシュ マップに挿入されてからロックが解除されます。バケットに挿入している間、x別のスレッドが同時にバケットに挿入できますが、バケットyに挿入する場合はロックを待ちますx。したがって、Java の ConcurrentHashMap には n-way 同時実行性があります。ここで、nはコンストラクターのバケットパラメーターです。

他のハッシュ マップと同様に、ConcurrentHashMap のバケットはいっぱいになる可能性があり、拡大する必要があります。通常のハッシュ マップと同様に、サイズを 2 倍にし、バケット内のすべてを再ハッシュして、より大きな自己に戻します。ただし、「より大きな自己」はバケットの「自己」にすぎません。バケットがホット スポットであり、公正なシェアを超えるキーを取得する場合、バケットは他のバケットと比較して不釣り合いに大きくなります。また、バケットが大きくなるたびに、それ自体に再ハッシュするのに時間がかかります。この最後の点は、ホット スポットの問題だけでなく、単純な古いハッシュ テーブルがより多くのキーを取得する場合にも問題になります。

キーの数が増えるにつれて、バケットの数を増やすことができると想像してください。これにより、個々のバケットの成長量を抑えることができます。

コンシステント ハッシュを入力すると、バケットをさらに追加できます。

ConcurrentHashMap テイク 2: 一貫性のあるハッシュ スタイル

2 つの簡単なステップで ConcurrentHashMap のバケット数を増やすことができます。

最初に、各バケットにマップされる関数をジャンプ コンシステント ハッシュ関数に置き換えます。これまでのところ、すべてが同じように機能するはずです。

バケツがいっぱいになると、2 番目に新しいバケツが分割されます。また、満たされたバケツを育てます。実際には、いっぱいになったバケットが容量の点で最大になる場合にのみ、新しいバケットを分割します。これは、バケットを反復せずに計算できます。

コンシステント ハッシュを使用すると、スプリットはキーを新しいバケットにのみ転送し、古いバケットには逆方向には転送しません。

エンドノート

このスキームには改善があると確信しています。つまり、バケットを分割するには、フル テーブル スキャンを実行してキーを新しいバケットに移動する必要があります。これは確かに通常のハッシュ マップよりも悪くはなく、おそらくそれよりも優れていますが、フル スキャンを実行する必要がない ConcurrentHashMap 実装には不利です。

于 2016-05-11T05:27:32.557 に答える