《How does a relational database work》阅读笔记 2024.01.05 数据库

这篇文章上次修改于 473 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

《How does a relational database work》阅读笔记

当你进行一个数据库请求的时，会优先发送给客户端管理器

客户端管理器

• 查看你的用户密码是否有权限（是否有权限访问）
• 查看是否有线程能处理请求
• 查看数据库是否属于高负荷
• 设定和检查超时时间
• 传输查询字符串到查询管理器，等待查询结果
• 查询如果成功，将会从查询管理器获得到目标数据
• 查询如果失败，就会返回给你错误原因，其他什么都不做

查询管理器

它接收到的是查询内容 ，同时查询管理器还包含了查询解析器和查询重写器以及查询优化器

• 查询解析器检查是否合法
• 查询重写器去除无用字符，并进行预优化处理
• 查询重写器接着进行优化以提高性能，并转化为执行(execution)和数据访问计划(data access plan)
• 编译数据访问计划
• 执行数据访问计划

至于如何优化查询，SQLite的官方文档有描述

查询解析器

查询解析器会检查关键词语法和顺序，一旦不正确就会立即返回失败结果

• 查询表是否存在
• 查询表的字段是否存在
• 字段操作合法（例如将字符串和数字比较是非法的运算）
• 检查操作权限（这是更细分的权限，例如读写等）
• 发送被转换的内部表示给查询重写器

解析过程中会把查询转换为内部表示（不同的数据库有不同的内部表示，通常是树）

查询重写器

查询重写器得到的是查询的内部表示

查询重写器主要是为了预优化查询，避免不必要操作，帮助优化器找到最佳解决。

查询重写器会使用一些优化规则，例如：视图合并，子查询扁平化等

这就是一个优化样例：

SELECT PERSON.*
FROM PERSON
WHERE PERSON.person_key IN
(SELECT MAILS.person_key
FROM MAILS
WHERE MAILS.mail LIKE 'christophe%');

会转换为：

SELECT PERSON.*
FROM PERSON, MAILS
WHERE PERSON.person_key = MAILS.person_key
and MAILS.mail LIKE 'christophe%';

• 去除不必要的运算符（DISTINCT但有UNIQUE 约束）

• 排除冗余的联接（相同JOIN条件）

• 常数计算赋值（用常量替代常量表达式）

• (Advanced)分区裁剪：如果你用了分区表，重写器能够找到需要使用的分区

• (Advanced)物化视图重写：如果你有个物化视图匹配查询谓词的一个子集，重写器将检查视图是否最新并修改查询，令查询使用物化视图而不是原始表

• (Advanced)自定义规则：自定义的规则去修改查询

• (Advanced)OLAP转换：分析/加窗 函数，星形联接，ROLLUP 函数……都会发生转换（可能由优化器完成）

• 传输重写后的查询交给查询优化器

统计

数据库和操作系统使用一个最小单元叫做页或者块（4 KB or 8KB）

当数据库收集统计信息，会计算下列值：

• 表中行和页的数量
• 表中每个列中的：
  • 唯一值
  • 数据长度（最小，最大，平均）
  • 数据范围（最小，最大，平均）
• 表的索引信息

这些统计信息会帮助优化器估计查询所需的磁盘 I/O、CPU、和内存使用

例如列的统计的某个作用

如果一个表 PERSON 需要联接 2 个列： LAST_NAME, FIRST_NAME。根据统计信息，FIRST_NAME只有 1,000 个不同的值，LAST_NAME 有 1,000,000 个不同的值。因此，应按照 LAST_NAME + FIRST_NAME 联接。因为 LAST_NAME重复的数据更少，在比较的时候在判断LAST_NAME时会更快的结束判断，这将减少比较的次数。

数据库也有一些高级统计，叫直方图。直方图是列值分布情况的统计信息。例如：

• 出现最频繁的值
• 分位数(quantiles)
• …

这些额外的统计会帮助数据库找到更佳的查询计划，尤其是对于等式谓词（例如： WHERE AGE = 18 ）或范围谓词（例如： WHERE AGE > 10 and AGE < 40），因为数据库可以更好的了解这些谓词相关的数字类型数据行（注：这个概念的技术名称叫选择率）。

