哈希数组映射到救援的尝试(HAMT)

构建分布式系统和Web3并非易事。让我给你讲一个简短的故事，这样你就能领会这一说法了。在Beyond BitSwap项目的范围内(我在这篇文章中简要介绍了这个项目)，我们收集了一堆想法，并设计了一套建议来(潜在地)提高Bitswap的性能。本周，我直接开始实施(我认为)最容易处理的提案。我是从这篇论文中得到这个想法的，而且它看起来相当直截了当。

其想法如下：为了加快从Bitexchange节点发现内容的速度，我们将检查所有邻居对内容的请求，并将它们存储在一个表(我们亲切地称之为对等块注册表)中，以便下次我们需要查找特定的CID时，不是盲目地要求网络中的每个人都发出大量请求，而是首先询问那些以前对该文件表现出兴趣的对等点，因为他们现在可能已经拥有了内容。有点过于简单化了，这就是解决方案背后的基本原理。

不过，在本出版物中，我不会讨论总体协议的设计，而是将重点放在这个我们称为对等块注册表的“简单”表的设计上。我们在团队里讨论解决方案，我天真地说，“来吧！为对等块注册表构建数据结构很简单，我们使用Golang映射结构，现在就可以开始了。“。然后，我的一位更聪明的同事提醒我注意一些我忽略的问题，“您知道单个节点收到多少个内容请求吗？扩展该数据结构并非易事。做这个实验。“。我就是这么做的。这些是在10个IPFS节点网络上看到的WAND消息数量的结果，该网络具有5个种子和5个水蛭，交换了1000个1.7MB的文件。

仅对于这些文件中的一个，节点就可以看到多达1700个对内容的请求，这些请求需要有效地存储在其注册表中，以便在将来的查找中使用此信息。这是针对具有9个连接的节点，其中只有一半的连接请求内容。的确，比我预期的更具挑战性。

与比你聪明的人一起工作最酷的一点是，他们会帮助你提高，在这个过程中你总是会学到一些新的东西。我的这位更明智的同事鼓励我做这项测试，他还告诉我：“考虑使用更高效的数据结构，如Hash Array映射的尝试，它们将使您的问题易于处理”，并且(再次)我做到了，所以本出版物是我向您介绍它们的卑微尝试，这样您也可以将它们放在您的工具带中。

HAMT是哈希表和Trie的组合。它们是由菲尔·巴格威尔(Phil Bagwell)在这篇文章中介绍的。HAMT是一种内存高效的数据结构，其中“插入、搜索和删除时间很小且恒定，与键集大小无关，操作数为O(1)。可以保证插入、搜索和移除操作的最坏情况时间很短，并且未命中的成本低于成功的搜索“。所以您可以明白为什么HAMT是解决我手头问题的完美人选。

在介绍HAMT之前，我强烈建议您修改哈希表和尝试的概念，因为如果您不熟悉这些概念，HAMT可能很难理解。

Trie可以看作是“一棵有前缀的树”。它由根据使用的前缀通向子项的一个节点和多个弧线表示。下图显示了一个前缀大小为2的Trie示例，它存储值“00000000”、“11111110”和“11111111”。您可以看到，根据前缀和后续位，存储值的级别是确定的。

为了将此trie转换为HAMT，我们使用一个数组来表示树，因此我们有一个长度等于树中节点数量的数组(在本例中为四个)。因此，不需要查找相关的映射，我们可以使用前缀作为数组索引：

不幸的是，这种方法占用了很大的内存，因此Bagwell在他的最新论文中建议使用一个整数位图来表示Trie中每个可能的弧的存在，以及一个包含指向适当的子项或终端节点的指针的关联表。因此，第一片叶子的贴图：

将用掩码“1001”表示，这表明只有Trie的第一个和最后一个弧是非空的。这将导致如下所示的结果：

