Kad Network Searchの仕組み

Mainline DHT bittorrentにはキーワード検索がないという苦情がよくあります。 通常、BitTorrent Inc.フォーラムでこのような検索を追加するリクエスト DHTはキーワードによる検索を許可せず、個々のキーによる検索のみを許可するという従来の回答を無視または受信しました。 原則としてこれは事実ですが、この不幸な状況から抜け出す方法として、各ノードに反転キーワードインデックスを作成する方法があります。



実際、これは、かなり広く使用されているKademliaプロトコルに基づいた分散ハッシュテーブルの実装であるKadネットワークでの検索の仕組みです。 Kad Networkは、eMule、iMule、aMule、MLDonkeyなどのプログラムで使用され、キーワードでファイルハッシュを検索し、ハッシュでファイルソースを検索します。



Kadネットワークでの検索プロセスの一般的な説明。

（理解を深めるために、Kademliaがどのように機能するかを想像すると役立ちます）



そのため、Kad Networkの各ノードには128ビットのIDがあり、ネットワークに入るたびにランダムに生成されます。 MD4に基づくアルゴリズムを使用して、ファイルと単語をハッシュし、すべてのノードのIDと同じスペースにキーハッシュを配布します。 各ノードは、いくつかのタイプの情報を保存する役割を果たします。 まず、各ノードはソースのマップを保存します。 特定のファイルを共有しようとするネットワークメンバーに関する情報。 マップは、キーとしてのファイルのハッシュと値としてのソースのリストです。 ノードソースマップには、ハッシュがノードIDと一致するか、それに近いすべてのファイルのハッシュに関する連絡先情報が含まれます（XORメトリックが使用されます）。 そのため、ファイルのハッシュを取得すると、ファイルのハッシュに近いIDを持つノードを見つけることができ（特定の検索メカニズムはKademliaで使用されているものとほぼ同じです）、ファイルをダウンロードするためのソースのリストを要求できます。 次に、ファイルハッシュがない場合は、キーワードで検索できます。 これを行うには、公開されたファイルの名前をいくつかの連続した単語に分割し、各単語を個別にハッシュします。 これらのキーワードを検索するために、各ノードには2番目のマップがあり、キーとファイルのハッシュおよび値としての名前として、ノード自体のIDに近い単語のハッシュが含まれています。



eMuleでの具体的な検索方法について詳しく説明します。



検索プロセスが開始されると、対応するオブジェクトが作成され、検索マップに入力されます。 各検索クエリには、Kad Networkで検索されるターゲットキー（ファイルハッシュ、ワードハッシュ）があります。 検索は、2つの並列プロセスを使用して実行されます。

最初のプロセスは、目的のオブジェクトのハッシュキーに近いIDを持つノードを検索します。 必要なノードを見つけるために、検索ノードは、検索対象のオブジェクトのキーに最も近いIDを持つ50個のノードをルーティングテーブルから取得し、一時マップに配置します。 次に、検索ノードは、これらの50個のノードへのアクセスを開始して、ノードを目的のオブジェクトのキーに近づけます。 一度に問い合わせられるノードは3つだけです。 検索ノードは、オブジェクトキー（ワードハッシュ、ファイルハッシュ、またはノードID）や要求されたノードの数（つまり、要求されたノードが応答として返す必要があるノードの数）などのパラメーターを含むKADEMLIA_REQメッセージを送信します。 最後のパラメーターは、検索クエリの種類によって異なります。 ノード検索の場合、パラメーターは11です。ソース検索またはワード検索の場合、-2。ノードがそのようなメッセージを受信すると、要求された連絡先（ノード）数のKADEMLIA_RESメッセージで応答します。 検索ノードはこのメッセージを受信すると、受信した連絡先をルーティングテーブルと現在の検索の一時マップに追加します。 次に、検索ノードは、オブジェクトのキーに最も近い3つのノードを再度ポーリングしますが、それらのIDは、連絡先情報を提供したノードのIDよりもキーに近い場合のみです。 この手順は、IDが検索対象のオブジェクトのキーにより近い一時マップに新しいノードが現れるまで繰り返されます。 ノードがKADEMLIA_REQ要求に応答しない場合、それらは削除されます。



2番目のプロセスは、検索対象に応じて、最も近い対応する検索要求から始めて、KADEMLIA_RESメッセージで応答したノードを送信します。 キーワードでソースまたはファイルを検索するにはSEARCH_REQ、ソースまたはキーワードを公開するにはPUBLISH_REQなどを指定できます。 これらの要求は、値0または1をとる追加のフラグを使用して、要求されているものを正確に判断します（キーワードによる名前のソースまたはハッシュ）。 ノードがこのような検索クエリを受信すると、ノードはそれを処理し（キーワードマップまたはソースマップで要求された情報を検索）、選択した結果でSEARCH_RESメッセージで応答する必要があります。 結果のタイプごとに、検索が停止する限界値があります。 ソースを検索したり、キーワードで検索したりする場合、この制限値は300の受信した元のオブジェクトです。 また、検索の開始から45秒が経過すると、ソースまたはファイルの検索が停止します。



有用な記事：

Petar Maymounkov、DavidMazières「Kademlia：XORメトリックに基づくピアツーピア情報システム。」

Kad Networkプロトコルの詳細な説明：

David Mysicka「eMuleのリバースエンジニアリング：eMuleでのKademliaの実装の分析」

Stefan Schmid、Thomas Locher「KADがBitTorrentに出会うとき-より強力なP2Pネットワークの構築」