详述kad和ed2k的之间的关系

2008-7-29来源:eMule电驴教程人气:12296

Kad是Kademlia的简称,eMule(电驴)的官方网站在2004年2月27日正式发布的 eMule v0.42b中,Kad开始正式内嵌成为eMule的一个功能模块,可以说从这个版本开始eMule便开始支持Kad网络了。
Kad的出现,结束了之前edonkey时代,在ed圈里只存在着ED2K一种网络的模式,它通过新的协议开创并形成了自己的kad网络,使之和ED2K网络并驾齐驱,而且它还完全支持两种网络,可以在两种网络之间通用。Kad同样也属于开源的自由软件。它的程序和源代码可以在官方网站http://www.emule-PRoject.net上下载。

Kad网络拓扑的最大特点在于它完全不需要服务器,我们都知道传统的ed2k网络需要服务器支持作为中转和存储hash列表信息,kad可以不通过服务器同样完成ed2k网络的一切功能,你唯一要做的就是连线上网,然后打开kad。Kad需要UDP端口的支持,之后Emule会自动按照客户端的要求,来判断它能否自由连线,然后同样也会分配给你一个id,这个过程和我们ed2k的高id和低id检查很像,不过这个id所代表的意义不同于ed2k网络,它代表一个是否“freely”的状态。

Kad和ed2k网络有着完全不同的观念但是相同的目的: 都是搜索和寻找文件的源。 Kad网络的主要的目标是做到不需要服务器和改善可量测性。相对于传统的ed2k服务器只能处理一定数量的使用者(我们在服务器列表也都看到了,每个服务器都有最大人数限制),而且如果服务器比较大连接人数过多,还会严重的的拖垮网络。而Kad能够自我组织,并且自我调节最佳的使用者数量以及他们的连接效果。因此, 它更能使网络的损失达到最小。由于具备了以上所叙述的功能,Kad也被称之为Serverless network(无服务器网络)。虽然目前一直处于开发阶段(alpha stage) 。但毫无疑问,它无可比拟的优势,将会使它成为p2p的明天。

可能很多朋友会关注, kad网络没有高低id的计算原则,是否对于低id来言就畅通无阻了呢?

我们大家知道在ed2k网络里面,我们的id是通过ip进行如下的算法计算得出的
设我们的IP = A.B.C.D
那么我们的ID number= A + 256*B + 256*256*C + 256*256*256*D
low ID的产生是由于我们的ID计算结果小于16777216.
即 ID number= A + 256*B + 256*256*C + 256*256*256*D < 16777216

Kad的 id计算原则并不是象上面那样,他更关注我们是否open和freely。
但是kad里面是如何计算我们的id呢?
事实上它的计算方法是这样
ID number=256*256*256*A+256*256*B+256*C+D
所以kad其实也有高低id的分别。所以内网用户在使用的时候依旧无法达到内网用户完全穿透网络的效果,而且目前来看,还存在着kad模块引入,导致占用系统资源会变大以及会突然产生Memory Leak的问题,对于内存的控制,目前emule做的效果还是不好。

其实kad本身有一个nodes.dat文件,也叫做节点文件,这里面存放了我们在Kad网络中的邻居节点,我们都是通过这些节点来进入Kad网络的。其实kad的网络倒更像是overnet和Kazaa网络,有兴趣的朋友大家可以对比看看。Kad网络提供了帮助寻找节点以及记录节点的机制。

下面我们来说说这个机制的原理:
Kad拥有一个160bit的ID,每一个节点送出的讯息都必须包含此ID。每一个节点都必须记录一个资料来保存已经存在的节点,资料的格式是 (IP address, UDP port, Node ID),节点所必须负责的范围是2的i次方及2的i+1次方,i的范围是0 < i <160,这个结构叫做k-bucket,该结构会形成一个tree的形状,每一次接收到新的信息时,各个节点都必须更新k-bucket内的资料,透过k-bucket结构我们可以保证所有的节点状态都是新的,而且一定会知道这个节点在哪里。

