目录：

[TOC]

正文：

数据管理器

查询管理器解析优化好SQL后，开始进行执行SQL，需要表和索引中的数据。 它要求数据管理器获取数据，但是有两个问题：

• 关系数据库使用事务模型。 因此，你做不到随时获取任意数据，因为其他人可能会同时使用/修改数据。
• 数据检索是数据库中最慢的操作，因此数据管理器必须足够聪明才能获取并将数据保留在内存缓冲区中。 在这一部分中，我们将看到关系数据库如何处理这两个问题。 我不会谈论数据管理器获取数据的方式，因为它不是最重要的。 我们分两部分介绍：缓存管理，事务管理

缓存管理Cache manager

我们知道，数据库的主要瓶颈是磁盘I/O。 为了提高性能，现代数据库使用缓存管理器。

查询执行程序不是直接从文件系统获取数据，而是向缓存管理器请求数据。 高速缓存管理器具有一个称为缓冲池的内存中高速缓存。 从内存中获取数据极大地加快了数据库的速度。

很难给出一个数量级，因为它取决于您需要执行的操作： - 顺序访问（例如：全表扫描）与随机访问（例如：按行ID进行访问）， - 读与写 以及数据库使用的磁盘类型： - 7.2k/10k/15k rpm HDD - SSD - RAID 1/5/…

但我想说内存比磁盘快100到10万倍。

但是，这导致了另一个问题（与数据库一样……）。 缓存管理器需要在查询执行程序使用它们之前获取内存中的数据； 否则查询管理器必须等待慢速磁盘中的数据。

预读

此问题称为预先读取。 查询执行程序知道所需的数据，因为它知道查询的全部流程，并且知道磁盘上的数据以及统计信息。 按这样的逻辑： - 当查询执行程序正在处理其第一堆数据时 - 它要求缓存管理器(我们简称为CM)预加载第二组数据 - 开始处理第二组数据时 - 它要求CM预加载第三束，并通知CM可以从缓存中清除第一束。 - … CM将所有这些数据存储在其缓冲池中。 为了知道是否仍然需要数据，缓存管理器添加了有关缓存数据的额外信息（称为latch）。

有时，查询执行程序不知道需要什么数据，或者某些数据库不提供此功能。取而代之的是，他们使用推测性预取（例如：如果查询执行器要求提供数据1,3,5，在不久的将来很可能会要求提供7,9,11）或顺序预读（在这种情况下，CM只是从磁盘加载要求的数据后的下一个连续数据）。

为了监视预读的工作状况，现代数据库提供了一个称为缓冲区/高速缓存命中率的指标。命中率显示在不需要DISK访问就直接在缓存里找到数据的频率。

请注意：不良的缓存命中率并不总是意味着缓存无法正常工作。有关更多信息，您可以阅读Oracle文档。 https://docs.oracle.com/database/121/TGDBA/tune_buffer_cache.htm  

但是，缓冲区是有限的内存。因此，它需要删除一些数据才能加载新数据。加载和清除缓存在磁盘和网络I/O方面要付出一定的代价。如果您有一个经常执行的查询，不断的加载然后清除该查询使用的数据会很笨拙。为了解决此问题，现代数据库使用缓冲区替换策略。

缓冲区替换策略 Buffer-Replacement strategies

现代数据库 (至少SQL Server, MySQL, Oracle and DB2)用 LRU算法.

LRU

LRU 是建立在 Least Recently Used.

该算法的思路是将最近使用过的数据保存在缓存中，因此更有可能再次使用。

让我们看一个直观的例子：

为了便于理解起见，我假设缓冲区中的数据没有被闩锁锁定（所以可以随时被删除）。在这个简单的示例中，缓冲区可以存储3个元素：

• 1：缓存管理器使用数据1并将数据放入空缓冲区
• 2：CM使用数据4并将数据放入未满的缓冲区
• 3：CM使用数据3并将数据放入未满的缓冲区
• 4：CM使用数据9。缓冲区已满，数据1被删除，因为它是最早使用的数据。数据9被添加到缓冲区
• 5：CM使用数据4。数据4已在缓冲区中，因此它再次成为最近使用的第一个数据。
• 6：CM使用数据1。缓冲区已满，因此数据9被删除，因为它是最早使用数据。数据1添加到缓冲区
• … 该算法效果很好，但存在一些限制。如果在一张大桌子上进行全面扫描怎么办？换句话说，当表/索引的大小大于缓冲区的大小时会发生什么？使用此算法将删除缓存中的所有先前值，而全表扫描中的数据可能仅使用一次。

