最近武汉冠状病毒有点凶猛, 希望大家都百毒不侵, 健健康康.

OPED 是 (我自己发起的) One Paper Each Day 挑战, 即每天(偶尔)读一篇 Paper, 领域不限.

这是 OPED 挑战的第十篇, 论文为 Spanner: Google’s Globally-Distributed Database

新年的第一篇博客是关于一篇比较老的论文 (2012 年), 并且之前就读过了. 之所以最近又想到读它是因为最近重读 DDIA, 它引用了 Spanner, 而我发现对 Spanner 的记忆已经非常模糊了, 所以就重新找来读一读.

Spanner 是什么

在介绍 Spanner 之前, 我们先来看看平时我们使用分布式数据库的时候, 希望它有哪些功能.

  1. 水平扩容. 不管我们的服务体量现在多大, 以后要是火了肯定要水平扩容
  2. 事务支持. 没有事务, 实现业务有点麻烦, 要是以后要收个钱啥的呢
  3. 线性一致. 没有线性一致, 写了之后半天才读得到, 不行不行

上面这些需求, 我想大家在工作中大部分情况下都会至少需要 1 到 2 个, 并且会有一个第一个选择. 比如我们公司, 需要水平扩容, 就会优先考虑 MongoDB; 事务支持的话就会优先考虑 Postgres. 同时要水平扩容和事务支持? 分库分表? Seata? 好像有点麻烦? TiDB?

Google 这么大的体量, 业务多种多样, 肯定会遇到更复杂的需求, 有的需求甚至同时需要三者. 为了解决这个问题, Google 实现了 Spanner. Spanner 是一个分布式的, Linearizable 的, 支持分布式事务的, 可以水平扩容的, 提供类似关系型数据库访问模式的一个数据库. 这个前缀真的多, 简单来说, Spanner 就是一个支持分布式事务并且还提供强一致的分布式数据库. (Spanner: 我全都要!)

Spanner 的物理架构

Spanner 的一个部署被称为一个 Universe. 由于 Spanner 的设计就支持”无限”水平扩容, 所以并不需要每个业务团队自己部署 Spanner 服务. 相反, 整个 Google 只有三个 Universe, 分别用来测试, 开发, 和线上环境. 业务团队在 Universe 中创建属于自己的 database, 并在 database 中创建若干个 table.

在一个 Universe 中, Spanner 包含了以下几种组件, 如下图所示

Spanner Components

一个 Spanner Universe 由若干个 Zone 组成, 一个 Zone 相当于一个”机房”, 它包含了一个 ZoneMaster, 若干个 LocationProxy 和很多的 SpanServer. ZoneMaster 负责分配数据到 SpanServer; SpanServer 负责保存数据并提供访问; LocationProxy 负责 route 请求. UniverseMaster 和 PlacementDriver 都是单点, 分别用作获取监控数据和处理 SpanServer 之间的数据迁移.

Spanner 的软件架构

Spanner 将数据划分成一个个 tablet, 每个 SpanServer 会存储很多个 tablet. Tablet 是 replication 的最小单元, 每个 tablet 都是一个 Paxos 节点, 一份数据的若干个备份所属的 tablet 组成一个 Paxos Group, 其中一个 tablet 会被选为 leader. 这个 leader 会包含一个 lock table 以及 transaction manager. Lock table 用于实现 2-phase-locking 来保证 serializable isolation. Transaction manager 实现 2-phase commit 用来执行分布式任务.

Spanner Software

Spanner 的 True Time API

True Time 应该是 Spanner 首创的一种新方案, 它将时间的不确定性暴露给用户, 让用户可以依赖于时钟判断顺序. 简单来说它提供了三种接口:

API 返回类型
now() Interval, 本质上是一个 tuple, 包含了 earliest 和 latest timestamp. 实际上就是包含了误差的一个时间范围
after(t) 判断当前时间是否是在传入的时间戳之后
before(t) 判断当前时间是否是在传入的时间戳之前

它的核心思想就是使用一个时间范围来包含时间的不确定性, 然后在判断时间先后的时候考虑上不确定性. 例如, 如果 now() 返回的 earliest 时间戳也大于 t, 那么 after(t) 就会返回 true, 否则就返回 false.

