問題タブ [kademlia]

分散ハッシュ テーブル (DHT) を使用する新しいアプリケーションを作成する場合は、p2p ネットワークをブートストラップする必要があります。既存の DHT (Bittorrent DHT など) に参加できるという考えがありました。

これは実現可能ですか？もちろん、同じ技術を前提としています。Chord と Kademlia を組み合わせることは明らかに不可能です。

はいの場合、これは寄生または共生と見なされますか? なんとなく本来の用途に抵触するという意味の寄生。相互にサポートするため、両方のアプリケーションに適している場合は共生。

私のプロジェクトで DHT を使用したいのですが、Kademlia のサンプルがうまく動作しません。

からの出力ログは次のtwistd -noy examples/server.tacとおりです。

上記のリンクにあるクライアント スクリプトの出力は次のとおりです。

どうしたの？ピアには接続するためのネットワークが必要であることは理解していますが、それはスタンドアロン サーバーが行うべきことではありませんか?

前もって感謝します！

Kademlia の論文、stackowrflow に関するいくつかの質問、およびその他のリソースを読みましたが、まだ p2p を理解していません...

もつれ たカデムリア、学習例、ソースを使用しましたが、まだp2pを理解していません...

誰かが私に言うことができますか、私のPCで絡み合ったまたはkademliaを使用してpythonで簡単なネットワークを作成する方法。たとえばnode、接続時に別の「こんにちは」メッセージを送信します。

私は現在、古典的な論文Kademlia: A Peer-to-peer Information System Based on the XOR Metric を読んで Kademlia ネットワークを学んでいます。その操作の複雑さを理解したいのですが、まだ理解できません。

3 証明のスケッチセクションでは、この論文は 2 つの定義を示しています。

1. ノードの深さ (h) : 160 − i、i は空でないバケットの最小インデックス
2. ノード x におけるノード y のバケットの高さ: x が y を挿入するバケットのインデックスから、x の最下位の空のバケットのインデックスを引いたもの。

そして3つの結論：

1. 圧倒的な確率で、任意のノードの高さは、n 個のノードを持つシステムのlog nの定数内になります。
2. k 番目に近いノードの ID に最も近いノードのバケットの高さは、log kの定数内にある可能性があります。
3. このノードの h個の最上位 k バケットが空でない場合、ルックアップ手順は、各ステップで半分ほど近い (または距離が 1 ビット短い) ノードを見つけ、そのノードをh − log kステップで上げます。 .

だから私の質問は：

1. 「最下位の空のバケット」と「最上位の k バケット」とは何ですか?
2. 深さとバケットの高さを視覚的に説明するにはどうすればよいですか?
3. 2 番目と 3 番目の結論を理解する方法、たとえばlog kとh - log kの理由は?

リソースの検索に関して Kademlia がどのように機能するかを理解しようとしています。セルフノードに最も近いノードツリーを構築する方法、ノード間の距離を見つける方法、プロセスを開始する方法などについて、かなり適切な説明があります。私が理解できないのは、ファイル情報ハッシュがこの図にどのように適合するかです. すべての説明は、どのようにプレイに参加し、分散ハッシュ テーブルの独自の部分を構築するかを教えてくれますが、そうではありません。これは、特定の情報ハッシュを持つファイルであるリソースを実際に見つけるために行っています。このノード ツリーにどのように格納されていますか、それとも別のノード ツリーがありますか? この情報ハッシュを持つノードを見つけて、結果としてファイルを持つのはどのように機能しますか。

ノード ID と情報ハッシュが同じ 20 バイトの長さのコードを持ち、ノード ID の XOR 情報ハッシュがノードとリソースの間の距離であるという事実について簡単に言及されていますが、それがどのように行われ、それがリソースを見つけるのにどのように役立つか想像できません。資源？結局、実際にリソースを持っているノード ID は、リソースまでの最大の XOR 距離を持つことができます。

ありがとう、アレックス