统计信息保存在数据库元数据内，例如（非分区）表的统计信息位置：

• Oracle： USER / ALL / DBA_TABLES 和 USER / ALL / DBA_TAB_COLUMNS
• DB2： SYSCAT.TABLES 和 SYSCAT.COLUMNS

统计信息必须及时更新。如果一个表有 1,000,000 行而数据库认为它只有 500 行就会发生错误的判断。数据库大多默认情况下不会自动计算统计信息，因为统计需要时间成本。数据达到百万级时统计会变得困难，这时候，可以选择仅做基本统计或者在一个数据库样本上执行统计。（但是也应当小心处理）

作者说自己只统计10%导致一个拥有上亿数据的表的一次本应 30 秒的查询执行了8小时

每个数据库还有其特定的更高级的统计。如果想了解更多信息，寻找的文档。推荐的官方文档来自PostgreSQL。

查询优化器

所有的现代数据库都在用基于成本的优化（即CBO）来优化查询。

优化器关注CPU 成本、磁盘 I/O 成本、和内存需求

每一个高级代码运算都要特定数量的低级 CPU 运算。

对于 Intel Core i7、Intel Pentium 4、AMD Opteron…等，（就 CPU 周期而言）CPU 的运算成本是不同的，也就是说它取决于 CPU 的架构。

大多数时候瓶颈在于磁盘 I/O 而不是 CPU 使用

用个例子来感受一下这个任务背后的复杂性，以理解CBO优化器的原理。

对于联接两个表

如果只考虑时间复杂度可以有三个种解法：嵌套循环联接， 哈希联接，合并联接

前置知识

在此之前，我们需要一些前置知识

存取路径

在应用联接运算符之前，首先需要获得数据。以下就是获得数据的方法。

• 全扫描

全扫描就是数据库完整的读一个表或索引。就磁盘 I/O 而言，很明显全表扫描的成本比索引全扫描要高昂。

• 范围扫描

其他类型的扫描有索引范围扫描，比如当使用谓词 ” WHERE AGE > 20 AND AGE < 40 ” 时

范围查询的时间成本大约是 log(N)+M。在磁盘 I/O 方面没有全扫描那么昂贵。

• 唯一扫描

如果你只需要从索引中取一个值你可以用唯一扫描。

• 根据 ROW ID 存取

多数情况下，如果数据库使用索引，它就必须查找与索引相关的行，这样就会用到根据 ROW ID 存取的方式。

例如运行：

SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28

如果 person 表的 age 列有索引，优化器会使用索引找到所有年龄为 28 的人，然后它会去表中读取相关的行，这是因为索引中只有 age 的信息而你要的是姓和名。

但是例如运行：

SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON
WHERE PERSON.AGE = TYPE_PERSON.AGE

PERSON 表的索引会用来联接 TYPE_PERSON 表，但是 PERSON 表不会根据行ID 存取，因为你并没有要求这个表内的信息。

虽然这个方法在少量存取时表现很好，这个运算的真正问题其实是磁盘 I/O。假如需要大量的根据行ID存取，数据库也许会选择全扫描。

联接运算符

内关系和外关系可以是一个表，一个索引，上一个运算的中间结果。

当你联接两个关系时，联接算法对两个关系的处理是不同的。

假定 A JOIN B 是 A 和 B 的联接，这里 A 是外关系，B 是内关系。（假定外关系有 N 个元素，内关系有 M 个元素）

多数情况下， A JOIN B 的成本跟 B JOIN A 的成本是不同的。

嵌套循环联接

针对外关系的每一行，查看内关系里的所有行来寻找匹配的行

可以说是暴力查找每个，查看是否是联接的

由于这是个双迭代，时间复杂度是 O(N*M)。

同时考虑IO方面，需要进行一定优化，对于原本的计算，需要进行多次的磁盘读取，需要很大的成本

以下是优化方案：

• 成簇读取，把两个关系的两簇数据行保存在内存里
• 比较两簇数据，保留匹配的
• 然后从磁盘加载新的数据簇来继续比较
• 直到加载了所有数据。

这个版本降低了磁盘访问，时间复杂度没有变化

原本的磁盘访问为N + N*M

这个版本为 将N和M都转化为对应的数据簇数量，同时，增加数据簇的尺寸，可以降低磁盘访问。

