落盘的b+树(二)

事务

之前的b+树,并没有满足一致性的需求(或者说原子性), 因为涉及到写操作的时候,牵扯多了多个节点变更,如果出现其中一个节点写出现问题,整体上就没有办法恢复了.

所以加了一个分支,实现了出现部分写入问题,可以进行回滚.

解决

需要解决这种问题,目前必须采用double write,就是提前讲数据落在别的地方,等出现问题的时候能够从别处恢复
整体上记住一件事,出现double write的场景都是因为写是inplace update而不是append only

redo/undo

例如mysqlinnodbundoredo
都知道undo记录原始数据的值,本质上是逻辑日志(面向tuple记录)
undo是保证原子性(另一个作用是为了mysql的快照读这种黑科技,mvcc)

redo记录事务中数据变化后的数据,本质上是物理逻辑日志日志(面向page页,physical-to-a-page, logical-within-a-page),更像是"残缺"的快照
残缺是因为如果快照下全部页的占用空间成本太高了,通常不会全部记录
快照是因为记录的数据本身,而不是逻辑数据
redo是为了保证持久性(实际上,我认为如果不考虑性能问题redo是没有必要存在的,mysql为了性能,把部分成功的commit事务脏页留在了内存,当出现闪断等崩溃时候,内存全丢,期望从redo里面恢复)

由于undo/redo是顺序写(page cahce起到的作用,系统/物理内存层面,不涉及用户态内存,跟用户态的buffer作用很像,但是概论上有差别),都属于wal, 速度很快

ps: undo也是被当成数据(对undo页的修改,也需要先写redo日志),有相应的redo日志,通过redo日志可以恢复undo

double write

这里面说的double write跟上面有点差别,但是概论上是一样
double write这里面原因是mysql的数据页是以 16k为单位的,而文件系统通常是以4k为单位的(磁盘io的通常是以512Byte为单位的,通常文件系统能保证4k单位写入是原子的,例如ext3/ext4,但是ext2就不行的,我猜文件系统实现也是以double write方式类似,redo的日志设计成512Bytes),数据页和文件系统的写入单位不一致,极端情况下就会可能出现数据页部分写入的问题(可以理解成数据页的原子写入),所以mysql需要double write将这部分数据先保存另一个地方,保证能够恢复

boltdb

对于boltdb的实现,是典型的append only,所以没有redoundo,将所有db文件直接mmap. 维护两个版本meta,每次涉及到的修改node(对应磁盘page)都不破坏原来的节点数据,直接新建一个新的.
落盘顺序是 data(不影响当前版本的数据)/meta. 如果data落盘失败,不影响当前已完成事务的数据;如果mata失败,由于meta会做checksum检查meta数据是否是正确的,当前meta也是不认为是完成事务的.

注意一点,就是boltdbb+树跟正常的有点不一样,page结构体没有next信息(没有维护指向兄弟的信息),没有parent节点信息.
这个是因为如果包含了,那么每次insert一个新的key,为了包括数据一致性,整颗树都得dump到内存中.
不维护这些信息,动态从pagenode的时候重新构建,这样每次产生的脏页只是查询链路的节点(如果不考虑分裂).

参考

https://youjiali1995.github.io/storage/boltdb/
https://blog.csdn.net/mydriverc2/article/details/50629599
https://www.cnblogs.com/cchust/p/3961260.html double write 和 redo 区别
https://www.zhihu.com/question/280594447/answer/416845508 阿里云的polardb 为什么可以取消double write
https://zhuanlan.zhihu.com/p/86622268 这里面redo是物理日志写的有问题
https://www.cnblogs.com/geaozhang/p/8555660.html
http://mysql.taobao.org/monthly/2017/07/01/ MySQL · 引擎特性 · InnoDB崩溃恢复