Kademlia

Kademlia 是由 Petar Maymounkov 与 David Mazières 所设计的P2P 重叠网络传输协议,以构建分布式的P2P电脑网络。是一种基于异或运算的P2P信息系统。它制定了网络的结构及规范了节点间通讯和交换资讯的方式。

Kademlia 节点间使用传输通讯协议 UDP 沟通。Kademlia 节点利用分布式散列表 (DHT) 储存资料索引。透过现有的局域网/广域网( LAN/WAN),建立起一个新的虚拟网络或重叠网络。

一个想要加入网络的节点需要先经过启动过程。在这个阶段,该节点需要知道另一个已经在 Kademlia 网络中注册的节点的 IP 地址 (通过另一个使用者或储存的清单取得)。如果启动中的节点还不是网络的一部分,它便会计算一个尚未指定给其他节点的随机ID(160比特)编号。这个ID是由节点的对外IP地址跟端口号经过SHA-1算法散列之后得到的。这个 ID 会一直使用到离开网络为止。

Kademlia 内的资讯都储存在称为“值(value)”的东西内,每个值都连接著一个“键(key)”。每一条<键,值>对作为Kad网络的基本信息结构被存储在本地数据库当中。

简单的说,拥有要分享的文件网络节点,会先处理文件的内容,并从内容计算出一组数字(散列),这组数字将会在文件分享网络中辨识这个文件。散列与节点 ID 的长度相同。接着会查找几个 ID 与散列值相近、且节点内有储存著自己 IP 地址的节点。搜索的用户会使用 Kademlia 来搜索网络上节点ID离自己最近距离的节点来取得文件的散列值,然后会取得在该节点上的路由清单。 当节点联入和联出时,这份存储在网络上的路由清单也将保持不变。因为内嵌的冗余存储算法,路由清单将复制在多个节点上。

在Kad网络中,每个节点只负责处理一小部分搜索和查找源的工作。分配这些工作的时候,通过我们每个用户端的唯一的ID和搜索文件的Hash值之间的匹配来决定。

一、前言

Kademlia协议(以下简称Kad)是美国纽约大学的PetarP. Maymounkov和David Mazieres.在2002年发布的一项研究结果《Kademlia: A peerto -peer information system based onthe XOR metric》。

简单的说,Kad 是一种分布式哈希表(DHT)技术,不过和其他DHT 实现技术比较,如Chord、CAN、Pastry 等,Kad通过独特的以异或算法(XOR)为距离度量基础,建立了一种全新的DHT拓扑结构,相比于其他算法,大大提高了路由查询速度。

在2005 年5 月著名的BiTtorrent 在4.1.0 版实现基于Kademlia 协议的DHT 技术后,很快国内的BitComet 和BitSpirit 也实现了和BitTorrent 兼容的DHT 技术,实现trackerless下载方式。

另外,emule 中也很早就实现了基于Kademlia类似的技术(BT中叫DHT,emule中也叫Kad,注意和本文简称的Kad 区别),和BT 软件使用的Kad 技术的区别在于key、value 和node ID 的计算方法不同。

二、节点状态

在Kad网络中,所有节点都被当作一颗二叉树的叶子,并且每一个节点的位置都由其ID值的最短前缀唯一的确定。

对于任意一个节点,都可以把这颗二叉树分解为一系列连续的,不包含自己的子树。最高层的子树,由整颗树不包含自己的树的另一半组成;下一层子树由剩下部分不包含自己的一半组成;依此类推,直到分割完整颗树。展示了节点0011如何进行子树的划分:

节点0011的子树划分

虚线包含的部分就是各子树,由上到下各层的前缀分别为0,01,000,0010。

Kad协议确保每个节点知道其各子树的至少一个节点,只要这些子树非空。在这个前提下,每个节点都可以通过ID值来找到任何一个节点。这个路由的过程是通过所谓的XOR(异或)距离得到的。

就演示了节点0011如何通过连续查询来找到节点1110的。节点0011通过在逐步底层的子树间不断学习并查询最佳节点,获得了越来越接近的节点,最终收敛到目标节点上。

通过ID值定位目标节点

需要说明的是,只有第一步查询的节点101,是节点0011已经知道的,后面各步查询的节点,都是由上一步查询返回的更接近目标的节点,这是一个递归操作的过程。

三、节点间距离