私はすでに、このトピックに関する多くのドキュメントをレビューしましたが、明確でないことがあります。たとえば、ビット トレント ドキュメント ( http://www.bittorrent.org/beps/bep_0005.html ) には次のように記載されています。

ルーティング テーブルは、それぞれがスペースの一部をカバーする「バケット」に分割されます。空のテーブルには、最小 = 0、最大 = 2^160 の ID スペース範囲を持つ 1 つのバケットがあります。ID「N」を持つノードがテーブルに挿入されると、最小 <= N < 最大のバケット内に配置されます。空のテーブルにはバケットが 1 つしかないため、ノードはその中に収まる必要があります。各バケットは、「満杯」になる前に K ノード (現在は 8 つ) しか保持できません。バケットが既知の正常なノードでいっぱいになると、独自のノード ID がバケットの範囲内に収まらない限り、それ以上ノードを追加できません。その場合、バケットは、それぞれが古いバケットの半分の範囲を持つ 2 つの新しいバケットに置き換えられ、古いバケットのノードは 2 つの新しいバケットに分散されます。バケットが 1 つしかない新しいテーブルの場合、

ノードIDのビットプレフィックスに従ってバケットが配置されるkademliaルーティングテーブルに関する他のドキュメントとは少し異なりますが、もう1つ紛らわしいことがあります。「ノードの検索」リクエストに応答するとき、XOR 操作を使用して、リクエストされたノードに最も近い 8 つのノードを見つける必要があります。一部の実装では、XOR 操作を実行するルーティング テーブル内の各アイテムを調べて、最も近い 8 つのアイテムを見つけました。私にもCPUの浪費のようです。

すべてがすでにバケツに入っています。ビット トレント ドキュメント システムによって提案されたものを使用したとしても、バケットを列挙してその最小数と最大数をチェックするだけで、要求されたノード ID を含む可能性のあるバケットをより迅速に見つけることができます。次に、潜在的にそのバケットにクローズノードが含まれている必要がありますが、それらはXORに最も近いノードではなく、値に最も近いノードです(私が理解しているように)。これは多少異なりますが、多少似ています。

0 から 99 までの数字を使用して簡単なテストを実行しました。ここでは、最も近い 8 つの XOR 数字を見つけたいと思っていました。ここで、バケットについて考えてみると、バケット内のすべてのノード ID がマイナーな例外に最も近い可能性があると思います。したがって、たとえば、このバケットを左から 1 つと右から 1 つ取得し、XOR 最も近いノード ID を検索すると、探しているものが見つかります。ルーティングですべてのノードを通過する意味はありません。テーブル。

私は正しいですか、それとも何か不足していますか?

私はさらに別のビットトレント クライアントの実装に取り​​組んでおり、現時点では DHT に苦労しています。この仕様http://www.bittorrent.org/beps/bep_0005.htmlに従って実装されていますが、デバッグを開始すると、ネットワーク上の他のノードの応答が異なることに気付きました。

たとえば、find_node は、ターゲット ノード情報または 8 つの最も近いノードのいずれかを返すことになっています。ほとんどのノードは 34 の最も近いノードで応答し、通常、それら 34 のうち 1 ～ 3 つのノードのみが結果の ping 要求に正常に応答します。

より良い実装の推奨事項を記載した別のドキュメントはありますか? ノードの状態を疑わしい状態に変更するために 15 分間隔を使用することは効率的ではないことが既に証明されている可能性があり、10 または他の数値を使用する必要がありますか? 最新の最適な提案はどこで見つけることができますか?

もう一つ奇妙なことがあります。router.bittorrent.com のようなブートストラップ ノードは、さらに最も近いノードで応答し、通常、「ノード」BDictionary プロパティのバッファー長は 6 で割り切れません (コンパクトなノード情報: IP の場合は 4、ポートの場合は 2)。今のところ、6 で割り切れる最も近い長さでバッファーを切り取るだけですが、それはすべて奇妙です。なぜそれが起こるのか誰か知っていますか？

Kademliaライブラリを使用して P2P ネットワークを作成します。ノードがネットワークに参加したら、ユーザーがコマンドラインでキーを取得したり、ネットワークにタプルを配置したりできるようにしたいと考えています。

私の問題は、I/O が接続をブロックしていることです。これは、ユーザーが入力している間にノードがネットワークから切断されることを意味します。

私のコードは次のとおりです。

この問題に関するいくつかの SO の質問を読みました。ツイストされた例から stdin.py と stdio.py の例を読みましたが、ツイストされたプロトコルで StandardIO を使用する必要があるようです。しかし、Kademlia はプロトコルの使用を簡素化するために高レベルのクラス (サーバー) を使用しており、ライブラリを変更せずにノンブロッキング I/O を取得できるかどうかはわかりません。

編集:私はreactor.callInThreadそのように使用しようとしました:

動作しているように見えますが、ノードが他のノードからの応答を取得できず、それらをバケットから削除してネットワークにタプルを配置できなくなることがあるので、まだ何か間違っていると思います。（私はなんとかバグを再現しました。ユーザー入力に5秒以上かかると発生するようです。kademliaは他のノードからの応答を受信できず、タイムアウトします）