# kademlia协议

By [Untitled](https://paragraph.com/@0x88e0a809bc3064d28317b564ecc1cb7d08fa1e79) · 2021-11-24

---

Kademlia协议（以下简称Kad)，是一种分布式哈希表（DHT，Distributed Hash Table）技术，不过和其他DHT实现技术比较，如Chord、CAN、Pastry等，Kad通过独特的以异或算法（XOR）为距离度量基础，建立了一种全新的DHT拓扑结构，相比于其他算法，大大提高了路由查询速度。

在Kademlia网络中，所有信息均以的哈希表条目形式加 以存储，这些条目被分散地存储在各个节点上，从而以全网方式构成一张巨大的分布式哈希表。我们可以形象地把这张哈希大表看成是一本字典：只要知道了信息索 引的key，我们便可以通过Kademlia协议来查询其所对应的value信息，而不管这个value信息究竟是存储在哪一个节点之上。在eMule、 BitTorrent等P2P文件交换系统中，Kademlia主要充当了文件信息检索协议这一关键角色，但Kad网络的应用并不仅限于文件交换。

节点     每个用户都有一个ID号, ID长度根据不同网络而定，例如以太坊中是512bit，eMule是128bit。在系统设计上的好处是——对分布式系统所依赖的物理网络的解耦。 ID是在你第一次使用Kad时随机生成的. 出现两个相同ID的概率实在太小了, 这几乎不可能发生. 我们可以认为, 在Kad网络里, 没有两个用户具有相同的ID号。

节点ID不仅可以用来做身份标识，还可以用来进行值定位(值通常是文件的散列或者关键词)，节点ID与文件散列直接对应，它所表示的那个节点存储着哪儿能够获取文件和资源的相关信息

很多 DHT 的设计会让“node ID”采用跟“data key”同构的哈希值。这么搞的好处是：1、当散列值空间足够大的时候，随机碰撞忽略不计，因此也就确保了 node ID 的唯一性。2、可以简化系统设计——比如简化路由算法，采用这种风格来设计路由机制，好处是：key 本身已经提供了足够多的路由信息。

距离     在Kad网络中，两个节点之间距离并不是依靠物理距离、路由器跳数来衡量的，事实上，Kad网络将任意两个节点之间的距离d定义为其二者ID值的逐比特二进制和数，即异或。假定两个节点的ID分别为a与b，则有：d=a XOR b。在Kad中，每一个节点都可以根据这一距离概念来判断其他节点距离自己的“远近”，当d值大时，节点间距离较远，而当d值小时，则两个节点相距很近。 这里的“远近”和“距离”都只是一种逻辑上的度量描述而已；

举个例子：     01010000与01010010距离（即是2个ID的异或值）为00000010（换算为十进制即为2）；     01000000与00000001距离为01000001（换算为十进制即为26+1，即65）；如此类推。

异或计算距离的特点，1、节点和它本身之间的异或距离是0。2、异或距离是对称的：即从A到B的异或距离与从B到A的异或距离是等同的。3、异或距离符合三角形不等式：给定三个顶点A B C，假如AC之间的异或距离最大,那么AC之间的异或距离必小于或等于AB异或距离和BC异或距离之和.4、对于给定的一个距离，距离A只存在有唯一的一个节点B，也即单向性，在查找路径上也是单向的，这个和地理距离不同。

---

*Originally published on [Untitled](https://paragraph.com/@0x88e0a809bc3064d28317b564ecc1cb7d08fa1e79/kademlia)*