CMU 15445 13.并发控制理论

2019-06-26 本文已影响0人西部小笼包

ACID

image.png

子性：一个事务的所有的操作要么全发生，要么全不发生
一致性：如果在事务的开始，数据库的状态是一致的，那么可以确保在事务结束的时候也是一致的。
隔离性：一个事务的操作对其他事务是隔离的。
持久性：如果事务提交，那么对db的改动是持久的。

原子性有2种实现方式。

image.png

数据库准确地模拟现实世界并遵循完整性约束。

将来的事务会看到过去在数据库中提交的事务的影响。

如果数据库在事务开始之前是一致的（单独运行），那么它之后也将是一致的。

事务一致性是应用程序的责任。

DBMS为事务提供了它们在系统中单独运行的错觉。他们没有看到并发事务的影响。这相当于以串行顺序（即，一次一个）执行事务的系统。但是为了获得更好的性能，DBMS必须交错并发事务的操作。
这就需要并行协议来保证。

有2类并行协议，一类是悲观的，一类是乐观的。
1.悲观：DBMS认为事务会发生冲突，因此在一开始就做预防措施。
2.乐观：DBMS假设交易之间的冲突很少，因此它选择在冲突发生时再补救。

当dbms交替的执行操作，就会出现一些问题。有如下三类。

读 - 写冲突（“不可重复读取”）：事务处理时多次读取同一个对象，无法获得相同的值。

写 - 读冲突（“脏读”）：事务看到另一个事务的写入的值在那个事务提交前。

写 - 写冲突（“丢失的更新”）：一个事务覆盖另一个并发事务的未提交数据。

Conflict Serializability就是移动了指令的先后顺序对整体不会有影响。
第一张图是Conflict Serializability，第二张不是。

image.png

验证算法

image.png

View Serializability比较抽象，他可以允许有环。如下图其实是等价的，但是我们画依赖图也是有环的。

image.png

View Serializability允许所有Conflict Serializability和“盲写”的计划。因此，允许比Conflict Serializability稍微更多的计划，但难以有效地执行。这是因为DBMS现在不知道应用程序将如何“解释”值。

同样也是用log 和 shadow paging来实现。