泽民博客 ☰ Menu

Kademlia 原理

一、P2P及DHT技术简介
P2P在思想上可以说是internet思想/精神/哲学非常集中的体现，共同的参与，透明的开放，平等的分享（让我想起之前学习过的，现在正在疯狂热炒的云计算的“中央集权”制度）。基于P2P技术的应用有很多，包括文件分享，即时通信，协同处理，流媒体通信等等。通过这些应用的接触，分析和理解，P2P其本质是一种新的网络传播技术，这种新的传播技术打破了传统的C/S架构，逐步地去中心化，扁平化，这或许在一定程度上应证了”世界是平的”趋势，呵呵。P2P文件分享的应用(BTs/eMules等)是P2P技术最集中的体现，我们这里的研究也是以P2P文件分享网络作为入口，P2P文件分享网络的发展大致有以下几个阶段，包含tracker服务器的网络，无任何服务器的纯DHT网络， 混合型P2P网络。DHT网络发展即有“思想/文化”上的“发展”，也有一定的商业上的需求（版权管理）。



   DHT全称叫分布式哈希表(Distributed Hash Table)，是一种分布式存储方法，一类可由键值来唯一标示的信息按照某种约定/协议被分散地存储在多个节点上，这样也可以有效地避免“中央集权式”的服务器（比如：tracker）的单一故障而带来的整个网络瘫痪。实现DHT的技术/算法有很多种，常用的有：Chord, Pastry, Kademlia等。我们这里要研究的是Kademlia算法，因为BT及BT的衍生派（Mainline, Btspilits, Btcomet, uTorrent…），eMule及eMule各类Mods(verycd, easy emules, xtreme…)等P2P文件分享软件都是基于该算法来实现DHT网络的，BT采用Python的Kademlia实现叫作khashmir（科什米尔），官网如下所示。eMule采用C++的Kademlia实现干脆就叫作Kad，当然它们之间有些差别，但基础都是Kademlia。我们这里以BT-DHT为例进行分析介绍，下面说到的DHT都可以默认是BT-Kademlia-DHT。


官方网站：http://www.tribler.org/trac/wiki/Khashmir



二、Kademlia实现原理
各种DHT的实现算法，不论是Chord, Pastry还是Kademlia，其最直接的目标就是以最快的速度来定位到期望的节点，在P2P文件分享应用中则是以最快的速度来查找到正在分享某一文件/种子的peers列表信息。因为每个节点都是分布式存在于地球的任何角落，如果用地理距离来衡量两节点间的距离则可能给计算带来极大复杂性甚至不可能进行衡量，因此基本所有的DHT算法都是采用某种逻辑上的距离，在Kademlia则采用简单的异或计算来衡量两节点间的距离，它和地理上的距离没有任何关系，但却具备几何公式的绝大特征：



   (1)节点和它本身之间的异或距离是0



   (2)异或距离是对称的：即从A到B的异或距离与从B到A的异或距离是等同的



   (3)异或距离符合三角形不等式：给定三个顶点A B C，假如AC之间的异或距离最大,那么AC之间的异或距离必小于或等于AB异或距离和BC异或距离之和.



   (4)对于给定的一个距离，距离A只存在有唯一的一个节点B，也即单向性，在查找路径上也是单向的，这个和地理距离不同。


Kademlia中规定所有的节点都具有一个节点ID，该节点ID的产生方法和种子文件中的info hash采用相同算法:即sha-1（安全hash算法），因此每个节点的id，以及每个共享文件/种子的info-hash都是唯一的，并且都是20个字符160bits位组成。两个节点间的距离就是两个节点id的异或结果，节点离键值（种子）的距离为该节点的id和该种子文件的info-hash的异或结果。Kademlia在异或距离度量的基础上又把整个DHT网络拓扑组织成一个二叉前缀树（XuanWu系统中arp的实现则是一个例子），所有的节点(所有的正在运行的，并且开取了DHT功能的Bt,Btspilits应用)等作为该二叉前缀树的叶子节点，可以想象这棵二叉树可以容纳多达2128个叶子（节点），这足以组织任何规模的网络了。对于每个节点来说按照离自己的远近区域又可以把这棵树划分为160棵子树，每一个子树和该节点都有一个共同的前缀，共同前缀越少离得越远。如下图所示：