哈希联接

意如其名，使用哈希表，对内关系进行哈希处理。

再对外关系进行哈希查表

时间复杂度是 (M/X) * N + 创建哈希表的成本(M) + 哈希函数的成本 * N 。

如果哈希函数创建了足够小规模的哈希桶，那么复杂度就是 O(M+N)。

还有个哈希联接的版本，对内存有利但是对磁盘 I/O 不够有利。 这回是这样的：

计算内关系和外关系双方的哈希表，保存哈希表到磁盘，逐个哈希桶比较（其中一个读入内存，另一个逐行读取）。

合并联接

合并联接就是两个输入源都按照联接关键字排序后再进行联接处理

有时数据集已经排序了

对于两个已经排序的联接关键字

• 在两个关系中，比较当前元素（当前=头一次出现的第一个）
• 如果相同，就把两个元素都放入结果，再比较两个关系里的下一个元素
• 如果不同，就去带有最小元素的关系里找下一个元素（因为下一个元素可能会匹配）
• 重复 1、2、3步骤直到其中一个关系的最后一个元素。

时间复杂度是 O(N+M)

比较

不同情况下，各有不同的表现。

• 内存不足：哈希联接需要大量的内存，虽然效率很高。
• 两个数据集的大小。比如，如果一个大表联接一个很小的表，那么嵌套循环联接就比哈希联接快，因为后者有创建哈希的高昂成本；如果两个表都非常大，那么嵌套循环联接CPU成本就很高昂。
• 是否有索引：若有两个 B+树索引，都是已排序状态，使用合并联接。
• 结果是否需要排序：即使你用到的是未排序的数据集，你也可能想用成本较高的合并联接（带排序的），因为最终得到排序的结果后，你可以把它和另一个合并联接串起来
• 数据的分布：如果联接条件的数据是倾斜的（比如根据姓氏来联接人，但是很多人同姓）某个或某些连接键（Join Key）的分布不均匀，导致部分键值的数据量远远超过其他键值。不建议用哈希联接，哈希函数将产生分布极不均匀的哈希桶。

实际优化器采用

使用一个例子来说明，假如有4个表ABCD需要被联接

三次联接有多重方案。例如(A+B) + (C + D) 或者 ((A+B) + C )+ D等等。

实际数据库采用动态规划，贪心算法和启发式算法

优化器会产生多个方案，并且对方案进行评估，使用最优的方案。

动态规划

此时，如何计算多个方案的成本，动态规划体现在评估中，例如当评估(A+B) + (C + D) 或者 ((A+B) + C )+ D时，(A + B)都需要被评估，只需要储存结果之后使用即可。降低了评估的复杂度。

为了最大利用已经评估的子问题，需要使用动态规划和一定的顺序来达成。

贪心算法

原理是按照一个规则以渐进的方式制定查询计划。在这个规则下，贪婪算法逐步寻找最佳算法，先处理一条JOIN，接着每一步按照同样规则加一条新的JOIN。

例如从A开始每两个表之间的联接成本，选择最低的，再分析当前情况选择剩余最低的。至于何为最低，在不同时刻采用的可能是不同的规则。

不仅从表 A 开始，还可以把同样的算法用在 B，然后 C，然后 D, 然后 E。（KNN算法）

但是可能会存在以下情况：

• 即使在 A, B, C 之间，A JOIN B 可得最低成本
• (A JOIN C) JOIN B 也许比 (A JOIN B) JOIN C 更好。

为了改善这一状况，你可以多次使用基于不同规则的贪心算法，并保留最佳的执行计划。

查询计划缓存

由于创建查询计划是耗时的，大多数据库把计划保存在查询计划缓存，来避免重复计算。数据库需要知道什么时候更新过时的计划。办法是设置一个上限，如果一个表的统计变化超过了上限，关于该表的查询计划就从缓存中清除。

查询执行器

有了一个优化的执行计划，再编译为可执行代码，此时交给查询执行器。

如果有足够资源（内存，CPU），查询执行器就会执行它。计划中的操作符 (JOIN, SORT BY …) 可以顺序或并行执行，这取决于执行器。

数据管理器

查询管理器执行了查询，需要从表和索引获取数据，于是向数据管理器提出请求。

