SQLite 内部原理：世界上最流行的数据库是如何工作的

引言

SQLite 是一个基于文件的数据库，以其极高的可靠性和稳定性著称。它是世界上使用最广泛的数据库——被部署在军事设备、飞机（如空客 A350）乃至太空飞行器中。尽管表面上简单易用，其代码库和内部机制却极为复杂。这种看似简单的特性和广泛的采用，使其成为深度探究软件的绝佳对象。

SQLite 的发音是 "S-Q-L-ite"，如同矿物名称。当然，怎么顺口怎么来。

基于 Abdur-Rahmaan Janhangeer 所著的《SQLite Internals: How The World's Most Used Database Works》以及 Richard Hipp 博士在多场技术会议上的分享，为你系统梳理 SQLite 的核心内部原理。

SQLite 的诞生：一个关于"从零开始"的故事

SQLite 由 Dwayne Richard Hipp（常缩写为 D. Richard Hipp 或 DRH）编写。这个数据库的诞生故事本身就引人入胜，也折射出 SQLite 的开发文化。

DRH 拥有计算语言学博士学位，早期甚至没有修过编程课程。他还拥有电子工程硕士学位，之后进入贝尔实验室工作。离开学术界后，他接手了一份为海军舰艇编写软件的合同——任务是通过控制阀门来解决管道爆裂故障。但当时的数据库服务器频繁宕机，软件几乎无法正常工作。

于是他想：为什么不自己写一个数据库？

"我当时的一个同事说：'Richard，你为什么不自己写一个呢？' '好吧，我试试。'"

恰逢政府合同全部中断，DRH 有几个月没有工作。他对自己说："那我就写个数据库吧。"

与许多流行的项目不同，Richard 从一开始就构思了一个基于字节码驱动的引擎。这体现了他早期在编译器构建方面的积累。在他看来，字节码引擎比直接操作 AST 更具优势——尽管当时他并不完全清楚这一点。

"于是我写了一个能实际运行查询的字节码引擎，然后写了一个编译器把 SQL 翻译成字节码。瞧，SQLite 就这样诞生了。"

发展里程碑

SQLite 并非一夜成名，但人们很早就意识到了它的潜力。以下是几个关键转折点：

摩托罗拉时代：一位用户自发将 SQLite 跑在了摩托罗拉手机的操作系统上。随后摩托罗拉向 Richard 提出了一份 8 万美元的合同，用于提供支持和增强功能。这是 Richard 第一次意识到开源也能带来收入。

美国在线（AOL）：他们希望在邮寄给客户的 CD 中加入 SQLite 数据库。Richard 欣然接受，中途发现原本的方案行不通——这类挑战最终帮助 SQLite 成长为一款健壮的产品。

Symbian 与 SQLite 联盟：Symbian 在评估了 10 款数据库（包括开源和闭源）后选中了 SQLite。但他们担心 Richard 万一不在后项目无法延续，于是提出成立 SQLite 联盟以提高"巴士因子"。Mozilla 基金会的 Mitchell Baker 参与了联盟架构的设计，坚持将项目方向掌控权留在开发者手中。

Google 与 Android：Android 团队找到 Richard 时，SQLite 此前从未在如此大规模的设备上运行过。

"我们到处吹嘘 SQLite 没有 bug——或者没有严重的 bug。但 Android 彻底证明了我们是错的。当你的软件突然部署在数百万台设备上时，会有多少 bug 冒出来，这太惊人了。"

Rockwell Collins 与 DO-178B 认证：这家航空电子设备供应商要求 SQLite 达到航空级质量标准——100% 的 MC/DC 测试覆盖率。这塑造了 SQLite 以测试为核心的开发方法。

从零开始的哲学

SQLite 以大量从零实现功能而闻名。这是一种大胆、惊人且需要极高自信和专业精神的风格。

• 需要 B 树层？他从书架上抽出 Donald Knuth 的算法书，自己实现了 B 树，还完成了书中关于删除元素的习题。
• 不理解为什么人们用 YACC、Bison 和 Lex？他自己写了一个解析器生成器叫 Lemon。
• 用 Git 但某些功能不满意？他写了自己的版本控制系统 Fossil。去 SQLite 官网下载源码，配置的就是 Fossil。
• 连写 SQLite 用的文本编辑器也是他自己写的。

这种"从零开始"的精神赋予了开发者极大的自由度——不受第三方库的限制和潜在问题的困扰。

总体架构概览

SQLite 的整体架构可以分为两大核心部分：

编译器：接收 SQL 语句，输出字节码（预编译语句）。 虚拟机：执行字节码。

从 B 树层往下，称为存储引擎。

一个更具体的分层视图如下：

SQL 语句
    ↓
词法分析器 (Tokenizer)
    ↓