LRU算法改进措施

为防止这种情况发生，某些数据库添加了特定规则。例如根据Oracle文档： https://docs.oracle.com/database/121/CNCPT/memory.htm#i10221

“对于非常大的表，数据库通常使用直接路径读取，该路径直接加载块[...]，以避免填充缓冲区高速缓存。对于中等大小的表，数据库可以使用直接读取或高速缓存读取。如果决定使用读取的缓存，则数据库会将这些块放在LRU列表的末尾，以防止扫描有效清除缓冲区缓存。”

还有其他可能性，例如使用LRU的高级版本：LRU-K。例如，SQL Server使用LRU-K表示K = 2。

LRU-K

该算法背后的思路是考虑更多历史使用信息。简单的LRU（其实就是K=1的特殊LRU-K），该算法仅考虑最后一次使用数据的时间。使用LRU-K：

• 它存储K:最后一次使用数据的时间。
• 使用数据的次数计为权重
• 如果将一堆新数据加载到缓存中，则不会删除旧的但经常使用的数据（因为它们的权重更高）。
• 但是，该算法不会保留旧数据在缓存里，如果它一直不再被用到。
• 如果不使用数据，权重会随着时间的推移而降低。 权重的计算成本很高，这就是为什么SQL Server仅使用K=2的原因。该值在可接受的开销下表现良好。

有关LRU-K的更深入的知识，您可以阅读原始的研究论文（1993年）：用于数据库磁盘缓冲的LRU-K页面替换算法。 https://www.cs.cmu.edu/~christos/courses/721-resources/p297-o_neil.pdf

其他算法

当然，还有其他算法可以管理缓存，例如

• 2Q（类似于LRU-K的算法）
• CLOCK（类似于LRU-K的算法）
• MRU（最近使用，使用与LRU相同的逻辑，但使用另一条规则）
• LRFU（最近和经常使用的）
• … 一些数据库允许使用默认算法以外的其他算法。

写缓冲驱 Write buffer

我只说过在使用数据之前加载数据的读取缓冲区。 但是在数据库中，还需要有写缓冲区，用于存储数据并将数据按束刷新到磁盘上，而不是一一写入数据以避免产生许多单个磁盘访问。

请记住，缓冲区存储的是页面（数据的最小单位）而不是行（这是查看数据的逻辑/人为方式）。 如果页面已被修改且未写入磁盘，则缓冲池中的页面是脏的。 有多种算法可以决定在磁盘上写入脏页的最佳时间，但它与事务的概念高度相关，这是本文的马上要开始的部分。

事务管理器 Transaction manager

最后一章节但并非是最不重要的一节，这部分是关于事务管理器的。 我们将看到此过程如何确保每个查询在其自己的事务中执行。 但是在此之前，我们需要了解ACID事务的概念。   ACID事务是确保以下四件事的工作单元：

• 原子性：哪怕一个事务持续了10小时，交易还是“全有还是全无”。 如果事务崩溃，则状态返回到事务之前（事务回滚）。
• 隔离性：如果2个事务A和B同时运行，则无论A在事务B之前/之后还是期间完成，事务A和B的结果都必须相同。
• 持久性：事务提交后（即成功结束），无论发生什么情况（崩溃或错误），数据都会保留在数据库中。
• 一致性：仅将有效数据（就关系约束和功能约束而言）写入数据库。 一致性与原子性和隔离性有关。

在同一事务中，您可以运行多个SQL查询来读取，创建，更新和删除数据。当两个事务使用相同的数据时，混乱就开始了。

最经典的例子是从帐户A到帐户B的汇款。假设您有2笔交易：

• 交易1从帐户A收取100美元，并将其转至帐户B
• 交易2从帐户A收取50美元，并将其转入帐户B

如果我们回到ACID属性： - 原子性可确保无论在T1期间发生什么情况（服务器崩溃，网络故障…），您都不会遇到从A提取100$而不将其分配给B的情况（这种情况是不一致的状态） 。 - 隔离性可确保如果T1和T2同时发生，则最终A将被收取150 $，而B被给予150 $，而不是例如，A被收取150$，B仅被给予$50，因为T2已部分抹去了T1（这种情况也是不一致的状态）。 - 持久性可确保如果T1提交后数据库崩溃，T1将不会消失。 - 一致性可确保不会在系统中创建或破坏任何金钱。

