概述
散列表是一种由键值对组成的列表。你可以把它看作一部字典，只需要经过少数的几步就能通过某种信息找到需要的信息，查询速度很快。
分布式散列表就是由一个网络内所有的节点共同维护的一种散列表，这类散列表通常十分巨大，或者压根不可能由单个机器或者某机组机器维护。
Kademlia 协议由 Petar Maymounkov 和 David Mazières 设计。它可以在容易出错的环境（比如节点会毫无征兆地下线）中建立一张分布式散列表。
为什么需要分布式散列表？
当散列表不是很大的时候只需要存储在一个机器上即可，但是有时哈希表会十分大，大到不是几组机器能够维护。亦或者有些哈希表是无法进行集中式存储的，比如 BitTorrent 的 DHT 网络。
以 BitTorrent 网络为例，每个文件都有一个文件 ID，文件 ID 是一个长度为 160 的二进制数。每个 BitTorent 节点也会有一个相同长度的节点 ID。文件 ID 和 节点 ID 之间是“多对多”的关系，想使用散列表集中式地存储这些信息几乎是不可能的，原因如下。
- 文件 ID 的取值空间十分巨大，即 $2^{160} \approx 1.46 \times 10^{48}$。这个值有多大？全球一共有 70 亿人，每个人每秒下载 1,000,000 个文件， 大概需要 $6 \times 10^{16}$ 亿年才能下载完。
- 节点 ID 的取值空间也和文件 ID 的取值空间同样巨大。
- 节点 ID 和文件 ID 之间是多对多的关系，我们假设每个节点指对应两个文件 ID，那么共需要存储 $2^{161}$ 个项目，这几乎不可能。
由此可见，仅从空间成本上来看就是不可能的事情，更不要说节点随时会下线和故障等头疼的问题。
分布散列表是由所有节点共同维护一个散列表，每个节点维护一部分，这样网络内就形成了一张巨大的散列表。
前置知识
Kademlia 协议要求每个节点都有一个长度为 160 bit 的节点 ID。
”异或“距离
Kademlia 协议使用”异或“算法来计算两个 ID 之间的距离，下面是一个例子。
假设节点ID 是 4 位二进制。
A 的 ID 为 0101
B 的 ID 为 1111
那么两者的距离就是 1010，换算成十进制就是 9。
0 1 0 1
⊕ 1 1 1 1
--------------
1 0 1 0二进制二叉树
每个节点都有一个长度固定的节点 ID，那么就可以将系统中的全部节点放到一个二叉树内，下面是一个例子。
假设节点 ID 的长度为 3 位二进制，则二叉树的每个叶子节点都代表了一个节点。
*
/ \
/ \
0 / \ 1
/ \
/ \
* *
/ \ / \
0 / \ 1 0 / \ 1
/ \ / \
O O O O信息的存储和查询
在 Kademlia 协议中，每个信息都有一个唯一的 ID，而发布这个信息的节点会将这个信息存储到距离距离信息 ID 最近的若干的节点中。可以认为是用全部已知节点 ID 和信息 ID 进行异或运算得到已知节点和信息之间的逻辑距离，然后选出若干个最近的节点，将信息存储到这些节点上。
查询某个信息时，过程可以认为是用全部的已知节点 ID 和被查询的信息 ID 进行异或运算得到已知节点和信息的逻辑距离，然后选择出若干的最近的节点，然后向这些节点发起信息查询请求。
路由表
Kademlia 协议依靠路由表和其它节点通信，下面介绍一下路由表的建立过程。
前面我们提到网络中的节点都可以放到同一个二进制二叉树中，而路由表的制作过程实际上就是二叉树的拆分过程。我们假设节点 ID 为 11（二进制），看看二叉树的拆分过程。
首先将不包含自身的最大子树取出。
+--------------+
| *|
| / | \
| / | \
| 0 / | \ 1
| / | \
| / | \
| * | *
| / \ | / \
| 0 / \ 1 | 0 / \ 1
| / \ | / \
| O O | O O
+--------------+重复上述步骤，直到剩余的部分只有自己这一个节点。本例中只需要拆分两次。
+--------------+
| * |
| / | \
| / | \
| 0 / | \ 1
| / | \
| / | \
| | +-------+
| * | | *|
| / \ | | / |\
| 0 / \ 1 | | 0 / | \ 1
| / \ | | / | \
| O O | | O | O
+--------------+ +-------+此时我们从左到右一共有了三颗子树，其中第三颗子树只有我们自己。此时三颗子树就对应了三个 K-桶（K-Bucket）。
| 编号 | 覆盖前缀 | 距离区间 | 已经联系上的节点 |
|---|---|---|---|
| 1 | 11 | 0 | … |
| 2 | 10 | 1 | … |
| 3 | 0? | [2, 3] | … |
这就是我们的路由表了，此时我们可以通过下列步骤查询距离某个 key 最近的节点，假设我们要寻找的 key 为 00（二进制），我们自己的节点 ID 为 11（二进制）。
- 使用异或运算计算出自身和目标 key 的距离，计算结果为 2（十进制）。
- 查询 K-桶的距离区间，发现 3 号 K-桶中的节点距离目标 key 最近。
- 按照某种策略（见后文）选出三号 K-桶中的某个节点（假设为节点 01），然后向其发送查询请求。
- 节点 01 也会使用相同的方式建立自己的路由表，收到查询请求后它会执行下列步骤。
- 使用异或运算计算出自身和目标 key 的距离，显然距离为 1（十进制）。
- 查询自身的 K-桶的距离区间，发现某个 K-桶的距离区间恰好为 1，并且此 K-桶内只有一个节点。
- 节点 01 发现自己已经存储了节点 00 的联系信息，于是将联系信息返回给节点 11。
- 节点 00 收到了节点 01 的响应，得知了节点 00 的联系信息，查询结束。
这只是一个简单的例子，有很多错误，还有很多情况没有考虑到，但已经能够体现查询原理了。
三个协议过程
Kademlia 由三个 RPC 过程组成，分别为 PING、STORE、FIND_NODE 和 FIND_VALUE。
RPC（Remote Procedure Call），即远程过程调用。可以简单地认为是一方向另一方发送某个指令，接收方执行对应的指令并将结果返回给发送方。
PING
用来测试节点是否在线。
STORE
请求目标节点存储一个键值对。
FIND_NODE
查询距离目标键值最近的若干的节点。
这个才是重点，本文将在这里详细描述查询过程。
此过程的参数是一个 160 bit 的节点 ID，即要查询目标节点的 ID。此过程结束后返回若干个三元组 < IP, UDP port, Node ID >，每个三元组都是某个节点的联系信息。
当一个节点收到 FIND_NODE 请求时，它会查询自己的 K-桶列表并返回 k 个距离目标节点最近的节点，如果此节点已知的节点不足 k 个则返回全部已知的节点。
当一个节点想要查询某个节点时，它会执行下列步骤。
- 查询自己的 k 桶列表并选出若干个距离目标最近的节点，然后向这些节点发送 FIND_NODE 请求。
- 当这些 FIND_NODE 请求返回时我们会得到许多个节点，记录这些新的节点。
- 从新得到的节点中挑选出若干个距离目标节点更近（相对于所有旧的节点）的节点，向这些节点发送 FIND_NODE 请求。如果没有找到距离更近的节点则查询结束
- 重复步骤 2，3，直到查询结束。
上面的步骤依然是简化的版本，但步骤已经完整了，只是跳过了一些细节，比如每次选择多少个节点发送请求。
FIND_VALUE
基本和 FIND_NODE 差不多，只不过如果收到请求的节点存有被请求的值得时候应该将其值返回。
信息的再发布
有两种情况可能会导致已经存在的信息却不能被查询到。
- 存储了这些信息的全部节点下线。
- 有许多距离更近的节点加入到了网络中，查询信息时则会向这些节点发起请求，而不是距离更远的但是之前已经存储了信息的节点。
为了缓解这一情况，每个节点会以一小时为周期，每个周期内重新发布一次信息。但是这么做的代价很大。假设有 A 个节点存储了同一个信息，那么每个周期内，每个节点都会先发起一次 FIND_NODE 请求，然后每个节点都会向其它最多 A-1 个节点发起 STORE 请求。这样网络中就会充斥着大量的请求，并且很多是无用的请求。
好在我们有优化方法，即当某个节点在本周期内收到 STORE 请求时，下一个周期内就不进行对该信息的再发布。
典型应用
BitTorrent 协议簇中的分布式散列表（DHT）协议及由此构成的属于 BitTorrent 网络内部的 DHT 网络。正是有了 DHT 网络，我们才能够在没有 .torrent 文件的情况下凭借磁力链接下载文件。我们有时候在 BitTorrent 客户端中粘贴一段十六进制字符串就能进行下载也是 DHT 网络的功劳。
参考资料
Kademlia: A Peer-to-peer information system based on the XOR Metric