语法分析器 (Parser) — 使用 Lemon 生成的向下自动机解析器，可重入且线程安全
    ↓
代码生成器 (Code Generator) — AST 转换，生成字节码（代码量最大的部分）
    ↓
虚拟机 (Virtual Machine) — 执行字节码指令（代码量第二大部分）
    ↓
B 树层 — B+ 树存储表，B- 树存储索引，每个数据库文件可有多个 B 树
    ↓
页缓存 (Pager) — 处理并发读写、事务、崩溃恢复（回滚模式或 WAL 模式）
    ↓
Shim 层 — 负责压缩、日志、加密，模拟操作系统层
    ↓
虚拟文件系统 (VFS) — 操作系统特定接口，也用于测试时模拟硬件故障

B 树存储引擎

B 树是一种提供对数级操作时间的数据结构。SQLite 尽可能保持树的深度较小，通过在第二层和第三层扩展广度来实现。

SQLite 同时使用 B+ 树（存储表数据）和 B- 树（存储索引）。每个数据库文件可包含多个 B 树。

页面类型

SQLite 文件被划分为等大小的页面（page）。每个页面属于以下类型之一：

• 锁定页面：仅用于向后兼容（Windows 95），由 VFS 层处理而非 SQLite 核心
• 空闲页面：存储在空闲链表中，由 trunk 页面和 leaf 页面组成
• B 树页面：可以是表页面或索引页面，每个页面要么是叶子页面要么是内部页面

记录格式

叶子页面数据部分的记录采用一种二进制格式。每条记录包含：

[头部大小 | 序列类型1 | 序列类型2 | ...] [数据1 | 数据2 | ...]

例如，存储 id=1, quantity=1, price=33, item='shoe' 的记录在磁盘上表示为：

[04 | 01 | 01 | 21] [00 | 03 | shoe]

SQLite 定义了丰富的序列类型编码：

B 树页面结构

每个 B 树页面包含一个头部，格式如下：

• 偏移 0 (1 字节)：页面类型标志
  • 0x02：内部索引 B 树页面
  • 0x05：内部表 B 树页面
  • 0x0a：叶子索引 B 树页面
  • 0x0d：叶子表 B 树页面
• 偏移 1 (2 字节)：第一个空闲块起始位置
• 偏移 3 (2 字节)：页面上的 cell 数量
• 偏移 5 (2 字节)：cell 内容区域起始位置（0 表示 65536）
• 偏移 7 (1 字节)：cell 内容区域内的碎片空闲字节数
• 偏移 8 (4 字节)：最右侧指针（仅内部页面有）

内部页面包含 k 个键（至少 2 个）和 k+1 个指向子页面的指针（32 位无符号整数）。

Varint：变长整数编码

Varint（变长整数）是一种静态霍夫曼编码，用于表示 64 位补码整数。对于小的正数占用更少空间。

• 长度在 1 到 9 字节之间
• 由零个或多个高位为 1 的字节 + 一个高位为 0 的字节组成（或 9 个字节，取较短者）
• 每个字节的低 7 位用于重构数值
• 大端序：前面的字节中的位更高

数据库文件头

SQLite 数据库文件的第一个页面至关重要，它声明了文件的全局信息。

前 16 字节是魔数：53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 33 00（即 "SQLite format 3\0"）。

关键字段包括：

由于第一个页面比普通页面少 100 字节的存储空间，某些页面类型的存储逻辑需要做相应的调整。

页缓存与事务机制

页缓存（Pager）层负责在断电时保护数据不丢失。它使用两种互斥的模式：

回滚模式（Rollback Mode）

这是 SQLite 的默认模式，主要原因是：

1. 某些旧计算机存在特殊的内存映射行为
2. 多台计算机同时访问文件时可能引发问题
3. 向后兼容性

流程：

1. 获取共享锁 → 防止其他进程修改数据
2. 修改数据前将旧值复制到日志缓存
3. 将日志缓存刷新到磁盘日志文件
4. 获取排它锁
5. 将新值刷新到 OS 缓存
6. 提交时删除日志文件

如果提交前断电，恢复时：

1. 获取共享锁
2. 获取排它锁
3. 从磁盘日志复制到日志缓存
4. 从日志缓存复制到 OS 缓存
5. 删除日志，完成回滚

预写日志模式（Write-Ahead Log, WAL）

WAL 模式相比回滚模式有两个核心优势：

1. 允许同时读写
2. 写入速度更快

读取时获取快照，写入时追加到 WAL 文件。检查点（checkpoint）操作会截断日志缓存和磁盘内容。

WAL 模式下，哈希查找页面在共享内存中进行。不同进程的读写操作通过快照隔离并发执行。

虚拟机与字节码

