DHT：Kademlia・Chord・Pastryの内部構造

トップページではDHTの概念を紹介しました。ここでは一歩踏み込み、実際のルーティングテーブルの構造、Kademliaの探索手順、ChordとPastryとの比較、チャーン（ノードの出入り）への対処、実システムでの採用例と攻撃耐性、そして理論値と現実のギャップとしての技術的限界までを解説します。

ルーティングテーブル:「近道表」の設計

DHTの核心は、各ノードが持つ小さなルーティングテーブルです。Chordでは「自分から2^k先を担当するノード」を並べたフィンガーテーブル（m本、mはハッシュのビット数）を持ち、Kademliaでは距離レンジごとにノードを溜めるk-バケットを持ちます。どちらも「遠くは粗く、近くは細かく」知っているのが共通点で、これにより一回のホップで目的地までの距離を半減させられます。テーブルサイズはO(log n)に収まるため、100万ノードでも1ノードが管理する知識はごくわずかです。

Kademliaの場合、160ビットのノードID空間（元論文はSHA-1採用）に対して最大160個のバケットを用意し、バケットiには自分のIDとの距離が2^iから2^(i+1)-1の範囲にあるノードを最大k個（原論文ではk=20）格納します。ノードIDはハッシュ関数で割り当てられるため、ID空間上にノードは一様に分散し、特定の距離帯に密集するわけではありません。バケットを分割するのは、ルーティングの要となる自分の周辺の精度を高めるためで、近いバケットは細かく、遠いバケットは粗いまま保たれます。バケットが満杯のとき新たなノードを検出した場合、Kademliaはバケット内で最も長く更新されていないノードにPingを送り、応答があれば既存ノードを優先して新ノードを破棄し、応答がない場合のみ入れ替えます。この生存確認つきの古参ノード優先の入れ替え（eviction policy）により、「長生きノードほど生き残る」経験則を反映します。

Kademliaの探索手順:XOR距離とα並列探索

Kademliaはノード間の「距離」をIDのXOR（排他的論理和）で定義します。この距離は対称的（AからBとBからAの距離が同じ）で、三角不等式に似た性質を持ち、バケット構造とうまく整合します。キーを探すノードは、自分のバケットから目的キーに最も近いα個（通常3）のノードへ並列に問い合わせ、返ってきた「もっと近いノード」の情報でさらに問い合わせを繰り返します。各ステップで必ず距離が縮むため、O(log n)ステップで収束します。

1. 自分のk-バケットから目的キーに近い順にα個のノードを選び、FIND_NODE（値取得ならFIND_VALUE）を並列送信する。
2. 返答に含まれる「さらに近いノード」候補を、既知の最近傍リストへマージする。
3. 未問い合わせのノードの中から再び最近傍のα個を選び、問い合わせを繰り返す。
4. 直近のラウンドで最近傍k個が更新されなくなった時点で探索を打ち切り、収束とみなす。
5. FIND_VALUEの場合は、途中で値を保持するノードが見つかり次第、その時点で終了する。

nノードのネットワークではホップ数はO(log n)に収まります。100万ノード規模でも、距離空間は各ホップでおおよそ半分に絞り込まれるため、数往復のラウンドで目的のノードへ到達します。αを大きくすると1ラウンドあたりの通信量は増えますが、ノードの無応答（タイムアウト）による遅延の影響を受けにくくなるため、実装ではレイテンシと帯域のトレードオフとしてαの値がチューニングされます。

Chordとの比較:リング構造とXOR距離

DHTのもう一つの代表であるChordは、ノードとキーを単一のリング（0〜2^m-1の円環）上に配置し、キーの担当者を「キー以上で最も近いノード（successor）」と定義します。フィンガーテーブルは自分から2^0, 2^1, ..., 2^(m-1)先を指すため、探索は常にリングを時計回りに縮めていく一方向の逐次ホップになります。Kademliaとの違いを整理すると次の通りです。

Kademliaが実運用で優勢なのは、探索の並列化によるレイテンシ低減に加え、明示的なメンテナンスプロトコル（Chordのstabilize/fix_fingers相当）を必要とせず、通常の問い合わせトラフィックがそのままテーブル鮮度の維持に寄与する設計になっているためです。

Pastry:プレフィックスルーティングと近接性を意識した設計

DHTの研究史でKademlia・Chordと並んでよく引用されるのが、Rowstron & Druschel（2001年、Microsoft Research / Rice University）が提案したPastryです。ChordやKademliaが数値的な「距離」でルーティングするのに対し、Pastryは初期のオーバーレイ研究であるPlaxton木やTapestryの流れを汲み、ノードIDのプレフィックス（先頭からの一致文字列）に基づいてルーティングします。

