Anri’s blog

/home

/posts

/categories

/tags

Home/Posts/ 15445 复盘

15445 复盘

Buffer、锁并发、MVCC

前言 #

简历上写了 15445，带着这半年的知识看一遍，还是有新东西的，之前写的 blog 没有营养，所以再写一篇复盘 blog

这次复盘侧重扩展与辨析，不会深入实现细节

一 | Buffer Pool 与 OS Cache 的比较 #

简单过一下实现：

  • LRU-K 针对范围读的效果，比 lru1 更好
  • 汰换、refcount、raii，负责自动管理资源
  • 数据存在固定的 frame 里，其实是将文件内容映射到内存中，供线程读写，再通过 flush 完成同步

这里只讨论一个高频问题，直接说结论

  • 事务、WAL 的存在，使得写盘时间需要严格控制，交给 OS 会破坏安全性

  • 性能上，db 可以针对性进行优化，比如汰换策略，预热缓存

抽象层不同，导致我们可以控制的自由度也不同，这就是不使用 mmap 的理由

这里带一下 mmap 的流程：

  • 触发中断，陷入 syscall
  • 分配对应的虚拟地址，加入查询表
  • 不分配物理地址映射，等待后续触发 page-fault

触发 page-fault 后：

  • 查表得知存在 mmap 映射
  • kernel 将文件读入到 page cache，将 va 直接映射到缓存上的地址
  • 所有通过 mmap 的 IO，都是在 page cache 上操作

这里意外补充了一个 OS 的点，虚拟内存，是虚拟地址到物理地址的映射，不会映射到磁盘， mmap 也是靠 page cache 实现的，之前读 LevelDB 没有意识到这一层

二 | B+树的 Crabing 原则 #

当时写 lab 没考虑并发优化，直接用了从上到下的悲观锁，理解不到位

要最大限度地获得并发性能，我们就要避免多余的 lock

Crab 的动机：在一次 IO 流程里，如果一个 node 不可能分裂、合并，那么它的父节点也可以认为是安全的，此时可以释放祖先节点上的锁

这样，我们拿锁时，可以逐个检查是否安全，及时释放

加锁顺序有一个细节，需要先获取新锁，再释放旧锁

如果顺序颠倒，会出现一个中间态，两个锁都不被我们持有，这样会导致其他事务介入，破坏隔离性

三 | 迭代器的加锁问题 #

本文的主要灵感来源，这就是饺子醋了

B+ 树的迭代器，在 leaf 层上进行线性扫描

假设这样一个场景：

  • 线程 A 申请了一个迭代器，读到 leaf 3，持有 3 的读锁
  • 线程 B 正在插入，恰好在 leaf 4 上发生了分裂，持有 4 的写锁

现在 A 执行 next()，请求 4 的读锁 同时，B 进行分裂操作，需要修改 leaf 3 上的 next 指针，请求 3 的写锁

此时发生死锁

这本质是两种语义的冲突：迭代器从左向右拿锁，分裂从右向左拿锁

一个明显的解决方案是，让其中一方暂时放弃自己的锁，给另一方 ”让路“

B 让路，暂时释放 leaf 4 的锁

那么，A 将会更进一步，读到 leaf4，但此时 4 已是被 B 修改过的 ”脏页“，处在分裂的中间态，读取不安全

如果让 B 先修改 next 指针，让路给 A，再进行实际的分裂操作呢？仔细想想也不行，先斩后奏，可能 B 在分裂途中就宕机了，不安全

退一步，分裂语义应该是 atomic 的，最后的替换也同样

这里我想到 RCU 的做法，让 B 在一块新空间上写，而不在 4 上原地修改，完成时，再一次性替换 next 指针就可以了

这是 shadow-paging 的想法

但这需要引入磁盘上的 GC

当 B 完成分裂后，旧的 leaf 4 就失效了，但 A 仍有读取 4 的可能，所以不能逐出 buffer，也不能直接删除磁盘上的 page