Kad 网络中每个节点都有一个160bit的ID值作为标志符,Key也是一个160bit的标志符,每一个加入Kad网络的计算机都会在160bit的key 空间被分配一个节点ID(node ID)值(可以认为ID是随机产生的),对的数据就存放在ID值“最”接近key值的节点上。

判断两个节点x,y的距离远近是基于数学上的异或的二进制运算,d(x,y) = x?y,既对应位相同时结果为0,不同时结果为1。例如:

010101

XOR 110001

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

100100

则这两个节点的距离为32+4=36。

显然,高位上数值的差异对结果的影响更大。

对于异或操作,有如下一些数学性质:

? d(x, x) = 0

? d(x, y) > 0, if x ≠ y

? ∨x, y : d(x, y) = d(y, x)

? 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

正如Chord的顺时针旋转的度量一样,异或操作也是单向性的。对于任意给定的节点x和距离⊿≧0,总会存在一个精确的节点y,使得d(x,y)= ⊿。另外,单向性也确保了对于同一个key值的所有查询都会逐步收敛到同一个路径上,而不管查询的起始节点位置如何。这样,只要沿着查询路径上的节点都缓存这个对,就可以减轻存放热门key值节点的压力,同时也能够加快查询响应速度。

四、K桶

Kad的路由表是通过一些称之为K桶的表格构造起来的。这有点类似Tapestry技术,其路由表也是通过类似的方法构造的。

对 每一个0≦i≦160,每个节点都保存有一些和自己距离范围在区间 内的一些节点信息,这些信息由一些(IP address,UDP port,Node ID)数据列表构成(Kad网络是靠UDP协议交换信息的)。每一个这样的列表都称之为一个K桶,并且每个K桶内部信息存放位置是根据上次看到的时间顺序排列,最近(least-recently)看到的放在头部,最后(most-recently)看到的放在尾部。每个桶都有不超过k个的数据项。

一个节点的全部K桶列表如表1所示:

I 距离 邻居

0 0 1[2 , 2) 0-1 (IP address,UDP port,Node ID) ......

0-k (IP address,UDP port,Node ID)

1 1 2[2 , 2) 1-1 (IP address,UDP port,Node ID) ......

1-k (IP address,UDP port,Node ID)

2 2 3[2 , 2) (IP address,UDP port,Node ID) ...... 2-1

(IP address,UDP port,Node ID) 2-k

……

i 1[2 , 2) i i+ i-1 (IP address,UDP port,Node ID) ......

i-k (IP address,UDP port,Node ID)

……

表1:K桶结构

不过通常来说当i值很小时,K桶通常是空的(也就是说没有足够多的节点,比如当i=0时,就最多可能只有1项);而当i值很大时,其对应K桶的项数又很可能会超过k个(当然,覆盖距离范围越广,存在较多节点的可能性也就越大),这里k是为平衡系统性能和网络负载而设置的一个常数,但必须是偶数,比如k=20。在BitTorrent的实现中,取值为k=8。

由于每个K桶覆盖距离的范围呈指数关系增长,这就形成了离自己近的节点的信息多,离自己远的节点的信息少,从而可以保证路由查询过程是收敛。因为是用指数方式划分区间,经过证明,对于一个有N个节点的Kad网络,最多只需要经过logN步查询,就可以准确定位到目标节点。这个特性和Chord网络上节点的finger table划分距离空间的原理类似。

当节点x收到一个PRC消息时,发送者y的IP地址就被用来更新对应的K桶,具体步骤如下:

1.计算自己和发送者的距离:d(x,y) = x?y,注意:x和y是ID值,不是IP地址

2.通过距离d选择对应的K桶进行更新操作。

3.如果y的IP地址已经存在于这个K桶中,则把对应项移到该该K桶的尾部

4.如果y的IP地址没有记录在该K桶中

⑴如果该K桶的记录项小于k个,则直接把y的(IP address,UDP port,Node ID)信息插入队列尾部

⑵如果该K桶的记录项大于k个,则选择头部的记录项(假如是节点z)进行RPC_PING操作

①如果z没有响应,则从K桶中移除z的信息,并把y的信息插入队列尾部

②如果z有响应,则把z的信息移到队列尾部,同时忽略y的信息。

