数据库之事务处理和恢复

事务是数据库管理系统中不可分割的逻辑工作单元，允许将多个操作表示为单个步骤。事务执行的操作包括读取和写入数据库记录。数据库事务必须保持原子性、一致性、隔离性和持久性。这些属性通常被称为ACID:

• 原子性(Atomicity)：事务步骤是不可分割的，这意味着要么与事务相关的所有步骤都成功执行，要么一个都不执行。换句话说，事务不应该部分应用。每个事务既可以提交(使事务期间执行的写操作的所有更改可见)，也可以中止(回滚尚未可见的所有事务副作用)。提交是最后一个操作。在中止之后，可以重试事务。
• 一致性(Consistency)：一致性是特定于应用程序的保证;事务应该只将数据库从一种有效状态转换到另一种有效状态，并维护所有数据库不变量(如约束、引用完整性等)。一致性是定义最弱的属性，可能是因为它是唯一由用户而不仅仅是数据库本身控制的属性。
• 隔离性(Isolation)：多个并发执行的事务应该能够不受干扰地运行，就像没有其他事务同时执行一样。隔离定义了何时可以看到数据库状态的更改，以及并发事务可以看到哪些更改。由于性能原因，许多数据库使用的隔离级别比给定的隔离定义要弱。根据用于并发控制的方法和方法，事务所做的更改可能对其他并发事务可见，也可能对其他并发事务不可见。
• 持久性(Durability)：事务提交后，所有数据库状态修改都必须持久化在磁盘上，并且能够在断电、系统故障和崩溃时保存下来。

除了在磁盘上组织和持久存储数据的存储结构之外，在数据库系统中实现事务还需要几个组件协同工作。在本地节点上，事务管理器协调、调度和跟踪事务及其各个步骤。

锁管理器保护对这些资源的访问，并防止违反数据完整性的并发访问。每当请求一个锁时，锁管理器检查它是否已经被任何其他共享或独占模式的事务持有，如果请求的访问级别没有冲突，就授予对它的访问权。由于在任何给定时刻最多只能由一个事务持有排他锁，其他请求排他锁的事务必须等待，直到释放锁，或者中止并稍后重试。一旦锁被释放或事务终止，锁管理器就会通知其中一个挂起的事务，让它获得锁并继续执行。

页面缓存充当持久存储(磁盘)和存储引擎其余部分之间的中介。它在主存中执行状态更改，并充当未与持久存储同步的页面的缓存。对数据库状态的所有更改都首先应用于缓存页。

日志管理器保存应用于缓存页面的操作历史(日志条目)，但尚未与持久存储同步，以确保在崩溃时它们不会丢失。换句话说，日志用于重新应用这些操作，并在启动期间重建缓存的状态。日志条目还可以用来撤消被中止的事务所做的更改。

分布式(多分区)事务需要额外的协调和远程执行。

缓冲区管理

大多数数据库使用两级内存层次结构构建:较慢的持久存储(磁盘)和较快的主内存(RAM)。为了减少对持久存储的访问次数，页面被缓存在内存中。当存储层再次请求该页面时，将返回其缓存副本。

在假定没有其他进程修改磁盘上的数据的情况下，可以重用内存中可用的缓存页。这种方法有时被引用为虚拟磁盘。只有在内存中没有页的副本时，虚拟磁盘才访问物理存储。同一概念更常见的名称是页面缓存或缓冲池。页面缓存负责将从磁盘读取的页面缓存到内存中。如果数据库系统崩溃或无序关闭，缓存的内容将丢失。

缓存页面的问题并不局限于数据库。操作系统也有页面缓存的概念。操作系统利用未使用的内存段来透明地缓存磁盘内容，以提高I/O系统调用的性能。

当未缓存的页面从磁盘加载时，它们被换入。如果对缓存页做了任何更改，则称其为脏的，直到这些更改被刷新回磁盘。

由于存放缓存页面的内存区域通常比整个数据集小得多，因此页面缓存最终会被填满，为了换入新页面，必须将其中一个缓存页面逐出。

在图1中，可以看到B-Tree页面的逻辑表示形式、它们的缓存版本和磁盘上的页面之间的关系。页面缓存将页面无序地加载到空闲槽中，因此在磁盘上和内存中页面的顺序之间没有直接映射。

页面缓存的主要功能可以总结为:

• 它将缓存的页面内容保存在内存中。

• 它允许对磁盘上页面的修改被缓冲在一起，并根据它们的缓存版本执行。

• 当请求的页面不在内存中且有足够的可用空间时，页面缓存会将其分页，并返回

  其缓存的版本。

• 如果请求一个已经缓存的页面，则返回其缓存版本。