此时需要将 leaf 4 存到一个负责 GC 的数据结构，与 buffer 进行交互，当 buffer 中的 pin_count 归零，逐出 page 时，就可以通知 GC 管理器了

这还不安全，pin 为 0 并不代表后续没有引用了，如果另一个 C 在 B 之前启动，它还是可能持有 leaf4 的指针，只是还没来得及载入 buffer

因此我们的 GC 策略会更保守，需要以 B 为划分点，等待旧 Epoch 的线程都结束后才能回收资源

可以预见到，让 B 这样一个写线程让路，引入的额外复杂度是巨大的

A 让路，暂时释放 leaf3 上的锁，随后通过 peek 回到 last_key

相比之下，让 A 这样一个读线程让路的代价就很小了：

  • B 原地修改
  • 重新 peek 的语义是自洽的
  • 可能会读到其他事务的写

bustub 中，没有考虑上面 GC 的问题，应该是简化了这部分逻辑

能通过测试，主要是我加的锁太多了，没出现这种并发情况

所以还是有 bug 的，delete 时，需要按照 “删除引用 -> 删除page” 的顺序来，这样就从上层规避了 ABA 问题

要增加这部分逻辑，我们从问题入手，删除之所以不安全，是因为旧线程会从旧的引用读出损坏数据

因此我们有两种解决角度：

  • 延迟删除，推迟到事务 commit 时再删除，就不会读出坏数据
  • 破坏旧引用，在 buffer 中标记为 delete，迫使旧线程触发读失败，重启事务，这样读到的引用就是新的了

简单说一下，除此之外的方案：

  1. 协议限制，锁获取的顺序，必须从左到右，这样 B 需要分裂时，会从根节点开始重试，重新获取左边 leaf 的写锁
  2. 乐观读锁，迭代器不加 read 锁，在 page 上增加 version 字段，每次先读数据，比较前后 version 是否一致，不一致说明有变化，就重试读，从根节点开始 seek
  3. B-Link Tree 是B+Tree的一种变形，引入了high key和指向右兄弟节点的link指针，通过这两个数据的引入，在并发查找时可以作为节点是否发生变更的根据（没有学，TODO）
  4. MVCC 并发读，不过空间放大严重

四 | Buffer Pool 的定位 #

意外谈到了 GC，我才发现对于 Buffer 的理解不是很到位

之前觉得 buffer 仅仅起到 cache 加速读的作用

Buffer 更多的作用，是为 DB 和 File 提供一个在内存上交互的“中间层”，否则我们是不可以直接操作磁盘文件的

Buffer 就是文件在磁盘中的 “映射”，我们用 Flush 来同步这种映射，将 db 的修改写回到磁盘，cache 只是它的一个副作用

五 | MVCC #

回到并发控制的话题

另一种方法就是 MVCC，为每次修改都保留快照，同时为事务分配事件戳，这样从可见度上就屏蔽了临界区的问题，也就不需要使用锁

这样 A 可以读时刻 3 的版本，B 可以写时刻 4 的版本，二者互不冲突

另外，这同样引入了 GC，需要定期清理那些过期的 version

我们先讨论布局方案，两种：

  • 全量复制
  • undo log

前者，每次都完整的复制出一个 page，仅仅维护 version 指针列表即可，缺点是写放大过于明显

后者，每次只记录增量变化，读出时，再遍历 undolog 进行即时回溯，缺点是增加了读开销

这里和 Leveldb 呼应了

在 LSM 树中，SSTable File 级别的 MVCC 就是前者，依靠 VersionSet 来进行访问

而 Table 内部的 MVCC 可以同时以两种方法解读，我认为记录 timestamp 的方案更接近后者，需要扫描很多 log 才能得出读结果

File 层面的变动频率非常小，因此采用 copy 方案是可以接受的

另外，针对 delete 操作，copy 方案会选择用墓碑标记，而 undo 方案也会做明显记录

我认为 MVCC 不适用于 B+ 树的场景，粒度太小了

