分布式系统一致性设计---乐观并发控制和悲观并发控制_架构

锁的缺点

传统的锁机制有许多固有的不足,加锁的缺点总结如下

（1）、锁的维护带来的开销,这些开销在不支持对共享数据并发访问的系统中是没有的。即使是只读事务(查询),它不可能改变数据的完整性,通常仍然需要利用锁来保证数据在读取时不会被其他事务修改。但是锁只在最坏的情况下才起作用。

例如,有两个并发执行的客户进程将n个对象的值增1。如果这两个客户程序同时开始执行并运行相同的时间,但它们访问对象的次序不相关,并使用独立的事务来访问并增加对象的值,那么这两个程序同时访问到同一个对象的概率只有1/n,因此每n个事务只有1个才真正需要加锁。

（2）、使用锁会引起死锁。预防死锁会严重降低并发度,因此必须利用超时或者死锁检测来解除死锁,但这两种死锁解除方法对交互程序来说都不理想为了避免连锁放弃,锁必须保留到事务结束才能释放。这会显著地降低并发度。

乐观并发控制

基于锁的缺点Kug和 Robinson提出的另一个方法是一种“乐观”策略,这是因为他们发现这样一个现象,即在大多数应用中,两个客户事务访问同一个对象的可能性是很低的。乐观锁内的事务总是能够执行,就好像事务之间不存在冲突一样。当客户完成其任务并发出提交请求时,再检测是否有冲突。如果确实存在冲突,那么一些事务将被放弃,并需要客户重新启动该事务。每个事务分成下面几个阶段

（1）、工作阶段:在事务的工作阶段,每个事务拥有所有它修改的对象的临时版本。这个临时版本是对象最新提交版本的拷贝。使用临时版本,事务便可以在工作阶段放弃或者在与其他事务发生冲突不能通过验证时放弃(而不产生副作用)。读操作总是可以立即执行，如果事务的临时版本已经存在,那么读操作访问这个临时版本;否则,访问对象最新提交的值。写操作将对象的新值记录成临时值(这个临时值对其他事务是不可见的)。当系统中存在多个并发事务时个对象有可能存在多个临时版本。另外,每个事务还维护被访问对象的两个集合:读集合

read set)包含事务读的所有对象;写集合( write set)包含事务写的对象。注意,所有的读操作都是在对象的提交版本(或它们的副本)上执行,因此不会出现脏数据读取。

（2）、验证阶段:在接收到提交请求时验证事务,判断它在对象上的操作是否与其他事务

对同一对象的操作相冲突。如果验证成功,那么该事务就允许提交,否则,必须使用某种冲突

解除机制,或者放弃当前事务,或者放弃其他与当前事务冲突的事务。

（3）、更新阶段:当事务通过验证以后,记录在所有临时版本中的更新将持久化。只读事务可在通过验证后立即提交。写事务在对象的临时版本记录到持久存储后即可提交。

事务的验证验证过程使用读-写冲突规则来确保某个事务的执行对其他重叠( overlapping)事

务而言是串行等价的,重叠事务是指在该事务启动时还没有提交的任何事务。为了帮助完成验证过程每个事务在进入验证阶段之前(即在客户发出提交时)被赋予一个事务号。如果事务通过验证并且成功完成,那么它保留这个事务号;如果事务未通过验证并被放弃,或者它是只读事务,那么这个事务号被释放以便重用。事务号是整数,并按照升序分配,因此事务号定义了该事务所处的时间位置，一个事务总是在序号比它小的事务之后完成它的工作阶段。也就是说,如果i<j,那么事务号为Ti的事务总是在事务号为Tj的事务之前。(如果在工作阶段的开始分配事务号,那么一个事务若在另一个具有更小事务号的事务之前到达工作阶段的结尾,就要在验证前一直等待前者完成。)

对事务Tv的验证测试是基于事务Tv和Ti之间的操作冲突完成的。事务Tv对重叠事务Ti而言是可串行化的,那么它们的操作必须符合下面的规则

与事务的工作阶段相比,验证过程和更新过程通常只需要很短的时间,因此可以采用一个简单