• 如果没有足够的空间可用于新页面，则将删除其他一些页面，并将其内容刷新到磁盘。

语义缓存

对缓冲区所做的所有更改都保存在内存中，直到它们最终被写回磁盘。由于不允许其他进程对备份文件进行更改，因此这种同步是单向的:从内存到磁盘，反之亦然。页面缓存允许数据库对内存管理和磁盘访问有更多的控制。可以把它看作是特定于应用程序的内核页面缓存的等价物:它直接访问块设备，实现类似的功能，服务于类似的目的。它抽象了磁盘访问，并将逻辑写操作与物理写操作解耦。

缓存页面有助于将树的一部分保存在内存中，而不需要对算法进行额外的更改，也不需要在内存中具体化对象。我们所要做的就是用对页面缓存的调用替换磁盘访问。

当存储引擎访问(换句话说，请求)页面时，我们首先检查其内容是否已经缓存，在这种情况下，将返回缓存的页面内容。如果还没有缓存页面内容，缓存会将逻辑页地址或页码转换为物理地址，将其内容加载到内存中，并将其缓存版本返回给存储引擎。一旦返回，带有缓存页面内容的缓冲区就被称为被引用了，存储引擎必须将其交还给页面缓存，或者在完成之后解除对它的引用。可以指示页面缓存通过固定页面来避免驱逐页面。

如果页面被修改(例如，一个单元格被附加到其中)，它将被标记为dirty。页面上设置的脏标志表明其内容与磁盘不同步，必须进行刷新以确保持久性。

缓存可以使我们在不使用持久存储的情况下提供更多的读，并且可以将更多的同页写缓冲在一起。然而，页面缓存的容量有限，为了提供新内容，旧页面迟早要被清除。如果页面内容与磁盘同步(即已经刷新或从未修改过)，且页面没有固定或引用，则可以立即将其移除。脏页必须先清除，然后才能被清除。当其他线程正在使用引用的页面时，不应该将它们逐出。

由于在每次清除时触发刷新可能不利于性能，所以一些数据库使用一个单独的后台进程来循环处理可能被清除的脏页，更新它们的磁盘版本。例如，PostgreSQL就有一个后台flush写入器。

另一个需要记住的重要属性是持久性:如果数据库崩溃，所有未刷新的数据都会丢失。为了确保所有更改都被持久化，刷新由检查点进程协调。检查点进程控制WAL (write-ahead log)和页面缓存，并确保它们同步工作。只有与应用于缓存页面的操作相关的日志记录可以从WAL中丢弃。在此过程完成之前，不能清除脏页。

这意味着在几个目标之间总是存在权衡:

• 延迟刷新以减少磁盘访问次数
• 先发制人地刷新页面，以允许快速清除
• 按最佳顺序选择要清除和刷新的页面
• 保持缓存大小在其内存范围内
• 避免丢失数据，因为它没有持久化到主存储

在缓存中锁定页面

每次读或写都必须执行磁盘I/O是不切实际的:后续读可能请求相同的页面，就像后续写可能修改相同的页面一样。由于B-Tree向顶部“变窄”了，大多数读取都是在高层节点(离根节点更近的节点)上进行的。拆分和合并最终也会传播到更高级别的节点。这意味着树中至少有一部分可以从缓存中获得显著的好处。

我们可以“锁定”那些在最近的时间内被使用的可能性很大的页面。在缓存中锁定页面称为固定。固定页面在内存中保存的时间更长，这有助于减少磁盘访问次数，提高性能。

由于每一个较低的B-Tree节点级别的节点数量都是指数级的，而较高级别的节点只代表树的一小部分，树的这一部分可以永久驻留在内存中，而其他部分可以根据需要换入。这意味着，为了执行查询，我们不需要进行h
次磁盘访问，而只需要访问较低级别的磁盘，其中的页面没有缓存。

对子树执行的操作可能会导致相互矛盾的结构变化—-例如，多个删除操作导致合并，然后写入操作导致拆分，或者相反。同样，从不同子树传播的结构变化(结构变化在时间上发生在树的不同部分，向上传播)。这些操作可以通过只在内存中应用更改来一起缓冲，这可以减少磁盘写的数量，并分摊操作成本，因为只能执行一次写，而不是多次写。

分页替换(Page Replacement)

当达到缓存容量时，要加载新页面，就必须清除旧页面。然而，除非我们驱逐那些最不可能再次访问的页面，否则我们可能会在随后加载它们几次，尽管我们本可以将它们一直保存在内存中。我们需要找到一种方法来估计后续页面访问的可能性，以优化这一点。

