> ## Content Index
> Fetch the complete content index at: https://blog.hacking.pub/llms.txt
> Use this file to discover other available public pages before exploring further.

# 落盘的b+树（二）
- URL: https://blog.hacking.pub/2019/11/07/untitled-6/
- Published: 2019-11-07T09:00:00.000Z
- Updated: 2019-11-11T10:33:53.000Z
- Author: chainhelen
- Tags: b+, bplus, b树, 事务, transcation

#### 事务

之前的[b+树](https://github.com/chainhelen/bptree/tree/master?ref=blog.hacking.pub)，并没有满足一致性的需求（或者说原子性）, 因为涉及到写操作的时候，牵扯多了多个节点变更，如果出现其中一个节点写出现问题，整体上就没有办法恢复了.

所以加了一个[分支](https://github.com/chainhelen/bptree/tree/transcation?ref=blog.hacking.pub)，实现了出现部分写入问题，可以进行回滚.

#### 解决

需要解决这种问题，目前必须采用`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://youjiali1995.github.io/storage/boltdb/?ref=blog.hacking.pub)  
> [https://blog.csdn.net/mydriverc2/article/details/50629599](https://blog.csdn.net/mydriverc2/article/details/50629599?ref=blog.hacking.pub)  
> [https://www.cnblogs.com/cchust/p/3961260.html](https://www.cnblogs.com/cchust/p/3961260.html?ref=blog.hacking.pub) double write 和 redo 区别  
> [https://www.zhihu.com/question/280594447/answer/416845508](https://www.zhihu.com/question/280594447/answer/416845508?ref=blog.hacking.pub) 阿里云的polardb 为什么可以取消double write  
> [https://zhuanlan.zhihu.com/p/86622268](https://zhuanlan.zhihu.com/p/86622268?ref=blog.hacking.pub) 这里面redo是物理日志写的有问题  
> [https://www.cnblogs.com/geaozhang/p/8555660.html](https://www.cnblogs.com/geaozhang/p/8555660.html?ref=blog.hacking.pub)  
> [http://mysql.taobao.org/monthly/2017/07/01/](http://mysql.taobao.org/monthly/2017/07/01/?ref=blog.hacking.pub) MySQL · 引擎特性 · InnoDB崩溃恢复