Kademlia：一个基于异或度量的P2P信息系统

论文原文：https://link.springer.com/chapter/10.1007%2F3-540-45748-8_5

原文除了摘要，总共有5部分，分别是：介绍、系统描述、证明、实现要点、总结。这里只翻译摘要和核心的系统描述以及实现要点部分

摘要

我们描述了一个在易发生故障的环境中具有可证明的一致性和高性能的P2P系统。我们的系统使用一种新的基于异或度量拓扑来进行路由查询和结点定位，这种拓扑简化了算法并易于证明。该拓扑在信息交换时仅传递或增强有用的信息，系统利用这些信息进行并行或异步的信息查询，同时也能容忍节点故障，并且不会给用户带来超时延迟

系统描述

我们的系统基本上采取了和其他DHT系统一样的方法。节点的 ID 是 160 位不透明的值，我们的算法也是逐步“逼近”所期望的 ID ，并以对数级的速度收敛到要查询的目标。

Kademlia把一个节点看这一颗二叉树的叶子，每个节点的位置由其ID的最短唯一前缀决定。图一展示了一个唯一前缀为0011节点在树中的位置。对于任意给定的一个节点，我们都把树划分为一系列不包含该节点的逐步降低的子树。最高层的子树有二叉树中不包含该节点的那一半组成，接下来的子树由剩余的不包含该节点的一半组成，以此类推。在示例中的0011节点，子树被圈出来，分别由前缀为0,01,000以及0010的节点构成

Kademlia协议确保每个节点都至少知晓这些子树中的一个节点。有了这个保证，任何一个节点都可以通过ID定位其他节点。1110的示例，其中节点 0011通过逐步查询它所知道的最佳节点来取得和越来越低层次子树的联系；最后查询收敛到目标节点。

接下来，我们会补充一些细节，并更具体的描述查询算法。首先，我们会给出 ID 接近这个概念的准确定义，这样就可以谈及“在距离 key 最近的k个节点上存储或者查询 键值对”这样的行为。然后，我们会介绍一个查询协议，该协议即使在任何节点都不和某个key具有相同的前缀或者和某个给定节点关联的子树中有一些为空的情况下，都可以正常工作。

异或度量

每个Kademlia节点都有160位的ID，节点id构造像Chord一样，但是为了简化，我们假设机器在加入系统时选择一个随机的160位标识符。节点传输的每个消息都包含其ID，并且允许接收方在必要时记录发送方的存在。

key同样也是160位的标识符。为了发布和查找键值对，Kademlia依赖于两个标识符之间的距离。给定两个160位标识符x和y,Kademlia将它们之间的距离定义为它们的为异或（d(x,y)），并转化为整数。

我们首先注意到虽然异或不是欧几里得度量，但仍是有效的。很明显，d(x,x) = 0。如果x ≠ y则d(x,y)>0。以及d(x,y)=d(y,x)。除此之外，异或还满足三角不等式，因为d(x,z) = d(x,y) xor d(y,z),而a+b >= a xor b

和chord的顺时针圆周度量一样，异或也是单向的。给定任意一个点x和距离d>0，都会存在一个点y，使得d(x,y) = d。单向性确保所有对相同键的查找都沿着相同的路径收敛，而不管初始节点是什么。因此，沿着查找路径缓存键值对可以缓解热点。就像Pastry一样，但不像Chord，异或拓扑是对称的，即(d(x,y) = d(y,x))

节点状态

Kademlia节点存储彼此之间的路由联系信息。对于每个i（0 <= i < 160），节点都会存储一个含有<IP地址列表;UDP端口;节点ID>列表，每个列表项表示距离自己2^i和2^i+1之间的节点。我们称这些列表为k桶。每个k桶都按照时间顺序进行排序，最后一次看到的节点位于头部，最近一次看到的节点位于尾部。对于较小的i值，为k桶通常是空的(因为没有合适的节点)。对于较大的i值，列表长度可以增长到k，其中k是一个系统范围的全局变量。选择k时，任何给定的k个节点都不太可能在一小时内发生故障(例如k = 20)。

