今日三荐：字节码虚拟机、嵌入式键值库与压缩编解码

1. gravity：源码走到字节码要过几趟

为什么今天看

最值得拆的机制

• 词法器零拷贝。 它逐字符扫过源码，产出的 token 只记下自己在这段源串里的偏移，既不复制也不修改输入缓冲区。4
• 解析器用 Pratt 方法。 每条语法规则带一个前缀处理函数、一个中缀处理函数、一个优先级和一个是否右结合的标志，+ 与 || 的绑定力就写在同一张表里。4
• 解析之后还有几站。 语法树先过两遍语义检查，再生成中间表示、跑一遍优化器，最后才是代码生成；src/compiler/ 里每一趟各占一个文件，按文件名就能排出顺序。4
• 字节码在一台栈式虚拟机上执行。 运行时的值是一个带类型的联合体，闭包捕获的变量、fiber 和类实例都由一个标记清除收集器管理。4 README 写明闭包的思路取自 Lua，fiber 和部分 GC 参考了 Wren。5
• 规模是数得出来的。 本机统计：编译器 11174 行、运行时 6781 行、共享部分 4790 行、可选的 Math/File/JSON/ENV 模块 2091 行、命令行 525 行。5 编译器和虚拟机加起来让可执行文件增大不到 200 KB。5
• 三元运算符那个属于代码生成。 分支是一个裸的局部变量时，值留在它自己的寄存器里，没有搬进结果寄存器的指令，而表达式去取 else 分支的寄存器。1
• 另外三个都在运行时。 List.sorted() 与 List.map() 把结果列表的容量覆写成源列表的容量，越出分配区写；String 的 UTF-8 处理按首字节推测序列长度却不检查剩余字节，还能让 String.split("") 永不前进；JSON.parse 不检查字段的 JSON 类型就去读联合体成员。1

复现难度：低

最小上手路径

git clone --depth 1 --branch 0.9.9 https://github.com/marcobambini/gravity.git
cd gravity && make
./gravity -i 'return 2 + 3'

RESULT: (INT) 5 (in 0.0002 ms)

./gravity -t test/unittest

Total Tests: 356
Total Successes: 356
Total Failures: 0
Result: 100.00 %
Time: 1519.9628 ms

今晚练习

1. 把那处代码生成 bug 复现出来。在 0.9.9 上跑 ./gravity -i 'func f() { var foo = 7; return true ? foo : 1 } return f()'，得到 7。6 把仓库切回 0.9.8 重新 make，同一条命令给出的是 true，也就是条件本身；把两边的顺序反过来写，0.9.8 又会吐出分支里那个变量的值。
2. 把编译和执行分开：./gravity -c demo.gravity 写出一个 841 字节的 gravity.g，再用 ./gravity -x gravity.g 执行它。5
3. 用递归和一个循环各量一次虚拟机的速度：本机 fib(28) 返回 317811，耗时 40.3 毫秒；一个 100 万次的累加循环是 43.7 毫秒。
4. 按架构文档第 2 节列出的顺序，从 src/compiler/ 的第一个文件读起，读完一趟就对照一次同名的 .c 文件。4

版本动作与限制

• 装 0.9.9，MIT 许可。5
• 如果宿主程序会执行外来的脚本，或者会对不可信输入调用 JSON.parse，这一版更值得换上去。1
• 语法不是 C 系。循环写 for (var i in 0..<5)，写成 C 风格的 for (init; cond; incr) 会报 Expected in but found ;。
• 交互式解释器还没实现，直接运行 ./gravity 只会打印一行 REPL not yet implemented.。

2. redb：一次提交落在磁盘的哪两个槽里

为什么今天看

最值得拆的机制

• 数据放在写时复制的 B+ 树里。 已提交的页永不原地修改：先分配新页，在新页上改完，再构造一棵引用新页的树。8 README 把这份设计列为受 lmdb 启发。9
• 文件从一个 512 字节的超级头开始。 里面是 64 字节的头部和两个各 128 字节的提交槽，之后才是数据区域。8
• 最新提交在哪个槽，由一个字节决定。 头部的 god byte 第一位记着最新提交在槽 0 还是槽 1，第二位要求打开时先做修复，第三位说明主槽是两阶段提交写下的。8 redb 依赖「这是一个字节」来完成原子提交。8

