一、概念

        常见的P2P网络主要分为两种类型:结构化网络和非结构化网络。

        非结构化的P2P网络：并不给节点的连接覆盖某种特定的架构，节点直接随机连接。因为缺少结构，所以网络面对频繁的动态添加和删除结点时，依然能够健壮地运行，但也正因为缺少结构，所以当某个结点想要搜索某些数据或文件时，查询必须flood整个网络。

        结构化的P2P网络：将网络组织成某种特定的扩扑结构，并且他们之间的协议能够保证任何结点都能高效地搜索网络中的资源，即使是非常冷门的资源。常见的结构化P2P网络通常实现一致性哈希或者其变种分布式哈希表DHT分配文件的所有权到特定的结点

二、P2P中常见的索引方式：

        中央索引：

        由一个中央服务器统一保存资源与结点的关系。这种方式搜索效率比较高，因为可以通过中央索引直接定位到目标结点，然而这种方式有时并不可行，特别是集群规模特别大时，无法解决单点故障。

        本地索引：

        每个结点保存自己的资源信息，当寻找不属于自己的资源时，会flooding整个网络进行寻找。这种flooding的方式会在网络中引起大量的traffic，并使每个结点都要处理查询请求而导致高CPU和内存使用率。并且flooding不保证通信质量，所以flooding也无法保证一定能够找到保存指定数据的那个结点。因为热数据在多个结点上存在，所以比较容易搜索成功。反之，冷数据只在很少的结点上存在，所以搜索很可能会以失败告终。并且搜索效率也很低，也容易导致安全问题。

        分布式索引：

        为了高效地在网络中搜索，结点需要保存满足特定条件的邻居的列表，这使得整个网络在高频率的添加删除结点时，没有非结构化网络那样健壮。使用DHT路由的结构化P2P网络的著名软件有BitTorrent，Kad Network，以及各种研究项目Chord等。基于DHT的网络在网络计算系统中也有广泛的应用，它帮助实现高效的资源发现和应用程序调度等

三、分布式索引--- KAD算法：

        KAD算法全程Kademlia，在实际的DHT路由中，大部分都是采用KAD这种变种来实现的，BT、eDonkey/电驴、eMule/电骡， I2P 暗网等等，其中以太坊中也采用KAD算法来实现路由的。

(一)、"最短距离"的概念

        当从P2P网络中查询某一条数据时，为了避免泛洪查找，首先要定位到离数据的KEY最近的一个节点，然后从该节点上提取所需要的数据。那么这个最短距离如何确定呢？

        首先，我们获取到P2P中所有节点的nodeId，经过hash算法，表示成某一固定长度的二进制接口。同理，用同样的hash对数据key进行hash并表示为二进制。然后对数据key和nodeId计算其异或距离，找到其中距离最小值就是我们的最短距离。

        假如hash完后的数据二进制长度为3位，并且存在4台服务器。 data key的值为101，按照data key 和node id的同构原理，应该是寻找节点101， 但是该节点不存在，故需要寻找距离最短的节点，也就是100节点。故应该从nodeId = 100这台机器上查询当前的数据。

注意：这里的距离并非真实的距离，而是逻辑距离。

(二)、逻辑拓扑结构 和 K-Buckets K桶

        在P2P的网络中，每个节点都保存了其他节点的信息。当我请求其中一个节点时，该节点如何快速的定位到数据是位于哪个节点上呢？那么其他节点信息在当前节点中如何存储，这就是逻辑拓扑结构要解决的问题了。

        现在假如 nodeId 经过hash后 的位数还是3位，那么理论上整个网络中就可以存在2^3 = 8 个节点。节点包括：