当Kademlia节点接收到来自另一个节点的任何消息(请求或响应)时，它将更新发送方节点ID所在的k桶。如果发送节点已经存在于收件人的k桶中，则收件人将其移动到列表的末尾。如果节点还没有在适当的的k桶中，并且桶的条目数小于k，那么接收方只需在列表的末尾插入新的发送方。但是，如果应村的k桶已满，则接收方将PING k桶的最近最少出现的节点，以决定该做什么。如果最近最少出现的节点没有响应，则将其从k桶中删除，并在末尾插入新的发送者。否则，如果最近最少出现的节点有响应，则将其移动到列表的末尾，并丢弃新发送方的联系人。

k桶有效地实现了一个最近很少键的清除策略，除非活动节点从未从列表中删除。这种对旧的联系的处理是基于对Saroiu等人收集的Gnutella微量数据分析而得出的。图1显示了Gnutella节点继续在线一个小时的百分比，这是当前正常运行的时间函数。节点运行的时间越长，它继续运行一个小时的可能性就越大。通过保留旧的联系人，k桶最大化了它们所存的节点保持在线的可能性。

k桶的第二个好处是，可以抵抗特定的DoS攻击。无法通过向系统中注入新节点来刷新节点的路由状态。Kademlia节点只会在旧节点离开系统时将新节点插入到k桶中。

Kademlia协议

Kademlia协议由四个rpc组成：PING, STORE, FIND NODE 和 FIND VALUE。PING探测一个节点，看看它是否在线。STORE指示节点存储键值对，以便以后检索。

FIND NODE以160位的ID作为参数。接收者返回<IP地址;UDP端口;节点ID>三元组表示它知道的最接近目标ID的k个节点。这些三元组可以来自单个k桶，也可以来自多个k桶（如果最近的k桶没有满的话）。在任何情况下，RPC接收方都必须返回k个条目(除非所有k个桶的组合中有少于k个节点，在这种情况下，它返回它所知道的每个节点)。

FIND VALUE的行为类似于FIND NODE，也返回<IP地址;UDP端口;节点ID>三元组，只有一个例外。如果RPC接收方收到了STORE的RPC，它只返回存储值。

在所有RPC中，接收者必须回显一个160位的随机RPC ID，这为地址伪造提供了一定的抵抗力。还可以在RPC应答上附加ping，以便RPC接收方获得对发送方网络地址,从而获得额外保证。

Kademlia参与者必须执行的最重要的过程是定位距离某个给定节点ID最近的k个节点。我们将此过程称为节点查找。Kademlia使用递归算法进行节点查找。查找发起者首先从最近的非空k桶中选择α个节点（如果已知节点数少于α，则选择全部节点）。。发起者发送并行或异步的rpc FIND NODE给α个节点。α是一个全系统的并发性参数，比如3

在递归步骤中，初始节点将FIND NODE重新发送到它从之前的rpc结果中了解到的节点（这个递归可以从先前的RPC返回后开始）。收到响应后，发起者向离目标更近的其中α个未被请求的节点发送FIND NODE。无法快速响应的节点将从考虑中删除，直到它们再次响应。如果一轮查找节点未能返回比已知的更近的节点，则初始节点将FIND NODE重新发送给它尚未查询的k个最近的节点。当初始节点查询并从它所知的k个最近的节点中获得响应时，查找将终止。当α= 1查找算法类似于Chord的信息消耗和延迟检测失败的节点。然而，Kademlia可以通过路由获得更低的延迟，因为它可以灵活地选择k个节点中的任意一个来转发请求。

大多数操作都是根据上面的查找过程实现的。要存储键值对，参与者需要找到距离键最近的k个节点，并向它们发送STORE rpc。此外，每个节点每小时重新发布它拥有的键值对，这确保键值对的持久性概率维持较高水平。通常，我们还需要键值对的原始发布者每24小时重新发布一次。否则，所有的键值对将在最初发布24小时后过期，从而限制系统中的陈旧信息。

最后，为了使键值对的发布-搜索在声明周期中保持一致，我们要求每当一个节点w观察到一个新的节点u时，这个新节点u更接近w的一些键值对时，w将这些对复制到u，而不从自己的数据库中删除。

要查找一个键值对，初始节点首先进行查找，查找id最接近的k个节点。不过，使用的rpc是FIND VALUE。此外，当任何节点返回值时，程序立即停止。出于缓存的目的，一旦查找成功，请求节点将键值对存储在它观察到的最接近目标但没有返回值的节点上。