如果需要，您可以跳到下一部分，我要说的对本文的其余部分并不重要

许多现代数据库不使用纯粹的隔离性作为默认行为，因为它带来巨大的性能开销。 SQL规范定义了4个隔离级别：

• 可序列化（SQLite中的默认行为）：最高级别的隔离。同时发生的两个事务是100％隔离的。每个交易都有自己的“世界”。
• 可重复读（MySQL中的默认行为）：每个事务也都有其自己的“世界”，除一种情况外：如果一个事务成功结束并添加新数据，则这些数据将在另一个仍在运行的事务中可见。但是，如果A修改数据并成功结束，则该修改将在仍在运行的事务中不可见。因此，事务之间的这种隔离性将中断仅与新数据有关，而与已有数据无关。

例如，如果事务A执行“来自TABLE_X的SELECT count（1）”，然后事务B将新数据添加并提交到TABLE_X中，如果事务A再次执行count（1），则该值将不是相同。这称为*幻读*。

• 读已提交（Oracle，PostgreSQL和SQL Server中的默认行为）：这是可重复的读操作，并且实现了新的隔离。如果事务A读取数据D，然后由事务B修改（或删除）并提交该数据，则如果A再次读取数据D，它将看到B对数据进行的修改（或删除）。这称为*不可重复读取*。

• 读未提交：最低级别的隔离。这是读已提交+在隔离性方向的新突破。如果事务A读取数据D，然后该数据D被事务B修改（未提交但仍在运行），如果A再次读取数据D，它将看到修改后的值。如果事务B被回滚，则第二次读取的数据D毫无意义，因为它已经被从未发生过的事务B修改过（因为它已被回滚）。这称为*脏读*。

大多数数据库都添加了自己的自定义隔离级别（例如PostgreSQL，Oracle和SQL Server使用的快照隔离）。而且，大多数数据库并没有实现SQL规范的所有级别（尤其是读未提交级别）。

数据库连接开始时，用户/开发人员可以指定新的隔离级别（添加一行非常简单的代码即可）。

并发控制

确保隔离性，一致性和原子性的真正问题是对同一数据的写操作（添加，更新和删除）：

• 如果所有事务都仅读取数据，则它们可以在不更改另一事务行为的情况下同时工作。
• 如果（至少）一个事务正在修改其他事务读取的数据，则数据库需要找到一种对其他事务隐藏修改的方法。此外，还需要确保不会被事务将修改擦除覆盖了。

此问题称为并发控制。

解决此问题的最简单方法是一个接一个地（即顺序地）运行每个事务。但这根本无法扩展，并且只有一个内核正在多处理器/核服务器上工作，效率不是很高……

解决此问题的理想方法是每次创建或取消事务时：

• 监控所有事务的所有操作
• 检查2个（或多个）事务的各个部分是否存在冲突，如果它们正在读取/修改相同的数据。
• 重新排序冲突事务中的操作以减小冲突部分的大小
• 以一定顺序执行有冲突的部分（无冲突的事务仍同时运行）。
• 考虑到事务是可以被取消的。 更正式地说，这是执行时间冲突的排序问题。更具体地说，这是一个非常困难且耗费CPU的优化问题。企业数据库不可以等待数小时才能为每个新事务的事件找到最佳时间表。因此，他们使用不太理想的方法，从而导致冲突事务之间不得不浪费更多时间。

锁管理 Lock manager

为了解决此问题，大多数数据库都使用锁和/或数据版本控制。由于这是一个大话题，因此我将重点介绍锁部分，然后再介绍一些数据版本控制。

悲观锁定

悲观锁定背后的思路是： - 如果事务需要数据， - 它锁定数据 - 如果另一笔事务也需要此数据， - 它必须等到第一个事务释放数据。

这称为排他锁 或者 互斥锁。

但是，对于仅需要读取数据的事务使用排他锁非常昂贵，因为这会迫使仅希望读取相同数据的其他事务等待。这就是为什么还有另一种类型的锁，即共享锁。

使用共享锁：

• 如果事务只需要读取数据A，
• 它“共享锁定”数据并读取数据
• 如果第二笔交易也只需要读取数据A，
• 它“共享锁定”数据并读取数据
• 如果第三笔交易需要修改数据A，
• 它“独占锁定”数据，但它必须等到其他2个事务释放它们的共享锁后才能将独占锁定应用于数据A。

