乐趣区

关于区块链:死磕以太坊源码分析之Kademlia算法

jiezi

死磕以太坊源码剖析之 Kademlia 算法

KAD 算法概述

Kademlia 是一种点对点分布式哈希表（DHT），它在容易出错的环境中也具备可证实的一致性和性能。应用一种基于异或指标的拓扑构造来路由查问和定位节点，这简化了算法并有助于证实。该拓扑构造有一个特点：每次音讯替换都可能传递或强化无效信息。零碎利用这些信息进行并发的异步查问，能够容忍节点故障，并且故障不会导致用户超时。

KAD 算法要解决的问题

  1. 如何调配存储内容到各个节点，新增 / 删除内容如何解决
  2. 如何找到存储文件的节点 / 地址 / 门路

节点状态

节点的根本属性包含如下：

  • 节点 ID，Node ID
  • 节点 IP 地址与端口号

在 Kad 网络中，所有节点都被当作一颗二叉树的叶子，并且每一个节点的地位都由其 ID 值的最短前缀惟一的确定。

对于任意一个节点，都能够把这颗二叉树合成为一系列间断的，不蕴含本人的子树。最高层的子树，由整颗树不蕴含本人的树的另一半组成；下一层子树由剩下局部不蕴含本人的一半组成；依此类推，直到宰割残缺颗树。图 1 就展现了节点 0011 如何进行子树的划分：

虚线蕴含的局部就是各子树，由上到下各层的前缀别离为 0，01，000，0010。

Kad 协定确保每个节点晓得其各子树的至多一个节点，只有这些子树非空。在这个前提下，每个节点都能够通过 ID 值来找到任何一个节点。这个路由的过程是通过所谓的 XOR（异或）间隔失去的。

图 2 就演示了节点 0011 如何通过间断查问来找到节点 1110 的。节点 0011 通过在逐渐底层的子树间一直学习并查问最佳节点，取得了越来越靠近的节点，最终收敛到指标节点上。

须要阐明的是:只有第一步查问的节点 101，是节点 0011 曾经晓得的，前面各步查问的节点，都是由上一步查问返回的更靠近指标的节点，这是一个递归操作的过程。

节点间隔

Kad 网络中每个节点都有一个 160 bit 的 ID 值作为标志符，Key 也是一个 160 bit 的标志符，每一个退出 Kad 网络的计算机都会在 160 bit 的 key 空间被调配一个节点 ID（node ID）值（能够认为 ID 是随机产生的），<key,value> 对的数据就寄存在 ID 值“最”靠近 key 值的节点上。

判断两个节点 x,y 的间隔远近是基于数学上的异或的二进制运算，d(x,y)=x⊕y，既对应位雷同时后果为 0，不同时后果为 1。例如：

    010101
XOR 110001
----------
    100100

则这两个节点的间隔为 32+4=36。

显然，高位上数值的差别对后果的影响更大。

对于异或操作，有如下一些数学性质：

  • 两个节点间的间隔是随机的
  • 节点与本身的间隔是 0
  • 对称性。A 到 B 的间隔和 B 到 A 的间隔相等
  • 三角不等。distance(A,B)+distance(B,C) <= distance(A,C)

对于任意给定的节点 x 和间隔 Δ≥0，总会存在一个准确的节点 y，使得 d(x,y)=Δ。另外，单向性也确保了对于同一个 key 值的所有查问都会逐渐收敛到同一个门路上，而不论查问的起始节点地位如何。这样，只有沿着查问门路上的节点都缓存这个 <key,value> 对，就能够加重寄存热门 key 值节点的压力，同时也可能放慢查问响应速度。

K 桶

K 桶的概念

Kad 的路由表是通过一些称之为 K 桶的表格结构起来的。

