Spanner | zzys

Spanner是谷歌公司的分布式数据库，通过2PC实现的可串行化以及外部一致性结合，达到了类似于线性一致性的效果。同时对只读事务做了优化，在保证并发正确性的前提下，达到了非阻塞、无锁的读取。

组织结构

对于读写事务，采用2PC+Paxos保证可串行化。Paxos提升了TM的可用性，优化了2PC的缺点，同时为分片提供了副本，为读取增加了吞吐，同时也提升了可用性。

对于读事务，Spanner只会从最近的分片读取，并且无锁，无RPC，大大的提升了性能。

外部一致性： $T_{i}$ 代表事务 $T$ 的提交时间， $i$ 按照时间排序那么如果 $T_{2} > T_{1}$ ， $T2$ 就一定能够看到 $T1$ 的更新。串行化是指并发事务的执行结果和一个串行化的顺序的执行结果相同，这两者结合起来，就十分类似于线性一致性的定义了。

Spanner会为每个事务分配一个时间戳，对于读写事务，时间戳是commit的时间，对于只读事务，时间戳是事务第一次读取的时间，事务必须要在最开始声明自己是只读事务。

同时，每个数据也都有自己的时间戳，并依次构建了多版本存储，每个事务都只能读到小于自己时间戳的版本，这被称为快照隔离。

由于只读事务只会从最近的分片读取，并且分片使用了Paxos集群，那么怎么保证当前的分片的数据不会读到来自Learner（FOllower）的还未同步的脏数据呢？

当执行只读事务时，必须要等到有大于自己时间戳的读写事务发生，才可返回，否则等待。

时间戳在分布式系统中是个不确定的东西，不同的机器之间时间是一定有偏差的，那么就必然会对上面的方案造成影响。

假设两台Spanner S1 和 S2 ，S1提交读写事务T1，S2提交只读事务T2，有以下情况：

如果 S2 的时间较快，假设S1提交的事务T1的时间戳为100，等到通过Paxos同步到S2，S2的时间却已经到达的200，但实际上同步可能只用了10。这时T2开始执行，时间戳可能为210，就需要在等待更大时间戳的读写事务提交才可以返回，会影响到只读事务的性能。

如果S2的时间较慢，还是假设S1提交的事务T1的时间戳为100，等到通过Paxos同步到S2，S2的时间却只到达的50。这时T2开始执行，时间戳可能为80，我们就无法读取到T1所更新的数据，这样就违反了外部一致性的定义。

谷歌在每个数据中心都存在两种时间服务器：GPS以及原子钟。GPS用于从GPS卫星同步全球时间，原子钟用于本地同步时间，它们之间也会相互校准。每隔30S，Spanner的Timeslave Deamon就会从多个时间服务器中读取时间，排除极端不可信值，计算出真实值，依次尽可能的将不同机器的时间同步。

TrueTime API中的TT.now()会返回一个时间戳以及误差时间，这个误差范围，依次为基础，我们需要修改上面的实现。

Start rule：设事务时间戳为 TT.now().lastest。对于读写事务，TT 为开始提交的时间戳；对于只读事务，TT 为事务开始时间。
Commit wait：对于读写事务，延迟到 TS < TT.now().earliest 时再提交，保证事务时间戳TS 已经完全过去。

这样，对于后面的只读事务开始时的时间戳，就一定是要大于前面执行的读写事务时间戳，保证了外部一致性。