基于XOR度量的p2p信息系统

概要

我们描述了一个在易出错环境中具有可证明一致性和性能的点对点分布式哈希表。我们系统使用新的基于XOR的度量拓扑，它讲话了算法，方便了我们的证明。该拓扑具有这样的属性，每个信息交换都传达或者强化了有用的联系信息。系统利用这些信息发送并行，异步的查询消息，这些消息容忍节点故障，而不会对用户造成超时和延迟。

1 介绍

这个paper描述了Kademlia，一个p2p的分布式哈希表（DHT）Kademlia有许多良好的特性之前的DHT没有同时提供。它最小化了节点为了了解彼此发送消息的数量。配置信息最为键查找的副作用自动传播。节点有足够的知识和灵活性通过低延迟的路径路由请求。Kademlia使用了并行的，异步的查询以避免失败节点的时延。节点记录彼此存在的算法可以抵抗某些基本的拒绝服务攻击。最后，只需对节点在线时间分布做出较弱的假设，就可以形式化地证明 Kademlia 的几个重要性质（我们用现有的点对点系统测量来验证假设）。

Kademlia采用了许多DHT的基本方法。秘钥是不透明的160-bit位数量（对于大的数据使用SHA-1 哈希）。参与的计算机每台在160位秘钥空间中都有一个节点ID key，value对被存储在节点上和ID接近的节点上，以表示接近的概念。最后一个基于节点ID的路由算法允许任何人在给定的目标键附近定位服务器。

Kademlia的许多好处都来自于它使用了新颖的XOR度量来表示键空间和点的距离。XOR是对称的，允许Kademlia参与者接受来自其他路由表中包含完全相同的节点分布中接受查找查询。没有这个属性，类似Chord的系统，不会从收到的查询中学习有用的路由信息。更糟糕的是，不对称导致了路由表刚性。Chord节点的手指表中的每个条目必须在ID空间中存储某个间隔之前的精确节点。这个区间的任何节点都离它前面的节点太远。作为对比，Kademlia可以发送查询到间隔内的任何节点，它基于延迟选择路由，甚至可以并行发送，对几个相同的节点进行异步的查询。

为了定位接近特定ID的节点，Kademlia使用了单一路由算法从开始到结束。相反，其他系统使用一个算以得到接近目标ID，最后几跳用其他的算法。在现有系统中，Kademlia类似于pastry的第一阶段，其（虽然作者没有这样描述）通过Kademlia的XOR度量依次找到距离目标大约一半远的节点。然而在第二阶段，Pastry将距离度量切换为ID之间的数值差异。它还在复制中使用第二个数值差异度量。不行的是，第二个指标附近的节点可能离第一个指标很远，在特定节点ID处产生不连续，降低性能，并让最坏情况下的行为的形式化分析复杂化。

2 系统描述

我们的系统采用与其他DHT相同的方法我们提供160-位的不透明ID并提供查找算法，它可以依次定位节点到任何目标ID，在对数部之后收敛到查找的目标。

图1：Kademlia二叉树。黑色展示了节点的位置0011在树中。灰色的椭圆表示节点所在的子树0011必须有联系人。

Kademlia有效的对待节点，将其视为二叉树中的叶子，通过ID最短的唯一前缀，确定每个节点的位置。图1这展示了前缀0011为例子的树中，节点的位置。对于任何给定的节点，我们将二叉树切分为一系列的连续的不包含该节点的子树。最高的子树由不包含该节点的二叉树的一半组成下一个子树包含了剩余不包含该节点的子树的一半组成。等等。0011节点的例子中，子树被圈起来，分别由前缀为1、01 000和0010的所有节点组成。

Kademlia协议确保了每个节点最少知道每个子树中只少有一个节点，如果该子树包含一个节点。有了这种保证，任何节点都可以通过ID定位其他任何节点。图2展示了一个节点的例子0011，通过连续查询它所知道的最佳节点，在下层和下层子树中寻找寻找从而定位节点1110。最后查找收敛到目标节点。

图2：通过它的ID定位一个节点。通过迭代相近的节点进行学习，在这前缀0011找到1110。上面的线段表示160位的空间，并且展示了它如何查询收敛到目标节点。我们下面通过1110说明RPC消息。后续的RPC指向前一个RPC返回的节点。

本章节的其他部分会填充细节并且让查找算法更加具体。我们首先定义接近度的精确概念，允许我们谈论在距离键最近的k个节点上存储和查找键值对。我们之后给出查找协议，即便在没有节点与秘钥共享唯一前缀或者给定节点关联的某些子树为空的情况下，该协议也能正常工作。

