IPFS 中的分布式哈希表 DHT

分布式哈希表 (Distributed Hash Table, DHT) 是一种用于将键映射到值的分布式系统。在 IPFS 中，DHT 是内容路由系统的基本组件，就像分布式的文件索引系统，将用户要查找的内容与存储该内容的节点联系起来。可以将其想象成一个巨大的电话簿，存储着谁拥有什么数据。使用 DHT 映射的键值对分为三种类型：

这些类型的含义略有不同，但它们都使用相同的 DHT 协议进行更新和查找。IPFS 使用改良的 Kademlia。

1 Kademlia

Kademlia 算法的目的是在三个系统参数之上构建 DHT：

1. 地址空间 (address space) ：可以唯一标识所有网络节点的方式。在 IPFS 中是从 0 到 2^256-1 的所有数字。
2. 度量 (metric)：对地址空间中的对等点进行排序的标准，IPFS 采用 SHA256(PeerID) 并将其转换为 0 到 2^256-1 之间的整数。
3. 投射方法 (projection)：根据一条记录的record key计算出地址空间中的一个位置，最适合存储该记录的（一个或多个）节点应邻近该位置。 IPFS 采用 SHA256(Record Key)。

有了地址空间和节点排序标准，我们就可以将网络视为一个排序列表进行搜索。我们可以将系统变成类似跳表的形式，其中节点知道距离为 1,2,4,8... 的其他节点。这使我们能在在对数于网络规模的时间内搜索列表，即查找时间为 O(log(N)) 。

与跳表不同，Kademlia 不稳定，因为节点可以随时加入、离开或重新加入网络。为了应对系统的不稳定特性，Kademlia 节点不仅仅保持与距离为 1,2,4,8... 的节点的链接。对于每个 2 的倍数，它保持最多 K 个链接。在 IPFS中 K = 20 。例如，与其保持单个距离 128 的链接，不如保持 20 个距离在 65 到 128 之间的链接。

像 K 这样的网络范围参数的选择不是任意的，而是根据网络中观察到的平均流失率和网络重新发布信息的频率来确定的。系统参数（例如K）的计算旨在最大化网络保持连接的概率，并且在保持理想查询延迟的同时不丢失任何数据，前提是平均流失率观察值保持恒定。这些系统和网络参数驱动着 Kademlia 的两个主要组件的决策：

• 路由表 (routing table)：跟踪网络中的所有链接；
• 查找算法 (lookup algorithm)：确定如何遍历这些链接以存储和检索数据。

1.1 不可拨节点

Kademlia 的一个主要特性是所有节点都可以从小到大排列。该特性的用处在于，当节点 0按顺序寻找节点 55 时，它可以知道自己在逐渐接近目标。但这需要序列中的每个节点都可以相互通信。否则，节点 33 可能会告诉节点 0 想要的内容在无法通信的节点上，这会使网络缓慢、分裂，数据只能被部分节点访问。

节点间无法相互通信的两个常见原因是网络地址转换器 (NAT) 和防火墙。节点 X、Y 和 Z 可以连接到 A 但 A 无法连接到 X、Y 的非对称网络很常见。同样，在 NAT 后的节点 A 和 B 无法相互通信也是非常常见的。为了解决这个问题，IPFS 节点忽略了公认无法访问的节点。如果节点怀疑自己不可达也会将自己从网络中过滤掉。

为此，需要使用 libp2p 的AutoNAT，它充当分布式 STUN 层 ( session traversal utility for NAT, NAT会话穿越应用程序) ，通知节点其地址及节点是否公开可拨。只有当节点检测到自身公开可拨时，才会从客户端模式（可以查询 DHT 但不响应查询）切换到服务器模式（可以查询及响应查询）。同样，如果服务器发现自己不可拨，将切换回客户端模式。

IPFS 在所有公开可拨的 IPFS 节点上暴露速率受限的 AutoNAT 服务。这类请求很少见并且没有明显的开销。

2 双DHT

许多 IPFS 节点使用公共 DHT 发现和宣传内容，但是，某些节点在隔离网络中运行，例如本地网络或隔离的 VPN。一个所有非公开可拨节点都是客户端的 DHT 会为此类用户带来问题，因为节点都不是公开可拨的。

可用于非公用网络节点的 DHT，称为 LAN DHT。与公共的 WAN DHT 完全分离。这两个 DHT 通过使用不同的 DHT 协议名称来区分：