ノードIDは通常128ビットをb=4ビットずつの16進数字列として扱い、ルーティングテーブルは「行＝共通プレフィックス長」「列＝分岐先の16進数字（0〜f）」の格子状に構成されます。行rのエントリは、自分と最初のr桁が一致し、r+1桁目だけが異なるノードを指します。加えて、ID順で自分に数値的に近いノード群を保持するリーフセット（ChordのSuccessor Listに相当）と、物理的なネットワーク近接性で選んだノード群を保持する近隣セットを併せ持ちます。

ルーティングは単純です。メッセージを受け取ったノードは、自分より1桁以上長く宛先キーとプレフィックスが一致するノードがルーティングテーブルにあればそこへ転送し、なければリーフセットの中で数値的に最も近いノードへ転送します。1ホップごとに一致するプレフィックスが最低1桁ずつ伸びるため、ホップ数はO(log_16 n)であり、ChordやKademliaのO(log_2 n)よりも定数倍小さく収まります。

Pastry最大の特徴は、近接性を意識したルーティングテーブル構築です。同じプレフィックスを持つ候補ノードが複数存在する場合、Pastryは単なるID演算ではなく、実測した往復遅延（RTT）が最も小さいノードをテーブルに採用します。この結果、論理的なホップ数を減らすだけでなく、各ホップが実際のネットワーク上でも近いノードを経由するようになり、原論文では実際の遅延と直接通信した場合の遅延の比（Relative Delay Penalty）をシミュレーション上で小さな定数に抑えられると報告されています。ChordやKademliaの経路選択が基本的にID空間上の演算だけで決まるのとは対照的な設計判断です。

Pastryを土台に構築された研究システムとしては、複製とキャッシュでファイルを保存するPAST（大規模分散ストレージ）、Pastryの経路を逆向きにたどる木構造でトピックベースの配信を行うSCRIBE（Pub/Sub・マルチキャスト）、Webキャッシュとして設計されたSquirrelなどがあります。実装はJavaによるFreePastryが広く参照されました。

重要なのは、PastryがChord・CAN・Tapestryと並んで大学の分散システム講義やDHT関連論文で「定番の比較対象」として今なお頻出する一方、BitTorrentのMainline DHTやIPFS、discv5のような大規模な本番採用例がほぼ存在しない点です。プレフィックスルーティングと近接性認識という設計思想は後続研究に影響を与えましたが、Pastry自体は「研究では広く引用されるが、実運用では普及しなかった」DHTの代表格であり、Kademlia系が歩んだ道とは対照的な結末を辿りました。

チャーンとの闘い:バケットリフレッシュと再公開

P2Pの現実は、ノードが数分〜数時間で頻繁に入れ替わるチャーンとの闘いです。測定研究によれば、ピアの滞在時間分布は裾の重い分布に従い、多数の短命ノードと少数の長寿命ノードが混在します。Kademliaが「長く生きているノードを優先的にバケットに残す」戦略を取るのは、「長く生きたノードはこの先も生き残りやすい」という経験則に基づいています。定期的な値の再公開（republish）やバケットリフレッシュも、チャーンによる知識の腐敗を防ぐ仕組みです。

• バケットリフレッシュ: 元のKademlia論文では、一定時間（1時間程度）問い合わせのなかったバケットに対し、そのバケットの距離範囲内のランダムなIDでlookupを実行し、テーブルを能動的に鮮度維持します。
• 値の再公開（republish）: 保存された値は有効期限（原論文では24時間）を持ち、期限切れ前に保持ノードが再度FIND_NODEで担当ノード群を確認し、値を再配布します。担当ノードの入れ替わりでデータが消失するのを防ぎます。
• k=20という数字の意味: kを大きくするほど1バケットあたりの冗長性が増し、複数ノードの同時離脱にも耐えられますが、その分メンテナンス通信も増えます。BitTorrentのMainline DHT（BEP 5）はk=8と、元論文より小さい値を採用しており、実運用ではネットワーク規模や用途に応じてkをチューニングするのが一般的です。

実システムでの採用例

Kademlia系のDHTは学術的な提案にとどまらず、複数の大規模P2Pシステムの基盤として実運用されています。

同じ「Kademlia」を名乗っていても、ID長・k・αといったパラメータやメッセージフォーマットはシステムごとに異なります。DHTを設計・実装する際は、原論文のデフォルト値をそのまま使うのではなく、想定ノード数・チャーン率・許容レイテンシに応じてパラメータを見直す必要があります。

