Kademlia 算法（一）

Kademlia 是一种通过分布式哈希表（DHT）实现的协议算法，专为非集中式对等网络（P2P）而设计。它由 Petar Maymounkov 和 David Mazières 于 2002 年提出。Kademlia 协议包含了对应网络的结构，规定了节点之间通过查询进行信息交换的方式。很多著名的点对点（P2P）系统，比如 BitTorrent 的 DHT 网络、以太坊（Ethereum）等，都使用了 Kademlia 或其变种算法。

Kademlia 的主要特点和概念：

1. 基于 XOR 度量： Kademlia 使用异或（XOR）运算来计算节点之间的距离。对于两个节点 ID x 和 y，它们之间的距离定义为 d(x,y)=x⊕y。XOR 度量具有一些重要的数学性质，例如三角不等式，这使得路由更加高效。XOR 结果被解释为一个整数，数值越小表示距离越近。选择异或是因为通过它计算的距离享有几何距离公式的一些特征，尤其体现在以下几点：节点和它本身之间的异或距离是0；异或距离是对称的：即从A到B的异或距离与从B到A的异或距离是等同的；异或距离符合三角不等式：三个顶点A B C，AC异或距离小于或等于AB异或距离和BC异或距离之和。由于以上的这些属性，在实际的节点距离的度量过程中计算量将大大降低。Kademlia搜索的每一次迭代将距目标至少更近1 bit。一个基本的具有2的n次方个节点的Kademlia网络在最坏的情况下只需花n步就可找到被搜索的节点或值。

2. 节点和密钥的 ID 空间： 网络中的每个节点都被分配一个唯一的 160 位（或更高）的 ID。存储在 DHT 中的每个数据项（键值对）也有一个相应的 160 位密钥。节点 ID 和密钥都位于相同的地址空间中。

3. k-桶（k-buckets）： 每个节点维护一个称为 k-桶的路由表。每个 k-桶对应于节点 ID 空间中的一个距离范围。具体来说，对于节点 ID 的每一位（从 0 到 159），节点维护一个包含最多 k 个其他节点的 ID 和网络地址的 k-桶，这些节点的 ID 与本节点 ID 在该位上不同，而在前面的所有位上相同。k 是一个系统参数，通常设置为 20。k-桶的主要作用是存储与本节点距离在特定范围内的其他活跃节点的信息。

4. 节点查找（Node Lookup）： 当一个节点需要查找具有特定 ID 的另一个节点时，它会首先查询其 k-桶中距离目标 ID 最近的 α 个节点（α 是一个小的并行查询参数，通常为 3）。被查询的节点会返回它们所知道的距离目标 ID 更近的节点。查询节点会继续向新收到的节点发送查询，直到找到目标节点或找到 k 个它所知道的距离最近的节点。

5. 数据存储和检索（Data Storage and Retrieval）：

   • 存储： 当一个节点想要存储一个键值对时，它会找到 k 个距离该键的 ID 最近的节点，并将该键值对存储在这些节点上。
   • 检索： 要检索与某个键关联的值，节点会执行类似于节点查找的过程，找到 k 个距离该键最近的节点，并向它们请求该值。如果存储该值的节点之一在线，它将返回该值。为了提高可靠性，值通常会存储在多个距离最近的节点上。

6. 节点加入（Node Join）： 当一个新节点加入网络时，它需要知道至少一个已在网络中的引导节点。新节点首先联系引导节点，并执行节点查找过程来查找它自己的节点 ID 附近的节点。在此过程中，新节点会填充自己的 k-桶，并且其他节点也会将新节点添加到它们的 k-桶中。

7. 节点离开（Node Departure）： Kademlia 协议对节点的突然离开具有一定的鲁棒性。由于信息被冗余地存储在多个节点上，并且每个节点都维护了多个邻居的信息，即使某些节点离线，网络仍然可以继续运行。节点可以通过定期地 ping 其 k-桶中的其他节点来检测离线的节点，并用新发现的节点替换它们。

Kademlia 的优势：

• 去中心化： 没有中心服务器，网络依赖于所有参与节点的共同努力。
• 容错性： 网络对节点的加入和离开具有较强的适应性。
• 可扩展性： 理论上可以支持大量的节点。
• 高效的查找： 基于 XOR 度量的路由使得查找过程相对高效，平均查找时间复杂度为 O(logN)，其中 N 是网络中节点的数量。

