CMU-cs445:并发控制

ACID

A:原子性
C:如果事务是一致的，数据库是一致的，那么结束时也必须是一致的
I:隔离性
D:事务提交之后会持久化

原子性

Logging
记录所有动作到undo log
Shadow Paging
事务运行的时候，拷贝那些用到的page，然后在上面执行事务，当事务提交后，用这些page替换原来的page

一致性

数据库一致性
事务一致性
https://www.zhihu.com/question/31346392

隔离性

多个事务同时执行时，每个事务无法读到别的事务的中间结果。

不可重复读
脏读
Overwriting Uncommited Data

如何判断两个事务存在冲突？

依赖图

锁

锁的类型
- 共享锁
- 排他锁
锁控制协议：两阶段锁
- Growing（增长阶段）
  每个事务被允许从锁管理器中获得锁。
- Shrinking（收缩阶段）
  事务只被允许释放前面获得的锁，不能申请新的锁。
  两阶段锁可以消除序列化矛盾，但是会存在级联终止问题。如下图
  
  要解决上面这个问题，需要使用强严格两阶段锁，也就是说我们必须在事务提交的时候才能释放之前获得的锁，这样就能避main脏读和级联终止。
  两阶段锁也会导致死锁，如下图：
  
  有两种方法解决死锁问题
检测
锁管理器维护一个waits-for图，用来追踪每个事务等待要获取的锁，每个节点是一个事务，如果事务A正在等待事务B的锁，他们之间就有一个箭头，当存在环形结构就说明存在死锁。

检测周期可以设置一个可容忍的系统值。
处理
选择一个事务，回滚，选择的标准可以是：
- 时间戳
- 查询数
- 被锁住的item数量
- 需要回滚的事务数量
预防
根据时间来确定优先级
- Wait-Die
  如果请求锁的事务优先级高于持有锁的事务，那么等待持有锁的事务，否则终止。
- Wound-Wait
  如果请求锁的事务优先级高于持有锁的事务，那么持有锁的事务终止并且释放锁，否则请求锁的事务等待。
  
  当事务重启之后，其优先级（也就是时间戳）是它原本的时间戳，这有助于避免此事务饥饿。
锁的层次

数据库中有成千上万个tuple，我们不能直接管理这些，因此我们需要一些更高层次的抽象锁，让我们同一时间管理更少的锁。
- 意向锁
  - 意向共享锁（IS）
  - 意向排他锁（IX）
  - 共享锁（S）
  - 排他锁（X）
  - 共享意向排他锁（SIX）

基于时间戳顺序的控制

基于两阶段锁是一种悲观锁，基于时间戳顺序是一种乐观锁。
我们需要向每个tuple添加两个时间戳：

写时间戳：最近对tuple写的事务的时间戳
读时间戳：最近对tuple读的事务的时间戳
在读阶段，确保自己的时间戳不小于tuple的写时间戳，在写阶段，要确保事务的时间戳小于tuple的写时间戳和读时间戳。有一种优化叫做托马斯写入规则：

基于时间戳的并发控制是不可恢复的。如果事务大多时间很短并且不会发生冲突，那么可以考虑这种病发控制协议。

乐观并发控制协议
偷懒，看下别人的总结

MVCC

并发控制协议
- 基于时间戳的控制
- 乐观并发控制
- 两阶段锁
版本存储
通过版本链（version chain）存储，索引指向链表头，有三种方法：
- Append-Only
  
  每更新一次，作为一个新的tuple插入到表中，并更新链表指针。
- Time-Traval
  
  每次更新将旧数据拷贝到time-travel表中，并更新指针。
- Delta Storage
  
  每次更新不用将整个tuple拷贝，只需要拷贝delta值即可
垃圾回收
- tuple级别的回收
  - 后台处理：后台线程对表进行定期扫描，查看开始时间戳和结束时间戳，不在活跃线程范围内就可以清除,一个优化是设置脏页面bitmap
  - 合作清理：当执行事务的线程在扫表的时候判断历史数据，只适用于从旧到新的版本数据存储方式
- 事务级别的回收
索引管理
- 辅助索引的更新
  - 逻辑指针：每个tuple对应一个固定的id，这个id不变，我们去改变中间层，也就是将逻辑指针映射到物理指针的这一层，辅助索引保存的是主键索引的副本，每次去查找的时候实际上做两次操作，一次去查找主键，一次根据主键去查找这是的物理数据。
  - 物理指针：直接修改物理指针去更新链表头