Post

并发控制

Posted
By lreverse
10 min read
并发控制

事务(Transaction)

  • 事务在数据库上执行的一个或多个操作构成的序列，用来完成数据库系统的高级功能
  • SQL事务语句
    • 事务启动：BEGIN
    • 事务提交：COMMIT
      • 将事务对数据库的修改持久地写入数据库中
    • 事务中止：ROLLBACK
      • 将事务对数据库的修改全部撤销(undo)
      • 事务既可以被自己中止，也可以被DBMS中止
  • 事务的ACID性质
    • 原子性(Atomicity)
      • “All or Nothing”
      • 事务的操作要么全部执行，要么一个也不执行
      • DBMS保证：已中止事务必须undo
    • 一致性(Consistency)
      • “It looks correct to me”
      • 如果事务的程序正确，并且事务启动时数据库处于一致状态，则事务结束时数据库一定处于一致状态
    • 隔离性(Isolation)
      • “As if alone”
      • 一个事务的执行不受其他事务的干扰
      • DBMS保证：并发控制
    • 持久性(Durability)
      • “Survive failures”
      • 事务一旦提交，则它对数据库的修改一定全部持久地写到数据库中
      • DBMS保证：redo、undo

并发控制

  • 调度：一个或多个事务的重要操作的序列
    • 串行调度(Serial Schedule)：如果一个调度中不同事务的操作没有交叉
      • 能保证数据库的一致性
    • 非串行调度(Nonserial Schedule)：不是串行调度的调度
      • 可能会破坏数据库的一致性
  • 异常：非串行调度会导致事务的异常行为，从而破坏数据库的一致性
    • 脏写
    • 脏读
    • 不可重复读
    • 幻读
  • 等价调度：如果两个调度在任意数据库实例上的效果都相同
  • 可串行化调度：如果一个调度等价于一个串行调度（一般是非串行调度）
    • 满足调度的正确性
    • 不存在异常

隔离级别

在不同隔离级别下，一个事物修改过的对象的值对其他并发事务的可见程度不同

a. 读未提交(Read Uncommitted)

  • 未提交事务所做的修改对其他事务可见

b. 读提交(Read Committed)

  • 只有已提交的事务所做的修改才对其他事务可见

c. 可重复读(Repeatable Read)

  • 如果一个事务不修改对象X的值，则该事务在任何时候读到的X值都等于事务启动时读到的X值

d. 可串行化(Serializable)

  • 不存在异常

冲突可串行化

  • 冲突
    • 两个操作属于不同的事务
    • 两个操作涉及相同的对象
    • 两个操作中至少有一个操作是写
  • 冲突等价
    • 这两个调度涉及相同事务的相同操作
    • 每一对冲突的操作在两个调度中的顺序都相同
  • 冲突可串行化调度
    • 如果一个调度冲突等价于一个串行调度，则该调度是冲突可串行化调度
    • 冲突可串行化调度
  • 冲突可串行化测试
    1. 将调度S表示为优先图
      • 每个顶点代表S中的一个事务
      • 从事务$T_i$到事务$T_j$有一条有向边：如果$T_i$的某个操作$o_i$和$T_j$的某个操作$o_j$冲突，并且$o_i$在$S$中先于i$o_j$
    2. S是冲突可串行化调度，当且仅当其优先图没有环

并发控制协议

1. 基于锁的并发控制

lock-based concurrency control

  • 锁
    • 事务T只有获得了对象A的锁，才能读或写A
    • 如果事务T请求了对象A的锁，但并未获得，则T开始等待，直至获得A的锁为止
    • 如果事务T获得了对象A的锁，则在T完成对A的操作后，T必须释放A的锁
  • 锁的类型
    • 共享锁（S锁）
      • 事务T只有获得了对象A的共享锁，才能读A
    • 互斥锁（X锁）
      • 事务T只有获得了对象A的互斥锁，才能写A
      • T获得了A的互斥锁后，亦可读A
  • 锁的相容性
    • 若A加上了S锁，则其他事务还可以对A加S锁，不能加X锁
    • 若A加上了X锁，则其他事务不能加S锁，也不能加X锁

两阶段锁协议（2PL）

  • 每个事务的执行分为两个阶段
    • 增长阶段
      • 事务向锁管理器请求需要的锁
    • 萎缩阶段
      • 事务释放它获得的锁，但不能再请求加锁
  • 特点
    • 优点
      • 2PL能够保证冲突可串行化
    • 缺点
      • 2PL面临着级联中止的问题
        • 级联中止
      • 2PL可能导致死锁
  • 严格调度
    • 如果一个调度中任意事务在结束前由它写入的数据库对象的值没有被其他事务读过或修改过，则该调度被称为严格调度
    • 严格调度不会引发级联中止

强两阶段锁协议（SS2PL）

  • 增长阶段
    • 与2PL的增长阶段一致
  • 萎缩阶段
    • 当事务结束时，释放它获得的全部的锁（同时）
  • 保证生成严格的冲突可串行化调度，因而不会产生级联中止

死锁（Deadlock）

参考os的死锁

  • 如果一组事务中每个事务都在等待其他事务释放锁，则这组事务形成死锁
    • 死锁
  • 死锁的处理
    • 死锁检测
    • 死锁预防
死锁检测
  • 超时检测
    • 如果在给定的时间内没有任何事务执行，则认为死锁发生
  • 等待图检测
    • 事务产生锁当且仅当等待图中有环
    • 等待图
死锁解除
  • 从等待图的环中选择一个事务作为“牺牲品”，中止该事务
  • 选择“牺牲品”时需要考虑多种因素
死锁预防
  • 当事务启动时，DBMS为事务分配一个唯一且固定的优先级
    • 开始得越早，优先级越高
  • 当事务$T_i$请求事务$T_j$拥有的锁而无法获得时，DBMS根据以下两条规则之一来预防
    • Wait-Die规则
      • $T_i$比$T_j$的优先级高，则$T_i$等待；
      • 否则，中止（$T_i$重启后，优先级保持不变）
      • Wait-Die
    • Wound-Wait规则
      • $T_i$比$T_j$的优先级高，则$T_j$中止（$T_j$重启后，优先级保持不变）
      • 否则，$T_i$等待
      • Wound-Wait

2. 时间戳定序的并发控制

timestamp ordering concurrency control

  • $TS(T_i)$：DBMS为每个事务$T_i$分配一个唯一且固定的数，作为其时间戳
    • 时间戳单调递增：分配得越晚，时间戳越大

Basic T/O

  • 每个对象$X$关联着2个时间戳
    • $RTS(X)$：成功读X的最晚的事务的时间戳
    • $WTS(X)$：成功写X的最晚的事务的时间戳
  • 事务$T_i$准备读对象X
    • 如果$TS(T_i)<WTS(X)$，则中止并重启$T_i$（分配新的时间戳）
    • 否则，允许$T_i$读$X$，并将$RTS(X)$更新为$max(RTS(X), TS(T_i))$，并创建$X$的局部副本
  • 事务$T_i$准备写对象X
    • 如果$TS(T_i)<RTS(X)$或$TS(T_i)<WTS(X)$，中止并重启$T_i$
    • 否则，允许$T_i$写$X$，并将$WTS(X)$更新为$max(WTS(X), TS(T_i))$，并创建$X$的局部副本

3. 多版本并发控制

multi-version concurrency control（MVCC）

Course, 数据库系统
deadlock
This post is licensed under CC BY 4.0 by the author.