Kademlia 的应用：

Kademlia 算法被广泛应用于各种 P2P 应用中，例如：

• 文件共享网络： 如 eMule 和 BitTorrent 的某些实现。
• 分布式存储系统。
• 分布式域名系统（DNS）。
• 即时通讯系统。

1 算法思想

我们用一个简单的比喻来理解 Kademlia 算法。

想象一下，你要在一个非常非常大的图书馆里找一本书，但是这个图书馆没有中央索引卡片系统，也没有管理员总台。更麻烦的是，书架（或者说，存书的地方）也不是按字母顺序或者主题排列的，而是有点随机。

Kademlia 就像是给这个混乱的图书馆设计的一套找书和放书的规则，让每个图书管理员（我们称之为“节点”或“计算机”）都能高效地找到任何一本书（我们称之为“数据”），或者知道该把新书交给谁保管。

它是怎么做到的呢？

1. 每个管理员和每本书都有一个独特的“身份证号”（ID）：

   • 每个参与网络的计算机（节点）都会得到一个随机但唯一的 ID 号码。
   • 同样，你想存储的每一份数据（比如一个文件）也会根据其内容生成一个唯一的 ID 号码（通常叫做“键 Key”）。
   • 这些 ID 通常是很长的一串数字（比如 160 位或 256 位）。

2. 定义了一种特殊的“距离”：

   • Kademlia 不关心计算机实际的地理位置远近，而是定义了一种基于 ID 号码的“逻辑距离”。
   • 最常用的方法是使用“异或（XOR）”运算来计算两个 ID 之间的距离。你可以简单理解为：两个 ID 号码越相似，它们的“距离”就越“近”。
   • 关键点：这种距离是对称的（A 到 B 的距离等于 B 到 A 的距离），并且有明确的远近关系。

3. 每个管理员（节点）都维护一个“通讯录”（路由表）：

   • 每个节点不会记录网络中所有其他节点的信息，那太多了。
   • 它只记录一部分其他节点的联系方式（IP 地址、端口、ID）。
   • 这个通讯录是精心组织的，按照逻辑距离来分类。它会把联系人分到不同的“桶（k-bucket）”里。
   • 规则是：离自己“近”的节点，它会知道得更详细、更多；离自己“远”的节点，它可能只知道几个代表。就像你很清楚你家邻居是谁，但对于很远城市的人，你可能只认识一两个。

4. 找书（查找数据/节点）的过程：

   • 假设你的节点 A 想找 ID 为 X 的那本书（数据），或者想联系 ID 为 Y 的那个管理员（节点）。
   • 节点 A 先查看自己的通讯录，找出通讯录里记录的、ID 与目标 X 或 Y “逻辑距离”最近的几个节点（比如 K 个）。
   • 节点 A 就去问这几个“距离最近”的节点：“嘿，你知道 ID 为 X/Y 的信息吗？或者你知道谁比你更接近 X/Y 吗？”
   • 被问到的节点也会查看它们自己的通讯录，然后回复给节点 A 一批它们认为更接近目标 ID 的节点列表。
   • 节点 A 收到回复后，更新自己了解到的“更近”的节点名单，然后继续向这个新名单里最接近目标的节点发出询问。
   • 这个过程不断重复，每一次询问都会让你（节点 A）得到离目标 ID 更近的节点信息，就像问路一样，一步步接近目的地。
   • 最终，你要么直接找到了持有数据 X 的节点，要么找到了节点 Y 本身，要么找到了理论上最应该存储数据 X 的那些节点（即使数据暂时不在那里）。

5. 放书（存储数据）的过程：

   • 当一个节点想要存储一份数据（有自己的 Key ID）时，它会先执行上述的“查找”过程，找到网络中那些节点 ID 与这份数据的 Key ID “逻辑距离”最近的一批节点。
   • 然后，它会把这份数据发送给这些“最近”的节点，请求它们帮忙存储。通常会存储多份副本以防某个节点下线。

总结一下：

Kademlia 就是一套让分布式网络中的计算机们，通过给彼此和数据分配独特的 ID，利用一种特殊的“逻辑距离”概念，并维护一个“远疏近密”的通讯录，从而能够像接力问路一样，快速高效地找到网络中任何其他计算机或存储的数据，而不需要一个中央协调者。