效率：数据提取速度慢，需要一定优化地利用缓冲区

冲突：事务模型导致同时多人使用访问数据时，不能获取。

缓存管理器

缓存管理器负责了效率问题。

查询执行器从缓存管理器获取数据。缓存管理器有缓冲池，显著提升数据库性能。（直接文件io太慢了）

为了提高性能，缓存管理器最好在查询执行器使用数据之前得到数据，否则查询管理器就要等待数据读出。

预读

为了解决这个问题，采用了预读，最理想的预读结果就是

处理数据A时，预读将要处理的B，处理B时预读将要处理的C，并且意识到A不再需要，从缓存池移除。

然而有时查询执行器不知道它需要什么数据，这时就需要预判和猜测它需要的数据，例如推测预读法(按照读取规律预测)或者顺序预读法(按储存顺序读取)

缓存命中率

对于预读的效率和效果，使用缓存命中率这个概念来判断。

糟糕的缓存命中率不总是意味着缓存工作状态不佳。

缓冲区置换策略

同时，如果一个数据被反复读取，它可能更会被保留使用，现代数据库用缓冲区置换策略来解决这个问题。

LRU算法

LRU（Least Recently Used）算法：在缓存里保留的数据是最近使用的，所以更有可能再次使用

先假设没有没锁住的数据，缓存在根据需求添加数据时，一旦数据将缓冲区填满，再次添加时将覆盖最久没有使用的数据。

对于全扫描的数据，缓冲区可能不够用。

于是数据库对于非常大的表通常采用直接路径读取，避免填满缓冲区。对于中等大小的表，数据库可以使用直接读取或缓存读取。如果选择缓存读取，数据库把区块置于LRU的尾部，防止清空当前缓冲区。

或者使用更高级的算法

LRU-K

考虑数据最后第K次使用的情况，数据使用的次数加进了权重，一批新数据加载进入缓存，旧的但是经常使用的数据不会被清除（因为权重更高），数据如果不再使用，权重值随着时间推移而降低。

其他算法

• 2Q（类LRU-K算法）

• CLOCK（类LRU-K算法）

• MRU（最新使用的算法，用LRU同样的逻辑但不同的规则）

• LRFU（Least Recently and Frequently Used，最近最少使用最近最不常用）

写缓冲区

缓冲区保存的是页（最小的数据单位），对于写缓冲区，可能有多次写的行为，但如果被修改了但还没有写入磁盘，就是脏页。有很多算法来决定写入脏页的最佳时机，但这个问题与事务的概念高度关联。

事务管理器

事务模型是计算机科学和数据库管理领域中的一个概念，用于描述一组操作的执行方式，使其具有以下特性：

1. 原子性（Atomicity）： 事务是不可分割的工作单位，要么全部执行成功，要么全部失败回滚，不存在中间状态。
2. 一致性（Consistency）： 事务的执行使系统从一个一致性状态转移到另一个一致性状态。这意味着事务在执行前后，数据库必须保持一致性，不破坏数据库的完整性约束。
3. 隔离性（Isolation）： 多个事务可以并发执行，但其执行的结果必须与按某种顺序串行执行时的结果一致。隔离性确保一个事务的执行不会受到其他事务的影响。
4. 持久性（Durability）： 一旦事务成功完成，其对数据库的改变是永久性的，即使系统崩溃或发生其他故障，事务的结果也不会丢失。

对于一个数据库，想保证多个请求下互不冲突，最简单的办法就是依次执行，但依次执行只有单核心工作，效率很低。

并发控制

对相同数据的写操作增删改：

• 多个事务的读操作互不影响，可以同时处理。
• 若有事务在修改的数据需要被其他事务读取，数据库应当对其它事务隐藏修改。并且要确保隐藏但不能被其他事务影响擦除。

这个问题叫并发控制。

一个理想的办法是，每次一个事务创建或取消时：

• 监控所有事务的所有操作，检查是否有多个事务的部分操作因为读取/修改相同的数据而存在冲突
• 重新编排冲突事务中的操作来减少冲突的部分
• 按照一定的顺序执行冲突的部分（同时非冲突事务仍然在并发运行）
• 考虑事务有可能被取消

