02. 定长块:从内存分页到 InnoDB 数据页

0. 本章先解决什么问题

学 MySQL 的时候我记住了”InnoDB 以 16 KB 的页为单位管理数据”,学操作系统的时候又记住了”内存以 4 KB 的页为单位管理”。当时当成两个孤立知识点背,后来才看清这是同一个决定在不同尺度上的重复:

把存储切成固定大小的块,按块分配、按块搬运、按块缓存。

本章把每一层的块都当正主讲:OS 的页和页表怎么工作、InnoDB 的 16 KB 页里面到底装了什么、磁盘扇区和 SSD 擦除块的物理约束、Kafka 段和稀疏索引的构造,以及一个容易搞混的反例:Redis 里没有页也没有 B+ 树,但定长思想换了个地方出现。

这张图怎么读

从左到右尺度递增:CPU 缓存行 64 字节、OS 内存页 4 KB、InnoDB 数据页 16 KB、Kafka 日志段 1 GB。每一层的块都是那一层”分配、搬运、缓存”的最小单位,尺寸由那一层的介质成本决定。

1. 为什么是定长块,而不是要多少给多少

假设存储按需分配任意长度,会遇到三个麻烦:

1. 外碎片: 释放后留下大小不一的洞,总空闲够但连续的不够
   (malloc/free 混战之后要 128 KB 连续空间,翻遍堆找不到)
2. 记账复杂: 每块的起点、长度都要记,找一块合适的要搜索、
   要挑选策略(首次适应还是最佳适应),分配本身变慢
3. 搬运低效: 磁盘和内存之间的传输,硬件天然按块工作,
   变长的搬运单位对不齐硬件的节拍

定长块用一点内碎片(块内尾部浪费)换三个便宜:

1. 分配就是找一个空位: 位图或空闲链表,O(1) 级别
2. 地址换算就是算术: 块号 x 块大小 + 块内偏移,无需查询
3. 传输、缓存、淘汰统一以块为单位,整条管理链共用一个粒度

这和 Java 里 ArrayList 永远只管理一整块连续数组、宁可扩容浪费也不碎着存,是同一个味道:用可控的空间浪费换管理模型的极简。

2. 各层的块尺寸总表

两条规律贯穿全表:

1. 越靠近 CPU 块越小,越靠近冷存储块越大。
   延迟越高的介质,越要靠”一次多带”摊薄每次访问的固定成本。
2. 上层块通常是下层的整数倍。
   InnoDB 一页 16 KB = 4 个文件系统块 = 4 个内存页,对齐才不浪费。

缓存行 64 字节这一格牵出的伪共享问题(两个变量挤同一行被不同线程写,行在核间弹跳),已在 缓存分层 连同 LongAdder 的填充手法完整展开,此处记住它属于”块粒度带来的误伤”即可。

2.1 对齐与 padding:块的习惯漏进了结构体设计

CPU 按对齐的块取数这个习惯,会一路漏到每个语言的结构体内存布局里,这就是各种 padding 字段的来历:

• 硬件事实:CPU 取一个 8 字节数,地址是 8 的倍数就一次访存搞定;
  跨在两个块上就要两次访存再拼接,有些架构干脆报错
• C 结构体的规则:每个成员按自身大小对齐(int 对 4,long 对 8),
  编译器在成员之间和结构体末尾自动塞 padding 补齐
  -> 成员声明顺序会影响结构体大小,大到小排列最省
• JVM 对象:默认按 8 字节对齐,对象头 + 字段(JVM 会自动重排
  字段顺序减少空洞)+ 末尾 padding 补到 8 的倍数
  对齐还白送一个大礼: 地址都是 8 的倍数,低 3 位恒为 0,
  压缩指针就能右移 3 位借出空间,32 位引用寻址 32 GB 堆
• 缓存行级的 padding:@Contended / LongAdder 的 Cell 填充,
  把字段撑到独占 64 字节行,防伪共享(缓存分层一章的主角)
• jemalloc 的档位:8、16、32、48 全是 8 的倍数,分配出来天然对齐

一个精彩的反例把规则的适用条件挑明了:Redis 的 SDS 头部声明成 packed(强制取消 padding)。
它敢反着来,因为 SDS 头的字段本来就按单字节读写,不吃对齐的红利,而 Redis 里千万级的字符串对象,每个省几字节 padding 就是省出上百 MB。
对齐换访存速度,紧凑换内存,两头都是定长块思想在字节尺度的账。

3. OS 的 4 KB 页:分页机制完整过一遍

3.1 为什么需要虚拟内存

