1. 首页
  2. 文档
  3. 白皮书
  4. Kademlia:基于异或度量的点对点信息系统

Kademlia:基于异或度量的点对点信息系统

作者:Petar Maymounkov; David Mazieres
翻译:IPFS点滴资讯

摘要:我们将描述一个点对点分布式哈希表,在容易出错的环境中仍具有可证的一致性和性能。我们的系统使用一种新的基于异或运算的度量拓扑来进行路由查询和节点定位,可以简化算法和简便我们的证明。拓扑有一种属性,即每次交换的消息都传递或强化有用的联系信息。系统利用这些信息发送并行的异步查询消息,可以容忍节点故障,而不会对用户造成超时延迟。

1 介绍

本文介绍了点对点分布式哈希表(DHT)——Kademlia。Kademlia有许多以前的DHT表无法同时提供的理想特性。它最小化了节点为了彼此识别而必须发送的配置信息的数量。配置信息作为键查找的附带信息自动传播。节点有足够的知识和灵活性来通过低延迟路径进行路由查询。Kademlia使用并行、异步的查询来避免故障节点的超时延迟。节点之间记录彼此存在的算法可以抵抗一些基本的拒绝服务攻击。最后,通过在正常运行时间分布上的弱假设可以正式证明Kademlia几个重要属性(我们通过对于现有点对点系统的测量验证的假设)。

Kademlia采用了许多DHT的基本方法。键是不透明的,160位数值(例如某些较大数据的SHA-1散列)。每台参与的计算机在160位键空间中都有一个节点ID。<key,value>键值对存储在ID在某种接近度上“接近”该键的节点上。最后,基于节点ID的路由算法允许任何人有效地定位任何给定目标键附近的服务器。

Kademlia的许多优点源于它对键空间中各点之间的距离使用了新的异或度量。 异或是对称的,允许Kademlia参与者从其路由表中包含的精确相同的节点分布接收查询请求。如果没有这个属性,Chord [5]等系统就不会从它们收到的查询中得到有用的路由信息。更糟糕的是,不对称会导致严格的路由表。Chord节点的指针表中的每个条目,必须在ID空间中的某个间隔之前存储精确节点。实际上在该时间间隔内的任何节点都会在同一时间间隔内与其前面的节点相距太远。相比之下,Kademlia可以向一个时间间隔内的任何节点发送查询,允许它根据延迟选择路由,甚至可以向几个同样适当的节点发送并行异步查询。

为了定位特定ID附近的节点,Kademlia从头到尾使用单个路由算法。相比之下,其他系统使用一种算法来接近目标ID,并在最后几次跳跃中使用另一种算法。在现有的系统中,Kademlia最类似于Pastry[1]的第一阶段,通过Kademlia的异或度量,该阶段(尽管作者没有以这种方式描述)连续地发现距离目标ID大约一半远的节点。然而,在第二个阶段,Pastry将距离度量转换为ID之间的数值差异。它还在复制中使用第二个数值差异度量。不幸的是,第二种情况附近的节点在第一种情况下可能非常远,在特定的节点ID值处产生不连续性,从而降低了性能,并使对最坏情况的行为的正式分析的尝试复杂化。

 

2 系统描述

我们的系统采用与其他DHT相同的通用方法。我们为节点分配160位不透明ID,并提供一种查找算法,该算法将“更近”的节点连续定位到任何所需的ID,以对数步收敛到查找目标。

Kademlia有效地将节点视为二叉树中的叶子,每个节点的位置由其ID的最短唯一前缀确定。图1显示了示例树中具有唯一前缀0011的节点的位置。对于任何给定节点,我们将二叉树划分为一系列不包含节点的连续较低子树。最高子树由不包含节点的二叉树的一半组成。下一个子树由不包含节点的剩余树的一半组成,以此类推。在节点0011的示例中,子树被圈出并且分别由具有前缀1,01,000和0010的所有节点组成。

如果该子树包含节点,则Kademlia协议确保每个节点知道其每个子树中的至少一个节点。有了这个保证,任何节点都可以通过其ID找到任何其他节点。图2示出了节点0011定位节点1110的示​​例,其通过连续查询它知道的最佳节点来寻找下级和下级子树中的联系人;最后,查找收敛到目标节点。

本节的剩余部分补充了细节,使查找算法更加具体。我们首先定义ID接近度的精确概念,来表示在第k个最接近键的节点上存储和查找<key,value>对。然后,我们给出一个查找协议,即使在没有节点与键共享唯一前缀或者与给定节点关联的一些子树为空的情况下也能工作。

