CMU15-445/645 小结
花了一个月的时间学完了 CMU15-445/645，其实这门课早就列入计划表里了，我一直在等 FALL 2018 project source code 开源，但是一直不开源，
发邮件问了下才知道不会开源了，最后是看的 FALL 2018 视频做的 FALL 2017 project。
课程
这门课基本把关系型数据库的方方面面都介绍了，当然都是基础内容，其实只看 video 不做 project 帮助也很大，因为数据库的书
如数据库系统概念、数据库系统实现，如果不是有数据库方面经验的人看起来会很困难，有 video 看起来会容易很多。
我不熟悉关系型数据库，就连 sql 都很少写，所以这门课对我帮助蛮大的。除了向我普及了关系型数据库的知识外，
最大的收获是帮我整合了之前关于 kv 存储积累的一些理论，因为 kv 数据库可以说是关系型数据库的阉割版本，用到的理论或多或少都和关系型数据库的理论相关。
Project
project 是用 sqlite 的 virtual table 机制重写后端设计的，sqlite 的前端会解析 sql、生成执行计划，最后调用 virtual table 的后端接口完成操作。project 就需要实现后端的
Buffer Pool Manager、Concurrency B+ Tree Index、Lock Manager 和 Log System，模块划分很清晰，但也导致了 project 间联系不大，建议做之前把整个项目先过一遍，
看下 virtual table 的实现是如何使用这几个模块的。
virtual table 提供的操作都是 point 增删改查，索引也只有全部匹配且是 point 查找时才会用到，所以对后端的功能要求不高。project 整体比较简单，代码量也不大，
想通过 project 附带的测试是分分钟，但想要正确实现的话还是要花点时间补充额外测试的。美中不足的是 project 有些地方感觉设计和实现上有些问题，比如：
TablePage::UpdateTuple()没更新MarkDelete tuple的offset，导致我补充测试时一直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 在实现上有很多需要关注的，最基本的有：
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。leaf node一般会有sibling指针，为了方便range scan。
boltdb 的 B+ tree 一些实现细节如下：
key和value都是变长，所以是按照fill percent分裂和合并，同时有overflow page。page和变长node的转化就需要marshal/unmarshal，但page的存储格式方便了二分查找key。- 之前的文章说
branch node的key/value个数相同不太对，因为branch node的第一个key不起作用，所以一般情况下branch node的value比key多一个。但是在node分裂/合并时需要 计算从parent node中插入/删除的key，这时候就可以用第一个key保存分裂/合并时的key，不需要再计算了，当然这里还可以做suffix truncation的优化。 leaf node没有sibling pointer，所以boltdb查找时用栈保存了查找路径，用于实现range scan。
有本书 Modern B-Tree Techniques 介绍了 B+ tree 实现上的优化和细节，以后有时间可以看一下。
Transaction
之前文章关于 boltdb 事务的也不太对，之前是说用 MVCC + COW 实现事务的 ACID，准确的说是用 Shadow Paging 实现的 A 和 D，用 Shadow Paging + RWLatch 实现的一写多读的 I。
Shadow Paging 通俗来说就是每当修改时就 COW 写到新的 page，在 commit 时整个切换到新的 page，相当简单的就实现了 AD：commit 切换成功最新的数据已经落盘，commit 失败不会切换到新 page，也
不会影响现有数据。Shadow Paging 采用的是 NO-STEAL + FORCE 策略：
NO-STEAL：不允许uncommitted数据覆盖磁盘上committed数据。(有时会说只有commit时才能写数据，感觉不太准确，比如用Shadow Paging的话提前写到新page也没影响，只要不覆盖committed数据就好)。FORCE：commit时要把所有更新的数据写到磁盘上。
boltdb 的实现就是如此：commit 时进行 B+ tree 的分裂和合并，然后所有 dirty page 写到新的 page，最后把 metadata 写到新的 page 然后切换到新的 B+ tree。NO-STEAL + FORCE 的局限性很多，
以 boltdb 的实现为例：
page修改很小也需要写入整个page，写放大较大，而且因为新分配了page，所以从leaf到root的所有page都会变为dirty(因为修改了child page id)，写放大就更大了。boltdb用mmap做读的buffer pool manager，node中的数据指向的是mmap的数据，可以减少内存使用。但commit时不是将dirty node一个个写入磁盘，而是先给每个dirty node分配buffer + page id， 然后对page id排序再写入，目的是减少随机I/O，但是极大增加了内存使用，很容易导致stall。Shadow Paging需要GC回收之前的page。boltdb是用freelist维护可以复用的page，虽然上面先排序再写可以减少部分随机I/O，但是仍然不可避免。而且没有compaction，文件大小会一直增大。- 没法做
page内的并发，因为若不同事务使用了相同的新page会导致commit未提交的数据，若不使用相同的新page又会丢失已提交的新的数据。而且boltdb是用固定的前2个page保存metadata， 这也导致了没法做写写并发。
boltdb 提供的是一写多读的 I，一写是用 W-Latch 保护的，而 Shadow Paging 天然支持了读写并发，只要读事务访问到的 page 没有被新的 page 覆盖即可，
所以 boltdb 的 freelist 中维护了每个 tx 释放的旧 page id，只有当所有读事务的 txid 都大于它时才能释放。(其实就相当于维护了多个版本的 B+ tree)
与 Shadow Paging 相对应的就是 STEAL + NO-FORCE 的 WAL，好处就是顺序写 log 即可，性能高，写放大也小；坏处是恢复较慢，要有 checkpoint 机制来清理 log。
对于 leveldb 这种没事务，或者说只支持单个必定成功的读写操作事务的存储引擎来说，只需要 redo log 即可，更一般而言，还需要考虑 data page 和 log 的新旧关系，
还有 log 的类型等，具体可以看 ARIES。
还有一点值得一提，因为我之前都是搞 kv 的，所以觉得只用 MVCC 就能实现 concurrency control，其实它只是减少读写冲突，但对于操作必定成功的 kv 来说，事务就是单个读写，所以 MVCC 就能保证隔离性。
更一般的 concurrency control 指的是 T/O, OCC,2PL 这种，数据库如果使用 MVCC 仍然需要前面的 concurrency control，MVCC 主要能解决读写冲突、提高并发度并提供只读事务的 snapshot isolation。
后续
Andy 老师很有趣，听说号称数据库匪徒，后面会继续开坑他的 CMU 15-721。课上有三个场景印象深刻，
一是他介绍自己时说只关心 2 件事：他的妻子和数据库；二是贴了别人骂他的邮件还挂了中国版 youtube(bilibili) 搬运他的视频；三是说要把永远不要在数据库中用 mmap 刻到他的墓碑上。
留下评论