时标并发控制算法-分布式数据库技术

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

【摘要】：不像基于封锁的算法，基于时标的并发控制算法不通过互相排斥来维持可串行化。这里，唯一性是时标的第一个性质。协调事务管理器为每个事务指定时标，确定每个数据项存放的节点，并向这些节点发送执行相关操作的命令。下面的算法称为基本时标序事务管理算法，记作BTO-TM。严格2PL算法要求封锁必须推迟到事务的提交或夭折才释放，同样也可以给出一个严格的TO算法。

不像基于封锁的算法，基于时标（TO）的并发控制算法不通过互相排斥来维持可串行化。取代它们的是选择一种优先串行化序，让事务按照这个序来执行。为了建立这个序，启动每个事务Ti时就定义了唯一的时标（timestamp），记作ts（Ti）。

时标是一个简单的标识，标示每个事务都是唯一的，是有序的。这里，唯一性是时标的第一个性质。第二个性质是其单调性。同一个事务管理器生成的时标是单调递增的。这样，时标是一个全序域生成的值。时标很像邮局给客户寄信时盖的邮戳，每个邮戳定义了邮寄邮件的序。

生成时标的方法有多种：一种方法是使用一个全局的单调递增计数器。该方法存在的问题是，要维持一个全局计数器对分布式系统来说比较难。因此，更好的方法是每个节点自主地在本地计数器基础上赋予时标。为了维持唯一性，每一个节点在计数器值上附加一个自己的标识。这样，时标是一个二元组〈本地计数器值，节点标识〉。如果每个系统使用自己的系统时钟，那么可以用这个时钟代替计数器。当两个不同的节点给出相同的计数器值时，需要给它们设置一个序，以保证时标的唯一性。

我们可以简单地让事务按照它们的时标序来执行。我们将这样一个时标（TO）序规则简述如下。

TO规则：给定两个冲突操作aij和akl，它们分别属于事务Ti和Tk，aij在akl前执行，当且仅当ts（Ti）＜ts（Tk）。此时，Ti称为是较老的（older）事务，Tk称为是较年轻的（younger）事务。

一个强加TO规则的调度会检查与找出每个与已调度执行相冲突的操作。如果一个事务的新操作比所有已调度的冲突对象新，则接受该操作。否则，就拒绝它，让整个事务带着新时标重新启动。

这样运作的一个时标序调度能保证生成一个可串行化调度。然而，能做这样的事务时标比较，只有在调度器接收到所有要调度的操作时才可能。然而，操作是一次采用一种方式抵达调度器的（理想情况），必须能够在操作出队列时就能发现。为了能够检查出结果，科学家建议，给每个数据项授予两个时标：一个是最大读时标（rts（x）），这是读过这个数据项x的事务的最大时标；一个是最大写时标［wts（x）］，这是写（更新）过这个数据项x的事务的最大时标。这样就有充分条件来将一个操作和对应的数据项读/写时标进行比较，以确定是否有比自己时标更大的事务存取过该数据项。

换言之，除事务被赋予时标外，还需要为数据项赋予时标。

为每个数据项x指定如下两个时标。

●最大读时标（read timestamp），记作rts（x），记录最后读该数据项（x）的那个事务的时标。

●最大写时标（write timestamp），记作wts（x），记录最后写该数据项（x）的那个事务的时标。

基本算法为：每个事务在其发起节点获得一个时标ts；该事务请求的每个读/写操作继承该事务的时标ts；每个数据项x拥有一个最大读时标rts（x）和最大写时标wts（x）。

若该事务有一个对x的读操作，则If ts＜wts（x），拒绝该读操作，该事务带新时标重启动；否则，执行该读操作，为x设置新的最大读时标：rts（x）=max（rts（x），ts）。若该事务有一个对x的写操作，则If ts＜rts（x）or ts＜wts（x），拒绝该读操作，该事务带新时标重启动；否则，执行该读操作，为x设置新的最大写时标：wts（x）=max（wts（x），ts）。

1.基本TO算法

基本TO算法是直接实现TO规则的方法。协调事务管理器为每个事务指定时标，确定每个数据项存放的节点，并向这些节点发送执行相关操作的命令。

下面的算法称为基本时标序事务管理算法，记作BTO-TM。

