案例库 · 软件与 IT · 技术决策 · 2002
Kademlia通过XOR距离使任何节点在少数几跳内可达
Maymounkov和Mazières在2002年提出的Kademlia将节点ID的XOR视为距离，因此节点可以在O(log n)跳内找到任何对等节点，并传播发现的节点。
纽约大学
那一手
去中心化的对等网络没有索引来查找谁持有某个文件。泛洪网络成本太高；中央追踪器则违背了初衷。
2002年的Kademlia将距离定义为160位ID的按位异或。由于XOR是其自身的逆运算且对称，节点的路由表根据前导位差异的位数将其他ID分桶，每一桶保留约一个联系。
要找到一个对等节点，节点查询距离目标最近已知节点，每次回复都会带来一个更近的节点，因此搜索距离每轮减半——大约需log n跳。系统具有自愈性，因为节点在回答时学习和传播信息。
为什么管用
- XOR距离是对称的，节点在每个位级别上都靠近某个联系。
- 路由表保持很小，但可达性是全局的，因此没有节点认识所有人。
- 每一跳将距离减半，使得在无目录的情况下实现O(log n)搜索。
- 查找和插入使节点学习到其他节点，因此网络能自我修复。
值了多少将XOR称为距离；每个节点都靠近某个人聪明
可以搬走什么
在没有目录的网络中，选择一个度量标准，让每个节点在每个距离桶中保持一个联系。每个节点通过最接近的已知邻居到达任何其他节点，而不需要全局列表。
后来呢
Kademlia成为BitTorrent DHT、以太坊以及许多文件共享网络的查找协议。它是大型对等系统中无协调器路由的标准答案。
资料来源
发现哪里写错了？告诉我们。