Bustub 的 P4 也只是在 Table 上增加 MVCC，使用 Undo 方案

实现分几步：

  • 对比新旧 data，生成 undo log
  • 事务管理中，增加 version 时间戳的控制
  • 访问数据时，应该加一层带有 version 的抽象，屏蔽底层的 undo log
  • 简单的 GC，用 watermark 标记应该回收的 undo log

另外注意存在 “write-write” 冲突，也就是两个事务，同时对一个 version 做修改的情况

undo log 是针对数据的，在可见性上是被所有事务共享的，这也就导致，一个事务可以看到另一个事务的写，破坏了 MVCC 所提供的快照隔离

遇到这种冲突，应该选择 abort，重试事务

为什么会出现写写冲突呢？

我认为是 snapshot 级别的限制，快照本身就是只读的副本，我们仅仅是借用 MVCC 的壳子来实现这种隔离

而写写冲突，在同一个 snapshot 上做修改，就像 git 分出了两个 branch，但是 snapshot 是不允许 merge 的

因此我们才要 abort，将 snapshot 流变成线性的

为什么我在 Leveldb 没有想到这个问题呢？原来 Leveldb 是不支持事务的

另外，bustub 在实现算子 MVCC 时，还需要考虑与 index 的交互

B+ 树存的是 key 到 RID 的映射，而 MVCC 是针对 RID 内容的，不影响 B+ 树

24fall 的 P4 ，Task3 实现 RID 层的 MVCC，而 Task4 就增加对 index 的支持，这样 index 就不是映射到 RID 与单一地址了，而是映射到 RID 与其对应的 version entry

这就与 bustub 本身的 table 数据布局强相关了，不懂但不关键，这里不展开了

当时写 P4 已经是八月底了，要应对 bustub 的 tuple、table 等原有的石山对象，阅读难度很大，越写越烦躁，就直接上 vibe-coding 了，错过了对 MVCC 本身的思考

不过也见识到了 llm 在复杂系统中的上限，需要手工调教 + review 才能工作，对我而言，它的优势区间还是在 grep 串联上下文这一块

六 | 查询层 #

P3 的内容，我不是很喜欢，过一下各种算子的实现，当常见八股准备了

Reference

SQL 由四个模块解析：

  • parser，语法分析
  • binder，绑定到具体对象
  • planner，生成算子构成的查询树
  • optimizer，优化查询树

这里贴一下 table 布局的实现，读过 leveldb 后也理解了，值得注意的是，这里的 Table Page 是定长的，因此从两头向中间增长

  • Scan 算子调用 TableIterator 进行扫描
  • Insert 直接 append Tuple
  • Delete 采用墓碑删除
  • IndexScan 调用 P2 实现的 Index 迭代器
  • NestLoopJoin，双重循环实现，可以用一层 index 优化复杂度，也可以以 block 为粒度，减少 IO 次数
  • HashJoin，一边建hash表，另一边计算 hash 值，查表
  • 聚合算子，用 hash 实现
  • sort、limit、fliter、top-n
  • 对于外部归并排序，我们需要将中间结果存到 SortPage 上，然后用 MergeIterator 一轮轮归并

Nest 、Hash 、MergeSort 三种 Join 的对比

Nest：

  • 两个表，一大一小，小表存在内存里，只需 IO 大表
  • 可利用 Index 减少复杂度
  • 非等值 Join
  • 如果没有优化，复杂度非常高

Hash：

  • 两个大表，建表完成后是线性复杂度
  • 等值 Join
  • 缺点：输出结果是乱序的，不利于后续处理
  • 另外 hash 表 也占用了额外的内存开销

MergeSort：

  • 两表分别排序，然后双指针扫描
  • IO 开销巨大，但输出天然有序，方便后续处理

bustub 采用火山模型，从根节点 pull 数据

这种 pipeline 的写法节省内存，但带来了虚函数的开销，也不利于 CPU 乱序执行的分支预测

