Kademlia DHT：基本

こんにちは
この記事では、以下で期待するように、現代の構造化されたピアツーピアネットワークの1つについて説明します。この資料には、トピックに関するドキュメント、説明、記事の処理が含まれています。序論として、p2pネットワークの一般的な簡単な理論であるDHTが提示され、その後にのみ、メモが当てられる主要部分が続きます。

1.一般的なp2p理論

ユーザー間のデータ、プロセッサ時間、およびその他のリソースの分配は、さまざまなレベルおよび相互作用でのネットワーキングのソリューションを探すことを余儀なくされています。
クライアントとサーバーの相互作用の代わりに、p2p（ポイントツーポイント）ネットワークは、より高いレベルのスケーラビリティ、自律性、匿名性、および耐障害性を提供します。
以下に一般的な分類を示します。

集中化の程度に応じて、次のタイプのp2pネットワークを区別できます。

一元化
ハイブリッド
完全に分散化

集中管理 -ルーティングと検索に1つ以上のサーバーを使用するネットワーク。悪名高いNapsterは、中央集中型のp2pネットワークの典型的な例です。

このタイプのネットワークの短所：

サーバーはネットワークのボトルネックを表します。失敗すると、システムパフォーマンスが完全に失われます。
サーバー立法の脆弱性
ネットワーク人口が大幅に増加すると、サーバーは一種のDDoS攻撃を受け、障害につながります。

長所：

検索からファイルの受信までの全プロセスは、可能な限り最短のスキーム（サーバーへの検索要求、サーバーからの結果の配信、目的のノードへの接続）に従って実行されます。
さらに、後で示すように、完全一致だけでなく重要な検索も可能です。

ハイブリッド-2種類のノードを含むネットワーク：汎用ノードとスーパーノード（スーパーピア）。後者は特定の条件に応じて動的に割り当てられ、ネットワーク上のデータのルーティングとインデックス作成を制御できます。

短所と長所は、「ハイブリッド」の程度に依存します-どの特性を集中型から継承し、どの特性を分散型から継承します（後で説明します）。

分散型 -このタイプのネットワークは、サーバーの完全な欠如を意味します。これにより、ネットワークのボトルネックが解消されます。

短所：

結果の信頼性を保証しない場合がある特定のルーティングおよび検索アルゴリズムが必要です。
このようなネットワークに含めるには、少なくとも1つのノードの座標を知る必要があります。そのため、ネットワーク参加者の一定量のアドレスデータを含むリストは、公開サイト（サイトなど）で公開する必要があります。接続プロセス自体は、ブートストラップ/ブートストラップステージを意味するため、このようなリストはブートストラップリストとも呼ばれます。

長所：

サーバーの除外により、参加者の数が急速に増加/減少しても、ネットワークはフォールトトレラントになります。
検閲保護の強化

分散ネットワークは、構造化と非構造化に分けることができます。最初のケースでは、ネットワークトポロジは特定のルールに従って構築されます。これにより、正確な一致によってのみクイックデータ検索を整理できます。実際、各ノードは、独自のデータ領域（そのような領域の割り当て方法、外観、ルーティングテーブルの配置-すべてが特定のネットワークトポロジに依存します）を担当します。非構造化ネットワークでは、リクエストを送信できる場所が事前にわからないため、最も単純なバージョンでは、フラッドリクエストのオプションが使用されます。ノードはリクエストを近隣のノード、独自のノードなどに送信します。このような要求に対してTTL（Time To Live）が定義されていることが重要です。これにより、特定の数のネットワークがジャンプした後にそれらを切断できます。明らかに、TTLが低いと、ネットワークは（一部のソースに到達することなく）誤った検索結果を生成し、高い検索結果-要求の時間とトラフィック量が容認できないほど増加する可能性があります。ただし、構造化ネットワークとは異なり、完全に一致するものだけを検索することはできません。これは、ファイル共有システムにとって重要です。構造化されていないネットワークの拡張性は、存在しないとしても、非常に問題があります（TTLの存在とデータの検索時間の増加）。

構造化ネットワークのトポロジとプロトコルを設計する場合、次の関係が最適と見なされます。
-各ノードのルーティングテーブルのサイズ：O（log（n））
-検索の難易度：O（ログ（n））

2. DHT

DHT（分散ハッシュテーブル）-分散ハッシュテーブル。この構造は、分散トポロジによく使用されます。ただし、これが唯一の選択肢ではありません（ただし、文献が示唆しているように、ここでさらに独立した検索を行うことをお勧めします）。
各ノードの各値（データ）に対して、ハッシュが特定のルール（SHA-1を使用するなど）に従って計算され、これがキーになります。また、ノード識別子が計算されます（ハッシュと同じ長さで、多くの場合同じ関数です）。したがって、各ホストには独自の識別子があります。キーはオンラインで公開されます。ノードは、特定のメトリック（距離）でそれに近いテーブルのキーを担当します。ここで、数学の言語を省略した場合、キーは識別子と「類似」していることがわかります。このため、キーと関連情報（値が配置されているノードの座標）を保存するとき、各ノードは独自の責任領域を占有します。これにより、特定の方法で正確な値に従って検索アルゴリズムを整理できます（最初に、ファイル名などの検索用の値キーを計算し、次に、フルパスを提供する仲介者を介してそれを担当するノードに要求を送信することにより、このキーを検索します）。
DHTは、復元力とスケーラビリティを完全に提供します。たとえば、Peer Exchangeと組み合わせて、DHTを使用すると、Torrentトラッカーの機能を傍受できます。

3.カデムリア

メートル法