DHT	Path
WAN	/ipfs/kad/1.0.0
LAN	/ipfs/lan/kad/1.0.0

WAN 和 LAN DHT 之间的主要区别在于节点的接受标准：哪些节点有资格成为路由表或查询的一部分。 WAN DHT 的标准是“看起来像不像公共地址”，LAN DHT 的标准是“看起来像不像非公共地址”。 WAN DHT 节点根据其是否公开可拨决定是否从客户端模式切换到服务器模式，而 LAN DHT 节点始终是服务器，除非设置了 dhtclient 选项。

3 路由表

路由表是用于决定网络数据传输路径的一组规则。所有支持 IP 的设备，包括路由器和交换机，都会用到路由表。每个 IPFS 节点都维护一个路由表，其中包含指向网络中其他节点的链接。 IPFS 依靠 Kademlia 算法来定义内容是否应该进入路由表：

1. 当我们连接到一个节点时，检查它是否符合添加到我们的路由表的条件。
2. 如果符合条件，则确定新节点与我们的距离，以确定它应该进入哪个桶 (bucket)。
3. 尝试将节点放入桶中。
4. 如果我们无法连接到路由表中的某个节点，则将其从路由表中删除。

这里有三个值得注意的属性：条件、桶和刷新/删除节点。

3.1 条件

可以被添加进路由表的节点满足以下两个条件：

1. 确保节点是 DHT 服务器，且在宣传 DHT 协议 ID，WAN DHT 为 /ipfs/kad/1.0.0，LAN DHT 为 /ipfs/lan/kad/1.0.0。
2. 确保节点 IP 地址与我们预期的范围相匹配。例如，公共 DHT 的成员至少有一个公共范围的 IP 地址，而不是只有 192.168.X.Y 这样的地址。

3.2 节点桶

桶是最多 20 个具有相似地址的节点的集合。例如，如果节点距离我们在 2^7 到 2^8 之间，地址空间大小为 2^256，则节点进入桶 256-8。如果该桶中节点少于 20 个，则可以将节点添加进该桶。如果该桶已经有 20 个节点，则 IPFS 决定是否可以删除其中的节点。否则，IPFS 不会将节点添加到桶中。

3.3 刷新/删除节点

为保持路由表准确、及时更新，IPFS 每 10 分钟刷新一次路由表。虽然比必要的频率高，但在 IPFS 获取更多 DHT 网络动态信息的同时确保网络的健康非常重要。路由表刷新的工作方式如下：

1. 遍历所有桶，从桶 0 到包含节点的最高桶。最大可能的桶数上限为 15。
   1. 对于每个桶，在 Kademlia 空间中选择一个可以放入该桶的随机地址，并进行查找以找到离该随机地址最近的 K 个节点。这可以确保我们用尽可能多的节点填满每个桶。
2. 此外，在网络中搜索我们自己，以防网络规模和网络分布使得前 15 个桶不足以包含离我们最近的 K 个节点。

节点可以出于几个原因从路由表中删除，通常是因为该节点离线或无法访问。每次刷新后，IPFS 都会遍历路由表并尝试连接到我们最近没有查询过的节点。如果节点不活跃或不在线，就会从路由表中被删除。如果节点在一次刷新时的预期可用时限内不可用，也会被删除。该时限为 Log(1/K) * Log(1 - α/K) * refreshPeriod，其中 α 是可以同时查询的节点数。此外， IPFS 将“可用”定义为“响应时间不超过路由表中任意节点响应时间的二倍”。这主要针对缓慢、过载、不可靠或与我们的网络连接不良的节点。

4 查找算法

查找算法回答了“最接近 X 的 K 个节点是哪些？”。 Kademlia 查找算法的 IPFS 实现工作流程如下：

1. 从路由表中将 K 个最接近 X 的节点加载到查询队列中。
2. 允许最多 10 个并发查询，找到最接近 X 的节点并询问其哪些是最接近 X 的 K 个节点？
3. 当对某节点的查询完成后，将结果添加到查询队列中。
4. 将次近的节点拉出队列并对其进行查询。
5. 只要成功查询到距 X 最近的三个已知节点且没有任何超时或错误，终止查询。
6. 查询完成后，取出最近的 K 个未失败的节点并返回。