DHT がどのように機能するかについて説明できる人はいますか?
重すぎることはなく、基本的なことだけです。
Gustavo Carreno
質問する
75858 次
4 に答える
252
わかりました、それらは基本的に非常に単純なアイデアです。DHT は辞書のようなインターフェイスを提供しますが、ノードはネットワーク全体に分散されます。DHT の秘訣は、特定のキーを格納するノードがそのキーをハッシュすることで見つかるため、事実上、ハッシュ テーブル バケットがネットワーク内の独立したノードになることです。
これにより、耐障害性と信頼性が大幅に向上し、パフォーマンスが向上する可能性もありますが、多くの頭痛の種にもなります。たとえば、障害などによってノードがネットワークから離脱するとどうなるでしょうか? また、負荷がほぼ均等になるように、ノードが参加するときにどのようにキーを再分配しますか。考えてみれば、どうやって鍵を均等に分配するのですか? また、ノードが参加したときに、すべてを再ハッシュしないようにするにはどうすればよいでしょうか? (バケットの数を増やす場合は、通常のハッシュ テーブルでこれを行う必要があることに注意してください)。
これらの問題のいくつかに取り組む DHT の 1 つの例は、それぞれがキースペースの 1/n を担当する n ノードの論理リングです。ノードをネットワークに追加すると、他の 2 つのノードの間に位置するリング上の場所が見つかり、兄弟ノードのキーの一部を担当します。このアプローチの利点は、リング内の他のノードが影響を受けないことです。2 つの兄弟ノードのみがキーを再配布する必要があります。
たとえば、3 ノード リングでは、最初のノードがキー 0 ～ 10、2 番目のノードが 11 ～ 20、3 番目のノードが 21 ～ 30 を持っているとします。4 番目のノードがノード 3 と 0 の間に挿入された場合 (リング内にあることを思い出してください)、ノード 3 のキースペースの半分を担当できるため、ノード 3 は 26 ～ 30 を処理し、ノード 3 は 21 を処理します。 -25.
このような他の多くのオーバーレイ構造があり、コンテンツベースのルーティングを使用して、キーを格納する適切なノードを見つけます。リング内のキーを見つけるには、一度に 1 つのノードでリングを検索する必要があります (ローカル ルックアップ テーブルを保持しない限り、数千ノードの DHT では問題があります)、これは O(n) ホップ ルーティングです。拡張リングを含むその他の構造は、O(log n) ホップ ルーティングを保証し、O(1) ホップ ルーティングをより多くのメンテナンスを犠牲にして主張するものもあります。
ウィキペディアのページを読んでください。さらに深く知りたい場合は、かなり包括的な参考文献リストがあるハーバード大学のコースページをチェックしてください。
于 2008-09-27T20:59:46.060 に答える
11
DHT は、通常のハッシュテーブル (キーで値を検索) と同じタイプのインターフェイスをユーザーに提供しますが、データは任意の数の接続されたノードに分散されます。ウィキペディアには優れた基本的な紹介がありますが、これ以上書くと本質的に逆流するでしょう -
于 2008-09-27T20:12:16.000 に答える
8
一貫性のあるハッシュについての洞察が得られたので、HenryRの有用な回答に追加したいと思います。通常/ナイーブ ハッシュ ルックアップは、2 つの変数の関数であり、そのうちの 1 つはバケットの数です。コンシステント ハッシュの優れた点は、方程式からバケット数 "n" を削除することです。
単純なハッシュでは、最初の変数はテーブルに格納されるオブジェクトのキーです。キーを「x」と呼びます。2 番目の変数は、バケットの数「n」です。したがって、オブジェクトが格納されているバケット/マシンを特定するには、hash(x) mod(n) を計算する必要があります。したがって、バケットの数を変更すると、ほぼすべてのオブジェクトが保存されるアドレスも変更されます。
これをコンシステント ハッシュと比較してください。ハッシュ関数の範囲として「R」を定義しましょう。R は単なる定数です。コンシステント ハッシュでは、オブジェクトのアドレスは hash(x)/R に配置されます。ルックアップはバケット数の関数ではなくなったため、バケット数を変更したときの再マッピングが少なくなります。
于 2016-04-28T21:45:47.780 に答える