2.1 节点度量

每个Kademlia节点有160位的节点ID。节点ID目前只是随机的160位标识符，虽然它们也可以像Chord那样被构造。每个节点传递包括节点ID在内的节点信息，如有必要允许收件人记录发件人的存在。

秘钥也是160位的标识符。将键值对给特定的节点，俩个标识符之间距离的概念。给定160位的标识符，x和y，Kademlia定义了它们之间的距离为位的异或解释为证整数，$d(x, y) = x \oplus y$。

三角属性也叫三角不等式。是数学中与距离（度量）相关的一个重要性质。它是度量空间的一个核心特征，用于描述三点间的距离关系。

我们首先记住，XOR是有效的尽管是非欧几里得度量。如果$x \neq y$那么$d\left( {x,x}\right) = 0,d\left( {x,y}\right) > 0$，并且$\forall x,y : d\left( {x,y}\right) = d\left( {y,x}\right)$。XOR也提供了三角形属性$d\left( {x,y}\right) + d\left( {y,z}\right) \geq d\left( {x,z}\right)$。三角属性遵循一个现实$d\left( {x,y}\right) \oplus d\left( {y,z}\right) = d\left( {x,z}\right)$并且$\forall a \geq 0,b \geq 0 : a + b \geq$ $a \oplus b$ .

接下来我们注意到XOR捕获了我们基于二叉树系统草图中隐含的距离概念。在完全填充160位的二叉树中，俩个ID的最大的距离包含它们最小树的高度。当一个树没有完全生长，到ID x最近的叶子是和ID有最长公共前缀的x。如果树上有空枝，可能有多个叶子具有最长的公共前缀。在这个例子中，翻转x中对于空分支的位，最接近x的叶子将会是离$\tilde x$最近的叶子。

类似Chord的顺时针圆圈度量一样，XOR是单向的（unidirectional）。对于任何给定的点x和距离$\Delta>0$,只有一个点y$d(x,y)=\Delta$​,单向保证了对于同一个密钥的所有查找沿着相同的路径，无论七点是什么。因此，沿着查找路径缓存键值对可以缓解热点。像Pastry和Chord不同，XOR拓扑也是对称的对于所有x和y$d(x,y)=d(y,x)$。

2.2 节点状态

K-Bucket 用一个 Bucket 来保存与当前节点距离在某个范围内的所有节点列表，比如 bucket0, bucket1, bucket2 ... bucketN 分别记录[1, 2), [2, 4), [4, 8), ... [2^i, 2^(i+1)) 范围内的节点列表

Kademlia节点存储了联系信息包含了每个其他路由查询信息。每一个$0\leq i <160$，每个节点都会保存一个(Ip地址，UDP端口，节点ID)元组，这些节点与当前节点的距离在$2^i和2^i+1$之间。我们可以叫这些列表k-bucket。每个节点按照最后一次出现的时间进行排序-最久未见的节点位于头部，最近被看到的节点在列表尾部。对于较小的i值，k-bucket通常为空（不存在合适的节点）。对于大的i值，列表的大小可以达到k，其中k是系统范围的复制参数。k是可以选择，因此任何给定的k个节点不太可能在一小时内发生故障(例如k=20)。

当Kademlia节点接收到任何来自其他节点 的信息（请求或者回复），它为发送方的节点ID更新响应的k-bucket。如果发送方节点已经存在于接受者的k-bucket中，接受者移动它到列表的末尾。如果节点不在适当的k中，并且bucket少于k个条目，那么接受者插入新的发送者到列表的尾部。然而，如果合适的k-bucket已经满了，那么接受者ping最久未见的节点以决定做什么。如果最久未见的节点没有反应，它被从k桶中驱逐，并将新的发送方插入尾部。否则，如果最久没见的节点相应了，则将其移动到队列的尾部，并丢弃丢弃新发送方的联系人。

Gnutella是一种去中心化的点对点（P2P）文件共享协议，最初由Justin Frankel和Tom Pepper在2000年开发。它允许用户直接相互连接并共享文件，而不需要依赖于集中式的服务器。Gnutella的工作原理基于节点之间的相互通信，每个节点都可以充当客户端和服务器的角色。

