Kademlia:A Peer-to-Peer Information System Based on the XOR Metric

Papers Link

Key Concepts

分布式哈希表（distributed hash table，缩写DHT）

分布式哈希表（distributed hash table，缩写DHT）是分布式计算系统中的一类，用来将一个键（key）的集合分散到所有在分布式系统中的节点。这里的节点类似哈希表中的存储位置。分布式哈希表通常是为了拥有大量节点的系统，而且系统的节点常常会加入或离开。

Technical Content

Kad协议是什么

Kad是一种分布式哈希表技术（DHT），通过独特的以异或算法为距离度量基础，建立了一种全新的DHT拓扑结构。是基于UDP协议的P2P网络的节点动态管理和路由协议。

Kad协议特点

查找迅速，可以在O（Log（N））的时间内得到查询结果，并且可以通过参数调节查找速度。
算法实现相对简单。

为什么要使用Kad协议

在P2P网络中，相对于Chord、CAN、Pastry等协议相比，大大提高了其路由查询速度

关键问题

使用一个对等网络(P2P Network)构建分布式存储系统，需要解决以下几个关键问题：

拓扑——如何构建一致的网络拓扑？
路由查找——如何快速查找特定网络节点（节点路由技术）？
路由表更新——如何处理网络中节点动态变化，离线节点如何处理，如何处理节点动态变化时的对象可靠性和可用性？
路由表构建——如何构建存储对象与节点之间的映射关系？

Kad协议详解

如何构建一致的网络拓扑

网络拓扑——指网络成员（如计算机设备）间的特定排列（组织）方式，分为物理拓扑与虚拟拓扑两种。

首先，Kad网络中每一个节点都会被分配唯一的节点ID，一般是160bit的二进制数，节点之间可以计算距离，节点距离以节点ID的XOR值度量。

XOR（异或）的计算规则是两个二进制数每一个bit相同为0，不同为1。如：

                               010100

                         XOR   110001

                    -----------------

                               100101

所以，Dis(M,N)=1+4+32=37

基于以上方法，整个网络空间可以被如下一棵二叉树表示，树的叶子节点代表网络节点，每个网络节点的id采用从根节点到自己本身的路径上的二进制位序列组成，下图采用的是采用5bits作为节点ID，如实心节点的nodeId为0011x。

从网络中每个节点的视角来看，它可以根据公共前缀长度将这颗二叉树分解为一系列不包含自己的子树。顶层的子树，由整棵不包含自己的树的另一半组成，即与节点之间的公共前缀长度为0；下一层子树由剩下部分不包含自己的一半组成，即公共前缀长度为1；依此类推，直到分割完整棵树。下图展示了从节点 M 视角来分割上面的网络树的结果：

因此，我们可以将KAdemlia的网络拓扑总结为：每个节点按照与自己的距离来切割节点网络树：被切割的子树称之为 Bucket 。整个路由表本质上便是一个 Bucket 数组，Kademlia协议以聚类网络节点：每个 Bucket 中的节点必然与本节点具有相同的最长公共前缀。

路由表

路由表构建

构建路由表的本质是建立到网络全局的地图，目标是：对于节点 M ，给定任意节点 X ，可以根据节点很容易计算出距离 X 更近的节点列表。虽然我们的目标是本地一步到位的查找，但这是不现实的，这需要维护数量巨大的全局节点信息。我们退而求其次，采用迭代查找的思路：每次查找要距离目标更近一点点。

存储对象与节点映射问题，Kad网络是将对象根据其唯一特征计算160bit的指纹，根据该指纹找到网络中与其指纹最接近的K个节点，这些节点将成为对象的最终存储目的地。一般这个指纹会选取对象内容的hash，便于对象去重和对象的唯一性保证。而之所以选择K个节点存储对象是为了提高对象数据的可靠性。

因此，其存储模式如下图：

构建过程——分裂

在一些实现Kademlia协议实现中，每个节点初始时只有一个 Bucket ，感知到网络上有节点时，直接将远程节点信息添加至该Bucket，直到该Bucket内节点数量超过，此时开始分裂 Bucket 。

所谓的分裂是指创建一个新的 Bucket ，然后将原来 Bucket 内的部分节点迁移至新 Bucket 。因为原 Bucket 内的节点与本节点的距离不尽相同，所以，迁移的原则是：将与本地节点更近节点迁移至新建 Bucket ，迁移完成后再判断新建 Bucket 内节点数是否超过限制，如果是，继续对该新建 Bucket 进行分裂。

上面提到迁移的过程中会将部分节点迁移至新 Bucket ，那么如何选择这些需要被迁移的节点呢？答案是根据内节点与本节点之间的距离决定。

例子：

假设本地节点为 Local(100) ，初始时所有其他节点都位于一个 Bucket 内，共包含7个节点，假设演示中 Bucket 内的节点数最大 K 为1。

第一次分裂创建一个新的，将原中与local的cpl超过0的节点迁移至新的 Bucket 。于是，此时两个 Bucket 内的内容变为：

Bucket_old = {A,B,C,D} Bucket_new = {E,F,G}

第二次分裂将其中与local的cpl超过1的节点迁移至新的 Bucket ，于是，现在就变为：

Bucket_new = {F,G} Bucket_new1 = {E}

形成了如下的分区：

路由表更新

Kademlia网络中节点是动态变化的，节点可新接入网络，也可从网络离线。这也意味着每个节点的路由表也是一直变化着的。