このトポロジの作成者は、Petar MaymounkovとDavidMazièresです。プロトコルとテーブルの構築は、XORメトリックによるノード間の距離の決定に基づいています。
d（x、y）= x XOR y。距離はXOR演算の結果であり、異なるビットの数ではなく、数値として解釈されることに注意することが重要です（この基準は、キー/識別子スペースでメトリックを生成することもできます）。つまりキー長が4ビットの場合：d（2,5）= 0010 XOR 0101 = 0111 = 7。
XORメトリックは、メトリックのすべての公理を満たします。

d ( x , y ) >= 0 // d ( x , y ) == 0 <=> x == y d ( x , y ) = d ( y , x ) // d ( x , y ) <= d ( x , z ) + d ( z , y ) //
d ( x , y ) >= 0 // d ( x , y ) == 0 <=> x == y d ( x , y ) = d ( y , x ) // d ( x , y ) <= d ( x , z ) + d ( z , y ) //
d ( x , y ) >= 0 // d ( x , y ) == 0 <=> x == y d ( x , y ) = d ( y , x ) // d ( x , y ) <= d ( x , z ) + d ( z , y ) //
d ( x , y ) >= 0 // d ( x , y ) == 0 <=> x == y d ( x , y ) = d ( y , x ) // d ( x , y ) <= d ( x , z ) + d ( z , y ) //

このプロパティは、ルーティングテーブルのサイズと検索の複雑さに関する論文の正式な証明の可能性に関連して記載されています。（公平に、概要として提供）。

ルーティングテーブル

ルーティングテーブルを構築するためのアルゴリズムは、ノード間の距離の計算に基づいています（識別子にメトリックを適用することにより）。
テーブルのi番目の各列は、2 ^（i + 1）から2 ^ iまでの距離にあるノードに関する情報を格納します。したがって、ノード0111の最後の列には、ノード1xxxに関する情報、最後から2番目のノードに関する情報、ノード00xxに関する情報、さらに1レベル近いノード010xに関する情報を含めることができます。

もちろん、実際のネットワークでは、キーの長さは通常128ビットまたは160ビットに適用されます。実装に依存します。

さらに、各レベルの格納ノードの数Kに制限が導入されます。したがって、このようなKに限定されたテーブルの列はKバケットと呼ばれます（残念ながら、ロシアの同等音は完全に不協和音です）。

シートにノードの識別子が含まれているバイナリ検索ツリーを見ると、このようなKバケット構造はランダムではないことが明らかになります：各ノード（110の例のように）は、各サブツリーの少なくとも1つのメンバーの知識を受け取ります（塗りつぶされた楕円でマークされた110について）。したがって、各Kバケットは、レベルiのサブツリーの参加者がK人以下であるノードの接続を反映します。

プロトコル

Kademliaプロトコルには、4種類のメッセージが含まれています。

ping
店舗
FIND_VALUE
FIND_NODE

PINGは 、ネットワーク内の特定のノードの存在を確認するために必要です。たとえば、Kバケットにノードを追加しようとするとき、すでにいっぱいになっているときに使用されます。既存のノードがポーリングされ、応答がない場合、ノードが挿入されます。古いノードがKバケットの下部にあることは注目に値します。これは、ノードがネットワーク上に長く残るほど、離れる可能性が低いことを示唆する実験データに基づいています。したがって、彼らは新しいものの後にのみインタビューされます。

特定のノードに情報を配置できるようにするSTOREリクエスト。 STOREを実行する前に、ノードはパブリッシュするキーに最も近いKを見つけてから、キーとその座標とともに各STOREに送信する必要があります。 K個のノードにすぐにストレージを使用すると、情報の可用性を高めることができます。

FIND_VALUEクエリ。これは反復を形成するために頻繁に繰り返され、 キーごとに値を見つけることができます。ネットワークに値検索を実装します。目的のデータを格納するノードの達成度に応じて、最も近いノードのKまたは値自体を返します。反復は、値が返されたとき（成功）、またはすでにポーリングされたK個のノードが返されたとき（ネットワークに値がないとき）に停止します。

FIND_NODEは、指定された識別子に最も近いKを見つけるために使用されるクエリです（動作はFIND_VALUEに似ており、値を返すことはなく、常にノードを返します！）。たとえば、次のスキームに従ってノードをネットワークに接続する場合に使用されます。
-ブートストラップノードに連絡する
-FINS_NODEリクエストとその識別子をbsノードに送信し、さらに繰り返し送信
-Kバケットを更新します（この場合、新しいノードのKバケットと、渡されたすべての要求が更新されます（ここではXORメトリックの対称性が手元にあります））

ご覧のとおり、仕様のプロトコルは実質的にセキュリティの問題をカバーしていません。これはKademliaベースのネットワークの攻撃に関する研究と取り組みに反映されています。
機能のうち、レプリケーションの存在、値のライフタイム（一定期間後の再割り当ての必要性）、より短い時間で必要なノードに到達するためにFIND_ *要求を送信する際の同時実行（αで示され、通常は3に等しい）を強調する価値があります。要求が渡されるたびに、Kバケットの更新が試行されます。これにより、ルーティングテーブルを可能な限り最適な状態に保つことができます。

4.実装

まず、最も有名なKademliaベースのネットワークは、 aMule / eMuleで利用可能なKadネットワークです。ブートストラップには、eDonkeyの既存のノードが使用されます。
Khashmir -BitTorrentで使用されるKademlia Python実装
現在開発中のアクティブなライブラリのうち、
maidsafe-dht - UDTおよびNAT TraversalをサポートするC ++インフラストラクチャの実装。
Mojito -LimeWireのJavaライブラリ。