CMU 15445 15. TO + OCC + MVCC
image.png
时间戳排序（T / O）是一种乐观的并发控制协议类，其中DBMS假定事务冲突很少。 DBMS不是要求事务在允许读取/写入数据库对象之前获取锁，而是使用时间戳来确定事务的可序列化顺序。
大致思路是给每个事务一个时间戳
image.png
当事务要拿一个未来时间的object，它会abort或者重启。
我们看下读的规则。
image.png
写的规则
image.png
2个example
成功的例子
image.png
image.png
回滚的例子
image.png
thomas-write 规则
image.png
image.png
如果您不使用托马斯写入规则，则基本T / O协议会生成conflict serializable 的计划。 因为没有事务等待它不会有死锁。 但如果短事务不断引发冲突，那么长期事务就有可能出现饥饿。
它还是不可恢复的计划。 如果事务仅在所有读取或提交更改的事务之后提交，则可以恢复调度。 否则，DBMS无法保证事务读取将在从崩溃中恢复后将恢复的数据。
image.png
OCC
对于假设事务不会发生冲突的常见情况，OCC可能是更好的方法。
当冲突数量很少时，OCC运作良好。 这是当所有事务都是只读或当事务访问不相交的数据子集时。 如果数据库很大并且工作负载没有偏差，那么冲突的可能性很小，因此加锁是浪费的。
DBMS为每个事务创建一个私有工作区：
- 所有修改都应用于私有工作区。
- 将读取的任何对象复制到工作空间中。
- 没有其他事务可以读取其私有工作空间中另一个事务所做的更改。
当事务提交时，DBMS会比较事务的工作空间写入集，以查看它是否与其他事务冲突。 如果没有冲突，则将写入集覆盖到“全局”数据库中
image.png
image.png
验证阶段
这是DBMS检查事务是否与其他事务冲突的地方。 DBMS需要保证只允许可序列化的计划。 DBMS在进入验证阶段时分配事务时间戳。
Ti检查RW和WW冲突的其他事务，并确保所有冲突都是单向的（从旧事务到年轻事务）。 DBMS使用所有其他正在运行的事务检查提交事务的时间戳顺序
MVCC
核心特性是
Writers don’t block the readers. Readers don’t block the writers.
只读事务可以在不获取锁的情况下读取一致的快照。 时间戳用于确定可见性。
轻松支持DBMS可以在时间点快照上执行的时间旅行查询。
有四个重要的MVCC设计决策：
1.并发控制协议（T / O，OCC，2PL等）。
2.版本存储
3.垃圾收集
4.索引管理
版本存储
就是关于DBMS如何存储逻辑对象的不同物理版本。
DBMS使用元组的指针字段为每个逻辑元组创建一个版本链。 这允许DBMS在运行时查找特定事务可见的版本。 索引总是指向链的头部。 线程遍历链，直到找到可见的版本。 不同的存储方案确定每个版本的存储位置/内容。
image.png
APPEND ONLY
image.png
TIME TRAVEL
image.png
image.png
image.png
image.png
DELTA STORAGE
image.png
image.png
image.png
image.png
垃圾回收
DBMS需要随着时间的推移从数据库中删除可回收的物理版本。
→DBMS中没有活动的txn可以“看到”该版本（SI）。
→版本是由中止的txn创建的。
image.png
方法＃1：元组级垃圾收集 - 通过直接检查元组查找旧版本
•Background Vacuuming：单独的线程定期扫描表并查找可回收的版本，适用于任何版本的存储方案。
image.png
image.png
•协作清理：工作线程在遍历版本链时识别可回收的版本。 仅适用于OLD2NEW。
image.png
方法＃2：事务级别 - 每个事务都跟踪自己的读/写集。 当事务完成时，垃圾收集器可以使用它来识别要回收的元组。 DBMS确定完成的事务创建的所有版本何时不再可见。
image.png