（注意：上图只是一个划分子树的例子，节点都没有位于同一层的叶子上面）



   以上图红色节点位例0011位例，它可以把其他的节点划分位4棵不同子树，离自己越近子树和自己有越长的公共前缀，如果节点是均匀分布则离自己越近的子树含有的叶子节点更少（兄弟只有一个即和自己有159个共同前缀的那个）。因为节点都位于该树最底层的叶子位置，水平看上去则所有的叶子都在一条线上，如果把这条线当作2128空间的每一个点，则更能体现上面的划分特性（折半拆分）。为了能快速到达这160棵子树，处于DHT网络中的每一个节点都记录了每棵子树上的k个节点的信息（ip,port,id），在BT中K固定为8，比如上图中红色节点就可能保存有最左边子树的8个叶子节点信息，当然靠近自己的子树可能没有8个叶子，则把所有当前存在的叶子记录上去，这份记录信息在Kademlia算法中叫作K桶，也叫作“路由表”，当然这个“路由表”的信息和我们IP路由的含义有点不同，它代表的是为了到达处于距离自己某范围[ 2i — 2i+1 )的节点，可以通过该范围内的选取的k个节点来进一步定位，下图是一个“路由表”结构：

<img src="https://xiazemin.github.io/MyBlog/img/Kademlia1.jpg"/> 注意：这里只是一个举例，在实际的“路有表”中可能是没有160份，因为路由表的生成过程是对半分拆的，最初只有一个K桶（范围为:0—2160，且只包括自己），在插如过程中当该K桶节点大于k(8)时，则分拆成两半，一半包括自身节点，一半不包括自身。循环往复下去，则形成一个动态的大小（1<=len(table)<=160）的“路由表”。


每一个新加入到DHT网络的节点最开始这些“路由表”信息都是空的，它有以下几个方式可以来逐步生成和形成自己的“路由表”信息：



（1）如果本节点曾经启动过程，则从保存的“路由表”文件中直接读取然后刷新该“路由表“



（2）如果该节点第一次启动（比如新安装BTSpilits然后启动），并且该节点自带有“超级节点“则通过这些“超级节点“来间接地生成自己的”路由表“（在Kashmir的某个版本中有一个文件保存这些”超级接点的信息“，BTSplits, BTcomet, eMules则内嵌有20多个）



（3）如果第一次启动的节点没有这些所谓的“超级节点”(比如Mainline则没有这个功能)，则它的路由表生成过程需要推迟到download文件过程。它会从它获取到的种子文件中提取nodes字段，该字段是做种子（支持DHT网络的种子）的时候生成的，一般nodes字段设置为该原始种子的ip和port，或者是做种子的节点离该种子的info-hash最近的k个节点。通过这些nodes字段中的节点通过来间接地生成自己的路由表。



（4）动态建立过程，该过程为节点经过上面的初始化后，在下载或者上传或者无任务过程中有收到任何节点发送的任何消息，都会去检查当前的“路由表”并尝试按照一定的规则去建立/刷新路由表。



   我们知道DHT网络最主要的目标是替代Tracker（纯P2P网络，无traker）或者说作为Tracker的一个备份（混合型P2P网络，当前基本所有主流文件分享的应用都是该类型）。而Tracker最主要功能就是对每一个分享文件（种子）维护一个peers列表，然后告诉需要下载的询问者Client。实现的方法就是把Tracker集中维护的所有种子的peers-list信息利用DHT的方法散列并保存到所有的DHT网络中的节点上去，然后在此基础上提供查找的方法。“路有表”作用就是为了加速这个查找的过程的。在DHT实现中包括两种类型的查找，一种是查找nodes(find_nodes)，另一种是查找peers（get_peers）。查找nodes的过程主要是为了建立本地的“路由表”，它的最终目的是后面查找peers。查找节点的过程大概是这样，如果节点x需要查找节点y，则x首先从xor(x,y)对应的本地K桶中得到k个比较closer的节点，然后向这些比较close的k个节点继续询问它是否有离y更近的节点，这些k个节点当然也从自己的对应的K桶中返回k个更近的节点给x，x然后再从返回结果中选取k个更more closer节点重复上面的动作，直到不能返回更近的节点为止，则最后找到的k个节点即为the most closest nodes，在这个过程中返回的任何k个close的节点都会尝试去插到自己的路由表中去。而x查找peers-list的方法则和上面查找节点的方法类似，不同的是它是以info-hash作为参数进行查找，并且如果在查找过程中有任何一个节点返回了(info-hash, peers-list)对则提前结束查找。当一个节点通过上面方法得到了peers-list后，则会试图对每个peers主动发起TCP的连接继续后面真实的下载过程（该过程由peer-peer protocol协议规定），同时会把自己的peer信息发送给先前的告诉者和自己K桶中的k个最近的节点存储该peer-list信息。该信息在该k个节点上可以保存24个小时，24小时后如果没有收到x发送的更新消息则失效。因此一个活动的节点存储有两部份的信息，一部分是本地的“路由表”，另一部分则是(info-hash, peers-list)列表信息（可有多个）。Info-hash的值当然也属于(0-2160)空间的一部分，但是它和节点id不同，节点ID是可以作为那棵无形的二叉前缀树的叶子（为什么是无形的，因为每个节点其实是没有用数据结构来存储这个棵的树的），而info-hash则只能附着在离它的值最近的node id上面。


三、kademlia的消息
为了实现上面的“路由表”建立，刷新，获取peers-list,保存peers-list这些功能，kademlia定义四个最基本的KRPC操作:



   (1)ping操作，作用是探测一个节点，用以判断该节点是否仍然在线。



   (2)store操作，作用是通知一个节点存储一个<key,value>对，以便以后查询需要。



   (3)find_node操作，作用是从自己的“路由表”对应的K桶中返回k个节点信息(IP address,UDP port,Node ID)给发送者



   (4)faind_value 操作，作用是把info-hash作为参数，如果本操作接收者正好存储了info-hash的peers则返回peers list，否则从自己的“路由表“中返回离info-hash更近的k个节点信息（同find_node过程）。



  上面只是最基本的操作，一次nodes或者info-hash的查找lookup过程则需要节点进行若干次上面的find操作的，一个递归查找的过程。利用上面的操作更精确的描述一次一个节点x要查找ID值为t 的节点， 过程如下：



   1、计算到t 的距离：d(x,y) = x⊕y。



   2、从x 的第[㏒ d]个K 桶中取出α 个节点的信息（各个实现α值不一样，有些是3有些则等于k值），同时进行FIND_NODE 操作。如果这个K 桶中的信息少于α 个，则从附近多个桶中选择距离最接近d 的总共α个节点。



   3、对接受到查询操作的每个节点，如果发现自己就是t，则回答自己是最接近t 的。否则测量自己和t 的距离，并从自己对应的K 桶中选择α 个节点的信息给x。



   4、X 对新接受到的每个节点都再次执行FIND_NODE 操作，此过程不断重复执行，直到


每一个分支都有节点响应自己是最接近t 的，或者说FIND_NODE操作返回的节点值没有都已经被查找过了，即找不到更近的节点了。



   5、通过上述查找操作，x 得到了k 个最接近t 的节点信息。



   注意：这里用“最接近”这个说法，是因为ID 值为t 的节点不一定存在网络中，也就是说t 没有分配给任何一台电脑。



   查找peers-list的过程则换成find_value动作，但注意前文提到的区别即可以有类似的描述。



   上面的四个原始在BT-DHT的实现上则进行了重命名，定义了如下四类信息，它们叫作KRPC（K代表Khashmila/Kademlia），通过udp进行发送，一个请求一个响应或者错误。


（1） Ping（和Kademlia同名同功能）



Beconded（以BitSprits为例）:



Ping Request格式：



d1:ad2:id20:xxxxxxxxxxxxxxxxxxxe1:q4:ping1:t4:tttt1:y1:qe



表示的含义：此操作为ping操作请求，参数为发送者的id是：xxxxxxxxxxxxxxxxxx



Ping Reponse格式:



d1:rd2:id20:yyyyyyyyyyyyyyyyyy e1:t4:1:y1:re



返回的数据中只包括有一个响应者的id信息。



（2） find_node（和Kademlia同名同功能）



Beconded（以BitSprits为例）:



find_node Request格式：



d1:ad2:id20:xxxxxxxxxxxxxxxxxxxx6:target20:yyyyyyyyyyyyyyyyyyyy1:q9:find_node1:t4:1:y1:qe



