Concurrency Control

并发操作带来的数据不一致性

• 丢失修改（Lost Update）
• 不可重复读（Non-repeatable Read）
• 读“脏”数据（Dirty Read）

记号

• R(x):读数据x
• W(x):写数据x

不可重复读包括三种情况， 后两种不可重复读有时也称为幻影 现象（Phantom Row）： ◼ 事务T1读取某一数据后，事务T2对其做了修改，当事务T1再次读 该数据时，得到与前一次不同的值 ◼ 事务T1按一定条件从数据库中读取了某些数据记录后，事务T2删 除了其中部分记录，当T1再次按相同条件读取数据时，发现某些 记录神秘地消失了。 ◼ 事务T1按一定条件从数据库中读取某些数据记录后，事务T2插入 了一些记录，当T1再次按相同条件读取数据时，发现多了一些记 录。

数据不一致性及并发控制

数据不一致性：由于并发操作破坏了事务的隔离性

并发控制就是要用正确的方式调度并发操作，使一 个用户事务的执行不受其他事务的干扰，从而避免 造成数据的不一致性

对数据库的应用有时允许某些不一致性，例如有些 统计工作涉及数据量很大，读到一些“脏”数据对统 计精度没什么影响，可以降低对一致性的要求以减 少系统开销

并发控制的主要技术

• 封锁(Locking)
• 时间戳(Timestamp)
• 乐观控制法
• 多版本并发控制(MVCC)

封锁:

排它锁（Exclusive Locks，简记为X锁）

• 共享锁（Share Locks，简记为S锁

排它锁又称为写锁

• 若事务T对数据对象A加 上X锁，则只允许T读取 和修改A，其它任何事 务都不能再对A加任何 类型的锁，直到T释放A 上的锁
• 保证其他事务在T释放A 上的锁之前不能再读取 和修改A

共享锁又称为读锁

• 若事务T对数据对象A加 上S锁，则事务T可以读 A但不能修改A，其它事 务只能再对A加S锁，而 不能加X锁，直到T释放 A上的S锁
• 保证其他事务可以读A， 但在T释放A上的S锁之 前不能对A做任何修改

在运用X锁和S锁对数据对象加锁时，需要约定一些 规则，这些规则为封锁协议（Locking Protocol）。

• 何时申请X锁或S锁
• 持锁时间
• 何时释放

Starvation

避免活锁：采用先来先服务的策略 ◼ 当多个事务请求封锁同一数据对象时 ◼ 按请求封锁的先后次序对这些事务排队 ◼ 该数据对象上的锁一旦释放，首先批准申请队列中第一个事务获得锁

死锁

是两个或多个事务都已封锁了一些数据对象，然后又都请求 对已为其他事务封锁的数据对象加锁，从而出现死等待。

解除死锁 ◼ 选择一个处理死锁代价最小的事务，将其撤消 ◼ 释放此事务持有的所有的锁，使其它事务能继 续运行下去

Transaction Schedule

对于并发程序, 必须要考虑按照什么样的顺序进行调度.

可串行化(Serializable)调度

多个事务的并发执行是正确的，当且仅当其结 果与按某一次序串行地执行这些事务时的结果相同

冲突可串行化 (一个比可串行化更严格的条件)

冲突可串行化调度是可串行化调度的充分不必要条件

两段锁协议

指所有事务必须分两个阶段对数 据项加锁和解锁

遵守两段锁协议的调度一定是一个可串 行化调度。

数据库管理系统普遍采用两段锁协议的方法实 现并发调度的可串行性，从而保证调度的正确 性

两段锁协议，指所有事务必须分两个阶段对数据项加锁和解锁

• 在对任何数据进行读、写操作之前，事务首先要获 得对该数据的封锁
• 在释放一个封锁之后，事务不再申请和获得任何其 他封锁

遵守两段锁协议的事务可能发生死锁

Locking Granularity

多粒度封锁(Multiple Granularity Locking)

• 在一个系统中同时支持多种封锁粒度供不同的事务 选择

选择封锁粒度，同时考虑封锁开销和并发度两 个因素, 适当选择封锁粒度

• 需要处理多个关系的大量元组的用户事务：以数据 库为封锁单位
• 需要处理大量元组的用户事务：以关系为封锁单元
• 只处理少量元组的用户事务：以元组为封锁单位

非常自然的设计

表示上, 可以用树形结构里表示不同粒度的locking

多粒度树

• 以树形结构来表示多级封锁粒度
• 根结点是整个数据库，表示最大的数据粒度
• 叶结点表示最小的数据粒度

在多粒度封锁中一个数据对象可能以两种方式封锁：

• 显式封锁: 直接加到数据对象上的封锁
• 隐式封锁:是该数据对象没有独立加锁，是由于其上级 结点加锁而使该数据对象加上了锁

显式封锁和隐式封锁的效果是一样的

对某个数据对象加锁，系统要检查

• 该数据对象

  • 有无显式封锁与之冲突

• 所有上级结点

  • 检查本事务的显式封锁是否与该数据对象上的隐式封锁 冲突：(由上级结点已加的封锁造成的）

• 所有下级结点

  • 看上面的显式封锁是否与本事务的隐式封锁（将加到下 级结点的封锁）冲突

引入意向锁 (intention lock)

意向共享锁(Intent Share Lock，简称IS锁)

• 如果对一个数据对象加IS锁，表示它的后裔结 点拟（意向）加S锁。
• 例如：事务T1要对R1中某个元组加S锁，则要 首先对关系R1和数据库加IS锁

意向排它锁(Intent Exclusive Lock，简称IX 锁)

• 如果对一个数据对象加IX锁，表示它的后裔结 点拟（意向）加X锁。
• 例如：事务T1要对R1中某个元组加X锁，则要 首先对关系R1和数据库加IX锁