MIT 6.824 - Spanner: Google’s Globally-Distributed Database

Posted on 2022-06-19 Word count in article: 19k Reading time ≈ 32 mins.

介绍

Spanner 是一个由 Google 设计，构建和部署的可扩展的全球分布式数据库。从高层次的抽象来看，作为一个数据库，Spanner 会将数据进行分片，每个分片构建在一组 Paxos 状态机之上，同时所有的数据存储在世界各地的各个数据中心内。Spanner 使用副本来保证数据库的全球可用性和客户端读取数据的就近访问性；客户端也能自动的在各个副本之间实现故障转移。当数据量或者服务器数量发生变化时，Spanner 能自动的跨服务器对数据进行重分区；同时，Spanner 也能自动的跨服务器（甚至是跨数据中心）迁移数据来应对负载均衡或者异常。Spanner 的扩展性能够支持上百个数据中心内的几百万台服务器，以及几万亿的数据行。

应用程序可以借助 Spanner 来确保高可用，即使是面对大面积的自然灾害，也可以通过将数据存储在单个大洲或者跨大洲的多个数据中心来保证容错。Spanner 的第一个客户是 F1，F1 是 Google 广告后端的一个重构项目。F1 的每份数据在美国境内存有5个副本。大部分其他的应用程序一般会将数据备份在同一个地理区域内的3到5个数据中心中，不过这在应对极端灾害时的容错性要略差一些。因为在能够容忍1到2个数据中心异常的情况下，大多数的应用程序相比于更进一步的高可用来说更看重低延迟。

Spanner 设计的首要关注点是管理跨数据中心的数据副本，不过设计者依然在 Google 已有的分布式系统设施之上花了大量的时间来设计和实现某些重要的数据库特性。虽然 Bigtable 能满足很多项目的需求，不过依然有很多 Bigtable 的用户反馈在某些场景下 Bigtable 难以胜任：例如涉及复杂、不断改变的数据库模式；或者要求在大范围数据复制场景下保证强一致性。由于半关系型数据模型以及同步复制的特性，很多 Google 的应用选择使用 Megastore 来存储数据，尽管 Megastore 的写性能不是很好。因此，Spanner 从一个类似 Bigtable 的带版本号的键值存储演化为了一个基于时间戳的多版本数据库。Spanner 中的数据保存在半关系型的表中；每个数据存有多个版本，每个版本的数据都自动标记着提交时的时间戳；旧版本的数据可以根据可配置的垃圾回收策略进行回收；应用程序可以读取某个旧的时间戳下的数据。Spanner 支持通用的事务，以及提供了一个基于 SQL 的查询语言。

作为一个全球分布式数据库，Spanner 提供了几个有趣的特性。首先，应用程序能以合适的粒度动态的调控数据复制的配置。应用程序可以通过配置指定哪个数据中心保存什么样的数据，数据存储的位置距离终端用户有多远（控制读延迟），数据的各个副本间距离有多远（控制写延迟），每个数据要保存几个副本（控制持久性，可用性和读性能）。同时，系统可以动态和透明的在各个数据中心间迁移数据，从而在各数据中心间实现资源的均衡使用。第二，Spanner 实现了两个在分布式数据库中难以实现的功能：提供了外部一致性的读和写，以及在某个时间戳上跨全球数据库的一致性读。这些特性使得 Spanner 能够在全球多数据中心级别支持一致性备份，一致性的 MapReduce 任务执行，以及原子的数据库模式更新，即使执行这些操作时存在进行中的事务也没有关系。

Spanner 通过对事务记录全球提交时间戳来实现上述特性，即使事务可能会被分布式的执行。事务的时间戳体现了串行顺序性。另外，这个串行顺序性满足外部一致性（或者相当于线性一致性）：如果某个事务 $T_1$ 在另一个事务 $T_2$ 开始执行前完成提交，则 $T_1$ 的提交时间戳小于 $T_2$ 的提交时间戳。Spanner 是第一个在全球数据中心级别保证这一特性的系统。

实现上述特性的关键点是一个全新的 TrueTime API 及其实现。这个 API 直接将时间的不确定性暴露给了使用方，而 Spanner 基于 TrueTime 提供的不确定性时间的范围（后面会提到 TrueTime 返回当前时间时不是返回一个单独的值，而是一个范围，TrueTime 会确保当前时间落在这个范围内）实现了事务的时间戳先后顺序保证。如果这个时间的不确定性范围太大，Spanner 会减缓操作来等待不确定性范围变小。Google 的集群管理软件提供了 TrueTime API 的一种实现。这个实现利用多个现代的基准时钟（GPS 和原子钟）能将时间不确定性控制在很小的一个范围内（一般来说小于10毫秒）。

实现

本节描述了 Spanner 的结构及其底层实现。然后会再介绍目录（directory），和文件系统中的目录不同，Spanner 中的目录是一个抽象的概念，用于管理数据副本和访问局部性，同时也是数据迁移的最小单元。最后会介绍 Spanner 的数据模型，相比于键值数据库 Spanner 更像是个关系型数据库，以及描述了应用程序如何控制数据的存储位置来实现访问局部性。

