Clever Geek Handbook

Kademlia（DHT）-実用ガイド

Kademliaとして知られる実装の例でDHTについて説明します。 DHTは分散ハッシュテーブルとして変換され、分散型の情報交換ネットワークを構築することを目的としています。 上記のすべては、Androidプラットフォーム用のED2KネットワークのクライアントおよびLinux上のデーモンの形で機能します。 以下の実装の詳細。



資源



各ホストには独自の識別子があります。 さらに、DHTのリソースは、キーワードであろうとファイルであろうと、識別子も持っています。 識別子として、ハッシュ関数の値が使用されます-トレントではSHA1、ED2KではMD4です。 違いは長さのみです-160ビット対128。したがって、ネットワーク上で何かを公開または検索するには、目的のリソースのハッシュが必要です。



Kademliaでは、ED2Kネットワークで使用されるハッシュがファイルの公開に使用されますが、いくつかの予約があります。 ファイルハッシュ自体が単にバイトのシーケンスとしてシリアル化される場合、KAD識別子は4つの32ビットワードのシーケンスとしてシリアル化されます。 これは、Cademliaの機能です。



バイトを回転させる必要があります。 



/** * save/load as 4 32 bits digits in little endian save as 4 32 bits digits network byte order * rotate bytes in each 4 byte portion * */ @Override public ByteBuffer get(ByteBuffer src) throws JED2KException { for (short i = 0; i < value.length; ++i) { byte b = src.get(); value[(i / 4)*4 + 3 - (i % 4)] = b; } return src; } @Override public ByteBuffer put(ByteBuffer dst) throws JED2KException { for (short i = 0; i < value.length; ++i) { dst.put(value[(i / 4) * 4 + 3 - (i % 4)]); } return dst; }


ED2Kネットワークでのシリアル化
歴史的に、1バイト以上を占有するすべてのプリミティブは、ターゲットプラットフォームと同じ順序、つまりLITTLE ENDIAN（シニアアドレスの古い部分）でシリアル化されます。 これは、eDonkey / eMuleクライアントが元々Windowsプラットフォームと対応するアーキテクチャ専用に開発されたという事実が原因だと思います。 例外は、バイトシーケンスとしてシリアル化可能なMD4ハッシュでした。 IPアドレスは32ビットの符号なし整数LITTLE ENDIANに保存され、パケットにも書き込まれます。 カデリアのサポートは後で追加され、おそらく他の人によって追加されました。 何らかの理由で、これらの人々は、ネットワークバイトオーダーを適用することを決定しました。これはおそらく、TCP / IPネットワークの標準である（または考慮される）ためです。 さらに、彼らは新しいバイトオーダーをIPアドレスにのみ適用しました-KADパケットに書き込むとき、それはビッグエンディアンに変換され、他はすべてそのままです。 新しいKadIdプリミティブは、ハッシュとしてではなく、4つの32ビット数の配列として追加されました。そのため、KAD識別子を読み書きするときは、いくつかの変換を行う必要があります。



キーワードを公開するために、ファイル名は単語に分割され、各単語はハッシュされます。 受信したハッシュは公開されます。 ハッシュは、バイトオーダービッグエンディアン-最下位アドレス（先頭）の上位バイトまたは単なるバイト配列の大きい整数として表すことができます。



DHTの機能は、ハッシュ間の距離を計算する機能に基づいています。これにより、距離を縮めて目標に一貫して近づくことができます。 HASH_SIZEは128です。



ただxor： 



 // returns the distance between the two nodes // using the kademlia XOR-metric public static KadId distance(final KadId n1, final KadId n2) { assert n1 != null; assert n2 != null; KadId ret = new KadId(); for(int i = 0; i < MD4.HASH_SIZE; ++i) { ret.set(i, (byte)(n1.at(i) ^ n2.at(i))); } return ret; }


あるターゲットハッシュに対する2つのハッシュのコンパレータ。 通常、ターゲットハッシュはホスト自身のハッシュです。 



 // returns -1 if: distance(n1, ref) < distance(n2, ref) // returns 1 if: distance(n1, ref) > distance(n2, ref) // returns 0 if: distance(n1, ref) == distance(n2, ref) public static int compareRef(final KadId n1, final KadId n2, final KadId ref) { for (int i = 0; i != MD4.HASH_SIZE; ++i) { int lhs = (n1.at(i) ^ ref.at(i)) & 0xFF; int rhs = (n2.at(i) ^ ref.at(i)) & 0xFF; if (lhs < rhs) return -1; if (lhs > rhs) return 1; } return 0; }