Kademlia:基于异或度量的点对点信息系统

图1:Kademlia二叉树。黑点表示节点0011…在树中的位置。灰色椭圆表示子树,在其中节点0011…必然有一个联系人。

 

Kademlia:基于异或度量的点对点信息系统

图2:通过ID查找节点。这里,具有前缀0011的节点通过连续得知并查询更近和更近的节点来找到具有前缀1110的节点。顶部的线段表示160位ID的空间,并显示查找如何收敛到目标节点。下部我们说明了1110所做的RPC消息。第一个RPC是节点101,已知为1110。后续RPC是前一个RPC返回的节点。

 

2.1 异或度量

每个Kademlia节点都有一个160位的节点ID。节点ID当前只是随机的160位标识符,尽管它们同样可以像在Chord中那样构造。节点发送的每条消息都包含其节点ID,允许接收方在必要时记录发送方的存在。

键也是160位标识符。为了将<key,value>对分配给特定节点,Kademlia依赖于两个标识符之间的距离概念。给定两个160位标识符x和y,Kademlia将它们之间的距离定义为按位异或(XOR)解释为整数,d(x,y)= x⊕y。

我们首先注意到XOR是有效的,尽管是非欧几里德度量。很明显,如果x≠y,则d(x,x)=0,d(x,y)>0,并且∀x,y:d(x,y)=d(y,x)。XOR还具有三角形属性:d(x,y)+d(y,z)≥d(x,z)。三角形属性遵循如下事实:d(x,y)⊕d(y,z)=d(x,z),对于∀a≥0, b≥0 : a+ b≥a⊕b。

接下来我们注意到XOR捕获了系统中基于二叉树的草图中隐含的距离概念。在160位ID的完全填充的二叉树中,两个ID之间的距离的大小是包含它们的最小子树的高度。当树未完全填充时,与ID 最接近的叶是其ID与x共享了最长公共前缀的叶。如果树中有空分支,则可能与多个叶子都具有最长的公共前缀。在这种情况下,与最接近的叶子将是与ID 最接近的叶子,通过翻转对应于树的空分支的x中的位而产生。

与Chord的顺时针圆度量一样,XOR是单向的。对于任何给定点x和距离> 0,恰好有一个点y使得d(x,y)= Δ 。单向性确保相同键的所有查找沿着相同路径会聚,而不管始发节点如何。因此,沿着查找路径缓存<key,value>对能够减缓热点。与Pastry一样,与Chord不同,XOR拓扑也是对称的(对于所有x和y,d(x,y)= d(y,x))。

 

2.2 节点状态

Kademlia节点存储关于彼此的联系信息以路由查询消息。 对于每个0≤ i <160,每个节点为离它距离在2i和2i+1之间的节点保留<IP地址,UDP端口,节点ID>三元组的列表。我们将这些列表称为k-buckets。每个k-bucket都按照上次看到的时间进行排序 – 最不最近看到的节点在头部,最最近看到的节点在尾部。对于小的值,k-buckets通常是空的(因为不存在适当的节点)。对于大的值,列表可以增长到大小为k,其中k是系统范围的复制参数。k的选择使得任何给定的k个节点在一小时内不太可能彼此失联(例如k = 20)。

Kademlia:基于异或度量的点对点信息系统

图3:下一小时保持在线的概率关于运行时间的函数。x轴表示分钟。y轴表示在线保持至少x分钟的节点,同时也保持了在线至少x+60分钟的比例。

当Kademlia节点从另一个节点收到任何消息(请求或回复)时,它会根据发送方节点ID更新的相应k-bucket。如果发送节点已经存在于收件人的k-bucket中,则收件人将其移动到列表的尾部。如果节点尚未位于相应的k-bucket中且存储桶的条目少于k个,则接收方只需将新发送方插入列表的尾部即可。但是,如果适当的k-bucket已满,则接收方会ping k-bucket最近最少见的节点以决定要执行的操作。如果最近最少看到的节点无法响应,则将其从k-bucket中逐出,并将新发送方插入尾部。否则,如果最近最少看到的节点响应了,则将其移动到列表的尾部,并丢弃新发送者联系人。