对每一个 0≤i≤160，每个节点都保留有一些和本人间隔范畴在区间 [2^i^,2^i+1^) 内的一些节点信息，这些信息由一些 (IP address,UDP port,Node ID) 数据列表形成（Kad 网络是靠 UDP 协定替换信息的）。每一个这样的列表都称之为一个 K 桶，并且每个 K 桶外部信息寄存地位是依据上次看到的工夫顺序排列，最近（least-recently）看到的放在头部，最初（most-recently）看到的放在尾部。每个桶都有不超过 k 个的数据项。

一个节点的全副 K 桶列表如下图 所示：

当 i 值很小时，K 桶通常是空的（也就是说没有足够多的节点，比方当 i = 0 时，就最多可能只有 1 项）；而当 i 值很大时，其对应 K 桶的项数又很可能会超过 k 个（当然，笼罩间隔范畴越广，存在较多节点的可能性也就越大），这里 k 是为均衡零碎性能和网络负载而设置的一个常数，但必须是偶数，比方 k = 20。在 BitTorrent 的实现中，取值为 k = 8。

因为每个 K 桶笼罩间隔的范畴呈指数关系增长，这就造成了离本人近的节点的信息多，离本人远的节点的信息少，从而能够保障路由查问过程是收敛。因为是用指数形式划分区间，通过证实，对于一个有 N 个节点的 Kad 网络，最多只须要通过 logN 步查问，就能够精确定位到指标节点。

K 桶更新机制

当节点 x 收到一个 PRC 音讯时，发送者 y 的 IP 地址就被用来更新对应的 K 桶，具体步骤如下：

  1. 计算本人和发送者的间隔：d(x,y)=x⊕y，留神：x 和 y 是 ID 值，不是 IP 地址
  2. 通过间隔 d 抉择对应的 K 桶进行更新操作
  3. 如果 y 的 IP 地址曾经存在于这个 K 桶中，则把对应项移到该该 K 桶的尾部

  4. 如果 y 的 IP 地址没有记录在该 K 桶中

    1. 如果该 K 桶的记录项小于 k 个，则间接把 y 的 (IP address, UDP port, Node ID) 信息插入队列尾部

    2. 如果该 K 桶的记录项大于 k 个，则抉择头部的记录项（如果是节点 z）进行 RPC_PING 操作

      1. 如果 z 没有响应，则从 K 桶中移除 z 的信息，并把 y 的信息插入队列尾部
      2. 如果 z 有响应，则把 z 的信息移到队列尾部，同时疏忽 y 的信息

K 桶的更新机制十分高效的实现了一种把 最近看到的节点更新 的策略，除非在线节点始终未从 K 桶中移出过。也就是说在线工夫长的节点具备较高的可能性持续保留在 K 桶列表中。

所以，通过把在线工夫长的节点留在 K 桶里，Kad 就明显增加 K 桶中的节点在下一时间段依然在线的概率，这 对应 Kad 网络的稳定性和缩小网络保护老本（不须要频繁构建节点的路由表）带来很大益处。

这种机制的另一个益处是能在 肯定水平上进攻 DOS 攻打，因为只有当老节点生效后，Kad 才会更新 K 桶的信息，这就防止了通过新节点的退出来泛洪路由信息。

为了避免 K 桶老化，所有在肯定工夫之内无更新操作的 K 桶，都会别离从本人的 K 桶中随机抉择一些节点执行 RPC_PING 操作。

上述这些 K 桶机制使 Kad 弛缓了流量瓶颈（所有节点不会同时进行大量的更新操作），同时也能对节点的生效进行迅速响应。

协定音讯