SQLite 的虚拟机（Virtual Machine）包含在 vdbe.c 中。opcodes.h 为操作码分配数值，opcodes.c 为操作码指定符号名称。这些文件由 mkopcodeh.tcl 和 mkopcodec.tcl 脚本自动生成。

每条字节码由操作名和操作参数组成：

opname oparg oparg oparg oparg oparg

通过 EXPLAIN 关键字可以查看基于字节码的查询计划输出。

寄存器与指令

每个字节码程序包含多个寄存器。寄存器可存储 NULL 值、64 位整数或帧对象等各种项。

字节码引擎没有用于存储子程序返回地址的栈——返回地址必须存储在寄存器中。

关键指令示例：

• Goto：无条件跳转到地址 P2
• Gosub：将当前地址写入寄存器 P1，然后跳转
• Return：跳转到寄存器 P1 中存储的地址
• If：条件跳转，仅当寄存器 P1 存有整数时跳转
• Yield：交换程序计数器与寄存器 P1 的值，实现协程切换
• HaltIfNull：如果 r[P3] 为空则终止
• Halt：立即退出，关闭所有打开的游标等。P1 为结果码，P2 决定是否回滚，P4 为错误信息字符串
• Integer：将 32 位整数 P1 写入寄存器 P2

每个程序的末尾会隐式插入一条 Halt 0 0 0 指令。

虚拟表

虚拟表（Virtual Tables）的使用方式与普通表相同，但有以下限制：

• 不能在虚拟表上创建索引
• 不能修改或添加列
• 不能创建触发器

虚拟表不涉及对数据库文件的读写（但某些实现会使用真实表——称为影子表——来存储虚拟表的信息）。

测试文化：100% MC/DC 覆盖率

SQLite 的测试方法论是其可靠性的基石。为了满足航空级 DO-178B 标准，SQLite 实现了 100% 的 MC/DC（修正条件/判定覆盖）测试覆盖率。这使得 SQLite 的测试质量甚至超过了依赖同行评审的 PostgreSQL。

这种测试文化使开发者能够无畏地实验和修改代码——任何回归都会被测试套件立即捕获。

SQLite 的生态与衍生项目

LibSQL

LibSQL 是 SQLite 的一个优秀分支，旨在使 SQLite 真正"开源"（目前 SQLite 是"源代码开放"而非完全的开源模式）。它保持与 SQLite 的状态兼容，并引入了对 WebAssembly（WASM）的原生支持。

LumoSQL

LumoSQL 是一个 100% 基于时间线的克隆版，不依赖于合并主分支。它具有可替换的数据库引擎和 B 树实现，在密码学方面有独特优势。

ABE-SSS 加密方案

Martina Palmucci 的硕士论文在 LumoSQL 项目上实现了基于属性的加密（ABE）与 Shamir 秘密共享（SSS）的结合。方案使用 Ristretto255（基于 Curve25519 应用 Decaf 技术得到）和 ECIES 混合加密，通过布尔策略树实现细粒度的访问控制。

Bloomberg 的定制化

彭博社使用了 SQLite 的代码生成器和存储引擎，但替换了后续层次，实现了自己的大规模、高并发、多数据中心的存储引擎。

名句与哲学

关于不听从所谓的专家：

"我有一个疯狂的想法——构建一个没有服务器的数据库引擎，直接与磁盘对话，忽略数据类型。如果你去问当时的任何专家，他们会说：'这不可能，永远行不通，这是个愚蠢的主意。'幸运的是，我不认识什么专家，所以我做出来了。也许，不要太听专家的话，做你觉得有意义的事，解决你遇到的问题。"

关于不过度思考前方的困难：

"如果早知道这会有多难，我可能根本不会开始写它。"

关于从小型系统中学到的：

"（关于他的 Apple II）只有 4KB 的内存，我能理解那台电脑里发生的一切。但现在最小的电脑也有 4GB 内存，新入行的人绝无可能理解那台电脑里发生的一切。"

关于如何积累他这样的知识：

"我花了四十年、将近五十年的时间积累这些知识。你怎么能用四年的大学教育学会这些？我不知道。有些东西你只能先当作信念接受——是的，这能行，相信它。"

延伸阅读

1. SQLite, A Database for the Edge of the Network, DRH, Databaseology Lectures, Carnegie Mellon (2015)
2. CORECURSIVE Podcast, Episode #066, The Untold Story of SQLite
3. Richard Hipp Speaks Out on SQLite, ACM SIGMOD interviews (2019)
4. DEF CON 27 - Omer Gull - SELECT code execution FROM USING SQLite
5. SQLite 文件格式官方文档
6. SQLite Internals: B-trees
7. Changelog Podcast Episode 201, Why SQLite succeeded as a database
8. SQLite: Past, Present, and Future, VLDB 2022