表示的含义：此操作为find_node请求，参数为发送者id及目标节点的id



find_node Reponse格式：



d1:rd2:id20:xxxxxxxxxxxxxxxxxxxx5:nodes208:nnnnnnnnnnnnn5:token20:ooooooooooooo1:t4:ttt 1:y1:re



表示的含义是：找到了8个最近的节点，nodes208表示8个node信息（ip,port,id）共208Bytes



（3） get_peers（对应Kademlia中的find_value消息）



Beconded（以BitSprits为例）:



Get_peers请求格式：



d1:ad2:id20:xxxxxxxxxxxxxxxxxxxx9:info_hash20:zzzzzzzzzzzzzzzzzzzze1:q9:get_peers1:t4:tttt1:y1:qe



表示的含义：此操作为get_peers操作请求，参数为：发送者的id和要查询种子的info-hash。



Get_peers响应格式有两种，一种是找到了节点含有该info-hash的peers列表信息，如下格式：



表示的含义：



d1:rd2:id20:xxxxxxxxxxxxxxxxxxx5:token20:ooooooooooooooooooo6:valuesl6:(ip1,port1)+(ip2,port2)+(ipi,porti)…e1:t4:tttt1:y1:re



(values后面跟上的则是peers列表，ip, port)



另一种是没有找到列表信息，如下格式：



d1:rd2:id20:xxxxxxxxxxxxxxxx5:nodes208:nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn 5:token20:ooooooooooooooo1:t4:tttt1:y1:re



表示的含义为：



没有找到存有info-hash的节点，但找到了离该info-hash更近的8个节点，nodes208表示8个node信息（ip,port,id）共208bytes



（4） announce_peer（对应Kademlia中的store消息）



Beconded（以BitSprits为例）:



announce _peers请求格式：



d1:ad2:id20:xxxxxxxxxxxxxxxxx9:info_hash20:zzzzzzzzzzzzzzzzzz4:porti10756e5:token20:ooooooooooooooooo1:q13:announce_peer1:t4:tttt1:y1:qe



表示的含义是：此操作为announce_peer请求操作，告诉对端我这边对info-hash文件上传和下载，可以成为peers list中的一员，端口号是10756.



Announce_peer Reponse格式



d1:rd2:id20:xxxxxxxxxxxxxxxxxxxx2:ip4:pppp1:t4:tttt1:v4:UTb*1:y1:re



附件为抓取的分别为为一简单下载过程/一初始初始化路由表的数据包：可以对照进行分析



四、Bttorent DHT实现几个重要过程
种子制作：



1）./maketorrent-console参数use_tracker设置为false，则不会产生announce tracker字段



2） 读取本地“路由表”文件，并从中找出k个离info-hash最近的节点，作为nodes字段



启动过程：



1） 从routing_table文件中装载之前保存的”路由表”K桶信息，初始化内存“路由表”信息



2） 强制刷新“路由表“中的每一个K桶，刷新过程是随机产生一id进行findNode查找。



刷新路由表的过程：



1） 启动的时候进行强制刷新



2） 每15分钟如果K桶中的信息没有进行更新的话，则进行刷新一次K桶，即refreshTable



3） 每5分钟进行一次checkpoint操作，以把当前的路由表存放到routing_table文件中



routing_table文件的格式：



{‘id’:node.id, ‘host’:node.host, ‘port’:node.port, ‘age’:int(node.age)}



有些实现是用SQLite数据库来实现这部分功能的。



   每一个“路由表”的K桶都有一个“最近更新时间“属性，当收到该桶中任何节点的ping响应，或者有任何节点被加入或者被替换，则该属性都需保持更新，并且重启一个15分钟的定时器，如果定时器超时（15分钟内该K桶节点没有任何更新操作），则会对该K桶进行一次refresh操作，操作的过程是从该K桶范围选出一随机的ID，然后对该ID进行find_node操作。“路由表”中的节点需要保持live状态，即得保证没有离线，如果向路由表中的一节点发出的连续3次请求都没有收到响应，则认为该节点失效。


refreshTable（force=1）过程：



（1） 如果force=1，则对当前每个K桶都进行刷新



