论文笔记 SQLite: Past, Present, and Future

• 论文名称：SQLite: past, present, and future

• 作者单位：威斯康星大学麦迪逊分校 (University of Wisconsin-Madison)的三名研究人员和 Sqlite 社区的三名贡献者

• 发表期刊：VLDB Endowment（数据库领域三大顶会之一），01 August 2022

TL; DR

这篇论文 novelty 比较一般，主要跑了几个 benchmark 然后基于测试场景提出了一个奇奇怪怪的优化方法. 但对 SQLite 的一些介绍和分析比较全面，因此也是比较值得阅读的.

历史与架构

历史

SQLite自2000年首次发布以来，已成为最广泛部署的数据库引擎之一，存在于几乎所有智能手机、计算机、网络浏览器、电视和汽车中.

它的普及归功于其跨平台，自包含和极小的 release 体积，可靠和快速.

引擎架构

模块

如图，SQLite 使用了模块化的设计. 它的架构包括SQL编译器模块、核心模块、后端模块和一些辅助模块，如测试代码和实用工具.

• core modules. 核心模块负责接收和执行SQL语句.
  • SQLite 的虚拟机又叫 virtual database engine (VDBE)，是 SQLite 的核心. 其执行代码的过程其实类似于 JVM，略.
• SQL compiler modules. SQL编译器模块将SQL语句转换为字节码程序，该程序可以由虚拟机执行.
  • 可以把每个 SQL statement 看做一个源码. SQLite 就像一个编译器一样，拥有 Tokenizer、Parser 和 Code Generator，将 SQL statement 转换为 bytecode. Bytecode 如上图所示，包括 opcode 和 oprands，例如 Column 就是从当前行取某一列的值存入寄存器.
• backend modules. 后端模块用于访问数据库页并与 OS 交互以持久化数据.
  • VDBE 高强度和 backend 交互，主要是在操作 B 树.
• accessory modules. 包括超大规模的测试代码和一些实用工具，例如用于内存分配、字符串操作和随机数生成.

backend 细节

B树

SQLite 数据库文件本质上是B树的集合. 分为两种：表B树和索引B树

• 表B树（Table B-trees）：
  • 使用64位有符号整数作为键（key）;
  • 数据存储在叶节点中.
• 索引B树（Index B-trees）：
  • 使用任意键.
  • 不存储数据.

数据库表的表示

• 数据库中每个表都由一个表B树表示.
• 表B树的键是表的隐式rowid列.
• 对于INTEGER PRIMARY KEY表，主键列取代rowid成为B树的键.
• 声明为 WITHOUT ROWID的表是特殊情况：
  • 这些表完全存储在索引B树中.
  • WITHOUT ROWID表的B树键由主键列组成，然后是表的所有剩余列.
• 数据库架构中的每个索引都有一个索引B树，除非索引已由表B树表示，如INTEGER PRIMARY KEY表的情况.

页缓存（Page Cache）

• 页缓存负责提供B树模块请求的数据页.
• 页缓存还负责确保修改过的页能够安全且高效地刷新（flush）到稳定存储中.

操作系统接口

• SQLite使用一个称为虚拟文件系统（VFS）的抽象对象来跨操作系统提供可移植性.
• SQLite为Unix和Windows操作系统提供了几种现成的VFS.
• 可以通过创建 VFS 来支持新的操作系统或扩展SQLite的功能.

值提取

• 灵活的类型系统：SQLite允许任何类型的数据存储在任何列中（INTEGER PRIMARY KEY列除外）.
• 列声明灵活性：SQLite中可以创建没有数据类型声明的列，如 CREATE TABLE t (a, b, c);.
• 类型信息存储：每个值旁边都会存储类型信息，SQLite记录分为头部和主体，头部包含数据类型编码，主体包含实际值.
• 值提取过程：
  • 查找过程：通过检查记录头部的指针，确定值的位置，头部包含每列数据类型的序列化类型码.
  • 计算偏移量：SQLite遍历头部的类型码，累加每个值的大小来计算所需值的偏移量.