程序里的指针值全是虚拟地址,硬件配合 OS 把它翻译成物理地址。这层翻译买到三样东西:

• 隔离:每个进程一张页表,看不见别人的物理页,
  野指针最多写坏自己
• 重定位:物理内存可以任意腾挪(换出、整理),
  程序里的地址不用变,改页表映射就行
• 超卖:声明 2 GB 只在真正摸到时才给物理页,
  所有进程声明的总量可以远超物理内存

3.2 页表和缺页

以页为单位翻译才让页表这个方案可行:4 KB 一页,32 位地址空间只需约一百万条映射,还能用多级页表把没用到的区段整段省掉;若按字节翻译,映射表本身比内存还大。
翻译加速靠 TLB(缓存分层 第一站里的那层)。

访问一个页表里没有有效映射的地址,CPU 抛缺页异常,OS 接手分四种结局:

1. 页在磁盘交换区或文件里 -> 读进来,补映射,重执行指令(major fault,毫秒级)
2. 页是”声明了还没给”的 -> 分配一个零页补上(minor fault,微秒级)
3. 页是写时复制的共享页 -> 拷一份再写(第 10 章 COW 的主场)
4. 纯非法访问 -> SIGSEGV,Java 世界里 JVM 把它接住变成各种错误

“进程 RSS 远小于声明的堆大小""程序刚启动跑得慢,热起来就快了”这两个日常现象,分别对应超卖和缺页换入。完整机制在 内存管理。

3.3 4 KB 这个数怎么来的

页大小是两头拉扯的平衡点:页越大,页表越小、TLB 覆盖越广、单次缺页搬运越多,但内碎片越重(平均每个内存区浪费半页);页越小则反过来。4 KB 是历史沿革下的通用平衡点,数据库和大内存 JVM 常开 2 MB 大页,用内碎片换 TLB 命中,方向依然是这两头的权衡。

4. InnoDB 的 16 KB 页:拆开看内部构造

MySQL 的表数据文件(.ibd)整个由 16 KB 的页排成,每页的骨架从头到尾是:

File Header(38 B): 页号、前后页指针、最后修改的 LSN、页类型、校验和
前后页指针把同一层的页串成双向链表(B+ 树叶子层的横向链)
Page Header(56 B): 页内记录数、还剩多少空闲、页目录槽数等页内账本
Infimum / Supremum: 系统预置的最小、最大虚拟记录,
页内记录链表的固定头尾哨兵
User Records: 真正的行,按主键顺序组成单向链表
(物理上按插入顺序堆放,逻辑顺序靠链表指针维持)
Free Space: 还没用掉的空间,从中间被 User Records 逐渐蚕食
Page Directory: 每隔几条记录设一个槽,指向该组最大记录
页内查找先在槽数组上二分,再沿链表短距离顺扫
(没有它,页内查找就是纯链表遍历)
File Trailer(8 B): 校验和 + LSN 低位,读页时和 File Header 比对,
检测出”只写了半页”的损坏

两个设计值得专门咀嚼:

页内为什么是”链表 + 槽二分”而不是纯数组:
插入新行只改链表指针,不用像数组那样搬移后续所有行;
查找性能靠页目录的稀疏槽补回来。空间换算力的微型样板。
File Trailer 为什么存在:
16 KB 页刷盘时底层是 4 个文件系统块,中途断电可能只写一半;
头尾校验对不上就知道页坏了,配合 doublewrite buffer 修复
(doublewrite 的完整机制在日志先行一章)。

4.1 B+ 树的节点就是页:扇出算术

平衡树、红黑树与 B/B+ 树 从数据结构角度推过”页改变了树的设计”,这里补工程侧算术:

非叶子页只存”键 + 子页号”:
bigint 主键 8 B + 页号指针 6 B = 14 B
16 KB / 14 B ≈ 1170 个分叉
叶子页存整行,假设一行 1 KB: 一页约 16 行

• 高度 2:1170 x 16 ≈ 1.8 万行
• 高度 3:1170 x 1170 x 16 ≈ 2000 万行

这就是”两千万行以内三层就够,一次按主键查询最多三次页 IO”的完整推导(根页几乎必在 buffer pool,实际磁盘 IO 更少)。
反向结论有两条:单表行数逼近再上一个数量级,树要长到第四层,每次查询多一次 IO,这是”单表两千万要考虑拆”经验值的出处;主键越长,非叶子页扇出越小、树越高,这是”主键别用长字符串”的出处。
二级索引叶子存的是主键值而不是整行,查完还要回聚簇索引再走一遍,这是”回表”的机制来源,展开在 索引。

