Spanner：Google 的全球分布式数据库

来自 Google 论文 Spanner: Google’s Globally-Distributed Database。

1 介绍

Spanner 是 Google 设计和部署的数据库：

• 可扩展
• 多版本
• 全球分布
• 同步复制

从最高层的抽象来看，它将数据分片在遍布全球的数据中心里的许多 Paxos 状态机组上。采用复制（replication）实现的高可用；客户端自动在副本间故障切换。

• 服务器数量变更，会自动重新分片数据
• 自动在机器（甚至数据中心）间迁移数据以均衡负载
• 被设计成能够扩展到几百个数据中心的上百万台机器的规模，存储上万亿行数据

Bigtable 是一个多版本的键值数据库，而 Spanner 是一个支持通用事务且提供 SQL 查询语句的半关系型数据库：

• 数据被存储在半关系型表中
• 数据有多个版本，每个版本都被打上提交时的时间戳
• 旧数据可能会被垃圾回收
• 应用程序能够根据读取老版本的数据

一些有趣的功能：

• 应用程序可以指定数据存储在哪个数据中心、与用户的距离（控制读延迟）、副本之间的距离（控制写延迟）、维护多少个副本
• 难以在分布式数据库中实现的功能：
  1. 外部一致性读写
  2. 全局一致读取某个时间点的数据

2 实现

• Spanner 底层实现的结构
• 抽象化的目录，用于管理复制和定位，是数据移动的单元
• 数据模型，为何 Spanner 看上去像关系型数据库而非键值存储

• 每个区域（zone）都有一台 zonemaster
• zonemaster 将数据分配至 spanserver；spanserver 为客户端提供服务
• 客户端通过每个区域的 location proxy 访问提供服务的 spanserver
• universe master 和 placement driver 目前都是单点
  • universe master 主要是一个展示所有区域状态的交互式控制台
  • placement driver 处理各区域之间的数据自动化移动，它会定期与 spanserver 通信来找出需要被移动的数据，满足更新后的复制约束或负载均衡。

2.1 Spanserver 软件栈

复制和分布式事务是分层到基于 Bigtable 的实现中的。

• 多版本

  • 每台 spanserver 存储 100-1000 个 tablet 数据结构，和 Bigtable 的 tablet 类似。通过 tablet 实现了下面的映射：

    (key:string, timestamp:int64) → string

  • Spanner 为数据分配时间戳，所以更像是一个多版本的数据库而非键值存储。

  • tablet 状态被存储在 B-tree 结构的文件组和一份 write-ahead 日志中，都在一个叫做 Colossus 的分布式文件系统（GFS 的后代）上。

• 多副本
  • 有些多副本的映射数据需要强一致性：每台 spanserver 实现了一个 Paxos 状态机，在其关联的 tablet 中存储元数据和日志。写操作必须要经过 leader 走 Paxos 协议；而读操作直接访问底层任何一个最新副本的 tablet 就行了。
  • 每个作为 leader 的 spanserver 副本都实现了一张锁表以控制并发，存储着二阶段锁的状态。
  • 每个作为 leader 的 spanserver 副本都实现了一个 transaction manager 以支持分布式事务，transaction manager 的状态存储在底层 Paxos 组中。

2.2 目录和数据位置

directory 是类似 bucket 的抽象。目录是数据位置的单元，是 Spanner 在 Paxos 组之间移动数据的单元：将频繁被一同访问的目录置于同一组，或将目录移动至离访问者更近的组。甚至当客户端正在操作时也能移动。

对目录的支持允许应用程序控制数据的位置，从两个维度控制：副本类型与数量，和副本的地理位置。

如果目录体积太大了，Spanner 会将其分片至不同的 Paxos 组（不同的服务器）。

2.3 数据模型

Spanner 向应用程序暴露这些数据功能：

• 基于半关系型固定表结构
• 查询语言
• 通用事务

对这些功能的支持是由多方面因素驱动的：

• 支持半关系型固定表结构和同步复制是因为 Megastore 的普及，Google 内部至少 300 个应用程序（Gmail、Calendar、Android Market、AppEngine 等等）在使用 Megastore，因为它的数据模型比 Bigtable 更易于管理，还有它支持跨数据中心的同步复制（Bigtable 只支持跨数据中心的最终一致性复制）。
• 支持类 SQL 查询语句同样明确，是因为 Dremel（一种交互式数据分析工具）的流行。
• Bigtable 缺失跨行事务导致怨声载道。虽然支持通用的二阶段提交开销巨大，会带来性能和可用性问题，但谁不喜欢事务呢？在 Paxos 上跑二阶段提交减轻了可用性问题。