• 这种方式（无数据类型声明）的一个缺点是不能很好的压缩，占用空间也比较大，COLUMN 字节码指令的效率也相对较低.

事务

事务性数据库引擎

• SQLite 是一个事务性数据库引擎.
• 它提供了原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability）的ACID保证.
• SQLite 提供了 2 种可选的事务模式：回滚模式（Rollback Mode）和预写日志模式（Write-Ahead Log Mode, WAL）.

回滚模式（Rollback Mode）

• 开始事务时，SQLite获取数据库文件的共享锁.
• 获取共享锁后，可以随意读取数据库页.
• 如果事务涉及更改，SQLite将读锁升级为保留锁（reserved lock），阻止其他写入者，但允许读取者继续.
• 更改前，SQLite创建回滚日志文件(rollback journal file).
• SQLite将每个将要修改的页的原始内容写入回滚日志，并在用户空间保留更新的页.
• 提交事务时，SQLite将回滚日志刷新到稳定存储.
• 然后获取数据库文件的排他锁，阻止读写者，并应用更改.
• 更新的数据库页刷新到稳定存储后，回滚日志有多种失效方式，具体取决于日志模式：
  • 在DELETE模式中，SQLite删除回滚日志.
  • 因为某些系统上删除文件代价高昂，SQLite也提供了其他日志模式.
  • TRUNCATE模式下，回滚日志被截断而非删除.
  • PERSIST模式下，回滚日志的头部被覆盖为零.
• 使回滚日志失效实际上等同于提交事务.
• 最后，SQLite释放数据库文件的排他锁.

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

• 概念上，WAL模式是回滚模式的反转.
• 回滚模式中，SQLite将原始页写入回滚日志，修改后的页写入数据库文件.
• WAL模式保留数据库文件中的原始页，并将修改后的页附加到单独的WAL文件.
• WAL模式下，事务开始时记录WAL中最后一个有效提交记录的位置，称为结束标记(end mark).
• 需要页时，SQLite在WAL中搜索结束标记之前该页的最新版本.
• 如果WAL中没有该页，SQLite从数据库文件中检索.
• 变更仅仅被追加到WAL的末尾. (即追加写)
• WAL增长超过指定大小会触发检查点，此时WAL中更新的页写回数据库文件.
• 检查点后，WAL文件不会被删除，而是起始部分被后续事务覆写.

WAL模式的优势

1. 增加并发性：读取者可以在写入者将更改提交到WAL时继续操作数据库.
2. 速度：通常更快，因为它需要较少的落盘操作，且写入操作更加顺序. （大概就是 commit 前可以享受内存的性能或者说追加写的性能）

WAL模式的劣势

• 为加速搜索WAL，SQLite在共享内存中创建WAL索引，这提高了读事务的性能，但要求所有读取者必须在同一台机器上.
• 因此，WAL模式不适用于网络文件系统.
• 进入WAL模式后无法更改页大小.
• WAL模式增加了检查点操作的复杂性和存储WAL及WAL索引的额外文件

运行硬件和工作负载的演变

• 硬件的进步和软件需求的变化对SQLite提出了新的挑战.
• 尽管SQLite主要用于OLTP，但它也被用于处理复杂的OLAP查询和边缘计算场景. （好像是对一个移动设备进行 trace 得出的结论）.
• SQLite 的行存储格式和执行引擎对许多 OLAP 操作来说并不是最佳选择

作者这里举了个例子，说现在的科研人员其实都有这样一个广泛的需求，就是在上线大模型前在本地 in-process 的快速跑一些 OLAP 查询，比如比较常见的就是用 pandas 跑一些数据分析任务，但这些库的效率其实是很低的，作者认为 sqlite 这种嵌入式数据引擎在这方面未来大有可为.

性能测试和优化

这一部分主要是一些基准测试，图表比较多也有些无聊，这里摘一些主要结论.

TATP 吞吐测试（OLTP 领域）

