计算机工程
Computer Engineering
1999年　第25卷　第4期　Vol.25　No.4　1999



WCSR: 一个弱一致性的复制数据库系统
李霖　周兴铭
摘　要　介绍了一个弱一致性的复制数据库系统WCSR。系统支持服务器的移动性与断接，采用Read-Any-Write-Any复制范型，通过周期同步方式维护系统的一致性（并发事务的Epsilin-可串性），并且支持可变一致性的事务处理，因此非常适合移动计算机环境。
关键词　移动计算机复制弱一致性Epsilin-可串性
WCSR：A Weakly Consistent Replicated Database System
LiLing Zhou Xinmin
（Dept.of Computer,National Univ.of Defence Tech.Change 410073)
Abstarct:This paper presents a weakly consistent replicated database system,called WCSR.WCSR supports mobile server and its disconnection,provides Read-Any-Write-Any replication for databases,and maintains comsistency (Epsilon-serializability)by periodic pairwise synchronization.WCSR can also support variable-consistency transaction processing.Finally,we argue that WCSR is suitable for mobile computing environments.
Key words:Mobile computing;Replication;Weak consistency;Epsilon-serializability.s
　　数据复制是指在多个结点上维护数据库的备份，其主要目的是提高分布式数据库系统的可用性、可靠性或访问性能。在移动计算环境[1,2]中，可移动的数据库服务器可能与其它服务器暂时断接，而严格一致性复制协议不能有效地支持这种需求；另一方面，与可用性相比，许多应用宁可放弃严格的一致性。因此，针对移动计算环境，我们设计了一个弱一致性复制数据库系统，称作WCSR。WCSR系统的主要设计目标为：支持服务器的移动性与暂时断接；采用Read-Any-Write-Any复制机制；保证整个系统的彻底收敛性；维护并发事务的Epsilon-可串性；支持用户事务的弱一致性与可变一致性等。
1　WCSR系统概述
　　WCSR系统采用关系数据模型。所有复制服务器的总和构成一个复制集合，其中每一个复制服务器S都拥有一个全局唯一的标识符，记作S.id。每个复制服务器都可以与其他任意服务器直接通信。假设网络通信是面向连接的，那么消息传递保持正确的次序。WCSR服务器可以建立在移动计算机上，因此可能与其他服务器暂时断接。
　　用户对复制服务器的访问以事务为基本单位。事务由一系列读/写操作组成。我们把只含有读操作的事务称作查询事务(只读事务)，含有写操作的事务称作更新事务。服务器保留更新事务的Undo与Redo日志，因此可以回滚或重做已完成的更新事务。
　　WCSR系统采用Read-Any-Write-Any的弱一致性复制策略，即每个复制服务器都支持查询与更新操作，并且允许各个复制之间存在暂时的不一致。因此，一个用户在访问数据库时，只需要访问一个复制服务器即可。复制服务器接到一个查询事务之后，根据本地数据库的状态返回查询结果；对于更新事务，服务器则将其记入暂时事务日志中，在本地数据库上执行，并立即返回给用户其标识符和结果，用户不必等待服务器将该事务的结果传递给其他复制服务器，因此具有较短的响应时间。
2　WCSR系统复制一致性的维护
　　在WCSR系统中，用户对复制数据库的更新均以事务为基本单位。因此，维护WCSR系统的一致性，实际上就是维护不同服务器上并发更新事务之间的一致性。
2.1　WCSR服务器的事务处理
　　由于WCSR系统中查询事务的执行不影响复制数据库之间的一致性，因此我们在后面的讨论中忽略查询事务的存在；如无特殊说明，文中提到的事务均指更新事务。
　　WCSR系统允许任意一个复制服务器单独接收并执行更新事务，并在随后的时间里将其传播给其他的服务器，这时不同服务器上的事务之间可能会因为发生冲突而使某些事务的结果被取消(Undo)。因此，与严格一致性复制系统不同，WCSR中事务的执行结果是暂时性的，即暂未永久化，我们把这些事务称作暂时事务，而把永久化的事务称作已提交事务。相应地，数据库中每个记录都包含两个版本：提交版本与暂时版本。提交版本反映了所有已提交事务执行的最新结果，而暂时版本则是本地所有暂时事务执行的最新结果。
　　WCSR系统采用基于时间戳的并发事务控制技术：每个服务器维护一个本地逻辑时钟(各个服务器逻辑时钟之间的同步采用Lamport分布时钟同步算法[3]来维护)。当服务器S接到一个更新事务t时，S根据本地逻辑时钟为t指定一个时间戳ts，并更新逻辑时钟，然后将事务t记入本地暂时事务日志TTL中。最后，服务器S将t的执行结果记录到本地复制数据库的暂时版本中。
　　设首先接收事务t的服务器(称作t的始发服务器)的标识符为t.sid，定义t在WCSR系统中全局唯一的事务标识符为t.id=<t.ts,t.sid>。WCSR系统按照事务id对所有暂时事务进行排序。任意两个暂时事务t1与t2标识符之间的序关系定义如下：

