Kademlia 算法（二）

1 算法流程

1. 节点 ID (Node ID)

• 结构：通常是一个 160 位或 256 位的随机数。这个长度决定了网络的理论最大规模以及发生 ID 碰撞（两个节点生成相同 ID）的概率（极低）。
• 生成：节点第一次启动时，通常会随机生成自己的 Node ID。这个 ID 在节点的生命周期内保持不变。
• 意义：ID 不仅仅是标识符，它定义了节点在 Kademlia “地址空间”中的位置。

2. XOR 距离度量 (XOR Metric)

• 定义：两个 ID（无论是节点 ID 还是数据 Key）之间的距离是通过它们的**按位异或（XOR）**操作结果来定义的。 distance(ID1, ID2) = ID1 XOR ID2 这个结果被解释为一个无符号整数。数值越小，表示“距离”越近。
• 属性：
  • distance(A, A) = 0
  • distance(A, B) > 0 (如果 A ≠ B)
  • distance(A, B) = distance(B, A) （对称性）
  • distance(A, C) <= distance(A, B) + distance(B, C) （三角不等式） 这些属性使得 XOR 距离成为一个真正的度量空间。
• 优点：
  • 计算简单快速。
  • 能够均匀地分布节点，没有“中心点”。
  • 使得路由非常高效：每次跳转都能保证在“距离”上更接近目标。

3. K-桶 (k-buckets)

• 目的：每个节点维护一个路由表，用来存储它所知道的其他节点的信息（IP 地址、UDP 端口、Node ID）。K-桶是这个路由表的核心结构。
• 结构：路由表被划分为多个列表，称为 k-桶。每个 k-桶对应 ID 空间中的一个特定距离范围。
  • 假设 ID 是 160 位的。可以有 160 个 k-桶。
  • 第 i 个 k-桶（0 <= i < 160）存储与当前节点距离在 [2^i, 2^(i+1)) 范围内的节点信息。
  • 这意味着：
    • 桶 0 包含距离在 [1, 2) 之间的节点（只有一个可能，因为 XOR 距离为 1）。
    • 桶 1 包含距离在 [2, 4) 之间的节点。
    • …
    • 桶 159 包含距离在 [2^159, 2^160) 之间的节点。
• 桶的大小 (k)：每个 k-桶最多只能存储 k 个节点的信息。k 是一个系统参数，通常取 20。
  • 目的：k 提供了冗余。即使桶中的某些节点下线，仍然有其他节点可以联系。k 的选择是在网络开销和系统鲁棒性之间做权衡。
• 更新机制 (重要)：当一个节点（我们称之为 A）收到来自另一个节点（B）的任何消息（请求或响应）时，它会尝试更新与 B 对应的 k-桶：
  1. 计算 A 和 B 之间的距离 d，确定 B 应该属于哪个 k-桶。
  2. 检查 B 是否已在桶中：
     • 如果在：将被观察到的节点 B 移动到该 k-桶列表的末尾（表示它是最新联系过的/最活跃的）。
     • 如果不在：
       • 桶未满（少于 k 个条目）：将 B 的信息（ID, IP, Port）添加到 k-桶列表的末尾。
       • 桶已满（已有 k 个条目）：找到桶中最久未联系的节点（通常是列表头部的节点），我们称之为 C。
         • 节点 A 向 C 发送一个 PING RPC（见下文）。
         • 如果 C 回复了 PONG：说明 C 仍然在线。A 将 C 移动到桶列表的末尾（标记为最新联系过），并丢弃新节点 B 的信息（因为桶满了，且旧节点依然活跃）。
         • 如果 C 没有回复（超时）：说明 C 可能下线了。A 将 C 从 k-桶中移除，然后将新节点 B 的信息添加到列表末尾。
  • 这种机制优先保留稳定、长期在线的节点，因为它们对网络的健康更重要。

4. 远程过程调用 (RPCs)

Kademlia 节点之间通过 UDP 消息进行通信。主要有四种 RPC：

• PING: 用来探测一个节点是否仍然在线。被 PING 的节点如果在线，应回复 PONG。
• STORE(key, value): 请求接收方存储一个 (key, value) 数据对。接收方收到后应将其存储起来。通常数据会有一个过期时间。
• FIND_NODE(target_id): 请求接收方返回其 k-桶中离 target_id 逻辑距离最近的 k 个节点的信息 (ID, IP, Port)。
• FIND_VALUE(key): 与 FIND_NODE 类似，但有一个额外的目的。
  • 如果接收方存储了 key 对应的 value，则直接返回该 value。
  • 如果接收方没有存储该 key，则其行为与 FIND_NODE(key) 完全一样，返回它所知道的离 key 最近的 k 个节点信息。

5. 查找过程 (Lookup)

这是 Kademlia 最核心的操作之一，用于定位节点或数据。

• 目标：找到网络中离目标 ID (可以是节点 ID 或数据 Key) 最近的 k 个节点。
• 过程：
  1. 初始化：查找发起者从自己的 k-桶中挑选出离目标 ID 最近的 α (alpha) 个节点。（α 是一个并发参数，通常取 3）。
  2. 并发查询：向这 α 个节点同时发送 FIND_NODE (或 FIND_VALUE) RPC 请求。
  3. 维护候选列表：发起者维护一个“短名单”，记录目前已知的、离目标 ID 最近的节点，按距离排序。
  4. 迭代：
     • 当收到一个节点的回复时，将其提供的节点信息加入短名单。
     • 从短名单中选出尚未查询过的、距离目标最近的 α 个节点，向它们发送查询请求。
     • 确保任何时候最多只有 α 个查询请求在进行中（outstanding）。
     • 如果一个节点查询超时或失败，则不再考虑它。
  5. 终止：当发起者已经查询过短名单中距离目标最近的 k 个节点，并且它们都已回复（或者超时），或者当 FIND_VALUE 查找直接找到了值时，查找过程结束。
