本节书摘来自华章出版社《云数据管理：挑战与机遇》一书中的第二章，第2.3节，作者[美] 迪卫艾肯特•阿格拉沃尔（Divyakant Agrawal） 苏迪皮托•达斯（Sudipto Das）阿姆鲁•埃尔•阿巴迪（Amr El Abbadi） 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2.3 数据库系统
本节中，我们将为数据库系统中的一些主要概念提供一个相当抽象、简洁和高层次的描述。知识体系与Bernstein et al. [1987]一致。对数据库知识比较熟悉的读者可以跳过本部分内容。
2.3.1 预备知识
数据库由对象的集合组成，如x、y、z。假设每个对象都有一个值，所有对象的值构成了数据库的状态。通常情况下，这些状态必须满足数据库的一致性约束。数据库对象支持两种原子操作：针对x的读和针对x的写，或者r[x]和w[x]。事务的概念在数据库系统中至关重要。一个事务是按照一定偏序执行的操作的集合。事务ti执行的操作记作ri[x]和wi[x]。如果一个事务是正确的，即，如果一个事务在一致数据库上单独执行，那么该事务可以将数据库转换成另外一个一致状态。
事务的执行必须是原子的，即必须满足如下两个属性：
1. 事务之间互不干扰。
2. 事务中的操作要么全部执行，要么都不执行。
事务ti以commit(ci)或abort(ai)操作结束。并发控制协议可以确保并发执行的事务彼此之间互不影响。恢复协议可以确保all-or-nothing属性。
如果两个操作的执行顺序对结果有影响，即，如果其中一个是写操作，那么这两个操作是冲突的。给定一个事务集合T，T上的一个历史H是针对所有事务操作的偏序，该顺序反映了操作执行的顺序（事务顺序和冲突操作顺序）。
数据库管理系统必须满足ACID特性，即
原子性（atomicity）：每个事务要么全部执行，要么都不执行，即all-or-none属性。
一致性（consistency）：每个事务是一个一致的执行单位。
隔离型（isolation）：事务之间互不影响。
持久性（durability）：事务的效果是永久的。
当一个并发事务集合执行时，事务的正确性概念必须以每一个事务都是一致的（ACID中的C）为前提，因此，如果事务是隔离执行的，数据库将从一个一致状态转换成另外一个一致状态。因此，如果事务集合串行执行，那么可以保证其正确性。特别是，对于一个调度H中的任意两个事务ti和tj，如果ti的所有操作在H中都位于tj的所有操作之前，或者相反，那么H是串行的。
为了允许事务之间在一定程度上并发执行，产生了可串行化的概念。如果一个历史的执行结果与一个串行历史的执行结果等价，那么该历史是可串行化的。如果两个历史产生相同的结果，即所有的事务写入相同的值，我们认为这两个历史是等价的。由于我们不知道哪些事务执行写操作，事务就需要从相同的事务中读数据，最终写入的值也相同。不幸的是，识别可串行化的历史是NP完全问题[Papadimitriou, 1979]。因此，产生了一个更强的可串行性概念，称之为冲突可串行性。
回想一下，如果针对相同对象的两个操作中，至少有一个是写操作，那么这两个操作是冲突的。如果两个历史H1和H2定义在相同的操作集合之上（相应的事务集合也相同），并且这两个历史中所有的冲突操作的顺序都一致，那么H1和H2是冲突等价的。如果一个历史H和某一个串行历史Hs是冲突等价的，那么H就是冲突可串行化的。既然串行执行是正确的，那么就可以保证冲突可串行化历史也是正确的。
2.3.2 并发控制
并发控制协议必须能够保证冲突可串行性。并发控制协议一般可以分为悲观协议（pessimistic protocol）和乐观协议（optimistic protocol）两种，悲观协议使用锁来避免错误的操作，而乐观协议是在提交阶段采用验证器（certifier或validator）来保证正确性。一般情况下，从技术的角度来看，任何并发控制协议都可以很容易地扩展到分布式环境中。
*协议
对于每一个操作，事务（或并发控制调度器）都会申请一个锁，每个锁都有两种模式：读和写。两个读锁是相容的，而两个写锁或者一个读锁和一个写锁是不相容的。如果一个数据项没有以不相容的模式*，那么该数据项就可以授予锁。否则，存在一个锁冲突，并且事务处于*状态（会经历锁等待）直到当前的锁持有者释放锁。一个操作执行完成后，相应的锁就会被释放。锁本身不足以保证正确性。两段锁协议增加了下列条件，以下条件足以保证冲突可串行性[Eswaran et al., 1976]：
一旦一个事务释放了一个锁，该事务不能随即获取任何数据项的任何其他锁。
图2-9显示，在扩展阶段，事务所需要的锁的数量不断增加，在收缩阶段，锁的数据逐渐减少
两段锁在很多商业化系统中广受欢迎，尤其是严格版本，在事务结束之前（即提交或中断），保留所有的锁。然而，两段锁可能会出现死锁。而且由于冲突操作的存在，数据项队列可能导致数据冲突。这种冲突可能导致系统抖动（在常规多道程序设计系统中，资源冲突一般是由内存、处理器、I/O通道引起的，而不是数据引起的冲突）。
乐观协议
如上所述，*可能造成长时间的资源阻塞。乐观并发控制协议可以允许事务执行所有操作，并使用验证方法来判断其他事务是否执行了冲突操作，通过这种方式可以有效避免这种阻塞。最简单的情况是，事务t1执行其所有操作（写操作会导致本地缓存更新）。当事务提交时，调度器会检查是否有活动的事务执行了冲突操作，如果有，就中止t1。
Kung and Robinson [1981]对上述简单思想进行了扩展，通过三个阶段来执行每个事务t1：
读阶段。在该阶段，事务可以无限制地读取任何对象，而写是本地的。
验证阶段。在该节点，调度器通过检查所有的并发事务t2从而确保没有冲突发生，即可以检查事务t2在其写阶段进行写操作的对象集合与事务t1在其读阶段进行读操作的对象集合是否重叠，如果有重叠，则中止t1。
写阶段。验证成功以后，值可以写入数据库中。
简单的正确性证明显示乐观并发控制可以确保事务的可串行化执行。该协议出现了很多种变体，而且由于乐观协议在数据资源上不会产生排它锁，因此，乐观协议在云计算环境中的应用越来越广泛。
2.3.3 恢复和提交
集中式恢复
故障恢复是数据库管理系统不可分割的一部分。集中式恢复可以在单站点数据库在磁盘上存储所有数据时确保其持久性或永久性。为了在确保原子性的同时实现故障恢复，很多机制在事务执行的过程中都使用持久性存储设备，如磁盘，从而确保all-or-nothing属性。下面是3种常用的方案。
1. 影子页：在磁盘上保存两份数据库备份，其中一个用于事务更新，当事务提交时，原子指针切换到新的数据库备份。
2. 前像文件：磁盘日志用来存储所有更新数据项的前像文件（before-image），事务会立即更新物理数据库。一旦故障出现并且事务尚未提交，数据库就会根据日志恢复到初始状态。
3. 后像文件：所有更新操作在后像文件（after image）日志中执行。事务提交后，根据日志，将所有的后像文件装载到数据库中。
在这些基本概念的基础上，提出了各种各样的恢复方法。这些方法以不同的方式对前像文件日志和后像文件日志进行组合，从而提高提交事务或中止事务的性能[Bernstein and Newcomer, 2009, Gray and Reuter, 1992, Weikum and Vossen, 2001]。
从集中式数据库扩展到分布式数据库（即对象可能存在于不同的站点上）的关键挑战是：当故障出现时，如何在不同站点之间确保原子性。下面将介绍主要的分布式提交协议。
原子提交（atomic commitment）
提交的根本问题是由于事务在多个服务器上执行操作而引起的。全局提交需要所有参与者的一致本地提交。分布式系统可能会部分失效，在特殊情况下，服务器可能崩溃，极端情况下，会出现网络故障，从而导致网络划分。这可能会导致不一致的决定，即，在某些服务器上事务完成了提交，而在其他服务器上，事务却中止了。
基本的原子提交协议是一种简单的分布式握手协议，称为两阶段提交协议（two-phase commit, 2PC）[Gray, 1978]。在该协议中，协调者（事务管理者）负责一致决定：提交或中止。其他所有的执行事务的数据库服务器在该协议中都是参与者，都依赖于该协调者。提交时，协调者向所有参与者请求选票。原子提交要求所有进程得到相同的决定，特别是，只有当所有进程都投赞成（yes）票时，事务才能提交。因此，如果没有故障发生，并且所有的进程都投赞成（yes）票时，最终结果才可以提交。
该协议执行过程如下。协调者向所有参与者发送投票请求（vote-request）。当参与者接收到投票请求消息时，如果能本地提交，就返回一个yes消息，如果需要中止该事务（由于死锁或者无法把本地操作写到磁盘上），就返回no消息。协调者收集所有投票，如果都是赞成票（yes），那么就认为事务已经提交，否则事务就被中止了。协调者将结果发送给所有参与者，参与者相应地对本地事务进行提交或中止。
如果一个站点没有接收到预期的消息，该站点会怎么做呢？注意，该协议假设分布式系统是异步的，因此，其中有一个超时机制。有以下3种情况需要考虑。
1. 参与者等待投票请求：这种情况下，参与者在本地中止事务是安全的。
2. 协调者等待投票：这种情况下，协调者也可以安全地中止事务。
3. 参与者等待最终决定：这是一种不确定的情况，由于事务可能已经提交或者中止，因此，参与者也可能是不确定的，参与者可能不知道实际的决定。而有趣的是，协调者是确定的。
接下来详细探讨不确定参与者的情况。实际上，该参与者可以向其他参与者询问最终决定并寻求帮助。一旦任何参与者已提交或中止，该参与者就可以发送提交或中止决定。如果一个参与者尚未投票，那么它就可以安全地中止该事务，并可以向其他参与者发送中止决定。然而，如果所有参与者都投赞成票（yes），那么所有活动的参与者都是不确定的。这种情况下，该事务就被认为已阻塞，所有活动的参与者都需要一直等待，直到有足够多的站点赞成该事务进行恢复的决定。直观来看，活动的参与者处于不确定状态，其他一些失败的参与者可能处于提交状态，还有一些参与者处于中止状态。一般来说，两阶段提交协议即使是在简单的系统崩溃故障情况下也可能存在阻塞问题。
为了解决阻塞问题，可以引入中间缓冲状态，这样一来，如果任何运行站点是不确定的，那么，所有进程都不能提交[Skeen and Stonebraker,1983]。这种协议就是三阶段提交协议，该协议在站点故障情况下是非阻塞的。然而，三阶段提交协议不允许分区故障。实际上，可以证明在分区故障情况下，不存在非阻塞原子提交协议[Skeen and Stonebraker, 1983]。
总之，分布式数据库中的提交协议可能导致高复杂度和潜在的阻塞问题。实际上，其他站点的故障可能导致本地数据不可用。分布式数据库需要大量的额外开销来确保执行的正确性。这种对全局同步机制的依赖会限制系统的可扩展性，并对容错性和数据可用性产生重要影响。上述所有原因及其他因素（与不同地点的数据权限有关）共同导致分布式数据库的商业化应用较少。