专栏
《数据库系统内 幕》存储引擎
《数据库系统内 幕》事务恢复与处理
《数据库系统内 幕》日志结构存储
《数据库系统内 幕》B树的变体
《数据库系统内 幕》分布式系统

章五

第五章是本书中重要一章，有三节。是存储结构后的一些高级组件问题，包括缓冲区管理、锁管理和恢复。为了更方便的理解数据库事务。

缓冲区管理

页缓存

对于双层存储体系，磁盘的访问速度较慢，所以为了减少访问磁盘，页面被缓存在内存中。
当磁盘上的数据一直不被修改，就可以重用内存的缓存页，称为虚拟磁盘。但是当内存的副本满了，就会去访问磁盘，以上称为页缓存。
存储引擎请求页的时候，就是先看内存中有无缓存版本，有的话直接访问，没有的话去磁盘中，将逻辑地址和页号转换为物理地址，加载到内存，然后给存储引擎已缓存的版本。
脏页：页上的脏标志位表示内容与磁盘不同步，必须刷写至磁盘才能保证持久性。

回收

保持页缓存满的的状态较好。
持久性的维持：需要预写日志（WAL）和页缓存。因为若数据库崩溃则未刷写的数据会丢失，所以设置日志，只有刷写完成才丢弃日志记录。

预写日志、页缓存（缓存页刷写完成）-> 日志记录丢弃 -> 脏页换出缓存

锁定页

根据b树的数据结构，可以了解他是“矮胖”的形状，可以考虑到层次高的节点会在大多数读取中命中。同时在分裂合并操作中往往也会被命中。所以对于这些频率贼高的页可以进行“固定”。

页置换策略：同os中的置换策略。

FIFO：注意会产生belady异常。
LRU：最长时间未使用，如果每次维护一个队列，将页进行一个更换时，重新引用和链接节点代价较高。
CLOCK/CLOCK-sweep：（时钟页面置换算法）
LFU：最小频率算法。tinyLFU是基于频率的页置换策略，它不是选择换出的元素，选择的是要保留的元素形成一个保护队列，对于访问频率相对很高的元素在队列中进行长时间保留。采用了一个频率直方图来维护紧凑的缓存访问历史记录。
该策略里面有三个队列：
入场队列----考察队列----保护队列

恢复

通过预写日志这个仅追加的辅助磁盘数据结构，保证数据库系统有持久性语义。
WAL既保存单独的操作记录，又保存事务完成的记录。
系统在回滚或恢复期间为保证系统正常工作，会在撤销操作时记录补偿日志记录并将其存储在日志中。

检查点

检查点用来标记之前的日志记录已经不被需要了，减少了工作量。强制将所有脏页刷写到磁盘过程称为同步检查点。
因为全部刷写是不现实的，所以大多数数据库选择了模糊检查点。
日志头部用last——checkpoint指针记录最后一次成功的检查点信息。模糊检查点从begin-checkpoint记录开始到end-checkpoint结束。

steal和force策略（不太理解，要回看）

为了确定何时将内存的更改刷写到磁盘上，定义出来的策略。
steal策略是在事务提交之前允许刷写事务修改过的页。
no-sreal策略不允许将未提交的事务内容刷写到磁盘。
force策略要求在事务提交前将事务修改的所有页刷写到磁盘上。
no-force策略即使事务修改的页尚未刷写到磁盘上，也可以提交。
现在DBMS常用的是steal/no-force策略，因此一般都需要记录redo log和undo log。这样可以获得较快的运行时性能，代价就是在数据库恢复（recovery）的时候需要做很多的事情，增大了系统重启的时间。
数据库崩溃后重启时的恢复过程分为三个阶段：

分析阶段：识别页缓存中脏页和崩溃时进行的事务。
重做阶段：重放历史记录直到崩溃点。
撤销阶段：回滚所有未完成事务，还原到一致状态。防止再次崩溃，撤销事务操作也会记录到日志中。

并发控制

本章节研究的是本地的并发控制技术。
乐观并发控制：
允许多个事务并发的读取和写入，事务不会相互阻塞，而是保留记录，并在提交前检查这些历史记录是否冲突，如果产生冲突则终止某一个冲突事务。

多版本并发控制mvcc：
允许一条数据同时存在多个时间戳的版本，通过这种方式事务读到的是过去的某一时刻的一致的视图。后续的操作都是针对一个版本的数据进行的（这里的翻译非常混乱）。

悲观并发控制：
加锁的版本会要求维护数据库记录上的锁。不加锁的实现根据未完成事务调度，维护读写操作列表。

异常

并发执行事务期间会出现读异常和写异常：脏读、不可重复读、幻读；脏写、丢失更新、写偏斜。

脏读：读到未提交的数据，比如说前面的事务更新之后回滚，后面的事务就读到了未提交的数据。
不可重读：同一事务两次执行，读取到的数据不一致，t1读取一行，t2修改并提交，t1再次读取数据改变。
幻读：指的是两次范围读取获取的行集合不一样。

丢失更新：两个事务同时更新一个值，且都commit,则后提交的覆盖了前面提交的。
脏写：脏读情况下又修改。
写偏斜：单个事务满足一些约束，组合事务却违反了。

处理数据库死锁的几种方法：

1.引入超时机制并终止长时间运行的事务。

2.保守2PL（两阶段锁）。

数据库常使用等待图（waits-for graph实现）来检测或者避免死锁：