这里，如果将数据上有排他锁，一个读取数据的事务将不得不等待排他锁的结束才能在数据上放置共享锁。

锁管理器是提供和释放锁的过程。 在内部，它将锁存储在哈希表（key是要锁定的数据）中，并且知道每个数据：

• 哪些事务锁定了数据
• 哪些事务正在等待数据

死锁

但是锁的使用会产生一个问题：两个事务都在等一个数据

在此图中：

事务A在data1上具有排他锁，并且正在等待获取data2 事务B在data2上具有排他锁，并且正在等待获取data1 这称为死锁。

死锁发生后，锁管理器选择要取消（回滚）的事务以删除死锁。这个决定并不容易：

• 是不是最好：杀死修改了最少数据量的事务（因此将产生最少的回滚）？
• 是不是最好：杀死最近的事务，因为另一个事务的用户等待了更长的时间？
• 是不是最好：取消需要较少时间完成的事务（并避免可能的资源不足）？
• 如果发生回滚，此回滚将影响多少事务？  

但是在做出决定之前，它还需要检查是否存在死锁。

哈希表可以看作是一个图形（就像前面的图中一样）。如果图中有一个循环，则存在死锁。由于检查周期非常昂贵（因为带有所有锁的图形很大），因此通常使用一种更简单的方法：使用超时。如果在此超时时间内未给出锁定，则事务将进入死锁状态。

锁管理器还可以在提供锁之前检查该锁是否会产生死锁。但是，还是同样的问题这个检查的代价有点大。因此，这些预检查通常是一组基本规则。

两阶段锁定

确保完全隔离的最简单方法是在事务开始时获取所有锁，然后在事务结束时释放锁。 这意味着事务在开始之前必须等待其所有锁，并且在事务结束时释放由其持有的锁。 它可以工作，但会浪费大量时间来等待所有锁。

更快的方法是两阶段锁定协议（DB2和SQL Server使用），该协议将事务分为两个阶段：

• 加锁阶段：事务可以加锁但是无法释放任何锁的阶段。
• 解锁阶段，在该阶段事务可以释放锁（针对已经处理且不会再次处理的数据），但无法获得新的锁。

这两个简单规则的思路是：

• 释放不再使用的锁，以减少等待这些锁的其他事务的等待时间
• 防止在事务开始后读到被篡改的数据（这部分修改是事务开始以后才发生的）并因此与事务一开始获取的数据不一致的情况。（不可重复读）

该协议运行良好，除非另一个事务修改了数据并释放关联锁的事务（回滚了）。 您可能会遇到另一个事务读取修改后的值而该值被回滚的情况。 为避免此问题，必须在事务结束后再释放所有排他锁

补充几句话

当然，真正的数据库使用的是更复杂的系统，其中涉及更多类型的锁（例如意向锁）和更多粒度（行锁，页锁，分区锁，表锁，表空间锁），但是实现的思路仍然相同。

我只介绍了基于锁的方法。数据版本控制是解决此问题的另一种方法。

版本控制的设计思路是： - 每个交易都可以同时修改相同的数据 - 每笔交易都有自己的数据副本（或版本） - 如果2个事务修改了相同的数据，则仅接受一个修改，而另一个则被拒绝，并且关联的事务将回滚（并可能重新运行）。

由于以下原因，它提高了性能： - 读事务不会阻止写事务 - 写事务不会阻止读事务 - “胖而慢”的锁管理器没有超额 开销 一切都比*仅使用锁*好，除非两个事务写入相同的数据。此外，您可能很快会面临巨大的磁盘空间开销。

数据版本控制和锁定是两个不同的版本：乐观锁定与悲观锁定。他们都有优点和缺点；这实际上取决于具体的CASE（更多的读取还是更多的写入）。对于数据版本控制的演示，我推荐这个关于PostgreSQL如何实现多版本并发控制的很好的演示。 http://momjian.us/main/writings/pgsql/mvcc.pdf

某些数据库，例如DB2（直到DB2 9.7）和SQL Server（快照隔离除外）仅使用锁。其他类似PostgreSQL，MySQL和Oracle同时用涉及锁和数据版本控制的混合方法。我不知道是不是有仅使用数据版本控制的数据库（如果您知道仅仅是基于纯数据版本控制的数据库，请随时告诉我）。

