LiJT的灵质空间

高级数据库系统知识点总结（Part 4）

发表于 更新于 分类于 阅读次数：
本文字数： 3.4k 阅读时长 ≈ 3 分钟

事务处理：故障与恢复 & 并发控制

事务处理I: 故障与恢复

重点内容：

  1. 数据库的一致性概念
  2. 事务的基本概念、ACID和原子操作
  3. Undo日志、Redo日志、Undo/Redo日志的恢复过程
  4. Checkpoint

数据库一致性

  • 数据库一致性是指事务执行的结果必须是使得数据库从一个一致性状态转变到另一个一致性状态
  • 保证数据库一致性是指当事务完成时，必须使所有数据都具有一致的状态

事务的基本概念、ACID和原子操作

  1. 事务：一个不可分割的操作序列，其中的操作要么读做，要么都不做

事务的ACID性质

  1. 原子性 Atomicity
  2. 一致性 Consistency
  3. 隔离性 Isolation
  4. 持久性 Durability

事务的原子操作

  1. 磁盘 <-> 内存
    1. input(x): disk block with x -> memory
    2. output(x): buffer block with x -> disk
  2. 内存 <-> 内存 (必要时，磁盘 -> 内存 <-> 内存)
    1. read(x,t): do input(x) if necessary; t <- value of x in buffer
    2. write(x,t): do input(x) if necessary; value of x in buffer <- t

Undo、Redo、Undo/Redo日志

  1. 事务日志记录了所有更新操作的具体细节
  2. 日志文件的登记严格按事务执行的时间次序

Undo日志规则

  1. 事务的每一个修改操作都生成一个日志记录 < T, x, old-value >
  2. WAL：先写日志，在X被写到磁盘之前，对应该修改的日志记录必须已被写到磁盘上
  3. 事务的所有修改结果都已经写入磁盘之后，将 < commit, T >日志记录写到磁盘上
  4. 恢复时忽略已提交事务，只撤销未提交事务
  5. 从尾部开始扫描日志记录< T,x,v >，如果T没有commit过或者已经abort，则：
    1. write(x,v)
    2. output(x)
    3. 反向扫描结束后，对于所有未commit过的事务，写入< abort, T >

Redo日志规则

  1. 事务的每一个修改操作都生成一个日志记录 < T, x, new-value >
  2. WAL：先写日志，在X被写到磁盘之前，对应该修改的日志记录必须已被写到磁盘上
  3. 事务的修改结果写入磁盘之前，将 < commit, T >日志记录写到磁盘上
  4. 从首部开始扫描日志记录< T,x,v >，如果T已经commit过，则
    1. write(x,v)
    2. output(x)
    3. 正向扫描结束后，对于所有未commit过的事务，写入< abort, T >

Undo vs. Redo

项目 Undo Redo
更新时间 立即更新（乐观） 延迟更新（悲观）
内存代价 低 高
恢复代价 高 低

Undo/Redo日志规则

  1. 在x被写到磁盘之前，对应该修改的日志记录必须已被写到磁盘上（WAL）
  2. 日志中的数据修改记录：< T, x, v, w >
    1. v: old value; w: new value
  3. 基于Undo/Redo日志的恢复
    1. 正向扫描日志，将commit的事务放入Redo列表中，将没有结束的事务放入Undo列表
    2. 反向扫描日志，对于< T, x, v, w >，若T在Undo列表中，则
      1. write(x,v); output(x)
    3. 正向扫描日志，对于< T, x, v, w >，若T在Redo列表中，则
      1. write(x,w); output(x)
    4. 对于Undo列表中的T，写入< abort, T >

检查点(checkpoint)

  1. 提出背景：当系统故障发生时，必须扫描日志。需要搜索整个日志来确定undo列表和redo列表
    1. 搜索过程太耗时
    2. redo列表很大，使得恢复过程变得很长（所有成功commit的事务都要redo一遍；每个事务可能涉及大量值更新操作）
  2. 检查点技术保证检查点之前的所有commit操作的结果已经写回数据库，在恢复时不需要redo