Kademlia 协定包含四种近程 RPC 操作：PING、STORE、FIND_NODE、FIND_VALUE。

  1. PING 操作的作用是探测一个节点，用以判断其是否依然在线。
  2. STORE 操作的作用是告诉一个节点存储一个 <key,value> 对，以便当前查问须要。
  3. FIND_NODE 操作应用一个 160 bit 的 ID 作为参数。本操作的接受者返回它所晓得的更靠近指标 ID 的 K 个节点的 (IP address, UDP port, Node ID) 信息。

    这些节点的信息能够是从一个独自的 K 桶取得，也能够从多个 K 桶取得（如果最靠近指标 ID 的 K 桶未满）。不论是哪种状况，接受者都将返回 K 个节点的信息给操作发起者。但如果接受者所有 K 桶的节点信息加起来也没有 K 个，则它会返回全副节点的信息给发起者。

  4. FIND_VALUE 操作和 FIND_NODE 操作相似，不同的是它只须要返回一个节点的 (IP address, UDP port, Node ID) 信息。如果本操作的接受者收到同一个 key 的 STORE 操作，则会间接返回存储的 value 值。

    注：在 Kad 网络中，零碎存储的数据以 <key,value> 对模式寄存。依据笔者的剖析，在 BitSpirit 的 DHT 实现中，其 key 值为 torrent 文件的 info_hash 串，其 value 值则和 torrent 文件有密切关系。

为了避免伪造地址，在所有 RPC 操作中，接受者都须要响应一个随机的 160 bit 的 ID 值。另外，为了确信发送者的网络地址，PING 操作还能够附带在接受者的 RPC 回复信息中（在上述 4 种操作中 接受者回复 发送者时，能够携带上 接受者对 发送者的 PING, 以此校验 发送者是否还健在）。

路由查找

Kad 技术的最大特点之一就是可能提供疾速的节点查找机制，并且还能够通过参数进行查找速度的调节。

如果节点 x 要查找 ID 值为 t 的节点，Kad 依照如下递归操作步骤进行路由查找：

  1. 计算到 t 的间隔：d(x,y)=x⊕y
  2. 从 x 的第 [logd] 个 K 桶中取出 α 个节点的信息（“[”“]”是取整符号），同时进行 FIND_NODE 操作。如果这个 K 桶中的信息少于 α 个，则从左近多个桶中抉择间隔最靠近 d 的总共 α 个节点。
  3. 对承受到查问操作的每个节点，如果发现自己就是 t，则答复本人是最靠近 t 的；否则测量本人和 t 的间隔，并从本人对应的 K 桶中抉择 α 个节点的信息给 x。
  4. X 对新承受到的每个节点都再次执行 FIND_NODE 操作，此过程一直反复执行，直到每一个分支都有节点响应本人是最靠近 t 的。
  5. 通过上述查找操作，x 失去了 k 个最靠近 t 的节点信息。

留神：这里用“最靠近”这个说法，是因为 ID 值为 t 的节点不肯定存在网络中，也就是说 t 没有调配给任何一台电脑。

这里 α 也是为系统优化而设立的一个参数，就像 K 一样。在 BitTorrent 实现中，取值为 α=3。

当 α=1 时，查问过程就相似于 Chord 的逐跳查问过程，如图 4。

整个路由查问过程是递归操作的，其过程可用数学公式示意为：

N0=x (即查问操作的发起者)

N1=find ⎯noden0(t)

N2=find ⎯noden1(t)

… …

Nl=find ⎯nodenl−1(t)

这个递归过程始终继续到 Nl=t，或者 Nl 的路由表中没有任何对于 t 的信息，即查问失败。

因为每次查问都能从更靠近 t 的 K 桶中获取信息，这样的机制保障了每一次递归操作都可能至多取得间隔减半（或间隔缩小 1 bit）的成果，从而保障整个查问过程的收敛速度为 O(logN)，这里 N 为网络全副节点的数量。

当节点 x 要查问 <key,value> 对时，和查找节点的操作相似，x 抉择 k 个 ID 值最靠近 key 值的节点，执行 FIND_VALUE 操作，并对每一个返回的新节点反复执行 FIND_VALUE 操作，直到某个节点返回 value 值。