用更正规的说法，这是对冲突的调度问题。更具体点儿说，这是个非常困难而且CPU开销很大的优化问题。企业级数据库无法承担等待几个小时，来寻找每个新事务活动最好的调度，因此就使用不那么理想的方式以避免更多的时间浪费在解决冲突上。

锁管理器

使用锁是一个很常见的解决方法，类似于多线程中听到的锁。用于解决并发控制问题

悲观锁

悲观锁（Pessimistic Lock）是一种并发控制的机制，用于在多个事务同时访问共享资源时保证数据的一致性和完整性。悲观锁的核心思想是在操作数据之前，先获取锁，确保在整个操作过程中其他事务无法修改该数据，从而避免并发引起的数据不一致问题。

悲观锁的具体实现方式有排他锁和共享锁

排他锁

排他锁含义是，当我锁上这个数据，不允许其他事务操作。

• 如果一个事务需要一条数据，它就把数据锁住
• 如果另一个事务也需要这条数据，它就必须要等第一个事务释放这条数据上的排他锁

但其实我们没必要对多个读取同数据操作加排他锁，它们可以同时运行。

共享锁

共享锁含义是，当我锁上这个数据，请保证数据不能被修改，但可以被读取。

• 如果一个事务只需要读取数据A, 它会给数据A加上『共享锁』并读取
• 如果第二个事务也只需要读取数据A, 它会给数据A加上『共享锁』并读取
• 如果第三个事务需要修改数据A, 它会给数据A加上『排他锁』，但是必须等待另外两个事务释放它们的共享锁。

同样的，如果一块数据被加上排他锁，一个只需要读取该数据的事务必须等待排他锁释放才能给该数据加上共享锁。

锁管理器是添加和释放锁的进程，用一个哈希表保存锁信息（关键字是被锁的数据）：

• 数据被哪个事务加的锁
• 数据被哪个事务等待

死锁

死锁是一种处理时产生的问题，需要我们去解决，其情况是：

• 事务A 给 数据1 加上排他锁并且等待获取数据2
• 事务B 给 数据2 加上排他锁并且等待获取数据1

两个事物因为锁互相等待，导致卡死。

如何判断死锁，对于一个储存状态的哈希表，需要去查找一个循环，这个成本很大，于是采用超时设定。如果一个锁在超时时间内没有被加上，那么事务就是死锁状态

锁管理器也可以在加锁之前检查该锁会不会变成死锁，但是想要完美的做到这一点还是很昂贵的。因此这些预检经常设置一些基本规则。

解决死锁，锁管理器要回滚其中一个事务，对此应当考虑多个因素

• 减少回滚的成本 杀死数据修改量最少的事务
• 杀死持续时间最短的事务，因为其它事务的用户等的时间更长
• 杀死能用更少时间结束的事务（避免可能的资源饥荒）
• 一旦发生回滚，有多少事务会受到回滚的影响

两段锁

一个简单的思路是：事务开始时，加上所有会用到的锁，做完之后，释放所有结束使用的锁。

但是为了等待所有的锁，大量的时间被浪费了。

更快的方法是两段锁协议（Two-Phase Locking Protocol，由 DB2 和 SQL Server使用），在这里，事务分为两个阶段：

• 成长阶段：事务可以加锁，但不能释放锁。
• 收缩阶段：事务可以释放锁，但不能加新锁。

它的区别在于不是一次性添加所有锁和解除所有锁，在用到数据的时候添加锁，处于收缩阶段时，一旦某个数据不再会被修改，就释放锁。锁是被逐渐添加和逐渐释放的，而并不是一次性的。

但有一个问题：

如果修改了一条数据、释放了关联的锁后，事务被回滚，而另一个事务读到了修改后的值，但最后这个值需要被回滚。

解决：

所有独占锁必须在事务结束时释放。

更多

真实的数据库涉及到更多类型的锁（比如意向锁，intention locks）和更多的粒度（行级锁、页级锁、分区锁、表锁、表空间锁），但是思路是相同的。

数据版本控制

数据版本控制是解决这个问题的另一个方法。

版本控制是这样的：

• 每个事务可以在相同时刻修改相同的数据
• 每个事务有自己的数据拷贝（或者叫版本）
• 如果2个事务修改相同的数据，只接受一个修改，另一个将被拒绝，相关的事务回滚（或重新运行）