k-buckets有效地实现了最不-最近看到的驱逐策略,只是活动节点从未从列表中删除。我们对Saroiu等人收集的Gnutella痕迹数据的分析驱动了对旧接触者的这种偏好〔4〕。图3显示了Gnutella节点作为当前正常运行时间的函数而保持在线一小时的百分比。节点越长,就越有可能再保持一个小时。通过保持最老的活动联系人,k-bucket最大化了它们包含的节点保持在线的可能性。

k-buckets的第二个好处是它们可以抵御某些DoS攻击。无法通过使用新节点涌入系统来刷新节点的路由状态。只有当旧节点离开系统时,Kademli节点才会在k-buckets中插入新节点。

 

2.3 Kademlia协议

Kademlia协议由四个RPC组成:PING,STORE,FIND_NODE和FIND_VALUE。 PING RPC探测节点以查看它是否在线。STORE指示节点存储<Key,Value>对以供以后检索。

FIND_NODE将160位ID作为参数。RPC的接收方为它知道最接近目标ID的k个节点返回<IP地址,UDP端口,节点ID>三元组。 这些三元组可以来自单个k-bucket,或者如果最近的k-bucket未满,它们可能来自多个k-bucket。 在任何情况下,RPC接收者必须返回k个项目(除非所有k-buckets中的节点总数少于k个,在这种情况下它返回它知道的每个节点)。

FIND_VALUE的行为类似于FIND_NODE-返回<IP地址,UDP端口,节点ID>三元组 – 只有一个例外。如果RPC收件人已收到键的STORE RPC,则它只返回存储的值。

在所有RPC中,收件人必须回显160位随机RPC ID,这会对伪造地址提供一些阻力。PINGS还可以在RPC回复中为RPC收件人提供支持,以获得发件人网络地址的额外保证。

Kademlia参与者必须执行的最重要的过程是定位到距离某个给定的节点ID的最近的k个节点。我们将此过程称为节点查找。Kademlia采用递归算法进行节点查找。查找启动器首先从最近的非空k-bucket中挑选节点(或者,如果该桶少于α个条目,它只需要它知道的最近的α个节点)。然后,启动器将并行的异步FIND_NODE RPC发送到它选择的α个节点。α是系统范围的并发参数,例如3。

在递归步骤中,启动器将FIND_NODE重新发送到它从先前的RPC中得知到的节点。(此递归可以在所有先前的RPC返回之前开始)。在发起者所知最接近目标的k个节点中,它选择了一个尚未查询的节点,并将FIND_NODE RPC重新发送给它们1。无法快速响应的节点将被排除在考虑之外,除非他们做出响应。如果一轮FIND_NODE未能返回比已经看到的最近的节点更近的节点,则发起者将FIND_NODE重新发送到它尚未查询的所有k个最近的节点。当查询者查询并从它看到的k个最近的节点获得响应时,查找终止。当α=1时,查找算法在消息成本和检测失败节点的延迟方面类似于Chord。 但是,Kademlia可以降低延迟,因为它可以灵活地选择任何一个k节点来转发请求。

大多数操作都是根据上述查找过程实现的。为了存储<key,value>对,参与者将k个最近的节点定位到键并向它们发送STORE RPC。此外,每个节点都会根据需要重新发布<key,value>对以使它们保持活动状态,如第2.5节中所述。这以很高的概率确保了<key,value>对的持久性(正如我们在证明示意图中所示)。 对于Kademlia当前的应用程序(文件共享),我们还要求<key,value>对的原始发布者每24小时重新发布一次。否则,<key,value>对在发布后24小时到期,以限制陈旧索引系统中的信息。对于其他应用程序,例如数字证书或加密散列到值映射,更长的到期时间可能更适当。

为了找到<key,value>对,节点首先执行查找以找到ID最接近键的k个节点。但是,值查找使用FIND_VALUE而不是FIND_NODE RPC。此外,当任何节点返回值时,该过程立即停止。出于缓存目的,一旦查找成功,请求节点将<key,value>对存储在它观察到的最接近的节点上,该节点不返回该值。

由于拓扑的单向性,在查询最近的节点之前,将来搜索相同键可能会触发缓存的条目。在某个键的高流行度期间,系统可能最终在许多节点上缓存它。为了避免“过度缓存”,我们使任何节点数据库中的<key,value>对的到期时间与当前节点与ID最接近键的ID的节点之间的节点数成指数反比2。虽然简单的LRU驱逐会导致类似的生命周期分布,但是没有自然的方法来选择缓存大小,因为节点没有系统将存储多少值的先验知识。