4.2 页分裂与合并:定长块的代价现场

页是定长的,插入是无限的,装不下就要分裂:

乱序主键(如 UUID)插入:
新行经常落进已满的页中间
-> 分裂: 申请新页,搬走约一半记录,更新前后链表和父节点
-> 三笔代价: 写放大(一次插入引发多页写)、
空间空洞(分裂后两页各半满)、缓存命中下降(逻辑相邻物理分散)
自增主键插入:
永远追加在最右侧页,页满就开新页,几乎不分裂
删除到页很空时:
相邻页合并(默认阈值是页容量一半),减少半空页

“主键要用自增”这条规矩优化的就是 16 KB 块的填充率和分裂频率。大字段(TEXT、超长 VARCHAR)单页装不下的处理:默认行格式(Dynamic)在行内只留 20 字节指针,正文整个放溢出页。定长块管普遍情况,例外单独开路,这个补丁模式后面还会反复见到。

5. 磁盘的块:扇区、文件系统块、SSD 擦除块

5.1 机械盘和文件系统

• 扇区:磁盘控制器的读写原子单位。传统 512 B,
  现代盘物理 4 KB(有些对外仍模拟 512 B 兼容老系统)
• 文件系统块:ext4 默认 4 KB,刻意对齐内存页,
  页缓存里一页恰好装一个块,搬运不用切割
• 后果:文件不足 4 KB 也占一整块(内碎片),
  海量小文件的目录”占用空间”远大于”文件总大小”就是这么来的

5.2 SSD:定长块最苛刻的一层

闪存的物理规则给块加了硬约束:

读写单位是 page(4~16 KB),但擦除单位是 block(数百 KB 到数 MB)
写过的 page 不能原地改写,必须先整块擦除才能再写
-> 改 4 KB 数据的真实动作: 把新数据写到别处的空 page,
旧 page 标记作废,攒够作废后由 GC 搬走整块里的存活数据再擦除
-> 写放大: 应用写 1 的量,介质实际写了好几倍
FTL(闪存转换层): 维护”逻辑块地址 -> 物理位置”的映射表
磨损均衡、GC 都在这层做(它本身又是下一章间接层的实例)

这解释了两件事:SSD 也偏爱顺序大块写(整块整块地写和作废,GC 几乎不用搬数据);SSD 越满越慢(空块少,GC 被迫频繁搬运)。

6. Kafka 的段:以文件为块,配稀疏索引

Kafka 把”按块管理”推到文件尺度。一个 partition 在磁盘上是一串段文件:

00000000000000000000.log 1 GB 满了就滚动新段(log.segment.bytes)
00000000000000000000.index 偏移量稀疏索引
00000000000000000000.timeindex 时间戳稀疏索引
文件名 = 该段第一条消息的 offset,段列表天然按 offset 有序

稀疏索引的构造和查找:

稀疏的意思是:索引项远少于消息,每写入约 4 KB 日志(log.index.interval.bytes)
才记一条 (相对 offset, 文件物理位置)
查 offset = 5000:

1. 按文件名二分定位到段
2. 在该段 .index 里二分,找到 <= 5000 的最大索引项
3. 从那个物理位置起顺序扫一小段(最多 4 KB)找到目标

敢用稀疏是因为负载形态:消费是顺序读,定位只发生在重启或回溯时,偶尔多扫 4 KB 不值得为它付出稠密索引的空间。对照 InnoDB 的页内”稀疏槽 + 短顺扫”,同一个手法在两个尺度上出现。

删除策略同样按块:数据以段为单位过期,删数据就是删文件,不存在”找到该删的行再腾空间”的逻辑。块越大,管理动作越粗,越适合顺序写入、批量过期的日志型负载。这印证第 2 节的规律:越冷的数据,块越大。

7. 澄清:Redis 里没有页,也没有 B+ 树

我一度以为”数据库都用 B+ 树和 16 KB 页”,Redis 大概也差不多。这个印象是错的,纠正它正好暴露定长块的适用条件:

B+ 树 + 页,优化的是磁盘 IO:
磁盘按块读写、随机访问毫秒级
-> 把树节点做成一个页,一次 IO 多带数据,把树压矮
Redis 数据全在内存:
内存按字节寻址、随机访问纳秒级
-> 没有”按块读写”的硬约束,不需要页
-> 有序结构选了跳表,实现远比 B+ 树简单,范围查询同样对数级

Redis 世界的实际结构,逐个点名:

• dict:全局键空间。数组 + 链表的哈希表,
  扩容用渐进式 rehash(机制在惰性与摊销一章展开)
