事务和并发控制

本篇文章重写了之前的一篇：

事务：

事务定义了一个服务器操作序列，由服务器保证这些操作序列在多个客户端并发访问和服务器出现故障情况下的原子性。

本篇文章描述了三种并发控制的方法：

• 锁用于在多个事务访问同一对象时，根据这些操作访问同一对象的先后次序给事务排序。
• 乐观并发控制允许事务一直执行，直到它们准备提交为止，只是在提交时通过检查来确定已执行的操作是否存在冲突。
• 时间戳排序利用时间戳将访问同一对象的事务根据它们的起始时间进行排序。

0. 并发事务中的著名问题

我们以银行的例子说明并发事务中的两个著名问题 —— “更新丢失”问题和“不一致检索”问题。

0.1 更新丢失问题

假设有三个银行账户：A、B和C，初始余额分别为$100, $200, $300。

事务T将资金从账户A赚到账户B，事务U将资金从账户C转到账户B，两次转账的金额都是当前B账户余额的10%。（B的最终值应该为$242）

0.2 不一致检索

下面是另一个与银行账户有关的例子：事务V将资金由账户A转到账户B，事务W调用branchTotal方法获取银行所有账户的总余额。

账户A，B的初始余额都为$200，但是branchTotal计算A和B的总和，却是$300。

0.3 串行等价性

如果每个事务知道它单独执行的正确结果，那么我们可以推断出这些事务按照某种次序依次执行一个事务的结果也是正确的。如果并发事务交错执行操作的效果等同于按照某种次序一次执行一个事务的效果，那么这种交错执行是一种串行等价的交错执行。我们说两个事务具有相同效果。(是指读操作返回相同的值，并且事务结束时，所有对象的实例变量也具有相同的值。)

1. 锁

一个简单的串行化机制是使用互斥锁。在这种锁机制下，服务器试图给客户事务操作所访问的对象加锁。如果客户端请求访问的一个对象已被其他客户的事务锁住，那么服务器将暂时挂起这个请求，直到对象被解锁。

下图说明了互斥锁的使用：

1.1 两阶段加锁

串行等价性要求一个事务对某个对象的所有访问相对于其他事务进行的访问而言是串行化的。两个事务的所有冲突操作必须以相同的次序执行。为了保证这一点，事务在释放任何一个锁后，都不会允许再申请新的锁。

每个事务的第一个阶段是“增长阶段”，在这个阶段中，事务不断地获取新的锁；

在第二个阶段中，事务释放它的锁（一个“收缩阶段”），这称为两阶段加锁。

1.2 锁的实现

锁的授予通常由服务器上一个对象实现，我们称该对象为锁管理器（lock manager）。锁管理器把所拥有的锁放在诸如散列表之类的数据结构中。每个锁都是Lock类的一个实例，并与某个对象相关联。

Lock类的每个实例在它的实例变量中维护一下信息：

• 被锁住的对象的标识符
• 当前拥有该锁的事务的标识符（共享锁可以有若干拥有者）

类Lock的方法都是同步方法，这样试图获得或者释放锁的线程将不会相互干扰。
另外，当试图获取正在使用的锁时，线程将调用wait方法等待该锁释放。

1.3 死锁

死锁是一种状态，在该状态下一组事务中的每一个事务都在等待其他事务释放某个锁。

等待图（wait-for graph）可用来表示当前事务之间的等待关系。

2 乐观并发控制

2.1 锁机制的固有不足

• 锁的维护带来了新的开销，这些开销在不支持对共享数据并发访问的系统(例如：redis)中是没有的。即使是只读事务，它不可能改变数据的完整性，通常仍然需要利用锁来保证数据在读取时不会被其他事务修改，但锁只在最坏的情况下起作用。
• 使用锁需要预防死锁。预防死锁会严重降低并发度，因此必须利用超时或者死锁检测来解除死锁。
• 为了避免连锁放弃，锁必须保留到事务结束时才释放，这会显著降低潜在的并发度。

2.2 乐观并发控制

Kung和Robinson提出了一种“乐观策略”，基于它们发现的一种现象：

在大多数的应用中，两个客户事务访问同一个对象的可能性是很低的。事务总是能够执行，就好像事务之间不存在冲突一样。

当客户完成其任务并发出closeTransaction请求时，再检测是否有冲突。如果确实存在冲突，那么一些事务将会被放弃，并需要客户端重启该事务。

每个事务氛围下面几个阶段：

• 工作阶段：在事务的工作阶段，每个事务拥有所有他修改的对象的临时版本。这个临时版本是对象最新提交版本的拷贝。使用临时版本，事务便可以在工作阶段放弃或者在其他事务发生冲突不通过验证时放弃（而不产生副作用）。读操作总是可以立即执行 —— 如果事务的临时版本已存在，那么读操作访问这个临时版本；否则，访问对象最新提交的值。写操作将对象的新值记录成临时值（这个临时值对其他事务是不可见的）。当系统中存在多个并发事务时，一个对象可能维护多个临时版本。
• 验证阶段：在接收到closeTransaction请求时验证事务，判断它在对象上的操作是否与其他事务对同一对象的操作冲突。如果验证成功，那么该事务就允许提交。否则，必须使用某种冲突解决机制，或者放弃当前的事务，或者放弃其他与当前事务冲突的事务。
• 更新阶段：当事务通过验证后，记录在所有临时版本中的更新将持久化。只读事务在通过验证后立即提交。写事务在对象的临时版本记录到持久存储后即可提交。

3. 时间戳排序

在基于时间戳的并发排序中，事务中的每一个操作在执行之前要先进行验证。如果该操作不能通过验证，那么事务将立即被放弃，然后由客户端重启该事务。

每个事务在启动时被赋予了唯一的时间戳，这个时间戳定义了该事务在事务时间序列中的位置，来自不同事务的操作请求可以根据它们的时间进行全排序。

基本的时间戳排序规则：

• 只有在对象最后一次读访问或者写访问是由一个较早的事务执行的情况下，事务对该对象的写请求是有效的。只有在对象的最后一次写请求是由一个较早的事务执行的情况下，事务的对该对象的读请求是有效的。

<待续>

部分示例

• Dropbox：采用乐观的并发控制形式，更新是以文件为颗粒度的。如果两个用户同时对一个文件做了并发更新，那么第一个更新将被接受，而第二个更新将被拒绝。
• Wikipedia：它在编辑的时候采用的乐观并发控制。并允许编辑人员并发的访问那些第一次写入已经被提交的页面，或者在某个用户提交之后显示“编辑冲突”并要求该用户解决冲突的页面。
• Mysql：悲观并发控制
• Postgresql：乐观并发控制
• Git：乐观并发控制的思想

参考链接：