Go内置映射中Swiss Tables的工作原理

# Go内置映射中的瑞士表如何工作 来源：https://victoriametrics.com/blog/go-swiss-table-map/index.html 我们已在《Go映射详解：键值对的实际存储方式》(https://victoriametrics.com/blog/go-map/)中探讨过Go映射及其旧版运行时实现。Go 1.24已用基于瑞士表的设计取代了该实现，因此现在是时候进行更新了。 您无需回头阅读旧文。在深入新的运行时内部原理之前，我们将先回顾映射的行为表现及相关概念。 *Go官方博客也有一篇精彩文章《使用瑞士表加速Go映射》(https://go.dev/blog/swisstable)。该文章更深入，且需要一定背景知识。我们采取不同方法：将循序渐进地、以可视化方式探讨相同实现，让您放松大脑的同时仍能理解Go的工作原理。* 若您已熟悉Go映射，可直接跳过第一部分。 ## Go映射快速回顾 ## \# (https://victoriametrics.com/blog/go-swiss-table-map/index.html#maps-in-go-a-quick-review) 映射存储键值对，每个键对应一个值。键类型和值类型可以不同： ``` m := map[string]int{ "dog": 1, "cat": 2, } ``` 除使用映射字面量外，我们通常用`make`创建空映射： ``` m := make(map[string]int, 100) ``` 可选的`100`告知Go我们期望映射存储约100个条目。Go在创建映射初始存储空间时将`100`作为提示（下文将解释）。这样映射在需要扩容（昂贵操作）前可容纳指定数量的条目。 先剧透一下：使用提示值`100`时，Go会创建128个槽位的初始存储空间。在下一次新条目导致扩容前，它可容纳112个条目。 刚揭露的剧透属于内部细节，因为Go不公开映射容量。`len(m)`报告已存储的条目数，而内置函数`cap`不接受映射。传给`make`的值仅是运行时的容量提示。 ``` println(len(m)) // 0 println(cap(m)) // 编译错误：cap的无效参数：m ``` 赋值、查找和删除在所有Go版本中使用相同操作： ``` m["dog"] = 1 value := m["dog"] value, ok := m["dog"] delete(m, "dog") ``` 首次查找`value := m["dog"]`直接返回值。若`"dog"`不存在，则返回`0`（`int`的零值）。 双值形式`value, ok := m["dog"]`还会返回`ok`以告知映射是否包含`"dog"`。这消除了缺失键与值为`0`的已存储键之间的歧义。 两种情况下`value`都返回`0`，但缺失键时`ok`为`false`，已存储键时为`true`。 ``` m := map[string]int{"dog": 0} println(m["dog"]) // 0：键存在 println(m["cat"]) // 0：键不存在 ``` 映射的零值为`nil`，但其行为略有不同，因为并非所有对nil映射的操作都会导致panic： ``` var m map[string]int value, ok := m["dog"] // 安全 println(len(m)) // 安全 delete(m, "dog") // 安全 for range m {} // 安全 m["dog"] = 1 // panic：对nil映射条目赋值 ``` 读取、删除、调用`len`及遍历nil映射是安全的。向nil映射写入条目会panic并报`assignment to entry in nil map`错误。 在深入映射内部之前，再看两条规则： - `range`循环不保证任何迭代顺序。 - 内置映射支持并发读取（只要没有goroutine写入）。并发读写或多个并发写入需要同步（如互斥锁）。 映射的键类型必须是可比较的，因为内部会哈希每个键以定位候选槽位，然后比较候选键是否相等（`==`）以确认找到请求的键： - 字符串、整数、指针和通道是有效的键类型。 - 若结构体所有字段可比较，则其可作为键。 - 若数组元素类型可比较，则数组可作为键。 - 切片、映射和函数不可。 ``` m := make(map[[2]string]int) // 有效：字符串数组可比较 m[[2]string{"dog", "cat"}] = 1 _ = make(map[[]string]int) // 编译错误：无效的映射键类型[]string ``` Go在编译期间拒绝无效的映射键类型，因此此程序无法构建或运行。 像`any`这样的接口类型是有效的映射键类型，但作为键赋值的每个具体值也必须可比较： ``` m := make(map[any]string) m["dog"] = "字符串键" // 有效 m[42] = "整数键" // 有效 m[[2]string{"dog", "cat"}] = "数组键" // 有效 m[[]string{"dog", "cat"}] = "切片键" // panic：运行时错误：不可哈希类型[]string的哈希值 ``` 以上代码通过编译并存储前3个条目。当运行时尝试哈希接口键中存储的`[]string`值时，最终赋值会导致panic。 热身结束。是时候深入映射内部原理了。 ## 运行时中的映射是什么？ ## \# (https://victoriametrics.com/blog/go-swiss-table-map/index.html#what-is-a-map-at-runtime) 让我们从映射的实际定义开始。 ``` m := make(map[string]int) ``` `make`初始化映射。`map[string]int`是语言级类型，表示映射使用字符串作为键、整数作为值。在该类型底层，`m`的运行时表示是指向`internal/runtime/maps.Map`的指针。 ``` type Map struct { used uint64 seed uintptr dirPtr unsafe.Pointer dirLen int ... } ``` 我们可以通过`println`轻松检查此指针： ``` m := make(map[string]int) m2 := m println(m) // 0x14000122000 println(m2) // 0x14000122000 ``` 将`m`复制到另一个映射变量会复制此指针，因此两个变量引用相同的运行时`Map`和条目。 复制映射变量使m和m2指向同一个运行时Map。 复制映射变量使m和m2指向同一个运行时Map。顶部的两个字段描述映射本身，而非其条目的存储。 ``` type Map struct { used uint64 seed uintptr ... } ``` `used`计算当前存储的条目数。由于Go确切知道从哪里查找条目数，当您编写`len(m)`时，Go会将此调用替换为访问`Map`的第一个字段并转换为`int`。这就是`len(m)`是O(1)而非扫描整个映射的原因。 `seed`是个有趣的字段，因为它导致不同映射以不同方式分配相同键。Go为每个映射用随机数初始化此字段。 当映射使用不同种子时，相同条目排列方式不同。 当映射使用不同种子时，相同条目排列方式不同。*上图仅为解释使用的简化表示。实际数据结构更复杂。* 每当Go需要定位映射存储中的键时，它会使用映射的种子哈希该键。由于每个映射有其自己的种子，在两个映射中哈希相同键可能产生不同的哈希值，因此存储位置不同。 ### 组 ### 映射根据其存储的键值对数量以不同方式布局存储空间。 在最小形式中，映射将最多8个键值对存储在称为**组**的结构中。这是Go瑞士表实现在一次中检查的最小存储单元。每个组包含： - 用于键值条目的8个槽位。 - 每个槽位一个控制字节（共8个）。Go将这8个字节存储在一个`uint64`中。 组将每个控制字节与其下方的键值槽位配对。 组将每个控制字节与其下方的键值槽位配对。组的具体类型取决于映射的键和值类型，因此编译器为每种映射类型生成一个内部匿名结构。概念上，`map[string]int`具有此布局： ``` type group struct { ctrl uint64 slots [8]struct { key Key elem Elem } } ``` Go还在测试一种新的组布局，使用分离的键和数组以提高键查找局部性并移除重复的对齐填充，如分离组布局(https://victoriametrics.com/blog/go-swiss-table-map/index.html#the-split-group-layout)节所述。 #### 控制字节与控制字 #### 让我们先看组的顶部行。这些是8个控制字节。它们共同形成8字节的**控制字**。 每个控制字节描述其正下方的槽位，因此控制字节0属于槽位0，控制字节1属于槽位1，此关系持续到槽位7。 但这些字节从何而来？ Go使用`Map`中的`seed`哈希键，然后将该哈希分为两部分。在大多数64位目标上，高57位称为**H1**，低7位称为**H2**。假设我们有另一个键`"cow"`，它在我们的插图中产生H2`42`： 64位哈希包含H1和7位H2。 64位哈希包含H1和7位H2。Go在32位目标（和Wasm）上使用32位哈希布局。本文后续将遵循64位布局。 H1是哈希的第一部分，Go用它选择映射存储中搜索的起始位置。小映射只有一个组，因此无需选择。在映射扩容前我们先搁置它。 H2是存储在活动槽位上方控制字节中的部分。 但控制字节有8位，而H2仅使用7位，因此还剩1位。Go使用这个最高位来指示槽位包含活动条目还是特殊状态。如果该位为`0`，低7位包含H2。如果该位为`1`，完整的控制字节表示`empty`或`deleted`： 控制字节表示活动、空或已删除的槽位。 控制字节表示活动、空或已删除的槽位。当其槽位包含键值条目时，最高位为`0`，低7位包含H2。H2`42`的二进制是`0101010`，因此`"cow"`的完整控制字节是`00101010`。 当最高位为`1`时，控制字节存储特殊值而非H2。空槽位使用`10000000`。已删除槽位使用`11111110`，也称为**墓碑标记**。两种状态都不包含活动键值条目，但查找可在`empty`处停止，而在`deleted`处必须继续。我们将在删除(https://victoriametrics.com/blog/go-swiss-table-map/index.html#deletion)节回到此区别。 使用此布局，控制字节让Go在读取槽位中完整键之前回答两个问题： - 此槽位包含活动条目，还是`empty`或`deleted`？ - 如果槽位包含活动条目，其键可能是我们要找的键吗？ 现在回到上面的原始组： 组将每个控制字节与其下方的键值槽位配对。 组将每个控制字节与其下方的键值槽位配对。接下来，为产生H2`42`的`"cow"`键赋值： 在存储`"cow"`之前，Go必须知道此赋值是更新现有键还是添加新键。它使用H2查找可能已存储该键的槽位，然后通过完整的键相等性检查确认每个候选项。 - `"cow"`的H2是`42`，这也是`"dog"`控制字节中存储的值。 - Go然后用相等性检查（`==`）比较完整键，但`"dog"`不等于`"cow"`。 - 没有其他控制字节包含H2`42`，因此Go知道此赋值添加了新键。 映射选择组中第一个空槽位（即槽位2），将`"cow"`和`4`写入该槽位，然后将H2`42`直接写入其上方的控制字节2： Cow使用第一个空槽位并在其上方存储H2 42。 Cow使用第一个空槽位并在其上方存储H2 42。插入使`used`从`3`增至`4`，这也使`len(m)`返回的值变为`4`。由于此小映射仍只需一个组，`dirPtr`直接指向该组且`dirLen`为`0`： 小映射直接指向其四条目组。 小映射直接指向其四条目组。在此小映射形式中，`dirPtr`直接指向存储映射键值条目的组。 现在组中有两个具有相同H2值`42`的控制字节：一个在`"dog"`上方，一个在`"cow"`上方。假设我们后来为`"cow"`赋另一个值： 在Go可以更新值之前，它必须找到现有键。它从哈希中取H2`42`并一次与组中所有8个控制字节比较： H2 42选择dog和cow作为候选键。 H2 42选择dog和cow作为候选键。Go不是逐个访问8个槽位并将H2与每个控制字节单独比较。在AMD64上，Go使用SIMD指令同时将H2`42`与那8个控制字节比较。 SIMD让CPU并行对多个字节值应用相同比较。在AMD64上，结果是一个压缩位图，每个槽位一位： 一次控制字比较产生候选位图。 一次控制字比较产生候选位图。在我们的组中，槽位0和2的位被设置，因为两个控制字节都包含`42`。其他位为空，这会屏蔽其他6个槽位而不读取其完整键。 其他架构通过对64位控制字进行算术和位运算产生相同的候选掩码，但它们每槽位使用一个字节而非将结果压缩为8位。 Go然后从槽位0和2读取完整键并与`"cow"`比较。`"dog"`未通过相等性检查（`==`），而`"cow"`匹配，因此赋值更新了为`"cow"`存储的值。 ### 表 ### 一个组只有8个槽位，因此如果我们持续添加超出其容量的键值对，Go需要另一个存储结构来存储它们。 Go将组数从1增加到2，并引入名为**表**的新结构来管理它们。它将现有组中的8个条目移入该表，在两个组间重新分配它们，然后存储新条目。 第九个条目将一个组变为包含两个组的表。 第九个条目将一个组变为包含两个组的表。表是完整的瑞士表，共同拥有一个或多个组： ``` type table struct { used uint16 capacity uint16 growthLeft uint16 ... groups groupsReference } ``` 我们的第一个表有`capacity = 16`、`used = 9`和2个组： - `groups`指向包含这些组的连续分配。 - `capacity`计算这些组中所有槽位。 - `used`计算此表中的活动条目数。 那么，为什么第一个组中的现有键值对需要重新分配，Go如何知道每对应该去哪个组？ 让我介绍H1，它正是用于此目的。Go使用H1计算每个键的起始组： ``` 起始组 = H1 % 组数 ``` 由于此表有2个组，`% 2`只需要H1的最低位。当我们从左到右写H1时，最低位是最右边的位，直接在原始哈希中与H2相邻。 例如，假设`"cow"`的H1以`0`结尾，而`"dog"`的H1以`1`结尾： H1最低位在两个组间重新分配条目。 H1最低位在两个组间重新分配条目。由于组数改变，Go为每个现有键再次运行此计算。一些键值对插入新组0，而另一些插入新组1。 此结果仅为起始组。例如，具有10个活动条目的16槽位表可能不均匀分布，使一个组满而另一个仍有空间...