一种改进的基于时间戳的分布式事务并发控制策略

李清霞

(东莞理工学院 城市学院，广东东莞 523419)

并发控制是事务处理的核心技术之一，是指数据库合理调度并发事务，避免并发事务之间的相互干扰造成数据的不一致性。分布式事务并发控制策略主要有封锁和时间戳这两种。时间戳策略是指每个事务在产生时，系统会赋予事务唯一的时间戳，越晚开始的事务将获得越大的时间戳，当某事务与比其时间戳更大(更晚)的事务发生冲突时，它会中止。而在同样的情况下，如果使用封锁策略的话，事务将等待或立即继续执行［1］。另一方面，基于时间戳的并发控制不会造成死锁，这对于分布式事务处理来说是一个很大的优点，因为如果分布式事务处理存在发生死锁的可能，那么系统一般只能采用死锁检测机制来处理死锁问题，而在分布式环境下实现死锁检测机制是较为复杂且资源开销比较大的，其复杂度和资源开销还会随着分布式规模的增大而增加。虽然基于时间戳的分布式事务并发控制能够避免死锁的发生，但是却容易造成事务的回滚［2］。

针对上述问题，本文在研究分析基于时间戳的分布式事务并发控制策略的基础上提出了一种改进策略，并通过实验证明了改进后的并发控制策略能够有效减少事务的回滚，降低资源的开销。

1 基于时间戳的并发控制

1.1 时间戳

对于每个事务T，系统需要为其指定时间戳TS(T)。常用来生成时间戳的两种方法是［2］:

1)使用系统时钟值作为时间戳，即事务的时间戳等于该事务进入系统时的时钟值。

2)使用逻辑计数器，即事务的时间戳等于该事务进入系统时的计数器值，每赋予一个时间戳，计数器增加一次。

事务的时间戳决定了事务的串行化顺序。即若TS(Ti)＜TS(Tj)，则系统必须保证所产生的调度等价于事务Ti出现在事务Tj之前的某个串行调度。

1.2 时间戳排序协议

利用时间戳可以将事务进行全局排序，使较早启动的事务(具有较小的时间戳)在冲突时拥有较高的优先权。如果一个事务试图去“读/写”一个数据项，只有当该数据项的最近一次更新是由比此事务更早的事务完成时，该“读/写”操作才允许进行，否则发出请求的事务将被重新启动，并给予一个新的时间戳。时间戳法产生的可串行化调度表的次序等价于成功提交事务的时间戳序列。

每个数据项Q 需要与两个时间戳相关联 :

●R－timestamp(Q):任何成功执行Read(Q)的事务的最大时间戳。

●W－timestamp(Q):任何成功执行Write(Q)的事务的最大时间戳。

1)假设事务Ti请求执行Read(Q)时。

a)如果TS(Ti)＜W－timestamp(Q)，则Ti需读入的Q 值已被覆盖。因此，Read 操作被拒绝，Ti回滚。

b)如果TS(Ti)＞ = W－timestamp(Q)，则执行Read 操作，R－timestamp(Q)被设为MAX(R－timestamp(Q)，TS(Ti))。

2)假设事务Ti请求执行Write(Q)时。

a)如果TS(Ti)＜R－timestamp(Q)，则Ti产生的Q 值是先前所需要的值，且系统已经假定该值不会发生。因此，Write 操作被拒绝，Ti回滚。

b)如果TS(Ti)＜W－timestamp(Q)，则Ti试图写入的Q 值已过时。因此，Write 操作被拒绝，Ti回滚。

c)否则，执行Write 操作，将w－timestamp(Q)设为TS(Ti)。

如果事务Ti由于请求Read 或Write 操作而被并发控制机制滚回，则系统赋予它新的时间戳并重新启动。

1.3 存在的不足

基于时间戳的并发控制虽然能保证冲突可串行化和无死锁性，但是当一系列冲突的短事务引起长事务反复重启时，可能会导致长事务饿死的现象［2］。另外，并发发事务频繁读写同一个数据项时，很容易会造成事务的频繁回滚，从而耗费大量的资源开销。在分布式环境中，要实现全局时间戳的一致性和唯一性也是一个难题［3］。此外数据项的时间戳信息需要额外的空间来存储，一旦遇到事务处理要涉及的数据项很多的情况，那么存储它们的时间戳信息需要不小的空间，这无疑增加了系统负担［4］。

2 改进并发控制策略

针对传统策略存在的不足，我们提出了一种改进的并发控制策略，在传统策略的基础上增加了对事务操作的延迟，Tomas 写规则，两版本时间戳以及放弃对数据项时间戳信息的持久性保存。