算法9.6 BTO-TM。(www.chuimin.cn)

调度算法如下。

算法9.7 BTO-SC。

【例9.6】假设TO调度器首先接收Wi（x），然后接收Wj（x），其中ts（Ti）＜ts（Tj）。调度器会接收这两个操作并传递给数据处理器。这两个操作的结果是wts（x）=ts（Tj），然后希望Wj（x）的结果真实地表示在数据库中。如果数据处理器不按序执行，那么数据库中的结果就会出错。

当一个事务可能被拒绝时，它会重新启动，并获得一个新时标。这样就能保证事务下次还有机会来尝试能否被执行。因为事务不会占着数据的访问权限等待，所以TO算法不会发生死锁。但是，会有付出代价的事，无死锁的报复是可能产生的事务多次重启动，以让未成功事务获得新时标，试图获得执行机会。有些文献也把它称为“活锁”。

2.保守TO算法

为了解决“活锁”，产生了多种变异TO算法，如下面所说的保守TO算法。这里要对调度器和数据处理器间的通信进行进一步讨论。

调度器可以为每个数据项维持一个排队队列并施加强加序，让其能按序执行。

这种复杂问题在基本2PL的算法中不会出现，因为封锁管理器只在操作执行以后才释放封锁，以保证必要的序。从某种意义上讲，TO调度器所维持的也可以看成是一个封锁。但不能说两者的结果始终是等价的，所以会产生有时TO调度器允许的序在2PL中是不允许的。

严格2PL算法要求封锁必须推迟到事务的提交或夭折才释放，同样也可以给出一个严格的TO算法。例如，如果Wi（x）被数据处理器接受和释放，则调度器会推迟所有的Rj（x）和Wj（x）操作（Tj代表所有其他并发事务），直到Ti终结（提交或夭折）。

如前所述，基本TO算法不会让操作等待，但会造成事务的重启动。我们也曾指出这个算法没有死锁问题，但是其缺陷也是明显的，就是事务的不断重启动就像“活锁”。

如果一个遇到冲突的年轻事务A先启动，同时，与其冲突的另一个事务B由于“年迈”被拒绝，则会被一个TO调度器重启动。不幸的是，在其重启动后，又遇上了冲突，自己又晚了一步，结果又被拒绝和重启动。最不堪的情况是，B始终晚一拍，不停重启动，始终未获得机会。B就像被锁住了一样，这就是“活锁”。保守的TO算法就是设法通过减少重启动来降低系统开销。

保守TD算法的“保守”性质与它执行每个事务的方式有关。一方面，基本TO算法始终力图做到，一旦它接收到操作就执行一个操作，因此这是一种“积极”的方法。另一方面，保守算法先把操作延迟一下，观察是否带着比这个操作更小的时标操作在调度中出现，如果没有，就执行这个操作。如果保证这个条件，这个调度就不会拒绝一个操作。问题是会带来死锁的可能。

假设系统里每个调度器为每个事务维护一个队列。在节点i的队列Qij中存放它从节点j的事务管理器收到的所有操作。当从一个事务管理器收到一个操作，这个操作就按递增的时标序放入适当的队列。每个节点的调度器按递增的时标序执行来自队列的操作。

这种方法虽然会减少重启动的次数，但不能保证完全消除重启动。我们来看下面一种情况。

假设节点i关于节点j的队列（Qij）是空的。节点i的调度器选择一个具有最小时标的操作［R（x）］，并将其传递给数据处理器。然而，节点j有可能已经将一个带有最小时标的操作［W（x）］发送给了i，且它还在网络传输中。当这个操作抵达节点i时，由于该操作破坏了TO规则，因此被拒绝，即它试图存取一个数据项，该数据项正在为另一个有更高时标的操作所存取（而该操作是与之不兼容的）。

可以设计一种绝对保守的TO算法，只有当每个队列里至少有一个操作时，调度器才可以选择一个操作发送给数据处理器。这保证了未来这个调度器接收的每个操作拥有的时标大于或等于目前队列中操作的时标。当然，如果事务管理器没有处理的事务，则需要周期性地向系统中的每个调度器发送虚消息（dummy message），并告诉它们发送操作的时标将大于虚消息的时标。

时标并发控制算法-分布式数据库技术

相关推荐