桶通常由通过节点的请求流量保持新鲜。为了处理特定ID范围内没有查询的病态情况,每个节点刷新在过去一小时内未执行节点查询的任何存储桶。刷新意味着在桶的范围内选择随机ID并执行该ID的节点搜索。

要加入网络,节点u必须与已经参与的节点w有联系。u将w插入适当的k-bucket。然后,u对自己的节点ID执行节点查找。最后,u刷新比其最近邻居更远的所有k-bucket。在刷新期间,u都会填充它自己的k-bucket,并在必要时将其自身插入其他节点的k-bucket。

 

2.4 路由表

考虑到协议,Kademlia的基本路由表结构相当简单,但处理高度不平衡的树需要一些微妙的处理。路由表是二叉树,其叶子是k-buckets。每个k-bucket包含具有其ID的共同前缀的节点。前缀是k-bucket在二叉树中的位置。因此,每个k-bucket覆盖ID空间的某个范围,并且k-bucket一起覆盖整个160位ID空间而没有重叠。

根据需要,路由树中的节点是动态分配的。图4说明了该过程。最初,节点u的路由树具有单个节点,一个k桶覆盖整个ID空间。当您获悉新联系人时,它会尝试将联系人插入适当的k-bucket中。如果该存储桶未满,则只需插入新的联系人。否则,如果k-bucket的范围包括u自己的节点ID,则将桶分成两个新桶,旧内容在两者之间划分,并重复插入尝试。如果具有不同范围的k-bucket已满,则单纯地删除新联系人。

Kademlia:基于异或度量的点对点信息系统

图4:路由表随时间的演变。最初,节点具有单个k-bucket,如顶部路由表中所示。当k-buckets填充时,其范围覆盖节点ID的桶重复分成两个k桶。

高度不平衡的树木出现了一个复杂问题。假设节点u加入系统并且是ID开始为000的唯一节点。进一步假设系统已经有多于k个前缀为001的节点。每个前缀为001的节点都有一个空的k-bucket,u应插入其中,但是你的桶刷新只会通知k个节点。为了避免这个问题,Kademlia节点将所有有效联系人保留在大小至少为k个节点的子树中,即使这需要拆分节点自己的ID不驻留的桶。图5说明了这些额外的拆分。当您刷新拆分桶时,前缀为001的所有节点都将得知它。

Kademlia:基于异或度量的点对点信息系统

图5:该图举例说明了ID为00…00的节点的松弛路由表。松弛表在其分支中可能具有小(预期的恒定大小)不规则性,以便确保它知道节点周围最小子树中至少具有k个联系人的所有联系人。

 

2.5 高效键的重新发布

为了确保键值对的持久性,节点必须周期性地重新发布键。否则,两种现象可能会导致有效键查找的失败。首先,当键值对发布时,最初获得键值对的k个节点中的一些可能离开网络。第二,新节点可以比最初发布键值对的节点更接近某些已发布键的ID来加入网络。在这两种情况下,具有键值对的节点必须重新发布它,以便再次确保它在最接近键的k个节点上可用。

为了补偿离开网络的节点,Kademlia每小时重新发布一次键值对。该策略的幼稚实现将需要许多消息——存储键值对的每个k个节点都将执行节点查找,然后每小时执行k-1个STORE RPC。幸运的是,重新发布过程可以大大优化。首先,当节点收到给定键值对的STORE RPC时,它假定RPC也被发送到其他k-1个最近的节点,因此接收者不会在下一个小时重新发布键值对。这可确保只要重新发布间隔未完全同步,每小时只有一个节点将重新发布给定的键值对。

第二个优化避免在重新发布键之前执行节点查找。如2.4节所述,为了处理不平衡树,节点根据需要拆分k个桶以确保它们完全了解具有至少k个节点的周围子树。如果在重新发布键值对之前,节点u刷新k个节点的子树中的所有k-buckets,它将自动能够找出给定键的k个最近节点。这些桶刷新可以通过重新发布许多键来摊销。

要了解在刷新size ≥ k的子树中的桶后不需要节点查找的原因,有必要考虑两种情况。如果重新发布的键落在子树的ID范围内,那么由于子树的大小至少为k并且u完全了解子树,所以显然你必须知道与键最近的k个节点。另一方面,如果键位于子树之外,但是u是键最近的k个节点之一,它必须遵循u的k-buckets,使得距离键更近的区间比所有少于k个条目的子树。因此,您将知道这些k-buckets中的所有节点,这些节点连同子树的知识将包括与键最接近的k个节点。

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

 

3 证明草图

