节点状态- K桶数据结构

Kademlia 的设计中， 在每一个单一的节点都用一个数据结构来存储这个节点所了解的系统中其它节点的信息（view）。 也就是这个单一节点对于整个系统的一个视图。 当然这个视图是非常有限的， 因为单一的节点不可能也不需要存储全系统的节点信息。

Kademlia使用了一种 命名为K桶的数据结构来存储这个视图。

首先因为node ID 长度为160 bit 所以 Kademlia 将全系统的节点按照和本地节点之间的距离而划分为160个列表（桶）。 我们令 0 ≤ i < 160， 则第i个列表包含的是和本节点之间距离为  到  的K个节点。 K是个全局的值，需要根据系统具体情况来调整。 因为在i 比较小的情况下，距离近的节点数量可能很少或者没有， 而在i比较大的情况下， 节点数量可能会很大。 在第i个列表中的每一个节点会存储3个信息（IP地址，UDP端口号，节点ID） 如下图所示：

在每一个列表中， 最近看到的节点会被放置于队列尾部， 最久被看到的节点会被放置于队列头部。 当节点接收到其它节点的任何消息（查询或者应答），本地节点都会更新对应的K 桶数据列表。

1. 如果发送消息的节点已经在本地节点的K桶数据列表之中，则把它移动到队列尾部（最近发现原则）。

2. 如果发送消息节点并不在本地节点的K桶数据列表之中， 且所对应的列表节点数小于K， 则将它添加到队列尾部（最近发现原则）。

3. 如果发送消息节点并不在本地节点的K桶数据列表之中， 且所对应的列表节点数等于K（队列满!). 这个时候则需要向队列头部的节点发送Ping消息测试其是否在线。

3.1 如果头部节点在线， 则有消息返回，原来的头部节点被移动到队列尾部（最近发现原则）， 而发送消息节点的信息被抛弃不用！。

3.2 如果头部节点不在线，则将头部节点移除，发送消息节点被加入队列尾部。

这种设计有助于抵御拒绝服务攻击。亦即， 恶意攻击方无法通过巨量的新节点信息淹没仍然在线的有效旧节点。 因为K桶中列表如果已经满载，则只会在旧节点无效的情况下才会添加新节点。

后续请参考

Kademlia 简介（2） － 小专栏​xiaozhuanlan.com