如果有人问你数据库的原理，叫他看这篇文章(2)
哪个算法最好？
如果有最好的，就没必要弄那么多种类型了。这个问题很难，因为很多因素都要考虑，比如：
- 空闲内存 ：没有足够的内存的话就跟强大的哈希联接拜拜吧（至少是完全内存中哈希联接）。
- 两个数据集的大小 。比如，如果一个大表联接一个很小的表，那么嵌套循环联接就比哈希联接快，因为后者有创建哈希的高昂成本；如果两个表都非常大，那么嵌套循环联接CPU成本就很高昂。
- 是否有索引 ：有两个 B+树索引的话，聪明的选择似乎是合并联接。
- 结果是否需要排序 ：即使你用到的是未排序的数据集，你也可能想用成本较高的合并联接（带排序的），因为最终得到排序的结果后，你可以把它和另一个合并联接串起来（或者也许因为查询用 ORDER BY/GROUP BY/DISTINCT 等操作符隐式或显式地要求一个排序结果）。
- 关系是否已经排序 ：这时候合并联接是最好的候选项。
- 联接的类型：是 等值联接 （比如 tableA.col1 = tableB.col2 ）？ 还是 内联接 ？ 外联接 ？ 笛卡尔乘积 ？或者 自联接 ？有些联接在特定环境下是无法工作的。
- 数据的分布 ：如果联接条件的数据是 倾斜的 （比如根据姓氏来联接人，但是很多人同姓），用哈希联接将是个灾难，原因是哈希函数将产生分布极不均匀的哈希桶。
- 如果你希望联接操作使用 多线程或多进程 。
想要更详细的信息，可以阅读DB2, [ORACLE](http://docs.oracle.com/cd/B28359_01/server.111/b28274/optimops.htm# i76330) 或 SQL Server)的文档。
简化的例子
我们已经研究了 3 种类型的联接操作。
现在，比如说我们要联接 5 个表，来获得一个人的全部信息。一个人可以有：
- 多个手机号（MOBILES）
- 多个邮箱（MAILS）
- 多个地址（ADRESSES）
- 多个银行账号（BANK_ACCOUNTS）
换句话说，我们需要用下面的查询快速得到答案：
MySQL
SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTSWHEREPERSON.PERSON_ID = MOBILES.PERSON_IDAND PERSON.PERSON_ID = MAILS.PERSON_IDAND PERSON.PERSON_ID = ADRESSES.PERSON_IDAND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID作为一个查询优化器，我必须找到处理数据最好的方法。但有 2 个问题：
每个联接使用那种类型？
每个联接使用那种类型？
我有 3 种可选（哈希、合并、嵌套），同时可能用到 0, 1 或 2 个索引（不必说还有多种类型的索引）。按什么顺序执行联接？
按什么顺序执行联接？
比如，下图显示了针对 4 个表仅仅 3 次联接，可能采用的执行计划：
那么下面就是我可能采取的方法：
采取粗暴的方式
采取粗暴的方式
用数据库统计， 计算每种可能的执行计划的成本 ，保留最佳方案。但是，会有很多可能性。对于一个给定顺序的联接操作，每个联接有三种可能性：哈希、合并、嵌套，那么总共就有 3^4 种可能性。确定联接的顺序是个二叉树的排列问题，会有 (24)!/(4+1)! 种可能的顺序。对本例这个相当简化了的问题，我最后会得到 3^4(2*4)!/(4+1)! 种可能。采取粗暴的方式
用数据库统计， 计算每种可能的执行计划的成本 ，保留最佳方案。但是，会有很多可能性。对于一个给定顺序的联接操作，每个联接有三种可能性：哈希、合并、嵌套，那么总共就有 3^4 种可能性。确定联接的顺序是个二叉树的排列问题，会有 (24)!/(4+1)! 种可能的顺序。对本例这个相当简化了的问题，我最后会得到 3^4(2*4)!/(4+1)! 种可能。
抛开专业术语，那相当于 27,216 种可能性。如果给合并联接加上使用 0,1 或 2 个 B+树索引，可能性就变成了 210,000种。我是不是告诉过你这个查询其实 非常简单 吗？
我大叫一声辞了这份工作
我大叫一声辞了这份工作
很有诱惑力，但是这样一来，你不会的到查询结果，而我需要钱来付账单。
我只尝试几种执行计划，挑一个成本最低的。
我只尝试几种执行计划，挑一个成本最低的。
由于不是超人，我不能算出所有计划的成本。相反，我可以 武断地从全部可能的计划中选择一个子集 ，计算它们的成本，把最佳的计划给你。
我用聪明的 规则来降低可能性的数量 有两种规则：
我用聪明的 规则来降低可能性的数量 有两种规则：
我可以用『逻辑』规则，它能去除无用的可能性，但是无法过滤大量的可能性。比如： 『嵌套联接的内关系必须是最小的数据集』。我用聪明的 规则来降低可能性的数量 有两种规则：
我可以用『逻辑』规则，它能去除无用的可能性，但是无法过滤大量的可能性。比如： 『嵌套联接的内关系必须是最小的数据集』。
我接受现实，不去找最佳方案，用更激进的规则来大大降低可能性的数量。比如：『如果一个关系很小，使用嵌套循环联接，绝不使用合并或哈希联接。』
在这个简单的例子中，我最后得到很多可能性。但 现实世界的查询还会有其他关系运算符 ，像 OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT … 这意味着更多的可能性。
那么，数据库是如何处理的呢？
动态编程，贪婪算法和启发式算法
关系型数据库会尝试我刚刚提到的多种方法，优化器真正的工作是在有限时间里找到一个好的解决方案。
多数时候，优化器找到的不是最佳的方案，而是一个『不错』的
对于小规模的查询，采取粗暴的方式是有可能的。但是为了让中等规模的查询也能采取粗暴的方式，我们有办法避免不必要的计算，这就是 动态编程 。
动态编程
这几个字背后的理念是，很多执行计划是非常相似的。看看下图这几种计划：
它们都有相同的子树（A JOIN B），所以，不必在每个计划中计算这个子树的成本，计算一次，保存结果，当再遇到这个子树时重用。用更正规的说法，我们面对的是个重叠问题。为了避免对部分结果的重复计算，我们使用记忆法。
对于计算机极客，下面是我在先前给你的教程里找到的一个算法。我不提供解释，所以仅在你已经了解动态编程或者精通算法的情况下阅读（我提醒过你哦）：
procedure findbestplan(S)if (bestplan[S].cost infinite) return bestplan[S]// else bestplan[S] has not been computed earlier, compute it nowif (S contains only 1 relation) set bestplan[S].plan and bestplan[S].cost based on the best way of accessing S /* Using selections on S and indices on S */ else for each non-empty subset S1 of S such that S1 != S P1= findbestplan(S1) P2= findbestplan(S - S1) A = best algorithm for joining results of P1 and P2 cost = P1.cost + P2.cost + cost of A if cost 『对非常大的表来说，数据库通常使用直接路径来读取，即直接加载区块[……]，来避免填满缓冲区。对于中等大小的表，数据库可以使用直接读取或缓存读取。如果选择缓存读取，数据库把区块置于LRU的尾部，防止清空当前缓冲区。』还有一些可能，比如使用高级版本的LRU，叫做 LRU-K。例如，SQL Server 使用 LRU-2。这个算法的原理是把更多的历史记录考虑进来。简单LRU（也就是 LRU-1），只考虑最后一次使用的数据。LRU-K呢：- 考虑数据 最后第K次使用的情况 - 数据使用的次数 加进了权重 - 一批新数据加载进入缓存，旧的但是经常使用的数据不会被清除（因为权重更高）- 但是这个算法不会保留缓存中不再使用的数据- 所以 数据如果不再使用，权重值随着时间推移而降低 计算权重是需要成本的，所以SQL Server只是使用 K=2，这个值性能不错而且额外开销可以接受。关于LRU-K更深入的知识，可以阅读早期的研究论文（1993）：[数据库磁盘缓冲的LRU-K页面置换算法](http://www.cs.cmu.edu/~christos/courses/721-resources/p297-o_neil.pdf)其他算法当然还有其他管理缓存的算法，比如：- 2Q（类LRU-K算法）- CLOCK（类LRU-K算法）- MRU（最新使用的算法，用LRU同样的逻辑但不同的规则）- LRFU（Least Recently and Frequently Used，最近最少使用最近最不常用）- ……#### 写缓冲区我只探讨了读缓存 —— 在使用之前预先加载数据。用来保存数据、成批刷入磁盘，而不是逐条写入数据从而造成很多单次磁盘访问。要记住，缓冲区保存的是 页 （最小的数据单位）而不是行（逻辑上/人类习惯的观察数据的方式）。缓冲池内的页如果被修改了但还没有写入磁盘，就是 脏页 。有很多算法来决定写入脏页的最佳时机，但这个问题与事务的概念高度关联，下面我们就谈谈事务。### 事务管理器最后但同样重要的，是事务管理器，我们将看到这个进程是如何保证每个查询在自己的事务内执行的。但开始之前，我们需要理解ACID事务的概念。#### “I’m on acid”一个ACID事务是一个 工作单元 ，它要保证4个属性：- 原子性 （ A tomicity）: 事务『要么全部完成，要么全部取消』，即使它持续运行10个小时。如果事务崩溃，状态回到事务之前（事务回滚）。- 隔离性 （ I solation）: 如果2个事务 A 和 B 同时运行，事务 A 和 B 最终的结果是相同的，不管 A 是结束于 B 之前/之后/运行期间。- 持久性 （ D urability）: 一旦事务 提交 （也就是成功执行）,不管发生什么（崩溃或者出错），数据要保存在数据库中。- 一致性 （ C onsistency）: 只有合法的数据（依照关系约束和函数约束）能写入数据库，一致性与原子性和隔离性有关。在同一个事务内，你可以运行多个SQL查询来读取、创建、更新和删除数据。当两个事务使用相同的数据，麻烦就来了。经典的例子是从账户A到账户B的汇款。假设有2个事务：- 事务1（T1）从账户A取出100美元给账户B- 事务2（T2）从账户A取出50美元给账户B我们回来看看 ACID 属性：- 原子性 确保不管 T1 期间发生什么（服务器崩溃、网络中断…），你不能出现账户A 取走了100美元但没有给账户B 的现象（这就是数据不一致状态）。- 隔离性 确保如果 T1 和 T2 同时发生，最终A将减少150美元，B将得到150美元，而不是其他结果，比如因为 T2 部分抹除了 T1 的行为，A减少150美元而B只得到50美元（这也是不一致状态）。- 持久性 确保如果 T1 刚刚提交，数据库就发生崩溃，T1 不会消失得无影无踪。- 一致性 确保钱不会在系统内生成或灭失。[以下部分不重要，可以跳过]现代数据库不会使用纯粹的隔离作为默认模式，因为它会带来巨大的性能消耗。SQL一般定义4个隔离级别：- 串行化 (Serializable，SQLite默认模式）：最高级别的隔离。两个同时发生的事务100%隔离，每个事务有自己的『世界』。- 可重复读 （Repeatable read，MySQL默认模式）：每个事务有自己的『世界』，除了一种情况。如果一个事务成功执行并且添加了新数据，这些数据对其他正在执行的事务是可见的。但是如果事务成功修改了一条数据，修改结果对正在运行的事务不可见。所以，事务之间只是在新数据方面突破了隔离，对已存在的数据仍旧隔离。 可重复读 （Repeatable read，MySQL默认模式）：每个事务有自己的『世界』，除了一种情况。如果一个事务成功执行并且添加了新数据，这些数据对其他正在执行的事务是可见的。但是如果事务成功修改了一条数据，修改结果对正在运行的事务不可见。所以，事务之间只是在新数据方面突破了隔离，对已存在的数据仍旧隔离。 举个例子，如果事务A运行”SELECT count(1) from TABLE_X” ，然后事务B在 TABLE_X 加入一条新数据并提交，当事务A再运行一次 count(1)结果不会是一样的。 可重复读 （Repeatable read，MySQL默认模式）：每个事务有自己的『世界』，除了一种情况。如果一个事务成功执行并且添加了新数据，这些数据对其他正在执行的事务是可见的。但是如果事务成功修改了一条数据，修改结果对正在运行的事务不可见。所以，事务之间只是在新数据方面突破了隔离，对已存在的数据仍旧隔离。 举个例子，如果事务A运行”SELECT count(1) from TABLE_X” ，然后事务B在 TABLE_X 加入一条新数据并提交，当事务A再运行一次 count(1)结果不会是一样的。 这叫 幻读 （phantom read）。- 读取已提交 （Read committed，Oracle、PostgreSQL、SQL Server默认模式）：可重复读+新的隔离突破。如果事务A读取了数据D，然后数据D被事务B修改（或删除）并提交，事务A再次读取数据D时数据的变化（或删除）是可见的。 读取已提交 （Read committed，Oracle、PostgreSQL、SQL Server默认模式）：可重复读+新的隔离突破。如果事务A读取了数据D，然后数据D被事务B修改（或删除）并提交，事务A再次读取数据D时数据的变化（或删除）是可见的。 这叫 不可重复读 （non-repeatable read）。- 读取未提交 （Read uncommitted）：最低级别的隔离，是读取已提交+新的隔离突破。如果事务A读取了数据D，然后数据D被事务B修改（但并未提交，事务B仍在运行中），事务A再次读取数据D时，数据修改是可见的。如果事务B回滚，那么事务A第二次读取的数据D是无意义的，因为那是事务B所做的从未发生的修改（已经回滚了嘛）。 读取未提交 （Read uncommitted）：最低级别的隔离，是读取已提交+新的隔离突破。如果事务A读取了数据D，然后数据D被事务B修改（但并未提交，事务B仍在运行中），事务A再次读取数据D时，数据修改是可见的。如果事务B回滚，那么事务A第二次读取的数据D是无意义的，因为那是事务B所做的从未发生的修改（已经回滚了嘛）。 这叫 脏读 （dirty read）。多数数据库添加了自定义的隔离级别（比如 PostgreSQL、Oracle、SQL Server的快照隔离），而且并没有实现SQL规范里的所有级别（尤其是读取未提交级别）。默认的隔离级别可以由用户/开发者在建立连接时覆盖（只需要增加很简单的一行代码）。#### 并发控制确保隔离性、一致性和原子性的真正问题是 对相同数据的写操作 （增、更、删）：- 如果所有事务只是读取数据，它们可以同时工作，不会更改另一个事务的行为。- 如果（至少）有一个事务在修改其他事务读取的数据，数据库需要找个办法对其它事务隐藏这种修改。而且，它还需要确保这个修改操作不会被另一个看不到这些数据修改的事务擦除。这个问题叫 并发控制 。最简单的解决办法是依次执行每个事务（即顺序执行），但这样就完全没有伸缩性了，在一个多处理器/多核服务器上只有一个核心在工作，效率很低。理想的办法是，每次一个事务创建或取消时：- 监控所有事务的所有操作- 检查是否2个（或更多）事务的部分操作因为读取/修改相同的数据而存在冲突- 重新编排冲突事务中的操作来减少冲突的部分- 按照一定的顺序执行冲突的部分（同时非冲突事务仍然在并发运行）- 考虑事务有可能被取消用更正规的说法，这是对冲突的调度问题。更具体点儿说，这是个非常困难而且CPU开销很大的优化问题。企业级数据库无法承担等待几个小时，来寻找每个新事务活动最好的调度，因此就使用不那么理想的方式以避免更多的时间浪费在解决冲突上。#### 锁管理器为了解决这个问题，多数数据库使用 锁 和/或 数据版本控制 。这是个很大的话题，我会集中探讨锁，和一点点数据版本控制。##### 悲观锁原理是：- 如果一个事务需要一条数据- 它就把数据锁住- 如果另一个事务也需要这条数据- 它就必须要等第一个事务释放这条数据 它就必须要等第一个事务释放这条数据 这个锁叫 排他锁 。但是对一个仅仅读取数据的事务使用排他锁非常昂贵，因为 这会迫使其它只需要读取相同数据的事务等待 。因此就有了另一种锁， 共享锁 。共享锁是这样的：- 如果一个事务只需要读取数据A- 它会给数据A加上『共享锁』并读取- 如果第二个事务也需要仅仅读取数据A- 它会给数据A加上『共享锁』并读取- 如果第三个事务需要修改数据A- 它会给数据A加上『排他锁』，但是必须等待另外两个事务释放它们的共享锁。同样的，如果一块数据被加上排他锁，一个只需要读取该数据的事务必须等待排他锁释放才能给该数据加上共享锁。锁管理器是添加和释放锁的进程，在内部用一个哈希表保存锁信息（关键字是被锁的数据），并且了解每一块数据是：- 被哪个事务加的锁- 哪个事务在等待数据解锁##### 死锁但是使用锁会导致一种情况，2个事务永远在等待一块数据：##### 在本图中：- 事务A 给 数据1 加上排他锁并且等待获取数据2- 事务B 给 数据2 加上排他锁并且等待获取数据1这叫 死锁 。在死锁发生时，锁管理器要选择取消（回滚）一个事务，以便消除死锁。这可是个艰难的决定：- 杀死数据修改量最少的事务（这样能减少回滚的成本）？- 杀死持续时间最短的事务，因为其它事务的用户等的时间更长？- 杀死能用更少时间结束的事务（避免可能的资源饥荒）？- 一旦发生回滚，有多少事务会受到回滚的影响？在作出选择之前，锁管理器需要检查是否有死锁存在。哈希表可以看作是个图表（见上文图），图中出现循环就说明有死锁。由于检查循环是昂贵的（所有锁组成的图表是很庞大的），经常会通过简单的途径解决：使用 超时设定 。如果一个锁在超时时间内没有加上，那事务就进入死锁状态。锁管理器也可以在加锁之前检查该锁会不会变成死锁，但是想要完美的做到这一点还是很昂贵的。因此这些预检经常设置一些基本规则。两段锁实现纯粹的隔离 最简单的方法 是：事务开始时获取锁，结束时释放锁。就是说，事务开始前必须等待确保自己能加上所有的锁，当事务结束时释放自己持有的锁。这是行得通的，但是为了等待所有的锁， 大量的时间被浪费了 。更快的方法是 两段锁协议 （Two-Phase Locking Protocol ， 由 DB2 和 SQL Server使用），在这里，事务分为两个阶段：- 成长阶段 ：事务可以获得锁，但不能释放锁。- 收缩阶段 ：事务可以释放锁（对于已经处理完而且不会再次处理的数据），但不能获得新锁。这两条简单规则背后的原理是：- 释放不再使用的锁，来降低其它事务的等待时间- 防止发生这类情况：事务最初获得的数据，在事务开始后被修改，当事务重新读取该数据时发生不一致。这个规则可以很好地工作，但有个例外：如果修改了一条数据、释放了关联的锁后，事务被取消（回滚），而另一个事务读到了修改后的值，但最后这个值却被回滚。为了避免这个问题， 所有独占锁必须在事务结束时释放 。多说几句当然了，真实的数据库使用更复杂的系统，涉及到更多类型的锁（比如意向锁，intention locks）和更多的粒度（行级锁、页级锁、分区锁、表锁、表空间锁），但是道理是相同的。我只探讨纯粹基于锁的方法， 数据版本控制是解决这个问题的另一个方法 。版本控制是这样的：- 每个事务可以在相同时刻修改相同的数据- 每个事务有自己的数据拷贝（或者叫版本）- 如果2个事务修改相同的数据，只接受一个修改，另一个将被拒绝，相关的事务回滚（或重新运行）这将提高性能，因为：- 读事务不会阻塞写事务 - 写事务不会阻塞读 - 没有『臃肿缓慢』的锁管理器带来的额外开销除了两个事务写相同数据的时候，数据版本控制各个方面都比锁表现得更好。只不过，你很快就会发现磁盘空间消耗巨大。数据版本控制和锁机制是两种不同的见解： 乐观锁和悲观锁 。两者各有利弊，完全取决于使用场景（读多还是写多）。关于数据版本控制，我推荐[这篇非常优秀的文章](http://momjian.us/main/writings/pgsql/mvcc.pdf)，讲的是PostgreSQL如何实现多版本并发控制的。一些数据库，比如DB2（直到版本 9.7）和 SQL Server（不含快照隔离）仅使用锁机制。其他的像PostgreSQL, MySQL 和 Oracle 使用锁和鼠标版本控制混合机制。我不知道是否有仅用版本控制的数据库（如果你知道请告诉我）。[2015-08-20更新]一名读者告诉我：> Firebird 和 Interbase 用不带锁的版本控制。>> 版本控制对索引的影响挺有趣的：有时唯一索引会出现重复，索引的条目会多于表行数，等等。如果你读过不同级别的隔离那部分内容，你会知道，提高隔离级别就会增加锁的数量和事务等待加锁的时间。这就是为什么多数数据库默认不会使用最高级别的隔离（即串行化）。当然，你总是可以自己去主流数据库（像[MySQL](http://dev.mysql.com/doc/refman/5.7/en/innodb-transaction-model.html), [PostgreSQL](http://www.postgresql.org/docs/9.4/static/mvcc.html) 或 [Oracle](http://docs.oracle.com/cd/B28359_01/server.111/b28318/consist.htm# i5337)）的文档里查一下。日志管理器我们已经知道，为了提升性能，数据库把数据保存在内存缓冲区内。但如果当事务提交时服务器崩溃，崩溃时还在内存里的数据会丢失，这破坏了事务的 持久性 。你可以把所有数据都写在磁盘上，但是如果服务器崩溃，最终数据可能只有部分写入磁盘，这破坏了事务的 原子性 。 事务作出的任何修改必须是或者撤销，或者完成。 有 2 个办法解决这个问题：- 影子副本/页 （Shadow copies/pages）：每个事务创建自己的数据库副本（或部分数据库的副本），并基于这个副本来工作。一旦出错，这个副本就被移除；一旦成功，数据库立即使用文件系统的一个把戏，把副本替换到数据中，然后删掉『旧』数据。- 事务日志 （Transaction log）：事务日志是一个存储空间，在每次写盘之前，数据库在事务日志中写入一些信息，这样当事务崩溃或回滚，数据库知道如何移除或完成尚未完成的事务。##### WAL（预写式日志）影子副本/页在运行较多事务的大型数据库时制造了大量磁盘开销，所以现代数据库使用 事务日志 。事务日志必须保存在 稳定的存储 上，我不会深挖存储技术，但至少RAID磁盘是必须的，以防磁盘故障。多数数据库（至少是Oracle, [SQL Server](https://technet.microsoft.com/en-us/library/ms186259(v=sql.105).aspx), [DB2](http://www.ibm.com/developerworks/data/library/techarticle/0301kline/0301kline.html), [PostgreSQL](http://www.postgresql.org/docs/9.4/static/wal.html), MySQL 和 [SQLite](https://www.sqlite.org/wal.html)) 使用 预写日志协议 （Write-Ahead Logging protocol ，WAL）来处理事务日志。WAL协议有 3 个规则：- 1) 每个对数据库的修改都产生一条日志记录，在数据写入磁盘之前日志记录必须写入事务日志。- 2) 日志记录必须按顺序写入；记录 A 发生在记录 B 之前，则 A 必须写在 B 之前。- 3) 当一个事务提交时，在事务成功之前，提交顺序必须写入到事务日志。这个工作由日志管理器完成。简单的理解就是，日志管理器处于缓存管理器（cache manager）和数据访问管理器（data access manager，负责把数据写入磁盘）之间，每个 update / delete / create / commit / rollback 操作在写入磁盘之前先写入事务日志。简单，对吧？回答错误！ 我们研究了这么多内容，现在你应该知道与数据库相关的每一件事都带着『数据库效应』的诅咒。好吧，我们说正经的，问题在于，如何找到写日志的同时保持良好的性能的方法。如果事务日志写得太慢，整体都会慢下来。ARIES1992年，IBM 研究人员『发明』了WAL的增强版，叫 ARIES。ARIES 或多或少地在现代数据库中使用，逻辑未必相同，但AIRES背后的概念无处不在。我给发明加了引号是因为，按照[MIT这门课](http://db.csail.mit.edu/6.830/lectures/lec15-notes.pdf)的说法，IBM 的研究人员『仅仅是写了事务恢复的最佳实践方法』。AIRES 论文发表的时候我才 5 岁，我不关心那些酸溜溜的科研人员老掉牙的闲言碎语。事实上，我提及这个典故，是在开始探讨最后一个技术点前让你轻松一下。我阅读过[这篇 ARIES 论文](http://www.cs.berkeley.edu/~brewer/cs262/Aries.pdf) 的大量篇幅，发现它很有趣。在这一部分我只是简要的谈一下 ARIES，不过我强烈建议，如果你想了解真正的知识，就去读那篇论文。ARIES 代表『数据库恢复原型算法』（ A lgorithms for R ecovery and I solation E xploiting S emantics）。这个技术要达到一个双重目标：- 1) 写日志的同时保持良好性能 - 2) 快速和 可靠的数据恢复 有多个原因让数据库不得不回滚事务：- 因为用户取消- 因为服务器或网络故障- 因为事务破坏了数据库完整性（比如一个列有唯一性约束而事务添加了重复值）- 因为死锁有时候（比如网络出现故障），数据库可以恢复事务。这怎么可能呢？为了回答这个问题，我们需要了解日志里保存的信息。##### 日志 事务的每一个操作（增/删/改）产生一条日志 ，由如下内容组成：- LSN ：一个唯一的日志序列号（ Log Sequence Number ）。LSN是按时间顺序分配的 * ，这意味着如果操作 A 先于操作 B，log A 的 LSN 要比 log B 的 LSN 小。- TransID ：产生操作的事务ID。- PageID ：被修改的数据在磁盘上的位置。磁盘数据的最小单位是页，所以数据的位置就是它所处页的位置。- PrevLSN ：同一个事务产生的上一条日志记录的链接。- UNDO ：取消本次操作的方法。 UNDO ：取消本次操作的方法。 比如，如果操作是一次更新，UNDO将或者保存元素更新前的值/状态（物理UNDO），或者回到原来状态的反向操作（逻辑UNDO） 。- REDO ：重复本次操作的方法。 同样的，有 2 种方法：或者保存操作后的元素值/状态，或者保存操作本身以便重复。- …：（供您参考，一个 ARIES 日志还有 2 个字段：UndoNxtLSN 和 Type）。进一步说，磁盘上每个页（保存数据的，不是保存日志的）都记录着最后一个修改该数据操作的LSN。*LSN的分配其实更复杂，因为它关系到日志存储的方式。但道理是相同的。 ARIES 只使用逻辑UNDO，因为处理物理UNDO太过混乱了。注：据我所知，只有 PostgreSQL 没有使用UNDO，而是用一个垃圾回收服务来删除旧版本的数据。这个跟 PostgreSQL 对数据版本控制的实现有关。为了更好的说明这一点，这有一个简单的日志记录演示图，是由查询 “UPDATE FROM PERSON SET AGE = 18;” 产生的，我们假设这个查询是事务18执行的。*【译者注： SQL 语句原文如此，应该是作者笔误 】*每条日志都有一个唯一的LSN，链接在一起的日志属于同一个事务。日志按照时间顺序链接（链接列表的最后一条日志是最后一个操作产生的）。##### 日志缓冲区为了防止写日志成为主要的瓶颈，数据库使用了 日志缓冲区 。当查询执行器要求做一次修改：- 1) 缓存管理器将修改存入自己的缓冲区；- 2) 日志管理器将相关的日志存入自己的缓冲区；- 3) 到了这一步，查询执行器认为操作完成了（因此可以请求做另一次修改）；- 4) 接着（不久以后）日志管理器把日志写入事务日志，什么时候写日志由某算法来决定。- 5) 接着（不久以后）缓存管理器把修改写入磁盘，什么时候写盘由某算法来决定。 当事务提交，意味着事务每一个操作的 1 2 3 4 5 步骤都完成了 。写事务日志是很快的，因为它只是『在事务日志某处增加一条日志』；而数据写盘就更复杂了，因为要用『能够快速读取的方式写入数据』。##### STEAL 和 FORCE 策略出于性能方面的原因， 第 5 步有可能在提交之后完成 ，因为一旦发生崩溃，还有可能用REDO日志恢复事务。这叫做 NO-FORCE策略 。数据库可以选择FORCE策略（比如第 5 步在提交之前必须完成）来降低恢复时的负载。另一个问题是，要选择 数据是一步步的写入（STEAL策略） ，还是缓冲管理器需要等待提交命令来一次性全部写入（NO-STEAL策略）。选择STEAL还是NO-STEAL取决于你想要什么：快速写入但是从 UNDO 日志恢复缓慢，还是快速恢复。总结一下这些策略对恢复的影响：- STEAL/NO-FORCE 需要 UNDO 和 REDO: 性能高 ，但是日志和恢复过程更复杂 (比如 ARIES)。 多数数据库选择这个策略 。 注：这是我从多个学术论文和教程里看到的，但并没有看到官方文档里显式说明这一点。- STEAL/ FORCE 只需要 UNDO.- NO-STEAL/NO-FORCE 只需要 REDO.- NO-STEAL/FORCE 什么也不需要: 性能最差 ，而且需要巨大的内存。##### 关于恢复Ok，有了不错的日志，我们来用用它们！假设新来的实习生让数据库崩溃了（首要规矩：永远是实习生的错。），你重启了数据库，恢复过程开始了。ARIES从崩溃中恢复有三个阶段：- 1) 分析阶段 ：恢复进程读取全部事务日志，来重建崩溃过程中所发生事情的时间线，决定哪个事务要回滚（所有未提交的事务都要回滚）、崩溃时哪些数据需要写盘。- 2) Redo阶段 ：这一关从分析中选中的一条日志记录开始，使用 REDO 来将数据库恢复到崩溃之前的状态。在REDO阶段，REDO日志按照时间顺序处理（使用LSN）。对每一条日志，恢复进程需要读取包含数据的磁盘页LSN。如果LSN（磁盘页）>= LSN（日志记录），说明数据已经在崩溃前写到磁盘（但是值已经被日志之后、崩溃之前的某个操作覆盖），所以不需要做什么。如果LSN（磁盘页）< LSN（日志记录），那么磁盘上的页将被更新。即使将被回滚的事务，REDO也是要做的，因为这样简化了恢复过程（但是我相信现代数据库不会这么做的）。- 3) Undo阶段 ：这一阶段回滚所有崩溃时未完成的事务。回滚从每个事务的最后一条日志开始，并且按照时间倒序处理UNDO日志（使用日志记录的PrevLSN）。 恢复过程中，事务日志必须留意恢复过程的操作，以便写入磁盘的数据与事务日志相一致。一个解决办法是移除被取消的事务产生的日志记录，但是这个太困难了。相反，ARIES在事务日志中记录补偿日志，来逻辑上删除被取消的事务的日志记录。当事务被『手工』取消，或者被锁管理器取消（为了消除死锁），或仅仅因为网络故障而取消，那么分析阶段就不需要了。对于哪些需要 REDO 哪些需要 UNDO 的信息在 2 个内存表中：- 事务表 （保存当前所有事务的状态）- 脏页表 （保存哪些数据需要写入磁盘）当新的事务产生时，这两个表由缓存管理器和事务管理器更新。因为是在内存中，当数据库崩溃时它们也被破坏掉了。分析阶段的任务就是在崩溃之后，用事务日志中的信息重建上述的两个表。为了加快分析阶段，ARIES提出了一个概念： 检查点（check point） ，就是不时地把事务表和脏页表的内容，还有此时最后一条LSN写入磁盘。那么在分析阶段当中，只需要分析这个LSN之后的日志即可。## 结语写这篇文章之前，我知道这个题目有多大，也知道写这样一篇深入的文章会相当耗时。最后证明我过于乐观了，实际上花了两倍于预期的时间，但是我学到了很多。如果你想很好地了解数据库，我推荐这篇研究论文：[《数据库系统架构》](http://db.cs.berkeley.edu/papers/fntdb07-architecture.pdf)，对数据库有很好的介绍（共110页），而且非计算机专业人士也能读懂。这篇论文出色的帮助我制定了本文的写作计划，它没有像本文那样专注于数据结构和算法，更多的讲了架构方面的概念。如果你仔细阅读了本文，你现在应该了解一个数据库是多么的强大了。鉴于文章很长，让我来提醒你我们都学到了什么：- B+树索引概述- 数据库的全局概述- 基于成本的优化概述，特别专注了联接运算- 缓冲池管理概述- 事务管理概述但是，数据库包含了更多的聪明巧技。比如，我并没有谈到下面这些棘手的问题：- 如何管理数据库集群和全局事务- 如何在数据库运行的时候产生快照- 如何高效地存储（和压缩）数据- 如何管理内存所以，当你不得不在问题多多的 NoSQL数据库和坚如磐石的关系型数据库之间抉择的时候，要三思而行。不要误会，某些 NoSQL数据库是很棒的，但是它们毕竟还年轻，只是解决了少量应用关注的一些特定问题。最后说一句，如果有人问你数据库的原理是什么，你不用逃之夭夭，现在你可以回答：或者，就让他/她来看本文吧。#产品经理#版权声明
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！