512 字节超级头
├─ 数据库头部（64 字节）
│   ├─ 魔数 9 字节（'redb' + 0x1A 0A A9 0D 0A）
│   ├─ god byte 1 字节
│   │   ├─ bit 0  primary_bit：最新提交在槽 0 还是槽 1
│   │   ├─ bit 1  recovery_required：打开时要先走修复
│   │   └─ bit 2  two_phase_commit：主槽用两阶段提交写入
│   ├─ 页大小 4 字节、区域头页数、区域最多数据页、完整区域数……
│   └─ 补齐到 64 字节
├─ 提交槽 0（128 字节）
│   ├─ 文件格式版本 1 字节
│   ├─ 三个布尔：用户根页 / 系统根页 / 空闲树根页是否非空
│   ├─ 用户根页 8 字节 + 校验和 16 字节 + 表数量 8 字节
│   ├─ 系统根页 8 字节 + 校验和 16 字节 + 表数量 8 字节
│   └─ 最后一次提交的事务 id 8 字节 + 槽校验和 16 字节
└─ 提交槽 1（128 字节，与槽 0 同布局）

• 默认的持久提交只要一次 fsync。 先把数据、校验和与单调递增的事务 id 写下去，再翻转主位并 fsync。8 崩溃后要检查事务 id 是否更大、校验和是否全部有效，任一不成立就换另一个槽。8
• 想防「能控制落盘顺序的对手」时要显式换成两阶段提交。 它先把新副本写完 fsync，翻转主位字节后再 fsync 一次，代价是两次落盘；设计文档解释了默认策略为什么在理论上可以被攻击。8
• 校验和是一棵非加密的 Merkle 树。 每个页用 XXH3_128 记一份校验，一个只写了一半的事务能在重启时被发现并回滚。8
• 读事务靠 MVCC 隔离。 读事务私有复制一份 B+ 树根并登记，写事务释放的页先入队，等可能引用它的读事务结束才复用。8
• 存档点复用同一套结构。 它另外存下页分配器的状态，按 4 KB 页算每 1 GB 的值约 64 kB，回滚时把这份快照和当前已分配的页做一次 diff。8

复现难度：中

最小上手路径

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
cargo new kv && cd kv && cargo add redb@4.4.0

use redb::{Database, Durability, TableDefinition};
use std::time::Instant;

const TABLE: TableDefinition<u64, u64> = TableDefinition::new("data");

fn main() -> Result<(), redb::Error> {
    let db = Database::create("demo.redb")?;
    let t0 = Instant::now();
    for i in 0..2000u64 {
        let mut txn = db.begin_write()?;
        txn.set_durability(Durability::None)?;   // 换成 Durability::Immediate 再跑一次
        {
            let mut t = txn.open_table(TABLE)?;
            t.insert(i, &i)?;
        }
        txn.commit()?;
    }
    println!("2000 single-key commits: {:?}", t0.elapsed());
    Ok(())
}

2000 single-key commits, Durability::none: 17.073244ms
2000 single-key commits, Durability::immediate: 2.44252294s

今晚练习

1. 量一次持久化的价格。上面那段循环跑两遍，本机 None 是 17 毫秒，Immediate 是 2.44 秒，差大约 150 倍，差的就是那一次 fsync。
2. 试一次存档点。在一个写事务里先调 txn.ephemeral_savepoint()?，再打开表追加 1000 个键，然后回滚并提交；本机的表长度从 2000 回到 1000。顺序反过来——先打开表再创建存档点——拿到的是 SavepointError::InvalidSavepoint，所以存档点要在事务「变脏」之前创建。
3. 看一次 MVCC。先开一个读事务读键 500，再提交一次把它改成 999999，然后回到那个旧读事务里读同一个键：本机旧事务读到 500，新事务读到 999999。8
4. 读设计文档里「数据库修复」那一节，分清 quick-repair 和 full repair 的分界线在哪。8

版本动作与限制