k-bucket有效的实现了最久未见的驱逐策略，除了存活的节点永远不会从列表中删除。这种对于老联系人的偏好是受Saroiu等人收集的Gnutella追踪数据进行分析。图3显示了Gnutella节点根据当前在线时长，在接下来的一个小时内继续在线的百分比。一个节点的启动时间越长，它就越可能再运行一个小时。通过保留最老的节点在边上，K-bucket最大化了节点保持离线状态的概率。

第二个k-bucket的好处是它们提供了对dos攻击的阻力。不能通过找到系统的新节点刷新节点的路由状态。Kademlia节点只会在老的节点离开的时候插入新的节点。

2.3 Kademlia协议

Kademlia协议包含了四种RPC：PING，STORE，FIND_NOTE，FIND_VALUE。PING RPC探测节点如果它在线的话。Store指示存储键值对以便之后检索。

FIND_NODE接受160位的ID作为参考。RPC的接受者为它已知的最接近目标ID的k个节点返回 （IP地址，UDP端口，Node ID）三元组。这些三元组可以来自单个k-bucket，如果最近的k-bucket没满的话也可以来自多个k-bucket。在任何情况下，RPC接收方必须返回k个项目（除非k桶的节点总数少于k个，在这个例子中他返回它知道的每一个节点）。

FIND_VALUE行为类似FIND_NODE-返回（IP地址，UDP端口，节点ID）元组，有一个例外。如果RPC接受者已经接受了STORE RPC已经接收到了对于键存储的值，它只返回存储的值。

在所有的RPC中，接受者必须回显一个160位的随机RPC ID，它提供了对于地址伪造的阻力。PING 也可以在RPC回复上附加，以便RPC接受者获得发送者网络地址的额外保证。

最重要的步骤是Kademlia的参与者必须执行就是，找出k个离给定节点ID最接近的节点。我们把这个过程叫做node lookup。Kademlia 使用递归算法进行node looup。查找启动器首先从离他最近的非空的k桶中挑选$\alpha$个节点（或者，如果bucket只有少于$\alpha$个条目，它只取所知道的离$\alpha$最近的节点 ），之后发起人发起并行一步的FIND_NODE RPC到$\alpha$个已经被选中的节点。$\alpha$是系统范围的一个参数，比如3。

在递归步骤中，发起人发送FIND_NODE到它习得的来自之前节点的RPC。（这个递归可以在之前所有$\alpha$个RPC已经返回的时候开始）。在发起者听说过的最接近目标的k个点中，它选择$\alpha$个还没有查询并且重新发送FIND_NODE RPC给他们。那些缓慢响应的节点从考虑中移除，除非他们确实响应。如果一轮查找节点未能返回比当前已知的节点更接近目标的节点，发起者重新发送FIND_NODE到所有，它还没有查询的，k个最接近的节点。当发起者已经从k个它能看到的最接近的节点已经查询并得到了响应查询就结束。当$\alpha=1$，查找算法在消息开销角度和探测故障的节点类似Chord，然而Kademlia可以低延迟的路由，因为它可以灵活的选择k个节点中的任何一个来转发请求。

大部分的操作的实现类似于上述的查找出过差。为了存储键值对，参与者定位k个离秘钥最近最近的节点，比去年给向他们发送STORE RPC。此外，每个节点重新发布键值对是必要的以维护它们的存活，之后会在2.5章中描述。这确保了⟨key，value⟩对以非常高的概率保持持久性（正如我们在证明草图中所示）。对于Kademlia的当前应用（文件共享），我们也需要原键值对的原发布者每24小时重新发布它。此外键值对在发布之后的24小时到期，以便限制系统中陈旧的索引信息。对于其他的应用，比如数字证书或者密码学散列到值的映射，延迟过期时间可能是最合适的。

为了找到键值对，一个节点通过执行查询以开始寻找ID最接近的key的k个节点。然而值查找使用FIND_VALUE而不是FIND_NODE RPC。此外，当节点返回了值，过程立刻停止。处于缓存目的，一旦查找成功，请求节点奖键值对存储在它观察到的最接近没有返回值键的节点上。

因为单项的拓扑，之后查询相同的键的搜索可能会在查询最接近的节点之前碰到缓存项。对于某个键特别受欢迎的时候，系统可能最终会在多个节点缓存它。我们在任何节点的数据库中使⟨key，value⟩对的过期时间与当前节点和ID最接近密钥的节点之间的节点数量成指数反比。虽然简单的LRU逐出会导致类似的生命周期分布，但它不是自然选择缓存大小的方式，因为节点没有系统将会存储多少值的先验知识。