为此，我们可以说应该根据收回策略(有时也称为页面替换策略)来收回页面。它试图找到近期内最不可能再次被访问的页面。当页面从缓存中移除时，可以在其位置加载新页面。

为了实现页面缓存的性能，它需要一个高效的页面替换算法。理想的页面替换策略需要一个水晶球来预测页面被访问的顺序，并且只驱逐那些在很长一段时间内不会被访问的页面。由于请求不一定遵循任何特定的模式或分布，精确预测行为可能很复杂，但使用正确的页面替换策略可以帮助减少驱逐的数量。

通过简单地使用一个更大的缓存，我们可以减少驱逐的数量，这似乎是合乎逻辑的。然而，事实似乎并非如此。如果使用的页面替换算法不是最优的，增加页面数量可能会增加驱逐的数量。当很快可能需要的页面被驱逐并再次加载时，页面开始在缓存中竞争空间。因此，我们需要明智地考虑我们正在使用的算法，这样它将改善情况，而不是使情况更糟。

FIFO and LRU

最常用的页面替换策略是先入先出(FIFO)。FIFO按照页面id的插入顺序维护一个页面id队列，将新页面添加到队列的尾部。每当页面缓存已满时，它从队列的头部获取元素，以查找在时间点最晚被换入的页面。由于它不考虑后续的页面访问，而只考虑页面导入事件，因此对于大多数真实的系统来说，这是不切实际的。例如，根页面和最顶层页面首先被换入，根据该算法，它们是第一个被驱逐的候选页面，尽管从树结构中可以清楚地看到，这些页面可能很快再次被换入。

FIFO算法的自然扩展是最近最少使用(LRU)。它还按照插入顺序维护一个回收候选项队列，但允许在重复访问时将页面放回队列尾部，就好像这是它第一次被分页一样。然而，在并发环境中，每次访问时更新引用和重新链接节点的代价可能会很大。

还有其他基于lru的缓存回收策略。例如，2Q (two - queue LRU)维护两个队列，在初始访问期间将页面放入第一个队列，在后续访问时将它们移动到第二个热队列，允许你区分最近访问和频繁访问的页面。LRU-K通过跟踪最近K
次访问来标识频繁引用的页面，并使用此信息估计基于页面的访问时间。

CLOCK

在某些情况下，效率可能比精度更重要。时钟算法变体通常被用作紧凑的、缓存友好的、并发的LRU替代方案。例如，Linux使用了一种时钟算法的变体。

时钟扫描保存对循环缓冲区中的页和相关访问位的引用。一些变体使用计数器而不是位来解释频率。每次访问该页面时，其访问位设置为1
。该算法的工作原理是围绕循环缓冲区，检查访问位:

• 如果访问位为1
  ，且该页面未被引用，则将其设置为0
  ，并检查下一个页面。
• 如果访问位已经为0
  ，则该页面将成为候选页面，并计划进行退出。
• 如果当前页面被引用，它的访问位保持不变。假设被访问页面的访问位不能为0
  ，因此不能将其逐出。这使得被引用的页面不太可能被替换。

图2显示了具有访问位的循环缓冲区。

使用循环缓冲区的一个优点是，可以使用比较和交换操作修改时钟指针和内容，并且不需要额外的锁定机制。该算法易于理解和实现，经常在教科书和现实系统中使用。

LRU并不总是数据库系统的最佳替代策略。有时，考虑使用频率而不是最近次数作为预测因素可能更实际。最后，对于高负载的数据库系统，最近次数可能不是很具有指示意义，因为它只表示访问项的顺序。

LFU

为了改善这种情况，我们可以开始跟踪页面引用事件，而不是分页事件。允许我们这样做的方法之一是跟踪使用频率最低的(LFU)页面。

TinyLFU是一种基于频率的页面清除策略，它正是这样做的:它不是基于最近的页面清除，而是根据使用频率对页面进行排序。它是在流行的Java库Caffeine中实现的。

TinyLFU使用频率直方图来维护紧凑的缓存访问历史，因为对于实际目的来说，保存整个历史成本高昂。

元素可以属于以下三个队列中的一个:

• Admission
• Probation
• Protected

比起每次都选择移除哪些元素，这种方法更倾向于选择哪些元素能够提升留存率。只有那些频率大于提升次数的条目才能被移到probation队列中。在随后的访问中，项目可以从probation移动到受protected队列。如果protected队列已满，其中的一个元素可能必须重新放置到probation。使用频率越高的条目留存率就越高，而使用频率越低的条目就越有可能被淘汰。

admission队列、probation队列、protected队列、frequency filter、eviction队列之间的逻辑连接如图3所示。