（2） 如果K桶当前nodes数小于k（8），则也进行刷新



（3） 如果K桶中存在无效的节点，即连续三个消息没有收到响应的节点



（4） 如果K桶中所有节点没有交互的时间超过15分钟，则也进行刷新



   当一个节点收到任何一个RPC消息（请求和响应）后（ping/find/getPeers/announce_peer）都会去检查一下该消息的发送者是否在本地的“路由表“中，如果该发送者已经存在节点的本地“路由表”中，则会把该发送者从其对应的K桶移动到该K桶的末尾。如果该发送者不在节点的“路由表”中则会去尝试插入到本地”路由表“K桶中，这也是“路由表”的动态建立过程的一种，过程如下：


（0） 找到该发送者的对应的K桶



（1） 如果该节点是响应消息中发现的，则更新该节点lastSeen = time()时间



（2） 如果该K桶大小小于k（8）则直接插到该K桶后面



（3） 如果该K桶已经满了，则检查是否有无效的节点，如果有则把这些无效节点删除，并把该节点放入K桶末尾。（但后面会对这些早已经存在的节点进行再一次的ping操作，来进一步确定是否无效了，如果收到响应，则把这些节点重新放如K桶）



（4） 如果该K桶已经满了，并且所有的节点都是有效的，则需要查看自身（本客户短）是否在该K桶中（即该K桶是否是自己所在的K桶），如果不是则直接丢弃该节点



（5） 如果该K桶不是自身所在的K桶，则需要进行K桶分拆。拆分的方法即是一个变为两个等长K桶，一个包括自身，一个不包括。



（6） 对该节点添加到分拆后的一个K桶中去。



findNodes(id, invalid=True)的过程：



//该过程是内部过程，给下面findNode()



（0）如果该节点在自己的K桶中，则直接返回，结束该过程



（1） 如果invalid=True，则需要排除当前无效的节点



（2） 如果上面选取该K桶中的所有节点小于K(8)，则需要从其他桶中补充，如下



（3） 把左右相邻的两个K桶中的节点补充进去，然后把所有这些节点按照离id距离远近进行排序，选取最近的K(8)个节点



（4） 返回最后得到的最近的K个节点。



findNode(id)的过程：



（1） 从自己本地的“路由表“取离id最近的K桶，返回k(8)个nodes信息



（2） 从上面k个信息中选取a个（3）个，然后发送findNode消息给这3个节点



（3） 该3个节点查找自己的“路由表“同时返回k个nodes信息



（4） 从上面得到的3*k个节点在重复



Keyexpired过程：



1） 节点存放的（info-hash，peers-list）如果24小时没有收到原节点的更新则视作无效



2） 当前仍然活动的peer-lists中的节点需要24小时向其close节点进行刷新info-hash，peers-list。



3）当前仍然活动的peer-lists中的节点如果在自己的路由表中发现有离info-hash更近的节点，则会把自（info-hash，peers-list）announce给它们。



在BT程序中，对外只有一个过程，那就是下面的getPeersAndAnnounce过程，该过程的作用就是对提供的info-hash找到一个peers list表，并且把自己作为一个peer告诉给别人：



getPeersAndAnnounce过程：



（0） 该过程包括了getPeers和Announce_peer两个过程



（1） getPeers的过程首先是在自己的本地的（info-hash, peers-list）表中进行查找，如果查找到则直接进行连接



（2） 如果本地没有info-hash的key,values，则需要进行远程查找，查找的过程是



（3） 先从info-hash对应的K桶中找k个节点，然后分别向它们发送getpeers原始RPC消息



（4） 分析上面k个节点的响应信息，如果响应信息中存在values字段，则说明命中一个节点，该节点保存有info-hash的peers-list信息，保存起来。如果响应消息中只有nodes字段，则该字段后面跟上的是k（8）个更接近于info-hash的节点，判断这些节点是否发送过，如果没有则把这些节点保存起来继续发送getPeers RPC消息，直到收到响应消息中带有values字段，或者响应消息中所有的节点都发送过了（没有更接近info-hash的节点了）



（5） 当收到节点对get_peers响应包中包括有(info-hash,peers-list)后，则首先向响应者发送announce，然后向自己K桶中离info-hash最近的k个节点发送announce_peer消息



Ping消息的发送过程：