[2015年8月20日更新]一位读者告诉我：

Firebird和Interbase使用版本控制而没有记录锁定。
版本控制对索引产生有趣的影响：有时唯一索引包含重复项，索引可以包含的条目比表中具有行的条目多，等等。

如果您阅读了有关隔离级别不同的部分，则增加隔离级别时会增加锁的数量，因此事务等待它们的锁所浪费的时间增加了。这就是为什么大多数数据库默认情况下不使用最高隔离级别（可序列化）的原因。

与往常一样，您可以自己查看主要数据库的文档（例如MySQL，PostgreSQL或Oracle）。 https://dev.mysql.com/doc/refman/5.7/en/innodb-transaction-model.html https://www.postgresql.org/docs/9.4/static/mvcc.html https://docs.oracle.com/cd/B28359_01/server.111/b28318/consist.htm#i5337

日志管理器 Log manager

我们已经看到，为了提高性能，数据库将数据存储在内存缓冲区中。但是，如果在提交事务时服务器崩溃，则崩溃期间会丢失仍在内存中的数据，这会破坏事务的持久性。

您可以将所有内容都写在磁盘上，但是如果服务器崩溃，最终只写了一半的数据写在磁盘上，这会破坏事务的原子性。

一个事务的所有修改都必须是：撤消状态或完成状态。

要解决此问题，有两种方法：

• 影子副本/页面：每个事务都会创建自己的数据库副本（或只是数据库的一部分）并在此副本上工作。万一出错，副本将被删除。如果成功，数据库将使用文件系统技巧立即从副本刷数据到磁盘，然后删除“旧”数据。
• 事务日志：事务日志是一个存储空间。在每次将磁盘写入磁盘之前，数据库都会在事务日志上写入信息，以便在事务崩溃/取消的情况下，数据库知道如何删除（或完成）未完成的事务。

预写日志记录协议 WAL

当在涉及许多事务的大型数据库时，影子副本/页面会产生巨大的磁盘开销。 这就是为什么现代数据库使用事务日志的原因。 事务日志必须存储在稳定的存储器中。 我不会更深入地介绍存储技术，但是必须使用（至少）RAID磁盘，以防止磁盘故障。

大多数数据库（至少是Oracle，SQL Server，DB2，PostgreSQL，MySQL和SQLite）使用预写日志记录协议（WAL）处理事务日志。 WAL协议是3条规则的集合：

• 1）对数据库的每次修改都会产生一个日志记录，并且在将数据写入磁盘之前，必须将日志记录写入事务日志中。
• 2）日志记录必须按顺序写入； 事务A比事务B先发生，那么事务A要写事务B之前写入
• 3）提交事务后，必须在事务成功结束之前将提交顺序写在事务日志上。

这项工作由日志管理器完成。 很容易看出来*日志管理器*在*缓存管理器*和*数据管理器*（将数据写在磁盘上）之间，日志管理器在将每个更新/删除/创建/提交/回滚之前，将每个更新/删除/创建/提交/回滚写入事务日志。 容易吧？

错了！ 经历了所有前面步骤之后，您应该知道与数据库相关的所有内容都受到“数据库效应”的诅咒。 更大的麻烦是怎么找到一种在高性能的写入日志的方法。 如果事务日志上的写入太慢，它们将减慢一切操作。

恢复和隔离算法 ARIES

1992年，IBM研究人员“发明”了WAL的增强版本ARIES。大多数现代数据库都或多或少地使用ARIES。逻辑可能不尽相同，但ARIES背后的概念无处不在。我在“发明”两个字上加引号是因为，按照MIT的这一课程，IBM研究人员“仅写了事务恢复的良好实践”。而ARIES论文发表时我才5岁，我不在乎那些苦涩的研究人员的八卦。

实际上，在我们开始最后一个技术部分之前，跟你们讲这个八卦的原因是想让你们休息一下。

我已经阅读了有关ARIES的研究论文的大部分内容，并且发现它非常有趣！在这一部分中，我将仅向您简要介绍ARIES，但是如果您需要真正的知识，我强烈建议您阅读。 https://www.cs.berkeley.edu/~brewer/cs262/Aries.pdf  

ARIES代表：Algorithms for Recovery and Isolation Exploiting Semantics。利用语义的恢复和隔离算法

该技术的目标有两个：