事务处理II: 并发控制

重点内容：

  1. 可串性、冲突可串性的概念
  2. 冲突可串性的判定
  3. 锁
  4. 视图可串性
  5. 死锁
  6. 乐观并发控制技术

并发控制面临的问题

  1. 丢失更新
  2. 脏读
  3. 不一致分析
    1. 不可重复读
    2. 幻读

并发调度与可串性

  1. 调度的定义：多个事务的读写操作按时间排序的执行序列. 例如
    1
    2
    3
    T1: r1(A)w1(A)r1(B)w1(B)
    T2: r2(A)w2(A)r2(B)w2(B)
    Sc = r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)
    1. 调度中的每个事务的读写操作保持原来顺序
    2. 事务调度时不考虑数据库的初始状态和事务的语义
  2. 可串化调度：如果一个调度的结果与某一串行调度执行的结果等价，则称该调度是可串化调度，否则是不可串调度

冲突可串性

  1. 冲突操作：涉及同一个数据库元素，并且至少有一个是写操作
    1. r1(A)<->w2(A)
    2. w2(A)<->r1(A)
    3. w1(A)<->w2(A)
  2. 冲突操作不可交换；不冲突操作可交换
  3. 冲突等价：称调度S1和调度S2是冲突等价的，如果S1可以通过一系列非冲突交换转换到S2.
  4. 定理：如果一个调度满足冲突可串性，则该调度是可串化调度

优先图

  1. 优先图用于冲突可串性的判断
  2. 优先图的结构
    1. 节点：事务
    2. 有向边：Ti->Tj,满足TiTj
      1. 存在Ti中的操作A1和Tj中的操作A2，满足A1在A2前并且A1和A2是冲突操作
  3. 定理：给定一个调度S构造S的优先图P(S)，如果P(S)无环，则S满足冲突可串性

视图可串性

  1. 冲突可串性过于严格，原本可串的S不一定冲突可串。视图可串解决这一问题
  2. 调度S1和S2视图等价，如果：
    1. If in S1: wj(A)->ri(A)(中间无任何w(A)); then in S2: wj(A)->ri(A)
    2. If in S1: ri(A) reads initial DB value; then in S2: ri(A) also reads initial DB value
    3. IF in S1: Ti does last write on A; then in S2: Ti also does last write on A
  3. 视图可串是冲突可串的必要不充分条件

锁机制

  1. 用途：用于实现可串化调度

两阶段锁（2PL）

  1. 事务在对任何数据进行读写之前，首先要获得该数据上的锁
  2. 在释放一个锁之后，事务不再获得任何锁
  3. 定理：如果一个调度S中的所有事务都是两段式事务，则该调度是可串化调度
  4. 缺点：如果事务T只是读取X，也必须加锁，而且释放锁之前其他事务无法对X进行操作，影响数据库的并发性. 解决方法：引入不同的锁：S lock, X lock, Update lock, …

X Lock

  1. X lock: exclusive locks, 也称写锁
  2. 只有获得X锁的事务，才能对封锁的数据进行修改. 其他事务不能获取X锁，也不能获取S锁

S Lock

  1. S lock: share locks, 也称读锁
  2. 如果事务T对数据R加了S锁，则其他事务对R的X锁请求不能成功，但对R的S锁请求可以成功
  3. 当事务获得S锁后，如果要对数据R进行修改，则必须在修改前执行Upgrade(R)，将S锁升级为X锁（升变？！）

Update lock

  1. 如果事务取得了数据R上的更新锁，则可以读R，并且可以在以后升级为X锁（上一小节的S锁的可升变版本）
  2. 单纯的S锁不能升级为R锁
  3. 如果事务持有了R上的Update lock，则其他事务不能取到R上的S锁、X锁，以及Update锁
  4. 如果事务持有了R上的S锁，则其他事务可以获取R上的Update lock

S锁、X锁、Update锁的相容性

Y 表示相容；N表示不相容

T1 holds\T2 requrests S X U
S Y N Y
X N N N
U N N N