Kademlia协议原理简介.doc

《Kademlia协议原理简介.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Kademlia协议原理简介2006.2.20一、前言Kademlia协议（以下简称Kad）是美国纽约大学的PetarP.Maymounkov和DavidMazieres.在2002年发布的一项研究结果《Kademlia:Apeerto-peerinformationsystembasedontheXORmetric》。简单的说，Kad是一种分布式哈希表（DHT）技术，不过和其他DHT实现技术比较，如Chord、CAN、Pastry等，Kad通过独特的以异或算法（XOR）为距离度量基础，建立了一种全新的DHT拓扑结构，相比于其他算法，大大提高了路由查询速度。在20

2、05年5月著名的BiTtorrent在4.1.0版实现基于Kademlia协议的DHT技术后，很快国内的BitComet和BitSpirit也实现了和BitTorrent兼容的DHT技术，实现trackerless下载方式。另外，emule中也很早就实现了基于Kademlia类似的技术（BT中叫DHT，emule中也叫Kad，注意和本文简称的Kad区别），和BT软件使用的Kad技术的区别在于key、value和nodeID的计算方法不同。二、节点状态Kad网络中每个节点都有一个160bit的ID值作为标志符。节点ID的生成，各种具体的应用软件有不同的实现方法，一般

3、是选择一个不重复的值进行SHA－1计算，这个值可以是用户的IP地址，或者只是简单的随机生成。在Kad网络中，所有节点都被当作一颗二叉树的叶子，并且每一个节点的位置都由其ID值的最短前缀唯一的确定。对于任意一个节点，都可以把这颗二叉树分解为一系列连续的，不包含自己的子树。最高层的子树，由整颗树不包含自己的树的另一半组成；下一层子树由剩下部分不包含自己的一半组成；依此类推，直到分割完整颗树。图1就展示了节点0011如何进行子树的划分：49图1：节点0011的子树划分虚线包含的部分就是各子树，由上到下各层的前缀分别为1，01，000，0010。Kad协议确保每个节点知道

4、其各子树的至少一个节点，只要这些子树非空。在这个前提下，每个节点都可以通过ID值来找到任何一个节点。这个路由的过程是通过所谓的XOR（异或）距离得到的。图2就演示了节点0011如何通过连续查询来找到节点1110的。节点0011通过在逐步底层的子树间不断学习并查询最佳节点，获得了越来越接近的节点，最终收敛到目标节点上。图2：通过ID值定位目标节点需要说明的是，只有第一步查询的节点101，是节点0011已经知道的，后面各步查询的节点，都是由上一步查询返回的更接近目标的节点，这是一个递归操作的过程。由于各节点路由信息的不确定性（节点动态加入和离开引起），图2只是展示了多

5、种可能搜索路径的一个具体实现。三、节点间距离Kad网络中每个节点都可以（但不是必须）保存一个对，这里Key是一个160bit的标志符。每一个加入Kad网络的计算机都会在160bit的命名空间被分配一个节点ID（nodeID）值，value值就存放在ID值和key值相同或“最”接近的那个节点上。49判断两个节点x,y的距离远近是基于数学上的异或的二进制运算，d(x,y)=x⊕y，既对应位相同时结果为0，不同时结果为1。例如：010101XOR110001-------------100100则这两个节点的距离为32＋4＝36。显然，高位上数值的

6、差异对结果的影响更大。对于异或操作，有如下一些数学性质：l        d(x,x)=0l        d(x,y)>0，ifx≠yl        ∨x,y:d(x,y)=d(y,x)l        d(x,y)+d(y,z)≧d(x,z)l        d(x,y)⊕d(y,z)=d(x,z)l        ∨a≧0,b≧0,a+b≧a⊕b正如Chord的顺时针旋转的度量一样，异或操作也是单向性的。对于任意给定的节点x和距离⊿≧0，总会存在一个精确的节点y，使得d(x,y)=⊿。另外，单向性也确保了对于同一个key值的所有查询都会逐步收敛到同一个路径

7、上，而不管查询的起始节点位置如何。这样，只要沿着查询路径上的节点都缓存这个对，就可以减轻存放热门key值节点的压力，同时也能够加快查询响应速度。这种新颖计算方法最大的优点在于，它提供了一种在Kad网络上进行可靠距离度量的方法。假如Kad网络上所有其他用户都按照和你之间距离的远近而排成一条长队，如果已知另一个结点的ID，那么你很容易计算出他在这条长队中的位置；如果给定一个距离，你也能很容易从这条长队里找出与你的距离最接近给定距离的那些结点。四、K桶Kad的路由表是通过一些称之为K桶的列表构造起来的。这有点类似Tapestry技术，其路由表也是通

8、过类似的方