基于时间戳的并发控制(数据库)

时间：2022-12-27 08:30:01 | 来源：信息时代

时间：2022-12-27 08:30:01 来源：信息时代

    基于时间戳的并发控制 : 利用时间戳机制来控制多个事务的并发执行,以保证该多个事务并发执行的正确性。
时间戳(timestamp)是记录计算机系统时间的一种方法,在计算机的操作系统、分布式系统、数据库等多个领域中都有应用。在数据库管理系统中时间戳是系统赋予事务的唯一的时间,以标记该事务开始执行。时间戳可以是系统时钟值,也可以是逻辑计数器的值。采用系统时钟值时,要确保在一个时钟周期内不会产生两个相同的时间戳的值。采用计数器时,要设计好一种机制确保计数器能够安全地重置。在集中式系统中,时间戳的设置比较简单。但在分布式系统中,要维护一个全局一致的时间戳要复杂得多。
基于时间戳的并发控制方法的基本原理是: 系统以事先选定的事务次序(即按照事务时间戳的升序顺序)作为串性化的判定标准,然后判定事务调度是否和这个串行执行结果一致。如果某个事务的操作会违反这个次序,就迫使该事务“回滚”而不是等待。因此,也称该方法为时间戳排序协议。
所谓“事务回滚”,就是终止事务,并采用一系列措施,消除该事务已经执行的操作对数据库造成的影响。直观上看,采用回滚的办法来进行事务调度的代价挺大,并发度不会高。但是,实际应用中真正产生冲突的还是少数情况,回滚现象并不多。
基于时间戳的协议,相关的记号如下:
TS(T): 表示事务T的时间戳。
TS(T_i)<TS(T_j):表示事务T_i在事务T_j之前开始执行。
W-timestamp(Q):表示在数据项Q上成功执行write(Q)操作的所有事务中的最大时间戳。
R-timestamp(Q):表示在数据项Q上成功执行read(Q)操作的所有事务中的最大时间戳。
这是两个系统全局变量,当系统成功执行新的write(Q)或者read(Q)操作时,这些变量的值会被更新。
时间戳排序协议如下:
(1)假定事务T执行操作read(Q),若TS(T)<W-timestamp(Q),表示事务T要读入的数据项Q的值已经被执行序列中更后面的事务写过了,这时,应强迫T回滚; 若TS(T)≥W-timestamp(Q),这表明事务T可以读这个Q的值,因此,执行read(Q)操作,R-timestamp(Q)=max{R-timestamp(Q),TS(T)}。
(2)假定事务T执行操作write(Q),若TS(T)<Rtimestamp(Q),表明数据项Q已经被执行序列中更后面的事务读过了,不能再执行write(Q)操作了,因此,强迫T回滚; 若TS(T)<W-timestamp(Q),表明数据项Q已经被执行序列中更后面的更新事务写过了,不能再写write(Q)了,因此,也要强迫T回滚。否则,执行write(Q)操作,并令W-timestamp(Q)=TS(T)。
(3)被回滚的事务,系统重新赋予它新的时间戳,并重新启动。
按照这个协议进行调度,结果一定和事务的时间戳顺序一致,因为所有可能产生不一致的事务都被强制回滚了。在上述时间戳协议中,当TS(T)<Wtimestamp(Q)时,事务T的读操作read(Q)因为它要读取的值已被覆盖而被拒绝执行,系统强迫T回滚。如果每一个数据项的旧值副本被保存在系统中,这个问题就可以解决了。这个方案被称为多版本并发控制(multiversion concurrency control)。