hash - 複数のマシンでの一貫したハッシュ

Question

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

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

入れる

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

取得する

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

Answer 1

そのページには、著者がどのように意図したかについての明確な答えはありません。これは基本的に読者のための演習だと思います。ここにいくつかのアイデアがあります：

1. ハッシュテーブルスタイルの衝突解決を使用して、説明どおりに実装します。つまり、URL を作成するときに、それが既に何かに一致している場合は、何らかの方法でそれを処理します。再ハッシュまたは算術変換 (たとえば、1 を加算) の両方が可能です。これは単純に、利用可能なキーを見つけようとしてサーバーに n 回アクセスしなければならないという理論上の最悪のケースを意味します。

その基本的なアイデアを取り入れてスマートにする方法はたくさんあります。たとえば、サーバー上にあるキーが見つかるまで繰り返し再ハッシュするなど、同じサーバー上で利用可能な別のキーを検索するだけです。

2. サーバーが互いに通信し、自動インクリメント ID で調整できるようにします。

3. これはおそらく優れた解決策ではありませんが、状況によってはうまく機能する可能性があります。たとえば、最初の 16 ビットでサーバーを選択するなど、各サーバー (またはサーバーのセット) に個別の名前空間を与えます。作成時にランダムに1つ選択します。次に、その名前空間をどのようにマップするかを理解する必要があります。名前空間は、誰がどの ID を作成できるかについてのみ重要なので、後でノードを追加したり、バランスを取り直したりする場合は、大したことではありません。

さらに詳しく知りたい場合はお知らせください。この方法なら色々あると思います。著者がこの点について詳しく述べていないのは厄介です。この種のアルゴリズムに関する私の経験では、衝突の解決や同様の問題が、分散システムの実際の実装の中心にある傾向があります。