分布式数据库的可串行化理论及并发控制

2023-10-28 理论教育版权反馈

【摘要】：分布式数据库管理系统的并发控制是为了保证多用户分布环境下的数据库一致性。可串行化是涉及并发控制的一个重要理论。条件1表示调度涉及的域是一个由各个事务构成的集合。例9.2所示的是一个串行调度。下面我们讨论可串行化的问题。定义9.3 一个调度Sc是可串行的，当且仅当Sc冲突等价于一个串行调度，这种可串行化通常称为冲突等价可串

并发控制（concurrency control）是为了保证事务的隔离性（I）和一致性（C）。

分布式数据库管理系统的并发控制是为了保证多用户分布环境下的数据库一致性。如果事务内部一致（即不损害任何一致性约束），最简单的方法是让每一个事务单独执行，一个接着一个，互不干扰。当然，这只是理论上合理，实施起来无意义，因为这么做会把系统的吞吐量弄得很小，这不是我们所期待的。并发程度（并发事务的个数）是分布式数据库系统性能好坏的重要参数之一。因此，数据库系统的并发控制机制力图找出一个折中，使得既能保持数据库的一致性，又能维持高度的并发性。

现在我们假设整个分布式系统是完全可靠的，既没有任何软件故障，又没有硬件故障。尽管这是不现实的，但是可以简化我们的讨论。关于可靠性问题我们将在下一章讨论。

可串行化（serializability）是大家广泛认同的能保证并发控制算法正确性的依据。可串行化是涉及并发控制的一个重要理论。为了说明这个理论，我们需要先给出一些定义。

调度（schedule）是指一个调度S（也称历史（history））定义在一个事务集合T上，T=｛T1，T2，…，Tn｝，它可以指定这些事务的执行序。

对于任意一对操作aij（x）和akl（x）（i和k是事务标识，不必一样，即这两个操作可以属于不同的事务），它们存取同一个数据库的数据项x，如果它们中间有一个是写（write）操作，则它们是冲突（conflict）的。这样可以将这两个操作简单标为“读”和“写”，从而归结成两类冲突：读-写（read-write）（或写-读（write-read））冲突和写-写（write-write）冲突。其实，这两个操作可能来自同一个事务，也可能来自不同的事务。如果来自不同的事务，则这两个事务是冲突的。

下面先来定义一个完整调度（complete schedule），该调度定义了该域里所有操作之间的执行序。

定义9.1 一个完整调度的前缀是指由该域的事务子集构成的偏序，令POT为事务子集上的完整调度，则T=｛T 1，T 2，…，Tn｝构成一个偏序POT=｛ΣT，≯T｝，其中：

pagenumber_ebook=180,pagenumber_book=165

条件3：对于任意两个冲突操作而言，aij，akl∈ΣT，aij≯T akl，或者akl≯T aij。

条件1表示调度涉及的域是一个由各个事务构成的集合。条件2定义了一个序，它是各个事务序集合的超集。条件3强调任意一对冲突操作间必须有一个序。

【例9.1】考虑两个事务T 1和T 2的序：

T1: Read(x)

pagenumber_ebook=181,pagenumber_book=166

这样，关于这两个事务的一个完整调度POT为T=｛T 1，T 2｝，POT=｛ST，≯T｝，存在：

Σ1=｛r1（x），w1（x），C1｝

Σ2=｛r2（x），w2（x），C2｝

这样，ΣT=Σ1∪Σ2=｛r1（x），w1（x），C1，r2（x），w2（x），C2｝，且POT=｛〈r1，r2〉，〈r1，w1〉，〈r1，C1〉，〈r1，w2〉，〈r1，C2〉，〈r2，w1〉，〈r2，C1〉，〈r2，w2〉，〈r2，C2〉，〈w1，C1〉，〈w1，w2〉，〈w1，C2〉，〈C1，w2〉，〈C1，C2〉，〈w2，C2〉｝

这个调度可以用一个有向无环图（即DAG图）来表示，如图9.1所示。

我们可以使用简化一点的方式来描述这样一个调度，因为可以忽略那些无需强调的序，如〈r1，r2〉，〈r1，C1〉^[1]等。可以让执行序与表中操作的顺序对应，这样POT可简化为：

POT=［r1（x），r2（x），w1（x），C1，w2（x），C2］

可以将一个调度P看成是一个完整调度P的前缀。

给定一个偏序P=｛Σ，≯｝，令P=｛Σ，≯｝为P的一个前缀，如果满足：

pagenumber_ebook=181,pagenumber_book=166

图9.1　一个完整调度的DAG表示

（1）Σ⊆Σ；

（2）∀ai∈Σ，a1≯a2 iff a1≯a2；

（3）ai∈Σ，if∃aj∈Σ∧aj≯ai，then aj∈Σ。