Kademlia网络提供四种Potocol(RPC)
(1)PING 测试是否节点存在
(2)STORE存储通知的资料
(3)FIND_NODE 通知其他节点帮助寻找node
(4)FIND_VALUE 通知其他节点帮助寻找Value
而当每一个指令被接受到后,每一个节点都会到k-bucket上搜寻,通过这样的结构,kad提供一个方便快速且可以被保证在logN次数下找到所需的节点。

通俗的来讲就是在kad网络中,我们每个emule用户端只负责处理一小部分搜索和查找源的工作。分配这些工作的时候,通过我们每个用户端的唯一的ID和搜索文件的hash值之间的匹配来决定。比如像我猜我猜我猜猜.rm这个文件由用户小王来负责(通过该文件的hash值来决定),那么任何其他用户在下载这个文件的时候都会告诉其他用户,小王有这个文件,其他用户去下载这个文件的时候也会询问小王,小王也会告诉他们谁正在共享这个文件,这样kad找源的工作就完成了。搜索时候的方法也差不多,只不过是每个人负责一个关键字。

整个过程有点像在照线索循序问路而找到正确方向,而不是路上随便到处抓人在问路。而每个地方里的网络相关信息,则会随着电脑及文件的加入而持续更新。好处在于让你可以搜索整个网络,而不只是在某一地区。目前来讲,这个机制和算法是绝对领先而且非常优秀的。

如何找到用户小王则是通过将用户id异或的方式,两个id的二进位异或值决定他们之间的逻辑距离,如1100距离1101要比距离1001近。那么当一个用户加入kad后,首先通过一个已知的用户找到一批用户的id和ip地址和端口。当该用户要寻找一个特定用户A的时候,该用户先询问几个已知的逻辑距离较A较近的用户,如B用户,C用户,D用户,B,C,D会告诉该用户他们知道的更加近的用户的id和ip地址和端口,同理类推,这个用户最终就能找到A。所以寻找的次数会在logN数量级,这里N代表询问的人数。

其实也就是一种分散式杂凑的方法,基本上是对网络上某一特定时刻的文件进行快照(snapshot),然后将这些信息分散到整个网络里。 为了找到特定的文件,搜索的要求先到达网络上的任何一台电脑上,然后这台电脑就会再将它转到另一台有更多文件信息的电脑。第三台电脑可能就拥有文件本身——或者也可能再继续转到其他有正确信息的电脑。采用这种方法,通常只需要跳转两到三次,便可以轻松查找到所需文件。

以上几个部分,便是对于kad作用原理以及算法的分析,可能好多人看了之后头大,那么我们普通用户到底该注意些什么呢?

很简单,你要作的就是再使用emule的时候打开kad,你会发现有两个明显的特点
(1)你的下载速度会加快
(2)你的下载文件的源会增加
以上两条对于lowid和经常下载源在国外的文件用户,效果就更为突出,特别对于在ed2k网络中只有几个源或者没有源的文件,在kad网络中,一般都能找到源,所以说你使用了emule下载文件,基本上不会出现没有源的请况,无论多长时间,差别只是源的多少个数问题,由于kad网络都是自动配置的,所以你丝毫不用分心,那么索性我们就打开它,何乐而不为呢?

另外对于我们搜索的时候,如果采用kad网络搜索,多数情况下找到的文件源会远远多于ed2k的全局搜索,对于大家都是一个明智的选择。

虽然,目前kad还处在试验阶段,但是他的崛起是迟早的事情,我从kad一开始推出就一直在使用,开始的时候用的人不多,效果不明显。但是目前来讲,再我发帖前,我还做过测试现在kad的使用人数已经突飞猛进,我随便找了一期我猜我猜我猜猜来做测试,发现kad找到源的比例已经占了总源比例的30%,甚至更多,时间越长效果越明显。所以,在这里呼吁大家都打开kad,让我们的速度再迈上一个台阶.早日迎接kad天下的到来!
Ps:文中部分技术资料,来自于国外的网站,原文是英文的,我翻译过来,然后引用,由于本人英文水平有限,出现的错误请大家多多包涵!