一个 Spanner 的完整部署被称之为 universe。因为 Spanner 在全球级别的数据中心管理数据，所以一共只会有几个运行中的 universe。Google 目前运行了一个测试/体验环境的 universe，一个开发/生产环境的 universe，以及一个仅生产环境的 universe。

一个 Spanner 实例以一组 zone 的形式来组织，每个 zone 差不多等同于部署了一批 Bigtable 服务器。每个 zone 是一个可管理的部署单元。系统在各个 zone 之间进行数据复制。当上线或者下线数据中心时，可以向运行中的系统添加或者删除 zone。zone 也是物理隔离的单位：一个数据中心内可能有1个或者多个 zone，例如不同应用程序的数据需要分片到同一个数据中心内的不同服务器上。

alt

上图展示了 Spanner 的一个 universe 中各服务器的职责。每个 zone 有一个 zonemaster 和成百上千台 spanserver。zonemaster 向 spanserver 分发数据，spanserver 向客户端提供数据服务。同时，客户端通过每个 zone 内的 location proxy 来确定需要访问哪台 spanserver 获取数据。universe master 和 placement driver 目前是单点的。universe master 主要是一个控制台，用于展示所有 zone 的状态信息，从而方便调试。placement driver 负责自动的在各个 zone 之前进行数据迁移，这个的操作耗时一般是分钟级。出于满足数据副本数量的要求以及实现数据访问的负载均衡，placement driver 会周期性的和 spanserver 通信从而确认哪些数据需要迁移。出于篇幅考虑，论文只会描述 spanserver 的实现细节。

Spanserver 软件栈

alt

本节主要关注 spanserver 的实现并展示了如何在 Bigtable 的实现之上构建数据复制和分布式事务。上图展示了 spanserver 的软件栈。在底部，每个 spanserver 负责管理100到1000个被称之为 tablet 的数据结构实例。tablet 类似于 Bigtable 中表的抽象，其内部维护了如下的映射：

1	(key:string, timestamp:int64) -> string

和 Bigtable 不同的是，Spanner 给每一个数据都标记了时间戳，从而使得 Spanner 更像是一个多版本数据库而不是键值存储。每个 tablet 的状态会保存在一组类似 B 树的文件以及一个预写日志中，所有的文件都会保存在一个称之为 Colossus（Google File System 的后继者）的分布式文件系统中。

为了支持数据复制，每个 spanserver 在每个 tablet 之上构建了一个单 Paxos 状态机（Spanner 的早期设计支持每个 tablet 对应多个 Paxos 状态机，这能支持更灵活的复制配置。不过由于这种设计的复杂性作者最终放弃了）。每个状态机将其元数据和日志保存到对应的 tablet 中。Spanner 的 Paxos 实现支持长期存活的主节点，每个主节点会分配一个基于时间的租约，租期的默认长度是10秒。当前 Spanner 的实现会记录两次 Paxos 的写操作，一次是在 tablet 的日志中，另一次是在 Paxos 的日志中。不过这个目前只是权宜之计，可能会在未来修复。Spanner 的 Paxos 实现能以管道的方式执行，因此在 WAN 环境的延迟下能提高 Spanner 的吞吐；不过提交到 Paxos 的写操作会按照顺序执行。

Spanner 借助 Paxos 状态机实现了一致性的数据映射复制。每个副本的键值映射状态都会保存在相应的 tablet 中。客户端的写操作必须由主节点发起 Paxos 协议；而读操作可以由任意一个有着最新数据的副本执行。这些副本构成了一个 Paxos group。

对于身为主节点的副本来说，每个 spanserver 实现了一个锁表（lock table）来实现并发控制。锁表包含了两阶段锁的状态：它会将某个范围内的键和锁的状态建立映射（长期存活的主节点是高效管理锁表的关键）。在 Bigtable 和 Spanner 中，锁表都是专门为长时间运行的事务设计的（例如，对于报表生成这样的事务可能需要花费分钟级的时间才能完成），但在锁竞争激烈的情况下使用乐观并发控制策略会造成性能不佳。诸如事务读这样需要同步的操作需要先从锁表中获取锁；其他不涉及同步的操作则无需操作锁表。

对于身为主节点的副本来说，每个 spanserver 实现了一个事务管理器（transaction manager）来支持分布式事务。事务管理器被用来实现 participant leader；而其他同 Paxos 组内的副本则被称为 participant slaves。如果一个事务只涉及一个 Paxos 组（对于大多数的事务来说），则无需事务管理器介入，因为锁表和 Paxos 一起已经提供了事务功能。如果一个事务涉及多个 Paxos 组，则每个组的主节点需要协同完成两阶段提交。其中某个 Paxos 组会被选为协调者：该组的 participant leader 则会担任 coordinator leader，该组内其他的从节点则担任 coordinator slaves。事务管理器的状态会保存在底层的 Paxos 组中（因此这个状态数据也会存有多个副本）。

目录和数据放置

在键值映射之上，Spanner 的实现支持被称为目录（directory）的桶的抽象，目录是一组有着公共前缀的连续键的集合（命名为目录是由于历史的偶然；一个更好的命名可能是桶（bucket））。目录的支持使得应用程序可以通过设置合适的键来控制数据访问的局部性。