由于拓扑的单向性，未来对相同键的搜索可能会在查询最近的节点之前命中缓存的条目。在某个键非常流行的时候，系统可能会在许多节点上缓存它。。为了避免“过度缓存”，我们将任何节点数据库中的键值对的过期时间设置为与当前节点和ID最接近的节点之间的节点数量成指数反比。虽然简单的LRU清除将导致类似的生存期分布，但是没有选择缓存大小的天生方法，因为节点不知道系统将存储多少值。

桶中内容经常会保持最新，这是由于通过节点传输的请求流量造成的。为了避免在没有通信量的情况下出现病态情况，每个节点需要在某个桶所在范围内一个小时没有执行节点查找时进行刷新。刷新意味着在桶的范围内随机选择一个ID，并对该ID执行节点搜索。

要加入网络，节点u必须与已经参与其中的节点w有联系。然后，u对自己的节点ID执行节点查找。最后，u刷新所有k桶。在刷新期间，u都填充自己的k桶，并根据需要将自己插入其他节点的k桶中。

路由表

根据协议，Kademlia的基本路由表结构相当简单，不过在处理高度不平衡的树时需要稍作改进。路由表是一个二叉树，它的叶子是k桶。每个k桶包含一些节点，它们的id具有一些公共前缀。前缀是k桶在二叉树中的位置。因此每个k桶覆盖ID空间的某个范围，所有k桶一起覆盖整个160位ID空间，没有重叠。

路由树中的节点根据需要动态分配。图4说明了这个过程。最开始，一个节点u的路由树只有一个节点，一个k桶覆盖整个ID空间。当u获得一个新的连接时，他就会将其插入适当的k桶。如果该桶未满，只需简单插入。反之，如果k桶的范围包含u自己的ID，那么这个bucket就会被分成两个新桶，旧的内容被划分到这两个桶中，然后重复插入尝试。如果k桶已满，且不包含u的ID，则直接丢弃新的信息。

一个复杂的情况出现在高度不平衡的树中。假设节点u加入系统，并且是ID从000开始的惟一节点。进一步假设系统已经有超过k个前缀为001的节点。每个带001前缀的节点将有一个空的应该将u插入其中的k桶，但是u在对其k桶进行更新是只会通知到其中k个节点。为了避免这个问题，Kademlia节点将所有有效的联系人保存在至少k个节点大小的子树中，即使这需要分割桶，而节点本身的ID并不驻留在桶中。图5显示了这些额外的分割。当 u 更新这些分割过的 buckets 时，所有具有 001 前缀的节点都会得到通知。

高效的key重发布

为了确保键值对的持久性，节点必须定期重新发布key。否则，有两种情况会导致对有效 key 的查询失败。首先，在发布时，最初获得键值对的k个节点中的一些会离开网络。其次，新加入节点的 ID 相比键值对的原始发布节点，可能距离该key更近一些。在这两种情况下，拥有键值对的节点必须要对其进行重新发布，这样就再次保证了从距离该 key 最近的 k 个节点上可以获取该 key 。

为了对节点离开造成的问题的弥补， Kademlia 每一小时就对每个键值对进行重新发布。这种实现会导致很多消息往来，存储键值对的k个节点每小时都会进行一次节点查询，饭后进行k-1出STORErpc调用。幸运的是，可以对这种过程进行优化。首先，当一个节点收到一个针对某个键值对的STORE rpc时，他可以认为该rpc也发送给了其他k-1个节点，因此他就不会重新发布键值对。这就保证了只要重新发布间隔不是精确同步的，对于任何一个键值对来说，每小时只会有一个节点对其进行重新发布。

第二个优化是避免在重新发布key之前进行节点查找。如2.4小节所示，为了解决不平衡树，节点在需要时可以分裂k桶以保持其具有关于一个节点个数超过k的边缘子树的全部知识。在重新发布键值对之前，如果节点u更新了该字数中k个节点的所有k桶，那么他将自动获取关于某个key值最近的k个节点信息。对于这些桶的更新代价可以分摊到许多key的重新发布上。