Spanner 数据模型不是纯关系型的，行必须有名称，更确切地说，每个表都需要有一个或多个主键列的有序集合。所以 Spanner 看上去仍像是一个键值存储：主键构成了行名，每张表定义了从主键列到非主键列的映射关系。

3 真实时间（TrueTime）

真实时间以 TTinterval 代表时间，这是一个有边界的不确定的时间区间（与标准时间接口不同，标准时间接口没有不确定性的概念）。TT.now() 方法返回一个 TTinterval 时间段，保证其涵盖了 TT.now() 被调用的绝对时间。该时间段类似于带润秒的 UNIX 时间。定义瞬时误差的边界为 ε，为时间范围宽度的一半。TT.after() 和 TT.before() 方法是对 TT.now() 的封装。

用 t_abs(e) 函数表示事件 e 的绝对时间。换句话说，真实时间保证对于一次调用 tt = TT.now()，tt.earliest ≤ t_abs(e_now) ≤ tt.latest，e_now 是调用事件。

真实时间使用的底层时间参考来源于 GPS 和原子钟，使用两种参考源：

• GPS 参考源的天线和接收器可能会故障、被本地无线电干扰以及 GPS 系统中断，还有润秒这类设计错误。
• 原子钟和 GPS 截然不同，由于频率误差，在很长一段时间后会出现明显的漂移。

每个数据中心，有一组主时间机器，集群中的每台机器都部署一个从守护进程。大部分主时间机器用 GPS，其他用原子钟。每个守护进程轮询一组主时间机器来减小误差，有些来自邻近的数据中心有些来自父数据中心。通过 Marzullo 算法的一种变体来探测和拒绝不准确的时间机器，同步本地机器时钟。

4 并发控制

真实时间用于保证并发的正确性，实现了外部一致性事务、无锁只读事务和过去数据的非阻塞读等功能。

4.1 时间戳管理

单独的写入作为读写事务实现；单独的非快照读作为只读事务实现。两者都在内部重试（客户端无需实现重试循环）。

• 只读事务是一种有快照隔离性能优势的事务。它不仅仅是没有任何写入的读写事务。因为只读事务中的读取在系统选择的时间戳执行，没有锁，所以随之而来的写入不会阻塞。任意足够新的副本都可以处理只读事务中的读取。
• 快照读是无锁执行读取过去的数据。客户端也可以指定时间戳，或提供时间限制让 Spanner 来选择时间。在任意足够新的副本上执行。

对只读事务和快照读而言，只要选中了时间戳，提交就不可避免，除非那个时间点的数据被垃圾回收了。当一台服务器失败时，客户端内部通过相同的时间戳和当前读取位置在不同的服务器上继续查询。

4.1.1 Paxos Leader 租约

Spanner 的 Paxos 实现通过定时租约（默认 10s）使 leader 长期存活。潜在的 leader 发送请求获得投票租约；一旦收到 quorum 的租约投票，leader 就知道它有了租约。副本会在一次成功的写入后隐式地延长其租约投票，leader 会在租约投票快过期时请求延长。定义 leader 的租约时段以它得知租约为起始时间；当它不再有 quorum 数量的租约投票即终止。Spanner 依赖以下不相交的定理：每个 Paxos 组中每个 Paxos leader 的租约时段与其他 leader 的都不重叠。

Spanner 的实现允许某个 Paxos leader 通过从节点释放租约投票来退位。为了保证不重叠，Spanner 约束了何时退位。定义 s_max 为 leader 使用的最大时间戳。在退位前，必须等到 TT.after(s_max) 为 true

4.1.2 为读写事务分配时间戳

事务化的读写使用二阶段锁。可以在持锁的任意时间里为其分配时间戳。对于既定的事务，Spanner 为其分配时间戳，它同时也是代表着事务提交的 Paxos 写的时间戳。

Spanner 依赖以下单调定理：在每个 Paxos 组中，Spanner 以单调递增的顺序为 Paxos 写分配时间戳，甚至跨 leader 亦是如此。单个 leader 副本能够单调递增地分配时间戳。leader 必须只能在租约期内分配时间戳。要注意的是每当分配时间戳 s，s_max 会增大到 s 以保持不相交。