新节点上线

新节点 N 上线时，需要为其提供一个种子节点 S ，以 S 作为中介加入Kademlia网络，具体来说：

将 S 加入本地路由表，成为 N 的种子节点；
向 S 发起一次节点查询请求(FIND_NODE)，查询的目的节点其实是自身；该请求的目的有二：第一告诉 S 新增了节点 N ，第二通过 S 发现集群中更多的节点。而发起了指向自身的查询请求也很有意思：其一是因为 N 此时还不知道系统更多的节点信息；其二是通过这种方式 N 可以快速地找到更多距离自己更接近的节点。
S 收到 N 的查询目标节点请求，首先将节点 N 加入自身的路由表中，然后给 N 最多返回 K 个距离 N 更接近的节点信息；
N 收到 S 的响应，将响应中的节点加入自身路由表，然后对这些节点分别发起查询请求，当然，查询的目标还是自身。

普通节点更新

每个bucket里的节点都按最后一次接触的时间倒序排列
每次执行四个指令中的任意一个都会触发更新
当一个节点与自己接触时，检查它是否在K-bucket中
- 如果在，那么将它挪到k-bucket列表的最底（最新）
- 如果不在，PING一下列表最上面（最旧）的一个节点
  - a) 如果PING通了，将旧节点挪到列表最底，并丢弃新节点
  - b) 如果PING不通，删除旧节点，并将新节点加入列表

节点离线

节点离线在Kademlia协议中无需做特殊处理，如果某个节点离线，那么其离线事件最终会反馈到网络节点的路由表中，将其从路由表中剔除即可，相比于Chord协议有了极大的简化。

如何保证节点动态变化时保证对象的可访问

在P2P网络中，节点是动态变化的，而结合我们刚刚描述的对象节点映射算法，可能会导致以下几个问题:

对象<key, value>被存储在与key距离最接近的 K 个节点，如果 K 个节点全部离线，那么对象便不可达；
对象<key, value>被存储在与key距离最接近的 K 个节点，如果网络新加入节点 N 且 N距离key更接近，对象也需要进行一次迁移，因为下次去查找的时候，会直接定位到 N ，如果数据不迁移至 N ，那对象虽然数据存在，但也是不可达。

在论文中，作者提出了按照小时为单位执行Re-Publishing：每个小时，每个节点对本地存储的每一个对象进行Re-Publishing。每一次Re-Publishing包括下面两个步骤:

首先查询当前最近的K个节点信息；
节点向1中获得的节点发送数据存储消息，从而完成数据更新

针对每个节点的每个对象都执行类似操作，会导致P2P网络出现突激的网络流量。仔细分析上面的行为，我们可以发现，其实很多的Re-Publishing是无用的：

如果在一个小时的周期内，网络拓扑没有发生变化，那根本不需要进行Re-Publishing；
对于不同的节点，如果对象在节点、上均已存储，那其实在一个Re-Publishing周期内，只需要一个节点(或者)来更新即可，没必要大家同时一起上，浪费资源；
步骤1中的K-Closest查询是否有必要：因为根据上面的表述，对于新增节点，其实是可以很快速地反映到最近节点路由表，所以一般情况下，查询本地节点路由表即可。

针对上面的疑问，论文中也提出了几点优化方案：

避免不必要的Re-Publishing：首先，如果对象刚被写入（Re-Publishing周期内写入的），那么认为该对象其实是被写到最新的网络拓扑节点中，那就不对该对象做Re-Publishing；
关于多节点同时Re-Publishing相同对象问题，可以这么解：将不同节点的Re-Publishing设置不一样（如在一个范围内随机取值），这样，例如节点 Re-Publishing了对象，节点再次Re-Publishing对象时便发现其最后修改时间是刚刚，根据上面的描述，节点就不再Re-Publishing了，存储的其他节点同样如此，有效避免了一个周期内多节点同时Re-Publishing问题；
关于避免节点更新问题，大家自行参考论文吧，懒得看了。

路由算法

路由算法要解决的是如何根据目标ID找到地址或者找到与该ID最节点的目标节点地址。

在一个对等网络中，某个节点要查询其他节点的信息时，它可依赖的信息只有两个：

目标节点ID；
当前节点维护的路由表；

其查询的核心思想是：逐步迭代，递近查找。其基本过程如下：

发起查询节点从自己的路由表中非空的k-buckets中选择 α 个与目标nodeID最近的节点。
发起者向自己选择出来的α个节点并行，异步发起 FIND_NODE操作。
当选择出来的α的节点收到FIND_NODE消息时，会根据自身维护的路由表信息，返回 k 个距离发起者更近的节点供查询发起者继续查询。如果目标节点就是自身，那直接返回自身信息即可。
发起者查询收到响应时，会对响应中的结果进行过滤：如果该节点在之前已经被询问过，便不再加入待查询列表，保证查询的收敛性。
这样不断循环步骤3,4。
当发起者询问过它所知道的最近的 k 个节点，并且得到了它们的回应时，查询过程结束。

查询的最终结果是得到了一批距离目标节点很近的节点列表，然后从节点列表中选择出最接近目标的个节点。选择这个节点的目的是可用来读，也可用来写对象，具体见后面描述。

You may find interesting:

2018.1.18区块链论文讨论班通知

Nothing at stake problem of PoS