• 1）写日志时表现良好
• 2）快速可靠地恢复  

数据库回滚事务有多种原因：

• 因为用户取消了
• 由于服务器或网络故障
• 因为事务破坏了数据库的完整性（例如，列具有UNIQUE约束，然而事务添加了重复项）
• 由于死锁  

有时（例如，在网络故障的情况下），数据库可以恢复事务。

那怎么可能？要回答这个问题，我们需要了解存储在日志记录中的信息。

日志

事务的每个操作（添加/删除/修改）都会生成日志。日志记录包括： - LSN：唯一的日志序列号。该LSN按时间顺序给出。这意味着，如果操作A在操作B之前发生，则日志A的LSN将低于日志B的LSN。 - TransID：产生该操作的事务的ID。 - PageID：修改后的数据在磁盘上的位置。磁盘上的最小数据量是一个页面，因此数据的位置就是包含该数据的页面的位置。 - PrevLSN：指向同一事务产生的先前日志记录的链接。 - UNDO: 取消操作影响的一种方法，例如，如果操作是更新，则UNDO将存储更新前已更新元素的值/状态（物理UNDO），或者存储反向操作以返回到先前状态（逻辑UNDO）**。 - REDO:重新执行操作的一种方式，同样，有两种方法可以做到这一点。您可以在操作之后存储元素的值/状态，或者在操作本身中存储元素以重播它。 - 其他…：（例如，ARIES日志一般还有另外两个字段：UndoNxtLSN和Type）。

此外，磁盘上的每个页面（用于存储数据，而不是日志）具有修改数据的最后操作的日志记录（LSN）的ID。

*给出LSN的方式更加复杂，因为它与日志的存储方式相关。但是思路仍然是一样的。

ARIES一般仅使用逻辑UNDO，因为处理物理UNDO真是一团糟。

注意：据我所知，只有PostgreSQL没有使用UNDO。相反，它使用垃圾收集器守护程序来删除旧版本的数据。这与PostgreSQL中数据版本控制的实现有关。

为了给您一个更好理解，以下是查询UPDATE FROM PERSON SET AGE = 18;生成的日志记录的直观示例。 假设此查询是在*事务18*中执行的。 person表有几条记录，其中有个age=68,一个age=28

每个日志都有一个唯一的LSN。 链接的日志属于同一事务。 日志按时间顺序链接（链接列表的最后一个日志是最后一个操作的日志）。

日志缓冲区

为避免日志写入成为主要瓶颈，使用了日志缓冲区。

当SQL查询要修改数据时：

• 1）缓存管理器将修改存储在其缓冲区中。
• 2）日志管理器将关联的日志存储在其缓冲区中。
• 3）在这一步，查询执行者认为操作已完成（因此可以要求其他修改）
• 4）然后（稍后），日志管理器将日志写入事务日志中。 何时写入日志由算法决定。
• 5）然后（稍后），缓存管理器将修改内容写入磁盘。 何时将数据写入磁盘的决定由算法决定。

当我们说事务提交了，这意味着对于事务中的每个操作，都必须完成步骤1、2、3、4、5。写入事务日志的速度很快，因为它只是“在事务日志中的某处添加一个日志”，而将数据写入磁盘则更为复杂，因为它是“写入数据以方便下次快速读取它们的方式”。

假装和强制策略

出于性能方面的考虑，第5步可能会在提交后执行，因为即使发生崩溃仍然可以使用REDO日志恢复交易。这称为无强制政策。

数据库可以选择一个FORCE策略（即必须在提交之前执行步骤5）以降低恢复期间的工作量。

另一个问题是选择将数据逐步写入磁盘（假装STEAL策略）还是缓冲区管理器是否需要等到提交顺序一次写入所有内容（NO-STEAL）。在STEAL和NO-STEAL之间进行选择取决于您想要的：使用UNDO日志进行长时间恢复的快速写入还是快速恢复？  

以下是这些策略对恢复的影响的摘要：

• UNDO和REDO 都需要STEAL/NO-FORCE：最高的性能，但提供更复杂的日志和恢复过程（如ARIES）。这是大多数数据库做出的选择。注意：我在多个研究论文和课程中都读到了这一事实，但在官方文档中却找不到。
• 只有 UNDO 需要 STEAL/ FORCE.
• 只有 REDO 需要 STEAL/ FORCE.
• 不需要 STEAL/ FORCE：最差的性能和大量的内存ram。

