Spanner 论文阅读

相关背景

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

其主要有三点特色：

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

介绍

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

• 6.824 讲义
• 6.824 视频
• 论文
• Spanner 白皮书
• Spanner，True Time 和 CAP
• Spanner 十问

问题记录

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

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

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

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

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

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

总结

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