いわば、Kバケツで最も走行距離を決定する機能です。 



 // returns n in: 2^n <= distance(n1, n2) < 2^(n+1) // useful for finding out which bucket a node belongs to public static int distanceExp(final KadId n1, final KadId n2) { int bt = MD4.HASH_SIZE - 1; for (int i = 0; i != MD4.HASH_SIZE; ++i, --bt) { assert bt >= 0; int t = (n1.at(i) ^ n2.at(i)) & 0xFF; if (t == 0) continue; assert t > 0; // we have found the first non-zero byte // return the bit-number of the first bit // that differs int bit = bt * 8; for (int b = 7; b >= 0; --b) if (t >= (1 << b)) return bit + b; return bit; } return 0; }


ネットワーク接続



まず、クライアントはその識別子を生成します。 これはランダムなMD4ハッシュ（トレントの場合はSHA1）です。 ハッシュの生成中にデータの一部をアドレス、ポート、および同様の操作と混合して、チャンスを増やすことができます。



一目で理解できない瞬間の1つは、自分に割り当てたノードのハッシュと、提供するリソースの接続方法です。 答えはありません。 ハッシュのランダムな選択は、ネットワーク上のクライアントがハッシュに近いリソースを担当することを意味します-他のクライアントが公開と検索のために彼に来ます。 クライアントは、自分自身がソースであることを示して、リソースを他のサイトにも公開します。



DHTと分散ネットワークですが、それに接続するには、ネットワークに接続されている少なくとも1つのノードを知っている必要があります。 そのようなノードのアドレスを知っているクライアントは、特別なブートストラップ要求を送信し、応答としてノードのリストを受信します。 その後、これらのノードなどにブートストラップを送信できます。 ED2K形式のノードのセットを含むファイルをダウンロードできるサイトもあります。



ルーティングテーブル



特にルーティングテーブルは、ハッシュに最も近いノードを選択するように設計されています。 テーブルにはKバケットが含まれています。 Kバケットは、実際にはホストを記述する構造を持つコンテナにすぎません。 通常、テーブルはhereのようにツリー形式で示されます 。



ルーティングテーブル自体は、識別子までの距離の降順でソートされたKバケットのリストで簡単に表すことができます。



最初は、テーブルにはKバケットが含まれていません。ノードを追加するプロセスで追加されます。



テーブルに、作成済みのKバケットの数-N（numBuckets）などのパラメーターが含まれているようにします。 Kバケット番号は、前述のdistanceExp関数を128-1-distanceExpとして使用して計算されます。ハッシュに近いノードは、リストの末尾近くに配置されます。



N-2未満の各Kバケット位置には、ハッシュからの距離がnであるノードが含まれる場合があります。 数がN-1（極値）のKバケットには、距離がnのノードだけでなく、より近くにあるすべてのノード、つまり他のすべてのノードも含まれます。 nの値の範囲は[0..127]です。 これは、検索関数K-bucketのコード（以下）でより明確に見えます。



ノードを追加するためのアルゴリズム



  1. 新しいノードのKバケット番号を探しています。 これをコードで説明する方が簡単です。 



     public int findBucket(final KadId id) { int numBuckets = buckets.size(); if (numBuckets == 0) { buckets.add(new RoutingTable.RoutingTableBucket()); ++numBuckets; } int bucketIndex = Math.min(KadId.TOTAL_BITS - 1 - KadId.distanceExp(self, id), numBuckets - 1); assert (bucketIndex < buckets.size()); assert (bucketIndex >= 0); return bucketIndex; }


  2. Kバケットに空き領域がある場合-ノードを追加します
  3. Kバケットに空き領域がない場合、最後の更新、未応答のリクエスト数などのノードのメトリックを使用して、それをクリアしようとします。 場所が表示される場合-ノードが追加されます
  4. すべての試行後、Kバケットに空き領域がない場合は、Kバケットを分離してみてください。 パーティションに失敗しました-ノードは無視されました


Kバケット分割



Kバケットは、極端なコンテナであり、これが最後のKバケットではない場合にのみ分割できます。 理論的には、MD4の合計Kバケットは128になりますが、ノードのハッシュに一致するハッシュは処理されないため、最後の花束は使用できません。 原理は単純です-距離がnに等しいノードは現在のコンテナに残り、他のすべては新しいコンテナに移動します。 したがって、分割後、テーブルは1 Kバケツずつ大きくなります。