K桶的更新机制非常高效的实现了一种把最近看到的节点更新的策略,除非在线节点一直未从K桶中移出过。也就是说在线时间长的节点具有较高的可能性继续保留在K桶列表中。

采用这种机制是基于对Gnutella网络上大量用户行为习惯的研究结果,既节点的失效概率和在线时长成反比关系(横坐标为分钟,纵坐标为概率):

Gnutella网络中在线时长和继续在线的概率关系

可以明显看出,用户在线时间越长,他在下一时段继续在线的可能性就越高。

所以,通过把在线时间长的节点留在K桶里,Kad就明显增加K桶中的节点在下一时间段仍然在线的概率,这对应Kad网络的稳定性和减少网络维护成本(不需要频繁构建节点的路由表)带来很大好处。

这种机制的另一个好处是能在一定程度上防御DOS攻击,因为只有当老节点失效后,Kad才会更新K桶的信息,这就避免了通过新节点的加入来泛洪路由信息。

为了防止K桶老化,所有在一定时间之内无更新操作的K桶,都会分别从自己的K桶中随机选择一些节点执行RPC_PING操作。

上述这些K桶机制使Kad缓和了流量瓶颈(所有节点不会同时进行大量的更新操作),同时也能对节点的失效进行迅速响应。

五、Kademlia协议操作类型

Kademlia协议包括四种远程操作:PING、STORE、FIND_NODE、FIND_VALUE。

1、PING操作的作用是探测一个节点,用以判断其是否仍然在线。

2、STORE操作的作用是通知一个节点存储一个对,以便以后查询需要。

3、FIND_NODE操作使用一个160bit的ID作为参数。本操作的接受者返回它所知道的更接近目标ID的K个节点的(IP address,UDP port,Node ID)信息。

这些节点的信息可以是从一个单独的K桶获得,也可以从多个K桶获得(如果最接近目标ID的K桶未满)。不管是哪种情况,接受者都将返回K个节点的信息给操作发起者。但如果接受者所有K桶的节点信息加起来也没有K个,则它会返回全部节点的信息给发起者。

4、FIND_VALUE操作和FIND_NODE操作类似,不同的是它只需要返回一个节点的(IP address,UDP port,Node ID)信息。如果本操作的接受者收到同一个key的STORE操作,则会直接返回存储的value值。

注:在Kad网络中,系统存储的数据以对形式存放。根据笔者的分析,在BitSpirit的DHT实现中,其key值为torrent文件的info_hash串,其value值则和torrent文件有密切关系。

为了防止伪造地址,在所有RPC操作中,接受者都需要响应一个随机的160bit的ID值。另外,为了确信发送者的网络地址,PING操作还可以附带在接受者的RPC回复信息中。

六、路由查询机制

Kad技术的最大特点之一就是能够提供快速的节点查找机制,并且还可以通过参数进行查找速度的调节。

假如节点x要查找ID值为t的节点,Kad按照如下递归操作步骤进行路由查找:

1、 计算到t的距离:d(x,y) = x?y

2、 从x的第[㏒d]个K桶中取出α个节点的信息(“[”“]”是取整符号),同时进行FIND_NODE操作。如果这个K桶中的信息少于α个,则从附近多个桶中选择距离最接近d的总共α个节点。

3、 对接受到查询操作的每个节点,如果发现自己就是t,则回答自己是最接近t的;否则测量自己和t的距离,并从自己对应的K桶中选择α个节点的信息给x。

4、 X对新接受到的每个节点都再次执行FIND_NODE操作,此过程不断重复执行,直到每一个分支都有节点响应自己是最接近t的。

5、 通过上述查找操作,x得到了k个最接近t的节点信息。

注意:这里用“最接近”这个说法,是因为ID值为t的节点不一定存在网络中,也就是说t没有分配给任何一台电脑。

这里α也是为系统优化而设立的一个参数,就像K一样。在BitTorrent实现中,取值为α=3。

当α=1时,查询过程就类似于Chord的逐跳查询过程。

α=1时的查询过程

整个路由查询过程是递归操作的,其过程可用数学公式表示为:

这个递归过程一直持续到 Nl =t,或者 Nl 的路由表中没有任何关于t 的信息,即查询

失败。

由于每次查询都能从更接近t的K桶中获取信息,这样的机制保证了每一次递归操作都能够至少获得距离减半(或距离减少1bit)的效果,从而保证整个查询过程的收敛速度为O(logN),这里N为网络全部节点的数量。

当节点x要查询对时,和查找节点的操作类似,x选择k个ID值最接近key值的节点,执行FIND_VALUE操作,并对每一个返回的新节点重复执行FIND_VALUE操作,直到某个节点返回value值。

一旦FIND_VALUE操作成功执行,则对数据会缓存在没有返回value值的最接近的节点上。这样下一次查询相同的 key时就会更加快速的得到结果。通过这样的方式,热门对数据的缓存范围就逐步扩大,使系统具有极佳的响应速度,如图 5所示。

缓存原则

七、数据存放

存放对数据的过程为:

1、 发起者首先定位k个ID值最接近key的节点;

2、 发起者对这k个节点发起STORE操作

3、 执行STORE操作的k个节点每小时重发布自己所有的对数据。

4、 为了限制失效信息,所有对数据在初始发布24小时后过期。

另外,为了保证数据发布、搜寻的一致性,规定在任何时候,当节点w发现新节点u比w上的某些对数据更接近,则w把这些对数据复制到u上,但是并不会从w上删除。

八、节点加入和离开

如果节点u要想加入Kad网络,它必须要和一个已经在Kad网络的节点,比如w,取得联系。

u首先把w插入自己适当的K桶中,然后对自己的节点ID执行一次FIND_NODE操作,然后根据接收到的信息更新自己的K桶内容。通过对自己邻近节点由近及远的逐步查询,u完成了仍然是空的K桶信息的构建,同时也把自己的信息发布到其他节点的K桶中。

在Kad网络中,每个节点的路由表都表示为一颗二叉树,叶子节点为K桶,K桶存放的是有相同ID前缀的节点信息,而这个前缀就是该K桶在二叉树中的位置。这样,每个K桶都覆盖了ID空间的一部分,全部K桶的信息加起来就覆盖了整个160bit的ID空间,而且没有重叠。

以节点u为例,其路由表的生成过程为:

1. 最初,u的路由表为一个单个的K桶,覆盖了整个160bitID空间,最上面的路由表;

2. 当学习到新的节点信息后,则u会尝试把新节点的信息,根据其前缀值插入到对应的K桶中:

① 如果该K桶没有满,则新节点直接插入到这个K桶中;

② 如果该K桶已经满了,

⑴ 如果该K桶覆盖范围包含了节点u的ID,则把该K桶分裂为两个大小相同的新K桶,并对原K桶内的节点信息按照新的K桶前缀值进行重新分配

⑵ 如果该K桶覆盖范围没有包节点u的ID,则直接丢弃该新节点信息

3. 上述过程不断重复,最终会形成表1结构的路由表。达到距离近的节点的信息多,距离远的节点的信息少的结果,保证了路由查询过程能快速收敛。

节点000的路由表生成演化

演示了当覆盖范围包含自己ID 值的K 桶是如何逐步分裂的。

节点0100的K桶分裂过程

当K桶010满了之后,由于其覆盖范围包含了节点0100的ID,故该K桶分裂为两个新的K桶:0101 和0100,原K桶010的信息会根据其其前缀值重新分布到这两个新的K桶中。注意,这里并没有使用160bit的ID值表示法,只是为了方便原理的演示,实际Kad网络中的ID值都是160bit的。

节点离开Kad网络不需要发布任何信息,Kademlia协议的目标之一就是能够弹性工作在任意节点随时失效的情况下。为此,Kad要求每个节点必须周期性的发布全部自己存放的对数据,并把这些数据缓存在自己的k个最近邻居处,这样存放在失效节点的数据会很快被更新到其他新节点上。

相关词汇

网络传输协议
网络传输协议
节点
UDP
分布式散列表
广域网
虚拟网络
节点
节点
节点
节点
端口号
存储
网络节点
冗余
美国纽约大学
哈希表
Chord
CAN
Kad
XOR
DHT
路由
二叉树
节点
二叉树
节点
节点
节点
节点
表格
节点
数据项
节点
节点
节点
节点
队列
节点
队列
队列
节点
节点
节点
节点
节点
节点
存储
网络地址
节点
递归
节点
节点
节点
节点
节点
节点
邻近节点
二叉树
叶子节点
节点
节点
节点
节点
快速收敛
路由表
节点
节点
数据缓存
电脑版