Kademlia 协议原理简介 （k7mmx@tom.com）
一、前言
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是随机产生的），六、路由查询机制
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。
图4：α＝1时的查询过程
整个路由查询过程是递归操作的，其过程可用数学公式表示为：
这个递归过程一直持续到 Nl ＝t，或者 Nl 的路由表中没有任何关于t 的信息，即查询
失败。
由于每次查询都能从更接近t的K桶中获取信息，这样的机制保证了每一次递归操作都能够至少获得距离减半（或距离减少1bit）的效果，从而保证整个查询过程的收敛速度为O(logN)，这里N为网络全部节点的数量。
当节点x要查询