简而言之，位图中的1位表示有效圆弧，而0位表示空圆弧。表中的指针按排序顺序保存，并与位图中每一位的顺序相对应。例如，在我们的例子中，00是数组的第0个元素并存储一个值，而11是第一个元素并存储指向下一层的指针，因此Trie的第一级的掩码是1001，如上所述(前缀00和11处的值)。下一级别的掩码为0001，这意味着在值11中只有一个值，依此类推。

在此数据结构中，识别是否已设置密钥变得非常有效。在我们手边的示例中，通过检查根的掩码，我们可以查看是否有以前缀10和01开头的键。

前面几节介绍了具有2位前缀和4位位图的HAMT的简化版本。Bagwell的论文中提出的结构使用32位位图和5位前缀。一旦理解了这个简单的示例，这就是我们将如何在完整的32位HAMT上执行操作。

搜索：计算关键字的完整32位散列，取最高有效位并将其用作整数以索引到根散列表中。可能会遇到三种情况之一。首先，该条目为空，表示该键不在散列树中。其次，该条目是键/值对，并且键或者与指示成功的所需键匹配，或者与指示失败的所需键匹配。第三，该条目具有32位映射子散列表和指向非空子散列表项的有序列表的子trie指针。获取散列的接下来的5位，并将它们用作一个整数来索引到位图中。如果此位为0，则哈希表条目为空，表示失败，否则为1，因此对下面的1位进行计数，并将结果用作非空条目列表的索引。通过每次再获取散列的5位来重复该过程，直到找到终止键/值对或搜索失败。

插入：向散列树添加新关键字所需的初始步骤与搜索相同。遵循搜索算法，直到遇到两种故障模式之一。要么在哈希表中发现空位置，要么找到子哈希表。在这种情况下，如果这在根哈希表中，则只需用新的键/值对替换空位置。然而，如果在子哈希表中，则必须向位图添加新的位，并且子哈希表的大小增加1。必须分配新的子哈希表，将现有的子表复制到其中，以子哈希排序的顺序添加新的键/值条目，并且释放旧的哈希表。否则密钥将与现有密钥冲突。在这种情况下，必须用子散列表替换现有密钥，并且计算现有密钥的下一个5位散列。如果仍然存在冲突，则重复此过程，直到没有发生冲突。然后将现有密钥插入到新子哈希表中，并添加新密钥。

我希望上面的解释已经说服了您，也让我相信HAMT是一种比天真的哈希表更好的方式来表示我们在Web3世界中必须使用的那种规模的键值数据结构。

此时，我已经选择使用HAMT进行我的协议的初始实现，使用CID作为关键字，使用请求该特定CID的最后一个对等点作为值。因此，如果对等点没有收到任何CID请求，通过HAMT位图，我们可以快速识别。当然，这并不是故事的全部，HAMT是一个内存高效的键值存储，但是为了使我的协议在计算上也是高效的，可能需要实现其他方案，比如使用累加器(但在未来的出版物中将详细介绍这一点)。

为了开始获得一些灵感并加快我的开发，我在网上搜索了Golang中现有的HAMT实现，我只能找到这个简单的(显然没有维护)和另一个，仍然没有维护，但要完整得多。还有Filecoin中使用的IPLD HAMT的参考实现，我需要更深入地研究一下代码，看看它是否可以用来解决我手头的问题。

我还可以找到其他编程语言的实现，比如Clojure中的HAMT实现，这也是一个很好的灵感来源(快速搜索HAMT和Clojure，看看我的意思)。

各位，今天就到这里吧！除了了解更多关于HAMT的知识之外，我希望您从这本出版物中学到的主要知识是：在处理web3.0时要注意实现幼稚的方法，因为您可能会陷入性能陷阱(不要犯与我相同的错误)。在这个规模上，我们需要应用更先进的结构，有效地进行扩展。在这个项目的整个开发过程中，我不断发现一些很酷的技术，比如这些HAMT或密码累加器，它们可以帮助您处理Web3问题。我希望在接下来的几周里找到时间和灵感来分享更多关于这方面的信息。同时，祝您玩得开心！

既然这已经成为一种传统，如果你想成为这个激动人心的领域的活跃成员，请点击这个链接！