Spanner

image-20221010093526427

多处读取,解决读旧数据的问题

可能要操作不同的paxos组,需要分布式事务

Spanner比较有意思的点主要是:

  • 快照隔离机制, 该机制可以让只读型事务不经过2PC

  • TrueTime机制,在多地不同机器中,时钟不太可能完全同步,利用该机制就可以解决时钟不同步带来的问题。

外部一致性

Spanner引入了外部一致性的概念。指的就是在外部观测到一个事务,这个事务需要能看到在它开始之前(用真实时间瞄定)的所有已提交的事务所做的修改。

本质上其实就是一种 线性一致性

分布式事务实现

Spanner把事务分为:

R/W: 读写型事务

R/O: 只读型事务

读写事务

image-20221010094947274

二阶段提交会因为TC挂了卡死掉

Spanner使用paxos复制TC解决这个问题

读写型事务开销较大,如果明确都是读请求,应该转而实现只读型事务。

总结: 读写事务还是用了2PC,只不过使用paxos算法复制了TC(事务协调者)。

只读型事务

只读型事务不用经过2PC,而且可以直接找最近的节点读取。

2个正确性保证

  • 有顺序 serializable
  • 外部一致性 线性一致性

Snapshot Isolation 快照隔离

假设所有节点时钟同步
时间戳

我们给每个事务都标记上时间戳TIMESTAMP:

  • 读写型事务:

    把提交时间作为时间戳

    TS = COMMIT TIME

  • 只读型事务:

    把只读型事务开始的时间作为时间戳

    TS = START TIME

    image-20221018104410727

只读型事务读取快照规则

每个读写事务提交后,都会保存该事务的快照, 快照会附带最后一次事务的TS。

而只读型事务,只需要去该只读事务TS前最近的一个快照去读取数据就好了。

image-20221010171442752

上图中,

  • T1: 写x 写y 然后提交,提交时间是10,作为TS,生成快照@10
  • T2: 写x 写y 然后提交,提交时间是20,作为TS,生成快照@20
  • T3: 读x 读y,开始时间是15,作为TS

由于上文提到的规则,T3读取的是快照@10的值,得到x = 9, y = 11

how does it not absolutely brow up the storage? 这样做不会爆空间吗?

spanner肯定会丢掉过时的版本的snapshot,论文中没有详细提到。

其实就是,当TS < 15的只读型事务结束时,@15之前的快照版本就不需要了。只需要记录仍然还在执行的事务执行前的快照就好了(不会太多)

PS: paper中说可以取得这个数据昨天的版本,看起来应该保存的版本会更久一些。

如果读取数据的节点是少数派怎么办? SAFE TIME机制

只读型事务可以找最近的节点读取,但是paxos也只是多数复制,如果客户端读取的节点是少数派,并没有更新到最新的数据怎么办?

对此Spanner引入了SAFE TIME机制。Paxos ledear上的log会记录时间戳并且严格按照时间戳顺序发给replica,同时replica会记录从leader拿到的最后的log的时间戳。

当只读事务的时间戳>最新日志的时间戳时,会延迟直到收到更新的日志后再发送。

对于上面那个图的例子来说,就是如果要执行TS为15的只读型事务,就必须等到收到时间戳>15的log才可以进行。由于paxos按照时间戳发送,这时候肯定已经更新了时间15之前的所有数据了。

这个机制可能稍稍延迟只读事务。

各个节点时钟不同步怎么办?What if clocks aren’t synced? Spanner’s True Time Interval
时钟不同步的后果
  • 只读型事务取得的时间偏快

    截屏2022-10-18 11.28.49

这种情况下,T2开始之前,T1就提交了,由外部一致性,T2一定要能看到T1的修改。

但是由于T2和T3是并发执行的,所以T2可以看到T3的修改,也可以不看到,都符合外部一致性。

所以如果只读型事务的TS取得偏快,如图中这个情况,T2会读取@14的快照,无非就是多等待一段时间(SAFT TIME机制),还是满足外部一致性的。

  • 只读型事务取得的时间偏慢

    image-20221018113237461

这时候,T2会读不到T1的修改内容。**由于T2开始的真实时间是晚于T1提交的,由外部一致性,T2必须看到T1的修改。**这时候由于节点时钟没办法完全同步,就会造成不符合外部一致性的问题。

TrueTime Interval

为了解决上述问题,Spanner引入了TrueTime机制。

Spanner利用GPS和原子钟(只是手段),保证了节点获得的时间误差在一个范围内。

image-20221010200525768

True Time Interval: 反应正确时间的区间

(EARLIST, LATEST)

然后,spanner使用两条规则保证外部一致性:

  • 时间戳定义

    使用TrueTime的最晚值作为时间戳。

    TS = TT.now().latest

    对于读写型事务,时间戳依然为事务提交的结束时间的TS;对于只读型事务,时间戳依然为事务开始时间的TS。

image-20221018113955990

  • 等待提交机制

    对于读写型事务,按照上面所说的规则,时间戳依然为事务提交的结束时间的TS,此外,要求等待直到真实时间一定已经超过了改事务的时间戳以后,事务才实际提交。

    即:

    wait until TT.now().earliest > CommitTS

该机制能保证,当事务提交以后再获得的TrueTime,即使有误差,也不可能小于该事务的时间戳。 也就是说,如果紧接着就开启一个只读型事务,该只读型事务的TS,即使有误差,也一定是>前面那个事务的TS,一定能看到前一个事务的修改。这个机制保证了事务的外部一致性。

保证如果真实时间上,开启的时间在该读写型事务提交之后的只读型事务,一定能够看到该读写型事务的修改。

image-20221018114544298

比如下面这个例子:

事务T1选择了10为时间戳,但是它实际的提交需要等到保证真实时间绝对超过了10以后,再时间提交。这样,真实时间在10之后开启的只读型事务T3,取到的时间戳就一定>10, 可以正确读取到T1所做的修改。

image-20221010201914468

Q.E.D.