問題タブ [consistent-hashing]

コンシステント ハッシュに関する情報はネット上にたくさんあり、いくつかの言語での実装が利用可能です。トピックのウィキペディアのエントリは、同じ目標を持つ別のアルゴリズムを参照しています。

ランデブーハッシュ

このアルゴリズムはより単純に見え、不均一な負荷の問題に対処するためにリングの周りにレプリカ/仮想を追加する必要はありません。記事に記載されているように、O(n) で実行されるように見えますが、これは n が大きい場合に問題となりますが、O(log n) で実行するように構成できることを示す論文を参照しています。

この分野の経験を持つ人々への私の質問は、HRW ではなく一貫したハッシュを選択する理由、またはその逆を選択する理由です。これらのソリューションのいずれかがより適切な選択であるユースケースはありますか?

どうもありがとう。

私は終日、PHP を使用して Memcache を理解し、コーディングしようとしましたが、いくつかの点で混乱しています。私は多くの記事を読み、これに関連するほぼすべての SO の質問を調べましたが、正確な答えを見つけることができませんでした。

1) PHP で Consistent Hashed Key を作成するコードは何ですか? どのライブラリをインストールする必要があり、本当に何をする必要があるのか​​? 良い記事はありますか？

2) コンシステント ハッシュ キーを正常に保存したとします。コンシステント ハッシュ キーなどを使用している場合でも、いずれかのサーバーがダウンしているか、新しいサーバーを追加した場合、違いはありますか?

3) Memcached::addServer() の代わりに Memcached::addServers() を使用すると、http://ru.php.net/manual/en/memcached.addserver.php に記載されているように、Consistent Hashing の場合に違いが生じます。そうではなく、どういう意味ですか？

4) コンシステント ハッシュには上記のコードを使用するだけで十分であり、サーバーを追加/削除してもキーに違いはありませんか?

5) ケタマ図書館とは？Memcached::DISTRIBUTION_CONSISTENT がより適切に機能する場合、なぜそれを使用するのでしょうか? http://www.last.fm/user/RJ/journal/2007/04/10/rz_libketama_-_a_consistent_hashing_algo_for_memcache_clientsに従う

6) なんらかの方法でキーをハッシュする必要がありますか、それとも単にキーを提供し、残りは Memcached に処理させる必要がありますか?

できるだけ早く私の実稼働環境を理解して実装するために、あなたの本当のサポートが必要です。あなたの答えは、何をより良くコーディングする必要があるかを理解するのに役立ちます。

コンシステント ハッシュの背後にある理論を説明するいくつかの記事を読みました。しかし、それらのほとんどは、ノードの追加/削除を処理する方法についてあまり詳しく説明していません。memcached のようなキャッシュ レイヤーで使用する場合は何もする必要がないことは理解していますが、分散ストレージで使用する場合は、一部のデータを正しいノードに移動することが非常に重要です。ノードを追加/削除する必要があるとき、正確には何が起こったのですか?

その他の質問は次のとおりです。

1. さまざまなサイズのサーバーに対処する最善の方法は何ですか
2. 一度に複数のマシンを追加および削除する方法
3. レプリケーションと耐障害性に対処する方法

誰かがこれらを説明する記事を教えてくれることを願っています。

多くのマシンにデータを保存するために必要なキーがいくつかあります。Ketama 一貫性のあるハッシュ ライブラリを使用してこれを機能させましたが、キーごとに、そのキーのデータをプライマリとセカンダリの 2​​ 台のマシンに格納したいと考えています。

時計回りではなく反時計回り (たとえば、 ceilingEntryではなくfloorEntry ) でセカンダリ マシンを見つけることは想像できますが、それには、私が作成していないライブラリの変更が必要になります。

libを変更せずにこれを達成する方法はありますか? 1 つのアイデアは、リングの周りでハッシュを 180 "度" 回転させることですが、その方法は不明です。

ボーナス/オプション: 特定のキーの 1 次マシンと 2 次マシンに加えて 3 次マシンを見つける方法は?

http://n00tc0d3r.blogspot.com/のコンシステント ハッシュのアイデアについての記事を読みましたが 、複数のマシンでの方法について混乱しています。

基本的なプロセスは次のとおりです。

入れる

1. 入力された長い URL を単一の整数にハッシュします。
2. リング上のサーバーを見つけて、サーバーにキー longUrl を保存します。
3. ベース変換 (10 ベースから 62 ベースへ) を使用して短縮 URL を計算し、それをユーザーに返します。複数のマシンで短縮 URL を計算する値は何ですか? 自動増加する id はありません。)

取得する

1. ベース変換 (62 ベースから 10 ベースへ) を使用して短縮 URL をキーに戻します。
2. そのキーを含むサーバーを見つけて、longUrl を返します。(そして、キーを含むサーバーをどのように見つけることができますか? )

私は最小限の完全なハッシュ関数を実装しようとしていますが、これを実現するための主な方法の 1 つは、既知のキーの宇宙を取得し、それらを小さなサイズの適切なバケツに分割できるようにすることです (理由の範囲内で小さいほど良い) ）。問題は、これらのバイト配列を配布する方法がわからないことです。キーのセット全体は、アルゴリズムの開始時に使用できます。私にできることの提案はありますか？

ありがとう！

シャーディングには、優れたハッシュ アルゴリズムが必要です。0-2^31 の範囲内で文字列のハッシュ整数値を生成する必要があります。これは可能ですか？

次の回答は、md5 アルゴリズムから整数を生成する方法を提供します。

PostgresSQL で文字列を数値にハッシュする

しかし、範囲内でこの値を生成する方法はありますか?