的方法:每次只允许一个事务处于验证和更新阶段。当任何两个事务都不会在更新阶段重叠时,规则3自动满足。注意,在写操作上的这个限制和不发生脏数据读取这个事实,将产生事务的严格执行。为了防止重叠,整个验证和更新阶段被实现成一个临界区,使得每次只能有一个客户执行。为了增加并发度,验证和更新的部分操作可以在临界区之外实现,但是必须串行地分配事务号。我们注意到,在任何时刻,当前的事务号就像一个伪时钟,每当事务成功结束,这个时钟就产生一次嘀嗒。

事务的验证必须保证事务Tv和Ti的对象之间的重叠遵守规则1和规则2。有两种形式的验证：向前验证和向后验证。向后验证检查当前事务和其他较早重叠事务之间的冲突,向前验

证检查当前事务和其他较晚的事务之间的冲突。

向后验证

由于较早的重叠事务的读操作在Tv验证之前进行,因此它们不会受当前事务写操作的影响(满足规则1)。Tv的验证过程将检查它的读集(受Tv的读操作影响的对象)是否和其他较早的重叠事务Ti的写集是否重叠(规则2)。如果存在重叠,验证失败。

设 startTn是事务Tv进入其工作阶段时系统已分配(给其他已提交事务)的最大事务号, finishTn是Tv进入验证阶段时系统已分配的最大事务号。下面的程序描述了Tv的验证算法:

boolean valid = true

for(int Ti =startTn+I; Ti <=finishTn；Ti ++){

    if (Tv的读集与Ti写集相交)  valid= false;

}

下图给出了Tv验证过程中需要考虑的重叠事务。时间从左至右增加。T1、T和T3是较早提交的事务。T1在Tv开始之前提交。T2和T3在Tv完成其工作阶段前提交,并且有 startTn+1=T2, finishTn=T3。向后验证过程必须比较Tv的读集和T2、T3的写集。

向后验证比较被验证事务的读集和已提交事务的写集。因此一旦验证失败,解决冲突的唯一方法就是放弃当前进行验证的事务。在向后验证中,没有读操作(只有写操作)的事务无需进行验证。

向后验证的乐观并发控制要求最近提交事务中对象的已提交版本的写集合必须保留,直到没有可能发生冲突的未验证重叠事务。每当一个事务成功通过验证,它的事务号、startTn和写集合被记录在前述的事务列表中,这个列表由事务服务维护。注意,这个列表按事务号排序。如果有长事务存在较早事务的写集合的保留将是一个问题。例如在图中,T1、T2、T3和Tv的写集合必须保留到活动事务 active1结束之后。值得注意的是,尽管这个活动事务有事务标识符,但它还没有事务号。

向前验证

在事务Tv的向前验证中,Tv的写集合要与所有重叠的活动事务的读集合进行比较----活动事务是那些处在工作阶段中的事务(规则1)。规则2自动满足,因为活动事务在Tv完成之前不会进行写操作。设活动事务具有(连续的)事务标识符(从 active1~ activeN),那么下面程序描述了Tv的向前验证算法:

boolean valid =true

for (int Ti=active1;Ti<=activex; Ti++){

    if (Tv的写集与Ti的读集相交)  valid = false

}

在图中,Tv的写集合必须和事务 active1和acie2的读集合进行比较。(向前验证应该允许活

动事务的读集合在验证过程和写入过程中改变。)由于被验证事务的读集合没有包括在验证过程中,因此只读事务总能通过验证。因为与被验证事务进行比较的事务仍是活动的,所以发生冲突时,可以选择或者放弃被验证事务或者用其他方法解决冲突。Harder提出了下面几个策略

1、推迟验证,直到冲突事务结束为止。但是这不能保证被验证的事务在将来一定能够通过验证，在验证完成前,还是有可能启动会产生冲突的活动事务。

2、放弃所有有冲突的活动事务,提交已验证的事务。

3、放弃被验证事务。这是最简单的策略,但是由于冲突的活动事务可能在将来被放弃,因此这种策略会造成被验证事务的不必要放弃。

向前验证和向后验证的比较

我们看到,向前验证在处理冲突时有较强的灵活性,而向后验证只有一种选择,即放弃被验证的事务。通常,事务的读集合比写集合大得多。因此,向后验证将较大的读集合和较早事务的写集合进行比较;而向前验证将较小的写集合和活动事务的读集合比较。我们注意到,向后验证涉及存储已提交事务写集合(直到不再需要它们为止)的开销。另一方面,向前验证不得不允许在验证过程中开始新事务。