四月底，我们发布了迄今为止最大的 Go-IPFS 更新：IPFS 0.5。虽然有很多改进，但是对 IPFS 的分布式哈希表(DHT)的更改对于提高 IPFS 中查找数据的性能和稳定性尤为关键。有关我们如何实现最新的 DHT 更改的一些背景信息，请查看“通往新分布式哈希表之路”，或者在最新版本的 GO-IPFS 中亲自尝试这些更改。

在这篇文章中，我们想带你详细了解 DHT 在 v0.5.0 中的样子，所以准备好看一篇真正深入了解 IPFS DHT 表实现。如果您想了解 DHT 是如何工作的，以及我们如何使 IPFS 使用的实现更快、更具弹性，请继续阅读！

背景：DHT 对 IPFS 有何作用？

DHT 是用于将键映射到值的分布式系统。在 IPFS 中，DHT 用作内容路由系统的基本组件。它将用户正在查找的内容(CID)映射到实际存储匹配内容的对等点。使用 DHT 映射的键值对有3种类型：

• 提供者记录：这些记录将数据标识符（即，多哈希）映射到已通告其拥有并愿意为您提供该内容的对等方。

• IPFS 用于查找内容。

• IPNS 在 PubSub 上使用它来查找 pubsub 主题的其他成员。

• IPNS 记录：这些将 IPNS 密钥（即，公共密钥的哈希）映射到 IPNS 记录（即，指向诸如的某些路径的已签名和版本化的指针/ipfs/bafyXYZ）

• 由IPNS使用

• 对等记录：这些将对等 ID 映射到一组可以到达对等体的多地址。

• 当我们知道具有内容的对等方但不知道其地址时，由IPFS使用。

• 用于手动连接（例如ipfs swarm connect /p2p/QmXYZ）。

这些记录类型中的每一个都有稍微不同的语义，但是它们都是通过相同的 DHT 协议（IPFS在Kademlia上采用的）更新和找到的。

Kademlia 概述

Kademlia 算法已经存在了一段时间，并且已经有很多在线资源可供使用，包括论文本身和维基百科。不过，我们将在这里介绍一些基础知识。

Kademlia 的总体思路是在三个系统参数之上构建 DHT：

• 地址空间：一种可以唯一标识网络中所有对等点的方式（在IPFS中，这是从0到的所有数字2^256-1）

• 一种度量，用于对地址空间中的对等点进行排序，从而沿从小到大的顺序可视化所有对等点(在IPFS中，我们采用SHA256(PeerID)并将其解释为介于 0 和2^256-1之间的整数)。

• 一个投影，它将获取一条记录键并计算出地址空间中最适合存储记录的对等体应该位于的位置（在IPFS中，我们使用SHA256(Record Key)）

有了这个地址空间和对等点排序度量，我们就可以像搜索排序列表一样搜索网络。特别地，我们可以将系统变成类似于跳过列表的东西，其中对等体知道距离约为 1，2，4，8，16…的对等体。这将允许我们在网络大小对数的时间内搜索列表(即O(log(N))查找时间)。与跳跃列表不同，Kademlia 有点不稳定，因为对等点可以随时加入、离开和重新加入网络。为了处理系统的不稳定特性，Kademlia 对等体不仅保持到距离为 1、2、4、8、…的对等体的链接。远离它，但取而代之的是，对于每 2 个离开的倍数，它保持最多K个(在IPFS 20中)链接。例如，与对等点保持单个链路128距离不同，它将保持 65 到 128 之间的 20 个链路距离。

注意，像 K 这样的网络范围参数的选择不是任意的，而是基于在网络中观察到的平均抖动和网络将重新发布信息的频率来确定的。计算系统参数(如K)以最大化网络保持连接且没有数据丢失的概率，同时保持查询所需的延迟，并假设(平均流失)观测保持恒定。这些系统和网络参数驱动着在 Kademlia 的两个主要组件中做出的决策，一个是跟踪网络中所有这些链路的路由表，另一个是确定如何遍历这些链路以存储和检索数据的查找算法。

Kademlia 和不可拨号的对等点

如上所述，Kademlia 的一个主要属性是所有对等点都可以从最小到最大以内联方式组装。该属性是有用的，因为它意味着当对等体 0 沿着线路行进以找到对等体 55 时，它可以知道它正逐渐靠近。然而，这要求线路上的每个人都可以相互交谈，否则对等点 33 可能会通过告诉对等点 0 他们想要的内容在他们无法通信的节点上而将其送进死胡同。这可能会导致网络速度变慢，更重要的是，一些对等点可以访问数据，而其他对等点不能访问，从而导致数据碎片化。

