数据库复习8——并发，数据库复习8

数据库复习

---

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要对某个数据对象上锁，则需要对它上层节点上锁，并且申请锁时自上而下、释放锁时自下而上

15.5 死锁处理

DBMS的事务并发管理器处理死锁有两种机制：死锁预防和死锁检测

（1）死锁预防

死锁预防顾名思义就是保证数据库绝对不会进入死锁状态，一些策略如下：

• 要求所有事务在开始执行操作前获取所有需要的锁，叫做预先申请
• 事务对数据的上锁顺序取决于［偏序］，类似于死锁检测中的等待图
• 设置事务等待锁的时间上限，超时则会滚事务，称之为超时策略

（2）死锁检测

死锁检测是去检测等待图（Wait-For Graph，一种描述事务锁依赖的有向图）是否成环的机制，当检测到死锁时选取部分锁会滚或者直接所有事务会滚

等待图中有：

• 顶点V代表所有活跃的事务
• 有向边E=Ti->Tj表示Ti正在等待Tj释放某个元组t上的锁，并有Tj释放锁后Ti申请到时，删除边E

可以用有向图成环检测的算法来检测是否存在死锁

版权声明：本文为博主原创文章，未经博主允许不得转载。