以上图为例。文件 1 通过哈希运算，得到匹配 ID 的 DHT Node 为 Node C（当然还会有其他的，为了便于理解，咱们就先关注 Node C），所以，Node C 就有责任知道文件 1 的存放地址，虽然 Node C 本身没有存放文件 1。

    同理，文件 2 通过哈希计算，得到匹配 ID 的 DHT Node 为 Node E，但是 Node D 和 E 的值很近，所以 Node D 也知道。当然，文件 2 本身不一定在 Node D 和 E 这里，但是我们假设 E 就有一份。

    接下来，一个新节点 Node new 上线了，如果要下载文件 1，它首先要加入 DHT 网络。如何加入呢？

    在这种模式下，种子 .torrent 文件里面就不再是 Tracker 的地址了，而是一个 list 的 Node 地址，所有这些 Node 都是已经在 DHT 网络里面的。当然，随着时间的推移，很有可能有退出的，有下线的，这里我们假设，不会所有的都联系不上，总有一个能联系上。

    那么，Node new 只要在种子里面找到一个 DHT Node，就加入了网络。

    Node new 不知道怎么联系上 Node C，因为种子里面的 Node 列表里面很可能没有 Node C，但是没关系，它可以问。DHT 网络特别像一个社交网络，Node new 会去它能联系上的 Node 问，你们知道 Node C 的联系方式吗？

    在 DHT 网络中，每个 Node 都保存了一定的联系方式，但是肯定没有所有 Node 的联系方式。节点之间通过相互通信，会交流联系方式，也会删除联系方式。这和人们的沟通方式一样，你有你的朋友圈，他有他的朋友圈，你们互相加微信，就互相认识了，但是过一段时间不联系，就可能会删除朋友关系一样。

    在社交网络中，还有个著名的六度理论，就是说社交网络中的任何两个人的直接距离不超过六度，也就是即使你想联系比尔盖茨，最多通过六个人就能够联系上。

    所以，Node New 想联系 Node C，就去万能的朋友圈去问，并且求转发，朋友再问朋友，直到找到 C。如果最后找不到 C，但是能找到离 C 很近的节点，也可以通过 C 的相邻节点下载文件 1。

    在 Node C上，告诉 Node new，要下载文件 1，可以去 B、D、F，这里我们假设 Node new 选择了 Node B，那么新节点就和 B 进行 peer 连接，开始下载。它一旦开始下载，自己本地也有文件 1 了，于是，Node new 就告诉 C 以及 C 的相邻节点，我也有文件 1 了，可以将我加入文件 1 的拥有者列表了。

    你可能会发现，上面的过程中漏掉了 Node new 的文件索引，但是根据哈希算法，一定会有某些文件的哈希值是和 Node new 的 ID 匹配的。在 DHT 网络中，会有节点告诉它，你既然加入了咱们这个网络，也就有责任知道某些文件的下载地址了。

    好了，完成分布式下载了。但是我们上面的过程中遗留了两个细节性的问题。

1）DHT Node ID 以及文件哈希值是什么？
    其实，我们可以将节点 ID 理解为一个 160bits（20字节）的字符串，文件的哈希也使用这样的字符串。

2）所谓 ID 相似，具体到什么程度算相似？
    这里就要说到两个节点距离的定义和计算了。

    在 Kademlia 网络中，两个节点的距离采用的是逻辑上的距离，假设节点 A 和 节点 B 的距离为 d，则：

d = A XOR B

    上面说过，每个节点都有一个哈希 ID，这个 ID 由 20 个字符，160 bits 位组成。这里，我们就用一个 5 bits ID 来举例。
    我们假设，节点 A 的 ID 是 01010，节点 B 的 ID 是 01001，则：

距离 d = A XOR B = 01010 XOR 00011 = 01001 = 9

    所以，我们说节点 A 和节点 B 的逻辑距离为 9。

    回到我们上面的问题，哈希值接近，可以理解为距离接近，也即，和这个节点距离近的 N 个节点要知道文件的保存位置。

    要注意的是，这个距离不是地理位置，因为在 Kademlia 网络中，位置近不算近，ID 近才算近。我们可以将这个距离理解为社交距离，也就是在朋友圈中的距离，或者社交网络中的距离。这个和你的空间位置没有多少关系，和人的经历关系比较大。