很多分布式系统都需要一个 time oracle 来分配 timestamp 给 transaction, 以实现各种特性, 这个 time oracle 往往是一个单点 (或者一个 paxos 的 group) 以避免多机 clock 有偏差. 而 Spanner 通过这样一套 API, 使得每一个节点都能轻松又安全的使用”本地时间”来判断顺序. 当然 True Time API 的数据源并不是完全本地, 每台机器上都部署了一个 true time daemon 定期和 true time master 同步时间.

Serializable Isolation 如何实现

Serializable Isolation 回顾

首先我们回忆一下 Serializable Isolation 到底是什么. Serializable Isolation 是 ACID 中的 I, 它的目的是为了实现数据库的并发控制, 使得在允许多个事务并发执行的条件下, 让数据库的状态和以某种合理的顺序来一个一个执行这些数据一样 (更多详情请见这篇博客).

实现 Serializable Isolation 的方式主要有以下几种:

  1. 实际顺序执行
  2. 2-Phase Locking (注意和 2-Phase Commit 不同)
  3. Serializable Snapshot Isolation

实际顺序执行非常好理解, 这里就不多做阐述了. 2-Phase Locking 简而言之就是通过上读写锁来保证涉及到同一份数据的事务顺序执行, 它的优点在于比较好理解, 缺点是容易引发性能问题, 因为读会 block 写, 一个只读的事务不应该阻塞一个写事务.

Serializable Snapshot Isolation 实际上一种乐观的并发控制, 它也基于 MVCC 提供的 Snapshot Isolation, 但是会检测 write skew (幻读的一种) 并触发事务的回滚或重试.

Spanner 如何实现

上面提到 Spanner 每个 Paxos Group 的 Leader 会维护一个 Lock Table, 用来实现 2-Phase Locking. 当一个事务只涉及到某个 tablet 中的数据, 我们只需要 Lock Table 就可以保证 Serializable Isolation.

那么如何保证分布式事务 (涉及到多个 Paxos Group) 的 Serializable 呢? 毕竟 Leader 的 Transaction Manager 实现的 2-Phase Commit 只能保证事务的原子提交 (分布式事务的所有部分全部 commit 或全部 abort). 这里就需要利用上 True Time API 了, 对于任意的事务, Spanner 会分配一个时间戳, 同时保证这个事务中的读取能够读到所有这个时间戳之前提交的事务 (具体方法就是 hold 住直到 after(t) 是 true). 这样 write skew 就不会发生了.

Linearizability 如何实现

Linearizability 回顾

Linearizability 就是 CAP 中的 C, 也叫强一致. 简单来说, 它是指对于一个数据, 它的写操作是原子的, 并且外部总是能读到它最新的版本.

举个例子, 比如 A 刷数据, 发现他买的某股票的今日最高价位到达了 100, 然后兴高采烈地告诉了 B. B 将信将疑地掏出手机一刷, 发现今日最高价位还是 99.

之所以会出现这种情况, 往往是因为一份数据有多个副本, 当一个写操作发生在某个副本之后, 被一个用户读到了, 但是另一个用户因为各种原因读了另一个副本, 获取了没有更新的数据. 如果两个用户之间没有其他的通信渠道, 我们可能没有办法判断先后. 但是在上面的例子中, 两次读取是有明确的先后关系的 (因为存在因果关系), 但是后一次读取却读到了更老的数据. 实际上这种情况在只有一个用户的时候也会发生, 比如两次读取分别 hit 了不同的副本.

在分布式环境下, 为了保证 Linearizability, 人们已经已经提出了很多方法, 比如使用 Consensus (共识) 算法. 常见的做法往往是使用共识算法选出一个 Leader, 让所有的读写操作都只走 Leader. 其他的 Follower 使用共识算法来从 Leader 同步数据. 这样做的问题就是当读的流量变大后, 单个 Leader 可能会扛不住.

Spanner 如何实现

巧了, Spanner 提供的 Linearizability 也是通过 True Time API 来实现的. 它通过 Commit Wait 的方法, 保证了如果一个事务在另一个事务之后发生 (不管是单个线程顺序执行的两次事务, 还是外部信道的因果关系), 那么后一个事务的 commit 时间戳一定大于前一个事务的 commit 时间戳, 这样读到的数据一定包含了前一个事务读到和写到的所有数据.