Bucket通常通过请求传输的流量穿过节点来保持刷新。为了处理特殊情况如某个特定ID范围内没有进行查询操作，每个节点重新刷新它没有在过去一小时内刷新的所有的bucket。刷新意味着在桶的范围内选择一个随机ID并且对于哪个ID执行节点查询。

为了加入网络，一个节点u必须联系已经加入参与的节点w。u插入w到合适的k-bucket桶中，u然后对于它拥有的节点ID执行节点查询。最终，u重新刷新比它最近邻居远的所有k个桶。在刷新期间，u既填充自己的k-bucket，有根据需要插入到其他节点的k-bucket。

2.4 路由表

根据给定协议，Kademlia的路由表结构相当直接，尽管一个轻微的差别是必须的以处理高度不平衡的树。路由表是二叉树，叶子是k-bucket。每个k-bucket包含有ID共同的前缀。前缀是k-bucket在二叉树中的位置。因此每个k-bucket覆盖ID空间的一定范围，k-bucket一起覆盖了整个160位ID空间，没有重叠。

图4：路由表随着时间的改变。开始的时候一个节点只有一个k-bucket，如顶部所示。随着k-bucket满了，覆盖节点ID的桶被重复分成俩个桶。

节点在路由树中是根据需要动态分配的。图4展示了过程。开始的时候，节点u的路由树只有一个节点-一个k-bucket覆盖了整个ID空间。当u得知一个新的联系人，它企图插入合适的联系人到k桶中。如果这个桶没有满，新的联系人被简单的插入。否则，如果k-bucket的范围包含了u有的节点ID，那么bucket被切分为俩个新的bucket。旧的内容被分成了俩部分，重复插入尝试。如果k-bucket和不同的范围满了，新的联系人被简单的删除。

在高度不平衡的树中出现了一个复杂问题。假设节点u加入系统，并且是唯一一个ID是000开头的节点。进一步假设系统已经有超过k个前缀为001的节点。每个前缀为001的节点有一个空的k桶，u应该被插入其中，然后u的桶的刷新只会通知k个节点。为了避免这个问题，Kademlia节点奖所有有效的联系人只少保存在k个节点的子树中，即使这需要分割不包含自身ID的桶。图5展示了这个额外的分割。当u刷新分割桶时，所有001的前缀的节点将会知道。

图5：此图例说明了节点 ID 为 00...00 的松散路由表。松散的表可能很小（期望是常数尺寸）的不规则性，以确保它知道结点周围最小子树中至少有k个结点的所有结点。

2.5 有效的key重发布

为了确保键值对的持久性，节点必须定期的发布键。此外俩个现象可能会导致对于有效的键的查找失败。首先在发布时获得键值对的k个节点中的一些可能会离开网络。其次，新的节点可能会加入网络，其id更接近于某个已发布的秘钥（比最初是发布键值对的节点接近）。在这俩个例子中，具有键值对的节点必须重新发布它，因此再一次确保在k个最接近key的节点上是可用的。

为了补偿节点离开网络，Kademlia重新发布每个键值对每小时。一个这个策略的简答实现需要许多信息-存储键值对多达k个节点中的每一个都会执行节点查找然后每小时存储k-1个PRC。幸运的是重发布程序可以进行极大的优化。首先当节点接收到给定键值对的STORE RPC时1，它假设RPC发布了其他k-1个最近的节点，因此接受者不会在下一个小时重新发布键值对。这确保了只要重新发布的间隔不是准确同步的，每个小时只有一个节点将会重发布给定的键值对。

第二个优化避免了执行节点在重发布之前进行查找。如同2.4章中描述的，为了处理不平衡的树，节点根据需要切分k-bucket以确保它们完全了解周围只少有k个节点的子树。如果在重新发布键值对之前，节点u刷新了所有这个k个节点的子树中的k-bucket，它会自动的计算出第k个最近的节点到给定的key。这些bucket重刷新可以平摊在许多键的重新发布上。

为了看到为什么节点查询必须要在u刷新了大于等于k个大小钟bucket之后，必须要考虑俩中情况。如果重新发布的key在子树的ID范围内，那么因为子树的大小最少为k，并且u已经对子树有完全的了解，显然u必须知道离键最近的k个节点。如果键在子树之外但是u是最接近k个节点之一，它必须遵循u的k个桶，对于距离比子树更接近的间隔，它们都少于k个元素，因此u将会知道所有在这个k-bucket的节点，在加上子树的知识将会包括k个最接近key的节点。

