1. p2p网络
1.1 Kademlia协议
Kademlia网络节点之间使用UDP进行通信
1.1.1 拓扑结构
散列值的预处理
Kad 也采用了node ID 与 data key 同构的设计思路。然后 Kad 采用某种算法把 key 映射到一个二叉树，每一个 key 都是这个二叉树的叶子。
在映射之前，先做一下预处理:
最短唯一前缀
Kad 使用 160比特 的散列算法（比如 SHA1），完整的 key 用二进制表示有 160 个数位（bit）。
- 实际运行的 Kad 网络，即使有几百万个节点，相比 keyspace（2^160）也只是很小很小很小的一个子集。
- 由于哈希函数的特点，key 的分布是高度随机的。因此也是高度离散的——任何两个 key 都不会非常临近。
- 使用最短唯一前缀来处理 key 的二进制形式，得到的结果就会很短（比特数远远小于 160）。
距离算法: 异或（XOR）
Kad 采用XOR（按位异或操作）算法计算 key 之间的距离。 这样使得它具备了类似于几何距离的某些特性（下面用 ⊕表示 XOR）
(A ⊕ B) == (B ⊕ A)XOR 符合交换律，具备对称性。相比之下，Chord 的距离算法不对称
(A ⊕ A) == 0反身性，自身距离为零
(A ⊕ B) > 0不同的两个 key 之间的距离必大于零
(A ⊕ B) + (B ⊕ C) >= (A ⊕ C)三角不等式
1.1.2 路由机制
二叉树的拆分
对每一个节点，都可以按照自己的视角对整个二叉树进行拆分。
拆分的规则是：
- 先从根节点开始，把不包含自己的那个子树拆分出来；
- 然后在剩下的子树再拆分不包含自己的下一层子树；
- 以此类推，直到最后只剩下自己。
Kad 默认的散列值空间是 m = 160（散列值有 160 bits），因此拆分出来的子树最多有 160 个（考虑到实际的节点数远远小于2160，子树的个数会明显小于 160）。
对于每一个节点而言，当它以自己的视角完成子树拆分后，会得到n个子树；对于每个子树，如果它都能知道里面的一个节点，那么它就可以利用这n个节点进行递归路由，从而到达整个二叉树的任何一个节点。
K-桶（K-bucket）
每个节点在完成子树拆分后，只需要知道每个子树里面的一个节点，就足以实现全遍历。但是考虑到健壮性（分布式系统的节点随时动态变化），只知道一个显然是不够，需要知道多个才比较保险。
Kad 论文中给出了一个K-桶（K-bucket）的概念。也就是说：每个节点在完成子树拆分后，要记录每个子树里面的K个节点。这里所说的K值是一个系统级的常量。由使用 Kad 的软件系统自己设定（比如 BT 下载使用的 Kad 网络，K 设定为 8）。
K-桶其实就是路由表对于某个节点而言，如果以它自己为视角拆分了n个子树，那么它就需要维护 n个路由表，并且每个路由表的上限是K。
K 只是一个上限，是因为有两种情况使得K桶的尺寸会小于K。
K-桶（K-bucket）的刷新机制
刷新机制大致有如下几种：
- 任何节点都可以主动发起“查询节点”的请求（对应于协议类型 FIND_NODE），从而刷新K桶中的节点信息。
- 如果收到其它节点发来的请求（协议类型FIND_NODE或FIND_VALUE），会把对方的 ID 加入自己的某个K桶中。
- Kad 还是支持一种探测机制（协议类型PING），可以判断某个 ID 的节点是否在线。因此就可以定期探测路由表中的每一个节点，然后把下线的节点从路由表中干掉。
并发请求与α参数
K 桶的这个设计思路天生支持并发。因为同一个 K 桶中的每个节点都是平等的，没有哪个更特殊；而且对同一个 K 桶中的节点发起请求，互相之间没有影响（无耦合）。
所以 Kad 协议还引入了一个参数 α 因子，默认设置为 3，使用 Kad 的软件可以在具体使用场景中调整这个 α 因子。
当需要路由到某个子树，会从该子树对应的 K 桶中挑选 α 个节点，然后对这几个节点同时发出请求。
节点的加入
- 任何一个新来的节点（假设叫 A），需要先跟 DHT 中已有的任一节点（假设叫 B）建立连接。
- A 随机生成一个散列值作为自己的 ID（对于足够大的散列值空间，ID 相同的概率忽略不计）
- A 向 B 发起一个查询请求（协议类型 FIND_NODE），请求的 ID 是自己（通俗地说，就是查询自己）
- B 收到该请求之后，（如前面所说）会先把 A 的 ID 加入自己的某个 K 桶中。然后，根据 FIND_NODE 协议的约定，B 会找到 K 个最接近 A 的节点，并返回给 A。
- A 收到这 K 个节点的 ID 之后，（仅仅根据这批 ID 的值）就可以开始初始化自己的 K 桶。
- 然后 A 会继续向刚刚拿到的这批节点发送查询请求（协议类型FIND_NODE），如此往复（递归），直至 A 建立了足够详细的路由表。
节点的退出
与 Chord 不同，Kad 对于节点退出没有额外的要求（没有主动退出的说法）。所以 Kad 的节点想离开 DHT 网络不需要任何操作。
1.1.3 Kad 的优势
简单性
相对于 CAN（Content Addressable Network）——它是最早出现的四个 DHT 协议之一（2001年），CAN 的拓扑结构是基于多维笛卡尔环面。与 CAN 的多维环面比起来，Kad 基于二叉树的拓扑结构，就显得非常简单。
Kad 除了拓扑结构很简单，它的距离算法也很简单——只不过是节点 ID 的异或运算（XOR）。
灵活性
以 Kad 和 Chord 的路由表来作对比。Kad 的K-bucket是可以根据使用场景来调整K值，而且对 K值的调整完全不影响代码实现。这就是所谓的设计的弹性,相比之下，Chord 的Finger Table就没有这种灵活性。
性能
Kad 的路由算法天生就支持并发（参见前面介绍的“α 参数”），而很多 DHT 协议（包括 Chord）没有这种优势。
由于公网上的线路具有很大的不确定性（极不稳定），哪怕是同样两个节点，之间的传输速率也可能时快时慢。由于 Kad 路由请求支持并发，发出请求的节点总是可以获得最快的那个 peer 的响应。
安全性
假设某个攻击者想要攻击 Chord 网络的某个节点（假设叫 A），他可以先获得此节点 A 的 ID。知道 节点A 的 ID 后，攻击者就可以运行若干个受控的 Chord 节点（恶意节点），并且精心设置这批恶意节点的 ID；当这批恶意节点加入 Chord 网络后，就可以顺利被添加到 节点A 的路由表中（参见前面对Finger Table的介绍）。一旦节点 A 的路由表加入足够多的恶意节点，那么节点 A 的路由就有足够大的概率会经过这批恶意节点。攻击者作为这批恶意节点的控制人，就可以对节点 A 做很多手脚。
从理论上讲，类似的手法也可以用来针对 Kad。但是攻击难度会显著变大。原因如下：
- Kad 协议缺省约定——在线时间越长的节点越可能被加入 K 桶 。所以攻击者哪怕构造了一批恶意节点，这些恶意节点要想被正常节点加入自己的“K桶”，难度也很大。
- 某个恶意节点（比如叫 X）被正常节点（比如叫 A）加入 K-桶 。由于一个 K-桶 只对应一个子树。所以，只有当节点 A 在针对某个特定子树进行路由的时候，才有可能会碰上这个恶意节点。
- 即便正好对这个子树路由，也不一定会碰上恶意节点——碰上的概率取决于：K 的大小以及 从桶中选取节点的策略。
- 前面提到：Kad 协议支持并发查询——每次都会从同一个 K-桶中取出α个节点，发出查询请求（参数 α 默认设为 3,可以调大）所以，这α个节点中，如果只有一个是恶意的，这个恶意节点也很难捣乱；除非这α个节点全部都是恶意的，而这个概率又很小。
