对照测试回答的是“结果对不对”。数据库还有两类问题,单条语句的对照发现不了:断电之后还剩什么,以及几个进程同时写的时候会发生什么。阶段 27 为 SQLite 格式的文件各写了一个 fuzzer。它们找到两个 bug;修第二个时又引入了第三个,被下一阶段的 fuzz 抓到。
断电模型:只记 fsync,按扇区组合#
真实的断电比“进程在某一行崩溃”残酷:没有 fsync 的写入可能丢失,可能乱序落盘,一次写入还可能只落下一部分扇区。
逐次拦截 write 来模拟太繁琐,tests/crash_fuzz.py 换了个思路:
- 只拦截
os.fsync和os.unlink,记下每个文件上次 fsync 时的内容。 - 断电时,对每个文件比较“上次 fsync 的内容”和“当前内容”,以 512 字节扇区为单位,每个变化了的扇区独立地保留新值或旧值。文件变长或被截断这件事本身也可能没生效。
-shm不持久,随机删掉或保留。- 断电点选在某次 fsync 或 unlink 之前。两次 fsync 之间所有可能的中间状态,都被这个组合覆盖了。
然后让 sqlite3(子进程)和 MiniDB 各自恢复一份拷贝,要求三件事:
- 两边恢复出同一个状态;
- 这个状态完整,并且是最后一次确认的提交或正在进行的那一次;
- 恢复后还能接着写。
fuzzer 本身也要验证:让它“忘记”日志的 fsync,两种日志模式下大多数种子立刻失败。说明它确实能看见丢失的写入。
Bug 1:日志头写得太早#
第一轮 200 个种子里,回滚日志模式有 3 个失败。sqlite3 打开恢复后的文件报 malformed database schema。
断电点都在日志的 fsync 上:数据库文件一个字节还没动,日志却被撕裂了。MiniDB 把“日志里有几条记录”和日志头一起,在写记录之前就写下了,并且只 fsync 一次。断电时日志头落盘了,后面几条记录的部分扇区还是零。SQLite 回放时信任这个记录数,而记录的校验和只抽样每 200 个字节中的一个,于是撕裂的记录通过了检查,零字节被写回了数据库。
SQLite 自己的做法(pager.c 的 syncJournal,synchronous=FULL)是两段:
- 日志头先写 0 条记录;
- 写完记录,fsync;
- 再写入真实的记录数,再 fsync。
热日志的记录数为 0 时,不回放任何页。照做之后,回滚日志和 WAL 各 600 个种子、每个 8 到 10 次断电,没有一个失败。
多进程:用不变量代替逐步对照#
并发的结果取决于交错,没法和单个参考库逐语句比较。tests/concurrency_fuzz.py 让负载只由“可交换、可核对”的操作组成:
- 账户之间转账,总额不变,每笔还记一行日志;
- 计数器自增(upsert);
- 读事务:同一快照里两次求和必须相等、等于总额,自己提交过的转账恰好都看得见,日志的行数不会倒退;
- 并发的 CREATE / DROP INDEX、VACUUM、checkpoint。
6 到 8 个进程,MiniDB 和 sqlite3 交替,每个只记录自己确认提交了的操作。结束后 sqlite3 和 MiniDB 分别打开文件,要求:
- 都认为文件完整;
- 内容恰好等于所有已确认提交之和;
- 同一组查询(包括
sqlite_schema)的答案相同。
还有一条更强的检查:按 SQLite 的语义,这个负载不应该出现任何 busy。写事务以写开始(或用 BEGIN IMMEDIATE),读事务从不升级为写,超时给了 20 秒。
Bug 2:BEGIN 不该马上开始#
刚跑起来就看到:sqlite3 进程从不 busy,MiniDB 进程却时常报“database is locked”,而且全都发生在 BEGIN 之后的第一条UPDATE 上。
原因是 MiniDB 的 BEGIN(DEFERRED)当场就取了读快照,回滚日志模式下还会持有 SHARED 锁。如果别的进程恰好在 BEGIN和 UPDATE 之间提交了,这个快照就过期了,写不了。SQLite 的 DEFERRED 事务要到第一条语句才真正开始;如果第一条是写,它先等写锁、再取快照,所以总是最新的。只执行了 BEGIN 的连接也不挡任何人提交。
MiniDB 照这个语义改了。之后三种存储模式各 50 个种子 × 8 进程 × 400 次操作,一次 busy 都没有。
Bug 3:修 Bug 2 时引入的#
下一阶段拆分 executor 时照例跑了一轮 WAL fuzz,有两个种子失败:
- 一个查询少返回一行;
- 另一个种子里,sqlite3 对 MiniDB 的文件报“2nd reference to page 2”,也就是一页被两棵树引用。
二分到上一阶段的改动之后,缩小出来的序列只有两条:BEGIN; ROLLBACK;。
ROLLBACK 会重新加载 schema。以前事务一开始就有快照,重新加载读到的是一致的页。现在这个事务从没读过,WAL 下的页索引还是旧的,于是读的是数据库文件里还没回填的旧页,schema 里的根页号过时了,下一张新表就复用了一个已经在用的页。
修法很简单:从没开始读的事务,COMMIT 和 ROLLBACK 都没有东西要写或撤销,直接结束就行。
这个 bug 说明了为什么每个阶段结束都要跑全套 fuzz,而不只是跑当前阶段的那个 fuzzer。
对应的决策#
D120(WAL 的锁协议)、D122(断电模型与并发差分)。
代码、测试与文中引用的设计决策(D 编号,见 DECISIONS.md):github.com/ayaya114514/MiniDB ↗;浏览器里直接试:MiniDB Playground ↗。