时间戳并发控制
1.简介¶
之前提到了利用锁实现的二阶段提交，这是一种基于锁的悲观控制策略。另外一种方式是基于时间戳的悲观控制策略，虽然没有利用锁，但是它通过时间戳进行对象的所有权分配，并通过副本保证事务对对象的可重复读。
2.时间戳分配¶
基本思想是通过为事务定义时间戳，从而决定事务的提交顺序，保证事务对交集数据的顺序修改。
时间戳不一定是根据时间定义的，也不一定是事务创建或提交时分配。但时间戳一定要满足的特性为自增性以及唯一性。常见的策略有：
- 时间戳：真正意义的系统时间戳。在分布式中需要对各节点进行时间协调，参见Spanner的true time。
- 计数器：一个单调自增数。
- 混合时钟（hybrid clock）：使用系统时间戳和逻辑时间戳的组合，详见扩展。
3.基于时间戳的事务排列（Basic Timestamp Ordering）¶
为数据库每个对象x分配两个时间戳，分别为读写时间戳R-TS(x)、W- TS(x)，表示该对象最近被读写的时间。
- 读对象：事务需要将自身的时间戳与对象的写时间戳进行比对。
- 若大于对象的写时间戳，则读取对象、更新对象的读时间戳（R-TS(x)=max(R-TS(x),TS(Ti))），并为该事务保存一份该对象的副本，保证重复读时不会被后来的事务修改
- 若小于对象的写时间戳，则终止事务并重新进行事务，以得到更新的时间戳。
- 写对象：
- 如果对象的读时间戳大于事务的时间戳，表示该事务修改了其他事务读到的对象，因此放弃；如果对象的写时间戳大于事务的时间戳，表示该事务的修改会被其他事务的修改覆盖，因此放弃。
- 否则更新事务的写时间戳，并保存一份副本保证可重复读。
- 一种优化方式称之为Thomas Write Rule，内容是如果TS(Ti)<W-TS(x)，该事务不需要终止，虽然不能修改数据库中的对象，但可以保存一份自己修改后的该对象的副本，只供自己使用即可。
可能遇到的场景是一个长时间运行的事务，被一些短时间，只是进行了一些简单修改的事务打断。
其次是，该方式的表是不能保证中断后恢复的，事务只有在它所依赖数据的对应事务都已经提交的情况下才是可恢复的，类似之前提到的多米诺效应，如果该事务终止了，你需要将该事务依赖的事务都依次回滚才可以将已经修改的数据恢复。很显然，这种方式下事务是可以读到比该事务更晚提交的事务的修改数据的。
最后，由于读写事务都需要保存一份读写对象的副本，因此在高事务并发的场景下内存代价更大。
扩展与参考¶
https://pds.gin.sh/hybrid-clock/