作者本文是对victoriametrics Go Maps Explained: How Key-Value Pairs Are Actually Stored的整理与翻译发布日期2024 年 8 月 16 日阅读时间17 分钟分类Go VictoriaMetrics开源技术如果你刚开始接触 Go可能会觉得 Go 中的 Map 用起来有些令人困惑。即使已经积累了更多 Go 开发经验想真正搞清楚 Map 底层究竟是怎么工作的也并不是一件容易的事情。比如下面这个例子。你有没有在创建 Map 时设置过一个hint然后想过为什么这里叫作“hint提示”而不像 Slice 那样直接叫 length 或 capacity 之类更加明确的东西// hint 10m:make(map[string]int,10)或者你可能已经注意到使用for-range遍历一个 Map 时得到的顺序并不等于键值对插入 Map 的顺序。而且更加奇怪的是即使遍历的是同一个 Map在不同时间执行遍历时得到的顺序也可能发生变化。但很奇怪的是如果你恰好在同一时间遍历它顺序通常又会保持一致。这是一个很长的故事。所以系好安全带我们开始吧。在继续之前先说明一下本文中的内容基于Go 1.23。如果 Go 后续发生了变化导致本文内容已经过时欢迎通过 Xfunc25 联系我。Go 中的 Map快速入门先来聊聊 Go 中的 Map。Map 是 Go 内置的一种类型用于存储键值对。数组中的键实际上只能是不断递增的索引例如0 1 2 3 ...而 Map 则不同。Map 的 Key 可以是任意可比较comparable类型。因此它拥有大得多的灵活性。m:make(map[string]int)m[a]1m[b]2m// map[a:1 b:2]Map[“a”: 1, “b”: 2]在上面的例子中我们使用make()创建了一个空 Map。其中Key 类型是stringValue 类型是int当然与其手动一个一个地向 Map 中加入 Key你还可以通过 Map Literal也就是 Map 字面量节省一些时间。这样就可以在创建 Map 时一次性把所有键值对都写进去m:map[string]int{a:1,b:2,}你只需要在创建 Map 时在花括号中列出所有 Key 以及对应的 Value。就这么简单。如果之后发现某个键值对已经不需要了Go 也提供了一个非常方便的delete函数。顾名思义它可以删除你不想要的 Keydelete(m,a)Map 的零值是nil从某些角度来说nilMap 和空 Map 很相似。例如你可以尝试在nilMap 中查找一个 Key。Go 不会因此报错也不会导致程序崩溃。如果查询一个并不存在的 KeyGo 会直接返回这个 Map 的 Value 类型对应的零值varmmap[string]intprintln(m[a])// 0m[a]1// panic: assignment to entry in nil map不过需要注意不能向nilMap 中添加新的键值对。实际上Go 处理 Map 的方式与处理 Slice 有些类似。Map 和 Slice 的默认值都是nil。而且当它们处于nil状态时只要执行的是某些“无害”的操作Go 并不会直接 Panic。例如你完全可以遍历一个nilSlice不会发生任何问题。那么如果尝试遍历一个nilMap会发生什么varmmap[string]intfork,v:rangem{println(k,v)}什么都不会发生。没有错误也不会出现什么意外。它只会安静地什么都不做。Go 的设计理念之一就是尽量让任何类型的默认值都是有意义、可使用的而不是让它轻易把你的程序搞崩。只有当你做了真正不合法的事情时Go 才会报错。例如尝试向一个nilMap 中添加新的键值对访问一个 Slice 中越界的索引除此之外还有几件关于 Go Map 的事情值得了解使用for-range遍历 Map 时Key 不会按照任何特定顺序返回。Map 不是线程安全的。如果同时对同一个 Map 进行读取或者使用for-range遍历和写入Go Runtime 会触发 Fatal Error。可以通过简单的ok检查判断某个 Key 是否存在_,ok:m[key]Map 的 Key 类型必须是comparable也就是可比较类型。接下来重点看看最后这一点。前面提到Map 的 Key 可以是任意可比较类型。但这里其实还有一些细节。“那么究竟什么是可比较类型什么又不是”其实很简单如果两个相同类型的值能够使用运算符进行比较那么这个类型就是可比较类型。例如funcmain(){varsmap[int]stringifss{println(comparable)}}// compile error: invalid operation: s s (map can only be compared to nil)可以看到上面的代码甚至无法通过编译。编译器会报错invalid operation: s s (map can only be compared to nil)同样的规则也适用于其他不可比较类型例如SliceFunction包含 Slice 的 Struct包含 Map 的 Struct等等因此如果你想把这些类型作为 Map 的 Key那么是不行的。例如funcmain(){varsmap[[]int]string}// compile error: invalid map key type []intcompilerIncomparableMapKey不过这里还有一个小秘密Interface 既可能是可比较的也可能是不可比较的。这是什么意思你完全可以定义一个使用空接口作为 Key 的 Map而不会产生任何编译错误。但是要小心这样做很容易在运行时遇到错误。funcmain(){m:map[interface{}]int{1:1,a:2,}m[[]int{1,2,3}]3m[func(){}]4}// panic: runtime error: hash of unhashable type []int// panic: runtime error: hash of unhashable type func()在你真正尝试把一个不可比较类型作为 Map Key 写进去之前一切看起来都没有问题。到了这一步就会出现运行时错误。而运行时错误通常比编译期错误更加棘手。因此除非确实有充分理由并且能够通过约束防止错误使用否则一般最好避免直接使用interface{}作为 Map 的 Key。不过刚才的错误消息hash of unhashable type []int可能有些令人费解。这里为什么突然出现了hash这正好给了我们一个机会继续深入看看 Go 在底层到底是如何处理 Map 的。Map 的内部结构在解释 Map 这样的内部实现时很容易陷入 Go 源代码中的各种细枝末节。不过本文会尽量保持轻松和简单让刚接触 Go 的人也能够跟得上。在 Go 代码中你看到的 Map 仿佛就是一个完整的数据结构。但实际上它只是一个抽象层把底层复杂的数据组织方式隐藏了起来。真正的 Go Map 是由许多更小的单元组成的。这些单元叫作Bucket。在 Go 源代码中可以看到类似这样的结构typehmapstruct{...buckets unsafe.Pointer...}从上面的 Go 源码可以看到Map 中存在一个指针它指向 Bucket 数组。这也是为什么当你把一个 Map 赋值给另一个变量或者把 Map 传给一个函数时新变量和函数参数都能够操作同一份 Map 数据。例如funcchangeMap(m2map[string]int){m2[hello]2}funcmain(){m1:map[string]int{hello:1}changeMap(m1)println(m1[hello])// 2}不过不要因此产生误解。Map 底层虽然可以看作包含一个指向hmap的指针但 Map 并不是什么所谓的“引用类型”也不是像 C# 的ref参数那样进行引用传递。如果直接修改整个m2调用者中的原始 Mapm1并不会跟着变化。例如funcchangeMap(m2map[string]int){m2map[string]int{hello:2}}funcmain(){m1:map[string]int{hello:1}changeMap(m1)println(m1[hello])// 1}在 Go 中所有东西都是按值传递的。实际发生的事情稍微有些不同。当我们把m1传给changeMap函数时Go 会复制 Map 内部所包含的那个指向hmap的指针。因此main()中的m1changeMap()中的m2从变量本身来看是两个独立的值。但这两个值内部的指针都指向同一个hmap。Map 是按值传递的如果想进一步了解这个话题可以阅读 Dave Cheney 的一篇非常好的文章There is no pass-by-reference in Go每一个 Bucket 最多只能容纳8 个键值对。如下图所示Map 的 Bucket上面这个 Map 中有2 个 Bucketlen(map)为 6那么当你向 Map 中加入一个键值对时Go 并不是随机把它扔进某个位置也不是按照顺序依次插入。相反Go 会根据 Key 的 Hash 值决定应该把这组键值对放入哪个 Bucket。这个 Hash 值由下面的操作得到hash(key, seed)下面看看最简单的赋值场景。假设我们有一个空 Map然后向里面加入hello: 1向空 Map 中添加一个键值对首先Go 会计算hello的 Hash得到一个数字。然后用这个数字对 Bucket 数量取模。由于当前只有一个 Bucket因此无论任何数字对 1 取模结果都只能是0所以这个键值对会直接进入bucket 0当再添加一个键值对时也会执行同样的过程。Go 会尝试把它放进 Bucket 0。如果第一个 Slot 已经被占用或者其中存储的是不同的 Key就继续检查这个 Bucket 中的下一个 Slot。再来看一下刚才提到的hash(key, seed)如果你使用for-range遍历两个拥有完全相同 Key 的 Map可能会注意到它们返回 Key 的顺序可能不一样。funcmain(){a:map[string]int{a:1,b:2,c:3,d:4,e:5,f:6}b:map[string]int{a:1,b:2,c:3,d:4,e:5,f:6}fori:rangea{print(i, )}println()fori:rangeb{print(i, )}}// Output:// a b c d e f// c d e f a b这是怎么回事Mapa中的 Keya和 Mapb中的 Keya使用的 Hash 算法难道不是一样的吗确实。Go Map 针对相同 Key 类型使用的 Hash 函数是一致的。但是Hash 函数使用的seed对每个 Map 实例来说都不同。也就是说每次创建一个新的 Map 时Go 都会专门为这个 Map 生成一个随机 Seed。因此在上面的例子中a和b的 Key 都是string类型所以它们使用同一个 Hash 函数。但是两个 Map 各自拥有不同的 Seed。“等等一个 Bucket 只有 8 个 Slot”“如果 Bucket 满了怎么办”“它会像 Slice 一样扩容吗”某种程度上是的。当 Bucket 开始变满或者接近“满”的状态时——具体什么叫“满”取决于算法的定义——Map 会触发扩容。扩容过程中主 Bucket 的数量可能会直接翻倍。不过接下来会变得更有意思。刚才我特意使用了主 Bucketmain bucket这个说法。因为接下来要引入另一个概念Overflow Bucket也就是溢出 Bucket。当 Hash 冲突比较严重时就会使用 Overflow Bucket。例如假设当前 Map 有 4 个 Bucket。但是由于大量 Hash 冲突其中一个 Bucket 已经塞满了 8 个键值对。而剩下的另外 3 个 Bucket 仍然完全是空的。Bucket 0 出现严重 Hash 冲突现在因为需要再加入一条数据而不幸的是这条数据仍然应该落入第一个已经装满的 Bucket。难道仅仅为了这一条记录就真的需要把整个 Map 从4 个 Bucket扩展成8 个 Bucket吗当然没有必要。那样实在太浪费了。Go 会通过一种更加高效的方式处理这种情况创建 Overflow Bucket。这个 Overflow Bucket 会与原来的第一个 Bucket 链接起来。新的键值对会被存进 Overflow Bucket而不是直接触发整个 Map 完整扩容。Map 的 Overflow BucketGo 中的 Map 会在满足下面两个条件之一时发生增长Overflow Bucket 太多。Map 过载也就是 Load Factor 太高。由于存在两个不同条件因此 Map 也有两种不同形式的增长当 Map 过载时Bucket 数量翻倍。当 Overflow Bucket 太多时Bucket 数量保持不变但重新分布其中的 Entry。如果 Overflow Bucket 太多那么相比单纯继续增加更多内存更好的办法是重新分布现有 Entry。目前 Go 使用的 Load Factor 阈值是6.5这意味着Go Map 的设计目标是让每个 Bucket 平均维持大约6.5 个 Entry。一个 Bucket 最多有 8 个 Slot。因此大约相当于80% 的容量使用率。当 Load Factor 超过这个阈值时就认为 Map 已经过载。这种情况下Map 会分配一个新的 Bucket 数组。新 Bucket 数组大小是当前数组的两倍。把原有元素重新 Hash 到这些新的 Bucket 中。为什么一个 Bucket 还没有完全装满时就已经需要考虑扩容原因还是性能。通常我们会认为Map 的读取和赋值操作复杂度都是O(1)对吧但实际上并没有这么简单。严重 Hash 冲突会导致 Map 操作变慢一个 Bucket 中被占用的 Slot 越多操作就越慢。当你想向 Map 中添加另一个键值对时并不只是简单判断“这个 Bucket 还有没有空间”还需要把新 Key 与 Bucket 中已有的 Key 逐个进行比较从而判断这是新增一个 Entry还是更新一个已经存在的 Entry如果存在 Overflow Bucket事情会变得更加糟糕。因为还需要继续检查 Overflow Bucket 中的每一个 Slot。同样的性能下降也会影响Map 查询Map 删除不过Go 团队当然已经替我们对这个比较过程进行了优化。还记得对Hello计算 Hash 后得到的那个值吗Go 并不会在计算完成之后直接把完整 Hash 丢掉。它会把Hello的tophash缓存到 Bucket 中。tophash使用一个uint8保存。当新的 Key 到来时会先快速比较新 Key 和已有 Key 的tophash。这个检查非常快。Map 的 tophash比较tophash之后如果两者相同只能说明两个 Key **“可能”**相同。然后Go 才会执行后面更加缓慢的真正 Key 比较检查两个 Key 是否真的完全一致。“为什么使用make(map, hint)创建一个 Map 时第二个参数不是精确大小而只是一个hint”看到这里你应该已经差不多可以回答这个问题了。make(map, hint)中的hint参数告诉 Go你预计这个 Map 初始大概要容纳多少个元素。这个 Hint 可以帮助减少Map 随着元素不断增加而发生扩容的次数。因为每一次扩容都涉及分配一个新的 Bucket 数组把已有元素复制或者迁移过去这并不是一个特别高效的过程。因此如果一开始就提供一个较大的初始容量提示可以避免其中一部分代价比较高的扩容操作。下面看看在真实情况下随着 Hint 增长Bucket 数量究竟如何变化Hint 范围Bucket 数量容量0 - 8189 - 1321614 - 2643227 - 5286453 - 10416128105 - 20832256209 - 41664512417 - 8321281024833 - 16642562048“为什么 Hint 为 14 时会得到 4 个 Bucket”“明明 2 个 Bucket 的总容量已经可以放下 14 个元素了。”这就是 Load Factor 开始发挥作用的地方。还记得前面提到的 Load Factor 阈值6.5吗它会直接影响 Map 应该在什么时候进行扩容。当 Hint 为 13 时我们拥有 2 个 Bucket因此 Load Factor 为13 / 2 6.5正好达到阈值但还没有超过阈值。因此当 Hint 增加到 14 时Load Factor 就会超过 6.5。于是必须扩容。Hint 为 26 时也是同样情况。拥有 4 个 Bucket 时26 / 4 6.5同样刚好达到阈值。当继续超过 26 后Map 就需要增长以便继续高效地容纳更多元素。基本上从第二个范围开始可以看到与前一个范围相比Hint 范围翻倍Bucket 数量翻倍总容量也翻倍Map 扩容时的 Evacuation前面提到过Evacuation 并不总意味着 Bucket 数量会翻倍。如果只是因为 Overflow Bucket 太多而触发 Evacuation那么新的 Bucket 数组大小仍然可能与旧数组完全相同。相比之下更有意思的情况是Bucket 数量翻倍。因此接下来主要讨论这种情况。Map 的扩容机制可以回答两个经常出现的问题为什么不能获取 Map 中某个元素的地址为什么 Map 的for-range遍历顺序在不同时间并不保证一致例如funcmain(){a:map[string]int{a:1}ptr:a[a]}// compiler error: invalid operation: cannot// take address of a[a] (map index expression of type int)当 Map 扩容时会分配一个新的 Bucket 数组。新的 Bucket 数组大小是旧数组的两倍。这样一来旧 Bucket 中所有 Entry 原来的位置都会失效。它们必须移动到新 Bucket 中。因此它们的内存地址也会发生变化。Map 的 Evacuation问题在于假设一个 Map 中存在 1000 个键值对。如果每次扩容都一次性把这 1000 个 Key 全部移动过去这会是一个相当昂贵的操作。它甚至可能让当前 Goroutine 阻塞一段用户能够明显感觉到的时间。为了避免这个问题Go 使用Incremental Growth也就是渐进式扩容。Map 不会一次性重新 Hash 所有元素。而是每次只搬迁其中一部分。这样整个过程会被分散到多次操作中。程序能够继续平稳运行而不会突然出现明显的卡顿。不过这也会让整个过程变得更加复杂。因为在扩容过程中Go 仍然需要保证 Map 的完整性。与此同时还要支持读取写入删除遍历并且这时候旧 Bucket 和新 Bucket 会同时存在。“渐进式扩容到底什么时候发生”只有两种操作会真正触发渐进式扩容向 Map 中写入一个键值对。从 Map 中删除一个 Key。这两种操作中的任意一种都会触发 Evacuation。而且每次至少会把一个旧 Bucket 迁移到新的 Bucket 数组中。例如我们执行m[Hello]2如果 Map 当前正在扩容那么首先会对包含HelloKey 的旧 Bucket执行 Evacuation。这个旧 Bucket 中的每一个元素都会被移动到两个新 Bucket 中的其中一个。即使 Map 拥有的不只是 2 个 Bucket过程也是一样的。KeyHello可能移动到两个新 Bucket 中的任意一个例如假设正在从4 个 Bucket扩容到8 个 Bucket那么旧的bucket 1中的元素只可能移动到新的bucket 1或者bucket 5我们怎么知道这里只需要做一点和位运算有关的数学推导。假设hash % 4 1那么hash % 8的结果只可能是1或者5因为对于满足H % 4 1的旧 Bucket 来说H最低两位一定是01当新的 Bucket 数量变成 8 时我们需要观察最低三位如果从右往左数第三位是 0那么最低三位是001也就是说H % 8 1如果从右往左数第三位是 1那么最低三位是010也就是说H % 8 5旧 Bucket 如何执行 Evacuation如果旧 Bucket 还挂着 Overflow Bucket那么 Map 同样需要把 Overflow Bucket 中的元素一起移动到新的 Bucket 中。当旧 Bucket 中的所有元素全部完成搬迁后Map 会通过tophash字段把这个旧 Bucket 标记为已经 Evacuated。今天关于 Go Map 的讨论就到这里。实际上Go Map 的内部实现比本文介绍的内容还要复杂。其中还有大量细小的实现细节没有在这里展开。例如tophash不仅仅用于 Key 比较它还会参与 Evacuation。保持联系你好我是 Phuong Le一名 VictoriaMetrics 软件工程师。上面的写作方式主要强调清晰和简单。我希望通过一种容易理解的方式解释这些概念。因此其中的一些表达方式并不一定始终与严格的学术精确性完全一致。如果你发现其中有任何内容已经过时或者有任何问题欢迎联系我。可以通过 X 给我发私信Xfunc25相关文章VictoriaMetrics 的 Golang 系列文章Go I/OReader、Writer 与流动的数据Go 中的 Slice要么增长要么回家Go Sync Mutex正常模式与饥饿模式Go Defer从基础知识到各种陷阱Go 数组的工作原理以及 For-Range 中那些棘手的问题深入 Go 的 Unique Package简单理解字符串驻留Vendoring也就是go mod vendor它到底是什么我们是谁如果你希望监控自己的服务、跟踪指标并了解整个系统的实际运行表现可以了解一下 VictoriaMetrics。它是一种高性能开源节约成本的基础设施监控方案。而我们也是一群 Gopher。我们热衷于研究 Go对 Go 进行实验分享 Go 以及整个 Go 生态系统中的知识标签gogolang