• SQLite-WAL 性能：
  • 在两种硬件配置上均显示出最高的吞吐量.
  • 在云服务器上：达到了10,000 TPS，相较于DuckDB的性能优势为：
    • 小型数据库快了10倍.
    • 大型数据库快了500倍.
  • 在树莓派上：
    • 对于小型数据库比DuckDB快2倍.
    • 对于大型数据库快60倍.
• SQLite-DELETE 性能：
  • 比SQLite-WAL慢，但在云服务器上显著快于DuckDB.
  • 在树莓派上：
    • DuckDB对小型数据库的性能略胜于SQLite-DELETE.
    • 对于大型数据库，SQLite-DELETE更快.
• 性能一致性：
  • SQLite-WAL和SQLite-DELETE不管数据库大小如何，都显示出了较为一致的性能.
  • DuckDB的性能随数据库大小增加而下降.
• 一般观察：
  • SQLite的性能归功于其多年来精心调优的事务处理机制.
  • DuckDB，主要为OLAP和ETL工作负载设计，展现出在TATP（事务型）基准测试上的性能明显较差.
• 挖坑：
  • 作者在这里挖了个坑，说俺之后会研究下，这个性能差异是由于实现细节还是系统架构的根本差异.

SSB 吞吐测试（OLAP）

• DuckDB在所有查询中都明显快于SQLite.
• DuckDB在部分查询中的性能优势巨大，快了30-50倍；在部分查询中优势最小，快了3-8倍.
• SQLite在不同查询中的延迟差异较大.
• 在树莓派上，SQLite最快的查询比最慢的快10倍；而DuckDB最快的查询仅比最慢的快3倍.

进一步优化

作者开启编译时选项 VDBE_PROFILE 输出了 VDBE 执行每个字节码指令所消耗的 CPU 周期数. 发现只有两个指令（SeekRowid和Column）占了大多数 CPU 周期：

• SeekRowid 指令在B树索引中搜索具有给定行ID的行.
• Column 指令从给定记录中提取列.

然后分别水了下优化方法：

• 针对第一个问题，发现是 join 效率的问题，解决方法是给 Inner loop 的表上了个布隆过滤器实现了一个 Lookahead Information Pass- ing (LIP)，这样在基准测试场景能避免一些 seekRowid... 另外还有 hash Joins 的方法，但可以预见的内存消耗不可控，抛了.
• 针对第二个问题，作者想了几个办法但由于会担心破坏稳定性，抛了（原话）

Blob 测试

就是测试下二进制文件存储，和 fread/fdatasync 还有 duckdb 测试，感觉比较迷我直接跳了.

一些有意思的信息

1. 最初作为Tcl编程语言的扩展打包，SQLite诞生于对在另一个独立进程中运行的数据库服务器进行调试时的沮丧之情.
2. 据估计，目前可能有超过一万亿个正在使用的SQLite数据库. 据估计，SQLite是最广泛部署的软件库之一.
3. SQLite 是一个真正的工业级别数据库：SQLite 代码是一个 15 万行的单个 C 语言，但测试代码和脚本居然有九千多万行. 每行SQLite代码中有超过600行的测试代码. 测试覆盖库中100%的分支. 测试套件非常多样化，包括模糊测试、边界值测试、回归测试以及模拟操作系统崩溃、断电、I/O错误和内存不足等各种情况的测试.
4. 由于 SQLite 的变态测试覆盖率，给 SQLite 添加功能变得非常惬意，不用太担心对现有功能造成影响.
5. 删除操作比其他语句更加耗费资源，平均每个语句约为4毫秒.
6. 对于排序大量数据，SQLite使用可选的多线程外部合并排序算法.
7. 测试技巧：测试前可以用 SELECT * query populate 以下 buffer pool 以及 测试前可以先预热几秒钟再统计.
8. sqlite 文件格式是美国国会图书馆推荐的数字内容保存格式.
9. SQLite也有广泛的文档和注释，这有助于新开发人员快速理解SQLite的架构.