转载请注明出处：www.huamo.online
字节杭州 求贤若渴：
Kademlia：一种基于异或指标的P2P信息系统
概述
Kademlia是一种点对点分布式哈希表（DHT），它在容易出错的环境中也具有可证明的一致性和性能。使用一种基于异或指标的拓扑结构来路由查询和定位节点，这简化了算法并有助于证明。该拓扑结构有一个特点：每次消息交换都能够传递或强化有效信息。系统利用这些信息进行并发的异步查询，可以容忍节点故障，并且故障不会导致用户超时。
介绍
Kademlia有许多之前DTH无法同时提供的理想特性。它将节点为了彼此了解而必须发送的配置消息减至最少。查找key时附带的自动广播配置信息。节点具有足够的知识和灵活性能通过低延迟路径来路由查询。Kademlia使用并发异步查询来避免节点故障导致的超时。节点会记录彼此的存在性来抵抗某些基本的拒绝服务攻击。
Kademlia采用了许多DHT的基本做法，主键（keys）是无规律的160位空间。每个参与的计算机在这个160位主键空间中都有一个nodeID。键值对存储在那些nodeID“接近”主键的节点上。最终，这种基于nodeID的路由算法可以让每个人都能有效定位到接近指定主键的服务器。
Kademlia的许多优点都来源于其使用了新颖的XOR度量标准来定义主键空间两点之间的距离。XOR是对称的，这就允许Kademlia参与者能够接收来自于其路由表中包含的完全相同的节点分布的查询请求。没有这个特性，像Chord之类的系统就无法从它们收到的查询中学习到有用的路由信息。更糟糕的是，不对称会导致路由表不够灵活。比如在Chord中，节点指纹表的每一条都必须存储ID空间中某个间隔之前的精确节点，而实际上，在间隔内的任何节点与相同间隔之前的那些节点都可能会实际距离很远。相比之下，Kademlia可以对一个间隔内的任意节点发送查询，这使它能根据延迟选择最优的路由，甚至能够并行异步查询几个同样合适的节点。
为了定位接近一个特定ID的节点，Kademlia从头到尾都使用了一种单一路由算法。而其它系统则是使用一种算法来靠近目标ID，然后用另一种算法完成最后几跳。
系统描述
类似于其他DHT，Kademlia也会为节点分配一个160位的ID值，并提供一个查找算法来连续定位接近指定ID的节点，经过多个步骤后，对数级别的收敛到查找目标。
Kademlia将节点视为二叉树的叶子，每个节点的位置都由它的nodeID中最短唯一前缀来决定。下图1演示了一个前缀为0011的节点的位置。对于任一给定节点，我们将整个二叉树划分为一系列连续降低的子树，这些子树都不包含该节点。最高的子树由整个二叉树的一半构成（这一半不包含给定节点），次高子树由剩余部分的一半构成（剩余部分也不包含给定节点），依次类推下去。在下图样例中，被圈起来的子树分别由前缀为1，01，000和0010的所有节点构成。Kademlia协议确保每一个节点都知道它的每个子树中的至少一个节点，有了这个保证，任何节点都能够通过ID来定位其它节点。下图2演示了0011节点定位1110节点的过程，它通过连续的在越来越低的子树中查询所知的最佳节点来找到目标，最后查找收敛到了目标节点上。
图1：Kademlia二叉树。黑点代表了
0011节点的位置。灰线圈则表示0011节点的所有子树。0011节点在每个子树中都至少有一个熟人。
图2：根据ID定位节点。这里演示了
0011节点寻找1110节点的过程，它第一个RPC请求到101节点，该节点是0011节点提前已知的。后续的RPC则是根据之前RPC的返回再做决策。
下面会首先定义ID接近的精确概念，然后会给出一种可用的查找协议，即使没有节点与指定主键拥有共同的唯一前缀，或者一个给定节点的一些子树为空的情况下，这个查找协议依然是有效的。
XOR度量
每个Kademlia节点都有一个160位的nodeID，是一个随机产生的标识符。一个节点传输的所有消息中都包含了它自己的nodeID，允许接受者在必要时记录发送者的存在性。
主键，同样也是一个160位的标识符，为了将<key, value>对指定到特定的节点上，Kademlia用了2个标识符之间的距离这种概念。给定两个160位标识符，$x$和$y$，Kademlia将它们之间的距离定义为它们的按位异或，然后把结果转化为一个整数，即$d(x, y) = x \oplus y$。
我们首先注意到异或是一种有效的度量。很明显，$d(x, x) = 0$；如果$x \neq y$，则$d(x, y) > 0$；并且$\forall x, y: d(x, y) = d(y, x)$。异或还具有三角形特性：$d(x, y) + d(y, z) \geq d(x, z)$。三角特性由以下的事实推出：$d(x, y) \oplus d(y, z) = d(x, z)$以及$\forall a \geq 0, b \geq 0: a + b \geq a \oplus b$。
我们接下来发现异或度量还刻画了二叉树系统架构中的距离概念。在一个160位ID完全填充的二叉树（满二叉树）中，两个ID距离的大小是包含它俩的最小子树的高度。当树没有完全填充时，最接近IDx的叶子节点是nodeID与x具有最长共同前缀的节点，如果在树中有空的分支，则可能会有不止一个叶子节点具有最长共同前缀。在这种情况下，我们基于该树的空分支，把x对应的位取反得到ID $\widetilde{x}$，那么距离$\widetilde{x}$最近的叶子即为距离$x$最近的叶子。
类似于Chord中沿圆周顺时针方向的度量方法一样，XOR也是单向的。对于任意给定的点$x$和距离$\Delta > 0$，仅存在一个点$y$使得$d(x, y) = \Delta$。单向性保证了对于相同的主键，无论从哪个节点开始查询，都会沿着相同的路径进行收敛。因此，沿着查询路径对<key, value>对进行缓存就能够避免热点问题。另外，XOR拓扑结构还是对称的（对于所有的$x$和$y$，都有$d(x, y) = d(y, x)$）。
节点状态
Kademlia节点相互存储联系信息用来路由消息。对于每一个$0 \leq i < 160$，每个节点都会保存一个<IP地址, UDP端口, nodeID>的三元组列表，其中nodeID是那些距离自己为$2^i \leq \Delta \leq 2^{i + 1}$的节点ID，我们将这个列表称为k-buckets(K桶)。【所以每个节点大约都有160个K桶】每一个K桶都按照最近联系时间排序 – 最久没联系的节点位于头部，最近刚联系的节点放在尾部。对于比较小的$i$值，K桶一般的都是空的（因为没有合适的节点存在）。对于较大的$i$值，列表规模会增长至$k$，其中$k$是一个系统范围内的复制参数。$k$选取的原则是：对于任意给定的$k$个节点，1个小时内同时宕机的可能性很小（例如 $k = 20$）。
当一个Kademlia节点收到其它节点的任何信息（请求或答复）时，它就会更新K桶中对应的发送者nodeID条目：
如果发送者ID已经存在，则把它移到列表尾部。
如果K桶中还没有这个发送者ID，并且K桶规模此时少于$k$，则将该发送者三元组插入到列表尾部。
假如K桶已经满了（规模等于$k$），此时会去ping一下头部那个最久未联系的节点来决定下一步该怎么做。
3.1 如果最久未联系的节点没有回应，则它会移除这个节点，并将发送者三元组插入尾部。
3.2 而若最久未联系的节点响应了，则它会把这个最久未联系节点三元组移至K桶尾部，并且发送者的联系信息会抛弃掉。
K桶有效的实现了最近最久未联系的置换策略（有点类似于LRU），只是活动的节点永远不会从列表中移除。这种对于旧联系人的偏爱来自于论文作者对Saroiu等人所收集的Gnutella跟踪数据的分析结果。下图3展示了Gnutella节点的已经存活一小时的情况下，再继续存活一小时的百分比函数关系。可以看到，一个节点存活的时间越长，那么它再继续存活一小时的概率就越大。通过保留最旧的可用联系人信息，K桶最大化了保存的节点继续可用的可能性。
K桶的另外一个好处是它可以阻挡某些DoS攻击。攻击者无法通过向系统中洪泛新节点的方式来清空节点的路由信息。Kademlia节点只会在老节点离开系统的时候，才会将新节点插入到K桶中。
图3：正常运行x时长后再稳定运行1小时的概率图。X轴表示正常运行分钟数，Y轴表示还能再正常运行1小时的节点占比。
Kademlia协议
Kademlia协议包括4种RPC：PING，STORE，FIND_NODE，FIND_VALUE。PING RPC会对一个节点进行探测确认其是否在线。STORE通知一个节点存储一个<key, value>对以便以后获取。
FIND_NODE携带一个160位ID作为参数。接收者返回k个它所知的最靠近目标ID的节点三元组。这些三元组可以来自于一个单独的K桶，或者也可以来自多个（如果最接近的那个K桶不满的话）。无论如何，RPC接收者都必须返回k个元素（除非遍查了它自身的所有K桶之后都凑不够k个数量，这种情况下，它会把它知道的所有节点都返回给发送者）。
FIND_VALUE行为类似于FIND_NODE – 返回<IP地址，UDP端口，nodeID>三元组 – 只有一个例外，如果接收者曾经接受过这个主键的STORE请求，那么它就直接返回这个存储的值。
在所有的RPC中，接收者都必须在回应中包含一个160位的随机RPCID，这可以阻止一些地址伪造的情况。并且RPC的接收者还可以把PING附带在RPC的回复中来进一步确认发送者网络地址的有效性。
一个Kademlia参与者要做的最重要事情就是对给定的nodeID，要能定位出k个最近节点。我们称这个过程为一次节点查找【node lookup】。Kademlia使用了一种递归算法用于节点查找。查询发起者首先从离它自己最近节点组成的K桶（$2^0 \leq \Delta \leq 2^1$）中取出$\alpha$个节点（如果这个K桶少于$\alpha$个元素，它就会从次近的K桶再尝试抽取，直到凑够$\alpha$个节点）。然后这个发起者并行的异步发送FIND_NODERPC到这$\alpha$个节点。$\alpha$是一个系统范围内的并发参数，比如设为3。
在递归步骤中，发起者会根据之前RPC返回的结果再向新的节点发送FIND_NODE请求。（这个递归可以在所有$\alpha$个RPC返回之前就开始）。在发起者听到的接收者返回的$k$个结果中，从中挑选出$\alpha$个之前没有询问过的节点再发送FIND_NODE请求。没有快速响应的节点不会再考虑直到它响应为止。如果一轮FIND_NODE没有返回一个比之前所知的更近的节点，发起者就会对$k$个最近节点中所有未查询的节点发送一次FIND_NODE请求。当发起者询问过它所知道的最近$k$个节点并得到了它们的回应时，这个递归分支的查询过程结束。当$\alpha = 1$时，查询算法在信息开销和故障节点的检查延迟上，和Chord类似。然而，Kademlia可以做到低延时路由，因为它能够灵活的从$k$个节点中任意选择一个节点发送请求。
大部分的操作都是基于上述的查询过程实现的。为了存储一个<key, value>对，一个参与者定位出$k$个最接近key的节点，然后向它们发送STORERPC请求。另外，每个节点在需要保活的时候，都会重新发布<key, value>对，这个会在之后说。这种做法会保证<key, value>对有很大可能持久化。对于现在的Kademlia应用（比如文件共享），我们还会要求<key, value>对的原始发布者每隔24小时再重新发布一次。因为，为了限制系统中不可用的索引信息不至于太多，一个<key, value>对，在发布24小时后，默认就会被设为过期。对于其它的应用，比如数字证书或用于值映射的加密哈希，更长的过期时间也许会更合适。
要找到一个<key, value>对，一个节点先开始找到最接近这个key的$k$个节点。但是，值查找用的是FIND_VALUE而不是FIND_NODERPC。并且，只要有一个节点返回了value，查找过程就立即停止。为了缓存，一旦一个查找成功，请求节点将会在它发现的，那些最接近key的，但又没有存储这个<key, value>对的节点上存储这个键值对。
由于拓扑结构的单向性，后续对相同key的查找大概率会在查询最近节点之前就命中缓存条目。对于某个特别受欢迎的key，系统最终可能会在很多节点上缓存它的内容。为了避免“过度缓存”（over-caching），我们在每个节点的数据库中设置一个<key, value>对的过期时间，这个时间设置为与当前节点和距离key ID最近的节点之间的节点数量成指数反比关系。（节点数量可以从当前节点的K桶结构推算出来）。虽然简单的LRU策略会产生类似的生命周期分布，但是没有合适的方法去选择cache的大小，因为节点对于系统将要储存多少值没有先验知识。
一般来说，节点之间的请求通信就可以使K桶保持最新。但为了解决一些特定ID区间根本不会被查询的极端情况（无人问津的资源），每个节点会对过去一小时内都没有查询的节点条目进行更新。更新操作意味着在桶中随机挑选一个ID，然后对这个ID进行一次节点查找。
要加入Kademlia网络，一个节点$u$必须和一个已经在网络中的节点$w$有联系，$u$将$w$插入到合适的K桶中。然后$u$对自己的nodeID进行一次节点查找。最终，$u$会更新出更远的节点的K桶信息。在更新过程中，$u$会填充自己的K桶，并且如果需要还会将自己插入到其它节点的K桶中。
路由表（Routing Table）
Kademlia基本路由表结构是很直观的，只是在一些高度不平衡的树中需要做一些小处理。路由表是一颗二叉树，叶子节点就是K桶。每一个K桶包含的是ID拥有相同前缀的节点，这个前缀就是这个K桶再二叉树中的位置。因此，每一个K桶都覆盖了ID空间的一部分，所有的K桶加起来就无缝覆盖了160位ID空间的所有区域。
在路由树中的节点都是按需动态分配的。下图4展示了这个过程。最初，一个节点$u$的路由树只有一个节点 – 一个K桶覆盖了整个ID空间。当$u$知道了一个新的联系人时，它会将这个联系人插入到合适的K桶中。
如果这个桶不满，新联系人就简单的插入即可。
否则，即这个合适的K桶满了，此时如果这个K桶覆盖的范围包含节点$u$自己的nodeID，那么这个K桶会一分为2，旧内容也会随之分裂开，后续的插入重复这个过程。
如果这个K桶满了，并且K桶覆盖范围并没有包含节点本身ID，新联系人则简单的舍弃掉即可。
图4：随着时间变化一个节点（nodeID = 00..00）的路由表演进。最初，如图顶部所示，只有一个K桶。当K桶塞满时，包含节点本身nodeID范围的K桶就开始分裂。
在高度不平衡的树中会出现一种问题。假设节点$u$加入系统，且它是唯一一个nodeID以000开头的节点，再假设系统已经有多余$k$个节点前缀为001。这样每一个前缀为001的节点都会有一个空的K桶需要插入$u$节点信息，然而$u$的桶更新也只会通知$k$个节点。为了避免这个问题，Kademlia节点会保存所有合法的联系人在一个规模至少为$k$个节点的子树中，即使这需要拆分K桶（虽然此时这个K桶不是因为包含了节点本身的nodeID才导致的拆分）。下图5展示了这个额外的拆分处理，当$u$更新分裂的K桶时，所有前缀为001的节点都会知晓这件事情。【所以这段话的结论是，实际Kademlia实现中，只要K桶满了就会进行拆分？无论这个K桶范围是否涵盖了节点本身的nodeID？】
图5：一个nodeID = 00…00的节点的宽松路由表。为了确保它知道节点周围的最小子树中的所有联系人（这个最小子树至少有$k$个联系人），这个宽松的路由表在其分支过程中有一些小小的不按套路出牌。
Key的高效再发布
为了保证<key, value>对的持久化，节点必须定期重新发布keys。否则，两种情况可能会导致查找一个本来有效的key，结果却失败了。第一种：当<key, value>对发布的时候，初始得到它们的$k$个节点中的一部分节点离开了网络。第二种：新加入节点的nodeID较之前节点距离key更近。在这两种情况下，一个存储了<key, value>的节点都必须重新发布，以再次确保距离key最近的$k$个节点能获取到这个键值对内容。
为了弥补节点离开网络的情况，Kademlia每隔1小时对每个键值对进行再发布。这个策略的简易实现会带来很多消息开销 – 存储<key, value>对的$k$个节点每小时都会先进行一次节点查询，然后再进行$k - 1$次STORE调用。幸运的是，再发布过程可以被高度优化。首先，当一个节点收到一个指定<key, value>对的STORE调用时，它可以假设这个调用同时也发送给了另外$k - 1$个最近节点上，因此这个接收者下一个小时就不需要再发布该键值对。这就确保了只要再发布间隔不是完全同步的，那么每个小时对于一个指定的键值对，只会有一个节点重新发布。
第二个优化则是在重新发布之前避免执行节点查找。如之前所述，为了处理不平衡树，节点会分裂一个不平衡子树的K桶，以保证它能对周围节点有一个完全掌握。如果，在重新发布键值对之前，一个节点u更新了这个子树下的所有K桶，它就会对指定的key自动发现最近的$k$个节点。所以对这些K桶的更新代价可以分摊到许多key的再发布过程中。
参考链接：
转载请注明出处：www.huamo.online