一个目录是数据放置的最小单元。每个目录下的所有数据有着相同的复制配置。数据以目录的形式从一个 Paxos 组迁移到另一个 Paxos 组，下图描述了这个过程。Spanner 可能会移动一个目录来减轻某个 Paxos 组的负载；或者将经常被同时访问的多个目录移动到同一个 Paxos 组中；或者将某个目录移动到距离客户端更近的 Paxos 组中。目录的移动可以和客户端的操作同时进行。一个 50 MB 大小的目录可以在几秒内完成。

alt

一个 Paxos 组可能会包含多个目录说明 Spanner 的 tablet 和 Bigtable 的 tablet 不同：Spanner 的 tablet 没有必要是行空间（row space）内按照字典顺序的连续分区。相反，一个 Spanner 的 tablet 可能包含了行空间的多个分区。正是基于此特性才使得多个同时被访问的目录可以被移动到同一个 Paxos 组中。下图展示了各组成部分间的关系：

alt

Spanner 使用 Movedir 这样的后台任务在多个 Paxos 组之间移动目录。Movedir 也被用来向 Paxos 组中添加或者删除副本，因为目前 Spanner 还不支持在 Paxos 内部实现配置变更。Movedir 没有被设计为一个独立的事务，这主要是为了避免在进行大量数据移动时阻塞读写请求。相反，movedir 会在后台开始迁移数据。当 movedir 完成数据迁移，但还剩下一小部分数据未迁移时，则会发起一个事务自动的完成数据的迁移，然后更新涉及的两个 Paxos 组的元数据。

目录是应用程序能够控制副本的地理位置属性（或者简单来说，数据放置）的最小单位。在 Spanner 的设计中，数据放置规范语言（placement-specification language）和管理副本配置的职责相解耦。管理员可以控制两个维度：副本的数量和类型，以及副本所在的地理位置属性。Spanner 为这两个维度提供了可选的选项（例如，North America, replicated 5 ways with 1 witness）。应用程序通过标记每个数据库和/或者单个目录的复制选项组合来控制数据的复制。例如，某个应用程序可能会将每个终端用户的数据保存在自己的目录中，从而使得用户 A 的数据在欧洲有三个副本，用户 B 的数据在北美有5个副本。

出于表达清晰的考虑作者简化了这块的描述。实际上，如果某个目录包含的数据过多，Spanner 会将其拆分为多个段（fragment）。不同的段会由不同的 Paxos 组提供服务（也对应了不同的服务器）。Movedir 实际上是在各个 Paxos 组之间移动段，而不是整个目录。

数据模型

Spanner 为应用程序提供了如下的数据特性：一个基于模式化半关系型表的数据模型，一个查询语言，以及通用型事务。之所以要支持这些特性是受几方面的驱动。支持模式化半关系型表和同步复制的需求来自于 Megastore 的流行。至少有300个 Google 内部的应用程序选择使用 Megastore（尽管它的性能不是很好），因为它的数据模型比 Bigtable 更简单，而且它也支持跨数据中心的同步数据复制（Bigtable 只支持跨数据中心数据复制的最终一致性）。使用 Megastore 的 Google 应用程序中比较有名的有 Gmail，Picasa，Calendar，Android Market 和 AppEngine。在 Spanner 中支持类似 SQL 的查询语言的需求同样很明确，因为交互式数据分析工具 Dremel 也很流行。最后，希望 Bigtable 支持跨行的事务的呼声也很强烈；开发 Percolator 的部分原因就是为了解决这个问题。某些作者认为通用的两阶段提交的支持成本太大，因为它存在性能和可用性问题。不过，Spanner 的作者认为最好交给应用开发人员来处理由于过度使用事务而产生的性能瓶颈，而不是始终在缺少事务的环境下编程。而在 Paxos 之上实现两阶段提交则减缓了可用性问题。

应用程序的数据模型构建在目录式的键值数据映射之上。一个应用程序会在一个 universe 中创建一个或者多个数据库。每个数据库可以包含不限制数量的模式化表。Spanner 的表类似于关系型数据库中的表，它同样有行，列，以及带版本的值。本文不会深入探讨 Spanner 的查询语言。它和 SQL 很像不过在这基础之上多了些扩展来支持 protocol-buffer 类型的字段。

Spanner 的数据模型不是纯关系型的，它的行必须有名称。更准确的来说，每张表需要有一个或者多个主键列组成的有序集合。这个要求使得 Spanner 看起来像一个键值存储：主键定义了每行的名称，每个表定义了主键列到非主键列的映射。只有某个主键对应有值（即使值是 NULL）才能被认为某一行存在。采用这个结构使得应用程序能通过选择键来控制数据访问的局部性。

alt