前两个条件把P的域S定义在P的域S上，P中的序仍然保持在P中。第三个条件表示S中的所有元素，如果在S中有前元（predecessor），则它们在S中也有前元。

【例9.2】我们来看如下三个事务：

pagenumber_ebook=181,pagenumber_book=166

从以上事务可以看出，如下调度S是串行的（serial）：(www.chuimin.cn)

S=［w2（x），w2（y），r2（z），C2，r1（x），w1（x），C1，r3（x），r3（y），r3（z），C3］

因为T 2的所有操作都在T 1的所有操作前执行，T 1的所有操作都在T3的所有操作前执行，所以可以记作T 2≯s T 1≯s T 3或T 2→T 1→T 3。

例9.2所示的是一个串行调度。

串行调度能保证事务的一致性，但是系统的效率低。有更有效的办法吗？下面我们讨论可串行化的问题。

定义9.2 在一个调度S中，若各个事务的操作执行时不叠加（即操作一个接着一个发生），则这个调度是串行的。

两个调度S1和S2定义在相同的事务集上，如果它们对数据库产生相同的效果，则称为是等价的。更形式化地说，如果S1和S2定义在相同的事务集上，对它们中任意一对冲突操作aij和akl（i≠k）来说，如果aij≯S1 akl，则aij≯S2 akl，反之亦然，我们称之为冲突等价（conflict equivalence）。两个满足冲突等价的调度是等价的。

两个调度的等价条件可以定义如下。

条件1：在两个调度中，每个读操作读到的是相同写操作产生的数据。

条件2：且两个调度中对每个修改数据项的最后一个写操作相同。

【例9.3】再考虑例9.2中的三个事务，S是一个定义在三个事务上面的调度，它的冲突等价于串行S：

S=［w2（x），r1（x），w1（x），C1，r3（x），w2（y），r3（y），r2（z），C2，r3（z），C3］

这里：对x来说，按照冲突操作对的序，则T2→T1→T3；对y来说，按照冲突操作对的序，则T 2→T 3；对z来说，r2（z）和r3（z）不冲突，不需要强加序。因此，S等价于T2→T 1→T 3。

注意，冲突等价满足第三级一致性。

定义9.3 一个调度Sc是可串行的（serializable），当且仅当Sc冲突等价于一个串行调度，这种可串行化通常称为冲突等价可串行化（serializability）。

并发控制器的基本功能是产生一个要执行事务的可串行化调度。

可串行化理论可以简单地用于无副本的分布式数据库中。我们把每个节点上事务执行的调度称为本地调度，整个分布式数据库上的调度称为全局调度。此时，如果一个全局调度的每个本地调度是可串行的，且每个本地串行调度序是相同的，则这个全局调度是可串行的。在有副本的分布式数据库系统中，可串行化理论的要求更复杂些。

【例9.4】我们来看以下两个事务：

pagenumber_ebook=182,pagenumber_book=167

它们同时在两个副本所在地，也就是在两个节点上运行。下面是两个节点上的本地调度：

S1=［r1（x），w1（x），C1，r2（x），w2（x），C2］

S2=［r2（x），w2（x），C2，r1（x），w1（x），C1］

这两个调度都是可串行化的，确切来说是串行的。因此每一个调度代表一个正确的执行序。但要指出的是，在这两个调度中，T 1和T2的序是互相颠倒的，即S1等价于T1→T 2，S2等价于T 2→T 1。

如果在执行这两个事务前x的值是10，结果在执行这两个事务后，x在S1为150，在S2为105。

例9.3在现实中是不允许的，我们要求S1和S2应当满足互一致性。互一致性要求所有的副本数据值都是一样的。

直观地说，一个单副本可串行化全局调度必须满足如下条件。

●每个本地调度都是可串行化的。

●两个冲突操作在它们同时出现的所有本地调度中都必须有相同的序。

第二个条件保证在冲突事务一起执行时，所有节点上的串行序是相同的。

显然，在有副本的数据库中，需要附加副本控制协议。

假设一个数据项x有副本x1，x2，…，xn。下面我们把x称为逻辑数据项，其副本称为物理数据项。如果提供副本透明度，用户事务就对逻辑数据项x发布读/写操作要求。副本控制协议负责把逻辑数据项x上的每个读操作（Read（x））映射到一个物理数据项副本的读操作（Read（xj））上。将逻辑数据项x上的每个写操作映射到所有x的物理数据副本子集的写操作集上。是映射到物理数据项副本的全集还是子集取决于副本控制算法。如果把读操作映射到其中一个副本上，那么写操作就映射到一个物理数据项副本的全集上，这个算法就满足readonce/write-all（ROWA）协议。

分布式数据库的可串行化理论及并发控制

相关推荐