一旦 FIND_VALUE 操作胜利执行，则 <key,value> 对数据会缓存在没有返回 value 值的最靠近的节点上。这样下一次查问雷同的 key 时就会更加疾速的失去后果。通过这样的形式，热门 <key,value> 对数据的缓存范畴就逐渐扩充，使零碎具备极佳的响应速度 (cache 为存活 24 小时，然而指标节点上的内容时 每 1 小时 向其余最近节点从新公布 <key, value> 使得数据的超时工夫得以刷新，而远离指标节点的节点的数据存活工夫当然就可能不会被从新公布到，所以也就是数据缓存的超时工夫和节点的间隔成反比)

数据存储

寄存 <key,value> 对数据的过程为：

  1. 发起者首先定位 k 个 ID 值最靠近 key 的节点
  2. 发起者对这 k 个节点发动 STORE 操作
  3. 执行 STORE 操作的 k 个节点每小时重公布本人所有的 <key,value> 对数据
  4. 为了限度生效信息，所有 <key,value> 对数据在初始公布 24 小时后过期

另外，为了保证数据公布、搜查的一致性，规定在任何时候，当节点 w 发现新节点 u 比 w 上的某些 <key,value> 对数据更靠近，则 w 把这些 <key,value> 对数据复制到 u 上，然而并不会从 w 上删除。

节点的退出和来到

如果节点 u 要想退出 Kad 网络，它必须要和一个曾经在 Kad 网络的节点，比方 w，取得联系。

u 首先把 w 插入本人适当的 K 桶中，而后对本人的节点 ID 执行一次 FIND_NODE 操作 (向 w 公布 查找 u 的 FIND_NODE 申请)，而后依据接管到的信息更新本人的 K 桶内容。通过对本人邻近节点由近及远的逐渐查问，u 实现了依然是空的 K 桶信息的构建，同时也把本人的信息公布到其余节点的 K 桶中。

节点 u 为例，其路由表的生成过程为：

  1. 最后，u 的路由表为一个单个的 K 桶，笼罩了整个 160 bit ID 空间，如图 6 最下面的路由表；

  2. 当学习到新的节点信息后，则 u 会尝试把新节点的信息，依据其前缀值插入到对应的 K 桶中：

    1. 如果该 K 桶没有满，则新节点直接插入到这个 K 桶中；

    2. 如果该 K 桶曾经满了，

      1. 如果该 K 桶覆盖范围蕴含了节点 u 的 ID，则把该 K 桶决裂为两个大小雷同的新 K 桶，并对原 K 桶内的节点信息依照新的 K 桶前缀值进行重新分配
      2. 如果该 K 桶覆盖范围没有包节点 u 的 ID，则间接抛弃该新节点信息
  3. 上述过程一直反复，最终会造成表 1 构造的路由表。达到间隔近的节点的信息多，距离远的节点的信息少的后果，保障了路由查问过程能疾速收敛。

在图 7 中，演示了当覆盖范围蕴含本人 ID 值的 K 桶是如何逐渐决裂的。

当 K 桶 010 满了之后，因为其覆盖范围蕴含了节点 0100 的 ID，故该 K 桶决裂为两个新的 K 桶：0101 和 0100，原 K 桶 010 的信息会依据其其前缀值从新散布到这两个新的 K 桶中。留神，这里并没有应用 160 bit 的 ID 值表示法，只是为了不便原理的演示，理论 Kad 网络中的 ID 值都是 160 bit 的。

节点来到 Kad 网络不须要公布任何信息，Kademlia 协定的指标之一就是可能弹性工作在任意节点随时生效的状况下。为此，Kad 要求每个节点必须周期性【个别是：每小时】的公布全副本人寄存的 <key,value> 对数据，并把这些数据缓存在本人的 k 个最近街坊处，这样寄存在失效节点的数据会很快被更新到其余新节点上。所以有节点来到了，那么就来到了，而且节点中的 k - 桶刷新机制也能保障会把曾经不在线的节点信息从本人本地 k - 桶中移除

退出移动版