并发控制-两阶段锁定协议

缘起
今天，发生了一些事情，事情是这样的：

• 早上9点钟，乔布斯找我借了100块钱，他说下午或明天还
• 到了10点钟，库克找我还他的100块钱，我正忙，很烦库克（100块钱都好意思找我还），就让他找乔布斯要去。
• 到了下午2点，乔布斯很守信用，跑过来找我还钱。
• 到了下午3点，库克跑来对我一阵骂，说我忽悠他。

于是，很郁闷，随手找了本数据库原理看看，看了后，我觉得我明白些道理，想把这些道理记录下来。
数据库的故事

• 数据库需要同时处理多个事务：发现跟我一样，需要同时对付借钱、讨债的
• 数据库需要保证一致性：这个不错，我要学习一下

怎样保证一致性呢，书上说“一件事处理完再处理完一件事”，觉得很有道理，而且还进行深刻反思，比如今天的那件事，不让库克去找乔布斯，而是让库克后天再来找我，就不会有后面的烦恼了。
并发控制的故事
但是，计算机科学毕竟就是计算机科学，它不满足于这个结论，它希望干得更高效些，它说：“寻找一个让事务的执行等价于'一件事处理完再处理下一件事'的方法”。我深以为然，果然是聪明人想出来的，再次激发起我的好奇心。
聪明人说：只有读，没问题，因状态改变，才导致不一致性问题。如果将多个事务对多个数据的读写操作序列看成一张图，那么当图不存在环时，即事务的执行等价于一个一个来。而他们研究的则是产生这种图的事务并发控制方法。
并发控制方法-两阶段锁定
锁可分为读锁、写锁。读锁相容，读写锁、写写锁互斥。锁这件事上，可以想象一下每个数据都是一个带着锁的房间，所谓写锁，就是拿着钥匙，把门锁死了，锁死前，里面不能有人；所谓读锁，就是让人进房间，随意观看，进去前，登记一下。

• 锁增长阶段：在事务提交前，只允许获得锁。
• 锁缩减阶段：在事务提交后，释放所有持有的锁。

变种：在事务开始提交时，先释放所有读锁。那么当一个事务所申请的锁不存在时，处理的方式包括：

• 直接拒绝申请者
• 让申请者一直等待，直到系统通知结果
• 让申请者等待一段时间
• 申请者自己不耐烦，跑掉了

回到讨债这件事来，对于乔布斯的借钱，事情已经发生了，那就没办法了，但对于库克，我想处理方式跟上面同样的：

• 直接拒绝库克，说哥没钱
• 让库克等待，我有钱了再通知他
• 让库克等到今晚再回去
• 库克等的不耐烦，自己回跑掉的

其实，由于可能两个事务互相拥有对方的锁，导致这两个事务都申请不到需要的锁，从而导致死锁，死锁的解决办法如下几种：

• 赋予每个事务一个唯一序号，让低序号申请者申请高序号事务所拥有锁时，立即拒绝申请
• 让申请者等待一段时间，超时，则拒绝申请
• 建立全局的等待图，识别出死锁，当死锁将发生时，拒绝申请

有人提出，这种办法解决不了幻影读问题，所谓幻影读，即是

• 事务A读到当前数据库有两条记录
• 事务B插入一条记录
• 事务A读到当前数据库有三条记录

聪明人说，不是这种方法解决不了，而是，需要一个额外的对表的锁。两阶段锁方法由于要求申请者等待或拒绝，因此聪明人又想了一些其它方法来提高并发性。
多版本时间戳方法

• 读总是被允许，读到最近历史的一个版本
• 写写依然互斥
• 写总是产生新的版本

由于这篇文章长度原因，写不下来详细的证明，我简单的讲下背后的思想：将数据库当前状态看作在时间线上发生的事件的结果，时间线上的每个时间点都是数据库的一个状态。因此，在实现上，赋予每次提交一个唯一序号、每次读一个唯一序号，那么读操作可看成获取当前世界的一个历史状态。那么写写冲突怎么办呢，采用两阶段锁定方法呗。

真实世界的数据处理方法
讲了一堆废话，讲下真实世界的情况吧。真的需要完全的一致性吗？单靠数据库就能保证吗？在现实世界中：

• 并不是所有逻辑都在一个数据库事务中执行：比如，从其它地方获取到一个数据记录，然后修改起值后，提交到数据库中。显然并不是根据数据库中的数据状态进行修改后提交。这种情况被命名为长事务，通常采用乐观锁的方法，以求在数据库的当前状态上进行数据变更。
• 锁表有需要吗：通常没有这个必要，有就锁呗，应用负责申请该锁
• Oracle数据库采用多版本时间戳、两阶段写锁协议

综合以上，个人认为多版本时间戳、两阶段写锁、乐观锁的组合是一个保证并发性与一致性的最佳选择

其它

• 两阶段锁定，其实并不是数据库特有，比如java并发教程里的打电话例子
• 借钱、还债的例子是杜撰出来的，乔布斯、库克跟我有毛关系

掩卷叹息，没文化不知道害怕，债务这么简单的事情背后居然有这样的大道理。数据库的事情深不见底，也都是几十年前的技术，但是背后的思想，却让人深深着迷，我只是初学者，不正确的地方，还请大家不吝指出，以免误人
资料
http://research.microsoft.com/en-us/people/philbe/ccontrol.aspx
http://docs.oracle.com/cd/B10500_01/server.920/a96524/c21cnsis.htm#2611
Concurrency Control in Distributed Database Systems(by PHILIP A. BERNSTEIN AND NATHAN GOODMAN)

评论

1 楼 krystal_0424 2014-04-29