原文链接:https://www.dolthub.com/blog/2023-03-28-swiss-map/
这篇文章介绍SwissMap
,这是一个基于 SwissTable 的新 Golang HashTable
,比 Golang 内置的Map更快,更节约内存。我们将介绍这个新软件包的动机、设计和实现。并为您提供一些尝试它的理由。
在 DoltHub,我们热爱 Golang,并已将其用于构建 DoltDB,这是第一个也是唯一一个可以进行分支、差异和合并的 SQL 数据库。通过构建 Dolt 的经验,我们在语言上获得了一些专业知识。我们发现了很多我们喜欢的功能,也遇到了一些比较尖锐的问题。Go 语言的一个重要的特点是简洁性。它暴露最小的接口,将复杂性藏在Runtime
中(简洁不等于简单)。Golang 内置的 map 是其的一个很好的例子:内置在runtime 中,使用专门的接口进行读写。对于大多数用例,map 表现出色,但其不透明的实现使其很难扩展。在没有替代方案的情况下,我们决定自行编写HashTable。
动机
HashTable在 Dolt的代码库中被广泛使用,但在处理数据持久性和检索的底层堆栈中尤为重要。Dolt 中负责数据持久性的抽象被称为 ChunkStore
。 ChunkStore
许多的实现,但它们共享一组普通的语义:使用 [20]byte 内容可寻址哈希来存储和获取名为“chunks”的可变长度字节缓冲区。Dolt 的表索引存储在Prolly Trees
中,这是一种由这些可变大小块组成的基于树的数据结构。Prolly 树中的较高节点通过它们的哈希引用子节点。为了反解这个哈希地址,ChunkStore
必须使用“块索引”将哈希地址映射到磁盘上的物理位置。相比之下,传统的 B 树索引使用固定大小的数据页,父节点直接通过它们在索引文件中的物理位置引用子节点。
Dolt 中的大型 Prolly Tree 索引可以达到 4 至 5 个层级。遍历每个级别需要使用块索引来解析父节点和子节点之间的引用。为了与传统的 B 树索引竞争,块索引必须具有非常低的延迟。这个块索引的原始设计是一组静态的、排序的数组。查询索引涉及对每个数组进行二进制搜索,直到找到所需的地址为止。这种设计的好处在于它的紧凑性。块地址本身是 20 个字节,并且伴随着一个 uint64 文件偏移和一个 uint32 块长度。这种查找信息比传统的 B-Tree 索引存储的 8 字节文件偏移明显更臃肿。将查找结果存储在静态数组中最大限度地减小了块索引的内存占用。其缺点是查询索引的渐近复杂度为 m log(n),其中 m 是数组的数量,n 是它们的平均大小。
在设计我们的新 ChunkStore 实现 Chunk Journal 时,我们决定用HashTable替换基于数组的块索引。基于HashTable的索引将支持常数时间的哈希地址查找,从而减少 ChunkStore 的延迟。这种折衷方案是HashTable使用更多内存。实际上,使用多少内存取决于您使用的HashTable类型。我们的第一个实现使用了 Golang 的内置HashTable map,其"最大负载因子"为 6.5/8。这意味着在最佳情况下,map 使用的内存比基于数组的块索引多 23%。然而,平均情况要糟糕得多。那么,如何在不超出内存预算的情况下实现常数时间的块查找呢?这就是 SwissMap 的作用。
SwissTable 设计
SwissMap 基于 Google 的开源 C++库 Abseil 中的"SwissTable"HashTable家族。这些HashTable被设计为 C++标准库中 std::unordered_map
的更快速、更小型的替代品。与 std::unordered_map
相比,它们具有更密集、更友好的缓存内存布局,并利用 SSE 指令加速键值查找。该设计被证明非常有效,目前已被其他语言采用。Rust 的 SwissTable 移植版 Hashbrown 已经被纳入 Rust 标准库,在 Rust 1.36 中推出。甚至在 Golang 社区内,正在进行采纳 SwissTable 设计作为运行时映射实现的努力。SwissTable 设计非常适用于我们的分块索引用例:速度快,并支持更高的最大负载因子 14/16。
内置地图和 SwissMap 之间的主要设计差异在于它们的哈希方案。内置地图使用了一种“开放哈希”方案,其中具有冲突哈希的键值对被收集到单个“桶”中。要在地图中查找一个值,首先基于键的哈希选择一个桶,然后遍历桶中的每个键值对,直到找到匹配的键。
![[Pasted image 20240807102716.png]]
内置地图中的关键优化是使用“额外散列位”,这允许在遍历存储桶的插槽时快速进行相等性检查。在直接将查询键与候选键进行比较之前,查找算法首先比较每个键的 8 位散列(与存储桶散列独立)以查看是否可能存在正匹配。这种快速预检具有 1/256 的误报率,并且极大加速了通过散列表存储桶进行搜索。要了解有关 Golang 内置地图的更多设计细节,请查看 Keith Randall 在 2016 年 GopherCon 大会上的演讲“地图实现内部”。
SwissTable 使用一种名为“closed-hashing”的不同散列方案。与将元素收集到桶中不同,散列表中的每个键-值对被分配其自己的“槽位”。此槽位的位置由探测算法决定,其起始点由键的哈希决定。最简单的例子是线性探测搜索,它从槽位 hash(key) mod size 开始,并在找到所需键或到达空槽位时停止。这种探测方法用于查找现有键和为新键找到插入位置。与内置的 Golang map 类似,SwissTable 使用“短哈希”来加速探测期间的相等性检查。但与内置的 map 不同,它的哈希元数据与键-值数据分开存储。
![[Pasted image 20240807095909.png]]
SwissTable 的分段内存布局是其性能的关键驱动因素。在表中探测序列只访问元数据数组,直到找到短哈希匹配为止。这种访问模式在探测过程中最大化了缓存局部性。一旦找到元数据匹配,相应的键几乎总是匹配的。拥有专用的元数据数组意味着我们可以使用 SSE 指令并行比较 16 个短哈希!使用 SSE 指令不仅更快,还是 SwissTable 支持最大负载因子 14/16 的原因。观察表明,“负面”探测(搜索表中不存在的键)仅在遇到空槽时终止。表中空槽越少,平均探测序列找到它们所需的时间就越长。为了保持HashTable的 O(1)访问时间,平均探测序列的长度必须受到一个小的恒定因子的限制。有效使用 SSE 指令允许我们将平均探测序列的长度除以 16。经验测量表明,即使在最大负载时,平均探测序列执行的 16 路比较也不到两次! 如果您对了解 SwissTable 设计(更多)感兴趣,请查看 Matt Kulukundis 在 2017 年 CppCon 大会上的演讲,“逐步设计一个快速、高效、友好缓存的HashTable”。
将 SwissTable 移植到 Golang
有了设计方案,就是该动手实施了。第一步是编写 find() 算法。正如马特·库卢昆迪斯在他的讲座中指出的那样,find() 是 SwissTable 中所有核心方法的基础:Get()、Has()、Put() 和 Delete() 的实现都从“查找”特定槽开始。您可以在此处阅读实际实现,但为简单起见,我们将查看伪代码版本。
|
|
搜索循环持续进行,直到达到两种退出条件之一。 对于调用 Get()、Has() 和 Delete() 的成功调用,当短哈希和键值都与查询键匹配时,会在第一个返回时终止。 对于 Put() 调用和未成功搜索的情况,会在找到空槽位时在第二个返回时终止。 在元数据数组中,空槽位由特殊的短哈希值编码。 matchEmpty 方法为此值执行 16 路 SSE 探测。
Golang 对 SSE 指令的支持以及对 SIMD 指令的支持都很有限。为了利用这些基本函数,SwissMap 使用优秀的 Avo 软件包生成具有相关 SSE 指令的汇编函数。您可以在这里找到代码生成方法。
块索引用例需要将哈希键映射到块查找数据的特定HashTable。但是,我们希望 SwissMap 是一个通用数据结构,可以在任何性能敏感的上下文中重复使用。使用泛型,我们可以定义一个HashTable,它和内置地图一样灵活
|
|
SwissMap 的哈希函数是 maphash,这是另一个 DoltHub 包,它使用 Golang 的运行时哈希程序,可以对任何可比较的数据类型进行哈希处理。在支持的平台上,运行时哈希程序将使用 AES 指令高效生成强哈希值。利用像 SSE 和 AES 这样的硬件优化使 SwissMap 能够将查找延迟最小化,甚至在处理更大的密钥集时胜过 Golang 的内置映射函数:
|
|
最后,让我们来看看 SwissMap 的内存消耗。我们构建 SwissMap 的最初动机是为了使我们的块索引在最小化额外内存消耗的同时获得常数时间查找性能。SwissMap 支持比内置地图更高的最大负载因子(87.5% 对比 81.25%),但仅凭这一点并不能讲述整个故事。使用 Golang 的 pprof 分析器,我们可以测量每个地图的实际负载因子,针对一系列键集大小。测量代码可以在这里找到。
![[Pasted image 20240807100333.png]]
在上面的图表中,我们可以看到瑞士地图(SwissMap)和内置地图之间内存消耗模式明显不同。为了比较,我们还包括了存储相同数据集的数组的内存消耗。内置地图的内存消耗遵循阶梯函数,因为它始终由两的幂次数个存储桶构建而成。这种情况的原因来自于经典的位运算优化模式。
任何HashTable查找(开放或闭合哈希)都必须基于查询键的哈希选择探测序列的起始位置。将哈希值映射到桶或插槽是通过余数除法完成的。事实证明,余数除法操作符%在 CPU 周期中是相当昂贵的,但如果除数是 2 的幂,则可以用最低 n 位的超快速位掩码替换%操作。因此,许多HashTable被限制在 2 的幂大小。通常这会产生可忽略的内存开销,但在分配包含数百万元素的HashTable时,影响会很大!如上图所示,Golang 的内置映射平均使用的内存比 SwissTable 多 63%!
为了避免余数除法的速度缓慢以及二次幂大小造成的内存膨胀,我们的 SwissMap 实现采用了一种不同的模映射,最初由 Daniel Lemire 提出。这个想法看似简单:
|
|
这种方法比经典的位掩码技术多出的操作很少,微基准测试只需四分之一纳秒。使用这种模数方法意味着我们受限于 uint32 的范围,但由于这个整数可以索引 16 个元素的存储桶,SwissMap 可以容纳高达 2 ^ 36 个元素。对于大多数用例来说,这已经足够了,并且可以节省内存,非常值得!
尝试一下 SwissMap
希望这是一次关于HashTable设计和高性能 Golang 的深入了解。SwissMap 已经证明是我们分块索引问题的有效解决方案,但我们希望它也能成为其他性能敏感用例的通用包。虽然它并不适合每种情况,但我们认为在关注大型HashTable的内存利用率时,它是有用的。如果您对 SwissMap 有任何反馈,请随时在存储库中创建一个问题。或者,如果您想直接与我们交流,请加入我们的 Discord!