Spanner 论文阅读

本文最后更新于:3 年前

相关背景

Google Spanner 是 Google 一篇跨时代的论文,开启了 NewSQL 时代的序幕。

其主要有三点特色:

  • 2PC + 共识组来避免 2PC 的无限超时阻塞。
  • GPS 原子钟同步技术以支持快速的只读事务。
  • 支持 ACID 的全球型 NewSQL 数据库。

介绍

暂仅搬运一些资料,之后有时间再补。

问题记录

  1. 在 Spanner 中,只读事务可以从本地数据中心读取数据,以提高性能。但是,如果只读事务向少数副本发出请求,它可能得到过时的数据。这种行为可能会破坏严格的可序列化保证。那么 Spanner 如何应对这种情况以保持其正确性条件呢?

在 Spanner 中,每个事务都会根据 TrueTime 的 Start Rule 选择一个时间戳作为事务 id:对于写请求,其会在提交事务时 2pc 的 prepare 阶段选择 TT.now().latest 作为事务 id;对于读请求,其会在读事务开始时选择 TT.now().latest 作为事务 id。

每个 replica 都会维护一个递增的 tsafe 变量,对于读事务 T,当 tsafe >= 读事务 T 的 tid 时,可以执行该读事务而不违背外部一致性。

对于 t_safe,其等于 min(tsafepaxos,tsafetm)。对于 tsafepaxos,其等于当前 replica 能够看到的最新写事务的 tid,注意到 Paxos 的 leader 会将写入事务按照时间序发送,因此一旦某 replica 发现了已经存在 tid 大于 T 的写事务,则表明所有 tid 小于等于读事务 T 的已提交写入事务均已同步到本地。对于 t safetm,需要了解每个 paxos group 都会有 replica 个数个 transaction manager,follower 的 transaction manager 可以根据 leader 发送过来的日志保持与 leader 的同步。如果当前 replica 的 transaction manager 不存在已 prepare 但还未 commit/abort 的事务,则 tsafetm 为正无穷;否则为最小的已 prepare 但还未 commit/abort 事务的 tid – 1。对于 tid 大于 tsafetm 的读事务,直接去读也是不安全的。因为这部分还未提交的事务可能会提交,直接读的话便会漏掉这些数据。

因此对于一个读事务 T,一旦某 replica 发现了本地维护的 tsafe >= 读事务 T 的 tid,则可以直接执行读事务,这不会违背外部一致性。否则该 replica 需要等待直到本地维护的 tsafe 大于 读事务 T 的 tid 为止。

值得注意的是,这样的实现在部分场景下可能也有 liveness 的问题,比如该分片短期内没有新的写入事务且当前所有的事务都已 commit,即使所有 replica 都已经 catch up,tsafe 仍然始终是最后一个写入事务的 tid。如果此时来了一个新的读事务,其似乎会被永远 block 住。因为该读事务的 tid 永远大于保持不动的 tsafe。对于这种情况,该 replica 可以向 leader 发送一个 rpc,待 leader 等到 tt.now().earliest 大于该读事务的 tid 时返回 ack,此时该 replica 可以执行该读事务,因为未来产生的写事务 tid 都一定大于该读事务的 tid ,虽然其还未产生,但其一定不会对该读事务产生影响。

总结

简单记录一下 6.824 课程对 Google Spanner 所学。


Spanner 论文阅读
https://tanxinyu.work/spanner-thesis/
作者
谭新宇
发布于
2021年5月20日
许可协议