还有许多其他算法可以用于最优缓存回收。页面替换策略的选择对延迟和执行的I/O操作的数量有很大的影响，因此必须予以考虑。

恢复(Recovery)

数据库系统是建立在一些硬件和软件层之上的，这些硬件和软件层可能有自己的稳定性和可靠性问题。数据库系统本身以及底层的软件和硬件组件可能会发生故障。数据库管理者必须考虑这些故障场景，并确保要写入的数据实际上已经写入。

预写日志(write-ahead log，简称WAL，也称为提交日志)是一种仅追加的辅助磁盘结构，用于崩溃和事务恢复。页面缓存允许在内存中缓冲对页面内容的更改。直到缓存的内容被刷新回磁盘，保存操作历史的唯一磁盘驻留副本存储在WAL中。许多数据库系统使用只追加提前写的日志;例如PostgreSQL和MySQL。

预写日志的主要功能可以总结为:

• 允许页缓存缓冲对磁盘驻留页的更新，同时确保数据库系统更大上下文中的持久性语义。
• 将所有操作保持在磁盘上，直到受这些操作影响的页面的缓存副本在磁盘上同步。修改数据库状态的每个操作都必须登录到磁盘上，然后才能修改相关页面的内容。
• 允许在崩溃时从操作日志中重新构建丢失的内存更改。

除了这个功能之外，预写日志在事务处理中也扮演着重要的角色。它确保了数据被保存到持久存储中，并且在崩溃时可用，因为未提交的数据会从日志中重放，崩溃前的数据库状态会完全恢复。

日志语义(Log Semantics)

预写日志是只追加的，它的写入内容是不可变的，因此所有对该日志的写入都是顺序的。由于WAL是一个不可变的，只追加的数据结构，读可以安全地访问它的内容，直到最新的写阈值，而写继续追加数据到日志尾。

WAL由日志记录组成。每条记录都有一个唯一的、单调递增的日志序列号(LSN)。通常，LSN由内部计数器或时间戳表示。由于日志记录不一定会占用整个磁盘块，因此它们的内容被缓存到日志缓冲区中，并在强制操作中刷新到磁盘上。强制在日志缓冲区填满时发生，可以由事务管理器或页面缓存请求。必须按LSN顺序将所有日志记录刷新到磁盘上。

除了个人操作记录外，WAL保存着表明交易完成的记录。在将日志强制达到提交记录的LSN之前，不能认为事务已提交。

为了确保系统在回滚或恢复期间崩溃后能够继续正常运行，一些系统在撤销期间使用补偿日志记录(CLR)并将它们存储在日志中。

WAL通常通过接口与主存储结构相结合，允许在到达检查点时对其进行修整。日志记录是数据库最关键的正确性方面之一，要正确处理这一点有点困难:在日志裁剪和确保数据已进入主存储结构之间即使有最轻微的分歧，也可能导致数据丢失。

通过检查点，日志可以知道达到某个标记的日志记录是完全持久的，并且不再需要，这大大减少了数据库启动期间所需的工作量。强制将所有脏页刷新到磁盘上的进程通常称为同步检查点，因为它完全同步主存储结构。

刷新磁盘上的全部内容相当不切实际，并且需要暂停所有正在运行的操作，直到检查点完成，因此大多数数据库系统都实现模糊检查点。在本例中，存储在日志头中的last_checkpoint
指针包含关于最后一个成功检查点的信息。模糊检查点以指定其开始的特殊begin_checkpoint
日志记录开始，以nd_checkpoint
日志记录结束，该日志记录包含脏页的信息和事务表的内容。在刷新此记录指定的所有页面之前，检查点被认为是不完整的。页面被异步刷新，一旦完成，last_checkpoint
记录将用begin_checkpoint
记录的LSN更新，在崩溃的情况下，恢复过程将从那里开始[MOHAN92]。

一些数据库系统，例如System R ，使用阴影分页:一种确保数据持久性和事务原子性的写时复制技术。新的内容被放置到新的未发布的影子页面中，并通过指针翻转使之可见，从旧页面到保存更新内容的页面。

任何状态的变化都可以用一个before-image和一个after-image或相应的redo和undo操作来表示。将redo操作应用于before-image产生after-image。类似地，对after-image应用undo操作将产生before-image。

我们可以使用物理日志(存储完整的页面状态或对页面的字节更改)或逻辑日志(存储必须针对当前状态执行的操作)将记录或页面从一种状态移动到另一种状态，同时可以向后或向前移动。跟踪物理和逻辑日志记录可以应用到的页面的确切状态非常重要。

物理日志记录前后的状态，要求记录受操作影响的整个页面。逻辑日志指定了哪些操作必须应用到页面上，例如“insert a data record X for key Y”
，以及相应的撤销操作，例如“remove the value associated with Y”
。