当一个新节点加入系统时，它必须存储它是 k 个最近节点之一的所有键值对。现有的节点通过类似地利用周围子树完整的知识，现有节点将会知道新节点应该存储哪些键值对。因此任何节点学习新的节点都会发出STORE RPC以以变换相关的键值对到新的节点。以避免冗余的STORE RPC，然而只有拥有的ID是比其他节点的ID更接近key的时候，节点才会传输键值对。

3 证据概要

4 实现注意

在这个章节，我们描述了俩个重要的我们用来提升Kademlia性能的技术实现。

4.1 优化联系人统计

k-bucket基础的渴求的特性是提供LRU检查和逐出无用的联系人而不需要丢失任何有效的联系人。如2.2章中描述的，如果k-bucket满了，它需要每次从捅范围内的位置节点接受消息时发送PING RPC。PING 检查k桶中最少使用的联系人是否有效。如果不是，新的替换旧的。不幸的是，上述的算法需要大量的网络信息来处理这些PING。

为了减少流量，Kademlia延迟了探测联系人直到有用的信息可以发送给它们。当Kademlia节点接收到未知联系人的RPC并且这个联系人的k-bucket已经存满了k个条目，节点将新联系人放置在符合条件的节点的替换缓存中以替换不新鲜的k-bucket条目。下一个时间节点查询在k-bucket中的联系人，任何一个没有反应的条目可以被逐出并且替换成替换缓存中的条目。替换缓存通过最后看到的时间进行排序，最近看到的条目有更高的优先级作为替换的候选人。

一个相关的问题是因为Kademlia使用了UDP，当网络包丢失的时候有效的联系人可能无法响应。因此包的丢失可能代表着网络拥塞，由于数据包丢失通常表示网络拥堵，Kademlia 会锁定未响应的联系人，并避免在一个指数增长的退避时间间隔内向它们发送任何进一步的 RPC。因为大部分的策略Kademlia查询只需要听到k节点中的一个，系统通常不会将丢弃的RPC重传同一节点。当一个联系人联系五次RPC响应失败时，它被认为过期了。如果k-bucket没有满或者替换缓存是空的，kademlia仅仅是标记了联系人过期而不是移出它们。这可以确保，如果一个节点自己的网络连接暂时中断，该节点不会完全清空它所有的k-bucket。

4.2 加速查找

另一个在实现里的优化是通过增加路由表的大小，每次查找实现更少的跳动。概念上，这是通过考虑b位ID而不是只考虑1位ID实现。如之前描述的，如之前描述的，每次查找期望的跳数为$log_2n$。通过增加路由表的大小变成了期望$2^blog_{2^b}n$

章节2.4描述了kademlia节点如何切分k-bucket，当bucket满了并且范围包含了自己的节点ID。然而实现中也切分了不包含节点的ID范围，最高可达b-1级。例如如果b=2，不包含节点ID的ID空间的一半被分割一次（到俩个范围）；如果b=3，他会在俩个级别上被最多分成四个范围等。一个常规的切分规则是，如果桶的范围包含了节点有的ID或者该k-bucket在路由树中的深度d满足d不为0（模b），则节点会分割一个完整的k-bucket。（深度只是k-bcket范围中所有节点共享的前缀长度。）当前的实现使用b=5。

尽管基于XOR路由算法的第一阶段类似于Pastry，Tapestry和Plaxton的分布式查询寻算法，当b>1的时候这三个算法都变得复杂难以处理。没有XOR拓扑，它们需要额外的算法接口以发现共享相同前缀但下一个b位数字不同的节点中的目标。这三个算法使用不用的方法解决这个问题，每个都有自己的缺陷；它们都需要大小为$O(2^b)$的耳机路由表加上一个大小为$O(2^blog_{2^b}n)$的主表。这增加了启动器和维护的成本使协议复杂化，Pastry和Tapestry使对正确性和一致性的形式化分析复杂化或阻止了形式化分析。Plaxton有证据，但系统不太适合对等网络这样高度容易出错的网络。

总结

伴随着新颖的基于XOR指标的拓扑，Kademlia是第一个p2p系统结合了可证明的一致性和性能，延迟最小化路由，以及对称的单项拓扑。Kademlia进一步引入了并发参数$\alpha$，这让人们可以用一个贷款上的常熟因子作为代价，换取异步的最低延迟跳数选择和无延迟的故障恢复。最后，Kademlia是第一个利用节点故障与正常运行时间成反比这一事实的点对点系统。