分散ハッシュテーブル（DHT）の簡単な基本的な説明
https://stackoverflow.com/questions/144360
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
DHTの仕組みについて説明してもらえますか？
重すぎず、基本だけです。
解決
OK、基本的には非常にシンプルなアイデアです。 DHTは辞書のようなインターフェースを提供しますが、ノードはネットワーク全体に分散されます。 DHTのコツは、特定のキーを保存するノードがそのキーをハッシュすることで見つかることです。そのため、実際にはハッシュテーブルバケットはネットワーク内の独立したノードになります。
これにより、多くのフォールトトレランスと信頼性が得られ、パフォーマンスが向上する可能性がありますが、多くの頭痛の種にもなります。たとえば、障害が発生したなどの理由で、ノードがネットワークを離れるとどうなりますか？また、ノードが参加したときにキーがどのように再配布されるので、負荷がほぼ均衡します。考えてみると、どうやってキーを均等に配布しますか？また、ノードが参加するとき、すべてを再ハッシュすることをどのように回避しますか？ （バケットの数を増やす場合は、通常のハッシュテーブルでこれを行う必要があることに注意してください。）
これらの問題のいくつかに取り組むDHTの例の1つは、n個のノードの論理的リングです。各ノードはキースペースの1 / nを担当します。ネットワークにノードを追加すると、リング上の他の2つのノードの間に位置する場所を見つけ、兄弟ノードのキーの一部を担当します。このアプローチの利点は、リング内の他のノードが影響を受けないことです。 2つの兄弟ノードのみがキーを再配布する必要があります。
たとえば、3ノードリングでは、最初のノードにキー0-10、2番目の11-20、3番目の21-30のキーがあります。 4番目のノードが来て、ノード3とノード0の間に自分自身を挿入する場合（それらはリング内にあることを思い出してください）、3のキースペースの半分について責任を取ることができるため、今では26-30を処理し、ノード3は21を処理します-25。
コンテンツベースのルーティングを使用してキーを格納する適切なノードを見つける、このような他の多くのオーバーレイ構造があります。リング内のキーを見つけるには、一度に1ノードずつリングを検索する必要があります（ローカルルックアップテーブルを保持している場合を除き、数千ノードのDHTで問題があります）。これはO（n）ホップルーティングです。他の構造-拡張リングを含む-は、O（log n）ホップルーティングを保証し、O（1）ホップルーティングに対するいくつかの主張は、より多くのメンテナンスを犠牲にします。
ウィキペディアのページを読んで、少し詳しく知りたい場合は、このハーバードのコースページには、非常に包括的な読書リストがあります。
他のヒント
DHTは、通常のハッシュテーブルと同じタイプのインターフェイスをユーザーに提供します（キーで値を検索します）が、データは接続された任意の数のノードに分散されます。ウィキペディアには、基本的な紹介があり、基本的にもっと書きたい場合は逆流します-
一貫性のあるハッシュについての洞察が得られたばかりなので、HenryRの有用な答えに追加したいと思います。通常/単純なハッシュルックアップは2つの変数の関数であり、そのうちの1つはバケットの数です。一貫性のあるハッシュの利点は、式からバケットの数「n」を削除することです。
単純なハッシュでは、最初の変数はテーブルに保存されるオブジェクトのキーです。キーを「x」と呼びます。 2番目の変数は、バケットの数「n」です。そのため、オブジェクトがどのバケット/マシンに保存されているかを判断するには、hash（x）mod（n）を計算する必要があります。したがって、バケットの数を変更すると、ほとんどすべてのオブジェクトが保存されるアドレスも変更されます。
これを一貫したハッシュと比較します。 「R」を定義しましょうハッシュ関数の範囲として。 Rは単なる定数です。一貫したハッシュでは、オブジェクトのアドレスはhash（x）/ Rにあります。ルックアップはもはやバケットの数の関数ではないため、バケットの数を変更したときに再マッピングが少なくなります。
このウィキペディアの記事をご覧ください またはこのパワーポイントスライド
AmazonのDynamoをご覧ください。サークル一貫性ハッシュに基づいたシンプルでありながら斬新なDHT実装について説明しています。
