优点
Kad 和其它 DHT 相比拥有一些独有的优点:
-
节点得知其它节点只需发送最少量的消息
-
查询 key 时会自动传播自己的信息(基于异或的距离计算,具有对称性)
-
节点有足够的知识和灵活性去通过低延迟路径进行路由查询
-
使用异步、并行的查询,避免某些节点失败而导致查询超时
-
能抵抗基本的拒绝服务攻击
基本构造
和其它 DHT 类似,节点有一个 ID,这里假定是 160 位。对于想查询的 ID,能找到与之最近的节点,查询仅需对数级别的步数。Kad 的节点是一个二叉树的叶子节点,二叉树左右两条边划分 0 和 1 时,每个叶子节点就形成了自己的 ID。对于任一个节点,整棵二叉树能分割成一系列不包含自身节点的下级子树。最大的下级子树是不包含自身节点的半边二叉树,然后剩下的半边二叉树继续分割下级子树。Kad 的关键在于,对于每个节点而对它而言划分的所有下级子树,如果任意一个下级子树不为空,那这个节点最起码知道其中一个节点的信息。
节点之间的距离通过对 ID 进行异或来计算,虽然这种计算方式算出来的不是欧几里得距离,但也具有一些基本的性质。定义 \(d\lparen x, y \rparen = x \oplus y\),则有:
-
\(d \lparen x,x \rparen = 0\)
-
if \(x != y\), then \(d \lparen x,y \rparen > 0\),满足
-
\(\forall x,y\),有 \(d \lparen x,y \rparen = d\lparen y,x \rparen \)
-
\(d\lparen x,y \rparen + d\lparen y,z \rparen \geq d\lparen x,z \rparen \),因为 \(d\lparen x,y \rparen \oplus d\lparen d,z \rparen = d\lparen x,z \rparen \) 而 \(\forall a \geq 0, b \geq 0, a+b \geq a \oplus b\)
和 Chord 中的在顺时针的环中度量距离一样, Kad 的异或也是单方向的。对于任意节点 x 和距离 \(\Delta > 0\),在 ID 空间里面必然存在 y,有 \(d\lparen x,y \rparen = \Delta\)。单方向能确保对于同一个 key 的查询会收敛到相同的路径,而不管查询的来源点是哪个。这样对于热点 key 的查询是可以缓存的。另外和 Chord 不同的一点是,异或是对称的。
在上面的这个二叉树拓扑上,跟某个 ID 为 x 的节点最近的叶子节点的 ID,一定和 x 拥有最长的公共前缀,如果二叉树中某个分支为空,那可能不止一个节点有最长的公共前缀。
K 桶
对于每个 i,\(0 \leq i < 160\),用 (ip, port, ID) 三元组数组来保存 ID 是 \(2^i \sim 2^{i+1}\) 这个区间的节点信息,这种三元组数组就是 K 桶,数组的长度为参数 k(一般为 20)。ID 的位数是多少,就需要多少个 K 桶,在这里也就是每个节点里面需要保存 160 个 K 桶。当 i 较小时, \(2^i \sim 2^{i+1}\) 范围也很小,这时这个 K 桶可能为空,因为可能根本就不存在这种 ID 的节点;i 较大时,ID 区间很大了,位于这个区间的节点也会更多,轻而易举就能超过 k 个,但是在这个 K 桶里面也只需保存 k 个即可,而且必须要在数据里面维护节点的活跃程度,最后得知活跃情况的节点信息要放在数组的末尾。
节点收到任何消息时都要检查是否能够更新 K 桶,假如得知某个节点 a 发来消息,按如下规则更新:
首先根据 a 的 ID 计算它应该要位于哪个 K 桶。
-
如果 a 已经保存在这个 K 桶里面,则将它移到数据末尾,表示它是最近活跃的节点
-
如果原来未保存
-
如果 K 桶未满 k 个,则直接将 a 添加到末尾
-
如果 K 桶已满,则 Ping K 桶中保存在最前面的节点
-
若没有响应,则去掉它,把 a 添加到末尾
-
若有响应,则 a 被抛弃暂不保存,并且把这个响应的节点添加到末尾
-
这种规则其实蕴含着无标度网络的特性:在线时间越长的节点,它继续在线的概率也越大;第二这其实能够一定程度抵抗 DoS 攻击,新节点如果是恶意的,它想被加入到其它节点的 K 桶里面,要等到老节点下线。
RPC 协议
Kad 协议中只定义了 4 个 RPC。节点每次发送消息时都要带上自己的 ID,好让接收者得知自己的存在。如果为了响应和请求对应,每个消息也可带上一个魔数。每个响应都需要带上自身 ID,防止节点伪造地址。
- Ping
参数:from_id。响应:自身 ID。用来探测某个节点是否还在线。
- Store
参数:from_id, (key, value)。响应:自身 ID。让某个节点保存键值对,注意这个节点的 ID 不一定和 key 相等,它只是在调用者眼里,这个键值对应该由这个节点保存。
- FindNode
参数:from_id, target_id,响应:自身 ID,k 个自己已知的离 target_id 最近的 (ip, port, ID) 三元组,可以来自单个 K 桶,也可以多个,如果总共已知的都不够 k 个,那就有几个就响应几个。
- FindValue
参数:from_id,target_id,响应:自身 ID,k 个自己已知的离 target_id 最近的三元组或者目标 value。
这几个 RPC 的核心都是一样的,就是节点查询:对于某个目标 ID,定位离它最近 k 个节点。
节点查询
节点查询是一个递归的过程,过程如下:
-
最初接收到查询请求的节点称为起始节点。起始节点从它的 K 桶中选则 \(\alpha\) (通常为 3)个节点(可以跨多个桶),异步并行地向它们发送 FindNode 消息,并且维护一个它眼里离目标 ID 最近的 k 个节点列表,下面称之为「最近 k 个」。
-
开启递归。收到消息的节点要响应 k 个它已知离目标 ID 最近的节点
-
起始节点收到响应后,它眼里的「最近 k 个」会发生变动,只要里面凑齐了 \(\alpha\) 个节点没有发过 FindNode 消息,就开始新一轮往这 \(\alpha\) 个节点发送 FindNode。所以这一步不需要上一步的 \(\alpha\) 个节点都有响应,它只要凑齐 \(\alpha\) 个即可。
-
结束条件是起始节点眼里的「最近 k 个」里面已经包含了目标 ID 或者 某一轮的 \(\alpha\) 个响应都不能引起「最近 k 个」变化,这时要往「最近 k 个」里面尚未发过 FindNode 消息的节点发送 FindNode,重复这个过程,直到「最近 k 个」不再变化。这个最终的「最近 k 个」就是整个网络中已知的离目标 ID 最近的 k 个节点。
k 的大小和消息的往返时延,可以作为确定 \(\alpha\) 大小的参数。如果某个节点不能响应,则暂时在这次节点查询过程中不考虑它。
对于文件分享型应用,存储 (key, value) 实际就是先 FindNode,找到 k 个离目标 ID 最近的节点,然后对它们发送 Store 消息。每个键值对应该由原始发布节点每 24 小时重新发布一次,因为键值对存储时会设置过期时间,另外可有可能之后有离目标 ID 更近的节点新加入进来了。而根据 key 查找 value 时,也是先找离目标 ID 最近的 k 个节点,不过这个过程中只要某个节点直接返回了 value,就可以提前终止。如果返回 value 的节点不是当前查询者眼里「最近 k 个」里面最近的那个节点,那接着要对当前最近的节点发送 Store 消息,让它缓存(这种缓存其实比较过度,所以过期时间是必不可少的)。这样热点 value 就会被越来越多的节点缓存,而且保存这个 value 的 id 会离 key 越来越远,过期时间可以设置成 ID 和 key 距离的反比。
节点内某个 K 桶如果一个小时内都没有变动过,可以随机选取一个桶范围内的 ID,对这个 ID 执行一下 FindNode,进行 K 桶刷新。
节点的加入和离开
节点新加入时必须先已知某个已存在的节点,作为 bootstrap,并将它加入到自己的 K 桶里面,再对自身 ID 执行一下 FindNode,将 k 个邻居节点添加到 K 桶。最后在对每个 K 桶刷新一次。
Kad 可以容许节点突然下线,因为 (key, value) 是存在 k 个节点里面,只要不是 k 个节点同时下线,整个网络中就总有副本存在。另外有重发布机制,(key, value) 总能存在当前它最应该去的节点。
路由表
Kad 的路由表是一棵二叉树,二叉树的叶子节点是 K 桶,所以它是很不平衡的。K 桶内节点 ID 的公共前缀,就是它在二叉树中的位置。
-
节点一开始只有一个 K 桶,一个桶就覆盖整个 ID 空间。当节点得知其它节点的信息时,将其加入到 K 桶里面。
-
如果 K 桶未满 k 个,则直接加入。
-
如果 K 桶已满 k 个(也就是每满 k 个的倍数就要考虑一下是否要拆分),而且这个 K 桶的 ID 范围包括了节点自身 ID,则这个 K 桶均分为两个桶(桶的 ID 范围对半划分)。
-
否则不用加入到 K 桶里面。
-
实现上的优化
Kad 有许多种变体,都是对其中一些细节的优化。下面介绍一下论文里提到的优化。
重发布优化
如果每个节点对它存储的每个 (key, value) 每隔 1 小时就重发布一次,那网络上的消息就太多了。以下 3 点可以优化这种情况。
-
节点收到 Store 消息之后的下一个小时不用重发布,因为按照 RPC 协议此时还有 k-1 个副本节点。将 k 个副本节点的重发布间隔不要设置成同步,平均每小时有一个副本重发布一次就可行。
-
重发布之前先执行刷新所以 K 桶的步骤,这样就能自动得知要发布给那些节点了,而且把刷新 K 桶的动作也完成了,这样摊销了开销。
-
节点如果新得知一个节点,而且它离自己保存的某个 (key, value) 比自己更近,则向新节点发送 Store 消息。这需要记录每个 key 的「最近 k 个」。
其它优化
-
得知新节点 a,但 K 桶又满了的时候,先不立即对 K 桶最前面的那个节点发送 Ping 消息,而是先将 a 维护到一个「候选列表」里面,也要按照活跃时间排序。等到节点查询时,如果正好要对 K 桶最前面的节点发送消息,这时如果它没有响应,再将它从 K 桶里面去掉,从候选列表里面补一个进去。
-
节点如果对 RPC 没有响应,可以按指数时间增长的间隔时间冷却它一段时间,期间不发送任何 RPC 给它(可能只是丢包或者临时下线)。如果连续 5 次失败,有候选节点的话,则踢掉它,如果踢掉后 K 桶没有满,那也不要去掉它,只是将它做个标记。
-
对于路由表的项,也就是 K 桶,增加 K 桶的范围,减少 K 桶的数目,可以减少节点查询时的跳数。正常 ID 是每一位划分成一个 K 桶,如果是 n 个桶,那跳数为 \(\log_{2}^{n}\);如果每 b 位划分为一个 K 桶,那就是 \(\log_{\lparen 2^b \rparen}^{n}\) 个桶,跳数为 \(\log_{\lparen 2^b \rparen}^{n}\)。这时路由表的拆分条件变为:K 桶首先必须已经满了,在加上 K 桶的 ID 范围包括节点自身 ID 或者 K 桶在二叉树的深度 d,\(d \bmod b\) 不为 0。