优点
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。