【CMU15-445 Part-16】Concurrency Control Theory

Part16-Concurrency Control Theory

架构概念

Transcations

txn就是通过在数据库系统中执行一系列操作（sql queries）来执行某种更高级的功能(应用程序所执行的功能)。

Transcations in SQL

一个新的事务开始 with BEGIN，txn结束with COMMIT / ABORT或者ROLLBACK

如果是COMMIT，要么保存事务的所有改变然后commit，或者数据库系统表示不能commit；commit并不意味着你就commit

如果是abort，自begin开始所做的修改都会被回滚。abort可能是自发的self-inflicted 或者DBMS告诉你这个事务需要中止

Correctness Criteria : ACID

• Atomicity：原子性，事务的所有做要么都发生，要么都不发生
• Consistency，一致性
• Isolation：隔离性，txn之间隔离执行
• Durability：持久性，事务提交，修改保存，不会丢失

Atomicity of TXN

• commit after completing all actions
• abort after excuting some actions

确保原子性的方法

1. Logging，预写日志Write Ahead Logging，DBMS log 所有的actions，在中止的时候来undo这些操作,维护undo records in mm and disk
2. Shadow Paging：对每个事务在磁盘上制作一份该数据库文件的副本，所有的修改都在副本上执行，事务提交的时候只需要更改指针指向该副本，表示现在这个副本是该数据的主版本。

logging in MM可以很快的恢复，on Disk 可以处理hard crash之后的recovery

Consistency

Database is logically correct → 查询的结果也是txn logically correct

Database Consistency

数据库要对现实世界准确建模通过integrity constraints （完整性约束）来保证一致性

Transaction Consistency

是application的责任，DBMS只能看到read 或者 write

Isolation of Transactions

隔离性为了更好的programming，实现隔离性一般通过并发控制协议

Mechanisms for Ensuring Isolation

pessimistic protocal 悲观协议

optimistic protocal 乐观协议

Correctness

如何确保一个schedule是正确的

也就是可串行化：某个schedule的执行结果等同于按顺序执行的结果，那么说这种执行顺序的schedule是正确的，也就是serializable schedule 可串行化的执行计划。

如果T1先执行，后面是T2，T1先被提交，是strict serializeability 严格可串行化。

Interleaved Execution Anomalies

R-W W-R W-W

Unrepeatable Reads

不可重复读：试着去读取同一个对象的时候得到的值并不相同，实际是read-write conflicts

Dirty Reads

脏读：read-write冲突，reading uncommitted Data，读未提交，读了脏数据。

W-W Conflicts

写写冲突，overwrting uncommitted data，覆写未提交的数据。

Conflict Serializability

如果两个schedule被认为是冲突等价conflict equivalent，如果这两个调度涉及相同事务的相同操作，每一对冲突的操作在两个调度中的顺序都相同。

冲突等价(ConflictEquivalence) 可串行化调度(Serializable Schedules)_软件工程小施同学的博客-CSDN博客

冲突可串行化调度

通过交换不冲突操作的顺序来弄清楚该schedule是否是冲突可串行化，最终得到一个可顺序执行的调度

Dependency Graph

依赖图或者叫precedence graph 优先图，如果一个事务中的某些操作和另外一个事务的操作有冲突，Oi早于Oj，则Ti→Tj是一条边，如果有环则是不可串行化。

并不是conflict serializable，但是仍然能够得到和按顺序执行事务的相同结果和相同的数据库状态，这就是ViewSerializability

View Serializability

屏幕打印看到的结果和实际最终的结果不一致，要追求看到的和实际的一致。

从视觉角度上来看 这两种执行顺序所达到的效果是等同的。但是要知道T3最后W（A）