[解決済み] 分散ハッシュテーブル(DHT)の簡単な基本説明

質問

DHTがどのように機能するのか、どなたか説明してください。

あまり重いものはなく、基本的なことです。

解き方は？

OK、基本的にはとてもシンプルなアイデアです。DHTは、辞書のようなインターフェースを提供しますが、ノードはネットワーク上に分散されています。DHT のトリックは、特定のキーを格納するノードを、そのキーをハッシュ化することで見つけることです。したがって、実質的に、ハッシュ テーブルのバケットは、ネットワーク内の独立したノードになります。

これにより、耐障害性と信頼性が向上し、パフォーマンスも向上する可能性がありますが、同時に多くの問題も発生します。例えば、あるノードが故障などでネットワークから離れたらどうするのか？また、ノードがネットワークに参加したときにキーを再分配し、負荷がほぼ均等になるようにするにはどうしたらよいでしょうか。考えてみれば、どうやってキーを均等に分配するのだろう？また、ノードが参加したときに、どうやってすべてを再ハッシュしないようにするか？(バケット数を増やせば、通常のハッシュテーブルでもそうする必要があることを思い出してください）。

これらの問題のいくつかに取り組むDHTの一例は、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(log n)ホップルーティングを保証し、より多くのメンテナンスの代償としてO(1)ホップルーティングを主張するものもあります。

wikipediaのページを読んで、本当に少し深く知りたい場合は、こちらをご覧ください。 コースページ ハーバード大学では、かなり包括的なリーディングリストがあります。