上图展示了 Spanner 数据模式的一个示例，在这个例子中，我们创建了两张表来存储每个用户和每张照片的元数据。Spanner 的模式语言和 Megastore 类似，不过 Spanner 有额外的要求，Spanner 的每个数据库必须由客户端分区为一个或者多个层次化的表。客户端程序通过 INTERLEAVE IN 来声明数据库模式的层次化结构。位于层次化结构顶端的表被称之为 directory table。directory table 中以 K 为键的数据，和关联的子孙表中所有键以 K 为起始的行按照字典顺序组成了一个目录。ON DELETE CASCADE 表明如果删除了 directory table 中的一条数据，则需要一并删除关联的子孙表中的数据。上图也展示了示例数据库的交错结构（interleaved layout）：例如，Albums(2, 1) 表示 Albums 表中 user_id 为2，album_id 为1的数据。这种由交错的表组成的目录对于客户端来说非常重要，因为它使得客户端能够描述不同的表之间的局部性关联，这对于分片、分布式的数据库的高性能来说非常重要。如果缺少这个特性，Spanner 将无从知晓最重要的局部性关联。

TrueTime

本节主要描述 TrueTime 的 API 及概述其实现。TrueTime 大部分的细节会在另一篇论文中描述，本文主要是展示它对于 Spanner 的重要性。下表列举了 TrueTime 的 API。TrueTime 以 TTinterval 的形式表示时间，TTinterval 是一段表示非确定性时间的有界区间（而标准时间接口并不会将时间的不确定性暴露给客户端）。TTinterval 两个端点值的类型为 TTstamp。TT.now() 会返回一个 TTinterval，并且保证 TTinterval 所表示的时间区间一定包含 TT.now() 被调用时的绝对时间。这个时间类似于带闰秒的 UNIX 时间。定义时间的瞬时误差上限为 $\epsilon$ ，其值为 TTinterval 区间长度的一半，以及定义 $\bar{\epsilon}$ 为平均误差上限。TT.after() 和 TT.before() 是基于 TT.now() 的更易用的封装。

Method	Returns
TT.now()	TTinterval: [earliest, latest]
TT.after(t)	true if t has definitely passed
TT.before(t)	true if t has definitely not arrived

记某个事件 e 发生的绝对时间为函数 $t_{abs}(e)$ 。那么以更正式的术语来说，TrueTime 保证对于某次调用 tt = TT.now()，有 $tt.earliest \leq t_{abs}(e_{now}) \leq tt.latest$ ，其中 $e_{now}$ 是调用 TT.now() 的事件。

TrueTime 底层使用的时间参照是 GPS 和原子钟。TrueTime 使用两种形式的时间参照是因为它们有着不同的异常模式。GPS 发生异常可能是由于天线或者接收器异常，本地电磁波干扰，某些关联异常（例如设计的缺陷造成无法正确处理闰秒和电子欺骗），以及 GPS 系统瘫痪。原子钟的异常模式和 GPS 无关，不过在经过很长一段时间后可能会因为频率误差造成严重的精度缺失。

TrueTime 的实现由每个数据中心中的一组 time master 机器完成，每个机器上存在一个 timeslave 守护进程。大多数的 time master 安装了具有专用天线的 GPS 接收器；这些机器在物理上相互隔离，从而降低天线异常，电磁波干扰和电子欺骗的影响。剩下的 time master（被称之为 Armageddon masters）则配有原子钟。一个原子钟并不是太昂贵；一个 Armageddon master 的成本和一个 GPS master 的成本相当。各个 time master 会定期的互相对比各自的参照时间。每个 time master 也会对比自己的参照时间和本地时钟，如果两者相差过大则该 time master 会退出集群。在时钟同步期间，Armageddon masters 会保守的根据最差情况的时钟漂移来逐渐增加时间的不确定性。GPS masters 的时间不确定性误差一般接近于0。

每个 timeslave 守护进程会拉取多个 time master 的参照时间来减少单个 time master 异常造成的时间误差。timeslave 轮询的 time master 一部分来自于就近数据中心的 GPS master；剩下的来自于更远的数据中心的 GPS master 以及一些 Armageddon master。获取到其他 time master 的参照时间后，timeslave 守护进程会通过一种 Marzullo 算法的变种来识别出不可信的值，然后根据可信的值同步本地时钟。为了避免异常的本地时钟造成影响，如果某个机器的时钟误差频繁超过组件规范和工作环境下的误差上限，则该机器会从集群中剔除。

在时钟同步期间，timeslave 守护进程也会逐渐增加时间的不确定性。记 $\epsilon$ 表示保守最差情况下的本地时钟偏移。 $\epsilon$ 的值同时也依赖 time master 的不确定性以及和 time master 的通信延迟。在 Google 的生产环境中， $\epsilon$ 呈现出随时间变化的锯齿形函数，在每次轮询 time master 间隔间 $\epsilon$ 的值在1到7毫秒内浮动。因此在大多数时间里 $\bar{\epsilon}$ 的值为4毫秒。当前 timeslave 守护进程轮询 time master 的时间间隔为30秒，以及时钟漂移速率为200微妙/秒，最后 $\epsilon$ 的浮动范围为0到6毫秒。而剩下的1毫秒则来源于和 time master 的通信延迟。当发生异常时， $\epsilon$ 的偏移范围超过7毫秒也是有可能的。例如，有时候 time master 的不可用会造成数据中心范围内 $\epsilon$ 值的增加。类似的，服务器过载以及网络链路异常也有可能造成局部范围内 $\epsilon$ 的值产生毛刺。

