落盘的b+树（二）

事务

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

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

解决

需要解决这种问题，目前必须采用double write，就是提前讲数据落在别的地方，等出现问题的时候能够从别处恢复

整体上记住一件事，出现double write的场景都是因为写是inplace update而不是append only

redo/undo

例如mysql中innodb的undo和redo

都知道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，所以没有redo和undo，将所有db文件直接mmap. 维护两个版本meta，每次涉及到的修改node(对应磁盘page)都不破坏原来的节点数据，直接新建一个新的.

落盘顺序是 data（不影响当前版本的数据）/meta. 如果data落盘失败，不影响当前已完成事务的数据；如果mata失败，由于meta会做checksum检查meta数据是否是正确的，当前meta也是不认为是完成事务的.

注意一点，就是boltdb的b+树跟正常的有点不一样，page结构体没有next信息（没有维护指向兄弟的信息），没有parent节点信息.

这个是因为如果包含了，那么每次insert一个新的key，为了包括数据一致性，整颗树都得dump到内存中.

不维护这些信息，动态从page到node的时候重新构建，这样每次产生的脏页只是查询链路的节点（如果不考虑分裂）.

参考

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崩溃恢复