在实践中，许多数据库系统使用这两种方法的组合，使用逻辑日志来执行撤销(为了并发性和性能)，使用物理日志来执行重做(为了提高恢复时间)。

为了确定何时必须将内存中所做的更改刷新到磁盘上，数据库管理系统定义了steal/no-steal和force/no-force策略。这些策略大多适用于页面缓存，但最好在恢复上下文中讨论它们，因为它们对哪些恢复方法可以与它们结合使用有很大的影响。

允许在事务提交之前刷新已被事务修改的页面的恢复方法称为steal策略。no steal策略不允许刷新磁盘上任何未提交的事务内容。在这里，要steal脏页意味着将其内存中的内容刷新到磁盘，并从磁盘中加载不同的页。

force策略要求在事务提交之前将事务修改过的所有页面刷新到磁盘上。另一方面，no-force策略允许事务提交，即使在事务期间修改的一些页面还没有刷新到磁盘上。此处force使用脏页意味着在提交之前将其刷新到磁盘上。

理解steal和force策略很重要，因为它们对事务撤消和重做有影响。undo将更新回滚到已提交事务的force页面，而redo则将已提交事务执行的更改应用到磁盘上。

使用no-steal策略允许只使用重做项实现恢复:旧副本包含在磁盘上的页面中，修改保存在日志中。在没有force的情况下，我们可以通过延迟页面来缓冲多个更新。由于此时页面内容必须缓存在内存中，因此可能需要更大的页面缓存。

当使用force策略时，崩溃恢复不需要任何额外的工作来重建提交事务的结果，因为由这些事务修改的页面已经被刷新。使用这种方法的一个主要缺点是，由于必要的I/O，事务需要更长的时间来提交。

在事务提交之前，我们需要有足够的信息来撤销其结果。如果刷新事务涉及的任何页面，我们需要在日志中保留撤消信息，直到它提交，以便能够回滚它。否则，我们必须在日志中保留重做记录，直到它提交。在这两种情况下，只有将撤销或重做记录写到日志文件中，事务才能提交。

ARIES(Algorithms for Recovery and Isolation Exploiting Semantics)

ARIES是一个steal/no-force恢复算法。它使用物理重做来提高恢复期间的性能(因为可以更快地安装更改)，使用逻辑撤消来提高正常操作期间的并发性(因为逻辑撤消操作可以独立应用于页面)。它使用WAL记录实现恢复过程中的重复历史，在撤销未提交事务之前完全重构数据库状态，并在撤销过程中创建补偿日志记录。

当数据库系统崩溃后重新启动时，恢复将分三个阶段进行:

1. 分析阶段识别页面缓存中的脏页和崩溃时正在进行的事务。有关脏页的信息用于标识重做阶段的起始点。在撤消阶段使用正在进行的事务列表来回滚不完整的事务。
2. 重做阶段重复历史，直到崩溃点，并将数据库恢复到以前的状态。对于未完成的事务以及已提交但其内容没有刷新到持久存储的事务，将执行此阶段。
3. 撤消阶段回滚所有不完整的事务，并将数据库恢复到上次一致的状态。所有操作都按时间倒序回滚。如果数据库在恢复期间再次崩溃，撤销事务的操作也会被记录下来，以避免重复它们。

ARIES使用lsn来标识日志记录，跟踪通过在脏页表中运行事务而修改的页面，并使用物理重做、逻辑撤消和模糊检查点。

并发控制(Concurrency Control)

在“DBMS架构”中讨论数据库管理系统架构时，我们提到了事务管理器和锁管理器共同处理并发控制。并发控制是一组用于处理并发执行事务之间交互的技术。这些技术可以大致分为以下几类:

• Optimistic concurrency control (OCC)

  允许事务执行并发的读写操作，并确定合并执行的结果是否可序列化。换句话说，事务不会相互阻塞，维护其操作的历史记录，并在提交之前检查这些历史记录，以防可能的冲突。如果执行导致冲突，则终止其中一个冲突事务。

• Multiversion concurrency control (MVCC)

  通过允许出现多个带有时间戳的记录版本，可以保证数据库在过去某个时间点上的一致视图。MVCC可以使用验证技术实现，只允许一个更新或提交事务成功，也可以使用无锁技术，如时间戳排序，或基于锁的技术，如两阶段锁定。

