問題タブ [consistent-hashing]

整数 1,2,3...n としてユーザー ID によって分割されるユーザー テーブルがあるとします。テーブルの分割に使用されるコンシステント ハッシュの方法を使用できますか?

利点は、パーティションの数が増減した場合、古いインデックスが同じになる可能性があることです。

質問A.

コンシステント ハッシュ アルゴリズムを使用してパーティション テーブルを作成するのは良い考えですか?

質問B。

これがサポートされているリレーショナルデータベースはありますか?

一部のnosqlデータベースはすでにそれを使用していると思います。

ただし、ここでのデータベースはリレーショナル データベースを指します。

インタビューでこの質問に遭遇しました。最初の反応では、長さで mod と答えただけですが、テーブルをより多くの部分に分割すると、問題が発生する可能性があります。

プロジェクトのヴォルデモートのデザインページ：

http://project-voldemort.com/design.php

ハッシュリングは区間[0、2^31-1]をカバーすると述べられています。

ここで、間隔[0、2^31-1]は2^31の総数を表し、最大数の2 ^ 31-1はすべて1に設定された31ビットです（これを納得させるために、2 ^3-を検討してください）。 1. 2 ^ 3=8で0x1000です。2^3-1= 7で0x111です）。

したがって、通常の32ビットアドレスワードを使用して値を格納する場合、1ビットの空き容量があります。

では、なぜ2 ^ 31-1が上限なのですか？その余分なビットは、ある種のシステム簿記に使用されていますか？

（たとえば、1ビット余分に1ビット追加すると、オーバーフローすることなく2つの有効なハッシュアドレスを安全に追加するためのスペースが提供されます）。

そして最後に、この選択はヴォルデモートに固有のものですか、それとも他のコンシステントハッシュスキームで見られますか？

基本的には、次のアルゴリズムを実装し、これらのアルゴリズムを使用して構築されたシステムがさまざまな条件下でどのように動作するかを分析したいと考えています。

• ゴシッププロトコル
• 複数のパクソ
• コンシステント ハッシュ

ここでの私の関心は、これらのアルゴリズムにあります。私は基本的に、これらのアルゴリズムをすばやく記述し、これらのアルゴリズムを深く理解できるプログラミング言語を探しています。

どの言語を選択すればよいですか? Java、Scala、Erlang など。

現在、私は Java と C++ を知っています。

サーバー間でオブジェクトを配布するためにhash_ringパッケージを使用しています。MD5ハッシュに基づいているため、分布は均一になると思います。残念ながらそうではありません。

を使用して生成されたランダムキーを使用していuuid.uuid4()ます。私は、MD5自体が実際に均一な分布を与えることを確認しました。ただし、を使用して配布してhash_ring.HashRingいる場合、ほとんどのバケットと最も少ないバケットの間で20〜30％の違いがあります。

• hash_ringいくつかの設定を微調整することで、分布の均一性を改善できますか？
• Pythonでコンシステントハッシュを行うための他の良い選択肢はありますか？

分布の均一性をテストするために使用したコード：

印刷されたもの：

比較のために、MD5を使用してコンシステントハッシュを直接実行しました。

はるかに良い結果が得られます：

ワークロードが複数のノードに分散される分散システムでは、複数のリクエストが同時に同じデータを操作する競合状態に対処する 2 つの方法は、コンシステント ハッシュと分散ロックを使用することです。コンシステント ハッシュにより、1 セットのデータを操作するすべてのリクエストが同じワーカーに送信され、分散ロックにより、一度に 1 つのワーカーだけが任意のデータ セットを操作できることが保証されます。

私の質問は、どちらのアプローチの長所と短所、そしてどちらが有利であるかということです。

確かに、コンシステント ハッシュは、分散キャッシュ アプリケーションで広く使用されているテクノロジです。これは、ノード数が動的に変化する場合に優れたソリューションを提供します。また、仮想ノードを組み合わせると、負荷分散の問題も解決されます。

この手法の欠点や制限はありますか?

ありがとう！

私はConsistent Hashingのようなものを探していますが、配布が可能な限り公平になることを保証します(ランダムキーの平均だけではありません)-そのようなものはありますか?もしそうならどこで見つけることができますか?

編集：私の特定のケースでは、キーのセットは事前にわかっています（そして「小さい」）。これらのキーは常に存在し、任意の時点でそれぞれ正確に 1 つのノードに割り当てる必要があります。

重複の可能性:
python-memcache はコンシステント ハッシュを使用しますか?

python-memcached はコンシステント ハッシュをサポートしていますか? これに関するスレッドをいくつか見つけましたが、それらのほとんどは 2 年以上前のものです。

乾杯

MongoDB には十分に文書化されたシャーディング機能があります。

私が必要としているのは、(デプロイと構成の両方が) シンプルで高速な一貫したハッシュ タイプのデータ分散 (Dynamo、Cassandra、Voldemort など) だけです。MongoDB でそれを達成する方法はありますか?

私が書いているJavaコードで一貫したハッシュアルゴリズムを使用することを検討しています。guava Hashing ライブラリにはconsistentHash(HashCode, int)メソッドがありますが、ドキュメントはかなり不足しています。私の最初の希望はconsistentHash()、単純なセッション アフィニティを使用して、一連のバックエンド サーバー間で負荷を効率的に分散できることでした。

この方法の使用方法の実例はありますか? 特に、ターゲット範囲からのバケットの削除の管理に関心があります。

例えば：

出力につながります：

私が望むのは、リストの前のサーバーを削除した後、その識別子 (「someId」) を同じサーバーにマップすることです。上記のサンプルでは、​​削除後、バケット 0 を「server1」に、バケット 1 を「server3」に、バケット 2 を「server4」に、バケット 3 を「server5」にマッピングしたいと思います。

バケットの削除と追加を管理するために、別の (リストよりも複雑な) データ構造を維持する必要がありますか? おそらく、特定のバケットを追加および削除した後の再マッピングを管理する、より複雑なハッシュ API を想定していたと思います。

注:サンプル コードが小さな入力とバケット セットを使用していることはわかっています。100 個のバケットにわたる数千の入力でこれを試しましたが、結果は同じです。バケット 0 ～ 98にマップされる入力は、 を 99 に変更しても同じままで、bucketsバケット 99 が残りの 99 バケットに分散されます。