（未完待续）

事务

1. DB中执行的最小单元
2. 具有ACID特性
   1. A——原子性
   2. C——一致性
   3. I——隔离性
   4. D——持久性
3. 控制命令
   1. BEGIN
   2. COMMIT
   3. ABORT
4. 影子分页（属于No-Steal + Force）
   1. 数据库维护两个独立的数据版本（有点类似于主从复制模型）
      1. master——负责其他事务的读取
      2. shadow——负责写事务的修改操作
   2. 提交完成后，将shadow版本切换至master版本
   3. 用例——LMDB
   4. 日志
      1. Redo日志（仅记录修改后的新值，所以只能重做，不能回滚）（属于No-Steal + Force）
         1. 每次修改，产生redo日志
         2. 事务commit前，事务所有修改不能落盘
         3. 事务commit成功前，事务的所有log必须先落盘
      2. Undo/Redo日志（同时记录旧值和新值，所以既可以实现回滚，又可以实现重做）（属于Steal + No-Force，对大事务友好，也减轻了写盘压力）
   5. 日志回收

隔离性

如何保证隔离性的同时实现并行？

想像A、B余额都为1000，事务T1:A转账100给B，事务T2：支付A、B 6%的利息

T1： T2:

BEGIN BEGIN

A -= 100 A *= 1.06

B += 100 B *= 1.06

COMMIT COMMIT

2. 矛盾

   1. 两个事务，在同一块数据上，而且至少有一个涉及写操作

3. 隔离级别（从低到高）

   1. Read Uncommited（导致脏读）

      

   2. Read Committed（可能会导致不可重复读）

      MVCC可以解决（MVCC中，T1第二个R(A)仍然读为$10)

   3. Repeatable Read（可能会导致幻读）（MySQL默认级别，InnoDB通过MVCC解决幻读问题）

   4. Serializable

4. 问题

   1. 不可重复读
   2. 脏读
   3. 写写冲突

5. 可串行化

   1. 矛盾可串行化
   2. 视图可串行化

6. 如何可串行化

   1. 交换
   2. 依赖图

悲观

让问题第一时间不发生（严格）

1. 2PL
   1. 锁种类
      1. Lock
         1. 隔离事务
         2. 保护数据库的内容
         3. 处于事务内
         4. 有共享锁、排他锁、更新锁
      2. Latch
         1. 隔离线程
         2. 保护内存中的数据结构
         3. 位于临界区
   2. 2PL
      1. 共享锁和排他锁
      2. 不需要提前知道事务中的内容
      3. 分为两阶段
         1. growing——可以通过管理器获取锁
         2. shrinking——只能释放，不能获取
      4. 缺陷
         1. 可能引起级联中止
         2. 死锁
         3. 仍然会脏读——需要严格2PL
            1. 
            2. 事务提交前不解锁
            3. No-steal，不会引发级联中止
   3. 死锁检测和预防
      1. 选择受害人

乐观

2PL假设事务内部很多冲突

但是如果问题很少发生，可以当其发生时才解决

1. 时间戳排序

   1. Basic T/O
      1. Ts(Ti) ——每个事物开始执行的时标
         1. 系统时钟作为时间戳
         2. 逻辑计数器
      2. 写时间戳W-Ts(X)——成功实行W(X)的所有事物的最大时间戳
      3. 读时间戳R-Ts(X)——成功实行R(X)的所有事物的最大时间戳
      4. 例子
         1. Ti需要R(X)
            1. if Ts(Ti) < W-Ts(X)， 证明此时读到的值已被覆盖；反之则可以读，R-Ts(X)设为max(R-Ts(X), Ts(Ti))
         2. Ti需要W(X)
            1. if Ts(Ti) < R-Ts(X)， 证明此时读到的值是先前需要的值；反之则可以写，W-Ts(X)设为max(W-Ts(X), Ts(Ti))
            2. if Ts(Ti) < W-Ts(X)， 证明此时读到的值已过时；反之则可以写，W-Ts(X)设为max(W-Ts(X), Ts(Ti))
         3. 此时T1的W(A)执行是满足2PL的，但不满足时间戳排序（Ts(T1) = 1 < W-Ts(A) = 2)，故引出托马斯写规则
      5. Thomas写规则
         1. if Ts(Ti) < R-Ts(X)，中止事物并重启Ti
         2. if Ts(Ti) < W-Ts(X)，托马斯规则认为：忽略写，允许事物执行
         3. 其他情况，允许Ti写，并更新W—Ts(X)
      6. 缺陷
         1. 违反了可恢复？
         2. 开销大，需要复制到本地工作区
         3. 长事物中途可能需要暂停
   2. Optimistic
      1. 创建一个private workspace for each tx
      2. 当tx提交，DBMS检查是否有冲突，如果没有就写到全局区域内
      3. 步骤
         1. 读阶段——读入到局部变量中
         2. 验证阶段——判断是否可以写且不违反可串行性
            1. Start(Ti)/Validation(Ti)/Finish(Ti)，将validation(Ti)作为事务Ti的时间戳
            2. 有效性检测的原则（Ts(Tk) < Ts(Ti))，需满足两者之一
               1. Finish(Tk) < Start(Ti)——这保证了可串行性（较强）
               2. Tk所写的数据项和Ti所读不相交，且Tk写完成的时间在Ti验证之前(Start(Ti) < Finish(Tk) < Validation(Ti))。这个保证可串行性
                  1. 因为前提Tk的写不影响Ti的读，所有两个阶段可以重叠
                  2. Tk写完，Ti还没写，没有重叠
         3. 写阶段——将临时变量写入数据库中
         4. 特点
            1. 不会发生级联中止
            2. 长事务会饿死
   3. Partition-based Timestamp

2. MVCC

   1. 以上的机制都相对悲观

   2. 具体设计

      1. 并发控制

         1. 写不阻塞读，读不阻塞写
         2. MVCC为每个W(X)创建一个新版本（类似于影子页），只写事务可以在不需要锁的前提下读数据库一致的快照（虚拟），很好的支持time-travel查询？
         3. 例子
            1. 

      2. 数据存储

         1. 怎么快速找到这个版本？构造一个链表
            1. append-only
               1. 每次都在表后增加一个版本，同一个数据项的新老版本连接起来（用单链表）
               2. 表中存放整个数据行
               3. 连接顺序
                  1. O2N从老到新，这样获取最新版本需要从头到尾遍历
                  2. N2O从新到老，这样每次遍历的头结点都是变化的
                     1. 优化——构造一个索引，指向各个数据项的最新版本
            2. time-travel
               1. 跟N2O的优化类似，分成master版本和time travel版本，master版本储存最新的数据
               2. 表中存放整个数据行
            3. delta storage
               1. 存放的不是整个数据行
               2. 存放的是增量值（类似于用于回滚的undo日志）

      3. 垃圾清理

         1. 元组水平
         2. 事务水平

      4. 索引管理