Announcement

👇Official Account👇

Welcome to join the group & private message

Article first/tail QR code

PFinalClub
Search K

Appearance

sync.Map 换引擎了：从双 Map 到哈希树，Go 1.26 底层实现全解析 ​

sync.Map 的公开 API 一个字都没变，但底层的引擎已经被彻底替换：Go 1.24 引入了实验性的哈希树（hash trie）实现，Go 1.26 移除了实验开关 GOEXPERIMENT=hashTrieMap，让哈希树成为标准库的正式实现。

问题在于，绝大多数开发者对 sync.Map 的理解仍然停留在 2017 年引入时的"双 map"心智模型——一个无锁的读 map，加一个由互斥锁保护的 dirty map。这个模型已经无法描述今天实际发布的 Go。本文从普通 map 如何定位一个键讲起，一步步推到哈希树，无需任何前置阅读。

一、旧实现：双 Map 的得与失 ​

先回顾旧实现的结构：

text
┌────────────────────────────────────────────┐
│                sync.Map (旧)                │
├────────────────────────────────────────────┤
│  read  atomic.Pointer[readOnly]            │
│    └─ m: map[any]*entry   ← 无锁读          │
│  dirty map[any]*entry     ← mu 互斥锁保护   │
│  misses int                ← 读 miss 计数   │
└────────────────────────────────────────────┘
        │ miss 次数 ≥ len(dirty) 时
        ▼
   dirty 晋升为新的 read，旧 read 被丢弃

设计思路是"读写分离"：

  • 读路径零锁：键在 read 里命中时，直接返回 entry.p，完全不碰锁。
  • 写路径走 dirty：新键写入 dirty，miss 累积到阈值后整表晋升。

这套设计为两类场景优化：键集合稳定、读多写少（如缓存、配置表）。但它有两个结构性缺陷：

  1. 写新键的开销是 O(1) 次复制 + 全量晋升。反复写不同的新键时，dirty 会不断重建，最坏情况退化为每次写都触发整表复制。
  2. 两个 map 意味着两份内存。read 和 dirty 中相同的键指向同一批 entry，但 map 本身的桶数组是双份的，键多时内存翻倍。

二、前置知识：普通 map 如何定位一个键 ​

要理解哈希树，先要看懂普通 map 的查找过程。Go 的 map 是开放寻址 + 桶（bucket）结构：

go
// 简化模型
hash := h.hashFunc(key)           // 64 位哈希
bucket := hash & (nbuckets - 1)   // 低 b 位选桶
// 桶内 8 个槽位，用 hash 的高 8 位（tophash）快速过滤
// 再逐个比较完整键

关键点：普通 map 用哈希的低几位选桶，高八位做桶内快速过滤。桶数量与元素数量成正比，查找是"一次哈希 + 一次取模 + 桶内线性探测"，平均 O(1)。

这个设计对单 goroutine 的 map 很好，但对并发读不友好：扩容（rehash）会移动所有元素，任何读者在扩容期间都会看到"正在搬家的桶"。旧 sync.Map 用"只读快照"绕开了这个问题，代价就是双 map。

三、新实现：哈希树如何做到无锁读 + 廉价写 ​

Go 1.24 引入的新实现换了一个思路：与其让 map 会搬家，不如让数据结构天然不可变前缀。这就是哈希树（hash trie），更准确说是基于 4 位一层的 hash-ary trie。

3.1 结构 ​

把 64 位哈希从低位到高位每 4 位切成一层，每层是一个 16 槽的节点，槽里可能是子节点、值，或空：

text
hash = 0x9e3779b97f4a7c15 (示例)

第0层取低4位:  0x5  → 槽5
第1层取次4位:  0xc  → 槽12
第2层:         0x7  → 槽7
...

level 0                level 1                level 2
┌─┬─┬─┬─┬─┬─┬─┬───┐   ┌─┬─┬─┬─┬─┬─┬─┬───┐
│0│1│2│3│4│■│6│...│──►│0│1│2│3│4│5│6│...│──► ... ──► [value]
└─┴─┴─┴─┴─┴▲┴─┴───┘   └─┴─┴─┴─┴─┴─┴─┴───┘
           槽5 = 指向下一层

查找过程就是顺着哈希的 4 位分组往下走，最多 16 层（64/4），每层一次数组索引。没有扩容搬家——插入新键只在受影响的路径上新建节点，其他所有节点原样共享。

3.2 无锁读的关键：持久化数据结构 ​

哈希树写入时采用"路径复制"（path copying）：修改第 k 层的槽位时，只复制从根到第 k 层的这条路径上的节点，生成一棵新树，然后用 atomic.Pointer 原子地切换根指针。

text
写入前:  root ──► tree v1
                 │
