問題タブ [consistent-hashing]

Python モジュールがデータを redis シャードに書き込み、Java モジュールが redis シャードからデータを読み取るアプリがあるため、Java と Python にまったく同じ一貫したハッシュ アルゴリズムを実装して、データが確実に見つかるようにする必要があります。

私はググっていくつかの実装を試しましたが、Java と Python の実装は常に異なり、一緒に使用することはできません。君の力が必要。

私が試した編集、オンライン実装:
Java: http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html
Python: http://techspot.zzzeek.org/2012/07/07 /the-absolutely-simplest-consistent-hashing-example/
http://amix.dk/blog/post/19367

編集、添付の Java (Google Guava lib を使用) と、私が書いた Python コード。コードは上記の記事に基づいています。

テストコード:

Python コード:

テストコード:

データベース テーブルのルックアップを処理するために、次のコードを数年間使用しています。現在、6 つのホストにわたってテーブルを分割しています。検索コードは次のとおりです。

この「アルゴリズム」には、高速でかなりランダムであるという利点があります。ただし、クラスターに新しいノードを追加するたびに、別のホストに移動する必要がある不要な量のテーブルがあるように見えるため、リバランスにはかなりの時間がかかります。これは大きな問題ではありません。リバランス スクリプトを作成できたので、リバランス中にダウンタイムが発生することはありません。むしろ、それが完了するまで、わずかなパフォーマンスのペナルティがあります。

私の質問は、新しいホストが追加されたときに大量のリバランスを行わずに、この形式の一貫したハッシュを達成する他のアルゴリズムがあるかどうかです。私はこのトピックの調査を続けていますが、Stack Overflow には、本番環境でうまく機能することがわかっている巧妙なソリューションがあると考えていました。

私たちのプロジェクトには、拡張可能な分散 SQL データベースが必要です。各データ レコードは、安全のために複数のデータ サーバー (マスターとスレーブ) に格納する必要があります。

システムがデータ レコードを失うことなくサーバーを動的に追加または削減できることを願っています。コンシステント ハッシュの同じ機能を持つアルゴリズムはありますか?

そのようなクラスがあるとしましょう：

ここで、プロパティがMyClass等しい場合、2 つのインスタンスが等しいとしましょう。したがって、それを表すメソッドとSomeValueを上書きします。を返しますが、同時に次のルールに従う必要があります。Object.Equals()Object.GetHashCode()Object.GetHashCode()SomeValue.GetHashCode()

1. オブジェクトの 2 つのインスタンスが等しい場合、それらは同じハッシュ コードを返す必要があります。
2. ハッシュ コードは、ランタイム全体で変更しないでください。

しかし、どうやらSomeValue変更される可能性があり、以前に取得したハッシュ コードが無効になる可能性があります。

クラスを不変にすることしか考えられませんが、この場合他の人が何をしているのか知りたいです。

そのような場合はどうしますか？そのようなクラスを持つことは、設計上の決定における微妙な問題を表していますか?

最初に2 つの memcached ノード (ノード A、B ) があり、新しいノード Cを追加すると、キーの一部が再マップされ、一貫したハッシュのおかげでそれらの一部のみが再マップされるとします。

元々サーバー A にあったキー「 foo」を持つ値が、現在サーバー C にマップされていると仮定しましょう。

最終的にノード C を削除すると、キーはノード A に再度マップされるはずですが、その時点ではノード A には古いデータしか含まれていません。

では、データをフラッシュすることがこの問題を解決する唯一の方法ですか?

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

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

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

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

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

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

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

I want to have memcached consistant hashing enabled. I've looked at phpinfo(); and I can see the following - last line "memcached.sess_consistent_hash":

Should this be set to one to enable consistant hashing or am I going in the wrong direction with this? I'm using spymemcached. Is there a different way to do this?

thankyou

** Also how do I enable this - I can't find an entry in php.ini

循環ハッシュアルゴリズムは、静的なターゲットのセットが与えられた場合に一貫性を提供します。例えば：

1. 私は最初のターゲットのセットを持っています、それらをと呼びましょうA、BそしてC。
2. 私は鍵を持っています、それを呼びましょうx
3. 循環ハッシュ関数があります。それを呼び出しましょうhash(key, targets)
4. 私が電話するときhash(x, [A,B,C])、x常にハッシュしますA

十分明白なようです。A私が常に与えられるという事実はx、円形ハッシュを使用するときに私が期待する一貫性を表しています。ただし、新しいノードを追加するとどうなるかを考えてみましょうD。

1. 私のターゲットセットは、、、、およびを含むように再調整されAますBCD
2. キーを再適用xしますhash(x, [A,B,C,D])
3. サークルのバランスが崩れているので、もう手に入る保証はありAません

私は何かが足りないのですか、それとも運が悪いのですか？hash(x, [B,A,D,C])ノードの並べ替えを開始した場合（例）、または既存のノードリストの途中に新しいノードを挿入した場合（例） 、問題はさらに悪化しますhash(x, [A,AA,B,C,D])。循環ハッシュのアカデミックな側面を少し調べましたが、このタイプの「スケーリングの一貫性」は、その主要な懸念事項の1つではないようです。たぶん私は間違ったタイプのハッシュアルゴリズムを使用しているだけですか？

のタスクサーバーとして機能しているRedisインスタンスを水平方向にスケールアウトしようとしていますPython-RQ。

私の知る限り、これを行うための最良の方法は、シャーディングロジック（おそらくコンシステントハッシュを使用）をカスタムConnectionPoolおよび/またはConnectionクラスに追加することです。コンシステントハッシュメカニズムにはライブラリを使用したいと思います。これは、おそらく利用可能であるはずであり、自家製のソリューションよりも優れている/バトルテストが行​​われている可能性が高いためです。

このようなことをするのに良いパターンは何でしょうか？調べておくべきライブラリはありますか？私が考慮に入れるべきである私が見逃している何かがありますか？

どうもありがとう！

Memcache の値を Java で設定し、C クライアントから同じ値を取得したいと考えています。

複数の memcache 環境で可能ですか。どちらも同じハッシュ標準を使用していますか?