关系型数据库是怎么工作的7:数据管理

作者:51ak

目录:

[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个元素:

数据库中的LRU算法

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:

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

其他算法

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

写缓冲驱 Write buffer

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

 

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

事务管理器 Transaction manager

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

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

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

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

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

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

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

 

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

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

并发控制

确保隔离性,一致性和原子性的真正问题是对同一数据的写操作(添加,更新和删除):

此问题称为并发控制

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

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

锁管理 Lock manager

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

 

悲观锁定

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

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

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

使用共享锁

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

数据库中的锁管理器

锁管理器是提供和释放锁的过程。 在内部,它将锁存储在哈希表(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条规则的集合:

数据库中的日志管理器

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

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

恢复和隔离算法 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。利用语义的恢复和隔离算法

该技术的目标有两个:

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

有时(例如,在网络故障的情况下),数据库可以恢复事务。

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

日志

事务的每个操作(添加/删除/修改)都会生成日志。日志记录包括: - 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

ARIES_logs

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

 

日志缓冲区

为避免日志写入成为主要瓶颈,使用了日志缓冲区。 数据库中的日志写入过程

当SQL查询要修改数据时:

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

 

假装和强制策略

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

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

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

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

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

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

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

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

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

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

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

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

总结一下

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

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

  回到我们这篇文章,

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

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

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

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

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

本篇文章分以下章节,当前最后一节:

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

发布日期:2018/01/11

Categories: 数据库理论 翻译 关系型数据库 mysql Tags: 转译 精品