• Pessimistic (also known as conservative) concurrency control (PCC)

  有基于锁和非锁的保守方法，它们在管理和授予对共享资源的访问的方式上有所不同。基于锁的方法要求事务维护数据库记录上的锁，以防止其他事务修改已锁定的记录，并在事务释放其锁之前评估正在修改的记录。非锁定方法维护读写操作列表并限制执行，这取决于未完成事务的时间表。当多个事务为了继续进行而等待对方释放锁时，悲观计划可能会导致死锁。

可串行性(Serializability)

事务由对数据库状态执行的读写操作和业务逻辑(应用于读取内容的转换)组成。从数据库系统的角度来看，计划是执行一组事务所需的操作列表(即，仅与数据库状态交互的操作，如读、写、提交或中止操作)，因为所有其他操作都假定是没有副作用的(换句话说，对数据库状态没有影响)。

如果一个计划包含了它所执行的每个事务的所有操作，那么这个计划就是完整的。正确的调度在逻辑上等同于原始的操作列表，但它们的部分可以并行执行，或者为了优化的目的而重新排序，只要这不违反ACID属性和单个事务结果的正确性。

当调度中的事务完全独立执行且没有任何交错时，它被称为串行调度:在下一个事务开始之前，前一个事务都被完全执行。与多个多步骤事务之间所有可能的交错相比，串行执行很容易理解。然而，总是一个接一个地执行事务会极大地限制系统吞吐量并损害性能。

我们需要找到一种方法来并发执行事务操作，同时保持串行调度的正确性和简单性。我们可以通过可序列化的时间表来实现这一点。如果调度等价于在同一组事务上的某个完整的串行调度，那么它就是可序列化的。换句话说，它产生的结果与我们按某种顺序依次执行一组事务的结果相同。图4显示了三个并发事务和可能的执行历史(3!= 6
种可能性，以每一种可能的顺序)。

事务隔离(Transaction Isolation)

事务性数据库系统允许不同的隔离级别。隔离级别指定事务的某些部分如何以及何时对其他事务可见。换句话说，隔离级别描述事务与其他并发执行事务的隔离程度，以及在执行期间可能遇到的异常类型。

实现隔离是有代价的:为了防止不完整的或临时的写在事务边界上传播，我们需要额外的协调和同步，这将对性能产生负面影响。

读写异常

SQL标准描述了并发事务执行过程中可能发生的读异常:脏读、不可重复读和幻读。

脏读是指事务可以从其他事务中读取未提交的更改。例如，事务T1
用地址字段的新值更新用户记录，事务T2
在T1
提交之前读取更新后的地址。事务T1
中止并回滚其执行结果。然而，T2
已经能够读取这个值，因此它访问了从未提交过的值。

不可重复读(有时称为模糊读)是指事务两次查询同一行并获得不同结果的情况。例如，即使事务T1
读取一行，然后事务T2
修改该行并提交更改，也会发生这种情况。如果T1
在执行结束前再次请求同一行，结果将与上一次运行不同。

如果我们在事务期间使用范围读取(即，不是读取单个数据记录，而是读取一段范围的记录)，我们可能会看到幻读记录。幻读是当事务两次查询相同的行集并收到不同的结果时。它类似于不可重复读，但用于范围查询。

还有一些语义类似的写异常:丢失更新(lost update)、脏写(dirty write)和写倾斜(write skew)。

当事务T1
和事务T2
都尝试更新V
的值时，就会发生更新丢失。由于事务不知道彼此的存在，如果允许它们都提交，T1
的结果将被T2
的结果覆盖，T1
的更新将丢失。

脏写是这样一种情况，其中一个事务接受一个未提交的值(即脏读)，修改它并保存它。换句话说，当事务结果基于从未提交过的值时。

当每个单独的事务都符合所需的不变量，但它们的组合不满足这些不变量时，就会发生写倾斜。例如，事务T1
和T2
修改两个账户A1
和A2
的值。A1
从100
美元开始，A2
从150
美元开始。账户值允许为负，只要两个账户的和是非负的:A1 + A2 >= 0
。T1
和T2
分别尝试从A1
和A2
提取200
美元。因为在这些交易开始的时候A1 + A2 = 250
美元，总共有250
美元可用。这两个事务都假定它们保留了不变量，并且允许提交。在执行之后，A1
有-100
美元，A2
有-50
美元，这显然违反了保持账户的总和为正的要求。

隔离级别

最低(换句话说，最弱)隔离级别读取未提交。在此隔离级别下，事务系统允许一个事务观察其他并发事务的未提交更改。换句话说，脏读是允许的。

我们可以避免一些异常。例如，我们可以确保特定事务执行的任何读取操作只能读取已经提交的更改。但是，不能保证事务在以后的阶段再次尝试读取相同的数据记录时，会看到相同的值。如果在两个读取之间有一个提交的修改，那么同一个事务中的两个查询将产生不同的结果。换句话说，脏读是不允许的，但幻像和不可重复读是允许的。此隔离级别称为已提交读。如果进一步禁止不可重复读，就会得到一个可重复读隔离级别。