Spanner 还强制以下外部一致性定理：如果一个事务 T2 在另一个事务 T1 提交之后开始，T2 的提交时间戳必须大于 T1 的提交时间戳。

• 开始 负责协调写事务 Ti 的 leader 分配一个提交时间戳 Si，Si 不小于 TT.now().latest 的值。
• 等待提交 负责协调的 leader 确保 client 直到 TT.after(Si) 为 true 才能看到 Ti 提交的数据。等待提交确保 Si 小于 Ti 的绝对提交时间。

4.1.3 在一个时间点提供读取服务

上面说到的单调定理使得 Spanner 能够正确地判断一个副本的状态对一次读操作来说是否足够新。每个副本追踪一个安全时间值 t_safe，这是最新的副本中最大的时间戳。如果读操作的时间戳 t <= t_safe，那么这个副本能够满足这次读操作。

4.1.4 为只读事务分配时间戳

一次只读事务分为两阶段执行：

1. 分配一个时间戳 s_read
2. 执行 s_read 时间点的快照读作为事务读。任意足够新的副本上都能执行快照读。

一种简单的分配方法是，在事务开始后的任意时间，s_read = TT.now()，通过参数保持外部一致性。但如果 t_safe 不够大，数组读的执行就会阻塞。为了减小阻塞的几率，Spanner 应该分配最老的时间戳来保证外部一致性。

4.2 细节

解释一些读写事务和只读事务的细节，还有特殊的事务类型，被用于实现原子化的表结构修改。

4.2.1 读写事务

就像 Bigtable，事务中的写被缓存在客户端直到提交。因此，事务中的读看不到事务写的效果。Spanner 这个设计效果非常好因为读操作会返回数据的时间戳，而未提交的写操作还没被分配时间戳。

读写事务中的读取利用 wount-wait 来避免死锁。客户端将读操作提交给相应的组中的 leader 副本，它会获取读锁并读取最近的数据。当一个客户端的事务处于打开状态，它会发送心跳来避免参与的 leader 将事物超时。当客户端所有读取都完成并缓冲了所有写入后，就开始二阶段提交。客户端选择一个协调组并向每个参与的 leader 发送一条提交消息，带有协调者的身份标志和写缓冲。让客户端来驱动二阶段提交避免二次发送数据。

非协调者 leader 首先获得写锁，然后选择一个必须大于任意已分配给事务的时间戳（保持单调），并通过 Paxos 将准备记录写入日志。每个参与者然后通知该协调者它们的准备时间戳。

协调者 leader 首先也获得写锁，但跳过准备阶段。它在收到所有参与者 leader 的消息后为整个事务选择一个时间戳。这个提交时间戳 s 必须大于或等于所有准备时间戳，大于协调者接收到它的提交消息的时间 TT.now().latest，而且大于 leader 之前已经分配给事务的任意时间戳（再一次保持单调）。协调者 leader 接着通过 Paxos 日志写入一条提交记录（如果等待其他参与者超时，就取消）。

在允许任意协调者副本应用提交记录之前，协调者 leader 会等到 TT.after(s)，遵循 4.2.1 中描述的提交等待规则。因为协调者 leader 基于 TT.now().latest 选择的时间戳 s，现在要等到改时间成为过去。这个等待通常与 Paxos 通信重叠。在提交等待后，协调者向客户端和所有其他参与的 leader 发送提交时间戳。每个参与的 leader 通过 Paxos 日志记录事务的结果。所有参与者都应用相同时间戳然后释放锁。

4.2.2 只读事务

分配时间戳需要在所有参与读取的 Paxos 组之间协商。因此对于所有只读事务，Spanner 需要一个作用域表达式，该表达式总结了会被整个事务读取的 key。Spanner 自动为单独查询推导作用域。

如果作用域的值由单个 Paxos 组提供，客户端将只读事务提交至该组的 leader。当前 Spanner 的实现只会在 Paxos leader 为只读事务选择一个时间戳。该 leader 分配 s_read 并执行读取操作。对单点（single-site）的读取来说，Spanner 通常比 TT.now().latest 做的更好。定义 LastTS() 为在某个 Paxos 组中最近一次写提交的时间戳。如果没有就绪的事务，s read = LastTS() 分配就能满足外部一致性：事务将看到上一次写的结果，因此顺序在上一次写之后。