并发控制

本节描述了 Spanner 如何使用 TrueTime 来保证并发控制下的正确性特性，以及如何利用这些正确性特性来实现诸如外部一致性事务，无锁只读事务以及非阻塞式的读取旧数据。例如要在某个时间戳 t 对整个数据库做一次审计读取操作，则借助这些特性可以保证这次操作一定能够读取到在时间戳 t 之前已经提交的事务修改。

另外，将 Paxos 的写操作（除非上下文明确的情况下，后续此操作都被称之为 Paxos writes）和 Spanner 的客户端的写操作区分开非常重要。例如，两阶段提交场景下 Paxos 会在准备阶段执行写操作，这个写操作没有任何相关联的客户端写操作。

时间戳管理

下表列举了 Spanner 支持的操作类型。Spanner 支持读写事务（read-write transactions），只读事务（read-only transactions）（预先声明的快照隔离事务（snapshot-isolation transactions）），和快照读（snapshot reads）。单独的写事务由读写事务实现；单独的非快照读由只读事务实现。两者都会在实现内部执行重试（因此客户端无需编写自己的重试逻辑）。

Operation	Timestamp Discussion	Concurrency Control	Replica Required
Read-Write Transaction	Section 4.1.2	pessimistic	leader
Read-Only Transaction	Section 4.1.4	lock-free	leader for timestamp; any for read, subject to section 4.1.3
Snapshot Read, client-provided timestamp	——	lock-free	any, subject to section 4.1.3
Snapshot Read, client-provided bound	Section 4.1.3	lock-free	any, subject to section 4.1.3

只读事务借助了快照隔离从而有着较好的性能。一个只读事务必须事先声明为不包含任何写操作；它并不简单是一个没有写操作的读写事务。系统会为只读事务选择一个时间戳从而能够以无锁的方式读取以该时间戳为基准的数据，因此也不会阻塞接下来的写操作。只读事务中的读操作可以由任何有着足够新的数据的副本执行。

快照读指的是读取过去的数据因此也无需加锁。客户端可以为快照读指定一个时间戳或者指定一个期望时间戳的上限，然后由 Spanner 选择一个时间戳。不管在哪种情况下，快照读可以由任何有着足够新的数据的副本执行。

对于只读事务和快照读来说，一旦确定了时间戳事务的提交就不可避免了，除非该时间戳对应的数据已经被垃圾回收了。因此，客户端可以避免在重试循环中缓冲结果。当某个服务器异常时，客户端可以在另一台服务器上重新以期望的时间戳和当前的数据读取位置继续执行查询操作。

Paxos 主节点租约

Spanner 的 Paxos 实现使用了基于时间的租约来确保某个主节点长期存活（租期默认是10秒）。主节点的候选者会向其他节点发送请求来获取基于时间的租约投票（lease votes）；当该候选者收到大多数的选票后就知道自己持有了租约。当某个副本成功的执行写入后会同时延长租约选票，而对于主节点来说则会在租期快过期前发起延长租约选票的请求。定义某个主节点的租期区间（lease interval）始于获取了大多数的选票，终于不再持有大多数的选票（因为某些选票已过期）。Spanner 依赖如下的不相交不变式（disjointness invariant）：对于每个 Paxos 组来说，每个 Paxos 主节点的租期区间都和任意其他主节点的租期区间不相交。

Spanner 的实现允许某个 Paxos 主节点通过释放从节点的选票来主动发起主节点退位。为了维持不相交不变式（disjointness invariant），Spanner 会限制在什么情况下才能发起主节点退位。定义 $s_{max}$ 表示某个主节点使用的最大时间戳。后面章节会描述什么时候 $s_{max}$ 会增加。因此，某个主节点只有等到 $TT.after(s_{max})$ 为真时才能发起退位。

为读写事务分配时间戳

读写事务需要用到两阶段锁。因此，Spanner 可以在获取所有锁之后，释放任意锁之前为事务分配时间戳。对于某个给定的事务来说，Spanner 会以 Paxos 的写操作的时间戳作为事务的提交时间戳。

Spanner 依赖如下的单调不变式（monotonicity invariant）：在每个 Paxos 组内，即使是多个不同的主节点之间，Spanner 分配给 Paxos 写操作的时间戳都是单调递增的。对于单个主节点来说，分配单调递增的时间戳没有什么困难。Spanner 通过不相交不变式（disjointness invariant）确保了在多个不同的主节点之间也能保证单调不变式（monotonicity invariant）：每个主节点只能分配位于任期区间内的时间戳。每当主节点分配了一个时间戳 s， $s_{max}$ （某个主节点使用的最大时间戳）都会更新为 s 来确保不相交不变式（disjointness invariant）。