2.1 事务的延迟操作

考虑分布式事务Ti的一个子事务Ti1，它要执行Read(Q)的操作，Q 为一个数据项，然而在经过很短的时间间隔t 后马上又有分布式事务Tj的一个子事务Tjl要执行Write(Q)的操作，而且TS(Ti1)＞TS(Tj1)，这就说明Ti1比Tj1要先开始，根据时间戳排序协议，TS(Ti1)＜R－timestamp(Q)，所以Tj1的操作被拒绝，Tj1不得不通过回滚获得一个新的时间戳。但如果能延迟时间tdelay(tdelay＞t)再执行Ti1Read(Q)的操作，那么事务Tj1的Write(Q)操作就会因为其时间戳小而先被得到执行，从而避免了事务Tj1的回滚［5］。

改进的并发控制策略引入了事务操作延迟的概念，如图1 所示，各种事务请求执行的操作将会被先放入延迟队列中，操作按时间戳的大小进行排列，时间戳越小的操作越排在前面被先执行，每次有新的操作请求来到时，系统会根据其时间戳的大小将其插入到延迟队列中相应的位置。当经过延迟时间tdelay后或者延迟队列中的事务操作数目超过最大延迟操作数目时，延迟队列中的操作将会被放入执行队列中被执行。这里的延迟时间和最大延迟操作数目都需根据实际环境而设置，延迟时间不能太短，最大延迟操作数目也不能太小，不然达不到减少事务回滚的目的，而相反的话就会造成事务操作延迟很久才被执行，降低事务处理的效率。

图1 事务操作延迟过程

2.2 Tomas 写规则

考虑对图2 所示的调度应用时间戳并发控制。T11是分布式事务T1的子事务，T21是分布式事务T2的子事务。由于T11先于T21开始，所以TS(T11)＜TS(T21)。T11的Read(Q)操作成功，T21的Write(Q)操作也成功。当T11试图进行Write(Q)操作时，由于TS(T11)＜W－timestamp(Q)，因为Wtimestamp(Q)= TS(T21)，所以T11的W rite(Q)操作被拒绝且事务T11必须回滚。虽然事务T11回滚是时间戳并发控制所要求的，但这是不必要的。由于T21己经写入了Q，T11想要写入的值永远不会被读到。满足TS(Ti)＜TS(T21)的任何事务Ti试图进行Read(Q)操作时都会被回滚，因为TS(Ti)＜W－timestamp(Q)。满足TS(Ti)＞TS(T21)的任何事务Ti必须读由T21写入的Q 值，而不是T11写入的值。

图2 事务调度

根据以上所述，在改进的并发控制策略中引入了Tomas 写规则［2］:

假设事务Ti发出Write(Q)操作请求。

1)如果TS(Ti)＜R－timestamp(Q)，则Ti产生的Q 值是先前所需要的值，且系统己经假定该值不会发生。因此，Write 操作被拒绝，Ti回滚。

2)如果TS(Ti)＜W－timestamp(Q)，则Ti试图写入的Q 值己过时。因此，Write 操作可以被忽略。

3)否则，执行W rite 操作，将W－timestamp(Q)设为TS(Ti)隔离级。

Tomas 写规则实际上是通过删除事务发出的过时Write 操作来实现可串行化的，可以避免由于过时Write 操作被拒绝而导致的事务回滚。

2.3 两版本时间戳

在基于时间戳的并发控制策略中，每一个事务只对应唯一的时间戳，但是这样可能会出现Read 操作由于相应值还未写入而延迟，或者因为它要读取的值己经被覆盖而被拒绝执行，从而导致事务的回滚［2］。但是如果每一数据项的更新的副本都被保存在系统中，这些问题就可以避免了，但这样做系统需要大量的额外空间来保存这些副本，而这些副本可能大多数都极少能被使用到。

针对这一点，改进策略采用了两版本时间戳的方法，每一数据项只保存当前的版本值和最近一次更新的版本值，这样基本可以解决Read 操作延迟读的问题又节省了不少的副本存储空间。

在改进策略中，对于每个数据项Q 包含以下五个数据段:

●OldC0ntent:Q 的旧版本值。

●NewC0ntent:Q 的新版本值。

●W－OldTimestam:Q 的旧版本执行完Write(Q)的事务的最大时间戳。

●W－NewTimestamp:Q 的新版本执行完W rite(Q)的事务的最大时间戳。

●R－Timestamp:Q 执行完Read(Q)的最大时间戳。