如果作用域的值由多个 Paxos 组提供，那么有多个选项。最复杂的一种是与所有组的 leader 通讯一遍来基于 LastTS() 协商 s_read。Spanner 当前选择了一种更简单的方式：客户端避免协商轮，就直接在 s_read = TT.now().latest 时执行读取操作（可能要等待安全的时间）。事务中的所有读取被发送到足够新的副本。

4.2.3 表结构变更事务

真实时间使得 Spanner 支持原子化的表结构变更。利用标准事务是不可行的，因为参与者的数量可能有几百万个。Bigtable 支持一个数据中心内的原子化表结构变更，但会阻塞所有操作。

Spanner 表结构变更事务基本上是一个标准事务的非阻塞变体。

1. 首先，显示地分配一个未来的时间戳，在事务就绪阶段注册。因此跨越成千上万台服务器的表结构变对其他并发活动的干扰最小。
2. 读取和写入，隐式地依赖于表结构，与任意已注册的表结构变更时间戳 t 同步：如果它们的时间戳在 t 之前，那就继续；如果落后于 t，必须阻塞到表结构变更事务之后。如果没有真实时间，定义在时间 t 发生表结构变更就没有意义。

5 评估

测试 Spanner 复制、事务和可用性的性能。

5.1 微基准测试

每个 spanserver 4C4G。客户端在不同的机器上运行。每个区域有一台 spanserver。客户端访问的网络延迟小于 1ms（这种布局应该很常见，大多数应用程序无需将数据分布至全球）。测试数据库由 50 个 Paxos 组 2500 个目录构成。操作为单独的读取和 4K 写入。所有读取会在压缩后耗尽内存，所以只能测试 Spanner 调用栈的开销。另外，在测试前先读一轮来预热缓存。

• 在延迟实验中，客户端发送了相当少的操作来避免服务器端的排队。从 1 个副本来看，提交等待大约 5ms，Paxos 延迟大概 9ms。随着副本数量上升，延迟大致保持不变，因为 Paxos 在一个组的副本中并行执行。随着副本数量增加，达到 quorum 的延迟就不再对单个慢速的 slave 副本敏感了。
• 在吞吐量实验中，客户端发送了相当多的操作来使服务器的 CPU 趋近饱和。快照读可以在任意足够新的副本执行，所以它们的吞吐量几乎随着副本的数量线性上涨。

表 4 展示了二阶段提交能够扩展到的合理的参与者数量：总结了跨 3 个区的一系列实验，每个实验有 25 台 spanserver。当扩展到 50 台 spanserver 时均值和 P99 延迟都很合理，扩展到 100 个参与者时延迟显著增加。

5.2 可用性

图 5 阐明了在多个数据中心运行 Spanner 的可用性效益，它展示了存在数据中心故障时三个吞吐量实验，所有实验都在相同时间范围内。实验 universe 由 5 个区域 Zi 组成，每个区域有 25 台 spanserver。测试数据库被分片至 1250 个 Paxos 组，100 个测试客户端持续地以 50K 次每秒的速率发送非快照读。所有 leader 都被显式地放置在 Z1 区域中。在每个实验 5 秒以后，一个区域内的所有服务器都会被干掉：非 leader 干掉 Z2；leader hard 干掉 Z1；leader soft 干掉 Z1，但是它会通知所有服务器先移交领导权。

干掉 Z2 对读取吞吐量没有影响。干掉 Z1 时给 leader 时间来移交领导权至另一个区域有少许影响：图中的吞吐量掉落得不明显，大概 3-4%。另一方面，不警告就干掉 Z1 有严重的后果：完成率几乎跌到了 0。当 leader 重新选举后，系统的吞吐量回升至 100K 次读每秒是因为实验中的两个因素：

1. 系统还有余量
2. 当 leader 不可用时操作会排队

因此系统的吞吐量回升，最终达到其稳定状态的速率。

我们还能看到 Paxos leader 租约设置为 10s 的效果。当区域被干掉后，leader 租约的过期时间应该在接下来的十秒内均匀分布。在挂掉的 leader 的租约很快过期后，新的 leader 被选举出来。大约在刺杀时间十秒后，所有组都有 leader 了，吞吐量恢复。更短的租约将减小服务器死亡对可用性的影响，但需要更多的租约刷新网络流量。