ルーティングテーブルはKバケットシートです。 K-bucketは、DHTネットワークのノードを記述する構造のリストです。 実装は任意です。たとえば、これらすべてをデータベーステーブルに入れることができます。 テーブルは圧縮されません-コンテナが完全に空になる前に特定のKバケットのノードが消えると、テーブルに残ります。 ノードは、たとえばしばらく使用できない場合に削除できます。



テーブル更新



ここで詳細に検討することはありません-更新は、ルーティングテーブルを最新の状態に保つために設計された内部プロセスです。 時々、更新が必要なKバケットが選択され、このKバケットに属するが既存のハッシュと一致しないランダムハッシュが生成され、検索プロセスが開始されます。 更新を開始する条件-たとえば、最後の更新は15分以上前でした。



公開と検索



公開と検索は、最後に見つかったサイトでの公開または検索リクエストの実行と同じプロセスです。 その本質は、識別子が目的のリソースの識別子に近い連続した反復によってノードにアプローチすることです。 ネットワークの論理に従って、これらのノードには、ハッシュがハッシュに近いキーワードとファイルに関する情報が含まれます。



  1. 最も近いノードの最初の50（またはいくつ）がテーブルから抽出され、調査リストが作成されます。
  2. Kad2Reqリクエストが送信されるか、リクエストされたノードよりもさらに近いノードのリクエストが送信されます。 ノードはルーティングテーブルを調べ、要求されたハッシュに近いノードからの応答を形成します。
  3. 回答は投票に戻され、すべてが再び始まります
  4. ターゲットに十分近い場所にあるノードは、目的のリソースの可用性を求めてポーリングされるか、パブリケーションが実行されます。 トレランスゾーンなどがあります-直接検索または公開を開始するためにハッシュがどれだけ異なる可能性があるか
  5. ポイント2は、制限条件に達するまで繰り返されます-十分なノードが検出され、すべてがインタビューされます。


ポイント4は、メインプロセスと並行して起動できる独立したプロセスです。 ただし、提示された実装では、メインプロセスの最後に個別に開始されます。



キーワードとソースの公開の構造
これ以上苦労することなく、キーワードとソースを保存するためのテーブル構造を提供します。 この構造は、別のホスト上のアグリゲーターで使用されます。 



 create table kad.sources ( kad_id character(32) not null , host inet not null , port_tcp int not null default 0 , port_udp int not null default 0 , packet bytea not null , last_update timestamp not null default current_timestamp , total_updates int not null default 0 , source_type int not null , constraint sources_pk primary key (kad_id, host, port_tcp, port_udp) ); create table kad.keywords ( kad_id character(32) , file_id character(32) , host inet not null , packet bytea not null , last_update timestamp not null default current_timestamp , total_updates int not null default 0 , constraint keywords_pk primary key(kad_id, file_id, host) );


ソースが1対1のファイルハッシュ用に公開されていることがわかります。 キーワードは、1対多と呼ばれる名前の関連ファイルハッシュと共に公開されます。 テーブルは使いやすさのために非正規化されています-ソース/キーワードのマスターとして何らかの種類のキーテーブルを持つことができます。



おわりに



アーキテクチャーについて一言。 DHTサポートは、専用のスレッドで実行される非同期UDPサーバーである別のトラッカーに実装されます。 クライアントアプリケーションとは別に起動できるため、テストに便利です。 実際、このトラッカーは別のマシンでデーモンとして機能します。 ネットワークへの要求は、RPCマネージャーを介したRPC呼び出しで編成されます。これにより、応答を待機する時間を制限する問題を解決し、応答しないノードをマークすることができます。



論理的に送信される要求は、マネージャー（アルゴリズム）で結合されます。 リクエストごとにオブザーバーが作成されます。 さて、これらはすべて、RPCマネージャーで説明したように開始されます。 詳細については、リンクのコードを参照してください。



Kademliaの機能は、複数のプロセスが同時に実行されている場合、ホストが送信した要求に対する答えを常に正確に決定し、同時に同じノードに複数の要求を送信することが常に可能ではないことです。 たとえば、ノードの検索プロセスは交差する可能性があり、ここではいくつかのトリックに頼らなければなりません。



トレントでは、より有能なトランザクションサポート-リクエストを送信するときに、クライアントは特別なtransaction_idブロックを送信します。 これにより、トランザクションを正確に識別できるだけでなく、ネットワークを少し保護できます。



Kademliaのこの機能のサポートに気付いていなかったため、ノート（ノート）の発行と検索を検討しませんでした。



何も混乱せずに資料を提示できたと思います。



参照資料





More articles:


All Articles