• 结果：对于 FIND_NODE，结果是发起者所能找到的、离目标 ID 最近的 k 个节点。对于 FIND_VALUE，结果可能是数据值本身，或者是最接近数据 Key 的 k 个节点。

6. 数据存储与发布

• 存储：当一个节点想要存储 (Key, Value) 对时，它首先执行 FIND_NODE(Key) 查找，找到离 Key 最近的 k 个节点。然后，它向这 k 个节点发送 STORE(Key, Value) RPC。
• 过期与重新发布 (Republish)：存储在节点上的 (Key, Value) 对通常会有一个过期时间（例如 24 小时）。为了保证数据持久性，最初发布数据的节点必须定期（在数据过期前）重新执行查找和存储过程，向当前离 Key 最近的 k 个节点发送 STORE 命令。
• 缓存/复制 (Replication)：收到 STORE 请求的节点也会缓存数据。有时节点还会主动将自己存储的数据复制给新加入的、距离 Key 更近的邻居节点，以提高数据可用性。

7. 加入网络 (Bootstrap)

• 一个新节点需要知道至少一个已经在网络中的节点（引导节点 Bootstrap Node）的地址。
• 新节点生成自己的 Node ID。
• 向引导节点发送 FIND_NODE(自己的 ID) 请求。
• 通过引导节点的回复，以及后续迭代查找过程，新节点逐渐填充自己的 k-桶，了解网络结构。
• 同时，新节点通过与其他节点的交互，也让网络中的其他节点认识了自己，将自己加入到它们的 k-桶中。

总结关键参数：

• k (桶大小/复制因子)：决定了每个距离范围存储多少联系人以及数据存储的冗余度。典型值为 20。
• α (并发因子)：控制查找过程中并行查询的数量。典型值为 3。
• ID 长度 (如 160 位)。
• 数据过期时间 (如 24 小时) 和 republish 时间间隔。

2 节点Key 与 数据Key

在 Kademlia 中，节点 ID 和数据（更准确地说是数据的 键 Key）都使用相同长度的 ID（例如 160 位或 256 位），并且存在于同一个 ID 空间中，都使用 XOR 来计算距离。这是一个巧妙的设计，因为它允许使用同一套路由算法来查找节点和定位数据存储的位置。

尽管它们在格式和度量空间上

内容相同，但它们在性质、生成方式、网络角色和关联信息上有着本质的不同：

1. 实体性质 (Nature of Entity):

   • 节点 ID (Node ID): 代表网络中一个活跃的参与者。它是一个实际运行 Kademlia 协议的计算机或进程。它是一个“活”的实体，可以发送和接收消息。
   • 数据键 (Data Key / ID): 代表一份被动的数据的标识符。它只是一个名字或标签，指向某个具体的数据值（Value）。它本身不是一个活跃的实体，不能主动通信。

2. 生成方式 (Generation Method):

   • 节点 ID: 通常是节点首次加入网络时随机生成的。目标是让节点 ID 在整个 ID 空间中尽可能均匀分布。
   • 数据键: 通常是通过对数据内容本身进行哈希运算（例如 SHA-1）得到的。这意味着 Key 是由它所代表的数据唯一确定的（内容寻址）。如果你知道数据内容，你就能计算出它的 Key。有时 Key 也可以通过其他方式生成（比如基于公钥），但它总是与数据内容或其来源相关，而不是随机的。

3. 网络角色 (Role in Network):

   • 节点 ID: 定义了节点在 Kademlia ID 空间中的“位置”。它用于路由决策（判断远近、选择下一跳）、填充 K-桶以及标识通信的端点。节点是执行操作（如 FIND_NODE, STORE）的主体。
   • 数据键: 定义了数据在 Kademlia ID 空间中应该被存储的“目标位置”。它是 FIND_NODE 或 FIND_VALUE 查询的目标。网络根据这个 Key 来决定哪些节点（即节点 ID 与该 Key 距离最近的 k 个节点）负责存储与之关联的 Value。Key 是被操作的对象，而不是操作的主体。

4. 关联信息 (Associated Information):

   • 节点 ID: 与一个具体的网络地址（IP 地址和端口号）以及该节点的本地状态（如 K-桶内容）相关联。
   • 数据键: 与一个数据值 (Value) 相关联。这个 (Key, Value) 对才是最终被存储和检索的信息单元。

5. 生命周期/稳定性 (Lifecycle/Stability):

   • 节点 ID: 在节点参与网络的生命周期内通常是稳定不变的。节点可能会上线或下线，但只要它运行，ID 就保持不变。
   • 数据键: Key 本身（如果由内容哈希生成）只要数据内容不变就是固定的。但是，(Key, Value) 对在网络中的存储状态是有生命周期的，需要定期重新发布 (Republish) 以防止过期被清除。Key 的“存在”意义在于是否有人想存储或查找它代表的数据。

总结可以这样理解：

• 节点 ID 回答了“谁在网络里？”以及“这个参与者在网络的哪个逻辑位置？”
• 数据 Key 回答了“我们要找/存的是什么信息？”以及“这个信息应该放在网络的哪个逻辑区域附近？”

将它们放在同一个 ID 空间是 Kademlia 的核心优势之一，因为它简化了设计：寻找一个节点和寻找应该存储某个数据的节点使用了完全相同的查找机制（Lookup Procedure）和距离计算方法。你只需将目标（无论是节点 ID 还是数据 Key）传入查找算法即可。