细说 Kademlia

Kad是Kademlia的简称，eMule的官方网站在2004年2月27日正式发布的 eMule v0.42b中，Kad开始正式内嵌成为eMule的一个功能模块，可以说从这个版本开始eMule便开始支持Kad网络了。

Kad的出现，结束了之前edonkey时代，在ed圈里只存在着ED2K一种网络的模式，它通过新的协议开创并形成了自己的kad网络，使之和ED2K网络并驾齐驱，而且它还完全支持两种网络，可以在两种网络之间通用。Kad同样也属于开源的自由软件。它的程序和源代码可以在官方网站上下载。

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：

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. 存储(store a pair)
步骤：
 1) 使用node lookup算法，找到距离 Key 最近的 k 个 node
 2) 向这 k 个 node 发送 STORE RPC
 3) 每一个 node 必要的时候重新发布(re-publish)所有的
    （对于当前的 Kademlia 应用(文件共享)，每一个的原始发布者被要求每隔24小时重新发布一次，否则将在发布之后的24小时之后过期。对于其他一些应用，比如digital certificates, cryptographic hash to value mapping，过期时间可以更长一些）

7. 搜索 （find a pair)
步骤：
 1) 使用 FIND_VALUE 代替 FIND_NODE 进行"node lookup"过程。一旦任何其他 node 返回了所要的 Value，搜索的过程就结束。
 2) cache: 如果搜索成功，搜索的发起者将这个对存储到已知的、最近的、但是在第一步中没有返回该 Value 的 node 上。
    显然，有了cache之后，以后对于该 的搜索很可能首先找到 cache，而不是直到找到最接近 Key 的那个 node。
    如果一个 被频繁的搜索，那么它很可能被缓存到很多 ID 不太接近 Key 的 node 中。
    为了避免过度缓存(over-caching)，每一个 都有一个过期时间，这个过期时间和 当前node 和“最接近Key之node”之间的 node 的个数（这个数目可以从当前node的bucket接口推断出）的指数倒数成正比。（To avoid "over-caching", we make the expiration time of a 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