这将提高性能，因为：

• 读事务不会阻塞写事务
• 写事务不会阻塞读
• 没有『臃肿缓慢』的锁管理器带来的额外开销

除了两个事务写相同数据的时候，数据版本控制各个方面都比锁表现得更好。但磁盘空间消耗巨大。（读多还是写多决定了使用哪一种）

一些数据库，比如DB2（直到版本 9.7）和 SQL Server（不含快照隔离）仅使用锁机制。其他的像PostgreSQL, MySQL 和 Oracle 使用锁和鼠标版本控制混合机制。

日志管理器

当事务提交时服务器崩溃，崩溃时还在内存里的数据会丢失，这破坏了事务的持久性。你可能把所有数据都写在磁盘上，但是如果服务器崩溃，最终数据可能只有部分写入磁盘，这破坏了事务的原子性。

根据原子性：事务作出的任何修改必须是或者撤销，或者完成。

有 2 个办法解决这个问题：

• 影子副本/页（Shadow copies/pages）：每个事务创建自己的(部分)数据库副本，并基于这个副本来工作。一旦出错，这个副本就被移除；一旦成功，数据库立即使用副本替换到数据中。
• 事务日志（Transaction log）：事务日志是一个存储空间，在每次写盘之前，数据库在事务日志中写入一些信息，这样当事务崩溃或回滚，数据库知道如何移除或完成尚未完成的事务。

第一种方案在运行时的副本造成大量磁盘开销，所以现代数据库使用事务日志。

事务日志必须保存在稳定的存储上，我不会深挖存储技术，但至少RAID磁盘是必须的，以防磁盘故障。

WAL（预写式日志）

多数数据库（至少是Oracle,SQL Server,DB2,PostgreSQL, MySQL 和SQLite) 使用预写日志协议（Write-Ahead Logging protocol ，WAL）来处理事务日志。

WAL协议有 3 个规则：

• 对数据库的每个修改都产生一条日志记录
• 日志记录必须写入事务日志，并且要在数据写入磁盘之前。
• 日志记录必须按顺序，先的写在前面。
• 当一个事务提交时，在事务成功之前，提交顺序必须写入到事务日志。

这个工作由日志管理器完成。

简单的理解就是，日志管理器处于缓存管理器和数据访问管理器之间，每个 update / delete / create / commit / rollback 操作在写入磁盘之前先写入事务日志。

但这个过程并不简单，因为如果事务日志写得太慢，整体都会慢下来。

我们应当考虑 如何找到写日志的同时保持良好的性能的方法

ARIES概念

1992年，IBM 研究人员“发明”了WAL的增强版，叫 ARIES。ARIES 或多或少地在现代数据库中使用，逻辑未必相同，但AIRES背后的概念无处不在。ARIES 代表 数据库恢复原型算法（Algorithms forRecovery andIsolationExploitingSemantics）。

这个技术要达到一个双重目标：

• 写日志的同时保持良好性能
• 快速和可靠的数据恢复

有多个原因让数据库不得不回滚事务：

• 因为用户取消
• 因为服务器或网络故障
• 因为事务破坏了数据库完整性（比如一个列有唯一性约束而事务添加了重复值）
• 因为死锁

日志信息

事务的每一个操作（增/删/改）产生一条日志，由如下内容组成：

• LSN：一个唯一的日志序列号（Log Sequence Number）。LSN是按时间顺序分配的，越早越小。
• TransID：产生操作的事务ID。
• PageID：被修改的数据在磁盘上的位置。磁盘数据的最小单位是页，所以数据的位置就是它所处页的位置。
• PrevLSN：同一个事务产生的上一条日志记录的链接。
• UNDO：取消本次操作的方法。比如，如果操作是一次更新，UNDO将或者保存元素更新前的值/状态（物理UNDO），或者回到原来状态的反向操作（逻辑UNDO, 只使用逻辑UNDO，因为处理物理UNDO太过混乱了)。
• REDO：重复本次操作的方法。 同样的，有 2 种方法：或者保存操作后的元素值/状态，或者保存操作本身以便重复。
• …：（还有 2 个字段：UndoNxtLSN 和 Type）