攻撃耐性:SybilとEclipse、S/Kademliaの対策

公開型のDHTは誰でもノードとして参加できるため、シビル攻撃（1人が大量のノードIDを偽装する攻撃）や、標的ノードの周囲を悪意ノードで固めてしまうEclipse攻撃に構造的に弱いという課題があります。Kademliaのルーティングテーブルは距離に基づく機械的な構造なので、攻撃者は狙ったキーに近いIDを大量に生成できれば、そのキーへの問い合わせ経路を支配できてしまいます。

• S/Kademlia（Baumgart & Mies, 2007）は代表的な対策案で、ノードID自体をハッシュの求解コスト（crypto puzzle）と結び付け、大量のIDを取得するコストを引き上げます。
• 同じくS/Kademliaが提案する互いに素な複数経路探索（disjoint paths lookup）は、単一経路ではなく複数本（d本）の独立した経路で並列に目的地へ近づき、経路上の一部に悪意ノードが混ざっていても多数決的に正しい結果へ収束させます。
• DHTの応答は誰でも観測できるため、探索クエリの送信元IPアドレスからノードの利用実態が推測されるプライバシー上の注意点もあります。

よくある誤解: 「DHTは分散データベースとして任意のデータを保存できる」というものがありますが、実際のKademlia系DHTはキーに対して比較的小さな値（ピア情報やメタデータへのポインタなど）を保存する用途に最適化されています。そのため、大容量データそのものの格納には向きません。また「DHTを使えば匿名になる」という誤解もありますが、DHTのやり取り自体はIPアドレスを露出するため、匿名性の確保には別途NAT越えや攻撃と防御で触れるような追加の設計が必要です。

DHTの技術的限界と実用性:理論値と現実のギャップ

ここまで見てきた設計はいずれも理論的にはO(log n)の美しい保証を持ちますが、実際にDHTを運用・設計する際には、論文のモデルには現れない現実的な制約がいくつも立ちはだかります。

• 探索時間のロングテール: O(log n)ホップという保証は、ルーティングテーブルの中身が常に生きているノードだけで構成されていることを前提とします。実際にはノードは明示的な離脱通知を送らずに突然オフラインになるため、テーブルには一定割合の死んだエントリが残り続けます。これらへの問い合わせはタイムアウトを待ってから次の候補へフォールバックするため、平均ホップ数は理論値に近くても、探索時間の分布には無視できないロングテールが生じます。
• 到達可能性の壁: DHTのプロトコル設計は「どのノードにも直接パケットを送れる」ことを暗黙に仮定しますが、現実のインターネットホストの相当割合はNATやファイアウォールの内側にあり、外部から直接到達できません。BitTorrent Mainline DHTの計測研究では、観測されたノードのうち到達不能な割合が無視できない規模に達することが報告されており、実装の多くはKademliaのノード状態を「good（応答あり）」「questionable（疑わしい）」「bad（応答なし）」に分類し、到達性が確認できたノードだけを他ノードへの紹介対象にするなどの工夫で品質を保っています。
• クエリの表現力の限界: DHTが提供するのは基本的に「キーを指定した完全一致の検索（get）」だけで、範囲検索・全文検索・ソート・結合といったデータベース的な操作はサポートしません。こうした機能を上に載せようとすると、プレフィックスハッシュツリーのような追加構造が必要になったり、結局は中央集権的なインデックスサーバーに頼らざるを得なくなったりします。
• 一貫性保証の弱さ: 多くのDHT実装はトランザクションや線形化可能性を提供しません。チャーンが激しい状況ではput/getが競合し、複製されたレプリカ間で値が一時的に食い違うこともあります。そのためDHTは「小さく、頻繁には変わらず、多少古くても実害が小さいデータ（ピア情報やメタデータへのポインタ）」の格納に向いており、真正な状態を保持する権威的なストアとしては設計されていません。

こうした限界を踏まえ、実運用のシステムはDHTを「唯一の真実の源」としてではなく、発見のための補助的なレイヤーとして使うのが定石です。IPFSはコンテンツそのものではなく「誰がそのコンテンツを持っているか」というプロバイダレコードの発見にDHTを使い、Ethereumのdiscv5はノード発見だけを担当し、実際の合意形成は分散合意の完全に別のプロトコル層に委ねます。DHTは「キーを渡せば担当ノードが分かる」という狭いが確実な問いに対する成熟した回答です。それ以上の役割、つまり調整や一貫性のある状態保持を期待すると、理論と現実のギャップに足元をすくわれることになります。