Spanner 同时也保证了如下的外部一致性不变式（external-consistency invariant）：如果某个事务 T2 的开始时间晚于事务 T1 的提交时间，则 T2 的提交时间戳一定大于 T 的提交时间戳。定义事务 $T_i$ 的开始和提交事件为 $e_i^{start}$ 和 $e_i^{commit}$ ；事务 $T_i$ 的提交时间戳为 $s_i$ 。则有不变式 $t_{abs}(e_1^{commit}) < t_{abs}(e_2^{start}) \implies s1 < s2$ 。Spanner 中执行事务和分配时间戳的协议遵循了如下的两条规则，从而确保了上述的不变式。定义两阶段提交协议的 coordinator leader 针对某个写操作 $T_i$ 发起提交请求对应的事件为 $e_i^{server}$ 。则 Spanner 遵循的两条规则为：

开始（Start）：在事件 $e_i^{server}$ 之后，两阶段提交协议的 coordinator leader 分配给某个写事务 $T_i$ 的提交时间戳 $s_i$ 不会小于 TT.now().latest。注意 participant leaders 在这一阶段不会参与；4.2.1节会介绍在实现提交等待（Commit Wait）规则时 participant leaders 的职责。
提交等待（Commit Wait）：两阶段提交协议的 coordinator leader 会确保在 $TT.after(s_i)$ 返回真之前客户端不会读取到事务 $T_i$ 提交的数据。提交等待（Commit wait）确保了 $s_i$ 一定小于事务 $T_i$ 提交的绝对时间，或者说 $s_i < t_{abs}(e_i^{commit})$ 。4.2.1节会描述提交等待（Commit wait）的实现。其证明如下：

\begin{aligned} s_1 &< t_{abs}(e_1^{commit}) \qquad& (commit \, wait) \\ t_{abs}(e_1^{commit}) &< t_{abs}(e_2^{start}) \qquad& (assumption) \\ t_{abs}(e_2^{start}) &\le t_{abs}(e_2^{server}) \qquad& (causality) \\ t_{abs}(e_2^{server}) &\le s_2 \qquad& (start) \\ s_1 &< s_2 \qquad& (transitivity) \end{aligned}

根据某个时间戳读

4.1.2节描述的单调不变式（monotonicity invariant）使得 Spanner 能正确的判断某个副本的状态是否足够满足某个客户端的读请求。每个副本都会记录一个称之为安全时间（safe time）的变量 $t_{safe}$ ，这表示当前副本拥有到 $t_{safe}$ 为止所有已提交事务的修改。因此，只要客户端希望读取的数据的时间戳 t 满足 $t \leq t_{safe}$ ，则当前副本就能够提供读操作。

定义 $t_{safe} = min(t_{safe}^{Paxos}, t_{safe}^{TM})$ ，其中 $t_{safe}^{Paxos}$ 表示每个 Paxos 状态机的安全时间， $t_{safe}^{TM}$ 表示每个事务管理器的安全时间。 $t_{safe}^{Paxos}$ 的实现很简单：它的值等于最近一次提交的 Paxos 的写操作的时间戳。因为 Spanner 会以单调递增的顺序分配时间戳，加上 Paxos 会按顺序应用写操作，因此某个写入操作一定不会在 $t_{safe}^{Paxos}$ 或其之前发生。

当不存在完成了准备阶段（但事务还未提交）的事务时， $t_{safe}^{TM}$ 的值为 $\infty$ ——即两阶段提交协议中已完成准备阶段，但还未完成提交阶段的场景（对于 participant slave 来说， $t_{safe}^{TM}$ 指向的是该副本所属主节点的事务管理器的安全时间，从节点可根据主节点下发的写请求中的元数据推断而来）。如果存在这样的事务，则受这些事务影响的状态是不确定的：因为对于 participant replica 来说并不知道这些事务最终是否会被提交。在4.2.1节会介绍，Spanner 的提交协议确保了每个 participant 能知道某个已准备完成的事务的时间戳的下界。每个 participant leader（对应某个 Paxos 组 g）会为某个事务 $T_i$ 在准备阶段的日志中记录一个时间戳 $s_{i, g}^{prepare}$ 。coordinator leader 会确保对于组 g 中的每一个事务的参与者来说，事务的提交时间戳 $s_i$ 满足 $s_i \geq s_{i, g}^{prepare}$ 。因此，对于组 g 中的每个副本来说，在组 g 内完成准备阶段的所有事务 $T_i$ ，有 $t_{safe}^{TM} = min_i(s_{i, g}^{prepare}) - 1$ 。

为只读事务分配时间戳

只读事务会有两阶段来执行：首先会分配一个时间戳 $s_{read}$ ，然后以快照读的方式来执行读取时间戳 $s_{read}$ 处的数据。快照读可以由任何有着足够新的数据的副本执行。

可以简单的选取 TT.now().latest 作为 $s_{read}$ 的值，则类似于4.1.2节中关于写事务的描述，就一定能读取到在 $s_{read}$ 之前提交的事务修改。然而，如果客户端读取的副本的 $t_{safe}$ 还没有更新（从系统层面来看，某个在 $s_{read}$ 之前提交的事务已执行成功，但当前副本并不一定知道这个信息），为了不破坏外部一致性，避免客户端读取到旧的数据，则可能需要阻塞客户端的读取直到 $t_{safe}$ 更新完成（另外， $s_{read}$ 的选取也会导致 $s_{max}$ 的更新来确保不相交不变式（disjointness invariant））。为了减少阻塞的可能，Spanner 需要选取满足外部一致性前提下最老的时间戳。4.2.2节会介绍如何选取这个时间戳。

