Kademlia

概述

Kademlia 由 Petar Maymounkov 与 David Mazières 于 2002 年提出，是应用最广的分布式哈希表（DHT）协议，以异或（XOR）作为节点间距离度量，结构对称、查找可并行，对高流失率的公网环境适应性强。

原理

每个节点持有 160 位 ID，与键的距离定义为两者 ID 的异或值。路由表由 k-bucket 组成，每个桶保存与自己某一距离区间内的至多 k 个节点，优先保留在线时间长的节点（经验上老节点更稳定）。查找时向距目标最近的 α 个节点并发询问，迭代逼近，复杂度 O(log N)；所有正常通信都顺带刷新路由表，无需专门维护流程。

应用

BitTorrent 的无 tracker 下载（Mainline DHT）、以太坊的节点发现协议、IPFS 的内容路由均基于 Kademlia 或其变体。