CMU15-445/645 小结

花了一个月的时间学完了 CMU15-445/645,其实这门课早就列入计划表里了,我一直在等 FALL 2018 project source code 开源,但是一直不开源, 发邮件问了下才知道不会开源了,最后是看的 FALL 2018 视频做的 FALL 2017 project

课程

这门课基本把关系型数据库的方方面面都介绍了,当然都是基础内容,其实只看 video 不做 project 帮助也很大,因为数据库的书 如数据库系统概念、数据库系统实现,如果不是有数据库方面经验的人看起来会很困难,有 video 看起来会容易很多。

我不熟悉关系型数据库,就连 sql 都很少写,所以这门课对我帮助蛮大的。除了向我普及了关系型数据库的知识外, 最大的收获是帮我整合了之前关于 kv 存储积累的一些理论,因为 kv 数据库可以说是关系型数据库的阉割版本,用到的理论或多或少都和关系型数据库的理论相关。

Project

project 是用 sqlitevirtual table 机制重写后端设计的,sqlite 的前端会解析 sql、生成执行计划,最后调用 virtual table 的后端接口完成操作。project 就需要实现后端的 Buffer Pool ManagerConcurrency B+ Tree IndexLock ManagerLog System,模块划分很清晰,但也导致了 project 间联系不大,建议做之前把整个项目先过一遍, 看下 virtual table 的实现是如何使用这几个模块的。

virtual table 提供的操作都是 point 增删改查,索引也只有全部匹配且是 point 查找时才会用到,所以对后端的功能要求不高。project 整体比较简单,代码量也不大, 想通过 project 附带的测试是分分钟,但想要正确实现的话还是要花点时间补充额外测试的。美中不足的是 project 有些地方感觉设计和实现上有些问题,比如:

  • TablePage::UpdateTuple() 没更新 MarkDelete tupleoffset,导致我补充测试时一直 assert 报错。
  • NEWPAGE 类型的 LogRecord 应该缺少了 current page id,而且 DiskManager::AllocatePage() 只是分配 page id,数据库关闭时文件大小可能会比需求的小,但是 DiskManager 没法正确处理这种情况, 所以我增加了 truncate()

还有一些比较小的问题或者和测试无关的问题就不说了,比较遗憾的是 project 没有前端相关的,感觉实现各种 operator 还是蛮有趣也挺有难度的。

project 还是能学到一些东西的,比如这是我第一次写 B+ tree,也是第一次用 C++ 写点东西。很坑的一点是发现 youcompleteme(libclang7.0)template 的支持不太好, 导致无法推断 template 内部的 auto 类型,也就无法自动补全,用全类型声明才可以,我还以为是自己的 Vim 配置有问题,搞了一天。

boltdb

学完了这门课,发现之前对 boltbd 的理解有些偏差,在这里更新下。

B+ tree

B+ tree 在实现上有很多需要关注的,最基本的有:

  1. key 是定长还是变长,leaf node 存数据还是存数据的地址。node 一般是以 page size 为单位,变长 key 或者存的数据变长会导致 node 变长,分裂和合并的标准也就不是 key 的个数, 而是 fill percent,可能还会需要 overflow page,当 key/value 太大一个 page 存不下时也需要 overflow page。定长 node 还有个实现上的好处是可以直接把 page 转换为 node, 变长就需要 marshal/unmarshal。当然可以通过只存 key 和数据的地址变为定长 node,但是多了通过地址取数据的流程,对于纯内存的 B+ tree 而言 cache locality 变差; 对于持久化的 B+ tree 而言会增加磁盘 I/O
  2. leaf node 一般会有 sibling 指针,为了方便 range scan

boltdbB+ tree 一些实现细节如下:

  1. keyvalue 都是变长,所以是按照 fill percent 分裂和合并,同时有 overflow pagepage 和变长 node 的转化就需要 marshal/unmarshal,但 page 的存储格式方便了二分查找 key
  2. 之前的文章说 branch nodekey/value 个数相同不太对,因为 branch node 的第一个 key 不起作用,所以一般情况下 branch nodevaluekey 多一个。但是在 node 分裂/合并时需要 计算从 parent node 中插入/删除的 key,这时候就可以用第一个 key 保存分裂/合并时的 key,不需要再计算了,当然这里还可以做 suffix truncation 的优化。
  3. leaf node 没有 sibling pointer,所以 boltdb 查找时用栈保存了查找路径,用于实现 range scan