那么 Spanner 怎么处理单个 Leader 扛不住所有流量的问题呢? 请继续往下看.

Transaction 的具体流程

说了这么多, 我们来具体看一下 Spanner 中事务的具体执行流程. Spanner 的事务主要分成了两类 (论文中是三类, 其中一个是 Schema 的更新事务, 这里就不讨论了)

  • Read-Only Transaction
  • Read-Write Transaction

下面我们分别看一下两者的流程.

Read-Only Transaction

Read-Only Transaction, 顾名思义, 就是只包含读操作的事务. 只包含读操作的事务相对比较简单, 只要有 Snapshot Isolation 就可以了, 因为 write skew 不会发生. 具体流程如下

Read Only Transaction

当发起一个 Read Only Transaction 时, Spanner 会使用 True Time API 为调用方分配一个时间戳, 并挑选一个足够新的 Replica 让调用方读取, 这就解决的共识算法的单点问题. 那么怎么判断一个 Replica 是否足够新呢? 在 Spanner 中, 每个 Replica 都维护了一个时间戳, 来表示这个 replica 能提供直到什么时候的数据. 这个时间戳是通过 Paxos 最新 Log 的时间戳和目前还处在 Prepare 状态的事务时间戳取最小值计算出来的. 如果没有足够新的 Replica, 就会阻塞这个读取操作.

这里在重复一下, Replica 的 Leader 会在 Lock Table 中对读到的数据上锁.

Read-Write Transaction

Read-Write Transaction 同时包含了 Read 和 Write. 它相较于 Read Only Transaction 更为复杂, 流程如下所示.

Read Write Transaction

首先, 它会像只读事务一样, 获取时间戳, 发送读请求 (注意在 Spanner 中比较特殊的一点是, 事务中的写都是在事务的最后执行的, 所以同一个事务中的读操作无法读到事务中新写入的数据), 这里 Replica 的 Leader 也会上读锁.

在所有读操作完成之后, 调用方会在所有涉及到的 Paxos Group 的 Leader 中挑选一个做 Coordinator. 之后的二阶段提交都由这个 Coordinator 来负责完成. 这里由调用方负责挑选是为了避免 Spanner 内部的多次通讯, 具体选择哪个做 Coordinator 并不会影响正确性.

在挑选完之后, 调用方发送写操作, 一个 Commit 消息, 以及选择的 Coordinator 的 ID 给所有涉及到的 Paxos Group 的 Leader, 这些 Leader 也就是之前提到的 Participant Leader. 非 Coordinator 的 Participant Leader 会上写锁, 然后执行 Prepare 并发送一个 Prepare Timestamp 给 Coordinator. Coordinator 也会上写锁, 并在获取到所有 Prepare 消息之后选择一个满足一定条件的 Commit Timestamp: S, 并在本地添加一个 Commit 记录. 之后 Coordinator 会 hold 直到 True Time 的 after(S) 返回 true 才让所有其他的 replica 真正 commit (也就是上文提到的为了保证 Linearizability 所遵循的 Commit Wait 逻辑).

总结

前面说了那么多, 实际上 Spanner 主要使用了四种手段来实现我们需要的特性:

  • 维护 Lock Table 来实现 2-Phase Locking, 保证了非分布式事务的 Serializable

  • 使用 Transaction Manager / Coordinator 来实现 2-Phase Commit, 保证了分布式事务的 Atomicity

  • Replica 组成 Paxos Group 保证单个 Group 内 Replica 的同步的一致性

  • 使用 True Time API 保证分布式事务 的 Serializable 事务之间的 Linearizability.

其中 True Time API 是一个比较新颖的想法, 它通过暴露时间的不确定性, 来获取确定的时间顺序, 避免了很多其他分布式系统使用单点做逻辑时钟带来的 Scalability 问题. 当然, 这种 wait 直到确信时间先后的做法会带来性能上的隐患, Spanner 也做了很多优化, 核心思想就是细化时间粒度, 比如让每个 key 有独立的时间, 避免一个比较新的还没有 commit 的事务 block 不相关的数据的读写操作.

个人觉得这篇论文让我对分布式存储的理解更清晰了一点, 希望我这篇博客也能帮到你.