要想知道为何在对规模大于k的子树中的桶进行更新后，就无需再进行节点查询操作，就得考虑两种情况。如果要被重新发布的key位于该子树覆盖的ID区间内，那么由于该子树的规模至少为 k ，并且 u 具有关于该子树的全部知识，因此u一定知道距离该key最近的 k 个节点。另一方面，如果key位于子树范围之外，而u是距离该key最近的k个节点之一，那么按照 u 的k桶规则，所有距离该key比子树更近一些的区间中的元素都少于k。因此， u 将知道这些k桶中的所有节点，再加上关于子树的知识，就可以得到距离该 key 最近的 k 个节点。

当一个新节点加入系统时，对于每个 key-vaule 对来说，如果该节点为其 k 个最近节点之一，那么必须对其进行存储。系统中原有的节点同样可以通过其边缘子树的完整知识，知道哪些键值对需要存储在该新增节点上。每个了解到新节点的节点都会发起 STORE RPC 把相关的 key-value 对传送到新节点之上。为了避免重复的 STORE RPC ，只有那些自身 ID 比其他节点 ID 更接近 key 的节点才会进行 key-value 对的传送。

实现注意事项

在本小节中，我们将介绍两个用来改进 Kademlia 实现性能的重要技术。

优化联系记录

对于k桶最基本的属性是能够提供LRU检查，并且在不丢失任何有效信息的情况下删除无效信息。如2.2节所述，如果一个k桶已满，他会在收到该桶范围内的任何一个位置节点的消息时发送一条PING。这个PING用来检测最近最少使用的节点是否仍然有效。如果无效，新的节点为替代带旧的节点。不幸的是，这种行为会导致大量的ping消息充斥在网络中

为了减少这些流量，Kademlia会延迟这个探测行为，直到要发送一条有用的消息给他们时。当一个节点收到一个未知节点的消息时，如果所在的k桶已满，节点会把它放在一个置换缓存中，当节点下次查询是，对于无效的节点会被用缓存中的节点替换。缓存中的节点时按照时间排序的，最近的节点有最高的优先级。

有一个和Kademlia使用UDP相关的问题。当网络丢包时，会丢失一些有效节点的信息。通常丢包意味着网络阻塞，所以Kademlia会锁定那些未响应的节点，并在一个以指数增长的退避时间间隔内不向其发送任何消息。因为在Kademlia查询过程中，大部分情况下只需联系到 k 个节点中的一个，所以一般情况下，系统不会向同一节点重传被丢弃的 RPCs

如果连续五条消息都没有响应，则认为是过期的。如果k桶不满，或缓存为空，那么Kademlia只是将过期信息打上标记，而不是立即清除，这就保证了节点出现短暂的网络故障时，不会完全清除其k桶

加速查询

另一个优化是用过增加路由表大小来减少查询的步数。从概念上讲，可以考虑每次使用b位ID而不是一位。和前面介绍一样，期望的步数是log2n。如果把路由表扩大到2^blog2^b n个k桶，我们可以减少步数到log2^b n

2.4小节较少了当Kademlia节点的k桶满且其区间包含了节点自己ID是，如何去分裂该k桶。然而，在实现中，也会把不包含节点自己ID的区间分裂成b-1层。比如，如果b=2，不包含节点ID的那一半会分类一次。如果b=3，会分裂两层，最多四个区间，以此类推。大致的分裂规则是，如果一个满的k桶包含了节点自身的ID或其在路由树中的深度d满足d=O(mod b)，就会被分裂，当前实现是b=5

虽然基于 XOR 的路由算法和 Pastry、 Tapestry以及 Plaxton 分布式搜素算法中第一阶段的路由算法很相似，但是当它们一般化到 b>1 时就都变得非常复杂。如果没有基于XOR的拓扑，就需要另外使用一个算法结构来从具有相同前缀但是后 b 位又不同的节点中找出目标节点。这三个算法采用了不同的方法来解决这个问题，各具缺点；除了大小为O(2^b log2^b n)的主路由表外，它们都需要一个大小为O(2^b)的二级路由表。这增加了启动和维护的成本，也使协议变得复杂，并且对于Pastry和Tapestry来说，也使得对其进行正确性和一致性方面的规范分析变得困难或不可能。有一个针对Plaxton的证明，但是该系统难以适应像 P2P 这样的高故障概率环境。

题图来自unsplash: https://unsplash.com/photos/phIFdC6lA4E