Kademlia原理介绍

http://blog.csdn.net/chenbuaa/article/details/2301638

 

Kademlia: A Peer To Peer Information Systems Based On The

XOR Metric, Petar Maymounkov and David Mazieres, 2002.

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



Kad概述



首先, 读者要清楚的是, Kademlia是用于信息查询的, 而不是一个文

件传输工具. 如何实现信息查询的功能呢? 首先, 信息的发布者根据

某个规则将指定的信息发布到指定的位置; 然后, 信息查询者根据这

个规则和自己所需要的信息, 找到那个指定的位置, 并在那里找到信

息. 电骡的Kad里, 信息就是文件的源的信息, 信息查询就是找某文件

的源. 下面结合电骡的实际情况来讲解这个过程.

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



结点的ID



在电骡的Kad网络里, 每个用户都有一个ID号, 这个ID是128位的, 它

是在你第一次使用Kad时随机生成的. 出现两个相同ID的概率实在太

小了, 这几乎不可能发生. 我们可以认为, 在Kad网络里, 没有两个用

户具有相同的ID号, 除非你故意那样做.



每个用户都是Kad网络里的一个结点, 因此用户的ID就是结点的ID.

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



XOR



XOR即二进制的"异或"操作, 它是这样定义的:

1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, 0 XOR 0 = 0.

两个二进制数相异或, 就是将这两个数的对应位做异或. 举例来说,

10110 XOR 11100 = 01010



异或有一个重要的性质: 设 a, b, c 为任意三个数. 则:

(a XOR b) = (a XOR c) 当且仅当 b = c

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



结点间距离



Kad网络上任意一个用户可用其结点ID来表示. 设 a, b 是两个结点,

则 a 与 b 之间的距离定义为 D(a,b) = a XOR b. 由上面介绍的异或

的性质可知: 给定一个结点 a 和距离 L, 有且仅有一个结点 b, 使得

D(a,b) = L. 这个性质太优秀了, 它提供了在Kad网络上进行度量的可

靠方法. 因为, 假设你是Kad上的一个用户, 那么Kad上所有其他用户

都可按照与你间距离的远近而排成一条长队. 如果已知另一个结点的

ID, 那么你很容易判断出他在这条长队中的位置; 如果给定一个距离,

那么你很容易从这条长队里找出与你的距离最接近给定距离的结点.

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



结点查找



因为有了可度量的距离, 查找某个结点就比较容易了. Kad上用户很多,

而且加入和退出Kad是频繁发生的, 因此一个结点不可能记录下所有结

点的信息. 每个结点都维护着一个联系人列表, 这张表的结构大概为:

+--------+-----------+---------+

|联系人ID| IP地址 | 端口 |

+--------------------+---------+

| a | a的IP地址 | a的端口 |

+--------+-----------+---------+

| b | b的IP地址 | b的端口 |

+--------+-----------+---------+

| ... | ... | ... |

+--------+-----------+---------+

| n | n的IP地址 | n的端口 |

+--------+-----------+---------+



联系人的选择不是完全随机的, 而是有倾向性的, 离自己越近的结点

越容易被选到联系人列表里. 也就是说, 每个结点都对自己附近的情

况非常了解, 而随着距离的增大, 了解的程度就降低了. 这很像交朋

友, 离自己越近的人群里, 朋友就越多. 联系人列表是不断更改的,

不在线的联系人将被删除, 被新找到的联系人所代替.



要查找某个结点a时, 如果a不在我的联系人列表里, 我就从联系人列

表里找到与a距离最近的结点b, 然后向b查询a. 如果b认识a, 就把a的

IP地址和端口告诉我; 如果b也不认识a, b就从自己的联系人列表里找

到与a距离更近的c, 然后我向c查询a. 这个递归过程不断重复, 直到

找到a为止.



结点查找是进行信息存储和查询的基础.

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



信息的存储



现在, 来解决信息的存储问题, 即信息发布者根据某个规则将自己要

发布的信息存储于Kad上的某个位置. 如果每条信息也有一个128位的

ID, 那么只要将信息存储于对应的结点上, 这个问题就完美地解决了!

在电骡里, 这简直太方便了, 因为每个文件都有一个128位的Hash值!

电骡的Kad里, 每条文件发布信息有三个最重要参数:

文件的Hash值, 发布者IP地址, 发布者端口.

发布者将该条信息存储于 结点ID 恰等于 文件Hash值 的那个结点上.

所有发布相同文件的人, 都将自己的IP地址和端口存储在这个结点上

了. 反过来, 对于任意一个结点a, 他存储了 Hash值为a的文件 的全

体发布者的IP地址和端口.

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



信息的查询



如果前面的内容你都理解了, 那么这部分就很容易: 比如你要查找某

文件的源, 首先你要知道该文件的Hash值, 然后去结点ID等于此Hash

值的那个结点, 让他告诉你发布者(源)的IP地址和端口就行了.

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



一个小问题



通常, 并不能保证对应于某个 文件Hash值 的结点一定在Kad网络里.

也许此结点未上线, 也许此结点ID尚未分配. 这时候如何存储信息呢?

实际上在存储信息时, 并不只存储在那唯一的结点上, 而是存储在与

目标结点距离比较近的一群结点上. 越接近目标结点, 该信息的保存

时间就越久.

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



加入Kad网络



我如何进入Kad网络呢? 我必须事先知道某个已经位于Kad上的用户的

IP地址和端口, 然后通过该用户将自己介绍到Kad网络中. 进入Kad后,

通过一系列的结点查找, 来建立我的联系人列表.