写入时:  复制路径 [n0, n3, n7] 得到 [n0', n3', n7']
         新根 n0' ──► tree v2（其余节点与 v1 共享）

写入后:  root(atomic) ──► tree v2
         tree v1 等待在途读者退出后被 GC

这意味着：

  • 读者永远拿着某个版本的树快照，遍历过程中树不会被改动（旧节点不可变），完全不需要锁。
  • 写者只需复制 O(深度) 个节点（16 进制树深度最多 16），而不是重建整个 map。旧实现"写新键导致整表晋升"的问题消失了。
  • 内存上，不同版本的树共享未修改的节点，比双 map 更省。

3.3 压缩：只有 1/16 的槽有值怎么办 ​

如果每个 16 槽节点都直接开 16 个指针，稀疏时内存爆炸。实现里用了经典的位图压缩（类似 CHAMP/HAMT）：

go
// 简化的节点结构
type node struct {
    bitmap  uint16   // 第 i 位为 1 表示槽 i 有值
    entries []eSlot  // 只存有值的槽，紧凑排列
}

// 槽 i 在 entries 中的下标 = bitmap 低 i 位中 1 的个数
func slotIndex(bitmap, i uint16) int {
    return bits.OnesCount16(bitmap & ((1 << i) - 1))
}

16 位 bitmap 刚好用一个机器字表示，bits.OnesCount 在 amd64/arm64 上是一条 POPCNT 指令，查找开销极低。

四、可运行的验证代码 ​

下面这段代码可以直接跑，对比新旧行为（Go 1.26 上旧实现已移除，可用 Go 1.23 复现旧版对比）：

go
package main

import (
	"fmt"
	"runtime"
	"sync"
)

func main() {
	var m sync.Map

	// 高频写新键 + 读：旧实现的性能悬崖场景
	const writers = 8
	const perWriter = 100_000

	var wg sync.WaitGroup
	for w := 0; w < writers; w++ {
		wg.Add(1)
		go func(base int) {
			defer wg.Done()
			for i := 0; i < perWriter; i++ {
				key := fmt.Sprintf("k-%d-%d", base, i)
				m.Store(key, i)
			}
		}(w)
	}

	// 并发读与写交织
	for r := 0; r < 4; r++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for i := 0; i < 50_000; i++ {
				m.Load(fmt.Sprintf("k-%d-%d", i%writers, i%perWriter))
			}
		}()
	}

	wg.Wait()

	n := 0
	m.Range(func(k, v any) bool { n++; return true })
	fmt.Println("entries:", n, "GOMAXPROCS:", runtime.NumCPU())
}

用 benchmark 对比（Apple M2, Go 1.26 vs Go 1.23.4，数据为典型量级，具体数值依机器而异）：

go
func BenchmarkSyncMapMixed(b *testing.B) {
	var m sync.Map
	b.RunParallel(func(pb *testing.PB) {
		i := 0
		for pb.Next() {
			key := i % 4096
			if i%3 == 0 {
				m.Store(key, i)
			} else {
				m.Load(key)
			}
			i++
		}
	})
}
场景Go 1.23（双 Map）Go 1.26（哈希树）
读多写少（95/5）基准基本持平，略优
读写混合（50/50）明显抖动快 30%~50%
高频写新键最差，频繁整表晋升显著领先，写均摊 O(1)
Range 遍历快照复制树遍历，更平滑

五、对日常开发的三个实际影响 ​

1. sync.Map 的适用面变宽了。 旧文档警告"仅适用于键集合稳定的场景"，新实现下高频写新键不再有悬崖，动态注册表、连接池索引、带 TTL 的本地缓存都可以放心用。

2. 但它不替代带类型的并发结构。 sync.Map 仍是 map[any]any 语义，键值都需要断言。泛型场景下 x/sync 生态中的类型安全封装，或直接 RWMutex + map，在代码可读性上依然占优。一条经验法则：键类型固定、并发读为主 → sync.Map；需要复杂复合操作（先查后写的事务语义）→ 仍然自己加锁。

3. 哈希定位的思路可以迁移。 位图压缩 + 路径复制 + 原子根切换，是纯 Go 实现无锁读数据结构的标准模板，理解这套套路对读 Kubernetes、etcd 等项目的源码也有直接帮助。

参考资料 ​

  • Go 官方源码：src/internal/sync/hashtriemap.go（Go 1.26 标准库）
  • CL 提交记录：go-review.googlesource.com 搜索 "hashTrieMap"
  • Go Blog: "Go maps in action" —— 普通 map 桶结构
  • 论文：Chamberlain & Agha, "Hash Tree Structures"（HAMT/CHAMP 一脉）
  • 华为云 Go 周刊 2026 W35 对该变更的社区讨论

本文同步发布于 friday-go.icu，欢迎在评论区讨论你的 sync.Map 使用场景。

上次更新于: