前两天在网上看到世界知名的电骡服务器Razorback 2被查封、4人被拘禁的消息，深感当前做eMule / BitTorrent等P2P文件交换软件的不易。以分布式哈希表方式(DHT，Distributed Hash Table)来代替集中索引服务器可以说是目前可以预见到的为数不多的P2P软件发展趋势之一，比较典型的方案主要包括：CAN、CHORD、 Tapestry、Pastry、Kademlia和Viceroy等，而Kademlia协议则是其中应用最为广泛、原理和实现最为实用、简洁的一种，当前主流的P2P软件无一例外地采用了它作为自己的辅助检索协议，如eMule、Bitcomet、Bitspirit和Azureus等。鉴于 Kademlia日益增长的强大影响力，今天特地在blog里写下这篇小文，算是对其相关知识系统的总结。
1. Kademlia简述
Kademlia(简称Kad)属于一种典型的结构化P2P覆盖网络(Structured P2P Overlay Network)，以分布式的应用层全网方式来进行信息的存储和检索是其尝试解决的主要问题。在Kademlia网络中，所有信息均以的哈希表条目形式加以存储，这些条目被分散地存储在各个节点上，从而以全网方式构成一张巨大的分布式哈希表。我们可以形象地把这张哈希大表看成是一本字典：只要知道了信息索引的key，我们便可以通过Kademlia协议来查询其所对应的value信息，而不管这个value信息究竟是存储在哪一个节点之上。在eMule、 BitTorrent等P2P文件交换系统中，Kademlia主要充当了文件信息检索协议这一关键角色，但Kad网络的应用并不仅限于文件交换。下文的描述将主要围绕eMule中Kad网络的设计与实现展开。
2. eMule的Kad网络中究竟存储了哪些信息?
只要是能够表述成为字典条目形式的信息Kad网络均能存储，一个Kad网络能够同时存储多张分布式哈希表。以eMule为例，在任一时刻，其Kad网络均存储并维护着两张分布式哈希表，一张我们可以将其命名为关键词字典，而另一张则可以称之为文件索引字典。
a. 关键词字典：主要用于根据给出的关键词查询其所对应的文件名称及相关文件信息，其中key的值等于所给出的关键词字符串的160比特SHA1散列，而其对应的value则为一个列表，在这个列表当中，给出了所有的文件名称当中拥有对应关键词的文件信息，这些信息我们可以简单地用一个3元组条目表示：(文件名，文件长度，文件的SHA1校验值)，举个例子，假定存在着一个文件 “warcraft_frozen_throne.iso”，当我们分别以“warcraft”、“frozen”、“throne”这三个关键词来查询 Kad时，Kad将有可能分别返回三个不同的文件列表，这三个列表的共同之处则在于它们均包含着一个文件名为 “warcraft_frozen_throne.iso”的信息条目，通过该条目，我们可以获得对应iso文件的名称、长度及其160比特的SHA1校验值。
b. 文件索引字典：用于根据给出的文件信息来查询文件的拥有者(即该文件的下载服务提供者)，其中key的值等于所需下载文件的SHA1校验值(这主要是因为，从统计学角度而言，160比特的SHA1文件校验值可以唯一地确定一份特定数据内容的文件)；而对应的 value也是一个列表，它给出了当前所有拥有该文件的节点的网络信息，其中的列表条目我们也可以用一个3元组表示：(拥有者IP，下载侦听端口，拥有者节点ID)，根据这些信息，eMule便知道该到哪里去下载具备同一SHA1校验值的同一份文件了。
3. 利用Kad网络搜索并下载文件的基本流程是怎样的?
基于我们对eMule的Kad网络中两本字典的理解，利用Kad网络搜索并下载某一特定文件的基本过程便很明白了，仍以 “warcraft_frozen_throne.iso”为例，首先我们可以通过warcraft、frozen、throne等任一关键词查询关键词字典，得到该iso的SHA1校验值，然后再通过该校验值查询Kad文件索引字典，从而获得所有提供 “warcraft_frozen_throne.iso”下载的网络节点，继而以分段下载方式去这些节点下载整个iso文件。
在上述过程中，Kad网络实际上所起的作用就相当于两本字典，但值得再次指出的是，Kad并不是以集中的索引服务器(如华语P2P源动力、 Razorback 2、DonkeyServer 等，骡友们应该很熟悉吧)方式来实现这两本字典的存储和搜索的，因为这两本字典的所有条目均分布式地存储在参与Kad网络的各节点中，相关文件信息、下载位置信息的存储和交换均无需集中索引服务器的参与，这不仅提高了查询效率，而且还提高了整个P2P文件交换系统的可靠性，同时具备相当的反拒绝服务攻击能力；更有意思的是，它能帮助我们有效地抵制FBI的追捕，因为俗话说得好：法不治众…看到这里，相信大家都能理解“分布式信息检索”所带来的好处了吧。但是，这些条目究竟是怎样存储的呢?我们又该如何通过Kad网络来找到它们?不着急，慢慢来。
4. 什么叫做节点的ID和节点之间的距离?
Kad网络中的每一个节点均拥有一个专属ID，该ID的具体形式与SHA1散列值类似，为一个长达160bit的整数，它是由节点自己随机生成的，两个节点拥有同一ID的可能性非常之小，因此可以认为这几乎是不可能的。在Kad网络中，两个节点之间距离并不是依靠物理距离、路由器跳数来衡量的，事实上，Kad网络将任意两个节点之间的距离d定义为其二者ID值的逐比特二进制和数，即，假定两个节点的ID分别为a与b，则有：d=a XOR b。在Kad中，每一个节点都可以根据这一距离概念来判断其他节点距离自己的“远近”，当d值大时，节点间距离较远，而当d值小时，则两个节点相距很近。这里的“远近”和“距离”都只是一种逻辑上的度量描述而已；在Kad中，距离这一度量是无方向性的，也就是说a到b的距离恒等于b到a的距离，因为a XOR b==b XOR a
5. 条目是如何存储在Kad网络中的?
从上文中我们可以发现节点ID与条目中key值的相似性：无论是关键词字典的key，还是文件索引字典的key，都是160bit，而节点ID恰恰也是160bit。这显然是有目的的。事实上，节点的ID值也就决定了哪些条目可以存储在该节点之中，因为我们完全可以把某一个条目简单地存放在节点ID 值恰好等于条目中key值的那个节点处，我们可以将满足(ID==key)这一条件的节点命名为目标节点N。这样的话，一个查找条目的问题便被简单地转化成为了一个查找ID等于Key值的节点的问题。
由于在实际的Kad网络当中，并不能保证在任一时刻目标节点N均一定存在或者在线，因此Kad网络规定：任一条目，依据其key的具体取值，该条目将被复制并存放在节点ID距离key值最近(即当前距离目标节点N最近)的k个节点当中；之所以要将重复保存k份，这完全是考虑到整个Kad系统稳定性而引入的冗余；这个k的取值也有讲究，它是一个带有启发性质的估计值，挑选其取值的准则为：“在当前规模的Kad网络中任意选择至少k个节点，令它们在任意时刻同时不在线的几率几乎为0”；目前，k的典型取值为20，即，为保证在任何时刻我们均能找到至少一份某条目的拷贝，我们必须事先在Kad网络中将该条目复制至少20份。
由上述可知，对于某一条目，在Kad网络中ID越靠近key的节点区域，该条目保存的份数就越多，存储得也越集中；事实上，为了实现较短的查询响应延迟，在条目查询的过程中，任一条目可被cache到任意节点之上；同时为了防止过度cache、保证信息足够新鲜，必须考虑条目在节点上存储的时效性：越接近目标结点N，该条目保存的时间将越长，反之，其超时时间就越短；保存在目标节点之上的条目最多能够被保留24小时，如果在此期间该条目被其发布源重新发布的话，其保存时间还可以进一步延长。
6. Kad网络节点需要维护哪些状态信息?
在Kad网络中，每一个节点均维护了160个list，其中的每个list均被称之为一个k-桶(k-bucket)，如下图所示。在第i个 list中，记录了当前节点已知的与自身距离为2^i~2^(i+1)的一些其他对端节点的网络信息(Node ID，IP地址，UDP端口)，每一个list(k-桶)中最多存放k个对端节点信息，注意，此处的k与上文所提到的复制系数k含义是一致的；每一个 list中的对端节点信息均按访问时间排序，最早访问的在list头部，而最近新访问的则放在list的尾部。
k-桶中节点信息的更新基本遵循Least-recently Seen Eviction原则：当list容量未满(k-桶中节点个数未满k个)，且最新访问的对端节点信息不在当前list中时，其信息将直接添入list队尾，如果其信息已经在当前list中，则其将被移动至队尾；在k-桶容量已满的情况下，添加新节点的情况有点特殊，它将首先检查最早访问的队首节点是否仍有响应，如果有，则队首节点被移至队尾，新访问节点信息被抛弃，如果没有，这才抛弃队首节点，将最新访问的节点信息插入队尾。可以看出，尽可能重用已有节点信息、并且按时间排序是k-桶节点更新方式的主要特点。从启发性的角度而言，这种方式具有一定的依据：在线时间长一点的节点更值得我们信任，因为它已经在线了若干小时，因此，它在下一个小时以内保持在线的可能性将比我们最新访问的节点更大，或者更直观点，我这里再给出一个更加人性化的解释：MP3文件交换本身是一种触犯版权法律的行为，某一个节点反正已经犯了若干个小时的法了，因此，它将比其他新加入的节点更不在乎再多犯一个小时的罪……-_-b
由上可见，设计采用这种多k-bucket数据结构的初衷主要有二：a. 维护最近-最新见到的节点信息更新；b. 实现快速的节点信息筛选操作，也就是说，只要知道某个需要查找的特定目标节点N的ID，我们便可以从当前节点的k-buckets结构中迅速地查出距离N 最近的若干已知节点。
7. 在Kad网络中如何寻找某特定的节点?
已知某节点ID，查找获得当前Kad网络中与之距离最短的k个节点所对应的网络信息(Node ID，IP地址，UDP端口)的过程，即为Kad网络中的一次节点查询过程(Node Lookup)。注意，Kad之所以没有把节点查询过程严格地定义成为仅仅只查询单个目标节点的过程，这主要是因为Kad网络并没有对节点的上线时间作出任何前提假设，因此在多数情况下我们并不能肯定需要查找的目标节点一定在线或存在。
整个节点查询过程非常直接，其方式类似于DNS的迭代查询：
a. 由查询发起者从自己的k-桶中筛选出若干距离目标ID最近的节点，并向这些节点同时发送异步查询请求；
b .被查询节点收到请求之后，将从自己的k-桶中找出自己所知道的距离查询目标ID最近的若干个节点，并返回给发起者；
c. 发起者在收到这些返回信息之后，再次从自己目前所有已知的距离目标较近的节点中挑选出若干没有请求过的，并重复步骤1；
d. 上述步骤不断重复，直至无法获得比查询者当前已知的k个节点更接近目标的活动节点为止。
e. 在查询过程中，没有及时响应的节点将立即被排除；查询者必须保证最终获得的k个最近节点都是活动的。
简单总结一下上述过程，实际上它跟我们日常生活中去找某一个人打听某件事是非常相似的，比方说你是个Agent Smith，想找小李(key)问问他的手机号码(value)，但你事先并不认识他，你首先肯定会去找你所认识的和小李在同一个公司工作的人，比方说小赵，然后小赵又会告诉你去找与和小李在同一部门的小刘，然后小刘又会进一步告诉你去找和小李在同一个项目组的小张，最后，你找到了小张，哟，正好小李出差去了(节点下线了)，但小张恰好知道小李的号码，这样你总算找到了所需的信息。在节点查找的过程中，“节点距离的远近”实际上与上面例子中“人际关系的密切程度”所代表的含义是一样的。
最后说说上述查询过程的局限性：Kad网络并不适合应用于模糊搜索，如通配符支持、部分查找等场合，但对于文件共享场合来说，基于关键词的精确查找功能已经基本足够了(值得注意的是，实际上我们只要对上述查找过程稍加改进，并可以令其支持基于关键词匹配的布尔条件查询，但仍不够优化)。这个问题反映到eMule的应用层面来，它直接说明了文件共享时其命名的重要性所在，即，文件名中的关键词定义得越明显，则该文件越容易被找到，从而越有利于其在 P2P网络中的传播；而另一方面，在eMule中，每一个共享文件均可以拥有自己的相关注释，而Comment的重要性还没有被大家认识到：实际上，这个文件注释中的关键词也可以直接被利用来替代文件名关键词，从而指导和方便用户搜索，尤其是当文件名本身并没有体现出关键词的时候。
8. 在Kad网络中如何存储和搜索某特定的条目?
从本质上而言，存储、搜索某特定条目的问题实际上就是节点查找的问题。当需要在Kad网络中存储一个条目时，可以首先通过节点查找算法找到距离 key最近的k个节点，然后再通知它们保存条目即可。而搜索条目的过程则与节点查询过程也是基本类似，由搜索发起方以迭代方式不断查询距离key较近的节点，一旦查询路径中的任一节点返回了所需查找的value，整个搜索的过程就结束。为提高效率，当搜索成功之后，发起方可以选择将搜索到的条目存储到查询路径的多个节点中，作为方便后继查询的cache；条目cache的超时时间与节点-key之间的距离呈指数反比关系。
9. 一个新节点如何首次加入Kad网络?
当一个新节点首次试图加入Kad网络时，它必须做三件事，其一，不管通过何种途径，获知一个已经加入Kad网络的节点信息(我们可以称之为节点 I)，并将其加入自己的k-buckets；其二，向该节点发起一次针对自己ID的节点查询请求，从而通过节点I获取一系列与自己距离邻近的其他节点的信息；最后，刷新所有的k-bucket，保证自己所获得的节点信息全部都是新鲜的。
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的全局搜索，对于大家都是一个明智的选择。
1. ID and Key
Node ID：160 bit （每一个Node拥有一个ID，随机产生）
Key：160 bit （Key也许是某个很大的数据的SHA-1 hash值）
(Key,Value)这一对数据保存在ID最“接近”Key的Node上。
“接近”的意思是Key和ID之间的“距离”很短。
Kad网络中“距离”的定义是：d(x,y) = x XOR y，也就是x和y的异或值。
* 选择XOR作为衡量距离的尺度，是因为XOR有xxx,yyy,zzz,...等特性，具体请看Kademlia的paper [1] section 2.1。
2. k-bucket
每一个Node保持160个 list。对于第 i (0 <= i < 160) 个 list，此 list 中保存着和该 Node 距离为 2*i ~ 2*(i+1) 【2的 i 次方到 2的 i+1 次方】的一些 Node 的信息（Node ID，IP地址，UDP端口）。这些 list 叫做 k-bucket 。k是每一个 listk 中保存的 Node 的最大
个数（比如，20）。
+------------------------+
list 0: | | 距离为[1,2)的node
+------------------------+
（ID前159 bit相同，第160 bit一定不同的node: 1个）
+------------------------+
list 1: | | 距离为[2,4)的node
+------------------------+
（ID前158 bit相同，第159 bit一定不同的node: 2个）
+------------------------+
list 2: | | 距离为[4,8)的node
+------------------------+
（ID前157 bit相同，第158 bit一定不同的node: 4个）
+------------------------+
list 3: | | 距离为[8,16)的node
+------------------------+
（ID前156 bit相同，第157 bit一定不同的node: 8个）
+------------------------+
list 4: | | 距离为[16,32)的node
+------------------------+
（ID前155 bit相同，第156 bit一定不同的node: 16个）
。
。
。
+------------------------+
list 159: | | 距离为[2*159,2*160)的node
+------------------------+
（ID第1 bit不同的node: 2*159个。此list中最多保存最近访问的k个）
每一个list （k-bucket）中的node按照访问的时间顺序排列，最先访问的在list头部，最近访问的在list的尾部：
Head Tail
| |
V V
+--+ +--+ +--+ +--+ +--+ +--+
| |-->| |-->| |-->| |-->| |--> ... --> | |
+--+ +--+ +--+ +--+ +--+ +--+
Node0 Node1 ... Node[N]
A A
| |
least-recently most-recently
3.k-bucket的刷新
当一个Node收到另一个Node发来的消息的时候，它根据以下规则（least-recently seen eviction policy）来刷新相应的k-bucket:
1) 如果发送者已经在某一个k-bucket中，将它在该 k-bucket 中移动到尾部
2) 如果发送者不在其对应的k-bucket中，并且该 k-bucket 还不满 k 个Node，将这个发送者加入到 k-bucket 的尾部
如果该 k-bucket 已经满了（有k个Node），那么接受消息的 Node 向该 k-bucket 中最老的（也就是头部的）Node发送一个 ping 消息
如果这个最老的 Node 没有响应，则将它从 k-bucket 中删除，将新的发送消息的 Node 加入到 k-bucket 的尾部
如果这个最老的 Node 响应了，则将它移动到 k-bucket 的尾部，并抛弃新的 Node 的信息
* 为什么要采取这样的规则，请看Kademlia的paper [1] section 2.2
4. 基本协议(protocol)
四种基本的RPC：PING, STORE, FIND_NODE, FIND_VALUE
1) PING
PING 探测一个Node是否在线
2) STORE
STORE 以(Key,Value)为参数。指示另一个Node（消息接收者）保存一个(Key, Value)对，以供以后取用。
3) FIND_NODE
FIND_NODE 以一个160 bit的ID作为参数。接收者返回它所知道的最接近该ID的 k 个 Node 的 Contact 信息（ID,UPD Port,IP）。这些 Node 不一定要从同一个 k-bucket 中产生。除非它所有的 k-bucket 中所有的 Node 加在一起都不到 k 个，否则它必需凑足 k 个。
4) FIND_VALUE
FIND_VALUE 以一个160 bit的ID/Key作为参数。如果接收者先前已经收到一个 STORE RPC，而且 STORE 的参数之一 Key 就是当前 FIND_VALUE 的参数，那么，接收者将 STORE 的另一个参数 Value 返回给发送者。否则，FIND_VALUE 和 FIND_NODE 一样，返回它所知道的最接近该ID的 k 个 Node 的 Contact 信息（ID,UPD Port,IP）。
FIND_VALUE 的意思就是：如果接收者有发送着所要的 Value，就将该 Value 返回。否则，接收者就帮忙找更接近该 ID/Key 的 Node。
所有的 RPC 消息都带有一个 160 bit的随机 RPC ID，由发送者产生，接收者在响应每一个消息的时候，返回的消息里面都必需拷贝此 RPC ID。目的是防止地址伪造。PING 消息可以在 RPC 响应里使用捎带确认机制来获得发送者网络地址（原文：pings can also be piggy-backed on RPC replies for the RPC recipient to obtain additional assurance of the sender's network address.）。
* piggyback
捎带确认(法)
A technique used to return acknowledgement information across a full-duplex (two-way simultaneous) data link without the use of special (acknowledgement) message. The acknowledgement information relating to the flow of message in one direction is embedded (piggybacked) into normal data-carrying message flowing in the reverse direction.
经全双工(双向同时)数据链路,不用专门(确认)报文返回确认信息所用的技术。与一个方向的报文流有关的确认信息钳在反方向正常携带数据的报文流中。
[1] Kadmelia的paper：http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf
5. 节点查找(node lookup)
node lookup:找到距离给定的 ID 最近的 k 个 node
定义 a:系统范围内的并发参数，比如3。
步骤：
1) 从最近的 k-bucket 里面取出 a 个最近的 node，然后向这 a 个 node 发送并行的、异步的 FIND_NODE RPC。
2) 再次发送 FIND_NODE RPC 给从前一步返回的 node（这一步可以不必等到前一步中所有 a 个 PRC 都返回之后才开始）：
从发送者已知的 k 个最接近目标的 node 当中，取出 a 个还没有查询的 node，向这 a 个 node 发送 FIND_NODE RPC。
没有迅速响应的 node 将被排除出考虑之列，直到其响应。
如果一轮 FIND_NODE RPC 没有返回一个比已知的所有 node 更接近目标的 node，发送者将再向 k 个最接近目标的、还没有查询的 node 发送 FIND_NODE RPC。
3) 查找结束的条件：发送者已经向 k 个最近的 node 发送了查询，并且也得到了响应。
6. 存储<Key, Value>(store a <Key,Value> pair)
步骤：
1) 使用node lookup算法，找到距离 Key 最近的 k 个 node
2) 向这 k 个 node 发送 STORE RPC
3) 每一个 node 必要的时候重新发布(re-publish)所有的<Key,Value>
（对于当前的 Kademlia 应用(文件共享)，每一个<Key,Value>的原始发布者被要求每隔24小时重新发布一次，否则<Key,Value>将在发布之后的24小时之后过期。对于其他一些应用，比如digital certificates, cryptographic hash to value mapping，过期时间可以更长一些）
7. 搜索<Key,Value> （find a <Key,Value> pair)
步骤：
1) 使用 FIND_VALUE 代替 FIND_NODE 进行"node lookup"过程。一旦任何其他 node 返回了所要的 Value，搜索的过程就结束。
2) cache: 如果搜索成功，搜索的发起者将这个<Key,Value>对存储到已知的、最近的、但是在第一步中没有返回该 Value 的 node 上。
显然，有了cache之后，以后对于该 <Key,Value> 的搜索很可能首先找到 cache，而不是直到找到最接近 Key 的那个 node。
如果一个 <Key,Value> 被频繁的搜索，那么它很可能被缓存到很多 ID 不太接近 Key 的 node 中。
为了避免过度缓存(over-caching)，每一个 <Key,Value> 都有一个过期时间，这个过期时间和当前node 和“最接近Key之node”之间的 node 的个数（这个数目可以从当前node的bucket接口推断出）的指数倒数成正比。（To avoid "over-caching", we make the expiration time of a <key,value> pair in any node's database exponentially inversely proportional to the number of nodes between the current node and the node whose ID is closest to the key ID. This number can be inferred from the bucket structure of the current node）
8. 刷新bucket (refresh bucket)
所有的 bucket 通过node之间的请求来刷新。
如果某一个bucket在过去一个小时之内没有任何的node lookup操作，那么这个node就随机搜索一个在这个bucket覆盖范围内的ID。
9. node加入网络
步骤：
1) 一个新加入的node（假设为u）必需首先获得一个已经在网络中的node（比如为w）的contact信息。
2) u 首先将 w 加入到其对应的 k-bucket 中
3) u 执行一个对自己ID的 node lookup 操作
4) u 刷新所有的 k-bucket