细节

本节会描述读写事务和之前介绍只读事务时省略的实现细节，以及某种特殊的事务类型实现用来支持原子的模式修改。然后会再描述某些对基础方案的改进。

读写事务

类似于 Bigtable，在某个事务提交前，其写操作会在客户端中缓冲。因此，某个事务中的读操作不会读取到同一个事务中的写操作。这个设计能很好的适配 Spanner，因为读取操作会返回被读取数据的时间戳，而未提交的写操作还未被分配时间戳。

读写事务中的读操作会使用 wound-wait 来避免死锁。客户端向主节点发起读操作，主节点会获取相应的锁然后读取最新的数据。当客户端的事务还在进行中时，它会定期的发送消息来避免 participant leaders 将其事务超时。当客户端完成所有的读操作以及缓冲了所有的写操作时，它就会开始执行两阶段提交。客户端会首先选择一个协调者组（coordinator group），然后给每一个 participant leader 发送一条提交消息，这个提交消息中包含了协调者的标识符以及所有客户端缓冲的写操作。由客户端发起两阶段提交避免了在广域链路下发送两次数据（如果两阶段提交不由客户端发起，可能的一种情况是客户端先将缓冲的写操作发给某个 participant leader，不管是这个 participant leader 自己成为 coordinator leader 还是让其他的 participant leader 成为 coordinator leader，都需要将客户端缓冲的写操作发送给其他的节点，这就造成发了两次数据）。

非协调者的 participant leader 会先获取写锁。然后它会选取一个比之前所有的事务的时间戳都大的时间戳作为准备阶段的时间戳（为了确保单调不变式（monotonicity invariant）），然后通过 Paxos 记录一条准备阶段的日志。然后每个 participant leader 会通知协调者自己所分配的时间戳。

协调者同样会先获取写锁，但是会跳过准备阶段。在收到所有 participant leader 的时间戳后，它会基于这些时间戳选择一个时间戳作为整个事务的时间戳。所选择的事务提交的时间戳 s 必须大于等于任意一个 participant leader 的准备阶段的时间戳（为了满足4.1.3节的限制约束），同时也要大于协调者收到提交消息时的时间戳 TT.now().latest，以及大于 coordinator leader 所有分配给之前的事务的时间戳（同样是为了确保单调不变式（monotonicity invariant））。然后 coordinator leader 也会通过 Paxos 记录一条提交的日志（或者在等待其他参与者时超时从而放弃当次事务）。

在允许参与事务的副本执行提交命令前，coordinator leader 会先进行等待直到 TT.after(s) 返回真，这就满足了4.1.2节描述的提交等待（commit-wait）规则。因为 coordinator leader 会基于 TT.now().latest 选择时间戳 s（TT.now().latest 只是其中的一个参考基准，但是实际的时间戳也必然会大于 TT.now().latest），然后现在需要等待直到当前的时间戳大于 s，则等待的时间至少是 $2 * \bar{\epsilon}$ （时间的瞬时误差上限记为 $\epsilon$ ，其值为 TTinterval 区间长度的一半， $\bar{\epsilon}$ 表示平均误差上限。因为最差的情况下当前的绝对时间可能正好是 TTinterval 区间的起始位置，从而需要等待整个区间长度）。不过这个等待时间基本上是和 Paxos 的通信重合的。在提交等待（commit-wait）结束后，协调者将事务的时间戳发送给客户端以及其他的 participant leader。每个 participant leader 通过 Paxos 记录事务的结果。每个参与者也同样在相同的时间戳下应用日志然后释放锁。

只读事务

给只读事务分配时间戳需要所有涉及的 Paxos 组进行协商。因此，Spanner 要求每个只读事务需要声明一个 scope 表达式，这个表达式汇总了整个只读事务会读取的键。Spanner 会自动的为独立的查询推导出 scope。

如果某个 scope 的值只涉及单个 Paxos 组，则客户端会向该 Paxos 组的主节点发起只读事务（当前 Spanner 的实现中只会由主节点为只读事务选取时间戳）。主节点选取时间戳 $s_{read}$ 之后开始执行读操作。对于单点（single-site）读操作，Spanner 通常能选取一个比 TT.now().latest 更好的时间戳。定义 LastTS() 表示该 Paxos 组中最后一次提交的写操作的时间戳。如果当前没有任何已完成准备阶段的事务，那么选取 LastTS() 作为 $s_{read}$ 的值就已经能满足外部一致性：当前的只读事务能读取到上一次写操作的结果，因此该只读事务也发生在这之后。

如果 scope 的值涉及了多个 Paxos 组，这就有几种选择。其中最复杂的选择就是和每一个 Paxos 组的主节点通信，然后基于每个 Paxos 组的 LastTS() 来选取 $s_{read}$ 。Spanner 目前选取了更简单的实现。客户端省略了和所有涉及的 Paxos 组的协商阶段，直接选取 TT.now().latest 作为 $s_{read}$ 的值（当然前面说过这会造成阻塞，需要等待副本的安全时间满足大于等于 $s_{read}$ ）。因此该事务中所有的读操作都可以发送给有着足够新的数据的副本处理。