由PrevLSN可以发现，同一个事务会产生多个日志，并且它们会依PrevLSN联接在一起并且按时间顺序。

磁盘上每个页（保存数据的，不是保存日志的）都记录着最后一个修改该数据操作的LSN。

日志缓冲区

为了防止写日志成为主要的瓶颈，数据库使用了日志缓冲区。

当查询执行器要求做一次修改会有以下五步：

• 缓存管理器将修改存入自己的缓冲区；
• 日志管理器将相关的日志存入自己的缓冲区；
• 到了这一步，查询执行器认为操作完成了（因此可以请求做另一次修改）；
• 接着日志管理器把日志写入事务日志，什么时候写日志由某算法来决定。
• 接着缓存管理器把修改写入磁盘，什么时候写盘由某算法来决定。

当事务提交，意味着事务每一个操作的5个步骤都完成了。写事务日志是很快的，因为它只是『在事务日志某处增加一条日志』；而数据写盘就更复杂了，因为要用『能够快速读取的方式写入数据』。

STEAL 和 FORCE 策略

出于性能方面的原因，第 5 步有可能在提交之后完成，因为一旦发生崩溃，还有可能用REDO日志恢复事务。这叫做 NO-FORCE策略。

NO-FORCE策略：第 5 步有可能在提交之后完成

FORCE策略：第 5 步在提交之前必须完成

数据库使用FORCE策略可以用来降低恢复时的负载。

STEAL策略：数据是一步步的写入

NO-STEAL策略: 缓冲管理器需要等待提交命令来一次性全部写入

选择STEAL还是NO-STEAL取决于你想要什么：快速写入但是从 UNDO 日志恢复缓慢，还是快速恢复。

下面是这些策略对恢复的影响：

• STEAL/NO-FORCE 需要 UNDO 和 REDO: 性能高，但是日志和恢复过程更复杂 (比如 ARIES)。多数数据库选择这个策略。
• STEAL/ FORCE 只需要 UNDO.
• NO-STEAL/NO-FORCE 只需要 REDO.
• NO-STEAL/FORCE 什么也不需要: 性能最差，而且需要巨大的内存。

恢复

ARIES从崩溃中恢复有三个阶段：

• 分析阶段：恢复进程读取全部事务日志，来重建崩溃过程中所发生事情的时间线，判断哪些事务要回滚、崩溃时哪些数据需要写盘。
• Redo阶段：这一关从分析中选中的一条日志记录开始，使用 REDO 来将数据库恢复到崩溃之前的状态。
  • 在REDO阶段，REDO日志依据LSN按照时间顺序处理。
  • 对每一条日志，恢复进程需要读取包含数据的磁盘页LSN。
  • 如果LSN（磁盘页）>= LSN（日志记录），说明数据已经在崩溃前写到磁盘，不需要做什么。
  • 如果LSN（磁盘页）< LSN（日志记录），那么磁盘上的页将被更新。
  • 即使将被回滚的事务，REDO也是要做的，因为这样简化了恢复过程。
• Undo阶段：这一阶段回滚所有崩溃时未完成的事务。回滚从每个事务的最后一条日志开始，并且按照时间倒序处理UNDO日志（使用日志记录的PrevLSN）。

恢复过程中，事务日志必须留意恢复过程的操作，以便写入磁盘的数据与事务日志相一致。ARIES在事务日志中记录补偿日志，从逻辑上删除被取消的事务的日志记录。

当事务被『手工』取消，或者被锁管理器取消，或仅因为网络故障而取消，分析阶段就不需要了。

对于那些需要 REDO 和 那些需要 UNDO 的信息在 2 个内存表中：

• 事务表（保存当前所有事务的状态）
• 脏页表（保存哪些数据需要写入磁盘）

当新的事务产生时，这两个表由缓存管理器和事务管理器更新。

因为是在内存中，当数据库崩溃时它们也被破坏掉了

分析阶段的任务就是在崩溃之后，用事务日志中的信息重建上述的两个表。为了加快分析阶段，ARIES提出了一个概念：检查点（check point），就是不时地把事务表和脏页表的内容，还有此时最后一条LSN写入磁盘。那么在分析阶段当中，只需要分析这个LSN之后的日志即可