logging in database

一些概念

• undo
  移除掉没有完成或者中断的事务的影响的过程。
• redo
  重新处理(re-instating)提交事务的影响的持久化。
• steal policy
  DBMS是否允许未提交事务覆盖写最近提交了的事务的对象到持久化存储。(想象磁盘中的一个B树，一个数据修改某个key,还没提交，但是这个修改已经在这个B树上执行生效了，这就是允许)
  1. steal: 允许
  2. no-steal: 不允许
• force policy
  当一个事务允许提交时是否确保事务的全部更新都在持久化存储上生效了。
  1. force 确保
  2. no-force 不确保

NO-STEAL + FORCE

shadow paging, 数据库维护两个拷贝master, shadow(像boltdb), 更新只在shadow做，commit的时候切master到shadow(boltdb 两个meta page,txnid最大的那个生效的是当前master, metapage有个指向root结点的pointer, 修改的时候从低往上到根结点做copy on write).

• undo
  丢弃shadow做的修改的page即可。
• redo
  不需要

缺点

• 拷贝整个page花费太大
• 提交overhead太大
  需要flush每个修改的page，维护free list的page table, page碎片(空闲的page不连续)，需要gc没用的page。
  这样随机写比较慢，需要把随机转换为顺序写。

write-ahead log

全部修改先写log到一个文件， log信息要包含足够信息可以redo&redo恢复到crash之前到状态, commit的时候写一个commit的log落地持久化了才可返回给应用。
Buffer bool: STEAL + NO-FORCE(几乎每个DBMS都使用这个)

一个修改log包含的信息

• 事务id
• 对象id
• before value(undo)
• after value(redo)

为什么需要用STEAL

• txn很大的时候内存可能不够，非steal修改的page先在内存Buffer bool里全部不刷到db.

checkpoints

WAL会越来越大，所以需要定期做checkpoint刷全部buffer到磁盘。

• checkpoint前已提交的可以忽略
• chckpoint后commit的要redo
• 没提交的如t3需要undo

reference

http://15445.courses.cs.cmu.edu/fall2017/slides/21-logging.pdf
http://15445.courses.cs.cmu.edu/fall2017/slides/22-recovery.pdf