徐术挺-漫思录

00-设计推演-从零造一个内存分配器

17分钟阅读

00 · 设计推演：从零造一个内存分配器

“Go 的分配器有 67 个 size class、三层结构、每 P 一个 mcache——这些都不是设计者的偏好，是被一个接一个的具体问题逼出来的。“

开场：先问”为什么不能直接用 mmap”

老陈：需求：分配任意大小的内存块，用完能释放。

小林：直接 mmap 不行吗？

老陈：可以。但先算两笔账。

第一笔：mmap 有多贵？

小林：……系统调用，大概几百纳秒？

老陈：对，约 500ns-1μs。对比一下：一次函数调用 2ns。

如果一个 HTTP 请求要分配 100 个对象呢？

小林：……50 微秒？那 QPS 最多两万。

老陈：第二笔账：mmap 的最小单位是什么？

小林：……页，4KB？

老陈：对。你只要 8 字节，它也给你 4KB。浪费 512 倍。

小林：那……要有一个”批发 + 零售”的中间层？

老陈：这就是内存分配器的全部意义。开始设计。

v0：直接 mmap

func Alloc(size int) []byte {
	// 每次都向 OS 要
	addr, _ := syscall.Mmap(-1, 0, size,
		syscall.PROT_READ|syscall.PROT_WRITE,
		syscall.MAP_PRIVATE|syscall.MAP_ANONYMOUS)
	return addr
}

能工作。 但前面算过了：

#问题数据
1系统调用开销~500ns/次，是函数调用的 250 倍
2页粒度浪费要 8 字节给 4096 字节，浪费 512 倍
3无法精细回收munmap 也是页粒度

老陈：注意第 3 点。这是最容易被忽略的。

如果你 mmap 了 100 个 8 字节对象，它们可能散布在几个页里。 释放其中 99 个，一个页都还不了 OS——因为每个页里还剩一个在用。

这叫”碎片导致的无法归还”。后面的设计都会跟它斗争。

v1：批发——一次 mmap 一大块，自己切

改动：先向 OS 要一大块（比如 64MB），然后在里面切分。

type Arena struct {
	data []byte
	used int
}
 
func (a *Arena) Alloc(size int) []byte {
	// ★ 简单的指针碰撞（bump）
	off := a.used
	a.used += size
	return a.data[off : off+size]
}

改进巨大：

分配: 从"系统调用"变成"一次加法"
     ~500ns → ~2ns，快 250 倍

失败：

#问题说明
1不能单独释放只能整体重置
2内存只增不减长期运行会耗尽

问题 1 值得展开——bump allocator 只能”整体重置”。

但它在特定场景是最佳选择：一次请求处理、一帧渲染、一个查询执行——对象生命周期一致。

老陈：这是全书第一次出现”用约束换性能”。

接受”对象生命周期必须一致”这个约束，换来 O(1) 分配 + 零碎片 + 完美局部性。

后面你会反复遇到这笔交易：

  • 栈分配（生命周期 = 函数）
  • Arena（生命周期 = 批次）
  • 不可变段（生命周期 = 直到 compaction）

v2：空闲链表（Free List）

针对 v1 的问题 1，加上”单独释放”能力。

思路：把释放的块串成链表，分配时从链表里找。

type block struct {
	next  *block
	size  int
}
 
var freeList *block
 
func Alloc(size int) unsafe.Pointer {
	// 遍历空闲链表，找第一个够大的（First Fit）
	prev, cur := (*block)(nil), freeList
	for cur != nil {
		if cur.size >= size {
			// 找到了，可能分裂
			removeFromList(prev, cur, size)
			return cur.data()
		}
		prev, cur = cur, cur.next
	}
	// 没有合适的，从 arena 切新的
	return bumpAlloc(size)
}
 
func Free(ptr unsafe.Pointer) {
	b := blockOf(ptr)
	b.next = freeList    // ★ 头插法
	freeList = b
}

改进：能单独释放了。

失败：

#问题数据
1分配是 O(链表长度)链表长的时候慢
2★ 外部碎片下面详细说

问题 2 是致命的。 看一个真实测试：

4MB arena，反复随机分配/释放 1-200 字节:

结果: 分配失败 847 次
      存活对象只占 123 KB
      ★ 4MB 内存，只用了 123KB 就分配不出东西了

为什么？

内存布局（■=已分配 □=空闲）:
■□■■□■□■□□■■□■□■□□■■■□■□□□■□■■□■□■□□■■□■□■□□■■□■□■□□■
  ↑   ↑  ↑   ↑ ↑  ↑     ↑  ↑   ↑ ↑  ↑
  全是小空洞，每个都放不下新请求

空闲总量可能有 3.8MB，但不连续 → 不可用

老陈：外部碎片的本质是：不是”空间不够”，而是”空间不连续”。

这是理解后面所有设计的钥匙。