有本书 Modern B-Tree Techniques 介绍了 B+ tree 实现上的优化和细节,以后有时间可以看一下。

Transaction

之前文章关于 boltdb 事务的也不太对,之前是说用 MVCC + COW 实现事务的 ACID,准确的说是用 Shadow Paging 实现的 AD,用 Shadow Paging + RWLatch 实现的一写多读的 IShadow Paging 通俗来说就是每当修改时就 COW 写到新的 page,在 commit 时整个切换到新的 page,相当简单的就实现了 ADcommit 切换成功最新的数据已经落盘,commit 失败不会切换到新 page,也 不会影响现有数据。Shadow Paging 采用的是 NO-STEAL + FORCE 策略:

  • NO-STEAL:不允许 uncommitted 数据覆盖磁盘上 committed 数据。(有时会说只有 commit 时才能写数据,感觉不太准确,比如用 Shadow Paging 的话提前写到新 page 也没影响,只要不覆盖 committed 数据就好)。
  • FORCEcommit 时要把所有更新的数据写到磁盘上。

boltdb 的实现就是如此:commit 时进行 B+ tree 的分裂和合并,然后所有 dirty page 写到新的 page,最后把 metadata 写到新的 page 然后切换到新的 B+ treeNO-STEAL + FORCE 的局限性很多, 以 boltdb 的实现为例:

  • page 修改很小也需要写入整个 page,写放大较大,而且因为新分配了 page,所以从 leafroot 的所有 page 都会变为 dirty(因为修改了 child page id),写放大就更大了。
  • boltdbmmap 做读的 buffer pool managernode 中的数据指向的是 mmap 的数据,可以减少内存使用。但 commit 时不是将 dirty node 一个个写入磁盘,而是先给每个 dirty node 分配 buffer + page id, 然后对 page id 排序再写入,目的是减少随机 I/O,但是极大增加了内存使用,很容易导致 stall
  • Shadow Paging 需要 GC 回收之前的 pageboltdb 是用 freelist 维护可以复用的 page,虽然上面先排序再写可以减少部分随机 I/O,但是仍然不可避免。而且没有 compaction,文件大小会一直增大。
  • 没法做 page 内的并发,因为若不同事务使用了相同的新 page 会导致 commit 未提交的数据,若不使用相同的新 page 又会丢失已提交的新的数据。而且 boltdb 是用固定的前 2page 保存 metadata, 这也导致了没法做写写并发。

boltdb 提供的是一写多读的 I,一写是用 W-Latch 保护的,而 Shadow Paging 天然支持了读写并发,只要读事务访问到的 page 没有被新的 page 覆盖即可, 所以 boltdbfreelist 中维护了每个 tx 释放的旧 page id,只有当所有读事务的 txid 都大于它时才能释放。(其实就相当于维护了多个版本的 B+ tree)

Shadow Paging 相对应的就是 STEAL + NO-FORCEWAL,好处就是顺序写 log 即可,性能高,写放大也小;坏处是恢复较慢,要有 checkpoint 机制来清理 log。 对于 leveldb 这种没事务,或者说只支持单个必定成功的读写操作事务的存储引擎来说,只需要 redo log 即可,更一般而言,还需要考虑 data pagelog 的新旧关系, 还有 log 的类型等,具体可以看 ARIES

还有一点值得一提,因为我之前都是搞 kv 的,所以觉得只用 MVCC 就能实现 concurrency control,其实它只是减少读写冲突,但对于操作必定成功的 kv 来说,事务就是单个读写,所以 MVCC 就能保证隔离性。 更一般的 concurrency control 指的是 T/O, OCC,2PL 这种,数据库如果使用 MVCC 仍然需要前面的 concurrency controlMVCC 主要能解决读写冲突、提高并发度并提供只读事务的 snapshot isolation

后续

Andy 老师很有趣,听说号称数据库匪徒,后面会继续开坑他的 CMU 15-721。课上有三个场景印象深刻, 一是他介绍自己时说只关心 2 件事:他的妻子和数据库;二是贴了别人骂他的邮件还挂了中国版 youtube(bilibili) 搬运他的视频;三是说要把永远不要在数据库中用 mmap 刻到他的墓碑上。

分类:

更新时间: