問題タブ [consistent-hashing]

google/guava@GitHubでは、 Hashingクラスが一貫性のある hashing@wikiを実装しています。メソッドには次のオブジェクトconsistentHashが必要です。HashCode

Rowプロトタイプの分散キー値ストレージを実装しており、カスタムキーとキーによってキースペースを分割したいと考えていColumnます。

ここで、 class Row(および class Column) は単にStringフィールドのラッパーであり、独自のhashCode()メソッドを持っています。私の質問は、呼び出すためにHashCode@param r と @param c に基づいてa を生成する方法です。locateNodeIndexForHashing#consistentHash

String ユーザー ID が渡されるライブラリがあるため、その String ユーザー ID に基づいて、これら 3 つの色のいずれかのみを選択する必要があります。

たとえば、ユーザーID が文字列である場合は、次に同じユーザー IDが渡された場合12345に選択できるため、同じ RED 色のみを選択する必要があります。String userid が である場合の別の例です。この場合、次に同じユーザー IDが渡された場合に選択できるため、同じ色のみを選択する必要があります。RED1234598765BLUE98765BLUE

アイデアは同じユーザーIDのためのもので、常に同じ色を選択する必要があります。最初に 1 つの色を選択し、次に別の色を選択するのと同じユーザー ID であってはなりません。

同じユーザーIDに対して常に同じ色を選択できるように、ここでユーザーIDに使用できるハッシュ手法は何ですか?

ここの教祖が私を助けてくれることを願っています

ハッシュ アルゴリズムとして SHA1 を使用してコンシステント ハッシュを実装する C/C++ コードを作成しています。

次のようにモジュール操作を実装する必要があります。

0100 0011....0110 100 mod 0010 1001 = ?

除数 ( 0000 1111) が 2 のべき乗である場合、被除数pow(2,n)の最後の n ビットが結果であるため、簡単です。

SHA1 の長さは 160 ビット (または 40 hex ) です。私の質問は、長いビット文字列のモジュロ演算を別の任意のビット文字列に実装するにはどうすればよいですか?

ありがとうございました。

ノードが DHT ネットワークに参加すると、再マッピングを最小限に抑えるために、新しいノードが一貫したハッシュの円の最大間隔を均等に分割することが最適なようです。^{ただし、これは 2 n}ノードに対してのみ最適です( n = 1 で開始すると仮定)。キーが一様にアクセスされる場合、他のすべての番号はホットスポットを作成します。

• n =2, ¹ / ₂ ¹ / ₂ , 最適
• n =3, ¹ / ₄ ¹ / ₄ ¹ / ₂ , ¹ / ₃のノードが¹ / ₂のトラフィックを処理するホットスポット
• n =4, ¹ / ₄ ¹ / ₄ ¹ / ₄ ¹ / ₄ , 最適
• n =5、1 ^/ 8 ₁ ^/ 8 ₁ ^/ 4 ₁ ^/ 4 ₁ ^/ 4 _、 3 ^/ 5_のノードが³ / ₄のトラフィックを処理するホットスポット

より多くの再マッピングを発生させながらホットスポットを最小限に抑えるアプローチは、新しいノードを均等に再配布することです。

• n = ^2、1 / ₂ ^1/2 _ _{_}
• n = ^3、1 / ₃ ^1/3 1/3 _ _{_} ^_ _{_}

以下のような実装では、かなり少数の要素が再マップされ (実際に最小化されているかどうかは不明)、ホットスポットが排除され、基本的な一貫したハッシュ アルゴリズムが維持されます。

そこからの遷移 (数字ではなく文字) は次のとおりです。
[abcdefghij]-> [abcde][fghij]-> [abc][defg][hij]->[ab][cde][fg][hij]

これに対する他の/より良い解決策はありますか (これは解決済みの問題ですか)? 私は一般的にDHTと分散アルゴリズムに比較的慣れていませんが、私が読んだDHT / p2p /分散アルゴリズムでこれに対処していることは見つかりませんでした. 私の特定のシナリオでは、ホットスポットを最小限に抑えることが重要ですが、再マッピングを最小限に抑えることはコストがかかりません。

Akka .NET コンシステント ハッシュ ルーターを少し試してみました。ハッシュに使用するキーを指定することはできますが、アクター間でキーを割り当てる方法を決定するのはルーターのようです。

アクター A がタイプ A のメッセージを受け取り、アクター B がタイプ B のメッセージを受け取る、などのようなことをしたかったのですが、一貫したハッシュ ルーターでこれはまったく可能ですか?

ConsistentHashingRoutingLogicAkka を使用して、同じキーを持つメッセージが同じアクターにルーティングされることを保証しようとしています。同じキーを持つメッセージが FIFO 順で処理されることが重要です。異なるキーを持つメッセージを異なるアクタにルーティングし、自由に並列処理できます。私は分散モードで Akka を使用していません。

メッセージは実際には RabbitMQ ブローカーから読み取られる JSON メッセージであるため、マスター アクターは AMQP メッセージを受信し、ルーティング キーをメッセージ キーとして使用します。同じキーがメッセージ自体にもあります。アクターは Spring アプリケーションの一部です。

私のマスター アクターは次のようになります。

私は最初にマスターを一度取得しています：

次に、次の方法でメッセージを送信します。

しかし、ワーカーのログを印刷するonReceive()と、同じキーに対して異なるディスパッチャ スレッドが使用されていることがわかります。

また、マスター アクターとワーカー アクターに同じディスパッチャー スレッドが使用されることがある理由も明確ではありません。これはスレッド間の非同期メッセージ パッシングではないでしょうか。

ここでわかるように、キー 10420186 を持つワーカー処理メッセージのディスパッチャー スレッドは、9 の場合もあれば 10 の場合もありました。マスター アクターもこれら 2 つのスレッドを使用する場合がありました。

ConsistentHashingRoutingLogicが実際に機能していて、同じスレッドが同じキーでメッセージを処理していることを確認するにはどうすればよいですか? ルーターの初期化で何か間違ったことをしていますか?