v3：Size Class + 分离空闲链表

核心洞察：碎片的根源是”块大小五花八门”。

那如果规定：块大小只能是固定的几种呢？

// 8, 16, 24, 32, 48, 64, 80, 96, 112, 128, 160, ...
var sizeClasses = []int{...}
 
func Alloc(size int) unsafe.Pointer {
	cls := sizeToClass(size)      // 找到 >= size 的最小 class
	return allocFromClass(cls)    // 每个 class 一条独立的空闲链表
}

改进：

改进原因
分配 O(1)直接取对应 class 链表的头部，不用遍历
无外部碎片同一 class 的块大小相同，释放后可完美复用
释放 O(1)头插法

代价：内部碎片

要 20 字节，给 32 字节 → 浪费 12 字节

★ 这是"用内部碎片换外部碎片"

★ 关键设计问题：size class 怎么划分？

方案 A: 2 的幂（8, 16, 32, 64, 128...）
  最坏浪费率: 接近 50%
  （要 33 字节给 64 字节，浪费 48%）
  size class 数量: 少

方案 B: 细粒度（8, 16, 24, 32, 48, 64, 80, 96...）
  最坏浪费率: ~12.5%
  size class 数量: 多

★ Go 选 B，共 67 档（8 字节 ~ 32KB）

为什么 Go 愿意用 67 档换 12.5% 的浪费率？

因为 size class 的代价是"管理开销"（每档一条链表），
而内部碎片的代价是"真实的内存浪费"。

内存比管理开销贵得多。

★ 而且注意 Go 的档位不是均匀分布:
  8~128:   间隔 8 字节     ← 小对象多，分得细
  128~512: 间隔 16 字节
  512+:    间隔逐渐变粗

★ 设计原则: 让"最坏情况下的浪费率"大致恒定

老陈：这是”优化目标决定参数分布”的典型例子。

如果你的目标是”size class 数量最少”，你会用 2 的幂。 如果你的目标是”浪费率最低”，你会用细粒度。

Go 的目标是”浪费率恒定在一个可接受的水平”——这直接决定了 67 档这个数字和它的分布。

先明确优化目标，参数几乎是唯一确定的。

v4：三层缓存 + 每 P 一个 cache

针对并发：多线程同时分配，freeList 是共享的 → 要加锁 → 锁竞争。

实测: 8 核机器上，一个全局锁的分配器
      吞吐随核数增加几乎不涨（甚至下降）

解法：层次化缓存

第 1 层: mcache（每个 P 一个，无锁）
         分配时从这里取，O(1) 无锁

第 2 层: mcentral（每个 size class 一个，加锁）
         mcache 空了，从这里批量补充

第 3 层: mheap（全局，加锁）
         mcentral 空了，从这里要 span

第 4 层: OS（mmap）
         mheap 空了，向 OS 要 64MB arena

★ 关键设计：为什么是三层而不是一层？

一层（全局锁）:
  每次分配都加锁 → 锁竞争是瓶颈

两层（per-thread + 全局）:
  大部分分配无锁 ✓
  但"补充"操作仍然频繁

三层（per-P + per-class + 全局）:
  · mcache: 无锁，覆盖 99% 的分配
  · mcentral: 按 size class 分锁 ★
  · mheap: 全局锁，但极少走到

★ "按 size class 分锁"是关键
  分配 32 字节的请求，没必要跟分配 4096 字节的请求抢同一把锁
  这叫锁分片（Lock Sharding）

★ 为什么 mcache 绑定 P 而不是 M（OS 线程）？

① M 的数量是动态的
   系统调用阻塞时会创建新的 M
   一个 8 核机器可能有几百个 M
   → 每个 M 一个 mcache 会浪费大量内存

② P 的数量是固定的（= GOMAXPROCS）
   → 最多 GOMAXPROCS 个 mcache，内存可控

③ G 必须绑定 P 才能执行
   → 从 P 取 mcache 是免费的（P 已在本地缓存）

★ 核心思想: P 是"资源的所有权单位"，M 只是"执行能力"

v5：微小对象优化（Tiny Allocator）

还剩一个问题：小于 16 字节的对象。

要分配一个 8 字节的 bool 指针:
  size class 最小是 8 字节 → 看起来没问题？

但如果是一个 16 字节的结构体里放两个 8 字节指针:
  → 每个指针 8 字节，各自一个 span
  → 缓存局部性差，且 span 元数据开销大

Go 的解法：Tiny allocator —— 把多个微小对象（<16B 且不含指针）塞进同一个 16 字节块。

// 分配 3 个 int32（各 4 字节）
// 传统: 3 个 8 字节的块 = 24 字节
// Tiny: 塞进 1 个 16 字节块 = 16 字节

★ 为什么要求”不含指针”？

因为含指针的对象需要被 GC 扫描。
如果把多个含指针对象塞进一个块，GC 就分不清块里哪些字节是指针。

