4

Kademliaルーティングテーブルは160個のバケットで構成されていることを理解しています。

ノードは、プレフィックス長（ローカルノードキーとノードのXORの先頭の未設定ビットの数）に応じて、バケット0〜159に配置されます。

なぜそうなのですか（160 * 20ノードを反復処理して最も近いノードを見つけることが不可能であるという事実以外に）パフォーマンス上の利点はありますか？

4

3 に答える 3

4

Kademliaは、2つのノードIDのXORを距離の尺度として使用します。ルーティングテーブルバケットの考え方は、ノードがそのノードに「近い」ネットワークについての詳細な知識を持ち、IDから遠くなるほど知識が少なくなるということです。

特定のキーに最も近いノードのグループを見つけるために、ノードは最初に、自身のルーティングテーブルから知っている最も近いノードを照会します。平均して、これらのルックアップの半分はバケット0でカバーされるアドレス空間に分類されます。ただし、そのバケットには20個のノードしか含めることができないため、これらのノードが実際に最も近い可能性はほとんどありません。ただし、そのバケット内の各ノードは、アドレススペースのその部分に関するより詳細な知識を持ち、独自のルーティングテーブルから、クエリを実行できる近いノードのより適切なリストを提供できる可能性があります。

このようにして、反復ルックアップは実際に最も近いノードのグループに非常に迅速に焦点を合わせます。

あなたが言う時

160 * 20ノードを反復処理して、最も近いノードを見つけることは不可能です。

私はあなたがそれらのそれぞれを実際に照会することは実行不可能であることを意味すると思います。このようなリストを繰り返し処理して最も近いリストを抽出するのは、まさにルックアップ要求（RPC）がノードによって処理される方法だからです。

実際のシナリオでは、バケットの数が160に近づく可能性は非常に低いことに注意してください。たとえば、10億ノードのネットワークの場合、平均バケット数は27になります。

元のKademliaの論文で選択された実際の値については、バケットサイズが20と指定されている理由はわかりません。ただし、160はSHA1ハッシュのビットサイズから派生していると思います。通常、ハッシュ関数は、格納される特定の値のキーを生成するために使用されます。SHA1を使用したハッシュ衝突のリスクが許容できるほど低い場合、これは問題ありません。そうでない場合は、別のハッシュアルゴリズムを使用できます。たとえば、SHA256は最大256個のバケットを生成します。

于 2012-06-30T11:54:12.263 に答える
3

なぜそうなのですか、パフォーマンス上のメリットはありますか？

この組織をXORメトリックと組み合わせると、階層化されたローカリティが作成され、ターゲットにいくらか近いノードをクエリすると、さらに近いノードが認識されることが保証されます。これは指数関数的な収束をもたらします。

多分あなたはそれを分散区間検索と考えることができます。

Kademliaルーティングテーブルは160個のバケットで構成されていることを理解しています。

（最大）160バケットのフラット配列は、多くの実装が正しいルーティングテーブルレイアウトを概算するために使用する基本的な方法です。

バケット分割またはマルチホームルーティングテーブルでは、160を超えるバケットを含む可能性のある実際のツリーレイアウトが必要です。

実際、これは89のノードIDを持つマルチホームDHTノードのツリーベースのルーティングテーブルのごく一部です。完全なテーブルはそれよりも大きくなります（これらは基本的に89のIDのうちの2つの領域です）。

0000000...   entries:8 replacements:8
0000001000...   entries:8 replacements:8
0000001001000...   entries:8 replacements:8
00000010010010...   entries:8 replacements:8
00000010010011000...   entries:8 replacements:8
000000100100110010...   entries:8 replacements:8
0000001001001100110...   entries:8 replacements:8
00000010010011001110...   entries:8 replacements:8
0000001001001100111100...   entries:5 replacements:0
0000001001001100111101...   entries:8 replacements:0
000000100100110011111...   entries:8 replacements:0
0000001001001101...   entries:8 replacements:8
000000100100111...   entries:8 replacements:8
000000100101...   entries:8 replacements:8
00000010011...   entries:8 replacements:8
000000101...   entries:8 replacements:8
00000011...   entries:8 replacements:8
0000010...   entries:8 replacements:8
0000011000...   entries:8 replacements:8
0000011001000...   entries:8 replacements:8
00000110010010...   entries:8 replacements:8
00000110010011000...   entries:8 replacements:8
000001100100110010...   entries:8 replacements:8
0000011001001100110...   entries:8 replacements:8
00000110010011001110...   entries:8 replacements:5
0000011001001100111100...   entries:6 replacements:0
0000011001001100111101...   entries:2 replacements:0
000001100100110011111...   entries:8 replacements:0
0000011001001101...   entries:8 replacements:8
000001100100111...   entries:8 replacements:8
000001100101...   entries:8 replacements:8
00000110011...   entries:8 replacements:8
000001101...   entries:8 replacements:8
00000111...   entries:8 replacements:8

そのルックアップキャッシュはさらに大きく、7kバケットで構成されています。

于 2012-07-07T00:25:24.193 に答える
0

このアルゴリズムは、2001年頃にP2Pファイル共有サービスを作成するために作成されました。これをコンテキストに入れるために、各P2Pノードがmp3ファイルを保存して提供すると想像してください。ルーティングテーブルには、これらのファイルのハッシュが含まれています。

当時のストレージハードウェアでは、各ノードにすべてのファイルを保存することはできませんでした。アイデアは、各P2Pユーザーがこのmp3データベースの一部を自分のPCに保存するというものでした。最大160*20 =3200mp3ファイルは約15Gbかかります。合理的だと感じました。

公正な方法でデータを配布する方法が必要です。Logdistance（プレフィックス長に基づく）はその1つです。「さらに」ハッシュがあるファイルは、より頻繁に衝突します。対応するバケットはすぐにいっぱいになり、どのファイルがそこに入るのかはよりランダムになります。「より近い」ハッシュを持つファイルは、ピアとしてのあなたがより長く保存する責任があるファイルになります。これらのファイルの数は少なく、バケットの充填が遅くなります。

160 * 20ノードを反復処理して最も近いノードを見つけることは不可能であるという事実を除いて、

現在、3200の距離を比較することは大したことではありませんが、そうです、バケットは、複製のために「最も近い」距離を見つけるのに役立ちます。

于 2022-02-15T13:23:16.230 に答える