对于数据库而言,重要的不是数据量,而是当数据量增加时运算如何增加。
时间复杂度用来检验某个算法处理一定量的数据要花多长时间,时间复杂度不会给出确切的运算次数,但是给出的是一种理念。
如果要处理2000条元素:
对于数据库,你需要理解这个 sort() 函数的工作原理。
归并排序是把问题拆分为小问题,通过解决小问题来解决最初的问题(注:这种算法叫分治法,即『分而治之、各个击破』),具体建议你看:算法思想 - 分治算法 和 算法思想 - 二分法。
为什么是归并排序?
数据库中查询的时间复杂度,是我们无法使用矩阵,转而使用二叉搜索树(BST)
查找一个特定值这个树挺好用,但是当你需要查找两个值之间的多个元素时,就会有大麻烦了。你的成本将是 O(N),因为你必须查找树的每一个节点,以判断它是否处于那 2 个值之间(例如,对树使用中序遍历)。而且这个操作不是磁盘I/O有利的,因为你必须读取整个树。我们需要找到高效的范围查询方法。
如果你在数据库中增加或删除一行(从而在相关的 B+树索引里):
换句话说,B+树需要自我整理和自我平衡。谢天谢地,我们有智能删除和插入。但是这样也带来了成本:在B+树中,插入和删除操作是 O(log(N)) 复杂度。所以有些人听到过使用太多索引不是个好主意这类说法。没错,你减慢了快速插入/更新/删除表中的一个行的操作,因为数据库需要以代价高昂的每索引 O(log(N)) 运算来更新表的索引。再者,增加索引意味着给事务管理器带来更多的工作负荷(在本文结尾我们会探讨这个管理器)。
当你想快速查找值时,哈希表是非常有用的。而且,理解哈希表会帮助我们接下来理解一个数据库常见的联接操作,叫做『哈希联接』。这个数据结构也被数据库用来保存一些内部的东西(比如锁表或者缓冲池,我们在下文会研究这两个概念)
为什么不用阵列呢?
我们已经了解了数据库内部的部分重要算法,现在我们需要回来看看数据库的全貌了。
数据库一般可以用如下图形来理解:
本章集中探讨数据库如何通过如下进程管理SQL查询的:
客户端管理器是处理客户端通信的。客户端可以是一个(网站)服务器或者一个最终用户或最终应用。客户端管理器通过一系列知名的API(JDBC, ODBC, OLE-DB …)提供不同的方式来访问数据库。客户端管理器也提供专有的数据库访问API。
当你连接到数据库时:
这部分是数据库的威力所在,在这部分里,一个写得糟糕的查询可以转换成一个快速执行的代码,代码执行的结果被送到客户端管理器。
这个多步骤操作过程如下:
这里我不会过多探讨最后两步,因为它们不太重要。
每一条SQL语句都要送到解析器来检查语法,如果你的查询有错,解析器将拒绝该查询。比如,如果你写成”SLECT …” 而不是 “SELECT …”,那就没有下文了。
但这还不算完,解析器还会检查关键字是否使用正确的顺序,比如 WHERE 写在 SELECT 之前会被拒绝。
然后,解析器要分析查询中的表和字段,使用数据库元数据来检查:
接着,解析器检查在查询中你是否有权限来读取(或写入)表。再强调一次:这些权限由DBA分配。
在解析过程中,SQL 查询被转换为内部表示(通常是一个树)。
如果一切正常,内部表示被送到查询重写器。
在这一步,我们已经有了查询的内部表示,重写器的目标是:
重写器按照一系列已知的规则对查询执行检测。如果查询匹配一种模式的规则,查询就会按照这条规则来重写。下面是(可选)规则的非详尽的列表:
会转换为: SELECT PERSON.* FROM PERSON, MAILS WHERE PERSON.person_key = MAILS.person_key and MAILS.mail LIKE 'christophe%';
重写后的查询接着送到优化器,这时候好玩的就开始了。
研究数据库如何优化查询之前我们需要谈谈统计,因为没有统计的数据库是愚蠢的。除非你明确指示,数据库是不会分析自己的数据的。没有分析会导致数据库做出(非常)糟糕的假设。
但是,数据库需要什么类型的信息呢?
我必须(简要地)谈谈数据库和操作系统如何保存数据。两者使用的最小单位叫做页或块(默认 4 或 8 KB)。这就是说如果你仅需要 1KB,也会占用一个页。要是页的大小为 8KB,你就浪费了 7KB。
回来继续讲统计! 当你要求数据库收集统计信息,数据库会计算下列值:
这些统计信息会帮助优化器估计查询所需的磁盘 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 的头 2 、 3 个字符就够了,这将大大减少比较的次数。
不过,这些只是基本的统计。你可以让数据库做一种高级统计,叫直方图。直方图是列值分布情况的统计信息。例如:
这些额外的统计会帮助数据库找到更佳的查询计划,尤其是对于等式谓词(例如: WHERE AGE = 18 )或范围谓词(例如: WHERE AGE > 10 and AGE < 40),因为数据库可以更好的了解这些谓词相关的数字类型数据行(注:这个概念的技术名称叫选择率)。
统计信息保存在数据库元数据内,例如(非分区)表的统计信息位置:
统计信息必须及时更新。如果一个表有 1,000,000 行而数据库认为它只有 500 行,没有比这更糟糕的了。统计唯一的不利之处是需要时间来计算,这就是为什么数据库大多默认情况下不会自动计算统计信息。数据达到百万级时统计会变得困难,这时候,你可以选择仅做基本统计或者在一个数据库样本上执行统计。
举个例子,我参与的一个项目需要处理每表上亿条数据的库,我选择只统计10%,结果造成了巨大的时间消耗。本例证明这是个糟糕的决定,因为有时候 Oracle 10G 从特定表的特定列中选出的 10% 跟全部 100% 有很大不同(对于拥有一亿行数据的表,这种情况极少发生)。这次错误的统计导致了一个本应 30 秒完成的查询最后执行了 8 个小时,查找这个现象根源的过程简直是个噩梦。这个例子显示了统计的重要性。
注:当然了,每个数据库还有其特定的更高级的统计。如果你想了解更多信息,读读数据库的文档。话虽然这么说,我已经尽力理解统计是如何使用的了,而且我找到的最好的官方文档来自PostgreSQL。
所有的现代数据库都在用基于成本的优化(即CBO)来优化查询。道理是针对每个运算设置一个成本,通过应用成本最低廉的一系列运算,来找到最佳的降低查询成本的方法。
为了理解成本优化器的原理,我觉得最好用个例子来『感受』一下这个任务背后的复杂性。这里我将给出联接 2 个表的 3 个方法,我们很快就能看到即便一个简单的联接查询对于优化器来说都是个噩梦。之后,我们会了解真正的优化器是怎么做的。
对于这些联接操作,我会专注于它们的时间复杂度,但是,数据库优化器计算的是它们的 CPU 成本、磁盘 I/O 成本、和内存需求。时间复杂度和 CPU 成本的区别是,时间成本是个近似值(给我这样的懒家伙准备的)。而 CPU 成本,我这里包括了所有的运算,比如:加法、条件判断、乘法、迭代……还有呢:
每一个高级代码运算都要特定数量的低级 CPU 运算。
对于 Intel Core i7、Intel Pentium 4、AMD Opteron…等,(就 CPU 周期而言)CPU 的运算成本是不同的,也就是说它取决于 CPU 的架构。
使用时间复杂度就容易多了(至少对我来说),用它我也能了解到 CBO 的概念。由于磁盘 I/O 是个重要的概念,我偶尔也会提到它。请牢记,大多数时候瓶颈在于磁盘 I/O 而不是 CPU 使用。
在研究 B+树的时候我们谈到了索引,要记住一点,索引都是已经排了序的。
仅供参考:还有其他类型的索引,比如位图索引,在 CPU、磁盘I/O、和内存方面与B+树索引的成本并不相同。
另外,很多现代数据库为了改善执行计划的成本,可以仅为当前查询动态地生成临时索引。
在应用联接运算符(join operators)之前,你首先需要获得数据。以下就是获得数据的方法。
注:由于所有存取路径的真正问题是磁盘 I/O,我不会过多探讨时间复杂度。
如果你读过执行计划,一定看到过『全扫描』(或只是『扫描』)一词。简单的说全扫描就是数据库完整的读一个表或索引。就磁盘 I/O 而言,很明显全表扫描的成本比索引全扫描要高昂。
其他类型的扫描有索引范围扫描,比如当你使用谓词 ” WHERE AGE > 20 AND AGE < 40 ” 的时候它就会发生。
当然,你需要在 AGE 字段上有索引才能用到索引范围扫描。
在第一部分我们已经知道,范围查询的时间成本大约是 log(N)+M,这里 N 是索引的数据量,M 是范围内估测的行数。多亏有了统计我们才能知道 N 和 M 的值(注: M 是谓词 “ AGE > 20 AND AGE < 40 ” 的选择率)。另外范围扫描时,你不需要读取整个索引,因此在磁盘 I/O 方面没有全扫描那么昂贵。
如果你只需要从索引中取一个值你可以用唯一扫描。
多数情况下,如果数据库使用索引,它就必须查找与索引相关的行,这样就会用到根据 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存取,数据库也许会选择全扫描。
我没有列举所有的存取路径,如果你感兴趣可以读一读 Oracle文档。其它数据库里也许叫法不同但背后的概念是一样的。
我们知道如何获取数据了,那现在就把它们联接起来!
我要展现的是3个个常用联接运算符:合并联接(Merge join),哈希联接(Hash Join)和嵌套循环联接(Nested Loop Join)。但是在此之前,我需要引入新词汇了:内关系和外关系( inner relation and outer relation)这里的关系可以是:
当你联接两个关系时,联接算法对两个关系的处理是不同的。在本文剩余部分,我将假定:
比如, A JOIN B 是 A 和 B 的联接,这里 A 是外关系,B 是内关系。
多数情况下, A JOIN B 的成本跟 B JOIN A 的成本是不同的。
在这一部分,我还将假定外关系有 N 个元素,内关系有 M 个元素。要记住,真实的优化器通过统计知道 N 和 M 的值。
注:N 和 M 是关系的基数。
嵌套循环联接是最简单的。
原因如下:
下面是伪代码:
nested_loop_join(array outer, array inner)
for each row a in outer
for each row b in inner
if (match_join_condition(a,b))
write_result_in_output(a,b)
end if
end for
end for
由于这是个双迭代,时间复杂度是 O(N*M)。
在磁盘 I/O 方面, 针对 N 行外关系的每一行,内部循环需要从内关系读取 M 行。这个算法需要从磁盘读取 N+ N*M 行。但是,如果内关系足够小,你可以把它读入内存,那么就只剩下 M + N 次读取。这样修改之后,内关系必须是最小的,因为它有更大机会装入内存。
在CPU成本方面没有什么区别,但是在磁盘 I/O 方面,最好最好的,是每个关系只读取一次。
当然,内关系可以由索引代替,对磁盘 I/O 更有利。
由于这个算法非常简单,下面这个版本在内关系太大无法装入内存时,对磁盘 I/O 更加有利。原因如下:
可能的算法如下:
// improved version to reduce the disk I/O.
nested_loop_join_v2(file outer, file inner)
for each bunch ba in outer
// ba is now in memory
for each bunch bb in inner
// bb is now in memory
for each row a in ba
for each row b in bb
if (match_join_condition(a,b))
write_result_in_output(a,b)
end if
end for
end for
end for
end for
使用这个版本,时间复杂度没有变化,但是磁盘访问降低了:
哈希联接更复杂,不过在很多场合比嵌套循环联接成本低。
哈希联接的原理是:
在时间复杂度方面我需要做些假设来简化问题:
时间复杂度是 (M/X) * N + 创建哈希表的成本(M) + 哈希函数的成本 * N 。如果哈希函数创建了足够小规模的哈希桶,那么复杂度就是 O(M+N)。
还有个哈希联接的版本,对内存有利但是对磁盘 I/O 不够有利。 这回是这样的:
合并联接是唯一产生排序的联接算法。
注:这个简化的合并联接不区分内表或外表;两个表扮演同样的角色。但是真实的实现方式是不同的,比如当处理重复值时。
我们已经谈到过合并排序,在这里合并排序是个很好的算法(但是并非最好的,如果内存足够用的话,还是哈希联接更好)。
然而有时数据集已经排序了,比如:
这部分与我们研究过的合并排序中的合并运算非常相似。不过这一次呢,我们不是从两个关系里挑选所有元素,而是只挑选相同的元素。道理如下:
因为两个关系都是已排序的,你不需要『回头去找』,所以这个方法是有效的。
该算法是个简化版,因为它没有处理两个序列中相同数据出现多次的情况(即多重匹配)。真实版本『仅仅』针对本例就更加复杂,所以我才选择简化版。
如果两个关系都已经排序,时间复杂度是 O(N+M)
如果两个关系需要排序,时间复杂度是对两个关系排序的成本:O(NLog(N) + MLog(M))
如果有最好的,就没必要弄那么多种类型了。这个问题很难,因为很多因素都要考虑,比如:
想要更详细的信息,可以阅读DB2, ORACLE 或 SQL Server)的文档。
我们已经研究了 3 种类型的联接操作。现在,比如说我们要联接 5 个表,来获得一个人的全部信息。一个人可以有:
换句话说,我们需要用下面的查询快速得到答案:
SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS
WHERE
PERSON.PERSON_ID = MOBILES.PERSON_ID
AND PERSON.PERSON_ID = MAILS.PERSON_ID
AND PERSON.PERSON_ID = ADRESSES.PERSON_ID
AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID
作为一个查询优化器,我必须找到处理数据最好的方法。但有 2 个问题:
比如,下图显示了针对 4 个表仅仅 3 次联接,可能采用的执行计划:
现实世界的查询还会有其他关系运算符,像 OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT … 这意味着更多的可能性。
那么,数据库是如何处理的呢?
动态规划
,贪心算法
和启发式算法
关系型数据库会尝试我刚刚提到的多种方法,优化器真正的工作是在有限时间里找到一个好的解决方案。
多数时候,优化器找到的不是最佳的方案,而是一个『不错』的
对于小规模的查询,采取粗暴的方式是有可能的。但是为了让中等规模的查询也能采取粗暴的方式,我们有办法避免不必要的计算,这就是动态规划。
这几个字背后的理念是,很多执行计划是非常相似的。
它们都有相同的子树(A JOIN B),所以,不必在每个计划中计算这个子树的成本,计算一次,保存结果,当再遇到这个子树时重用。用更正规的说法,我们面对的是个重叠问题。为了避免对部分结果的重复计算,我们使用记忆法。
应用这一技术,我们不再有 (2*N)!/(N+1)! 的复杂度,而是“只有” 3^N。在之前 4 个JOIN 的例子里,这意味着将 336 次排序降为 81 次。如果是大一些的查询,比如 8 个 JOIN (其实也不是很大啦),就是将 57,657,600 次降为 6551 次。
针对大规模查询,你也可以用动态规划方法,但是要附加额外的规则(或者称为启发式算法)来减少可能性。
但是,优化器面对一个非常大的查询,或者为了尽快找到答案(然而查询速度就快不起来了),会应用另一种算法,叫贪婪算法。
原理是按照一个规则(或启发)以渐进的方式制定查询计划。在这个规则下,贪婪算法逐步寻找最佳算法,先处理一条JOIN,接着每一步按照同样规则加一条新的JOIN。
我们来看个简单的例子。比如一个针对5张表(A,B,C,D,E)4次JOIN 的查询,为了简化我们把嵌套JOIN作为可能的联接方式,按照『使用最低成本的联接』规则。
因为我们是武断地从表 A 开始,我们可以把同样的算法用在 B,然后 C,然后 D, 然后 E。最后保留成本最低的执行计划。
顺便说一句,这个算法有个名字,叫『最近邻居算法』。
抛开细节不谈,只需一个良好的模型和一个 Nlog(N) 复杂度的排序,问题就轻松解决了。这个算法的复杂度是 O(Nlog(N)) ,对比一下完全动态规划的 O(3^N)。如果你有个20个联接的大型查询,这意味着 26 vs 3,486,784,401 ,天壤之别!
这个算法的问题是,我们做的假设是:找到 2 个表的最佳联接方法,保留这个联接结果,再联接下一个表,就能得到最低的成本。但是:
为了改善这一状况,你可以多次使用基于不同规则的贪心算法,并保留最佳的执行计划。
由于创建查询计划是耗时的,大多数据库把计划保存在查询计划缓存,来避免重复计算。这个话题比较大,因为数据库需要知道什么时候更新过时的计划。办法是设置一个上限,如果一个表的统计变化超过了上限,关于该表的查询计划就从缓存中清除。
在这个阶段,我们有了一个优化的执行计划,再编译为可执行代码。然后,如果有足够资源(内存,CPU),查询执行器就会执行它。计划中的操作符 (JOIN, SORT BY …) 可以顺序或并行执行,这取决于执行器。为了获得和写入数据,查询执行器与数据管理器交互,本文下一部分来讨论数据管理器。
在这一步,查询管理器执行了查询,需要从表和索引获取数据,于是向数据管理器提出请求。但是有 2 个问题:
在这一部分,我们看看关系型数据库是如何处理这两个问题的。
数据库的主要瓶颈是磁盘 I/O。为了提高性能,现代数据库使用缓存管理器。
查询执行器不会直接从文件系统拿数据,而是向缓存管理器要。缓存管理器有一个内存缓存区,叫做缓冲池,从内存读取数据显著地提升数据库性能。对此很难给出一个数量级,因为这取决于你需要的是哪种操作:
以及数据库使用的磁盘类型:
要我说,内存比磁盘要快100到10万倍。然而,这导致了另一个问题(数据库总是这样…),缓存管理器需要在查询执行器使用数据之前得到数据,否则查询管理器不得不等待数据从缓慢的磁盘中读出来。
这个问题叫预读。查询执行器知道它将需要什么数据,因为它了解整个查询流,而且通过统计也了解磁盘上的数据。过程是这样的:
缓存管理器在缓冲池里保存所有的这些数据。为了确定一条数据是否有用,缓存管理器给缓存的数据添加了额外的信息(叫闩锁)。
有时查询执行器不知道它需要什么数据,有的数据库也不提供这个功能。相反,它们使用一种推测预读法(比如:如果查询执行器想要数据1、3、5,它不久后很可能会要 7、9、11),或者顺序预读法(这时候缓存管理器只是读取一批数据后简单地从磁盘加载下一批连续数据)。
为了监控预读的工作状况,现代数据库引入了一个度量叫缓冲/缓存命中率,用来显示请求的数据在缓存中找到而不是从磁盘读取的频率。
注:糟糕的缓存命中率不总是意味着缓存工作状态不佳。
缓冲只是容量有限的内存空间,因此,为了加载新的数据,它需要移除一些数据。加载和清除缓存需要一些磁盘和网络I/O的成本。如果你有个经常执行的查询,那么每次都把查询结果加载然后清除,效率就太低了。现代数据库用缓冲区置换策略来解决这个问题。
多数现代数据库(至少 SQL Server, MySQL, Oracle 和 DB2)使用 LRU 算法。
LRU代表最近最少使用(Least Recently Used)算法,背后的原理是:在缓存里保留的数据是最近使用的,所以更有可能再次使用。
为了更好的理解,我假设缓冲区里的数据没有被闩锁锁住(就是说是可以被移除的)。在这个简单的例子里,缓冲区可以保存 3 个元素:
这个算法效果很好,但是有些限制。如果对一个大表执行全表扫描怎么办?换句话说,当表/索引的大小超出缓冲区会发生什么?使用这个算法会清除之前缓存内所有的数据,而且全扫描的数据很可能只使用一次。
为了防止这个现象,有些数据库增加了特殊的规则,比如Oracle文档中的描述:
『对非常大的表来说,数据库通常使用直接路径来读取,即直接加载区块[……],来避免填满缓冲区。对于中等大小的表,数据库可以使用直接读取或缓存读取。如果选择缓存读取,数据库把区块置于LRU的尾部,防止清空当前缓冲区。』
还有一些可能,比如使用高级版本的LRU,叫做 LRU-K。例如,SQL Server 使用 LRU-2。
这个算法的原理是把更多的历史记录考虑进来。简单LRU(也就是 LRU-1),只考虑最后一次使用的数据。LRU-K呢:
计算权重是需要成本的,所以SQL Server只是使用 K=2,这个值性能不错而且额外开销可以接受。
当然还有其他管理缓存的算法,比如:
我只探讨了读缓存 —— 在使用之前预先加载数据。用来保存数据、成批刷入磁盘,而不是逐条写入数据从而造成很多单次磁盘访问。
要记住,缓冲区保存的是页(最小的数据单位)而不是行(逻辑上/人类习惯的观察数据的方式)。缓冲池内的页如果被修改了但还没有写入磁盘,就是脏页。有很多算法来决定写入脏页的最佳时机,但这个问题与事务的概念高度关联,下面我们就谈谈事务。
最后但同样重要的,是事务管理器,我们将看到这个进程是如何保证每个查询在自己的事务内执行的。但开始之前,我们需要理解ACID事务的概念。
“I’m on acid”
一个ACID事务是一个工作单元,它要保证4个属性:
在同一个事务内,你可以运行多个SQL查询来读取、创建、更新和删除数据。当两个事务使用相同的数据,麻烦就来了。经典的例子是从账户A到账户B的汇款。假设有2个事务:
我们回来看看ACID属性:
确保隔离性、一致性和原子性的真正问题是对相同数据的写操作(增、更、删):
这个问题叫并发控制。
最简单的解决办法是依次执行每个事务(即顺序执行),但这样就完全没有伸缩性了,在一个多处理器/多核服务器上只有一个核心在工作,效率很低。
用更正规的说法,这是对冲突的调度问题。更具体点儿说,这是个非常困难而且CPU开销很大的优化问题。企业级数据库无法承担等待几个小时,来寻找每个新事务活动最好的调度,因此就使用不那么理想的方式以避免更多的时间浪费在解决冲突上。
为了解决这个问题,多数数据库使用锁和/或数据版本控制。这是个很大的话题,我会集中探讨锁,和一点点数据版本控制。
原理是:
这个锁叫排他锁。
但是对一个仅仅读取数据的事务使用排他锁非常昂贵,因为这会迫使其它只需要读取相同数据的事务等待。因此就有了另一种锁,共享锁。
共享锁是这样的:
同样的,如果一块数据被加上排他锁,一个只需要读取该数据的事务必须等待排他锁释放才能给该数据加上共享锁。
锁管理器是添加和释放锁的进程,在内部用一个哈希表保存锁信息(关键字是被锁的数据),并且了解每一块数据是:
但是使用锁会导致一种情况,2个事务永远在等待一块数据
这叫死锁。
在死锁发生时,锁管理器要选择取消(回滚)一个事务,以便消除死锁。这可是个艰难的决定:
在作出选择之前,锁管理器需要检查是否有死锁存在。
哈希表可以看作是个图表(见上文图),图中出现循环就说明有死锁。由于检查循环是昂贵的(所有锁组成的图表是很庞大的),经常会通过简单的途径解决:使用超时设定。如果一个锁在超时时间内没有加上,那事务就进入死锁状态。
锁管理器也可以在加锁之前检查该锁会不会变成死锁,但是想要完美的做到这一点还是很昂贵的。因此这些预检经常设置一些基本规则。
实现纯粹的隔离最简单的方法是:事务开始时获取锁,结束时释放锁。就是说,事务开始前必须等待确保自己能加上所有的锁,当事务结束时释放自己持有的锁。这是行得通的,但是为了等待所有的锁,大量的时间被浪费了。
更快的方法是两段锁协议(Two-Phase Locking Protocol,由 DB2 和 SQL Server使用),在这里,事务分为两个阶段:
这两条简单规则背后的过程是:
这个规则可以很好地工作,但有个例外:如果修改了一条数据、释放了关联的锁后,事务被取消(回滚),而另一个事务读到了修改后的值,但最后这个值却被回滚。为了避免这个问题,所有独占锁必须在事务结束时释放。
当然了,真实的数据库使用更复杂的系统,涉及到更多类型的锁(比如意向锁,intention locks)和更多的粒度(行级锁、页级锁、分区锁、表锁、表空间锁),但是思路是相同的。
我只探讨纯粹基于锁的方法,数据版本控制是解决这个问题的另一个方法。
版本控制是这样的:
这将提高性能,因为:
除了两个事务写相同数据的时候,数据版本控制各个方面都比锁表现得更好。只不过,你很快就会发现磁盘空间消耗巨大。
数据版本控制和锁机制是两种不同的见解:乐观锁和悲观锁。两者各有利弊,完全取决于使用场景(读多还是写多)。
一些数据库,比如DB2(直到版本 9.7)和 SQL Server(不含快照隔离)仅使用锁机制。其他的像PostgreSQL, MySQL 和 Oracle 使用锁和鼠标版本控制混合机制。
我们已经知道,为了提升性能,数据库把数据保存在内存缓冲区内。但如果当事务提交时服务器崩溃,崩溃时还在内存里的数据会丢失,这破坏了事务的持久性。你可以把所有数据都写在磁盘上,但是如果服务器崩溃,最终数据可能只有部分写入磁盘,这破坏了事务的原子性。
事务作出的任何修改必须是或者撤销,或者完成。
有 2 个办法解决这个问题:
影子副本/页在运行较多事务的大型数据库时制造了大量磁盘开销,所以现代数据库使用事务日志。事务日志必须保存在稳定的存储上,我不会深挖存储技术,但至少RAID磁盘是必须的,以防磁盘故障。
多数数据库(至少是Oracle,SQL Server,DB2,PostgreSQL, MySQL 和SQLite) 使用预写日志协议(Write-Ahead Logging protocol ,WAL)来处理事务日志。WAL协议有 3 个规则:
这个工作由日志管理器完成。简单的理解就是,日志管理器处于缓存管理器(cache manager)和数据访问管理器(data access manager,负责把数据写入磁盘)之间,每个 update / delete / create / commit / rollback 操作在写入磁盘之前先写入事务日志。这个过程并简单,原因在于如何找到写日志的同时保持良好的性能的方法,如果事务日志写得太慢,整体都会慢下来。
1992年,IBM 研究人员『发明』了WAL的增强版,叫 ARIES。ARIES 或多或少地在现代数据库中使用,逻辑未必相同,但AIRES背后的概念无处不在。ARIES 代表『数据库恢复原型算法』(Algorithms forRecovery andIsolationExploitingSemantics)。
这个技术要达到一个双重目标:
有多个原因让数据库不得不回滚事务:
有时候(比如网络出现故障),数据库可以恢复事务。这怎么可能呢?为了回答这个问题,我们需要了解日志里保存的信息。
事务的每一个操作(增/删/改)产生一条日志,由如下内容组成:
磁盘上每个页(保存数据的,不是保存日志的)都记录着最后一个修改该数据操作的LSN。
注:据我所知,只有 PostgreSQL 没有使用UNDO,而是用一个垃圾回收服务来删除旧版本的数据。这个跟 PostgreSQL 对数据版本控制的实现有关。
为了更好的说明这一点,这有一个简单的日志记录演示图,是由查询 “UPDATE FROM PERSON SET AGE = 18;
” 产生的
每条日志都有一个唯一的LSN,链接在一起的日志属于同一个事务。日志按照时间顺序链接(链接列表的最后一条日志是最后一个操作产生的)。
为了防止写日志成为主要的瓶颈,数据库使用了日志缓冲区。
当查询执行器要求做一次修改:
当事务提交,意味着事务每一个操作的5个步骤都完成了。写事务日志是很快的,因为它只是『在事务日志某处增加一条日志』;而数据写盘就更复杂了,因为要用『能够快速读取的方式写入数据』。
出于性能方面的原因,第 5 步有可能在提交之后完成,因为一旦发生崩溃,还有可能用REDO日志恢复事务。这叫做 NO-FORCE策略。
数据库可以选择FORCE策略(比如第 5 步在提交之前必须完成)来降低恢复时的负载。
另一个问题是,要选择数据是一步步的写入(STEAL策略),还是缓冲管理器需要等待提交命令来一次性全部写入(NO-STEAL策略)。选择STEAL还是NO-STEAL取决于你想要什么:快速写入但是从 UNDO 日志恢复缓慢,还是快速恢复。
下面是这些策略对恢复的影响:
Ok,有了不错的日志,我们来用用它们!
假设新来的实习生让数据库崩溃了,你重启了数据库,恢复过程开始了。
ARIES从崩溃中恢复有三个阶段:
恢复过程中,事务日志必须留意恢复过程的操作,以便写入磁盘的数据与事务日志相一致。一个解决办法是移除被取消的事务产生的日志记录,但是这个太困难了。相反,ARIES在事务日志中记录补偿日志,来逻辑上删除被取消的事务的日志记录。
当事务被『手工』取消,或者被锁管理器取消(为了消除死锁),或仅仅因为网络故障而取消,那么分析阶段就不需要了。对于哪些需要 REDO 哪些需要 UNDO 的信息在 2 个内存表中:
当新的事务产生时,这两个表由缓存管理器和事务管理器更新。因为是在内存中,当数据库崩溃时它们也被破坏掉了。
分析阶段的任务就是在崩溃之后,用事务日志中的信息重建上述的两个表。为了加快分析阶段,ARIES提出了一个概念:检查点(check point),就是不时地把事务表和脏页表的内容,还有此时最后一条LSN写入磁盘。那么在分析阶段当中,只需要分析这个LSN之后的日志即可。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。