Kademlia P2P协议：一种设计规范

Kademlia是用于对等网络的通信协议。它是分布式哈希表(DHT)的众多版本之一。

Kademlia网络的特征是三个常数，我们称之为α、B和k。第一个和最后一个是标准项。引入第二个密钥是因为某些Kademlia实现使用不同的密钥长度。

Alpha是一个小数字，表示网络调用的并行度，通常为3。

B是用于标识节点以及存储和检索数据的密钥的位大小；在Basic Kademlia中，这是160，即SHA1摘要(散列)的长度。

K是存储在存储桶中的最大联系人数；通常为20。

还可以方便地介绍几个在最初的Kademlia论文中找不到的其他常数。

TExpire=86400s，键/值对过期的时间；这是从原始发布日期算起的生存时间(TTL。

TReplicate=3600s，当节点需要发布其整个数据库时，Kademlia复制事件之间的间隔

TRePublish=86400s，原始发布者必须在此时间之后重新发布键/值对。

TRePublish和tExpire相等这一事实引入了竞争条件。正在发布的数据的存储可能会在节点过期后立即到达节点，因此实际上需要将数据放到网络上。明智的实现会使tExpire比tRePublish长得多。经验表明，t=86410就足够了。

Kademlia网络由多个相互协作的节点组成，这些节点相互通信并为彼此存储信息。每个节点都有一个节点ID，这是在网络中标识它的准唯一二进制数。

在网络中，数据块(值)也可以与相同固定长度的二进制数B(值的密钥)相关联。

需要值的节点在它认为最接近键的节点处搜索该值。需要保存值的节点将其存储在它认为最接近与该值相关联的键的节点处。

节点ID是长度为B=160位的二进制数。在Basic Kademlia中，每个节点通过某种未指定的准随机过程选择自己的ID。节点ID必须均匀分布，这一点非常重要；网络设计依赖于此。

虽然协议没有强制这样做，但是只要节点加入网络，就使用相同的节点ID，而不是生成新的特定于会话的节点ID，可能会有一些好处。

在Kademlia网络中存储或从Kademlia网络检索的数据还必须具有长度为B的密钥。这些密钥也应该均匀分布。有几种方法可以保证这一点；最常见的方法是获取值的散列，例如160位的SHA1摘要。

Kademlia的操作是基于异或(XOR)作为度量的使用。任意两个密钥或节点ID x和y之间的距离定义为。

其中^表示XOR运算符。结果是通过对操作数的每个字节进行逐字节异或得到的。

Kademlia效仿Pastry将键(包括nodeID)解释为大数。这意味着表示键的字节数组中的低位字节是最高有效字节，因此如果两个键靠近，则距离数组中的低位字节将为零。

Kademlia节点将其联系人(它已知的其他节点)组织在最多容纳k个联系人的存储桶中。这些被称为k桶。

存储桶按节点和存储桶中的触点之间的距离进行组织。具体地说，对于桶j，其中0<；=j<；k，我们保证。

给定非常大的地址空间，这意味着桶0只有一个可能的成员，即与节点ID仅在高位上不同的密钥，并且出于所有实际目的，除了可能在测试中之外，永远不会填充。另一方面，如果节点ID均匀分布，则很可能所有节点的一半位于桶B-1=159的范围内。

Kademlia的论文说，k设置的值是这样的，在一个大型网络中，任何一个桶中的所有联系人都不太可能在一小时内消失。任何试图计算此概率的人都应该考虑导致长期联系人优先保留在表中的策略，而不是较新的联系人。

Kademlia的设计者似乎没有考虑到使用IPv6地址或TCP/IP而不是UDP，或者一个Kademlia节点拥有多个IP地址的可能性。

在存储桶内，联系人按最近通信的时间排序，最近通信的联系人在列表的末尾，最近最少通信的联系人在最前面，而不管是节点还是联系人启动了消息序列。

每当一个节点接收到来自另一个节点的通信时，它都会更新相应的存储桶。如果联系人已存在，则会将其移动到桶的末尾。否则，如果存储桶未满，则在末尾添加新触点。如果存储桶已满，节点将ping位于存储桶列表顶部的联系人。如果最近最少出现联系人在(未指定的)合理时间内没有响应，则将其从列表中删除，并将新联系人添加到尾部。否则，出于存储桶更新的目的，新联系人将被忽略。

在大型繁忙网络中，当节点等待来自列表头部的联系人的回复时，可能会有来自不在桶中的联系人的另一通信。对于存储桶B-1=159来说，这是最有可能的，它负责网络中大约一半的节点。这种情况下的行为未指明，似乎可能会为DOS(拒绝服务)攻击提供漏洞。

经验表明，节点往往分为两个明显不同的类别，即瞬时节点和长期节点。这种更新策略对寿命较长的网络给予了强烈的优先考虑，从而促进了网络的稳定。它还针对某些类型的拒绝服务(DOS)攻击提供一定程度的保护，可能包括下面讨论的Sybil攻击。

最初的Kademlia论文maymo02说，Kademlia协议由四个远程过程调用("；RPC"；)组成，但随后指定了在执行这些协议和某些其他协议时必须遵循的过程。似乎最好将这些程序和其他协议添加到我们这里所称的Kademlia协议中。

此RPC涉及一个节点向另一个节点发送ping消息，另一个节点可能用PONG应答。

这具有双重效果：ping的接收方必须更新对应于发送方的存储桶；如果有回复，则发送方必须更新适合接收方的存储桶。

所有RPC数据包都需要携带由发送方分配并在回复中回显的RPC标识符。这是长度为B(160位)的准随机数。

使用较短消息标识符的实现必须考虑生日悖论，这实际上使得冲突的概率取决于标识符中位数的一半。例如，32位RPC标识符将产生与2^-16成正比的冲突概率，这在繁忙的网络中是一个令人不舒服的小数字。如果标识符被初始化为零，或者由具有相同种子的相同随机数生成器生成，则概率将确实非常高。

必须能够将ping携带到RPC回复上，以强制或允许发送方(RPC的发送方)向其接收方提供附加信息。这可能是不同的IP地址，也可能是将来通信的首选协议。

存储RPC的发送方提供密钥和数据块，并要求接收方存储数据并使其可用于以后通过该密钥进行检索。

虽然没有正式规定这一点，但很明显，除了消息ID之外，初始存储消息必须至少包含要存储的数据(包括其长度)和相关密钥。由于传输可以是UDP，因此消息还需要至少包含发送方的nodeID，而回复则需要包含接收方的nodeID。对任何RPC的回复还应包含操作结果的指示。例如，在没有指定最大数据长度的存储中，接收器显然可能因为空间不足或I/O错误而无法存储数据。

Find_node RPC包括160位密钥。RPC的接收方为它知道最接近密钥的联系人返回多达k个三元组(IP地址、端口、节点ID)。

如果可能，收件人必须返回k个三元组。如果它返回它已知的所有联系人，则它可能只返回少于k个。

此RPC的名称具有误导性。即使RPC的密钥是现有联系人的nodeID，或者实际上如果它是接收者本身的nodeID，接收者仍然需要返回k个三元组。更具描述性的名称应该是find_close_nodes。Find_node的接收者永远不应该返回包含请求者的nodeID的三元组。如果请求者确实收到了这样的三元组，它应该丢弃它。节点绝不能将自己的nodeID作为联系人放入存储桶中。

Find_Value RPC包括B=160位密钥。如果收件人上存在相应的值，则返回关联的数据。否则，RPC等价于find_node，并返回一组k个三元组。

本节介绍Kademlia用来定位离键最近的k个节点的算法。必须理解的是，从严格意义上讲，这些不一定是最接近的。此外，该算法是迭代的，尽管本文将其描述为递归。

搜索通过从最接近适合于正被搜索的关键字的桶的非空k桶中选择阿尔法触点开始。如果该存储桶中的触点少于Alpha，则从其他存储桶中选择触点。将记录最接近目标关键点closestNode的联系人。

未指定用于选择最近存储桶中的触点的标准。如果该桶内的触点少于阿尔法触点，并且触点是从其他桶获得的，则没有用于选择其他桶或从这些桶中使用哪些触点的规则。

然后，该节点将并行异步find_*RPC发送到候选列表中的Alpha联系人。每个联系人，如果它是活动的，通常应该返回k个三元组。如果任何阿尔法联系人未能回复，它将被从候选名单中删除，至少是暂时删除。

然后，该节点用收到的回复中的联系人填充入围列表。这些是离目标最近的。从入围名单中选择另一个Alpha联系人。此选择的唯一条件是尚未联系他们。再一次将find_*RPC并行发送给每一个。

并行搜索的序列被继续，直到返回的集合中没有节点比已经看到的最接近的节点更近，或者发起节点已经累积了k个已探测并已知为活动接触。

如果循环没有找到更近的节点，如果closestNode保持不变，则发起节点将向它尚未查询的k个最近节点中的每一个发送find_*RPC。

在此过程结束时，节点将积累一组k个活动联系人，或者(如果RPC是FIND_VALUE)可能已经找到数据值。可以是一组三元组，也可以将值返回给调用方。

原有的算法描述不够详细。但是，发起节点似乎维护着k个最近节点的候选列表。在每次迭代期间，选择其中的α进行探测，并相应地进行标记。如果探测成功，入围节点将被标记为活动节点。如果在一段未指定的时间之后没有回复，则从候选列表中删除该节点。随着每组回复的返回，它被用来改进候选列表：回复中更近的节点替换更远的节点(未探测？)。入围列表中的节点。迭代将继续，直到成功探测到k个节点或没有任何改进。

Kademlia使用值3表示alpha，即使用的并行度。看起来(请参见stutz06)该值是最佳的。

管理并行性至少有三种方法。第一种方法是启动alpha探测，并等到所有探测都成功或超时后再进行迭代。这称为严格并行。第二种是将飞行中的探测器数量限制在alpha以内；每当探测器返回时，就会发射新的探测器。我们可以称之为有界并行。第三种方法是在似乎合理的延迟(持续时间未指定)之后进行迭代，以便飞行中的探测器数量是alpha的某个较低的倍数。这是松散并行，也是Kademlia使用的方法。

这是Kademlia商店的运营。发起节点执行一次iterativeFindNode，收集一组k个最接近的联系人，然后向每个联系人发送一个原语存储RPC。

这是基本的Kademlia节点查找操作。如上所述，发起节点使用迭代节点查找和find_node RPC构建最接近的k个联系人的列表。该列表被返回给调用者。

这是卡德姆利亚的搜索行动。它作为节点查找进行，因此构建了k个最近联系人的列表。但是，这是使用find_value RPC而不是find_node RPC来完成的。如果在节点查找期间的任何时候返回值，而不是一组联系人，则放弃搜索并返回值。否则，如果没有找到值，则将k个最近联系人的列表返回给调用者。

当iterativeFindValue成功时，发起方必须将键/值对存储在最近的未返回值的节点上。

如果在任何给定的存储桶范围内都没有为tRefresh执行节点查找(在Basic Kademlia中为一小时)，则节点在该范围内选择一个随机数并使用该数字作为键进行刷新，即iterativeFindNode。

它将某个已知节点c的值作为其第一个联系人插入到适当的存储桶中。

它刷新比其最近邻居更远的所有存储桶，后者将位于索引最低的已占用存储桶中。

如果节点保存了一个良好联系人列表，并将其中一个用作"；已知节点"；，则它将与此协议一致。

数据使用iterativeStore存储，其效果是在离键最近的k个节点上复制数据。

每个节点以tReplicate秒为间隔(每小时)重新发布它包含的每个键/值对。不能将重新发布节点视为键/值对的原始发布者。

键/值对的原始发布者每隔tRePublish秒(每24小时)重新发布一次。

当iterativeFindValue成功时，发起方必须将键/值对存储在最近的未返回值的节点上。

为所有键/值对分配一个过期时间，该时间与当前节点和其ID最接近键的节点之间的节点数成指数反比，其中该数字是从当前节点的桶结构推断的。

当键/值对被存储时，编写器将使用类似于以下内容的内容来计算过期时间：

要求数据在最初发布日期之后(一天)过期，这一要求非常含糊，似乎意味着任何数据都不能重新发布。在任何情况下，系统都需要用原始发布时间戳标记存储的键/值对。如果这是准确的，时间戳必须由发布者设置，这意味着时钟必须至少在整个网络上松散地同步。使用数据到达时的生存时间(TTL)来标记键/值对似乎是明智的，tExpire(一天)或其中的一小部分。

RTT(往返时间)值或一组这样的值，以毫秒为单位。

将一个或一组RTT添加到联系人数据结构将使您能够在选择使用哪个RTT时做出更好的决定。

可以使用ping RPC或使用传统的互联网ping来测量到联系人的往返时间(RTT)。

实现者应该注意避免护送效应。当多个进程需要轮流使用一个资源时，就会出现这种情况。这种突发的活动有向同步漂移的趋势，这可能是灾难性的。在Kademlia中，所有节点都需要每小时重新发布其内容(TReplicate)。护送效应可能会导致这种情况在整个网络中同步，这对用户来说就像网络每小时都会死掉一样。

实现者应该记住，随机数生成器通常是不可重入的，因此需要同步来自不同线程的访问。

另外，请注意时钟粒度：在使用时钟为随机数生成器设定种子的情况下，连续调用可能使用相同的种子。

为了提高效率，商店RPC应该是两阶段的。在第一阶段中，发起方发送密钥和可能的长度，而接收方则用等同于OK的内容或代码来回复，该代码表示它已经具有该值或其他状态代码。如果回复为OK，则发起方可以发送该值。

还应考虑开发处理分层数据的方法。有些值会很小，适合UDP数据报。但有些消息会非常大，比如超过5 GB，需要分块。相对于UDP数据包，数据块本身可能非常大，通常约为128KB，因此这些数据块必须被分解成单独的UDP数据包。

如前所述，要求tExpire和tRePublish具有相同的值引入了争用条件：数据在到期后将频繁地立即重新发布。合理的做法是使过期间隔tExpire略大于重新发布间隔tRePublish。该协议当然还应该允许商店RPC的接收方回复它已经拥有数据，以节省昂贵的网络带宽。

Douceur02的John Douceur的一篇论文描述了一种网络攻击，在该攻击中，攻击者选择节点ID，这些节点ID的值使他们能够在网络中以最适合中断操作的模式定位自己。例如，要从网络中删除数据项，攻击者可能会聚集在其密钥周围，接受任何存储密钥/值对的尝试，但在提供密钥时从不返回值。

Sybil的变体是Spartacus攻击，攻击者加入网络时声称与其他成员具有相同的节点ID。正如规定的那样，卡德姆利亚没有任何辩护。具体地说，长寿节点总是可以窃取短命节点的nodeID。

Douceur的解决方案是要求所有节点从中央服务器获取其节点ID，该服务器至少负责确保节点ID的分布是均匀的。

一种较弱的解决方案是要求从节点的网络地址或某些其他准唯一值导出节点ID。