图3 给出Write(Q)操作的执行流程，如果事务Ti请求Write(Q)操作合法，那么先将数据项Q的OldContent 设为NewContent，而Q 的NewContent 则设为最近写入的值，再将W－OldTimestaimp 设为W－NewTimestamp，W－NewTimestamp 设为TS(Ti)，最后把R－Timestamp 设为MAX(R－Timestamp，TS(Ti))。

假设事务Ti发出Read(Q)操作，如果TS(Ti)＞= W－NewTimestamp，就读取NewContent 的值，否则如果TS(Ti)＞= W－OldTimestamp，就读取OldContent 的值，如果TS(Ti)＜W－NewTimestamp 而且TS(Ti)＜W－OldTimestamp 的话，Read(Q)操作被拒绝，事务Ti回滚，Read(Q)操作基本流程如图4所示。

图3 Write(Q)流程图

图4 Read(Q)流程图

2.4 数据项时间戳的非持久保存

在基于时间戳的并发控制策略中，数据项的时间戳充当着一个相当重要的角色。传统的做法都是将数据项最近一次的时间戳信息放入数据库保存，可是一旦需要使用大量数据项的时候，则需要不小的数据库空间来存储这些信息［4］。

考虑到数据项的时间戳信息在并发控制策略中主要用来实现时间戳排序协议，更新的频率比较高，而且对时间戳信息的使用集中在事务对数据项的操过程，一旦所有操作都己经完成，时间戳信息也失去了其使用价值。在改进策略中，数据项Q 的时间戳信息并不需要存入数据库，只是每次在使用到Q 之前都要先在内存中对其时间戳信息进行初始化，将R－timestamp(Q)和W－timestamp(Q)都设置为0，因为任何需要对Q 进行事务操作的时间戳都不可能小于0，就意味对Q 进行操作的事务只需考虑初始化之后与其他事务操作发生的冲突。这样一方面可以免去从数据库获取数据项时间戳信息的系统资源开销和时间开销，另一方面也可以节省存储数据项时间戳信息的数据库空间。

3 实验模拟

实验模拟主要是为了将传统的基于时间戳的分布式事务并发控制策略同改进策略进行性能的比较。因为在分布式事务处理中，由于网络的延迟等因素可能会造成分布式事务的处理请求并不是按照其时间戳的先后顺序被送到相应的结点进行处理的，所以在实验模拟中，对事务操作的时间戳采用逻辑计数器随机分配和非完全随机分配两种方式，操作请求时间间隔则都是随机生成的。这里的非完全随机是指在随机变量的基础上再加上一个递增变量。实验模拟的部分参数设置如表1 所示。

表1 实验模拟的部分参数设置

图5 实验结果

图5 所示的是几次典型的实验结果，可以明显看出改进策略具有比传统策略更低的事务操作回滚率，特别是当参与操作的数据项数目较多并且操作的时间戳采用非完全随机分配时，改进策略能够更为有效地减少回滚。而且在实验模拟中，所有参与操作的数报项的时间戳信息都在内存中进行初始化和相关操作，并没有存放入数据库，这不仅节省了存储空间，也减少了资源开销和时间开销，提高了执行效率。

4 结语

本文首先介绍了基于时间戳的分布式事务并发控制策略，然后提出了一种改进策略，最后通过实验证明了改进策略能够有效弥补传统策略上的部分不足之处。不过改进后的策略延迟了事务的操作，可能会延长部分事务的处理时间，不太适合应用到那些对实时性要求很高的事务处理中，而且在改进策略中，像如何实现全局时间戳的一致性等问题还没有得到解决，这都是我们下一步工作需要研究改进的地方。

［1］Andrew S. Tanenbaum，Maarten van Steen. Distributed systems Principles and Paradigms［M］.杨剑峰，常晓波，李敏，译. 北京:清华大学出版社，2004:9.

［2］Abraham Silberschatz，Henry F Korth Sudarshan S. DataBase System Concepts［M］. 杨冬青，唐世渭，译. 北京:机械工业出版社，2003:3.

［3］李陶深，武燕华. 基于全局时标的网格事务并发机制研究［J］. 计算机工程与设计，2011，32(8):2729－2733.

［4］Hector Garcia－Molina，Jeffrey D. Ullman，Jennifer Widom. Database system Implementation［M］. 杨冬青，唐世渭，徐其钧，等，译. 北京:机械工业出版社，2001:3.

［5］Philip A. Bernstein，Vassos Hadzilacos，Nathan Goodman. Concurrency Control and Recovery in Database Systems［M］. Addison－Wesley Publishing Company，1987.