谈谈几种Logging Schemes

引言
再次忙里偷闲，抽出一晚上时间来记录一些文字。动笔写这篇文章纯属巧合，按照计划今天下午我本应该回趟宝鸡和家里人吃顿饭的，奈何昨天忘了做核酸，今早九点便起床（对昨天晚上疯狂焦虑的我而言已经够早了）赶往最近的核酸检测点，但却被告知明早九点才出结果，只好作罢，又把回家的日子往后推了一周，这也使得今天晚上多出了一些时间（当然也可以说这是未来的时间），遂记录下一个有意思的问题。
日志恢复相关的名词对于初学者来说如同噩梦，undo，redo，WAL，，AOF，RDB，，等等名词一个还未搞清楚另外一个已经接踵而至的糊在脸上，实际上要搞清楚这些名词关键还是明白日志恢复到底是在做什么事情。我大抵是没功夫写一篇文章去总结他们之间的区别的，但是我可以基于几个已有的例子来聊聊这个问题，主要聚焦于Redis Multi Part AOF，的 edit以及可能暂时只有adl和我知道的基于 tree的日志恢复，以及搞清楚基于 tree的日志恢复到底是在做什么事情。
Steal和 Force
日志恢复中有两个很重要的概念，即Steal 和Force，前者的含义是DBMS是否允许在事务未提交时用内存中的脏数据覆盖非易失性存储中的数据；后者的含义是DBMS是否允许事务提交时所有的更新都被写入非易失性存储中。不管承认与否，几乎所有的日志恢复都是基于这两种策略来做的。
我们熟知的WAL其实就是STEAL + NO-FORCE，以关系型数据库举例，在事务修改 pool中数据后不执行脏页刷新，在实际事务的时候日志被写入非易失性存储(可以group )，然后才允许脏页刷新，这样做最大的好处就是执行时速度快，但是显然这样做我们需要redo和undo日志（所以关闭的默认WAL的都是没实现事务的），而且恢复时需要重做所有的WAL，WAL还可能是基于语句的，这意味着在时相对是较慢的。
与之对应的是NO-STEAL + FORCE策略，就是一种典型的实现。开始时 page table和 page table指向相同的地址，在实际写入时先把数据写到 page中，然后使得 page为 page，再重建 page，因为是树状，所以不需要重建整张表，但是这个重新建表的过程还是很昂贵，而且的成本也很高，不仅需要垃圾回收，而且需要刷新每个更新的页面、页面表和根目录。但是优势就是成功时数据才写入磁盘（[2]不要使用mmap代替 pool！），这意味着不存在，自然也就不需要redo和undo了，这意味着启动只需要载入非易失性存储上的数据即可。
LSM的日志恢复
LSM树相关的日志恢复WAL只是针对于的，实际大部分的数据存储还是在，随着每一次的变更，新的就被创建，对应的旧的也不再被使用，组织这些的文件就被称为，用于在重启时将数据库恢复到最新的一致状态，中用于恢复的函数是::，函数把文件中所有记录读出，通过后生成[9]，然后重放为宕机前的。
其实这类似于STEAL + NO-FORCE策略的结果，用时的低效换取运行时的高效（因为并不是所有的都存在于最后的），而基于 tree的做法则是类似于git的存储模型，在时一定所有的数据都是有效的。
在这个问题上花费太多的功夫其实并没有什么意义，因为的修改频率和log不是一个数量级的，而且总量也不是一个数量级的；其次站在的角度来说是不是树也无所谓，当然引入关于在上的优化思路则是另说了。
MPAOF
驱动哥的[1]这篇文章已经写的足够好的，我没必要再去陈述MPAOF的概念。我认为Redis的AOF其实就是一种特殊的WAL而已，因为其需要在数据库宕机时保证数据的持久性与事务的原子性，既然是WAL，那+WAL的做法总是没错的（内存数据库，当然不必讨论那两个 pool的策略了），至于则是生成而已，原来AOF最大的问题在于这个+WAL被塞成了一个AOF文件，这是一切低效和复杂性的根因。