P2P网络有四个发展阶段：集中式网络，纯分布式网络，混合式网络，结构化网络。

集中式网络

集中式的P2P网络最简单，即一个节点保存了其他所有节点的索引信息，而索引信息又包括了节点IP，端口，节点资源等。节点之间互连的路由查询由中心节点完成，一旦和对等节点建立连接则与中心节点没有什么联系。集中式的P2P网络结构简单，实现容易，但是由于所有路由信息在中心节点存储，当节点数量变多扩展的时候容易出现性能瓶颈，也容易出现单点故障。

纯分布式网络

纯分布式的P2P网络移除了中心节点，在P2P网络之间建立了随机网络，一个新加入的节点和P2P网络中的某个随机节点建立连接，从而形成一个随机的拓扑结构。新节点和邻居节点建立连接以后还需要全网广播，让整个网络知道自己的存在。

全网广播的方式是，该节点向自己的邻居节点广播，邻居节点收到消息以后在向自己的邻居节点广播，以此类推，从而广播到整个网络。这种广播也称为泛洪机制。

纯分布式的P2P网络不存在集中式网络的单点故障和中心性能瓶颈的问题，具有较好的扩展性，但是泛洪机制又引入了新的问题，一是容易形成泛洪循环，A节点发出的消息经过节点B到节点C，节点C在
广播到节点A，形成了一个消息循环；另一个是响应消息风暴的问题，如果节点A想请求的资源被很多节点所拥有，那么在短时间内就会出现大量的节点向A节点发送响应消息，可能会让节点A崩溃。

混合式网络

混合式的P2P网络就是混合了集中式和纯分布式的结构，网络中存在多个超级节点组成分布式网络，而每个超级节点则与多个普通节点组成局部的集中式网络。一个新的普通节点加入网络需要先选择一个超级节点通信，该超级节点在推送其他超级节点列表给新加入的节点，加入节点在根据超级节点列表中的状态选择加入哪个超级节点作为父节点。这种结构限制了泛洪广播的范围，避免了大规模的泛洪问题。
在实际应用中，混合式结构是相对灵活且比较有效的网络架构，实现也相对容易。

结构化网络

结构化P2P网络也是一种分布式网络结构，但又与纯分布式有所区别。纯分布式网络就是一个随机网络，而结构化网络则将所有节点按照某种结构有序的组织起来，比如形成一个环状网络或者树状的网络。
结构化网络的具体实现上普遍都是基于DHT(Distributed Hash Table，分布式哈希表) 算法。具体的实现方案有 Chord、Pastry、CAN、Kademlia 等算法，其中 Kademlia 也是以太坊网络的实现算法，后面中重点讲解它的实现原理。

Kad算法原理

Kad算法用来在分布式环境中准确的路由，定位数据。

在Kad网络中每个节点都有一个随机产生的160bit的标识符作为节点ID，Kad算法通过计算节点ID间的距离来快速路由和定位资源。

Kad算法通过异或节点ID来计算节点之间的距离，这个距离是逻辑上的距离并不是节点间物理上的距离。

1
2
3
节点A的ID（010）
节点B的ID（110）
A ⊕ B = 100（二进制） = 4（十进制）

在上面异或度量节点距离的基础之上，Kad算法还可以将整个网络划分成一个二叉前缀树，每个节点映射到二叉树上的某个叶子。

映射规则：

  • 将节点ID（160bit）从高到低依次分层，第N位就对应了第N层
  • 如果是0进入左子树，如果是1则进入右子树
  • 每个节点就对应树中的一个叶子

在这种二叉树结构下，对于每个节点来说离他它越近的值节点的异或距离也越近，每一个节点都可以从自己的视角来对二叉树进行拆分，拆分规则是从根节点开始，把不包含自己的子树拆分出来，然后在剩下的子树再拆分不包含自己的下一层子树，以此类推，直到最后只剩下自己。上图的例子就是以节点ID为110的视角多二叉树进行了拆分。

因为Kad算法默认的节点ID是160bit，所有拆分以后最多可以有160课子树，而对于每个子树，如果我们分别知道里面的一个节点，就可以利用这个节点递归路由到子树的任意一个节点。

但是在实际应用中，由于节点是动态增加减少的，如果知道的节点恰好宕机或者下线了就会出现问题，为了保证系统的鲁棒性Kad算法又引入了K桶（K-bucket）的机制。

K桶（k-bucket）

节点在完成拆分子树以后需要记录每个子树里面K个节点，K可以由用户自己定义，在BT下载使用的Kad算法中K是8。

K-bucket实际上就是路由表，每个节点按照自己的视角拆分完子树以后可以得到N个子树，那就需要维护N个路由表，对应N个K-bucket.

每个节点维护N个K-bucket以后还会出现一个问题，K-bucket中的节点也会动态的增减，那又如何K-bucket的稳定呢？

K桶的更新机制

K-bucket主要有三种方式来更新路由表。

  • 主动收集节点，主动发起FIND_NODE查询节点的请求，从而更新K桶的节点信息。
  • 被动收集节点，当收到其他节点发送过来的请求（如：FIND_NODE、FIND_VALUE），会把对方的节点ID加入到某个K桶中。
  • 检测失效节点，周期性的发起PING请求，判断K桶中某个节点是否在线，然后清理K桶中哪些下线的节点。

当一个节点ID被用来更新K桶的时候进行如下步骤：

  • 计算自己和目标节点ID的距离d
  • 通过距离d找到对应的K桶，如果ID已经在K桶中了则把对应项移到K桶的末尾

  • 如果不在K桶中则有两种情况

    1.如果该K桶存储的节点小于K个，则直接把目标节点插入到K-桶尾部；
    2.如果该K桶存储节点大于等于K个，则选择K-桶中的头部节点进行PING操作，检测节点是否存活。如果头部节点没有响应，则移除该头部节点，并将目标节点插入到队列尾部；如果头部节点有响应，则把头部节点移到队列尾部，同时忽略目标节点。

通过这种更新策略可以保证在线时间长的节点有较大的可能继续保存在K桶中，提高了稳定网络构建路由表的成本。

加入Kad网络

一个新节点需要加入Kad网络有如下的步骤

  • 新节点A需要一个种子节点B作为引导，并把该种子节点加入到K桶中。
  • 生成一个随机的节点ID，直到离开网络一直使用。
  • 向节点B发送FIND_NODE请求。
  • 节点B在收到节点A的FIND_NODE请求后，会根据FIND_NODE请求的约定，找到K个距离A最近的节点，并返回给A节点
  • A收到这些节点以后，就把它们加入到自己的K桶中
  • 然后节点A会继续向这些刚拿到节点发起FIND_NODE请求，如此往复，直到A建立了足够详细的路由表。

定位节点

节点查询可以同步进行也可以异步进行，同时查询并发一般为3。

  • 确定目标ID对应路由表中的K桶位置，然后从自己的K-桶中筛选出K个距离目标ID最近的节点，并同时向这些节点发起FIND_NODE的查询请求。
  • 被查询节点收到FIND_NODE请求后，从对应的K桶中找出自己所知道的最近的K个节点，并返回给发起者。
  • 发起者在收到这些节点后，更新自己的结果列表，并再次从其中K个距离目标节点ID最近的节点，挑选未发送请求的节点重复第一步
  • 不断重复上面的步骤直到找到目标节点为止