虽然无法相互通信的对等点听起来很奇怪，但其他对等点无法到达的两个常见原因是 NAT 和防火墙。例如，具有不对称网络，其中一组对等体 X、Y、Z 可以彼此连接并且可以连接到 A，但是 A 不能连接到它们在现代互联网上是相当常见的。同样，都在 NAT 之后的两个对等体 A 和 B 无法相互通信(或拨号)的情况也非常常见。

当 IPFS 网络在 2019 年增长 30 倍时，我们遇到了一个大问题：突然之间，IPFS  DHT 上的大多数对等点都在 NAT 之后，这降低了质量，因为你无法拨打应该具有给定内容的对等点。为了解决这个问题，我们现在让对等点忽略他们认为公众无法联系到的任何人，并让对等点在怀疑自己无法联系到的情况下将自己从网络中过滤出来。

为此，我们使用 libp2p 的 AutoNAT，它充当分布式 STUN 层，通知对等方观察到的地址以及它们是否可公开拨号。只有当对等设备检测到它们可以公开拨号时，它们才会从客户端模式(它们可以查询DHT，但不响应查询)切换到服务器模式(它们既可以查询又可以响应查询)。同样，如果服务器发现它不再可以公开拨号，它将切换回客户端模式。

服务 AutoNAT 请求(即，检查其他对等方是否可拨号)以前仅在选择加入节点(如某些IPFS公共基础设施)上启用。然而，如此严重地依赖AutoNAT来清理DHT中无法拨号的节点，促使我们推动 AutoNAT 变得更加分布式。因此，我们现在在发现它们可以公开拨号的所有 IPFS 节点上公开速率限制的 AutoNAT 服务。这些请求应该不频繁，因此对于标准 IPFS 节点没有明显的开销。

注意：DHT 客户端和服务器模式之间的自动切换是默认配置选项，但是，如果需要，也可以将您的节点设置为仅为“客户端”。在使用“dht”(自动模式)或“dhtclient”(仅客户端模式)之外的任何选项时错误配置您的网络设置，可能会通过向网络添加不可拨号的节点而降低您和其他所有人的网络性能，因此请谨慎操作。

虽然基于 AutoNAT 的模式切换很棒，我们希望它能将大多数不可拨号的节点清除出网络，但在将节点添加到它们的路由表或向它们发出查询之前，DHT 对等点(客户端和服务器)也应该验证节点是否可公开拨号(例如，通告公共 IP 地址，而不仅仅是192.168.X.Y这样的地址)，这似乎是唯一谨慎的做法。

两个 IPFS DHT：公共和本地

虽然我们的许多用户使用公共共享的 DHT 来发现和通告内容，但其中一些用户在隔离的网络(例如，本地网络或隔离的VPN)中运行。对于这些用户来说，拥有所有非公开拨号节点都是客户端的 DHT 是非常有问题的，因为没有一个节点是公开拨号的。

