# Time Traveling Optimistic Concurrency Control

## TicToc: Time Traveling Optimistic Concurrency Control

### 0x00 引言

 A common way to implement the allocator is through an atomic add instruction that increments a global counter for each new transaction. This approach, however, is only able to generate less than 5 million instructions per second on a modern multi-core system due to the long latency incurred by the CPU’s cache coherence protocol [11, 35]. As such, most state-of-the-art T/O-based algorithms suffer from the timestamp allocation bottleneck [37].


1. 不存在同一的时间戳分配，不相关的事务不会相互影响；
2. 可以推迟时间戳分配，使用逻辑顺序来达到serializability ，即使这些事务在物理时间上是重叠的。减少了事务的abort；

### 0x01 基本算法

#### Lazy Timestamp Management

1. A read(x)
2. B write(x)
3. B commits
4. A write(y)


wts: The logical timestamp of the last committed txn that wrote to the record.
rts: The logical timestamp of the last txn that read the record.


TicToc中，一个数据项在wts创建特定的版本在rts之前都是合法的。一个事务是合法的，必须满足以下2点：

1. 事务的提交的ts必须在事务读取的(所有的)项的wts到rts之间；
2. 对于事务写的项，提交的ts必须大于数据项的rts；

TicToc读的方法如下：

#### 举个例子

step 1: A读x，此时x(wts = 2 and rts = 3)，x保存在A的read set；
step 2: B写x，在4时刻commit，B提交之后会变成x(wts = 4 and rts = 4)；
step 3: A写y，此时新的y在A的write set里面，对其它不可见；
step 4: A进入检验步骤，根据算法2，提交时间戳读数据项最大的wts，写数据项的最大rts+1。x在timestamp 2 and 3是合法的, 可以通过校验，然后提交(timestamp=3)；


### 0x02 正确性证明

LEMMA 1. Transactions writing to the same tuple must have different commit timestamps.
不同的事务写相同的touple时必须是不同的时间戳；
LEMMA 2. Transactions that commit at the same timestamp and physical time do not conflict with each other.