刚从编译原理中学了 OOC 的对象布局，虚函数意味着每次都要根据 id 查 dispatch 表，增加指令开销

其他方案：

  1. 减少继承，用模板或者宏编程，避免编译产生额外的胶水指令
  2. batch 化，每次 Next() 返回一批数据，减少频率，也可以利用 SIMD

三种执行模型：

  • 火山模型：流水线式
  • 向量化模型：batch 流
  • 代码生成：根据 SQL 动态生成中间代码，直接编译到机器码

火山模型一次Next()吐出多个 Tuple， 与向量化模型的区别？

后者的数据在空间上更加集中，对 Cache 友好，可以使用并行指令，前者不可以

七 | 2PL 与隔离级别 #

往年的并发控制都是 2PL 实现，24fall没有这个，当新东西学了

2PL 要求只能有 “增长” 和 “减少” 两阶段，以此保证一致性

这里的 Lock 与平时说的 Lock 要区分开，针对事务的逻辑锁叫 Lock，针对数据的物理锁叫 Latch

要实现并发控制，我们需要建立一个统一的逻辑 Lock 管理器，为各个算子提供服务

Lock 是针对具体的 table 或者 row 对象的，粒度不同

假设，A 线程给 table 1 里的 row 2 加读锁，此时 B 打算给整个 table 1 都加锁

如果 B 只检查 table 锁，那么他就认为这里是安全的，忽略了下面还在运行的 row 锁

因此我们引入“意向锁”，加 row 锁时，也会在 table 上加锁，标记底层存在 row 锁

这是“自顶向下”的加锁协议

Lock Manager，采用队列处理各个事务的 lock 请求，以此控制隔离级别

一个线程可能先获取 read lock 又获取 write lock，这需要两次重复请求，针对这种情况，我们增加了 ”锁升级” 功能，允许 读锁 原地升级成 写锁

通过队列，我们建立了 “等待关系”，即 事务 A 在等待 B 释放某个锁，以此我们可以建图，进行死锁检测

四种隔离级别：

read uncommited：

  • 不加锁，B 可以读到 A 的脏写

read commited：

  • 读数据，加 S 锁，读完数据立刻释放
  • 写数据，加 X 锁，一直到事务结束
  • 解决”脏读“，在 A 写入完成前，B 不可能获取到 S 锁
  • 存在”不可重复读“，释放 S 锁后缺乏保护，A 可以修改 B 已经读过的数据，提交后释放 X 锁，此时 B 可以重复读到 A 的写入

repeatable read：

  • 读数据，加 S 锁，直到事务结束
  • 这样 A 直到 B 结束才能获取 X 锁
  • 存在“幻读”：B 读不到 A 原地修改的数据，但可以读到 A 新插入的数据（不知道新数据的存在，因此也没办法加锁保护）

serializable：

  • 对整个 Range 加锁，不允许插入数据
  • 解决幻读，但性能差

：说说 ACID，其中 C 和 CAP 的 C 有啥区别。ACID 分别通过什么技术来实现

先回答 C

C 是一致性，单机语境下，C 是指两个相关的数据对象，在逻辑上是否一致，对外的行为表现，是否是自洽的

而在分布式语境下，C 单纯指不同机器上的数据是否同步，往高了说，其实也是对外的行为表现，是否自洽

C 是一个需求属性，用于证明系统是正确的

A 是原子性，用 Undolog 实现 commit or rollback

I 是隔离性，并行事务不应该感知到彼此，利用并发控制（2PL 与 MVCC）实现

D 是持久性，也就是崩溃恢复能力，用 WAL 实现

总结 #

以上，借着 bustub 的底子，大致串联了一下数据库的知识体系

不谈代码，跳出实现来谈概念和取舍，感觉还是很舒服的，写完这篇复盘也增长了不少自信，希望一切顺利

TODO:写偏斜（Write Skew）与丢失更新（Lost Updates）

←
分布式论文阅读 II
TinyKV 复盘
→
back to top