通俗讲解 Kademlia 原理

古城微笑少年丶 2022-06-04 05:10 335阅读 0赞

我这好久没有学术性的文章出现了。。翻看了下日志，最早的是07年发表的做PCB电路板的日志，之后是08年PHP网页制作，之后是09年C\# 的GPS定位软件（虽然自己都没怎么用过。。。）  
今天就通俗介绍一下一个最常用，最简洁，最实用P2P的索引算法---Kademlia协议（简称 Kad）。 使用BT 的同学经常会发现DHT这个缩写，使用电驴的同学就会发现KAD缩写。 DHT的全称叫哈希表（Distributed Hash Table），KAD就是Kademlia的缩写。 Kademlia是DHT的一种，其实BT和电驴都是使用Kademlia 协议，只是电驴中加密方式不同。  
好了，前面只是简单引入一下基本问题。 下面我将非常非常非常非常通俗俗俗俗的给大家介绍Kademlia协议的知识。目的只是在于让使用p2p软件的非专业同学对此协议有一个了解，主要针对对p2p好奇的同学。因为网上关于Kademlia的资源不是很多，而且都是给专业人准备的，很抽象笼统。 所以一般同学理解会有困难。 专业同学直接按（http://emule-fans.com/emule-kademlia-protocol-document/）连接参考Kademlia 协议原文。  
在进入正题之前，先请看下面的一张图片。（我不是很懂的，感谢张junyuan同学提供精彩图片，这里只用来作为讲解工具，没有其他意思）熟悉的同学可能很容易看出这张图片是某国比较出名的影星集合照。 让我们的思绪回到纯真的高中或大学年代。。。。  
![p_large_vV3L_020300078e072d12.jpg][]  
  
  
首先，什么是P2P（peer to peer，点对点）？ 简而言之，班上某个同学（假设班长）有上面某位明星影视作品一部。 你知道了，你找到该班长，复制一份。。。这就是P2P。  
最早的P2P是使用索引服务器的。 什么是索引服务器？ -- 班级很多同学有不同影视作品N部。但是你想找到某人的某部，这么多同学你怎么去找了拷贝呢？ 这时候班上有个同学站起来了（还假设班长，班长嘛！），我来给大家登记信息。于是班长打开Excel，同学们过来，大家资源到我这登记一下，要找资源的同学可以直接来我这边来索引。这时候，班长所作的工作就是索引服务器。 由班长的好处是什么呢？ 简单，方便，查询次数是O(1)，也就是你唯一查询就可以找到目标。 但是坏处也是显而易见的，首先，班长很忙，其次，班长很脆弱，万一班长为班级出头被人家K了。。。不过最受不了的是，班主任发现班长的电脑里面文件，然后给delete了（04年电骡最大服务器Razorback2 由于侵权被关闭）。  
所以需要一个更好的解决方案来处理。这时候就是Kademlia协议出现了（还有CAN，CHORD等），其实他不能算一个协议，就是一个查询方法吧。 班长不帮你查了，你总要自己找资源吧！

首先，班上每个同学有学号，这是入学的时候就给你唯一的ID。其次，对资源用key代替学号和key都是数值，在上面的途中就可以看出，个人的资源所代的key（eMule用160bits，号码多好记，又安全，你在班上问8号在哪不会有人管你，你要是问松岛枫在哪。。。嘿嘿，等着进办公室吧）。 我们假设班级有100个人。那每个人都有号码，我们就从1-100编号。这样的话学号和资源号是重复的。 Kademlia的思想就是把某一个资源的信息，给和资源key相同id的人保管。 举个例子，比如上面8号（石川XX）， 有8号资源的人不知一个，比如班上1号，2号，10号等等。 但是8号石川（key）的号码，和班级8号同学（假设文艺委员）的号码是一样的，于是文艺委员就记下了所有有8号资源的人的信息（座位IP，资源在哪个盘port，学号ID）。 如果你想要找8号资源的时候就去找

8号同学文艺委员。 然后8号同学文艺委员就告诉资源在1号同学那，他坐在2组三排外面一个。直接去他座位上拷就行了。。。。。  
不过问题又来了，你怎么知道8号文艺委员坐在哪呢？（现在为了防止不良竞争，学号都不公开的，你知道他名字但不晓得学号）。 怎么办？ 好办，你自己不是也有张表嘛！假设你是60号， 你有资源60号（xx美子）的资源表。 你从你的表中找出靠8号最近的人的位置。比如你表中记录有 10号，坐在3组2排外面， 还有6号，坐在1组9排里面一个。你跑过去问他们：知道8号在哪不？！（这时候是2个人并行查询，也可以三个，或更多）他们就翻自己的档案，再返回他们最靠近8号的那个人给你。比如7号，9号，或7号，11号。 这里就有些难理解了。。。。那你就先认为他们返回8号坐的位置给你，你可以直接去拷了。 Ok，搞定，考到片子了。。。。  
   