不含指针的对象（int32、bool、float64）：
  GC 完全不用管 → 可以随意打包

老陈：这个限制体现了 Go 的一个设计原则：

“能利用的信息尽量利用，能用约束换来的优化尽量换。”

“不含指针”是编译期已知的信息——利用它，换来 33% 的空间节省和更好的局部性。

同样的思路出现在第 1 章第 05 节讲的：[]byte、[]int64 这类无指针类型，GC 完全不扫描。

v6：大对象怎么办？

超过 32KB 的对象不走 size class（因为 67 档已经到 32KB 了）。

直接走 mheap，分配整数个页。

func largeAlloc(size int) *mspan {
	npages := (size + pageSize - 1) / pageSize
	return mheap.alloc(npages)
}

为什么是 32KB 这个阈值？

权衡:
  · 阈值小 → size class 少，管理简单，但大对象走 mheap 频繁（慢）
  · 阈值大 → size class 多，管理复杂，但更多对象能走快速路径

32KB 是实测的经验值（tcmalloc 也是类似的量级）

v7：还差什么

到这里，Go 的分配器基本成型。剩下的：

机制解决的问题
Scavenger后台把长期空闲的物理页还给 OS
Page reclaimer细粒度的页回收（Go 1.16+）
MemoryLimitGo 1.19+ 软内存上限，容器环境必备
span 的 age 字段标记 span 空闲时长，辅助 scavenger 决策

★ 这一节真正的收获

需求: 分配任意大小内存，用完释放
  │
  ├─ v0 直接 mmap
  │    失败: 系统调用 500ns；页粒度浪费 512 倍；★ 无法精细归还
  ↓
  ├─ v1 批发 + bump 指针           ← 快 250 倍
  │    失败: 不能单独释放；内存只增不减
  ↓
  ├─ v2 空闲链表
  │    失败: 分配 O(n)；★ 外部碎片（4MB 只用 123KB 就失败）
  ↓
  ├─ v3 size class + 分离空闲链表   ← 用内部碎片换外部碎片
  │    失败: 多线程锁竞争
  ↓
  ├─ v4 三层缓存 + mcache 绑 P      ← 层次化 + 锁分片
  │    剩下: 微小对象浪费；大对象路径
  ↓
  ├─ v5 Tiny allocator（无指针打包）
  └─ v6 大对象走 mheap

五个可以迁移的思维模式

① 批发零售模式

向慢的下一层请求时，一次要一大批，然后在快的本层零售。 这在第 1 章出现过三次：CPU 缓存行、TLB、Buffer Pool。这是全书法则 #2。

② 用约束换性能

bump allocator 接受”生命周期一致”→ O(1) 分配。Tiny allocator 接受”不含指针”→ 空间打包。 每次问：“我能不能加一个限制，换来更简单的实现？”

③ 碎片有两种，交易方向相反

外部碎片（不连续）vs 内部碎片（分配了没用完）。 size class 是用后者换前者。理解这个交易，你就懂了所有分配器的核心设计。

④ 优化目标决定参数分布

67 个 size class 不是拍脑袋的——是”让最坏浪费率恒定在 12.5%“这个目标推出来的。 先明确目标，参数就唯一确定了。

⑤ 分层 + 分片解决并发

三层结构降低锁的触及频率；按 size class 分锁降低锁的粒度。 这是”降低锁竞争”的两个标准手段，适用于所有并发数据结构。

现在，轮到你了

练习：我们设计的分配器有一个隐含假设——单线程或每个 P 独立。

但如果一个 goroutine 在 P1 上分配了对象，然后被调度到 P2 上执行，最后在 P3 上释放呢？

提示（不要用，先自己想）：

  • 跨 P 释放会有什么问题？（想想 mcache 的设计前提）
  • Go 是怎么处理的？（提示：释放时根据”对象属于哪个 span”来路由）
  • 这会不会成为性能问题？什么情况下会？
  • 如果是你设计，有没有别的方案？

老陈：答案是：Go 允许跨 P 释放。释放时通过地址找到对应的 span，再路由到正确的 mcentral。

代价是：跨 P 释放比同 P 释放慢（要走 mcentral 的锁）。

这也是为什么”对象在同一个 P 上分配和释放”是性能更优的模式—— 在极致优化的场景（比如高频交易系统），这个细节会造成可观测的差异。

如果你来设计，可以考虑：能不能让”分配时的 P”记录在对象里，释放时快速路由？ 或者：能不能接受”延迟归还”（批量把空闲块还给原 P）？

下一节

01 · 开篇：一次查不出的 P0 事故

这一节我们推导了分配器本身，下一节看一个真实事故——当分配器和硬件（NUMA）打架时会发生什么。

带着这个问题去读：分配器认为”内存是均匀的”，但硬件不这么认为。这个错配会带来什么后果？

反向链接