为了证明我们系统的正确功能,我们需要证明对于某些小常数c,大多数操作需要[log n]+c时间,而<key,value>查找返回系统中存储的键具有压倒性概率。

我们从一些定义开始。对于覆盖距离范围[2i,2i+1]的k-bucket,将桶的索引定义为i。将节点的深度h定义为160-i,其中i是非空桶的最小索引。在节点x中定义节点y的桶高度作为桶的索引,其中x将向其中插入y减去x的最低有效空桶的索引。由于节点ID是随机选择的,因此高度不均匀的分布是不可能的。因此,对于具有n个节点的系统,以压倒性的概率,任何给定节点的高度都将在log n的常数范围内。此外,最近节点与第k个最近节点中的ID的桶高度可能在log k的常数内。

我们的下一步是假设每个节点的每个k-bucket包含至少一个联系人的不变量,如果节点存在于适当的范围内。根据这个假设,我们表明节点查找过程是正确的并且需要对数时间。假设到目标ID的最近节点具有深度h。如果此节点的最重要的k-buckets都不为空,则查找过程将在每个步骤中找到一半接近(或者更确切地说其距离缩短一点)的节点,从而以h-log k步长调高节点。如果节点的一个k-bucket是空的,则可能是目标节点位于空桶的范围内的情况。在这种情况下,最后的步骤不会将距离减半。但是,搜索将完全按照与空桶相对应的键中的位被翻转的方式进行。因此,查找算法将始终以h-log k步骤返回最近的节点。此外,一旦找到最近的节点,并发性从切换到k。找到剩余的k-1个最近节点的步骤数不能超过第k个最近节点中最近节点的桶高,这不大于常数加log k。

为了证明不变量的正确性,首先考虑不变量如果成立,桶刷新的影响。刷新后,存储桶将包含k个有效节点,或者如果存在少于k,则包含其范围内的每个节点。(这取决于节点查找过程的正确性。)连接的新节点也将插入任何未满的桶中。因此,违反不变量的唯一方法是在特定桶的范围内存在k+1或更多个节点,并且对于实际包含在桶中的k全部失效而没有中间查找或刷新。然而,k是精确地被选择出来的,要求在一小时内(最大刷新时间)同时失效的概率非常小。

实际上,失效的概率远小于k个节点在一小时内离开的概率,因为每个传入或传出请求都会更新节点的桶。这是由异或度量的对称性产生的,因为在传入或传出请求期间给定节点与之通信的节点的ID与节点的桶范围的分布完全兼容。

此外,即使单个节点中的单个存储桶的不变量确实失效,这也只会影响运行时间(通过向某些查找添加跳转),而不会影响节点查找的正确性。对于查找失败,查找路径上的k个节点必须在同一个桶中丢失k个节点,而不进行中间查找或刷新。如果不同节点的桶没有重叠,则发生概率为2-k^2。否则,出现在多个其他节点的桶中的节点可能具有更长的正常运行时间,从而降低了失败的可能性。

现在我们考虑一个<key,value>对的恢复。当发布<key,value>对时,它将填充在最靠近键的k个节点上。它也每小时重新发布一次。因为即使新节点(最不可靠)具有持续一小时的概率1/2,在一小时之后,<key,value>对仍将出现在最靠近该键的k个节点之一上,概率为1–2-k。这个属性不会因为插入接近键的新节点而违反,因为只要插入这些节点,它们就会联系最近的节点以填充它们的桶,从而接收它们应存储的任何附近的<key,value>对。当然,如果键的k个最近节点发生故障并且<key,value>对尚未在其他地方缓存,则Kademlia将无法存储该对,因此会丢失该键。

 

4实施说明

在本节中,我们描述用于改进Kademlia实现的性能的两个重要技术。

 

4.1 优化联系人计算

k-buckets的基本所需属性是提供LRU检查和驱逐无效联系人,而不丢弃任何有效的联系人。如2.2节所述,如果k-bucket已满,则每次从桶的范围内的未知节点收到消息时,都需要发送PING RPC。 PING检查k-bucket中最近最少使用的联系人是否仍然有效。如果不是,则新联系人将替换旧联系人。不幸的是,如上所述的算法将需要大量的网络消息用于这些PINGS。

