4月底，我们发布了迄今为止最大的go-ipfs更新：IpFS 0.5（https:\/\/blog.ipfs.io\/2020-04-28-go-ipfs-0-5-0\/）。虽然有许多改进，但对IpFS 的分布式哈希表 (DHT) 的修改对于提高 IpFS 中数据查找的性能和稳定性尤为关键。关于我们如何达成最新的DHT变化的一些背景，请看《通往新DHT之路》（https:\/\/blog.ipfs.io\/2020-05-19-road-to-dht\/），或者自己在最新的go-ipfs版本中尝试一下。
在这篇文章中，我们将带您了解DHT 在 v0.5.0 中的详细情况，所以准备好迎接一篇真正深入了解 IpFS DHT 实现的来龙去脉吧。如果你想了解DHT是如何工作的，以及我们是如何让IpFS使用的实现更快、更有弹性，请继续阅读！
1
背景介绍: DHT对IpFS有什么作用?
DHT是一个分布式系统，用于将键映射到值。在IpFS中，DHT被用作内容路由系统的基本组件。它将用户正在寻找的内容（CID）映射到实际存储匹配内容的对等体。使用DHT映射的键值配对有3种类型：
1、提供者记录：这些将一个数据标识符（即多哈希）映射到一个对等体，该对等体已经宣传他们拥有并愿意为你提供该内容。
由IpFS用来寻找内容
由IpNS通过pubSub来寻找pubsub主题的其他成员
2、IpNS记录：这些记录将IpNS密钥（即公钥的哈希值）映射到IpNS记录（即指向\/ipfs\/bafyXYZ等路径的签名和版本指针）。
由IpNS使用
3、对等体记录：这些记录将对等体ID映射到一组多地址上，在这些地址上可以找到对等体。
当我们知道一个有内容的对等体，但不知道它的地址时，IpFS会使用
用于手动连接（如ipfs swarm connect \/p2p\/QmXYZ）
每一种记录类型都有稍微不同的语义，但它们都是通过相同的DHT协议更新和查找的，IpFS在Kademlia上的应用。
2
Kademlia概述
Kademlia算法已经有一段时间了，网上已经有一些很好的资源，包括论文本身和维基百科。不过我们在这里还是要介绍一些基础知识。
Kademlia的总体思路是在三个系统参数之上建立一个DHT：
地址空间：网络中所有对等体可以被唯一识别的方式（在IpFS中，这是从到2^256-1的所有数字）
一个度量标准，用于对地址空间中的对等体进行排序，因此可以直观地看到沿着一条线从最小到最大排序的所有对等体（在IpFS中，我们取SHA256(peerID)并将其解释为和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距离的单一链路，而是保留20条距离在65和128之间的链路。
请注意，像K这样的网络范围参数的选择不是任意的，而是根据观察到的网络中的平均颤动和网络重新发布信息的频率来决定的。系统参数(如K)的计算是为了最大限度地提高网络保持连接和数据不丢失的概率，同时保持查询所需的延迟，并假设观察到的(平均流失率)保持不变。这些系统和网络参数驱动着Kademlia的两个主要组件的决策，路由表跟踪网络中所有这些链接，查找算法决定如何穿越这些链接来存储和检索数据。
3
Kademlia和不可拒绝的peer
如上所述，Kademlia的一个主要属性是所有的对等体可以从最小到最大依次排列组合。这个属性是很有用的，因为这意味着当peer 0沿着线路走下去找到peer 55时，它可以知道自己正在逐渐接近。然而，这要求线路上的每个人都可以相互交谈，否则对等体33可能会通过告诉对等体0他们想要的内容在一个他们无法通信的节点上，从而将对等体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这样的地址)。
4
两个IpFS DHT：公用和本地
虽然我们的许多用户利用公开共享的DHT来发现和宣传内容，但他们中的一些人在隔离的网络中操作（例如，本地网络或隔离的VpN）。对于这些用户来说，拥有一个DHT，在这个DHT中，所有非公开拨号的节点都是客户端，这是非常有问题的，因为没有一个节点是公开拨号的。
为了让这种用例变得更容易，我们添加了第二个DHT，目的是为了包含不属于公共网络的节点，如VpN、CJDNS、Yggdrasil等。目前，我们将其称为LAN DHT，与公网相对的是WAN DHT。这两个DHT通过使用不同的DHT协议名（即\/ipfs\/kad\/1.0.0代表WAN DHT，而\/ipfs\/lan\/kad\/1.0.0代表LAN DHT）来分隔，以消除两个网络的意外合并。但是，如果用户没有正确配置网络，所有的非公共网络都有一定的合并风险。
WAN和LAN DHT在实现上的主要区别是对等体的接受标准--哪些是有资格成为路由表或查询的一部分，哪些不是。WAN DHT的标准是 \"你看起来像一个公共地址吗\"，LAN DHT的标准是 \"你看起来像一个非公共地址吗\"。但是，WAN DHT节点根据是否可公开拨号从客户机模式切换到服务器模式，而LAN DHT节点始终是服务器（除非设置了 \"dhtclient \"选项）。
5
路由表
如前所述，Kademlia网络中的每个对等体都维护着网络中其他各个对等体的链接。其工作方式如下：
当我们连接到一个对等体的时候，检查它是否有资格被添加到我们的路由表上
n 确保对等体是一个DHT服务器，它正在宣传DHT协议ID（在IpFS中，\/ipfs\/kad\/1.0.0为公共\/WAN DHT，\/ipfs\/lan\/kad\/1.0.0为LAN DHT）。
n 确保对等体的Ip地址与我们期望的范围相匹配（例如，公共DHT的成员至少有一个公共范围的Ip地址，而不是只有192.168.X.Y这样的地址）。
如果它符合条件，那么确定新的对等体在Kademlia地址空间中离我们的距离有多近，以确定它应该进入哪个 \"bucket\"（例如，如果对等体离我们的距离在2^7和2^8之间，而地址空间的大小为2^256，那么对等体将进入256-8 bucket）
尝试将peer放入bucket
n 如果bucket未满（即bucket中的对等体少于20个），那么就添加对等体的
n 如果bucket已满，那么确定是否有任何\"可替换 \"的对等体（定义如下），然后放弃其中一个，并用新的对等体替换。否则，不要将对等体添加到bucket中
如果我们曾经尝试查询路由表中的对等体，但失败了，那么就驱逐他们。
。注意：每次刷新后（见下图），我们会检查路由表，并尝试连接到我们\"最近 \"没有查询过的对等体，以检查它们是否仍然在线，并且是我们路由表的有效对等体。如果不是，那么我们就驱逐他们。
此外，为了保持路由表的准确性和最新性，我们会定期刷新路由表。路由表刷新的频率是由一组类似于bucket大小的指标计算出来的（你可以增加刷新的频率，但是有一个底限，可以低到什么程度）。对于IpFS，下限频率被选择为每10分钟一次。虽然这个频率可能比严格意义上的必要频率要高，但我们认为这对保护网络的健康很重要，因为我们在采用go-ipfs v0.5.0后对IpFS DHT网络动态有了更多了解。
路由表刷新的工作原理如下：
翻阅所有的bucket，从0号bucket(有对等体的bucket与我们在不同的网络上)开始，直到最高的bucket，里面有一个对等体(出于实施上的考虑，我们的上限是15号bucket)。对于每个bucket，在Kademlia空间中选择一个可能适合该bucket的随机地址（例如，在选择512和1024之间的随机对等体时，我们选择了678，即使该对等体很可能不存在于网络中），并进行查找以找到与该随机地址最近的K个对等体。这将确保我们会用尽可能多的对等体填满每个bucket。
我们也在网络中搜索自己（即255号bucket），以防网络大小和分布情况，前15个bucket不足以让我们了解离我们最近的K个对等体。
6
查找算法
查找算法回答了“ K最接近的对等点是X什么？”的问题。我们对Kademlia查找算法的实现如下所示：
从我们的路由表中把离X最近的K个对等体加载到查询队列中。
允许最多Alpha并发查询（go-ipfs中的Alpha是10，但是是一个实现参数，不是网络本身固有的），抓住离X最近的对等体，问他们“离X最近的K个对等体是谁？”
当一个对等体的查询完成后，将这些结果添加到查询队列中，然后将下一个最接近的对等体从队列中拉出来，并查询它们的情况。
每当离X最近的已知Beta对等体被成功查询（即没有拨号超时、错误等），查询就会终止。
注意：Beta是一个全网参数，旨在给网络提供一定的弹性，对于IpFS来说，它被设置为3
查询完成后，把我们还没有查询失败的K个最近的对等体（即我们已经收到他们的消息，或者他们还在我们的队列中），返回给他们
注意：由于一些ApI兼容性的原因，go-ipfs也确保我们确实向所有的顶级
在路由表部分，我们提到，如果我们发现一个新的对等体可以取代他们在bucket中置，我们就会驱逐\"可替换 \"的对等体。在v0.5.0中，我们将一个对等体定义为 \"可替换\"，如果它们在概率上预期在刷新中被利用的时间段内对我们不“有用”。这个值是Log(1\/K) * Log(1 - Alpha\/K) * refreshperiod，其中Alpha是可以同时查询到的已拨出的对等体数量。
此外，我们将 \"有用 \"定义为在路由表中任何其他对等体响应我们所需时间的2倍内响应（这对那些速度慢、超载、不可靠或与我们的网络连接不好的对等体有偏见）。随着我们收集更多关于网络动态的信息并研究相关的威胁模型，可替换和有用的对等体的定义很可能会改变。
7
路由细节
虽然查找算法让我们能够将记录放入和获取到DHT中，但每种记录类型的方式略有不同。
提供者记录（对于具有Multihash的块H）
（1）投放：对K距离最近的对等点进行标准查找SHA256(H)
将提供者记录放在K最接近的对等方（也可以自己存储）
注意：目前，您仅允许自己放置提供商记录（即Alice无法宣传Bob的内容）
（2）获得：查找K最接近的对等实体X=SHA256(H)，而不只是询问查找中的每个对等实体“您知道谁是K最接近的对等实体X？”还问“请把与X您有记录相对应的记录发送给我”。
对等方添加它已了解的所有新提供程序，并继续进行直到查找终止。根据所使用的ApI，在收到一定数量的提供程序记录后，也可以强制中止查找。
IpNS记录（对于公共密钥的多重哈希为的IpNS密钥H）
（1）投放：对K距离最近的对等点进行标准查找SHA256(\/ipns\/H)
将IpNS记录放在K最接近的对等方（并自己存储）
（2）获得：查找K最接近的对等实体X=SHA256(\/ipns\/H)，而不只是询问查找中的每个对等实体“ 您知道谁是K最接近的对等实体X？” 还问“请把与X您有记录相对应的记录发送给我”。
如果用户收到更新的记录（即，具有较高IpNS序列号的记录），它将更新其现有记录并继续直到查找终止。为了确保用户获得最新记录，这是必需的。回想一下IpNS记录是可变的，因此，我们需要确保将请求指向内容的最新版本。
go-ipfs中的默认设置将在接收到16条记录后提前中止，但是可以将其设置为go，直到查询终止
查找完成后，如果K最接近的对等方X没有最新的IpNS记录，请向他们发送最新的记录
对等记录（对于公共密钥的多重哈希为的对等体H）
（1）放置：这是隐式发生的-libp2p对等体彼此连接时，它们会自动交换对等体信息。作为DHT的一部分（无论是作为客户端还是作为服务器），都需要经常与K最接近的对等方联系，因此，它们最终会以您的对等方记录结尾。
（2）获得：查找K最接近的对等实体X=SHA256(H)，而不只是询问查找中的每个对等实体“ 您知道谁是K最接近的对等实体X？” 还问“请给我您的同伴记录，H如果有的话”
我们一H了解到有关ID的地址，便会尝试连接到具有ID的对等方。如果我们最终连接到对等点，则查找可能会提前终止。
8
测试和结果
作为go-ipfs v0.5.0 版本的一部分，DHT 有很多变化。虽然许多变化在直觉上是相当有用的，但我们需要更有力的证据来证明全套的变化将导致一个稳定和性能良好的网络。为此，我们利用了Testground，这是一个新的分布式测试基础设施（在Testground博客文章（https:\/\/blog.ipfs.io\/2020-05-06-launching-testground\/）中查看他们的启动说明）。
在整个开发过程中，我们运行了许多Testground测试，以了解我们的变化如何改善网络。下面是一个1000对等网络的性能比较，其中所有的对等体有大约100-120ms的延迟，从对方，这是运行的DHT去ipfs v0.4.23和DHT去ipfs v0.5.0。注意：v0.4.23的DHT有一些小的修改，以使测试更容易，如删除硬编码的查找超时，所以我们可以看到查询真正应该运行多长时间。
从图中可以看出，最剧烈的变化是对第95百分位数的查找时间和花费更多时间进行查找的操作，并且不能尽早终止。这意味着需要实际通过网络完成查找的 IpFS provide 和 IpNS put 得到了非常大的提升（对于 provide 平均提速 24 倍，对于 95 百分位数提速 33 倍）。紧随其后的是需要查找许多记录的 IpNS Get，然后是查找对等者（Find peer），它需要查找一个非常具体的记录，最后是查找一个 IpFS provider 记录的时间，平均加快了 2.2 倍，第 95 百分位数加快了 6.4 倍。
9
分开想
phew! 如果你已经读完了这篇博客文章(甚至只是浏览了大部分内容)，我赞扬你! 在送你回到你的精彩生活之前，我只想对IpFS v0.5.0和未来的版本做一些简单的评论。
IpFS v0.5.0包含了很多DHT的变化和改进。需要注意的是，目前新的节点与老的go-ipfs v0.4.23和更早的节点参加相同的DHT。虽然v0.5.0的DHT代码比以前的版本有了很大的改进，但在一个大的网络中，一个节点只能帮到这么多。这意味着今天当你运行v0.5.0时，你应该会看到性能的提高，但随着更多的网络升级到v0.5.0及以后，我们将继续看到查找时间的改善。所以告诉你的朋友们，是时候升级了!
还有更多令人激动的改进即将到来--如果你有兴趣做出贡献或只是跟踪我们的改进，请关注我们在 GitHub 上的仓库，并在 IRC 上与我们聊天。
10
了解更多
1、IpFS 0.5.0公告：https:\/\/blog.ipfs.io\/2020-04-28-go-ipfs-0-5-0\/
2、发布重点：https:\/\/www.youtube.com\/watch?v=G8FvB_0HlCE
3、TestGround:https:\/\/blog.ipfs.io\/2020-05-06-launching-testground\/
点对点科技简介
点对点科技深耘IpFS与Filecoin技术，坚持区块链技术改变未来的信念。点对点 IpFS 数据中心是目前国内技术领先，性价比高、保障优的投资标的。自建杭州数据中心，合作数据中心分布于上海、宁波、河北、香港、斯德哥尔摩（瑞典）等地。点对点数据中心具有优秀的硬件配置与目前国内优质的网络节点资源。点对点科技力求将IpFS爱好者升级为IpFS领军者与受益者，让IpFS颠覆传统互联网，共同开启 WEB 3.0时代。
想了解更多区块链知识吗？关注我吧！
网友：张求:也是血刃神帝他们起的名字，这是一种很神秘的力量。
