数据库复习">数据库复习

CH15 并发

15.1 并发的问题

由事务ACID性质的I（Isolation，独立性），并发的事务间是透明的，穿插执行的事务会产生多种数据不一致问题（区别于数据库不一致状态）：

Lost Update problem：事务TA更新一个数据X后，事务TB又更新数据X，导致TA对X的更新被冲掉，即TA中“看见”的X和数据库中的X不一致 Uncommitted Dependency problem：TB更新了数据X后TA读取X/更新X，但TB由于某种失败rollback，导致TA中“看见”的X和数据库中的X不一致 Inconsistent Analysis problem：TA是一个先于TB开始的事务（业务逻辑上的先于），但由于并发，先执行的TA中读取了X后，后执行的TB修改X或修改了TA开始执行时刻对于TA本来一致的但TA还未读取并即将读取的数据Y，导致TA“看见”的数据X、Y和其执行时的X、Y不一致

注：事务并发带来的问题还有很多，上面只是原书作者的一种归类方法

15.2 并发调度和串行化

（1）定义

并发调度就是安排并发的事务的所有指令执行先后顺序，并保持事务内部指令顺序的操作；最常见的调度是串行调度，即多个事务仍然按照串行的顺序一个接一个的执行全部指令，但显然串行调度并发度极差

不是所有调度都能保证数据库的一致性，但是我们总期待找到一个等价于串行调度的并行调度方案（即不破坏数据库一致性的并行调度）；一般称这样的调度是可串行化（Serializable）的

在考虑事务的串行化时作以下几点假设：

每个事务是保持数据库一致性的，即没有逻辑错误串行地执行一系列事务也是保持数据库一致性的为了简化，只考虑读写操作，读写之间可能会包含各种各样的计算

定义事务间的两条指令oi、oj存在冲突（Conflict）当且仅当oi、oj访问同一数据项X并至少有一条指令试图write(X)；定义两调度S1、S2是冲突等价的，当且仅当S1可以通过交换一系列非冲突指令得到S2；显然一个可串行化冲突等价于串行调度

（2）可串行性检测

一般通过构造事务先序图（事务间的有向图）来检测调度的可串行性；考虑并发事务集合T1,…,Tn，若Ti到Tj有弧，则Ti和Tj之间存在冲突指令Oi和Oj，并且在调度方案中Ti的冲突指令Oi靠前

构造好先序图后根据如下定理判断调度的可串行性：

一个调度是可串行的当且仅当它构造的先序图无环，若先序图无环可以通过拓扑排序构造无冲突的调度

（3）评价

可串行性检测是事后发生的，并不适用于实时的并发控制！学习可串行性是为了更好地理解下面的并发协议

15.3 基于锁的并发协议

锁机制我们并不陌生，操作系统中处理进程、线程同步时很详细地讨论过
Lock(X)

并发中最简单的锁是二值锁（也叫互斥锁），一个事务Lock(X)只有等其Unlock(X)其他事务才能访问；由于互斥锁中只允许一个事务对同一数据访问，因此不允许并发的读操作，较为低效

更常用的高效的锁是共享/排他锁（Shared/Exclusive Lock、S-X Lock）

（1）共享/排他锁

S-X锁有共享和排他两种状态：

通过Lock-S指令获取共享锁，只能对获取了共享锁的数据读取操作通过Lock-X指令获取排他锁，可以对获取了排他锁的数据读写操作

对S-X锁的申请由并发控制管理器管理，一个事务必须获取了某种锁才能继续对某数据操作

S-X锁协议如下：

事务在retrieve元组t之前必须获得t上的S锁事务在upate元组t之前必须获得t上的X锁，若已有S锁则需升级到X锁如果事务A在元组t上有X锁，则某其他事务B对t的任何一种锁的申请都将被拒绝如果事务A在元组t上有S锁，则某其他事务B对t的X锁的申请将被拒绝，而对t的S锁的申请将被允许如果对某个锁的申请一直没有被允许，事务将一直等待，直到其他事务释放它申请的锁通常commit和rollback时默认为释放该事务申请的所有锁

仔细思考上述对S-X锁的描述，很容易发现会出现饥饿甚至是死锁（死锁的事务将强行释放掉它们拥有的锁并回滚）

（2）两阶段锁协议

两阶段锁（Two Phase Lock）协议是一个能够保证冲突可串行化调度方案的协议，两阶段锁协议中事务划分成两个阶段（两阶段之间的时间点称作Lock Point）：

扩张阶段：事务只能获取锁，但不能释放锁收缩阶段：事务只能释放锁，但不能获取锁

两阶段锁不能避免死锁，除非加上限制条件［事务获取的所有X锁必须在事务结束时才被释放］，此时称为严格的两阶段锁协议

（3）自动获取锁

一般的数据库语言中并不直接提供显式锁语句，而是将锁协议嵌入到**原子的**read和write中，如下是一种实现方式：

READ(Ti, D) {
    if Ti has no lock on D {
        wait until no other T has a X-lock on D;
        grant Ti a S-lock on D;
    }
    read(D);
}

WRITE(Ti, D) {
    if Ti has no X-lock on D {
        wait until no other T has any lock on D;
        if Ti has a S-lock on D {
            upgrade S-lock to X-lock;
        } else {
            grant Ti a X-lock on D;
        }
    }
    write(D);
}

`（4）锁机制的实现`

一般锁的实现由DBMS的lock manager完成，事务向lock manager发送上锁和释放锁的请求，lock manager向事务发送批准（grant）申请、拒绝申请以及强制会滚的消息（防止死锁）

lock manager在名为lock table的哈希表记录锁管理相关的信息，以元组做索引，其中记录批准锁的事务列表（包括批准了什么类型锁）以及等待

`15.5 锁粒度`

`（1）锁的粒度`

数据库中数据的粒度从高层到底层分别是：数据库、区域（不知道这是什么）、文件以及元组纪录，可以针对不同粒度的数据上锁

粒度较细是指对粒度层级较低的数据上锁，这样可以获取更高并发度，但锁管理开销负载较大；粒度较粗是指对粒度层级较高的数据上锁，这样可以获取低开销的锁管理，但并发度较低

`（2）S-X锁的粒度扩展——意向锁`

意向锁（Intention Lock）的提出是基于一个运用粒度适中的锁机制的数据库系统，假设事务T申请某个关系变量R（即某表）上的X锁，若全局扫描R中所有元组是否被其他事务锁住，这样开销很大

因此为了检测这样粒度划分后的锁的冲突，必须完善X-S锁协议，下列意向锁协议应运而生：

IS意向共享锁：T对某个粒度的数据对象加IS锁，表明T意欲对该对象的后继节点（粒度层级更低的数据对象）设置S锁，如T想要对R的元组t设置S锁，则先要对关系变量R加IS锁（或对R所在的数据库加IS锁） IX意向排他锁：T对某个粒度的数据对象加IX锁，表明T意欲对该对象的后继节点（粒度层级更低的数据对象）设置X锁 SIX共享意向排他锁：T对某个粒度的数据对象加SIX锁，相当于先加S锁再加IX锁，例如需要读关系变量R的所有元组并修改某些元组，则申请SIX锁

基于意向锁的多粒度扩展协议的基本原则就是：T要对某个数据对象上锁，则需要对它上层节点上锁，并且申请锁时自上而下、释放锁时自下而上

数据库复习8――并发(一)