5.3 真实时间

关于真实时间方面有两个问题必须回答：

1. ε 真的是不确定的时钟边界吗？
2. 最坏情况下 ε 是多少？

前者，最严重的问题是如果本地时钟漂移是否大于 200/us/s：那将打破真实时间的假设。统计后 CPU 故障率是时钟故障率的 6 倍。也就是说，时钟问题相较于其他硬件问题极其罕见。因此，可以认为 TrueTime 的实现值得信赖。

图 6 展示了于上千台 spanserver 采集的真实时间数据，数据中心之间的距离达到 2200km 之远。它绘制了 ε 的第 90、99 和 99.9 百分位数，在时间从机器 进程从时间主机器对齐后立即采样。该样本忽略了 ε 中因本地时钟不确定而产生的锯齿，因此测量了时间主机器的不确定度（通常为 0）加上到主时间机器的通讯延迟。

数据表明决定 ε 基础值的这两个因素通常不是问题。但是存在显著的尾延迟问题，导致 ε 的值很高。尾延迟在 3 月 30 日降低是因为网络的改善，降低了网络链路传输的拥塞。ε 在 4 月 13 日的增长，为期大约一小时，是因为一个数据中心的两个时间主机器由于常规维护而关闭。

5.4 F1

Spanner 于 2011 年早期开始在生产负载下进行实验评估，作为重写后的 Google 广告业务后台 F1 的一部分。该后台原本基于按多种方式手动分片的 MySQL 数据库。

• 未压缩的数据有数十 TB，虽然相比于很多 NoSQL 实现这只是个小数字，但是已经大到 MySQL 难以分片了。
• MySQL 的分片方案为每个消费者和所有相关数据分配一个固定的片区。这种布局要使用索引和复杂查询，需要相当的了解应用程序业务逻辑中的分片。
• 随着客户数量和他们的数据量的上涨，重新分片的开销极其巨大，最后一次重分片花了两年，涉及到几十个团队的协作与测试来降低风险。

这样的操作过于复杂且无法定期执行，因此 F1 团队不得不限制 MySQL 数据库的增长，用 Bigtable 存储一些数据，对事务和在所有数据中查询的能力有所妥协。

F1 选择使用 Spanner 的几个原因：

1. Spanner 无需手动分片

2. 提供同步的复制和自动的故障切换

   MySQL 主从复制的架构故障切换困难，还有数据丢失和宕机的风险

3. F1 需要强事务语义，这个需求使得 NoSQL 不切实际

   F1 团队还需要在他们的数据上做二次索引，能够使用 Spanner 事务实现自己的一致性全局索引

目前应用程序所有的写操作默认发送给 Spanner 而不是 MySQL。F1 在美国西海岸有两个副本，东海岸有三个。副板位置的选择考虑了重大自然灾害导致的停电，还有它们的前端站点。Spanner 的自动故障切换几乎是不可见的。尽管近几个月来有过意外的集群故障，F1 团队要做的是更新他们的数据库模型以告知 Spanner 将 Paxos leader 放置在哪里，保持它们始终接近前端所在位置。

Spanner 的时间戳语义使得 F1 高效维护从数据库状态计算而来的内存中的数据结构。F1 维护一份逻辑历史日志记录所有变更，也作为每个事务的一部分写入 Spanner。F1 在某个时间点对数据做全量快照来初始化它的数据结构，然后读取增量的变更应用至数据。

8 总结

综上所述，Spanner 结合并扩展了两个研究领域的想法：

• 从数据库领域来说：友好的、易于使用的、半关系型接口、事务还有基于 SQL 的查询语句
• 从系统领域的角度：可扩展、自动化分片、容错、一致的副本、外部一致性、广域的分布式

自从 Spanner 诞生，Google 花了 5 年迭代至当前的设计与实现。这漫长的迭代是因为过了很久才意识到 Spanner 应该做的不仅仅是解决全球化复制命名空间的问题，还应该聚焦于 Bigtable 缺失的数据库功能。

TrueTime 是 Spanner 的关键。Google 证明了在时间 API 中重新定义时钟的不确定性，使得构建带有强时间语义的分布式系统成为可能。另外，随着底层系统对时钟不确定性更严格的约束，更强的语义带来的开销也会减少。设计分布式算法时，不应该再依赖宽松的时钟同步和较弱的时间 API。