• skiplist:zset 的有序底座,多层链表,每个节点随机抽层数
  (抽中概率 1/4,最高 32 层),配合 dict 实现 O(1) 按成员查分数
• listpack:小集合的紧凑形态。整个集合挤进一块连续内存,
  牺牲单点操作复杂度,赚缓存局部性和极低的内存开销
  (元素少时线性扫比跳表还快,就是因为整块都在 CPU 缓存里)
  hash/zset/list 元素少时都用它,超过阈值转正式结构
• quicklist:list 的底座,双向链表串起一个个 listpack 块
• intset:全整数的小 set,有序数组直接存

有趣的是定长思想在 Redis 里换了个地方复活。Redis 用 jemalloc 做内存分配,jemalloc 按固定档位切内存:

小对象档位: 8, 16, 32, 48, 64, 80, … 字节逐级排开
申请 33 字节 -> 给 48 字节的槽,浪费 15 字节(内碎片)
换来: 同档位的槽整齐排列,分配释放极快,外碎片可控

INFO memory 里 used_memory(Redis 记账的逻辑用量)和 RSS(OS 给的物理内存)的差值除出来就是碎片率 mem_fragmentation_ratio:1.0 到 1.5 属正常(档位内碎片 + 空闲槽),远大于 1.5 说明大量删除后空闲槽还占着物理页(可开 activedefrag 整理),小于 1 说明内存被交换到磁盘了,性能警报。
介质变了,块的位置从”数据文件”挪进了”分配器”,思想没变。

各结构的源码级细节在 skiplist、listpack、dict;跳表和 B+ 树的选型对比在 bitmap - bloom - skiplist。

8. 其他数据库一览

• PostgreSQL:8 KB 页 SQL Server: 8 KB 页
• SQLite:默认 4 KB 页 MongoDB(WiredTiger): B 树家族 + 块管理
• HDFS:128 MB 块,大文件切块分布到多台机器,
  块大到”寻址时间占传输时间的比例可忽略”

页大小不同只是各家对”一次 IO 带多少”的估值不同,结构角色完全一致。

9. 联系实际:定长块解释的日常现象

• 现象:只 SELECT 一行,监控显示读了 16 KB

• 解释:InnoDB 最小读写单位是页,取一行也要整页载入 buffer pool

• 现象:表删了一半数据,磁盘文件没变小

• 解释:删除只是页内标记 + 页进空闲列表,文件尺寸不缩,
  要 OPTIMIZE TABLE 重建才归还

• 现象:UUID 主键的表,插入越来越慢,空间比数据大不少

• 解释:乱序插入频繁页分裂,页填充率掉到一半上下

• 现象:海量 1 KB 小文件,du 看总量比文件内容大好几倍

• 解释:文件系统 4 KB 块的内碎片

• 现象:SSD 用到 90% 以后写入明显变慢

• 解释:空擦除块不足,FTL 的 GC 被迫高频搬运,写放大飙升

• 现象:Redis 碎片率 2.1

• 解释:大批删除后 jemalloc 空闲槽未归还 OS,考虑 activedefrag

• 现象:Kafka 磁盘清理总是一大块一大块地释放

• 解释:过期以段为单位,删的是整个 1 GB 文件

10. 学完本章你能解决什么问题

1. 定长块用什么代价换了什么便宜,三个”便宜”分别是什么?
2. 虚拟内存的页表为什么必须以页为粒度,缺页有哪四种结局?
3. InnoDB 页内为什么用”链表 + 页目录二分”而不是数组?
4. File Trailer 的校验和在防什么事故?
5. 16 KB 怎么推出”2000 万行三层”,主键长度为什么影响树高?
6. 页分裂的三笔代价是什么,自增主键为什么能避开?
7. SSD 的写放大怎么产生,为什么越满越慢?
8. Kafka 的稀疏索引为什么敢稀疏,查找的三步是什么?
9. Redis 为什么不需要页和 B+ 树,定长思想在它哪个部件里复活?
10. 碎片率 1.3、2.1、0.8 分别说明什么?
11. 结构体 padding 和 JVM 的 8 字节对齐各在优化什么,SDS 为什么敢反着来?

核心一句话:定长块是存储层的通用协议,块大小是那一层介质延迟和管理成本的平衡点;判断一个系统用不用页,先看它的数据在磁盘还是在内存;块的代价(内碎片、分裂、写放大)在哪,调优的抓手就在哪。

延伸阅读

• 内存管理
• 平衡树、红黑树与 B/B+ 树
• 索引
• InnoDB引擎
• skiplist
• listpack
• dict