IPFS 0.5内容路由改进：更深入的研究 | 萤火虫Filecoin矿机
2020/7/23 9:49:19
原创：Adin Schmahmann
原文链接：https://blog.ipfs.io/2020-07-20-dht-deep-dive/
4月底，我们发布了迄今为止最大的go-ipfs更新：IPFS 0.5。尽管有许多改进，但是IPFS的分布式哈希表（DHT）的更改对于提高IPFS中查找数据的性能和稳定性尤其重要。有关我们如何实现最新DHT更改的一些背景知识，请查看《通往新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算法已经存在了一段时间，并且已经有很多在线资源可供使用，包括论文本身和Wikipedia。不过，我们将在这里介绍一些基础知识。
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之间。
请注意，对网络范围的参数的选择K并非是任意的，而是根据网络中观察到的平均用户流失以及网络将重新发布信息的频率来确定。计算系统参数（如K）可最大程度地提高网络保持连接状态且无数据丢失的可能性，同时保持所需的查询等待时间，并假设（平均用户流失）观测值保持恒定。这些系统和网络参数决定着Kademlia的两个主要组成部分的决策：路由表跟踪网络中所有这些链接，查找算法确定如何遍历这些链接以存储和检索数据。
Kademlia和Undialable Peers
如上所述，Kademlia的主要特性是所有对等方都可以从最小到最大内联。此属性很有用，因为它意味着当对等体0沿线寻找对等体55时，它可以知道它正在逐渐靠近。但是，这要求线路上的每个人都可以相互通信，否则对等体33可能会通过告诉对等体0他们想要的内容在无法与之通信的节点上，从而将对等体0发送到死角。这可能导致网络变慢，更重要的是，网络碎片化，某些对等方而不是其他对等方可以访问数据。
尽管无法互相通信的对等体听起来很奇怪，但NAT和防火墙是导致其他对等体无法访问的两个常见原因。例如，具有不对称网络，其中一组对等X，Y，Z可以相互连接并与A连接，但是A无法连接它们，这在现代Internet上非常普遍。同样，位于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添加到其路由表或向其发布查询之前，不仅要公开公共IP地址，而且还要发布它们。
两个IPFS DHT：公共和本地
尽管我们的许多用户都使用公共共享的DHT来发现和广告内容，但其中一些用户在隔离的网络（例如本地网络或隔离的VPN）中运行。对于这些用户而言，拥有所有非公共可拨号节点都是客户端的DHT是非常成问题的，因为没有节点是公共可拨号的。
为了使该用例更轻松，我们添加了第二个DHT，该DHT旨在包括不属于公共网络的节点，例如VPN，CJDNS，Yggdrasil等。现在，我们将其称为LAN DHT，而不是WAN DHT的公共网络。通过使用不同的DHT协议名称（即/ipfs/kad/1.0.0 WAN DHT和/ipfs/lan/kad/1.0.0 LAN DHT）来分离这两个DHT，以消除两个网络的任何意外合并。但是，如果用户未正确配置其网络，则所有非公共网络都存在合并的风险。
WAN DHT和LAN DHT之间的主要实现差异是对等点的接受标准，这些标准可以成为路由表或查询的一部分，而没有。WAN DHT的标准是“您看起来像一个公共地址”，LAN DHT的标准是“您看起来像一个非公共地址”。但是，虽然WAN DHT节点根据它们是否可公共拨打而从客户端切换到服务器模式，但LAN DHT节点始终是服务器（除非已设置“ dhtclient”选项）。
路由表
如前所述，Kademlia网络中的每个对等方都维护与网络中其他各个对等方的链接。其工作方式如下：
1. 当我们连接到同位体时，检查它是否符合添加到我们的路由表中的条件
○ 确保对等体是发布DHT协议ID的DHT服务器（在IPFS中/ipfs/kad/1.0.0为公用/ WAN DHT和/ipfs/lan/kad/1.0.0 LAN DHT）
○ 确保对等方具有与我们期望的范围相匹配的IP地址（例如，公共DHT的成员至少具有一个公共范围IP地址，而不是仅类似的地址192.168.X.Y）
2. 如果符合条件，则确定新对等方在Kademlia地址空间中与我们的距离，以弄清应该进入哪个“存储bucket”（即，对等方与我们和地址之间的距离在2 ^ 7到2 ^ 8之间）空间的大小为2 ^ 256，则对等方进入存储区256-8）
3. 尝试将peer置于bucket
○ 如果存储bucket未满（例如，其中的对等体少于20个），则添加对等体
○ 如果存储bucket已满，请确定是否有任何可“替换”的对等体（如下定义），然后删除其中一个对等体，然后将其替换为新的对等体。否则，请勿将对等方添加到存储bucket中
4. 如果我们曾经尝试查询路由表中的对等节点而失败，则驱逐它们
○ 注意：每次刷新后（请参阅下文），我们将遍历路由表，并尝试连接到尚未“最近”查询的对等方，以检查它们是否仍然在线以及对我们的路由表而言是否有效。如果没有，那么我们将其逐出。
此外，为了保持路由表的准确性和最新性，我们会定期刷新路由表。路由表刷新的频率是根据与存储bucket大小类似的一组指标来计算的（您可以增加刷新的频率，但是可能会降低多少）。对于IPFS，将下限频率选择为每10分钟一次。尽管这可能比严格要求的频率高，但是我们认为保护网络的健康非常重要，因为我们会更多地了解go-ipfs v0.5.0采用后的IPFS DHT网络动态。
路由表刷新的工作方式如下：
1. 遍历所有存储bucket，从存储bucket 0（与对等设备位于网络另一半的那个存储bucket）一直到拥有该存储bucket的最高存储bucket（由于实现而将其限制在存储bucket15内）关注）。对于每个存储bucket，在Kademlia空间中选择一个适合该存储bucket的随机地址（例如，在512和1024之间选择一个随机对等体时，即使该对等体可能不在网络中，我们也选择了678），并进行查找以查找K最接近该随机地址的对等体。这将确保我们将在每个存储bucket中填充尽可能多的对等端。
2. 我们也会在网络（即存储bucket255）中搜索自己，以防万一网络规模和分布使得前15个存储bucket不足以让我们了解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对等方
在路由表部分，我们提到如果发现可以在存储bucket中占据一席之地的新对等点，则将其“可替换”的对等点逐出。在v0.5.0中，如果对等体在概率性地希望被刷新利用的时间内没有对我们有用，则将其定义为“可替代”。该值是Log(1/K) * Log(1 - Alpha/K) * refreshPeriod，其中Alpha是可以同时查询的对等拨号号码。另外，我们将“有用”定义为在路由表中的任何其他对等方响应我们之前的2倍以内做出响应（这偏向于对等方速度较慢，过载，不可靠或对我们的网络连接不良）。随着我们收集有关网络动态的更多信息并调查相关威胁模型，可替换和有用对等方的定义可能会更改。
路由细节
虽然查找算法使我们可以将记录放入DHT中，但对于每种记录类型，这样做的方式略有不同：
● 提供者记录（对于具有Multihash的块H）
○ 投放：对K距离最近的对等点进行标准查找SHA256(H)
■ 将提供者记录放在K最接近的对等方（也可以自己存储）
■ 注意：目前，您仅允许自己放置提供商记录（即Alice无法宣传Bob的内容）
○ 获得：查找K最接近的对等实体X=SHA256(H)，而不只是询问查找中的每个对等实体“ 您知道谁是K最接近的对等实体X？” 还问“请把与X您有记录相对应的记录发送给我”。
■ 对等方添加它已了解的所有新提供程序，并继续进行直到查找终止。根据所使用的API，在收到一定数量的提供程序记录后，也可以强制中止查找。
● IPNS记录（对于公共密钥的多重哈希为的IPNS密钥H）
○ 投放：对K距离最近的对等点进行标准查找SHA256(/ipns/H)
■ 将IPNS记录放在K最接近的对等方（并自己存储）
○ 获得：查找K最接近的对等实体X=SHA256(/ipns/H)，而不只是询问查找中的每个对等实体“ 您知道谁是K最接近的对等实体X？” 还问“请把与X您有记录相对应的记录发送给我”。
■ 如果用户收到更新的记录（即，具有较高IPNS序列号的记录），它将更新其现有记录并继续直到查找终止。为了确保用户获得最新记录，这是必需的。回想一下IPNS记录是可变的，因此，我们需要确保将请求指向内容的最新版本。
■ go-ipfs中的默认设置将在接收到16条记录后提前中止，但是可以将其设置为go，直到查询终止
■ 查找完成后，如果K最接近的对等方X没有最新的IPNS记录，请向他们发送最新的记录。
● 对等记录（对于公共密钥的多重哈希为的对等体H）
○ 放置：这是隐式发生的-libp2p对等体彼此连接时，它们会自动交换对等体信息。作为DHT的一部分（无论是作为客户端还是作为服务器），都需要经常与K最接近的对等方联系，因此，它们最终会以您的对等方记录结尾。
○ 获得：查找K最接近的对等实体X=SHA256(H)，而不只是询问查找中的每个对等实体“ 您知道谁是K最接近的对等实体X？” 还问“请给我您的peer记录，H如果有的话”
■ 我们一H了解到有关ID的地址，便会尝试连接到具有ID的对等方。如果我们最终连接到对等点，则查找可能会提前终止。
测试与结果
作为go-ipfs v0.5.0版本的一部分，DHT进行了许多更改。尽管许多更改在直观上将是非常有用的，但我们需要更充分的证据来证明完整的更改将导致稳定且高效的网络。为此，我们利用了Testground，这是一种新的分布式测试基础结构（请在Testground博客文章中查看其启动说明）。
在整个开发过程中，我们运行了许多Testground测试，以了解我们的更改如何改善了网络。下面是对1000个对等网络的性能的比较，该网络中所有对等点之间的延迟大约为100-120ms，该网络运行go-ipfs v0.4.23中的DHT和go-ipfs v0.5.0中的DHT。注意：v0.4.23 DHT进行了一些小的修改，以使测试变得更容易，例如删除硬编码的查找超时，因此我们可以看到查询实际上应该运行多长时间。
从图中可以看出，最剧烈的变化是第95个百分位数的查找时间以及花费更多时间进行查找且无法尽早终止的操作。这意味着实际上需要通过网络完成搜索的IPFS Provide和IPNS Put有了很大的提升（Provide平均提高了24倍，而95％的提高了33倍）。其次是IPNS Get，它需要查找许多记录，然后是Find Peer，它正在查找一个非常具体的记录，最后，仅查找IPFS Provider记录的时间平均缩短了2.2倍，而在第95处平均缩短了6.4倍。百分位数。
写在末尾
嘘！如果你通过这篇博文（或者只是浏览了大部分）！在您重回激动人心的生活之前，请让我再简单介绍一下IPFS v0.5.0和即将发布的版本：
ipfsv0.5.0包含了很多DHT的更改和改进。需要注意的是，新节点当前与旧的go ipfs v0.4.23和更早的节点参与相同的DHT。虽然v0.5.0的DHT代码比以前的版本有了很大的改进，但是在一个大的网络中一个节点只能起到很大的作用。这意味着，当您运行v0.5.0时，性能应该会有所提高，但随着更多网络升级到v0.5.0及更高版本，我们将继续看到查找时间的改进。所以告诉你的朋友是时候升级了！
还有更多令人兴奋的改进即将到来，所以如果您有兴趣参与或跟踪我们的改进，请关注我们在GitHub上的存储库，并与我们在IRC上聊天。
欢迎来到Filecoin社区亮点系列的第六期~该系列的主题是用户和开发人员在Filecoin网络上构建基本工具和服务。我们希望这篇文章以及本系列的其他文章能激发您的兴趣，并为分布式Web构建世界一流的工具。
看看Zondax联合创始人 Juan Leni的最新文章，该文章正在为Filecoin构建密码库，硬件钱包集成，分类账应用程序和GPU加速软件。
