基本内容

Kademlia 是由 Petar Maymounkov 与 David Mazières 所设计的P2P 重叠 网络传输协议，以构建分布式的P2P 电脑网络。是一种基于 异或运算的P2P信息系统。它制定了网络的结构及规范了节点间通讯和交换资讯的方式。

Kademlia 节点间使用传输 通讯协议 UDP 沟通。Kademlia 节点利用 分布式散列表 (DHT) 储存资料索引。透过现有的局域网/ 广域网( LAN/WAN)，建立起一个新的 虚拟网络或重叠网络。

一个想要加入网络的节点需要先经过启动过程。在这个阶段，该节点需要知道另一个已经在 Kademlia 网络中注册的节点的 IP 地址 （通过另一个使用者或储存的清单取得）。如果启动中的节点还不是网络的一部分，它便会计算一个尚未指定给其他节点的随机ID（160比特）编号。这个ID是由节点的对外IP地址跟 端口号经过SHA-1算法散列之后得到的。这个 ID 会一直使用到离开网络为止。

Kademlia 内的资讯都储存在称为“值（ value）”的东西内，每个值都连接著一个“键（key）”。每一条<键 值="值">对作为Kad网络的基本信息结构被存储在本地数据库当中。

简单的说，拥有要分享的文件 网络节点，会先处理文件的内容，并从内容计算出一组数字（散列），这组数字将会在 文件分享网络中辨识这个文件。散列与节点 ID 的长度相同。接着会查找几个 ID 与 散列值相近、且节点内有储存著自己 IP 地址的节点。搜索的用户会使用 Kademlia 来搜索网络上节点ID离自己最近距离的节点来取得文件的散列值，然后会取得在该节点上的路由清单。 当节点联入和联出时，这份存储在网络上的路由清单也将保持不变。因为内嵌的冗余存储算法，路由清单将复制在多个节点上。

在Kad网络中，每个节点只负责处理一小部分搜索和查找源的工作。分配这些工作的时候，通过我们每个用户端的唯一的ID和搜索文件的Hash值之间的匹配来决定。

Kademlia 协议原理简介

一、前言

Kademlia协议（以下简称Kad）是 美国纽约大学的PetarP. Maymounkov和David Mazieres.在2002年发布的一项研究结果《Kademlia: A peerto -peer information system based onthe XOR metric》。

简单的说，Kad 是一种分布式 哈希表（DHT）技术，不过和其他DHT 实现技术比较，如Chord、CAN、Pastry 等，Kad 通过独特的以异或算法（XOR）为 距离度量基础，建立了一种全新的DHT拓扑结构，相比于其他算法，大大提高了路由查询速度。

在2005 年5 月著名的BiTtorrent 在4.1.0 版实现基于Kademlia 协议的DHT 技术后，很快国内的BitComet 和BitSpirit 也实现了和BitTorrent 兼容的DHT 技术，实现trackerless下载方式。

另外， emule 中也很早就实现了基于Kademlia类似的技术（BT中叫DHT，emule中也叫Kad，注意和本文简称的Kad 区别），和BT 软件使用的Kad 技术的区别在于key、value 和node ID 的计算方法不同。

二、节点状态

在Kad网络中，所有节点都被当作一颗 二叉树的叶子，并且每一个节点的位置都由其ID值的最短前缀唯一的确定。

对于任意一个节点，都可以把这颗二叉树分解为一系列连续的，不包含自己的子树。最高层的子树，由整颗树不包含自己的树的另一半组成；下一层子树由剩下部分不包含自己的一半组成；依此类推，直到分割完整颗树。图1就展示了节点0011如何进行子树的划分：

图1：节点0011的子树划分

虚线包含的部分就是各子树，由上到下各层的前缀分别为0，01，000，0010。

Kad协议确保每个节点知道其各子树的至少一个节点，只要这些子树 非空。在这个前提下，每个节点都可以通过ID值来找到任何一个节点。这个路由的过程是通过所谓的XOR（异或）距离得到的。