　　WCSR服务器的暂时事务日志TTL记录了所有本地服务器已知的暂时事务，这其中不仅包括用户直接发给本地服务器的事务，还包括从其他复制服务器上传播过来的暂时事务。日志中的所有暂时事务都按照事务id的次序排列。
2.2　WCSR系统的成对同步过程
　　WCSR系统采用周期性的成对同步方式来完成暂时事务的传播和不同复制服务器之间的同步，即：每个同步周期内，服务器随机地选择另一个服务器进行同步，互相交换未知的暂时事务，使两者的数据库状态达成一致。这种成对同步方法已经在一些弱一致性复制系统中得到应用(如Bayou系统[4])，其优点是：网络开销较低；可靠性高，即使发生网络故障，在故障恢复后同步过程将继续把未知的事务传送给其它服务器。
　　WCSR系统中的服务器在成对同步过程中，总是按照事务id(即<ts,sid>)的次序向另一个服务器发送本地的暂时事务日志；接收服务器则将收到的暂时事务日志与本地暂时事务日志合并，并重新按照事务id的次序排列。根据暂时事务传送的这种有序性，每个服务器维护一个时间戳向量NTSV，用于记录本地暂时事务日志中已知的始发于各个复制服务器的暂时事务的最新时间戳。这样，在成对同步过程中，通过比较两个服务器的NTSV向量，一个服务器可以只向另一个服务器传送其未知的暂时事务，而不必传送整个暂时事务日志，大大节约了网络开销。
　　成对同步中的接收服务器接到新的暂时事务之后，将接收到的每个暂时事务t插入到本地暂时事务日志TTL中，同时根据t的标识符<ts,sid>更新本地的NTSV向量。由于这些暂时事务的时间戳可能与本地TTL中的原有暂时事务发生交叉，因此接收服务器需要回滚排在新事务之后的暂时事务，并在新事务插入TTL完毕之后按照新的次序重新执行暂时事务，得到更新的数据库暂时版本。最后，服务器还要根据新得到的事务时间戳判断是否需要调整本地的逻辑时钟。
　　WCSR成对同步过程中的事务日志传递是一种单向的渐进式过程，它只需传送对方未知的事务日志部分，因此对可能发生的网络故障具有很好的容错性。
2.2.1　成对同步过程中的事务冲突
　　服务器在接收其它服务器传播来的更新事务日志时，需要回滚并重做本地的部分暂时事务。由于不同服务器始发的暂时事务之间的并发性，这些重做事务可能与其它事务产生冲突，此时系统必须选择夭折某个事务以消解冲突。
　　为了降低暂时事务重做时的夭折率，WCSR系统采用一种基于应用语义的冲突检测与消解方法。该方法允许应用程序指定暂时事务的冲突条件以及发生冲突后的消解方法，因此能够大大改善事务重做时的成功率。由于篇幅所限，我们将在其它专题论文中详细介绍WCSR系统中基于应用语义的事务冲突检测与消解方法。
2.3　WCSR并发事务的Epsilon-可串性
　　严格一致性复制系统中的并发事务满足单拷贝可串性(1SR[5])准则，而对于采用弱一致性复制协议的WCSR系统，其并发事务的执行不能用1SR描述。为此我们借鉴Calton Pu等针对弱一致性复制系统提出的Epsilon-可串性[6]的概念，作为WCSR并发事务的执行准则。下面我们简单介绍一下Epsilon-可串性的概念。
　　Epsilon-可串性(Epsilon-serializability ，简称ESR)准则允许复制系统采用异步的方式维护各个复制结点间的一致性(即弱一致性)。支持ESR准则的分布式复制系统允许在不同的复制结点之间存在暂时的和有限的差别，但是在所有更新事务传播到每个复制结点之后，所有复制结点的状态将收敛于1SR的一致状态。
　　并发事务执行时产生的数据操作序列称作这些事务的一个执行调度(schedule)。如果一个执行调度中的操作序列都是由顺序执行的事务构成，即不含有交叉的现象，则称该调度是一个串行(serial)调度。对于一个包含查询事务和更新事务的执行调度s，如果从该调度中删除所有查询事务的操作之后，剩下由更新事务操作组成的执行调度s' 是一个串行调度，则称s是一个Epsilon-串行调度。如果一个执行调度的执行结果等价于一个Epsilon-串行调度，则称该调度是Epsilon-可串(serializable)的，即ESR调度。
　　ESR调度允许查询事务与其它更新事务的执行任意交叉，因此查询事务可能会访问到不一致的数据。但是，因为查询事务并不改变数据库的状态，所以ESR调度仍然能够保证维护复制数据库的一致性。
　　WCSR是一个弱一致性复制系统，它允许各个复制服务器上数据库的状态存在暂时的不一致。但是，通过周期性的成对同步过程，WCSR系统总是致力于消除不同服务器之间的不一致性，使整个复制系统收敛于一致的状态。同样，在各个服务器上执行的并发更新事务也将收敛于一个串行的调度序列。可以证明(证明过程略)，在没有新的更新事务产生时，WCSR复制系统中的所有服务器上的数据库状态将最终收敛于一致状态，并且所有服务器始发的并发事务之间满足Epsilon-可串性。
3  暂时事务的永久化
　　在上述讨论中，我们假定事务的执行都是暂时的，即事务结果尚未永久化，可能在成对同步过程中回滚与重做。而事务处理的最终目的是使事务的结果永久化，因此这些暂时事务需要在适当的时候永久化，转变为真正的已提交事务。WCSR系统可以采用两种暂时事务永久化(即提交)算法，它们分别是自然收敛(Natural Converge,简称NC)提交算法和主服务器(Primary Server，简称PS)提交算法。这两种算法各有优缺点，因而适用于不同的环境。限于篇幅，本文只简单介绍一下主服务器提交算法。
3.1　主服务器提交算法
　　主服务器提交算法在WCSR系统中指定一个服务器作为主服务器，由主服务器负责提交所有暂时事务。具体地说，当主服务器PS在与某个服务器成对同步之后，由PS将接收到的暂时事务按照id的次序提交，同时给每个已提交事务分配一个单调递增的提交序列号(记作csn)。随后，这些已提交事务将和暂时事务一样，在成对同步过程中传播给其它的服务器。除了负责提交暂时事务之外，主服务器与其它服务器的功能完全相同。
　　由于WCSR系统中始发于某一个服务器的暂时事务总是按照id的顺序传播到其它服务器，主服务器也不例外，因此在主服务器提交算法中，对于始发于同一个服务器的暂时事务，其提交次序完全是按事务id排序的。但是，主服务器提交算法并不保证所有事务的提交顺序等同于事务id的次序：始发于不同服务器的事务提交次序完全取决于这些事务通过成对同步过程到达主服务器的顺序，因此某些事务的提交可能会落在始发于其它服务器而id更大的事务之后。为了确保复制系统的最终一致性，主服务器提交算法必须保证在每个服务器上已提交事务执行的次序都是一样的，为此需要对WCSR系统中事务日志的组织以及成对同步过程加以修改。
　　在采用主服务器提交算法的WCSR系统中，服务器的事务日志由两个部分组成，即已提交事务部分和暂时事务部分。由于已提交事务的结果已经永久化，因此其执行次序以及结果不会再发生变化，而暂时事务部分却可能在稍后的成对同步中回滚、重排与重做，所以在事务日志中，所有已提交事务必须排列在任意暂时事务之前。但是，主服务器提交算法中事务的提交次序不同于事务id的次序，因此我们改为根据<csn,id>的次序对事务日志排序，并将暂时事务的csn设为无穷大。事务的<csn,id>次序关系定义为：