为了减少流量,Kademlia推迟了联系人的探测,直到有合适的方法发送联系人为止。当Kademlia节点从未知联系人接收到RPC,并且该联系人的k-bucket已经满了k个条目时,该节点将新联系人放入有资格替换陈旧的k-bucket条目的节点的替换缓存中。下次节点查询k-bucket中的联系人时,可以删除任何无响应联系人,并用替换缓存中的条目替换它们。替换缓存按照上次看到的时间进行排序,最近看到的条目作为替换候选具有最高的优先级。

一个相关的问题是,因为Kademlia使用UDP,所以当网络数据包被丢弃时,有效的联系人有时会无法响应。由于数据包丢失通常表明网络拥塞,Kademlia会锁定无响应的联系人,并避免向其发送任何进一步的RPC,以获得指数增加的回退间隔。因为在大多数阶段Kademlia的查找只需要听取k个节点中的一个节点,所以系统通常不会将丢弃的RPC重新传输到同一节点

当联系人连续无法响应5个RPC时,它被认为是陈旧的。如果k-bucket未满或其替换缓存为空,则Kademlia仅标记陈旧的联系人而不是删除它们。 除其他外,这确保了如果节点自己的网络连接暂时中断,则该节点将不会完全使其所有k-bucket无效。

 

4.2 加速查找

实现中的另一个优化是通过增加路由表大小来实现每次查找的跳转更少。从概念上讲,这是通过一次考虑ID 的b位来完成的,而不是一次只考虑一个位。如前所述,每次查找的预期跳数是log2n。通过将路由表的大小增加到预期2blog2^bn的个k-buckets,我们可以将要记录的预期跳转数减少到log2^bn。

2.4节描述了Kademlia节点在存储桶已满并且其范围包含节点自己的ID时如何拆分k-bucket。但是,该实现还会将不包含节点ID的范围拆分为b-1级别。 例如,如果b = 2,则不包含节点ID的ID空间的一半被分割一次(分成两个范围);如果b=3,则将其分为两个级别,最多分为四个范围等。一般的拆分规则是,如果桶的范围包含节点自己的ID或路由树中的k-bucket的深度d满足d恒不等于0(mod b),则节点会拆分一个完整的k-bucket。(深度只是k-bucket范围内所有节点共享的前缀长度。)当前实现使用b = 5。

虽然基于XOR的路由类似于Pastry [1],Tapestry [2]和Plaxton的分布式搜索算法[3]的第一阶段路由算法,但是当推广到b> 1时,所有三个都变得更加复杂。没有异或拓扑,就有需要额外的算法结构来发现节点内的目标,这些节点共享相同的前缀但在下一个b位数字上不同。所有这三种算法都以不同的方式解决了这个问题,每个都有其自身的缺点;除了大小为O(2blog2^bn)的主表之外,它们都需要大小为O(2b)的辅助路由表。这增加了引导和维护的成本,使协议复杂化,并且Pastry和Tapestry使正确性和一致性的正式分析复杂化或无法进行。Plaxton有证明,但是该系统不太适合于高度易出错的环境,比如点对点网络。

5 总结

凭借其新颖的基于异或的度量拓扑,Kademlia是第一个将可证明的一致性和性能,延迟最小化路由和对称单向拓扑结合在一起的点对点系统。Kademlia还介绍了一个并发参数α,它允许人们在带宽中交换常数因子,以实现异步最低延迟跳跃选择和无延迟故障恢复。最后,Kademlia是第一个利用节点故障与正常运行时间成反比关系这一事实的点对点系统。

1可以使用往返时间估计来增加桶条目和FIND答复,以用于选择节点。

2此数字可以从当前节点的存储桶结构推断出来

 

参考文献:

  1. A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. Accepted for Middleware, 2001, 2001. http:/ /research.microsoft .com/-antr/pastry/.
  2. Ben Y. Zhao, John Kubiatowicz, and Anthony Joseph. Tapestry: an infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/ CSD-01- 1141, U.C. Berkeley, April 2001.
  3. Andrea W. Richa C. Greg Plaxton, Rajmohan Rajaraman. Accessing nearby copies of replicated objects in a distributed environment. In Proceedings of the ACM SPAA, pages 311- 320, June 1997.
  4. Stefan Saroiu, P. Krishna Gummadi and Steven D. Gribble. A Measurement Study of Peer-to-Peer File Sharing Systems. Technical Report UW-CSE-01-06-02, Univer­ sity of Washington, Department of Computer Science and Engineering, July 2001.
  5. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrish­ nan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of the ACM SIGCOMM ‘ 01 Conference, San Diego, California, August 2001.
这篇文章对你有帮助吗?

How can we help?