现在为什么找7号和10号的时候他们返回的是两个最相近的人的资料，而不是确切的资料。 因为你要考虑到万一有人没来呢（实际情况是ID没有分配给节点）。 比如8号今天生病没来，你又想拷。那不是找不到下文了？不用着急，其实8号的信息还在附近的人那备份了。 比如在7号那。当6号，和10号返回相同的7号的时候，就说明7号那边存有相关资料了。  
   
下面一个问题就是如何自己记录信息（路由表）。 Kademlia 使用k 桶（buckets）。 在Kademlia里面使用 160bits ID，所以每个点维160个list。 比如k=2，就是你的一张list里面最多存两个数据。 数据范围是按指数增加。比如，你是25号，跟你距离是1（24，26，）记录在第一行， 2-4（22，23，27，28）的只记录两个，4-8（。。。。），可以看出，距离越近，其实记录的数据越多，这样一来，就可以方便其他人来找啦。这段还是有些抽象。。。更新列队的时候，如果新访问的那个人不在你k桶，那就塞到尾部。如果k桶满了，看看问问这个k桶的第一个人还在不在，如果不在的话就删掉，要是在的话，把第一个人移到最后，新来的不要。 这个意思是约是经常在线的人就越会经常在线。。。宅男也废电的。。。。  
原理基本就讲完了。 Kademlia 有一个特别之处就是使用异或测算距离。  
   
   
下面是我从我们学校偷出来的例子。。。嘿嘿。网上没有什么好的例子，更本就没有例子。。。把下面ID改为01110 ，打印错误  
  
![1.JPG][]  
  
  
![2.JPG][]  
  
  
![3.JPG][]  
  
  
![4.JPG][]  
  
  
![5.JPG][]  
  
  
![6.JPG][]  
  
  
![7.JPG][]  
  
  
![9.JPG][]  
  
  
   
csdn http://hi.csdn.net/mpanxiao

[p_large_vV3L_020300078e072d12.jpg]: http://bf0lvw.blu.livefilestore.com/y1pziXRUkKKFwRwbW71-oSRCuqNJGmUCWtIRp9DQLqTKnTLJjrLkAnC3TDaUMHZSq7k-_ROBucx8ZqUqxA1Q5_NEMVudAR4kIYP/p_large_vV3L_020300078e072d12.jpg
[1.JPG]: http://public.blu.livefilestore.com/y1pgCQ2VkAxqpORA84O78HqEg18qi6ZmjwVteExH9JnP5P4q291qAqPj5fwcI5GmI2VT6KRHo7rRpFjJMUfZqQgzA/1.JPG
[2.JPG]: http://public.blu.livefilestore.com/y1p5VtgZl30DAqg3vWcAVR4xfFMdhEBWPgsBX1dvDvguw6Nurkggy7M0UIfigpU763aaCBMHbUD1pU2tbZPmTF6FA/2.JPG
[3.JPG]: http://public.blu.livefilestore.com/y1pvJSjWPN_Y0UViOP6Hc4w6DrvmmUdfYd_by9XLxhoYREx3uqImrunZYIuElDOP3rfcMcXCpCWKoATrKdZyDHW-A/3.JPG
[4.JPG]: http://public.blu.livefilestore.com/y1pKr3M56DB5n4hmjgOFGBNIvlb7kCbeyVmHMS0xzqIWr2kUosutHL63-JAp1WoaaxcDA_8unTlOLqj1OxQ2bq3tw/4.JPG
[5.JPG]: http://public.blu.livefilestore.com/y1pfxQaftI6n68QbNYbuRsjcUB5oNdtu5p1n26rgjWcl858JJLTo1ejkwqompJ7wzJAGqwm9c_ClCn8vjKHi23fhA/5.JPG
[6.JPG]: http://public.blu.livefilestore.com/y1pnYMejERY4y68gOLBSr3G5saEg_fp2snnmbqNzpqE7XCySI5IxxZMh_-Tr_5MipKReWJH1-y7htQpw7nspiif3A/6.JPG
[7.JPG]: http://public.blu.livefilestore.com/y1p0kANRmkl6jkvUupf52WL5DdeVC9uzOe8sPLwHamkeV78O9YC4TuJ0jgKUxu_rzKtv8m6ayzbONFSKSxQ1oOiUw/7.JPG
[9.JPG]: http://public.blu.livefilestore.com/y1pfv_aLF9-owyyT8BuVYpPd2HER-rFs3TBLLYo9Zn8xoQkdm_Nu-ZBEd2YyyJSZc86Pj0Z6UeImd5vDEkYh8nHoA/9.JPG