Go ethereum P2P : Kademlia (1)

为什么要引入P2P寻址协议

P2P 系统不存在一个中心的服务器来提供寻址， 而且系统中的节点在线状态是非常动态的，随时都会有新节点加入，或者有存在的节点退出。 这些特点给寻址协议带来了很大的挑战。 一个成功的设计需要满足以下要求 1. 节点的地址不能有冲突 2. 尽可能的高效的寻址 3. 如何保持网络拓扑的一致性 4. 如何的处理节点状态的变化（新加入与退出）

历史上已经存在Chord、CAN、Pastry 等协议，都存在方方面面的问题。

Kademlia 简介

Kademlia 是一种被广泛使用的第三代的P2P 分布式哈希表。 2002年纽约大学的 Petar Maymounkov, David Mazieres 发表名为《Kademlia: A Peer to Peer Information System Based on the XOR Metric》的论文。 由于Kademlia具备一些优异的特性，随后逐渐被主流P2P 开源项目接受，emule， IPFS， Bitrorrent，Gnutella 都使用了 Kademila相关技术。

1. 实现了从一个节点寻址另外一个节点所需发送的配置查询信息数量最小化。
2. 在节点寻址的过程中伴随着配置信息的传播。
3. 节点寻址算法可以提供优化的低延迟路径。
4. 节点通过使用并发的异步的查询来避免失败节点导致的超时。
5. 系统架构可以抵御一些基本的拒绝服务攻击。
6. 寻址过程一直使用单一的算法而不是不同步骤采用不同算法。

最后Kademlia的以上特性建立在一个比较重要的假设基础上。 该假设是 关于在线节点时间在线时间的分布（简单说就是较长时间在线的节点有更大概率在未来仍然在线）

系统的基本特征

节点的ID

在Kademlia的设计中，系统中每个节点都有一个唯一的ID。 在分布式哈希表(DHT)中普遍使用的伪随机的ID。 由SHA1 算法从种子数据中生成一个160 bits 的输出数据作为ID（SHA1的输出长度是20 Bytes,亦即 160 bits）。

Node 节点间异或距离(XOR Metric)

定义异或 距离 d 具备以下代数性质：

1. d(x,x) = 0. 异或的特性就是相同的比特位归零。

2. d(x,y) > 0, if x ≠ y. 如果x，y 有不同比特位 这个也是显而易见的.

3. d(x,y) = d(y,x). 可交换性也是显而易见的。

4. d(x,y) + d(y,z) ≥ d(x,z). （三角不等式）。 这里如果我们把不等式左边的加号替换为XOR, d(x,y) XOR d(y,z) -> (x XOR y) XOR (y XOR z） = x XOR z）。 从而我们只要比较 d(x,y) + d(y,z) 和 d(x,y) XOR d(y,z) 的关系， 显而易见的是 d(x,y) + d(y,z) ≥ d(x,y) XOR d(y,z) ，因为+ 对于各个比特位是累进的， 不会出现归零的情况。 所以肯定是大于等于关系。

树状分布

Kademlia 把每个节点都当作一个二叉树的叶子节点来对待。 如下图（引自原论文）

后续请参考