为了简化此用例，我们添加了第二个 DHT，该 DHT 将包括不属于公共网络的节点，如 VPN、CJDNS、Yggdrasil 等。目前，我们将其称为 LAN DHT，而不是公共网络，即 WAN DHT。(这两个DHT通过使用不同的分布式哈希表协议名称(即，用于 WAN DHT 的/ipfs/kad/1.0.0 和用于局域网 DHT 的/ipfs/lan/kad/1.0.0)分开，以消除两个网络的任何意外合并。但是，如果用户没有正确配置他们的网络，所有的非公共网络都有合并的风险。

WAN 和 LAN DHT 之间的主要实施差异在于对等项的接受标准，它们有资格成为路由表或查询的一部分，而哪些不是。WAN DHT 的标准是“您看起来像公共地址吗”，局域网 DHT 的标准是“您看起来像非公共地址吗”。但是，当 WAN DHT 节点根据它们是否可公开拨号从客户端模式切换到服务器模式时，LAN DHT 节点始终是服务器(除非设置了“dhtclient”选项)。

路由表

如前所述，Kademlia 网络中的每个对等方都维护与网络中其他各个对等方的链接。其工作方式如下：

1. 当我们连接到对等体时，检查它是否符合添加到我们的路由表中的条件。

• 确保对等体是发布 DHT 协议 ID 的 DHT 服务器（在IPFS中/ipfs/kad/1.0.0为公用/ WAN DHT和/ipfs/lan/kad/1.0.0LAN DHT）。

• 确保对等方具有与我们预期的范围相匹配的IP地址（例如，公共DHT的成员至少具有一个公共范围IP地址，而不是仅类似的地址192.168.X.Y）

2. 如果符合条件，则确定新对等方在 Kademlia 地址空间中与我们的距离，以弄清应该进入哪个“存储桶”（即，对等方与我们和地址之间的距离在2 ^ 7到2 ^ 8之间）空间的大小为2 ^ 256，则对等方进入存储区256-8）。

3. 尝试将对等方放入桶中。

• 如果存储桶未满（例如，其中的对等体少于20个），则添加对等体。

• 如果存储桶已满，则确定是否有“可替换”（定义如下）的对等项，然后删除其中一个对等项并用新的对等项替换。否则，请勿将对等方添加到存储桶中。

4. 如果我们曾经尝试查询路由表中的对等节点而失败，则驱逐它们。

• 注意：每次刷新后（请参阅下文），我们将遍历路由表，并尝试连接到尚未“最近”查询的对等方，以检查它们是否仍然在线以及对我们的路由表有效的对等方。如果没有，那么我们将其逐出。

此外，为了保持路由表的准确性和最新性，我们会定期刷新路由表。路由表刷新的频率是根据与存储桶大小类似的一组指标来计算的（您可以增加刷新的频率，但是可能会降低多少）。对于 IPFS，将下限频率选择为每 10 分钟一次。虽然这可能比严格要求的频率高，但是我们认为保护网络的健康非常重要，因为我们会更多地了解 go-ipfs v0.5.0 采纳后的 IPFS DHT 网络动态。

路由表刷新的工作方式如下：

1. 遍历所有存储桶，从存储桶 0（与对等设备位于网络另一半的那个存储桶）一直到拥有该存储桶的最高存储桶（由于实现而将其限制在存储桶15）关注）。对于每个存储桶，请在 Kademlia 空间中选择一个适合该存储桶的随机地址（例如，在512和1024之间选择一个随机对等体时，即使该对等体可能不在网络中，我们也选择了678），并进行查找以查找 K 最接近该随机地址的对等体。这将确保我们将在每个存储桶中填充尽可能多的对等端。

2. 我们也会在网络（即存储桶255）中搜索自己，以防万一网络规模和分布使得前 15 个存储桶不足以让我们了解 K 距离我们最近的对等点。

查找算法

查找算法回答了“ K 最接近的对等点是 X 什么？”的问题。我们对 Kademlia 查找算法的实现如下所示：

1. 将K最接近的对等节点 X 从路由表加载到查询队列中。

2. 最多允许 Alpha 并发查询（go-ipfs中的Alpha为10，但实现参数不是网络本身固有的），抓住最接近的对等点X并询问他们“谁是K最接近的对等点 X？”

3. 对对等方的查询完成后，将这些结果添加到查询队列中，然后将下一个最近的对等方从队列中拉出并进行查询。

4. 只要 X 成功查询了最接近的已知 Beta 对等方（即没有拨号超时，错误等），查询就会终止。

• 注意：Beta 是网络范围的参数，旨在为网络提供一定的弹性，对于 IPFS，将其设置为 3。

5. 查询完成后，获取 K 我们尚未在查询中失败的最接近的对等体（即，我们已经收到他们的来信或他们仍在队列中）并返回它们。

• 注意：出于某些 API 兼容性原因，go-ipfs 还可确保我们实际上已将查询发送给所有顶级 K 对等方。

在路由表部分，我们提到如果发现可以在存储桶中占据一席之地的新对等点，则将其“可替换”对等点逐出。在 v0.5.0 中，如果对等体在概率性地希望被刷新利用的时间内没有对我们有用，则将其定义为“可替代”。该值是 Log(1/K) * Log(1 - Alpha/K) * refreshPeriod，其中 Alpha 是可以同时查询的对等拨号号码。

另外，我们将“有用”定义为在路由表中的任何其他对等方响应我们之前的 2 倍以内做出响应（这偏向于对等方速度较慢，过载，不可靠或对我们的网络连接不良）。当我们收集有关网络动态的更多信息并调查相关威胁模型时，可替换和有用对等方的定义可能会更改。

路线详情

尽管查找算法使我们可以将记录放入 DHT 中，但对于每种记录类型，这样做的方式略有不同：

• 提供者记录（对于具有 Multihash 的块 H）

• 对等方添加它已了解的所有新提供程序，并继续进行直到查找终止。根据所使用的 API，在收到一定数量的提供程序记录后，也可以强制中止查找。

• 将提供者记录放在K最接近的对等方（也可以自己存储）

• 注意：目前，您仅允许自己放置提供商记录（即Alice无法宣传Bob的内容）

• PUT：对K距离最近的对等点进行标准查找 SHA256(H)

• GET：查找K最接近的对等实体 X=SHA256(H)，而不仅仅是询问查找中的每个对等实体“ 您知道谁是K最接近的对等实体X？” 还问“请把与 X 您有记录相对应的记录发送给我”。

• IPNS 记录（对于公共密钥的多重哈希为的IPNS密钥H）

• 如果用户收到更新的记录（即，具有较高IPNS序列号的记录），它将更新其现有记录并继续直到查找终止。为了确保用户获得最新记录，这是必需的。回想一下 IPNS 记录是可变的，因此，我们需要确保将请求指向内容的最新版本。

• 查找完成后，如果K最接近的对等方X没有最新的 IPNS 记录，请向他们发送最新的记录

• go-ipfs 中的默认设置将在接收到 16 条记录后提前中止，但是可以将其设置为 go，直到查询终止

• 将 IPNS 记录放在 K 最接近的对等方（并自己存储）

• PUT：对 K 距离最近的对等点进行标准查找 SHA256(/ipns/H)

• GET：查找 K 最接近的对等实体 X=SHA256(/ipns/H)，而不仅仅是询问查找中的每个对等实体“ 您知道谁是K最接近的对等实体 X？” 还问“请把与 X 您有记录相对应的记录发送给我”。

• 对等记录（对于公共密钥的多重哈希为的对等体H）

• 一旦了解到 ID 为 H 的对等设备的地址，我们将立即尝试连接到该对等设备。如果我们最终连接到对等点，查找可能会提前终止。

• PUT：这是隐式发生的 libp2p 对等体彼此连接时，它们会自动交换对等体信息。作为 DHT 的一部分（无论是作为客户端还是作为服务器），都需要经常与您 K 最接近的对等方联系，因此，它们最终会以您的对等方记录为最终对象。

• GET：查找 K 最接近的对等实体 X=SHA256(H)，而不仅仅是询问查找中的每个对等实体“ 您知道谁是 K 最接近的对等实体 X？” 还问“请给我您的同伴记录，H 如果有的话”

测试和结果

作为 Go-IPFS v0.5.0 版本的一部分，DHT 有很多变化。虽然直觉上看，许多变化将非常有用，但我们需要更有力的证据来证明全套变化将产生一个稳定和性能良好的网络。为此，我们利用了 Testround，这是一种新的分布式测试基础设施(请在Testround的博客文章中查看他们的发布说明)。

在整个开发过程中，我们运行了许多 Testround 测试，以了解我们的更改如何改进了网络。下面是1000个对等点网络的性能比较，其中所有对等点彼此具有大约 100-120ms 的延迟，即从 Go-IPFS v0.4.23 运行 DHT，从 Go-IPFS v0.5.0 运行 DHT。注意：v0.4.23DHT 做了一些小的修改，使测试变得更容易，比如删除了硬编码的查找超时，因此我们可以看到查询实际应该运行多长时间。

从图表中可以看到，最大的变化是第 95 个百分位的查找时间，以及那些花费更多时间进行查找并且不能提前终止的操作。这意味着需要通过网络实际完成搜索的 IPFS Provide 和 IPNS put 获得了非常大的提升(平均提供24倍的加速，第95个百分位数的加速33倍)，这意味着 IPFS Provide 和 IPNS put 获得了非常大的提升(提供平均24倍的加速比和33倍的第95个百分位数的加速比)。紧随其后的是 IPNS GET，它需要查找许多记录，然后是查找一个非常具体的记录的Peer，最后，仅查找一个IPFS提供商记录的时间平均加快了 2.2 倍，第 95 个百分位数加快了 6.4 倍。

最后的想法

IPFS v0.5.0 包含了许多DHT的更改和改进。需要注意的是，新节点当前与较旧的 Go-IPFv0.4.23 和更早版本的节点参与相同的 DHT。虽然 V0.5.0 的 DHT 代码比以前的版本有了很大的改进，但大型网络中的单个节点只能提供这么多帮助。这意味着当您运行 v0.5.0 时，您应该会看到性能的提高，但是随着更多的网络升级到 v0.5.0 及更高版本，我们将继续看到查找时间的改善。

接下来还会有更多令人兴奋的改进，所以如果您有兴趣贡献或者只是跟踪我们的改进，请在 GitHub 上关注我们的存储库，并在 IRC 上与我们聊天。