1） 对于DHT种子文件中nodes逐个节点发送ping消息，有响应者则添加到“路由表”中去



2） 当插入新节点到“路由表”中时，如果该“路由表”K桶已满，则会选择K桶的头部节点进行ping操作，如果该头节点仍然在线，则直接丢弃该节点（这是基于一种越长时间在线则可能以后越长在线的概率统计），否则删除头节点，并把新节点插到K桶尾

Kademlia(简称Kda)属于一种典型的结构化P2P覆盖网络(Structured P2P OverlayNetwork)，以分布式的应用层全网方式来进行信息的存储和检索是其尝试解决的主要问题。在Kademlia网络中，所有信息均以哈希表条目形式加以存储，这些条目被分散地存储在各个节点上，从而以全网方式构成一张巨大的分布式哈希表。我们可以形象地把这张哈希大表看成是一本字典：只要知道了信息索引的key，我们便可以通过Kademlia协议来查询其所对应的value信息，而不管这个value信息究竟是存储在哪一个节点之上。在eMule、BitTorrent等P2P文件交换系统中，Kademlia主要充当了文件信息检索协议这一关键角色，但Kad网络的应用并不仅限于文件交换。下文的描述将主要围绕eMule中Kad网络的设计与实现展开。
eMule的Kda存储信息
只要是能够表述成为字典条目形式的信息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校验值的同一份文件了。
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网络来找到它们?不着急，慢慢来。
节点的ID和距离
Kad网络中的每一个节点均拥有一个专属ID，该ID的具体形式与SHA1散列值类似，为一个长达160bit的整数，它是由节点自己随机生成的，两个节点拥有同一ID的可能性非常之小，因此可以认为这几乎是不可能的。在Kad网络中，两个节点之间距离并不是依靠物理距离、路由器跳数来衡量的，事实上，Kad网络将任意两个节点之间的距离d定义为其二者ID值的逐比特二进制和数，即，假定两个节点的ID分别为a与b，则有：d=a XORb。在Kad中，每一个节点都可以根据这一距离概念来判断其他节点距离自己的“远近”，当d值大时，节点间距离较远，而当d值小时，则两个节点相距很近。这里的“远近”和“距离”都只是一种逻辑上的度量描述而已；在Kad中，距离这一度量是无方向性的，也就是说a到b的距离恒等于b到a的距离，因为aXOR b==b XOR a
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小时，如果在此期间该条目被其发布源重新发布的话，其保存时间还可以进一步延长。
Kad节点维护
在Kad网络中，每一个节点均维护了160个list，其中的每个list均被称之为一个k-桶(k-bucket)，如下图所示。在第i个list中，记录了当前节点已知的与自身距离为2^i~2^(i+1)的一些其他对端节点的网络信息(NodeID，IP地址，UDP端口)，每一个list(k-桶)中最多存放k个对端节点信息，注意，此处的k与上文所提到的复制系数k含义是一致的；每一个list中的对端节点信息均按访问时间排序，最早访问的在list头部，而最新访问的则放在list的尾部。
k-桶中节点信息的更新基本遵循Least-recently SeenEviction原则：当list容量未满(k-桶中节点个数未满k个)，且最新访问的对端节点信息不在当前list中时，其信息将直接添入list队尾，如果其信息已经在当前list中，则其将被移动至队尾；在k-桶容量已满的情况下，添加新节点的情况有点特殊，它将首先检查最早访问的队首节点是否仍有响应，如果有，则队首节点被移至队尾，新访问节点信息被抛弃，如果没有，这才抛弃队首节点，将最新访问的节点信息插入队尾。可以看出，尽可能重用已有节点信息、并且按时间排序是k-桶节点更新方式的主要特点。从启发性的角度而言，这种方式具有一定的依据：在线时间长一点的节点更值得我们信任，因为它已经在线了若干小时，因此，它在下一个小时以内保持在线的可能性将比我们最新访问的节点更大，或者更直观点，我这里再给出一个更加人性化的解释：MP3文件交换本身是一种触犯版权法律的行为，某一个节点反正已经犯了若干个小时的法了，因此，它将比其他新加入的节点更不在乎再多犯一个小时的罪……-_-b
由上可见，设计采用这种多k-bucket数据结构的初衷主要有二：a. 维护最新到的节点信息更新；b.实现快速的节点信息筛选操作，也就是说，只要知道某个需要查找的特定目标节点N的ID，我们便可以从当前节点的k-buckets结构中迅速地查出距离N最近的若干已知节点。
Kad寻找节点
已知某节点ID，查找获得当前Kad网络中与之距离最短的k个节点所对应的网络信息(NodeID，IP地址，UDP端口)的过程，即为Kad网络中的一次节点查询过程(NodeLookup)。注意，Kad之所以没有把节点查询过程严格地定义成为仅仅只查询单个目标节点的过程，这主要是因为Kad网络并没有对节点的上线时间作出任何前提假设，因此在多数情况下我们并不能肯定需要查找的目标节点一定在线或存在。
整个节点查询过程非常直接，其方式类似于DNS的迭代查询：
a. 由查询发起者从自己的k-桶中筛选出若干距离目标ID最近的节点，并向这些节点同时发送异步查询请求；
b .被查询节点收到请求之后，将从自己的k-桶中找出自己所知道的距离查询目标ID最近的若干个节点，并返回给发起者；
c. 发起者在收到这些返回信息之后，再次从自己所有已知的距离目标较近的节点中挑选出若干没有请求过的，并重复步骤1；
d. 上述步骤不断重复，直至无法获得比查询者当前已知的k个节点更接近目标的活动节点为止。
e. 在查询过程中，没有及时响应的节点将立即被排除；查询者必须保证最终获得的k个最节点都是活动的。
简单总结一下上述过程，实际上它跟我们日常生活中去找某一个人打听某件事是非常相似的，比方说你是个AgentSmith，想找小李(key)问问他的手机号码(value)，但你事先并不认识他，你首先肯定会去找你所认识的和小李在同一个公司工作的人，比方说小赵，然后小赵又会告诉你去找与和小李在同一部门的小刘，然后小刘又会进一步告诉你去找和小李在同一个项目组的小张，最后，你找到了小张，哟，正好小李出差去了(节点下线了)，但小张恰好知道小李的号码(cache)，这样你总算找到了所需的信息。在节点查找的过程中，“节点距离的远近”实际上与上面例子中“人际关系的密切程度”所代表的含义是一样的。
最后说说上述查询过程的局限性：Kad网络并不适合应用于模糊搜索，如通配符支持、部分查找等场合，但对于文件共享场合来说，基于关键词的精确查找功能已经基本足够了(值得注意的是，实际上我们只要对上述查找过程稍加改进，并可以令其支持基于关键词匹配的布尔条件查询，但仍不够优化)。这个问题反映到eMule的应用层面来，它直接说明了文件共享时其命名的重要性所在，即，文件名中的关键词定义得越明显，则该文件越容易被找到，从而越有利于其在P2P网络中的传播；而另一方面，在eMule中，每一个共享文件均可以拥有自己的相关注释，而Comment的重要性还没有被大家认识到：实际上，这个文件注释中的关键词也可以直接被利用来替代文件名关键词，从而指导和方便用户搜索，尤其是当文件名本身并没有体现出关键词的时候。
Kad存储和搜索条目
从本质上而言，存储、搜索某特定条目的问题实际上就是节点查找的问题。当需要在Kad网络中存储一个条目时，可以首先通过节点查找算法找到距离key最近的k个节点，然后再通知它们保存条目即可。而搜索条目的过程则与节点查询过程也是基本类似，由搜索发起方以迭代方式不断查询距离key较近的节点，一旦查询路径中的任一节点返回了所需查找的value，整个搜索的过程就结束。为提高效率，当搜索成功之后，发起方可以选择将搜索到的条目存储到查询路径的多个节点中，作为方便后继查询的cache；条目cache的超时时间与节点-key之间的距离呈指数反比关系。
新节点加入Kad
当一个新节点首次试图加入Kad网络时，它必须做三件事，其一，不管通过何种途径，获知一个已经加入Kad网络的节点信息(我们可以称之为节点I)，并将其加入自己的k-buckets；其二，向该节点发起一次针对自己ID的节点查询请求，从而通过节点I获取一系列与自己距离邻近的其他节点的信息；最后，刷新所有的k-bucket，保证自己所获得的节点信息全部都是新鲜的。



Category algorithm