　　于是，服务器之间的成对同步过程不仅要交换未知的暂时事务，还需要交换未知的已提交事务。与暂时事务类似，为了在同步过程中判断哪些已提交事务是对方未知的，每个服务器S都要维护一个变量S.LCSN，即S的事务日志中已提交事务csn的最大值，用以表示S已知的已提交事务部分。
　　容易证明，虽然主服务器提交算法不保证事务提交的顺序等同于事务id的顺序，但在使用主服务器提交算法的WCSR系统中，每个服务器上的事务提交顺序仍然是一致的，因此其并发事务的执行仍是满足Epsilon-可串性的。
4　可变一致性事务
　　WCSR系统主要面对的是强调可用性的弱一致性应用。但是，即使是弱一致性应用也可能在必要的时候要求严格的一致性，即一个更新事务发给服务器之后要求立即提交，而且其结果也立即永久化，不会再发生回滚与重做的现象。
　　在WCSR系统中，我们把需要立即提交的更新事务称作强事务(Strict Transaction，简称ST)，相应地，把前面讨论的一般更新事务称作弱事务(Weak Transaction，简称WT)。为保持叙述的连贯性，在下面的讨论中，我们仍然沿用前面的提法，即未提交的弱事务称为暂时事务，而提交之后的弱事务称作已提交事务。
　　我们规定强事务的读/写操作只能对整个复制系统中最新的数据库提交版本进行，而暂时事务只能读/写本地数据库最新的暂时版本，因此强事务的执行不会与本地服务器现有的暂时事务发生冲突。为了便于支持强事务与弱事务的共存，也就是支持应用的可变一致性，WCSR系统采用主服务器暂时事务提交算法。这时，主服务器的数据库提交版本就是整个复制系统中数据库的最新提交版本。
　　服务器S接到用户的一个强事务请求st后，为st分配一个本地唯一的强事务序号，记作sno，并将st的时间戳设为0。然后，S立即将st发送给主服务器PS，如果PS没有响应或返回事务失败信息，则S向用户返回一个失败信息，强事务st夭折；否则，主服务器PS接到st后，执行st并提交，并分配给已提交的st一个提交序列号csn，将st以<csn,0,S>的次序插入到PS的事务日志中(已提交事务日志部分)，最后将事务执行结果以及st.csn返回给服务器S。接到主服务器的返回信息后，S向用户报告成功信息以及该事务的执行结果。至此，强事务st已经顺利地在主服务器上提交，并将在随后的成对同步过程中传播到其它的服务器上。
　　可以证明，强事务的引入并不会影响原来WCSR系统的正确性，即：在支持强事务的可变一致性WCSR系统中，各个复制服务器上的事务提交次序仍是一致的，其并发事务(包括查询事务与更新事务)的执行仍然是Epsilon-可串的。
5　WCSR系统评价
　　为了验证WCSR复制数据库系统的正确性，我们在局域网环境中实现了一个原型验证系统WCSR-SP，并对复制结点数较多的WCSR系统进行了模拟。
　　实验与模拟结果表明，WCSR系统的复制一致性可以得到保证，而且其复制维护开销是可以承受的，同步开销与复制结点数基本成线性关系；暂时事务的提交速度也比较快，一般在几个同步周期之内即可提交，因此系统的收敛性也比较好。
　　在用户的访问性能方面，由于WCSR系统采用Read-Any-Write-Any的复制机制，因此用户可以立即从本地服务器得到事务执行的结果，即具有较快的访问性能。
　　由于WCSR采用的弱一致性复制协议以及周期性地成对同步收敛方法，在复制集合中部分结点的故障不会影响整个系统的正确收敛，因此WCSR系统具有很高的可靠性；而且，只要用户能够访问到任意一个WCSR复制服务器，即使该服务器与其它服务器都失去联系(网络连接中断)，用户仍然能够访问复制数据库，在网络故障恢复之后该服务器将继续保持与其它服务器的同步，并将用户的事务传播给其它服务器，因此，WCSR系统具有非常好的可用性，特别适合于移动计算环境。
6　小结
　　WCSR弱一致性复制数据库系统能实现所有复制服务器的同步，支持事务处理的Epsilon-可串性(一致性)，并在适当的时候将事务的结果永久化，支持应用的可变一致性，提高服务器同步时暂时事务的成功率，因而能很好地支持移动计算环境。
作者简介：李霖　男，27岁，博士生，主研移动计算机与移动数据库系统
作者单位:国防科技大学计算机学院长沙　410073
参考文献
　1　Imielinski T，Badrinath B R.Mobile Wireless Computing：Challenges in Data Management.Communications of the ACM，1994，37(10)：18-28
　2　李霖，周兴铭.移动数据库技术:机遇和挑战.计算机科学，1997，24(3)
　3　Lamport L.Times，Clocks，and the Ordering of Events in a Distributed System. Communications of the ACM，1978，21(7)：558-565
　4　Demers A.The Bayou Architecture:Support for Data Sharing Among Mobile Users.In：Proc IEEE Workshop on Mobile Computing Systems and Applications，Santa Cruz，California,1994：2-7
　5　Bernstein P A.Concurrency Control and Recovery in Database Systems.Addison Wesley Publishing company，1987
　6　Ramamrithan K，Pu C.A Formal Characterization of Epsilon Serializability.IEEE Transactions on Knowledge and Data Engineering，1995(7)
收稿日期:1998-06-15