001，010，011，000，100，101，110，111

        我们将每个节点的表示为二进制后，按照左0右1构建如下二叉树。其中不难发现，所有的叶子节点就是我们的服务器节点。如下图

        如图，当前节点为101， 那么该节点如何存储其他节点，以方便快速定位呢？ 这里采用分层。

        首先计算每个节点与 当前节点101的距离， 按照一定距离进行分层。

        分层规则: 定义从最右位开始，第一次开始出现不同位时，则表示为同一层。

        按照入上规则进行分层，可以看出，第一层与当前节点的距离是最短的，层数越高，节点到当前节点的距离越远。

        此时，如果当前节点接收到查询请求，先将数据的key 按照同样的hash算法，然后表示为二进制， 假如data key = 100 。 首先将data key 与当前节点 nodeId = 101 进行距离计算(异或)， 其中异或结果就代表了当前数据节点所在的层。 100 ^101 = 1 ， 故存储数据的节点在第一层，然后定位到100节点，向100节点发送查询请求。

        此时可以发现，不用利用泛洪式查找就能快速定位到资源所在的位置。加入现在资源定位在第3层，那么我只要遍历二叉树中的左面四个节点就可以，避免了遍历整个子树的问题。

        K-Buckets:

        由于我们举例中的节点只有三位，但是现实中庞大的集群网络节点可能会存在上万个节点。比如以太坊中的位数为256位，那么网络中理论上就可以存在2^256个节点。

        当网络中节点的数量不断扩张时，不可能在每个节点上都存储所有其他节点的信息。 从上例也可以看出，位数的增加，层数也不断增加，而越高层存储的信息也就越多。

        所以 Kad 论文中给出了一个“K-桶(K-bucket)”的概念。也就是说：每个节点在完成子树拆分后，要记录每个子树里面的 K 个节点。这里所说的 K 值是一个【系统级】的常量。

        也就是说每一层，我们最多存储K个节点。因为只要知道当前子树的一个节点，理论上我们就可以知道并能够遍历当前子树的所有节点。那为什么不存储一个呢？ 因为分布式下的节点的动态变化的，如果当前节点宕机，就会影响该子树。故可以根据系统自身的特性来调整K值的大小。比如BT设定K = 8, 以太坊中设定为16.

        其中，每层中存储的节点的顺序是按照与当前节点的由近及远来存储的。

(三)、KAD节点的更新机制

        当节点 收到一个 PRC 消息时，发送者B的节点信息就被用来更新对应的 K 桶，具体步骤如下：

        1、计算发送者节点与当前节点的距离。

        2、根据距离选择位于K桶第几层

        3、如果发送者B已经存在于K桶中，则移动B节点到最前面

        4、如果B不在K桶中，且桶中数量小于K个，则添加B节点信息到K桶末尾

        5、如果B不在K桶中，且桶中的数据量大于K个，先给桶中末尾节点发送PING消息：

                                如果收到回复，则忽略B节点。

                                如果未收到回复，则删除末尾节点，加入B节点。

        原因如下: 

             K 桶的更新机制的实现依赖于一个理论：用户在线时间越长，它在下一时段继续在线的可能性就越高。        这种机制的另一个好处是能在一定程度上防御 DOS 攻击，因为只有当老节点失效后，Kad 才会更新 K 桶的信息，这就避免了通过新节点的加入来泛洪路由信息。

(四)、KAD的UDP通信协议：

        1、PING事件:  校验节点是否存活

        2、PONG事件：对PING事件的回复

        3、FIND_NODE事件：向节点查询某个与目标节点ID距离接近的节点

        4、NEIGHBORS事件：对FIND_NODE命令响应，发送与目标节点ID距离接近的K桶中的节点。

(五)、KAD的路由查询机制：

        假如集群中的某个节点A收到一个FIND_NODE请求，要求查询 与ID为m的节点最近的节点信息,具体的步骤如下：

        1、计算当前A节点ID与M的距离：

        2、锁定到K桶的层，并从中获取aplha个节点，如果节点数不足alpha，则从附近的桶中获取节点。

        3、同时向alpha个节点发送FIND_NODE请求。

        4、接收到FIND_NODE的节点，如果发现自己的ID是m则返回。从自己K桶中选择距离最近的alpha个节点返回。

        5、当节点A接收到返回的数据时，如果有m则返回，如果没有m，则再次向返回的alpha个节点发送FIND_NODE请求继续查找，如此循环，直至遍历完所有的节点。

        其中在BitTorrent和以太坊中设定alpha = 3。

        原因如下：

                由于每次查询都能从更接近 m 的 K 桶中获取信息，这样的机制保证了每一次递归操作都能够至少获得距离减半（或距离减少 1 bit）的效果，从而保证整个查询过程的收敛速度为 O(logN) ，这里 N 为网络全部节点的数量。

                借用网络上一张图描述其查找的过程: