Kademlia协议原理简介
一、前言
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值的最短前缀唯一的确定。
对于任意一个节点，都可以把这颗二叉树分解为一系列连续的，不包含自己的子树。最高层的子树，由整颗树不包含自己的树的另一半组成；下一层子树由剩下部分不包含自己的一半组成；依此类推，直到分割完整颗树。图1就展示了节点0011如何进行子树的划分：
图1：节
点0011的子树划分
虚线包含的部分就是各子树，由上到下各层的前缀分别为0，01，000，0010。 Kad协议确保每个节点知道其各子树的至少一个节点，只要这些子树非空。在这个前提下，每个节点都可以通过ID值来找到任何一个节点。这个路由的过程是通过所谓的XOR（异或）距离得到的。
图2就演示了节点0011如何通过连续查询来找到节点1110的。节点0011通过在逐步底层的子树间不断学习并查询最佳节点，获得了越来越接近的节点，最终收敛到目标节点上。
图2：通过ID值定位目标节点
需要说明的是，只有第一步查询的节点101，是节点0011已经知道的，后面各步查询的节点，都是由上一步查询返回的更接近目标的节点，这是一个递归操作的过程。
三、节点间距离
Kad网络中每个节点都有一个160bit的ID值作为标志符，Key也是一个160bit的标志符，每一个加入Kad网络的计算机都会在160bit的key空间被分配一个节点ID（node ID）值（可以认为ID是随机产生的），
判断两个节点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值的所有查询都会逐步收敛到同一个路径上，而不管查询的起始节点位置如何。这样，只要沿着查询路径上的节点都缓存这个
四、K桶
Kad的路由表是通过一些称之为K桶的表格构造起来的。这有点类似Tapestry技术，其路由表也是通过类似的方法构造的。
对每一个0≦i≦160，每个节点都保存有一些和自己距离范围在区间内的一些节点信息，这些信息由一些(IP address,UDPport,Node ID)数据列表构成（Kad网络是靠UDP协议交换信息的）。每一个这样的列表都称之为一个K桶，并且每个K桶内部信息存放位置是根据上次看到的时间顺序排列，最近（least-recently）看到的放在头部，最后（most-recently）看到的放在尾部。每个桶都有不超过k个的数据项。 一个节点的全部K桶列表如表1所示： I 距离 邻居
0 0 1[2 , 2) 0-1 (IP address,UDPport,Node ID) ...... 0-k (IP address,UDPport,Node ID)
1 1 2[2 , 2) 1-1 (IP address,UDPport,Node ID) ...... 1-k (IP address,UDPport,Node ID)
2 2 3[2 , 2) (IP address,UDPport,Node ID) ...... 2-1 (IP address,UDPport,Node ID) 2-k ……
i 1[2 , 2) i i+ i-1 (IP address,UDPport,Node ID) ...... i-k (IP address,UDPport,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,UDPport,Node ID)信息插入队列尾部
⑵如果该K桶的记录项大于k个，则选择头部的记录项（假如是节点z）进行RPC_PING操作
①如果z没有响应，则从K桶中移除z的信息，并把y的信息插入队列尾部 ②如果z有响应，则把z的信息移到队列尾部，同时忽略y的信息。
K桶的更新机制非常高效的实现了一种把最近看到的节点更新的策略，除非在线节点一直未从K桶中移出过。也就是说在线时间长的节点具有较高的可能性继续保留在K桶列表中。 采用这种机制是基于对Gnutella网络上大量用户行为习惯的研究结果，既节点的失效概率和在线时长成反比关系，如图3（横坐标为分钟，纵坐标为概率）：
图3：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操作的作用是通知一个节点存储一个
这些节点的信息可以是从一个单独的K桶获得，也可以从多个K桶获得（如果最接近目标ID的K桶未满）。不管是哪种情况，接受者都将返回K个节点的信息给操作发起者。但如果接受者所有K桶的节点信息加起来也没有K个，则它会返回全部节点的信息给发起者。 4、FIND_VALUE操作和FIND_NODE操作类似，不同的是它只需要返回一个节点的(IP address,UDPport,Node ID)信息。如果本操作的接受者收到同一个key的STORE操作，则会直接返回存储的value值。
注：在Kad网络中，系统存储的数据以
为了防止伪造地址，在所有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的逐跳查询过程，如图4。