• 装 4.4.0，MIT 或 Apache-2.0 任选一条。9
• 升级要留意两处行为变化：check_integrity() 不再在「一个把文件变大的事务被中止」之后误报「已修复损坏」，页缓存在写负载下不再无界增长。7
• NICHE 会换掉类型本身：给一个类型声明 niche 就等于换掉它 Option 的编码，声明前后的 Option<T> 不是同一个类型，用旧类型写过的表再打开会报 TableTypeMismatch，而不是被误读。7
• 限制：默认只有一个写者，多进程共享要开 experimental-multiprocess 特性另选模式。8 5.0.0 已经在 CHANGELOG 里排着，内容是 no_std 构建和 range 系列 API 的签名调整。10

3. klauspost/compress：把重复折叠掉

为什么今天看

最值得拆的机制

• 一套库里放了一排编解码器。 zstd（纯 Go 的 zstandard）、S2（Snappy 的高性能替代）、能替换标准库同名包的 flate/gzip/zip/zlib、snappy、lzw，以及只做熵编码的 huff0 与 FSE。14
• flate 按等级分成了三套实现。 等级 1 到 6 走 newFastEnc，每个等级一份 level1.go 到 level6.go，各自带着不同的哈希表；等级 7 到 9 换成懒匹配那条路径；负数等级用来指定自定义窗口大小。14
• 三个数字就决定了压缩率和工作量。 等级 1 是 BestSpeed，9 是 BestCompression，默认值 -1 实为 5。14
• 构建标签能整包关掉两条捷径。 nounsafe 关掉所有 unsafe 用法，noasm 关掉全部汇编。14
• 模块版本也可以被撤回。 go.mod 里有一条 retract，撤掉 v1.14.1 到 v1.14.3 和 v1.18.1，每条都带一个 issue 或 PR 链接。15
• 这一版顺手修了个小坑。 zip 的 ReadDir 现在拒绝名为 . 的条目，否则 fs.WalkDir 会一直转下去；同一批改动里还有 S2 对短索引块的拒绝。12

复现难度：低

最小上手路径

go mod init bench && go get github.com/klauspost/compress@v1.20.3

// 和标准库同名同形：只换 import 路径和包名
import kgzip "github.com/klauspost/compress/gzip"
import "github.com/klauspost/compress/zstd"

w, _ := kgzip.NewWriterLevel(&buf, 6)   // 标准库这里是 compress/gzip
w.Write(data)
w.Close()

enc, _ := zstd.NewWriter(nil, zstd.WithEncoderLevel(zstd.SpeedDefault))
comp := enc.EncodeAll(data, make([]byte, 0, len(data)/3))

今晚练习

1. 把手上项目里的 compress/flate 换成这个同名包再跑一次自己的基准。本机的 gzip 等级 6 从 151.5 毫秒降到 126.9 毫秒，解压从 71.0 降到 56.3。14
2. 换语料再量一遍。同一份程序跑日志、JSON、CSV 和二进制，压缩比会拉开很大差距；19.1 MiB 的 Go 源码落在 4.6 倍到 7 倍这一档。
3. 比一比 SpeedDefault 和 SpeedBestCompression：本机后者慢 6 倍，压缩后只小 20%，这就是那三个数字要你做的取舍。
4. 读 flate/level1.go 和等级 7 以上的实现，看最快那档在找重复串时省掉了什么。

版本动作与限制

• 装 v1.20.3，许可 BSD-3-Clause，版权分属 Go Authors 与 Klaus Post。14
• 版本号大小不代表包含关系。v1.20.2 与 v1.20.3 的 tag 各有自己的祖先链，按版本号推断「后者包含前者」在这里会出错。1112
• 官方公告只把 v1.20.2 写成修补版本，受影响的是 v1.20.1 及更早；两个版本的说明里能看到同一批修复条目。1113
• 这一版的性能改动集中在 arm64，x86_64 上要自己量；本机量到的是 zstd 相对 gzip 的压缩和解压差距。12
• 限制：项目声明只支持当前的 Go 版本和前两个版本。14 撤回掉的四个版本号也说明，装之前值得看一眼 go.mod。15

怎么选今晚的第一条路径