最强的隔离级别是可序列化性，它保证事务结果将以某种顺序出现，就像事务是串行执行的一样(也就是说，不会在时间上重叠)。不允许并发执行会对数据库性能产生重大的负面影响。事务可以被重新排序，只要它们的内部不变量保持不变并且可以并发执行，但是它们的结果必须以某种串行顺序出现。

隔离级别及其允许的异常情况如图5所示。

没有依赖关系的事务可以以任何顺序执行，因为它们的结果是完全独立的。不像线性化，序列化是多个操作以任意顺序执行的属性。它并不意味着或试图在执行事务时强加任何特定的顺序。在ACID术语中，隔离意味着可序列化。不幸的是，实现序列化需要协调。换句话说，并发执行的事务必须协调以保持不变量，并对冲突的执行施加串行顺序。

有些数据库使用快照隔离。在快照隔离下，事务可以观察在其启动时提交的所有事务执行的状态更改。每个事务获取数据的快照并对其执行查询。在事务执行期间不能更改此快照。事务只有在它已修改的值在执行时没有更改时才提交。否则，它将被中止并回滚。

如果两个事务试图修改相同的值，则只允许其中一个提交。这防止了丢失的更新异常。例如，事务T1
和事务T2
都试图修改V
。它们从快照中读取V
的当前值，快照中包含在它们开始之前提交的所有事务的更改。无论哪个事务首先尝试提交，都会提交，而另一个事务将不得不中止。失败的事务将重试，而不是覆盖该值。

在快照隔离下，写倾斜异常是可能的，因为如果两个事务从本地状态读取，修改独立的记录，并保留本地不变量，它们都被允许提交。

死锁(Deadlocks)

在锁定协议中，事务试图获取数据库对象上的锁，如果不能立即授予锁，则事务必须等待，直到锁被释放。当两个事务试图获取它们需要的锁以继续执行时，可能会出现这样的情况:它们互相等待对方释放它们持有的其他锁。这种情况称为死锁。

图6显示了一个死锁的例子:T1
持有锁L1
，等待锁L2
被释放;T2
持有锁L2
，等待锁L1
被释放。

处理死锁的最简单方法是引入超时并在假定长时间运行的事务可能陷入死锁的情况下中止它们。另一种策略是保守2PL
，它要求事务在执行任何操作之前获取所有锁，如果不能执行则终止。然而，这些方法极大地限制了系统的并发性，数据库系统主要使用事务管理器来检测或避免(换句话说，防止)死锁。

检测死锁通常使用等待图，它跟踪正在运行的事务之间的关系，并建立它们之间的等待关系。

图中的周期表明存在死锁:事务T1
在等待T2
，而T2
又在等待T1
。死锁检测可以是周期性的(每间隔一次)或连续的(每次等待图更新时)。其中一个事务(通常是最近试图获取锁的事务)被终止。

为了避免死锁并将获取锁限制在不会导致死锁的情况下，事务管理器可以使用事务时间戳来确定它们的优先级。时间戳越低，优先级越高，反之亦然。

如果事务T1
试图获取当前由T2
持有的锁，并且T1
具有更高的优先级(它在T2之前启动)，我们可以使用以下限制之一来避免死锁:

• Wait-die

  T1
  允许阻塞和等待锁。否则，T1
  将被中止并重新启动。换句话说，事务只能被具有更高时间戳的事务阻塞。

• Wound-wait

  终止T2
  并重新启动。否则(如果T2
  在T1
  之前已经启动)，则允许T1
  等待。换句话说，事务只能被时间戳较低的事务阻塞。

事务处理需要一个调度程序来处理死锁。同时，闩锁依赖于程序员确保死锁不会发生，而不依赖于死锁避免机制。

锁(Locks)

如果两个事务同时提交，修改重叠的数据段，其中任何一个都不应该观察到另一个的部分结果，从而保持逻辑一致性。类似地，来自同一事务的两个线程必须观察相同的数据库内容，并能够访问彼此的数据。

在事务处理中，保护逻辑和物理数据完整性的机制是有区别的。相应的，负责逻辑完整性和物理完整性的两个概念是锁和闩锁。

锁用于隔离和调度重叠的事务，管理数据库内容，而不是内部存储结构，并根据密钥获取。锁可以保护一个特定的密钥(无论它是存在的还是不存在的)或一组密钥。锁通常在树实现的外部存储和管理，并代表一个更高级别的概念，由数据库锁管理器管理。

