Kademlia: A Peer to Peer Information System Based on the Xor Metric (2002)
September 13, 2025peer-to-peerのファイル共有アプリケーション BitTorrentの分散ハッシュテーブルMainline DHTはKademliaをもとに実装されている。 Kademilaのノードやキーには160ビットのIDが割り当てられ、2つのIDの排他的論理和を両者の距離とみなす。 ノードは、ノード内に保存されたIDに近い宛先に再帰的にRPCを送り、IDを検索する。
ノードと通信するための宛先は、IPアドレス、UDPポート、ノードのIDの3つの情報から成り立つ。 宛先はノード内の160個の\(k\)-bucketに保存される。 \(i\)番目の\(k\)-bucketには距離が\([2^i, 2^{i+1})\)内の宛先を保存する。 \(k\)はバケットに保存するノードの最大数を示す。 バケットにある宛先は最後に参照された時刻の昇順に並ぶ。 リクエストやレスポンスを受信したノードは、添付されたIDを\(k\)-bucketに追加できるか確認する。 \(k\)-bucket内の宛先が\(k\)未満か、先頭の宛先から応答がなければ対向ノードの情報を\(k\)-bucketに追加する。 応答のない先頭の宛先は削除される。 先頭の宛先が応答すれば、先頭の宛先を最後尾に移動し、新しいIDを保存せずに破棄する。
PING, STORE, FIND_NODE, FIND_VALUEの4つのRPCがある。
PINGでノードがオンラインか確認できる。
STOREはキーバリューのペアを宛先のノードに保存する。
FIND_NODEはIDを引数にとり、送信先に最大\(k\)個のIDに最近傍の宛先を問い合わせる。
FIND_VALUEは受信したノードに目的のバリューがあればバリューを返し、なければFIND_NODEと同様に最大\(k\)個の宛先を返す。
IDで指定したノードを探すときはFIND_NODEを再帰的に呼出す。
はじめに、ノードは\(\alpha\)個のIDに最近傍のノードにFIND_NODEを並列に送る。
さらに、応答で得られた宛先のうち、\(\alpha\)個の最近傍かつ未送信の宛先にFIND_NODEを送る。
新たにFIND_NODEを送る未送信の宛先を得らなければ、未送信かつ最近傍の\(k\)個のノードにFIND_NODEを送る。
それでも、送信済みの宛先しか得られなければ再帰的探索を終了する。
再帰的探索はオンラインの宛先を\(k\)-bucketに維持するために使われる。 1時間以上再帰的探索のなかった\(k\)-bucketがあれば、\(k\)-bucketの範囲のIDを無作為に選び、そのIDの再帰的探索で\(k\)-bucketを更新する。
Kademliaに参加するノードも再帰的探索で\(k\)-bucketを充填する。 参加するノードは1つ以上の宛先を知らないといけない。 参加するノードは宛先を\(k\)-bucketに追加し、自身のノードのIDを再帰的探索し、\(k\)-bucketを更新すると同時に宛先に自身を登録させる。
バリューを探すときは、FIND_NODEのかわりにFIND_VALUEを呼出す。
キーバリューを保存する処理は、この再帰的探索をもとに実装されている。
ノードは、キーバリューを、再帰的探索で見つけた\(k\)個の最近傍のノードにキーを保存する。
24時間おきに探索の大本のノードはキーバリューを再配信する。
キーバリューは複製して保存されることもある。 ノードが新しい宛先を見つけたとき、ノード内のキーバリューのうち、ノードよりも宛先に近いキーのキーバリューを宛先に複製する。 ノードにあるキーバリューの保存期間は、キーと最近傍のノードとノードの間にあるノード数を指数とする関数で設定する。 キーから遠いキーバリューほど保存期間が短い。