恢复部分 好的，我们有不错的日志，让我们使用它们！

假设公司新来了一个实习生把数据库搞崩溃了（规则1：这总是实习生的错）。您重新启动数据库，恢复过程开始。

ARIES通过三个步骤从崩溃中恢复：

• 1）分析阶段：恢复过程读取完整的事务日志，以重新创建崩溃期间发生的事情的时间表。它确定要回滚的事务（所有没有commit order的事务都将回滚）以及崩溃时需要将哪些数据写入磁盘。

• 2）redo阶段：此过通过上一步*分析阶段*中确定的日志记录开始，并使用REDO将数据库更新为崩溃前的状态。

  在重做阶段，将按时间顺序处理REDO日志（使用LSN）。

  对于每个日志，恢复过程都会读取磁盘上包含要修改页面的LSN。

  如果LSN（page_on_disk）> = LSN（log_record），则意味着数据已在崩溃之前被写入磁盘（但是该值已被日志之后和崩溃之前发生的操作所覆盖），因此什么也不做。

  如果LSN（page_on_disk）<LSN（log_record），则更新磁盘上的页面。

  即使对于要回滚的事务，redo也能完成它，因为它恢复起来很容易（但是我敢肯定，现代数据库不会这样做）。

3）undo阶段：此阶段会回退崩溃时所有未完成的事务。回滚从每个事务的最后一个日志开始，并以反时间顺序（使用日志记录的PrevLSN）处理UNDO日志。

在整个恢复过程中，必须要重视：事务日志有关恢复过程的操作必须保证磁盘上写入的数据与事务日志中写入的数据同步（注：防止正在恢复的时候又crash了）。一个可能的解决方案是删除正在撤消的交易的日志记录，但这非常困难。相反，ARIES将补偿日志写入事务日志中，该日志将逻辑删除要删除的事务的日志记录。

当“手动”取消事务或由锁定管理器取消的事务（例如：死锁）或仅由于网络故障而取消事务时，则不需要*分析阶段*。实际上，有关REDO和UNDO内容的信息可在2个内存表中找到：

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

这些表由缓存管理器和事务管理器针对每个新事务事件进行更新。由于它们在内存中，因此在数据库崩溃时会被销毁。

分析阶段的工作是，崩溃后使用事务日志中的信息重新创建两个表。 *为了加快分析过程，ARIES提供了检查点的概念。这样做的想法是不时在磁盘上写入事务表，脏页表的内容以及该写入时的最后一个LSN的内容，以便在分析过程中仅分析该LSN之后的日志。

总结一下

在写这篇文章之前，我知道这个主题有多大，而且我知道写一篇深入的文章还需要时间。一开始我非常乐观但实际上我花了比预期多两倍的时间，不过学到了很多东西。

如果您想对数据库有一个很好的了解，我建议阅读研究论文“数据库系统的体系结构”。http://db.cs.berkeley.edu/papers/fntdb07-architecture.pdf ,这是一本很好的数据库介绍（110页），并且是非CS人士可读的。本文为我找到本文的计划提供了很多帮助，它不像我的文章那样关注数据结构和算法，而是更多地关注体系结构概念。

  回到我们这篇文章，

如果仔细阅读本文，您现在应该了解数据库的功能。由于这是一篇很长的文章，所以让我回顾下我们都学了什么：

• B+Tree索引概述
• 数据库的全局概述
• 基于成本的优化概述，重点关注join运算符
• 缓冲池管理概述
• 事务管理概述

但是数据库包含了更多的智慧。例如，我没有谈论一些棘手的问题，例如：

• 如何管理集群数据库和全局事务
• 当数据库仍在运行时如何创建快照
• 如何有效地存储（和压缩）数据
• 如何管理内存  

因此，当您不得不在野性的NoSQL数据库和坚如磐石的关系数据库之间进行选择时，请三思而后行。别误会，有些NoSQL数据库很棒。但是他们还很年轻，正在解决一些应用程序的特定问题。  

总而言之，如果有人问您数据库的工作原理，你不用再跑掉了，而试着告诉他，这是一个：magic

或者，您可以给他/她这篇文章。

本篇文章分以下章节，当前最后一节：

1. 引言
2. 时间复杂度
3. 合并排序
4. 数组.树.哈希表
5. 客户端管理
6. SQL查询
7. 数据管理