实现基于时间戳的事务处理原型。
TO算法流程
- 维护若干时间戳
- 事务时间戳：以事务开始时间标识事务的先后顺序，表示为ts(T)
- 数据项读写时间戳：记录读写该数据的最新事务的时间戳，表示为r_ts(X), w_ts(X)
- 另每个数据项x有三个队列，分别为读队列dm_read(x)，写队列dm_write(x)，预写队列dm_pre(x)。min_R_ts(x)，min_P_ts(x)分别为读队列最小时间戳和预写队列最小时间戳。
- 同一事务后续的写失败导致之前的写撤销，引发一系列异常
- 所有写均不能直写数据，需先预写成功，再进行数据的修改
- 事务对某数据进行第一次读后，其他事务修改该数据，导致不可重复读
- 读操作copy出一份数据，后续对该数据的读都在该副本上操作
读操作
- 若读时间戳小于数据的写时间戳，ts(R)<w_ts(x)，abort；
- 若读时间戳大于预写队列的最小时间戳，ts(R)>min_P_ts(x)，则暂时不能执行，先缓存到dm_read(x)；
- 否则，则可以直接执行读操作。
预写操作
- 所有的写操作都先做预写，为了避免级联回滚，即pre_write
- 若预写时间戳小于数据的读或写时间戳，ts(P)<R_ts(x)或W_ts(x)，abort；
- 否则，缓存到预写队列dm_pre(x)中；
写操作
- 若写请求时间戳大于min_P_ts(x)或min_R_ts(x)，缓存到写请求队列dm_write(x)中
- 否则，直接执行
- 每执行一个写操作，min_P_ts(x)增大，执行小于该时间戳的读操作；相应的，min_R_ts(x)增大，执行小于该时间戳的写操作
- 其实相当于将读队列和预写队列的请求按时间戳从大到小依次执行
代码说明
本人完成的代码原型已经上传到GitHub。
代码结构
- global.h：全局配置及变量
- data_to.h/.cpp：基于时间戳的并发控制的算法
- cc_to.h/.cpp：基于时间戳的读写操作实现
- main.cpp：程序入口，测试程序的实现
算法实现
- 读操作
- 由cc_lock中get()实现，调用data_to中access()，请求类型为R_REQ
- 写操作
- 由cc_lock中update()实现，先调用access()，请求类型为P_REQ
- 若P_REQ执行成功，再调用access()，请求类型为W_REQ