锁比闩锁更重量级，并在事务期间持有。

闩锁(Latches)

另一方面，闩锁保护物理表示:叶页内容在插入、更新和删除操作期间被修改。在导致从叶下传播和溢出的拆分和合并的操作期间，修改非叶页内容和树结构。在这些操作期间，闩锁保护物理树表示(页面内容和树结构)，并在页面级别获得。任何页面都必须被锁定以允许安全的并发访问。无锁并发控制技术仍然必须使用闩锁。

由于在叶级上的单个修改可能会传播到B-Tree的更高级别，因此可能必须在多个级别上获得闩锁。执行查询不应该能够观察处于不一致状态的页面，比如未完成的写或部分节点分割，在此期间，数据可能同时存在于源节点和目标节点中，或者还没有传播到父节点。

同样的规则也适用于父或兄弟指针更新。一般的规则是保持闩锁的时间尽可能短—-即在读取或更新页时—-以增加并发性。

并发操作之间的干扰大致可以分为三类:

• Concurrent reads

  当多个线程访问同一个页面而不修改它时。

• Concurrent updates

  当多个线程试图对同一个页面进行修改时。

• Reading while writing

  当一个线程试图修改页面内容，而另一个线程试图访问相同的页面进行读取时。

Readers-writer lock

最简单的闩锁实现将授予请求线程独占读/写访问权。然而，在大多数情况下，我们不需要将所有进程彼此隔离。例如，读取可以并发访问页面而不会造成任何麻烦，因此我们只需要确保多个并发写入器不重叠，读写器和写入器不重叠。为了达到这种粒度级别，我们可以使用读写器锁或RW锁。

RW锁允许多个读操作并发访问对象，只有写操作必须获得对对象的独占访问。读写锁的兼容性表如图7所示:只有读写锁可以共享锁的所有权，而所有其他读写组合应该获得独占所有权。

在图8(a)中，我们有多个读取器访问对象，而写入器正在等待轮到它，因为当读取器访问它时，它不能修改页面。在图8(b)中，writer 1
持有对象的排他锁，而另一个writer和三个reader必须等待。

由于试图访问同一页的两次重叠读不需要同步，只需要防止页缓存从磁盘提取两次，因此可以在共享模式下安全地并发执行读操作。一旦写开始起作用，我们就需要将它们与并发读和其他写隔离开来。

Latch crabbing

获取闩最直接的方法是在从根到目标叶子的过程中获取所有闩。这就造成了并发瓶颈，在大多数情况下是可以避免的。应尽量缩短闩锁的时间。可以用来实现这一目标的一种优化方法叫做Latch crabbing。

Latch crabbing是一种相当简单的方法，它允许在更短的时间内持有闩，并在明确执行操作不再需要它们时释放它们。在读路径上，只要找到了子节点并获得了它的闩锁，就可以释放父节点的闩锁。

在插入期间，如果保证操作不会导致可以传播到父锁存器的结构变化，则可以释放父闩锁。换句话说，如果子节点未满，则可以释放父闩锁。

类似地，在删除期间，如果子节点拥有足够的元素，并且操作不会导致兄弟节点合并，父节点上的闩锁就会被释放。

插入时根到叶的通道如图9所示:

• a)写锁存是在根级获得的。
• b)找到下一级节点，并获得其写锁存。检查节点的潜在结构变化。由于节点未满，可以释放父闩锁。
• c)操作下降到下一级。获取写闩锁，检查目标叶节点的潜在结构变化，并释放父闩锁。

这种方法是乐观的:大多数插入和删除操作不会导致结构更改，从而向上传播多个级别。事实上，结构变化的可能性在较高的层次上降低。大多数操作只需要目标节点上的闩锁，并且必须保留父闩锁的情况相对较少。

总结

在本文中，讨论了负责事务处理和恢复的存储引擎组件。在实现事务处理时，会遇到两个问题:

• 为了提高效率，我们需要允许并发事务执行。
• 为了保持正确性，我们必须确保并发执行的事务保留ACID属性。

并发事务执行可能导致不同类型的读写异常。通过实现不同的隔离级别来描述和限制这些异常的存在或不存在。并发控制方法确定如何调度和执行事务。

页面缓存负责减少磁盘访问的数量:它在内存中缓存页面并允许对它们进行读写访问。当缓存达到其容量时，页面将被移除并刷新回磁盘上。为了确保在节点崩溃的情况下不会丢失未刷新的更改，并支持事务回滚，我们使用提前写日志。页面缓存和预写日志使用强制和窃取策略进行协调，确保每个事务都能有效执行和回滚，而不会牺牲持久性。

感兴趣的关注如下公众号！