DHT 网络节点关系的维护

    就像人一样，虽然我们常联系的只有少数，但是朋友圈肯定是远近都有。DHT 网络的朋友圈也一样，远近都有，并且按距离分层。

    假设某个节点的 ID 为 01010，如果一个节点的 ID，前面所有位数都与它相同，只有最后 1 位不停，这样的节点只有 1 个，为 01011。与基础节点的异或值为 00001，也就是距离为 1。那么对于 01010 而言，这样的节点归为第一层节点，也就是k-buket 1。

    类似的，如果一个节点的 ID，前面所有位数和基础节点都相同，从倒数第 2 位开始不同，这样的节点只有 2 个，即 01000 和 01001，与基础节点的亦或值为 00010 和 00011，也就是距离为 2 和 3。这样的节点归为第二层节点，也就是k-bucket 2。

    所以，我们可以总结出以下规律：

如果一个节点的 ID，前面所有位数相同，从倒数第 i 位开始不同，这样的节点只有 2^(i-1) 个，与基础节点的距离范围为 [2^(i-1), 2^i]，对于原始节点而言，这样的节点归为k-bucket i。

    你会发现，差距越大，陌生人就越多。但是朋友圈不能把所有的都放下，所以每一层都只放 K 个，这个 K 是可以通过参数配置的。

DHT 网络中查找好友

    假设，Node A 的 ID 为 00110，要找 B（10000），异或距离为 10110，距离范围在 [2^4, 2^5)，这就说明 B 的 ID 和 A 的从第 5 位开始不同，所以 B 可能在 k-bucket 5 中。

    然后，A 看看自己的 k-bucket 5 有没有 B，如果有，结束查找。如果没有，就在 k-bucket 5 里随便找一个 C。因为是二进制，C、B 都和 A 的第 5 位不停，那么 C 的 ID 第5 位肯定与 B 相同，即它与 B 的距离小于 2^4，相当于 A、B 之间的距离缩短了一半以上。

    接着，再请求 C，在 C 的通讯里里，按同样的查找方式找 B，如果 C 找到了 B，就告诉 A。如果 C 也没有找到 B，就按同样的搜索方法，在自己的通讯里里找到一个离 B 更近一步的 D（D、B 之间距离小于 2^3），把 D 推荐给 A，A 请求 D 进行下一步查找。

    你可能已经发现了，Kademlia 这种查询机制，是通过折半查找的方式来收缩范围，对于总的节点数目为 N 的网络，最多只需要 log2(N) 次查询，就能够找到目标。

    如下图，A 节点找 B 节点，最坏查找情况：

    图中过程如下：

1. A 和 B 的每一位都不一样，所以相差 31，A 找到的朋友 C，不巧正好在中间，和 A 的距离是 16，和 B 的距离是 15；
2. C 去自己朋友圈找，碰巧找到了 D，距离 C 为 8，距离 B 为 7；
3. D 去自己朋友圈找，碰巧找到了 E，距离 D 为 4，距离 B 为 3；
4. E 在自己朋友圈找，找到了 F，距离 E 为 2，距离 B 为 1；
5. F 在距离为 1 的地方找到了 B。

节点的沟通

    在 Kademlia 算法中，每个节点下面 4 个指令：

• PING：测试一个节点是否在线。相当于打个电话，看还能打通不；
• STORE：要钱一个节点存储一份数据；
• FIND_NODE：根据节点 ID 查找一个节点；
• FIND_VALUE：根据 KEY 查找一个数据，实则上和 FIND_NODE 非常类似。KEY 就是文件对应的哈希值，找到保存文件的节点。

节点的更新

    整个 DHT 网络，会通过相互通信，维护自己朋友圈好友的状态。

• 每个 bucket 里的节点，都按最后一次接触时间倒序排列。相当于，朋友圈里最近联系的人往往是最熟的；
• 每次执行四个指令中的任意一个都会触发更新；
• 当一个节点与自己接触时，检查它是否已经在 k-bucket 中。就是说是否已经在朋友圈。如果在，那么就将它移到 k-bucket 列表的最底，也就是最新的位置（刚联系过，就置顶下，方便以后多联系）。如果不在，就要考虑新的联系人要不要加到通讯录里面。假设通讯录已满，就 PING 一下列表最上面的节点（最旧的），如果 PING 通了，将旧节点移动到列表最底，并丢弃新节点（老朋友还是要留点情面的）。如 PING 不同，就删除旧节点，并将新节点加入列表（联系不上的老朋友还是删掉吧）。

    通过上面这个机制，保证了任意节点的加入和离开都不影响整体网络。

小结

• 下载一个文件可以通过 HTTP 或 FTP。这两种都是集中下载的方式，而 P2P 则换了一种思路，采用非中心化下载的方式；
• P2P 有两种。一种是依赖于 Tracker 的，也就是元数据集中，文件数据分散。另一种是基于分布式的哈希算法，元数据和文件数据全部分散。

参考：

1. 维基百科-DHT 网络词条；
2. 维基百科-Kademlia 词条；
3. 刘超 - 趣谈网络协议系列课；