模式变更事务

TrueTime 使得 Spanner 能够支持原子的模式变更。使用标准的事务来处理模式变更是不切实际的，因为涉及的参与者数量（数据库中 Paxos 组的数量）可能有百万级别。Bigtable 支持单个数据中心内的原子模式变更，不过执行模式变更时会阻塞所有的其他操作。

Spanner 的模式变更事务基本上是标准事务的一个非阻塞式的变种。首先，它会被分配一个未来的时间戳，这个时间戳是在准备阶段生成的。因此，涉及几千台服务器的模式变更能够在尽可能少的影响到并发进行的事务的前提下完成。第二，依赖需要变更的模式的读写操作会和分配了时间戳 t 的模式变更事务保持同步：如果读写操作的时间戳小于 t，则这些操作可以继续进行；但是如果读写操作的时间戳大于 t，则需要阻塞等待模式变更事务完成。如果没有 TrueTiime，则定义模式修改发生在时间戳 t 就没有意义。

改进

上述定义的 $T_{safe}^{TM}$ 存在一个缺陷，某个已完成准备阶段的事务会阻止 $t_{safe}$ 更新（因为 $t_{safe} = min(t_{safe}^{Paxos}, t_{safe}^{TM})$ ，在4.1.3节有描述，当存在完成准备阶段的事务时， $t_{safe}^{TM} = min_i(s_{i, g}^{prepare}) - 1$ ，需要依赖各参与者所分配的准备阶段的时间戳）。因此，需要读取后面的时间戳的读操作都无法完成，即使该读操作和当前的事务没有冲突。一种解决方案是建立某个范围内的键到已完成准备阶段的事务的时间戳的映射。这部分的信息可以保存在锁表中，因为锁表本身已经保存了某个范围内的键到锁的元数据的映射。当 Spanner 收到一个读操作时，会先判断要读取的键是否存在已完成准备阶段但还未完成提交的事务，如果不存在这样的事务，则如4.1.3节所述 $t_{safe}^{TM}$ 的值为 $\infty$ ， $t_{safe}$ 的值就只取决于 $t_{safe}^{Paxos}$ 。

LastTS() 也有类似的问题：如果某个事务刚刚提交，一个无冲突的只读事务所分配的时间戳 $s_{read}$ 依然要在刚提交的事务的时间戳之后。因此，由于 $t_{safe}$ 的存在，该只读事务也有可能延迟。这个问题的解决方案也类似于 $T_{safe}^{TM}$ ，同样是建立某个范围内的键到 LastTS() 的映射（不过目前 Spanner 还未实现这个优化）。当 Spanner 收到某个只读事务时， $s_{read}$ 的值取决于读操作涉及的键所对应的 LastTS() 的最大值，除非同时还存在已完成准备阶段但还未完成提交的事务（则又回到上面一种情况）。

$t_{safe}^{Paxos}$ 的问题在于如果没有写操作，则这个值始终得不到更新。因此，如果某个期望读取时间戳 t 的快照读落在了某个最近一次写操作的时间戳小于 t 的 Paxos 组中，那么在没有新的写操作的情况下，这个快照读始终无法被执行。Spanner 通过主节点租约区间的不相交不变式（disjointness invariant）来解决这个问题。每个主节点维护了一个 Paxos 序号 n 到可能分配给下一个序号 n + 1 的最小时间戳的映射，即 MinNextTS(n)。当某个副本应用了序号 n 的指令后，则可以将 $t_{safe}^{Paxos}$ 的值更新为 MinNextTS(n) - 1，因为下一个被分配的最小时间戳为 MinNextTS(n)，减1就保证了不会超过这个值。

对于单个主节点来说可以很轻易的保证 MinNextTS() 的值的正确性（这里有一种可能的粗暴的方案，例如主节点设定10毫秒后才能提交下一个事务，如果10毫秒内来了一个事务，则直接等待到10毫秒后）。因为 MinNextTS() 的值必然落在当前主节点的租期内，又由于各个主节点租期之间的不相交不变式（disjointness invariant）的存在，使得 Spanner 能够在跨主节点时依然保证 MinNextTS() 的值的正确性（如果 MinNextTS() 的值超过了当前主节点的任期，则 MinNextTS() 的值的正确性就交由下一个主节点保证，从而转为了单主节点问题）。如果某个主节点在当前租期快过期时想要增加 MinNextTS() 的值，那么这个主节点就必须先延长租期。注意 $s_{max}$ （某个主节点使用的最大时间戳）始终会更新为 MinNextTS() 的最大值来确保不相交不变式（disjointness invariant）。

主节点默认每8秒增加一次 MinNextTS() 的值（因为如果一直没有写操作，则需要不断更新 MinNextTS() 来确保后续的读请求不会阻塞）。因此，在不存在已完成准备阶段的事务的情况下，某个空闲的 Paxos 组中健康的副本在最差情况下需要等待8秒才能返回数据给客户端。主节点可能也会根据从节点的要求来更新 MinNextTS() 的值。