译 Spanner: Google’s Globally-Distributed Database

分布式系统翻译系列的最后一篇，原文 https://research.google.com/archive/spanner-osdi2012.pdf

现在 Google Cloud 支持 Cloud Spanner 可以从产品文档上查看到其特性的一些细节。

翻译的很差，很多句子保留了英文的语序导致中文读起来很难理解，以后可能还是不要做全文翻译了。

还是语言能力太糟糕，无论英文还是中文。😢

Introduction#

Spanner 是 Google 设计，构建和部署的一个可扩展，全球分布的数据库。从最高层次的抽象来看，它是一个数据库，将数据分片到分布在全球各地数据中心的许多 Paxos 状态机中。副本用于实现全球可用性和地理上的局部性，客户端会在副本之间自动进行故障转移。随着数据量或者服务器数量的改变，Spanner 自动在机器之间重新分片。并且 Spanner 会自动在跨数据中心的机器之间迁移数据，以平衡负载和处理故障。Spanner 被设计成可以扩展到跨越数百个数据中心，数百万台机器，万亿行的数据。应用可以使用 Spanner 实现高可用性，即便在发生跨地区自然灾害的情况下，通过在同一个大陆内，甚至跨大陆复制。

我们的首个客户是 F1: 重写的 Google 广告后端。F1 使用分布在跨越全美的五个副本。大多数其他应用可能会同一个地理区域内的三到五个数据中心之间复制数据，有相对独立的故障模式。也就是说，大多数应用可能会选择低延迟而非高可用，只要在故障时能有一到两个数据中心存活。Spanner 主要关注的点是管理跨数据中心的副本数据，但是我们也花费了大量的时间设计和实现在分布式系统基础设施之上重要的数据库特性。

尽管很多项目乐于使用 Bigtable 我们也一直收到用户关于 Bigtable 很难在一些类型的应用上使用的抱怨：比如某些具有复杂且容易改变的 schemas 的应用，或者想要在多地区复制的情况下实现强一致性的应用。

Google 的许多应用选择使用 Megastore 因为它的语义化关系模型和对同步复制操作的支持，尽管他的写带宽相对很低。作为一个共识 Spanner 从类似 Bigtable 的带版本的 key-value 存储发展成一个临时多版本数据库。数据存储在有模式的半关系型的表上；数据有版本；且每个版本自动赋值成提交时的时间戳；旧数据遵循可配置的垃圾回收策略；应用可以读取旧时间戳上的数据。Spanner 支持通用事务，并且提供了一个基于 SQL 的查询语言。作为一个全球分布数据库，Spanner 支持很多有趣的特性。首先，应用可以在很细的粒度上动态控制和配置数据副本，应用可以指定一些限制来控制：哪个数据中心上包含哪些数据，数据距离用户的距离有多远 (用来控制读延迟)，每个副本间的距离有多远 (控制写延迟)，维护多少副本 (控制数据持久性，可用性和读性能)。数据可以动态且透明的在数据中心之间移动，通过系统平衡跨数据中心的资源使用。其次 Spanner 有两个难以在分布式数据库中实现的特性：它提供外部一致的读和写，并且在同一个时间戳上支持跨数据库的全球读一致性。这些特性使得 Spanner 在全球规模的级别上支持一致性备份，一致性 MapReduce 执行，和原子性的 schema 更新，即使有正在运行的事务的情况下也能保证。

这些特性之所以能够实现，基于一个事实：Spanner 可以给事务上赋值全局有意义的提交时间戳，即使事务可能是分布式的，此时间戳能够反映事务的序列化顺序。除此以外，序列化顺序适应外部一致性 (或者说等效于线性一致性)。如果一个事务 $T_{1}$ 在另一个事务 $T_{2}$ 开始之前提交，那么 $T_{1}$ 的提交时间戳比 $T_{2}$ 小。Spanner 是第一个在全球规模上提供这种保证的系统。

提供这种特性的关键支持是一个新的 TrueTime API 和它的实现。这个 API 直接反映了时钟的不确定性 Spanner 的时间戳对序列化顺序的保证依赖于 TrueTime 实现提供的范围界限 (bound 译注：时钟是不确定的，所以 TrueTime 的实现提供的是一个范围而非固定的时刻)。如果不确定性很大 Spanner 会放慢速度以消除不确定性。Google 的集群管理软件提供了 TrueTime API 的实现。这个实现通过多种现代时钟源 (GPS 和原子钟) 保证了不确定性足够小 (通常小于 10ms)。

Implementation#

这一节首先描述了 Spanner 的结构和实现的基本原理，然后描述了用于管理副本和局部性的目录抽象，它也是数据移动的基本单元，最后描述了我们的数据模型，为什么 Spanner 更像是关系型数据库而非键值存储，以及应用如何控制数据的局部性。

一个 Spanner 部署称为一个 universe 鉴于 Spanner 能够直接管理全球范围内的数据，运行的 universe 数量会很少。我们目前运行了一个 test/playground universe 一个 development/production universe 和一个 production universe. Spanner 由一组 zones 组成，每个 zone 大致类似于一组 Bigtable 服务器的部署。zones 是管理部署的基本单元。zones 的集合也是数据可以被复制的位置的集合。

随着新的数据中心投入使用和旧的数据中心关闭，可以动态的在系统中添加和移除 zone 同时 zones 也是物理隔离的单元：在一个数据中心内可能有多个 zones, 比如某些情况下同一个数据中心中不同应用的数据必须划分到的不同服务器集合上。

组织架构

上图表示一个 Spanner universe 的不同服务器。一个 zone 有一个 zonemaster 和几百到上千个 spanserver 前者将数据分配到 spanservers 后者为客户端提供数据服务。每个 zone 的 location proxies 用于客户端寻址其数据分配到的 spanservers. universe master 和 placement driver 目前都是单例的。universe master 主要是一个控制台，用于交互式调试显示所有的 zones 的状态信息。placement driver 处理分钟级别的跨 zone 的数据自动移动，placement driver 周期性的和 spanservers 通信，找到需要移动的数据，以满足更新后的复制约束或者负载均衡。篇幅所限，这里我们只详细描述 spanserver.

Spanserver Software Stack#

这一段聚焦于 spanserver 的实现来说明如何在基于 Bigtable 的实现上构建副本和分布式事务。软件栈如图：

软件栈

在底层，每个 spanserver 负责 100 到 1000 个叫做 tablet 的数据结构的实例。这里的 tablet 和 Bigtable 的 tablet 的抽象概念类似，它实现了以下映射关系的多重集合 (bag of mapping 多对一的映射)。

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

不像 Bigtable, Spanner 会直接给数据赋值时间戳，这是 Spanner 更像是数据库而非 key-value 存储的一个重要体现。每个 tablet 的状态存储在一组类似 B-tree 的文件和一个 write-ahead 日志中 (WAL)，这些文件全都存放在一个叫做 Colossus 的分布式文件系统中 (GFS 的后继者)。为了支持复制，每个 spanserver 在每个 tablet 之上实现了一个单独的 Paxos 状态机 (早期版本的 Spanner 支持每个 tablet 多 Paxos 状态机，允许更灵活的复制配置，但是这个设计的复杂度让我们放弃了)。每个状态机存储其元数据和负责的 tablet 的日志。我们的 Paxos 实现支持基于时间租约机制的 long-lived Leader, 默认租约时间 10 秒。目前的 Spanner 实现对每个 Paxos 写记录两次日志：一次在 tablet 的日志中，一次在 Paxos 的日志中。这个选择是出于便利考虑，并且最终可能会进行改善。我们实现的 Paxos 是流水线化的，以改善 Spanner 在 WAN 延迟情况下的吞吐量；但是写操作是 Paxos 顺序执行的。

Paxos 状态机用于实现一致性复制的映射关系多重集合 (consistently replicated bag of mappings)。每个副本的键值映射状态在对应的 tablet 中存储。写操作必须在 Leader 发起 Paxos 协议；读操作直接访问任何一个足够新的副本的底层 tablet 的状态。

一组副本的集合组成一个 Paxos 组，在每个 leader 副本上每个 spanserver 实现了一个 lock table 以实现并发控制。这个 lock table 包含了两阶段锁的状态：映射键的范围到锁状态 $K_{0..n} \Rightarrow lock$ (有一个 long-lived Paxos leader 是高效管理 lock table 的关键)。在 Bigtable 和 Spanner 我们都设计了 long-lived 事务 (比如报表生成，耗时可能在分钟级)，在产生冲突的场景下，乐观并发控制访问性能很差。需要同步的操作，比如事务读操作需要先获取到 lock table 的锁，其他操作则可以跳过 lock table 锁。

在每个副本 leader 上每个 spanserver 也实现了一个事务管理器以支持分布式事务。这个事务管理器用于实现参与领导者；同一组的其他副本会成为参与从节点。如果一个事务仅涉及一个 Paxos 组 (大多数事务)，可以不通过事务管理器，因为 lock table 和 Paxos 一起提供事务支持就足够了。如果一个事务涉及超过一个 Paxos 组，这些组的 leader 会协调执行两阶段提交。执行事务时会从涉及到的所有组中选取一个组作为协调员 (coordinator)，这个被选定的组内的 leader 会被称为协调领导者 (coordinator leader) 该组的从节点被称为协调者从节点。每个事务管理器的状态在底层 Paxos 组上存储 (因此是被复制的)。

Directories and Placement#

Spanner 的实现在键值映射多重集合之上支持一个称为 directory 的 bucket 抽象，即一组有相同前缀的连续键 (选择使用术语 directory 是一个历史遗留问题，更好的叫法可能是 bucket) 支持 directories 使得应用可以通过小心的选择键来控制他们的数据的局部性。一个 directory 是数据放置的单元，同一个 directory 下的所有数据有相同的副本配置。他们以 directory 为单位在 Paxos 组之间移动。如下图：

directory 移动

Spanner 可能会从一个 Paxos 组中移出一个 directory 以降低负载；将经常一起访问的 directories 放到相同的组；或者将一个 directory 移动到离它的访问者更近的组。directory 可以在客户端证正在进行操作时移动。一个 50MB 的 directory 可以在大约几秒钟内移动。

一个 Paxos 可能包含有多个 directories 这是 Spanner 的 tablet 和 Bigtable 的 tablet 不同之处：前者不一定是单个行空间按字典序连续的分区。相反，一个 Spanner tablet 是一个容器，可以封装行空间的多个分区。我们做出这个决定，使得多个被经常一起访问的分区共存成为可能。

Movedir 是一个后台任务用于在 Paxos 组之间移动 directories, Movedir 也用于在 Paxos 组中添加和移除副本，因为 Spanner 目前不支持基于 Paxos 的配置修改。Movedir 没有作为单个事务实现，以避免阻塞大量数据移动期间的正在进行的读写操作。相反 movedir 只是记录下它开始在后台移动数据，当它基本移动了全部数据，它使用一个事务自动移动剩下很少的数据然后更新两个 Paxos 组的元数据。

一个 directory 同时也是应用可以指定地理复制属性 (或放置策略) 的最小单元。我们的 placement-specification 语言将管理副本配置的责任分开。管理员控制两个维度：副本的数量和类型，和这些副本放置的地址位置。在这两个维度上创建了一个命名选项的菜单 (比如：北美，采用五副本加上一个见证副本)(译注：见证副本一般用于参与 Leader 选举投票，仲裁冲突，防止 brain split 等，参考 Cloud 文档) 应用通过这些选项的组合给每个数据库和 (或) 各个 directories 加上标签，来控制数据如何被复制。比如，一个应用可能将每个终端用户的数据存在他自己的目录中，可以使得用户 A 的数据在欧洲有三个副本，用户 B 的数据在北美有五个副本。

为了简化说明，我们做了过度的简化。事实上如果 directory 过大 Spanner 会将其分片成多个 fragments 然后 fragments 可能在不同的 Paxos 组上 (因此也就是不同的服务器上) 提供服务。Movedir 实际上是在组之间移动 fragments 而非整个 directories.

Data Model#

Spanner 给应用暴露了以下一些数据特性：一个基于有模式的半关系型表的数据模型，查询语言，和通用事务。朝着支持这些功能转变是由多种因素驱动的。

支持有模式的半关系型表和同步复制的需求是 Megastore 的流行所推动的。Google 至少有 300 个应用使用 Megastore (尽管它的性能相对较低) 因为它的数据模型比 Bigtable 管理起来更简单，并且支持跨数据中心的同步复制 (Bigtable 仅支持跨数据中心的最终一致性复制)。比较知名的使用 Megastore 的应用有 Gmail, Picasa, Calendar, Android Market, and AppEngine 等。鉴于 Dremel 作为一个交互式数据分析工具的流行度，在 Spanner 中支持类 SQL 查询语言的需求也非常明了。

最后 Bigtable 中缺失的跨行事务也经常招致抱怨 (led to frequent complaints); 构建 Percolator 的部分原因就是解决这个问题。一些作者认为支持通用的两阶段提交太过昂贵，因为其带来了性能或者可用性问题。我们认为最好让应用程序员在滥用事务导致出现性能瓶颈时处理性能问题，而不是在缺失事务的情况下编程。通过 Paxos 运行两阶段提交减轻可用性问题。

应用的数据模型构建在以目录为桶的键值映射之上。一个应用可以在一个 universe 上创建一个或多个数据库。每个数据库可以包含无限制数量的结构化表。表类似于关系型数据表，包含行，列和版本化的值。我们不会深入 Spanner 的查询语言的细节。它看起来像是 SQL 并进行了一些扩展以支持 protocol-buffer 值字段。

Spanner 的数据模型不是纯关系型的，因为每个行必须具有名称。更准确的说，每个表需要有一个或多个有序的主键列的集合。这个要求使得 Spanner 看起来仍像是一个键值存储：主键组成行的名称，每个表定义了一个主键列到非主键列的映射。一个行只有在为主键定义了值 (即使是 NULL) 时才存在。强制使用这种结构是有用的，因为这让应用可以通过选择键来控制数据的局部性。

spanner-figure4

上图包含一个 Spanner 示例结构：在每个用户，每个相册的基础上排序照片元数据。这种 schema 定义语言和 Megastore 类似，但是增加了额外的需求：每个 Spanner 数据库必须被客户端按照一个或多个层级结构对表进行分区。

客户端应用在数据库 schemas 中通过 INTERLEAVE IN 声明层级结构。层级结构最上层的表是一个 directory 表。在 directory 表中以键 K 为起始的，按照字典序排列的之后的所有以 K 开头的所有行，组成一个 directory.

ON DELETE CASCADE 表示删除 directory 表的一个行时删除所有相关子行。上图也显示了 example 数据库的交错布局：比如 Albums (2,1) 表示 Albums 表中从 user_id == 2 && album_id == 1 开始的行。这种表交错构成 directory 非常重要，因为这允许客户端在描述多个表之间的局部性关系，对于在分片的分布式数据库中取得良好的性能是必要的。没有这个功能 Spanner 无法知道最重要的局部性关系。

TrueTime#

这一段描述 TrueTime API 和实现的大概 (sketches)。我们将大部分的细节留在了另外一篇论文，这一段的目标是为了证明有这样一个 API 带给我们的力量。

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

上表列出了 API 的方法 TrueTime 显式的将时间表示为 $TTinterval$ 一个具有有界时间不确定性的时间间隔 (不像标准库时间接口不过告诉客户端不确定性的概念)。 $TTinterval$ 的节点的类型是 $TTstamp$ , $TT.now()$ 方法返回一个 $TTinterval$ 范围，它保证包含调用 $TT.now()$ 时的绝对时间。time epoch 类似于有闰秒模糊处理的 UNIX 时间。定义瞬时误差界限为 $\varepsilon$ 也就是时间区间宽度的一半，平均误差为 $\bar{\varepsilon}$ 其中 $TT.after()$ 和 $TT.before()$ 方法是对 $TT.now()$ 的简易封装。

用函数 $t_{abs}(e)$ 表示事件 $e$ 发生的绝对时间。更正式的说 TrueTime 保证：对于任意一个调用 (invocation) $tt = TT.now(), tt.earliest \le t_{abs}(e_{now}) \le tt.latest$ 其中 $e_{now}$ 是调用 (invocation) 事件。

TrueTime 底层时间参考的是 GPS 和原子钟。TrueTime 使用两种形式的时间参考是因为他们有不同的故障模式。GPS 参考源的漏洞包括天线和接收器故障，本地无线电干扰，相关故障 (涉及缺陷，比如错误的闰秒处理和欺骗)，以及 GPS 系统中断。原子钟可能会以与 GPS 和其他原子钟无关的方式产生故障，随着时间的推移，由于频率误差会出现明显的漂移。

TrueTime 是由每个数据中心的一组 time master 机器和每台机器上的 timeslave 进程实现的。大多数的 master 有配备有专用天线的 GPS 接收器；这些 master 在物理上隔离以减天线故障，无线电干扰和欺骗的影响。剩下的 master (我们称之为 Armageddon 世界末日 master) 装备有原子钟。一个原子钟没那么贵：一个 Armageddon master 的成本和一个 GPS master 的成本相当。

所有 master 时间参考会定期相互比较，每个 master 也会将参考时间的推进速率与自己本地的时钟进行交叉检查，并且在有显著的偏差时将自己退出。在两次同步之间 Armageddon master 会宣告一种缓慢增加的时间误差 (time uncertainty)，这个误差根据时钟漂移最坏的情况下保守估算出来的。GPS master 宣告的误差一般接近于零。

每个守护进程会轮询多个 master 以减少依赖任何一个 master 节点产生错误的脆弱性。一些是从数据中心附近选择的 GPS master; 剩下的 GPS maste 来自较远的数据中心；当然还有一些 Armageddon master. 守护进程使用一种 Marzullo 算法变种来检测和拒绝虚假信息，并将本地机器时钟和非虚假信息 (nonliars) 进行同步。为了防止本地时钟故障，频率偏移超过对应组件标准和操作环境下最坏情况误差界限的机器会被剔除。

在两次同步之间，守护进程宣告一个缓慢的增加的时间误差。e 表示保守估计最坏情况下本地时钟漂移 e 也依赖于 time-master 的误差和与 time-master 的通信延迟。在我们的生产环境中 e 通常是一个关于时间的锯齿函数。在每个轮询间隔内会有 1ms 到 7ms 的变化，因此 e 大多数时间是 4ms 守护进程的轮询间隔目前是 30s 当前使用的漂移率被设置为 200 microseconds/second 加起来共同导致了 0 到 6ms 的锯齿变化范围，剩下的 1ms 来自于到 time master 的通信延迟。在出现故障情况下，这种锯齿会出现偏移，比如偶现的 time-master 不可用会导致 e 在数据中心范围上增加。类似的，机器和网络连接过载也会导致偶尔局部的尖刺 (spike 突发峰值)。

Concurrency Control#

这一段描述如何使用 TrueTime 在并发控制中保证正确性，以及如何使用这些性质来实现类似于外部一致性事务，只读无锁事务，历史非阻塞读之类的特性。这些特性能够使得，比如：在时间戳 $t$ 时整个数据库的审计读取会读取到在 $t$ 之前提交的所有事务产生的效果。

区分 Paxos 看到的写入 (后续称为 Paxos 写) 和 Spanner 客户端写入很重要。比如两阶段提交在 prepare 阶段产生了一个 Paxos 写但是没有对应的 Spanner 客户端写。

Timestamp Management#

Operation	Concurrency Control	Replica Required
Read-Write Transaction	pessimistic	leader
Read-Only Transaction	lock-free	leader for timestamp; any for read
Snapshot Read, client-provided timestamp	lock-free	any
Snapshot Read, client-provided bound	lock-free	any

上表列出了 Spanner 支持的操作类型。Spanner 的实现支持读写事务，只读事务 (预声明快照隔离事务)，和快照读。独立写作为读写事务实现；非快照独立读作为只读事务实现，两者都有内部重试 (不需要客户端显式循环重试)。

只读事务是一种有快照隔离性能优势的事务。一个只读事务必须提前声明不包含任何写入，它不仅仅是一个没有任何写操作的读写事务。在只读事务中，读操作在系统选择的时间戳上无锁执行，所以不会阻塞后续的写操作。只读事务中的读操作可以在任何足够新的副本上执行。

快照读是对过去的读取，执行时也不加锁。一个客户端可以指定快照读的时间戳，或者提供一个期望时间戳的过期上限 (bound on the desired timestamp’s staleness) 然后让 Spanner 选择一个时间戳。在任何一种情况下，快照读都会在足够新的副本上执行。

对于只读事务和快照读，一旦选择了一个时间戳，提交时不可避免的，除非这个时间戳的数据已经被垃圾回收了。最终，客户端可以避免在重试循环缓冲结果。当一个服务故障，客户端内部会向另外一个服务器提供时间戳和当前读取位置继续查询。

Paxos Leader Leases#

Spanner 的 Paxos 实现使用了基于时间的租约来保证 long-live-leader (默认 10s)。一个潜在的 leader 发送基于时间的租约投票请求；收到足够 quorum 的票数后他可以认为自己获得了租约。一个副本在成功写入后显式的延长租约投票，并且 leader 会在租约临近过期时会请求租约续期投票。

定义一个 leader 的租约间隔：从他发现自己收到足够 quorum 的租约投票开始，到他不再有足够 quorum 的租约投票时结束 (因为某些投票过期了)。

Spanner 依赖以下不相交性不变量 (disjointness invariant)：对于每个 Paxos 组，每个 Paxos 的 leader 和其他每个 leader 的租约间隔不重叠 (附录 A 描述了如何维持这种不变量)。

Spanner 的实现允许一个 Paxos leader 通过释放他的租约投票的 slave 来放弃 leader 地位。为了保持不相交性不变量 Spanner 限制何时允许弃权。定义 $s_{max}$ 为 leader 使用的最大时间戳，后续的段落会描述何时 $s_{max} {\huge }$ 会被提前，在弃权之前，leader 必须保证 $TT.after(s_{max})$ 为 true.

Assigning Timestamps to RW Transactions#

事务读和写使用两阶段锁，最终，他们可以在 [获得所有锁后，释放任何锁之前] 的任何时间被赋值时间戳。对于一个给定的事务 Spanner 将其时间戳赋值成 Paxos 赋值给表示事务提交的 Paxos 写入的时间戳。

Spanner 依赖以下单调不变性：在每个 Paxos 组中 Spanner 以单调递增的顺序给 Paxos 写赋值时间戳，即使是跨 leader (译注：leader 变成其他节点了)。一个单独的 leader 副本可以很容易的按照单调递增的顺序赋值时间戳。通过利用不相交不变性，可以在各个 leader 之间维持这种不变性：一个 leader 仅能在其 leader 租约间隔内赋值时间戳。

注意无论合适赋值了一个时间戳 $s$ 则 $s_{max}$ 一定比 $s$ 大以维持不相交。Spanner 也强制如下的外部一致性不变量：如果事务 $T2$ 的开始发生在事务 $T1$ 的提交之后，则 $T2$ 的提交时间一定比 $T1$ 的提交时间大。

定义对于事务 $T_{i}$ 的开始和提交时间为 $e_{i}^{start}$ 和 $e_{i}^{commit}$ 提交时间戳为 $s_{i}$ , 则不变性变成了：

$t_{abs}(e_{1}^{commit}) < t_{abs}(e_{2}^{start}) \Rightarrow s_{1} < s{2}$

执行事务和分配时间戳的协议遵守两条规则，共同保证了不可变性，如下所示。定义写事务 $T_{i}$ 提交请求到达协调 leader 的事件为 $e_{i}^{server}$

Start: 协调 leader 给写事务 $T_{i}$ 分配一个时间戳 $s_{i}$ 这里 $s_{i}$ 不小于在 $e_{i}^{server}$ 计算过后的 $TT.now().latest$ 注意参与者 leader 在这里不重要，后续会描述它们如何参与第二条规则的实现
Commit Wait: 协调 leader 确保在 $TT.after(s_{i})$ 为 true 之前客户端不可能看到任何 $T_{i}$ 提交的数据。提交等待确保 $s_{i}$ 小于 $T_{i}$ 提交的绝对时间，即 $s_{i} < t_{abs}(e_{i}^{commit})$ 提交等待的实现在后续会介绍，证明：

Proof

Serving Reads at a Timestamp#

前面描述过的单调不变性允许 Spanner 正确的决定一个副本的状态是否足够新来满足一个读请求。每个副本跟踪一个叫做安全时间 $t_{safe}$ 的值，即此副本更新到的最大时间戳。如果请求时间戳 $t \le t_{safe}$ 则副本可以满足一个读请求。

定义 $t_{safe} = min(t_{Paxos}^{safe}, t_{TM}^{safe})$ 其中每个 Paxos 状态机有一个安全时间 $t_{Paxos}^{safe}$ 每个事务管理器有一个安全时间 $t_{TM}^{safe}$ 其中 $t_{Paxos}^{safe}$ 很简单：它是已经 apply 过的 Paxos 写操作的最大时间戳。由于时间戳单调递增且写操作顺序 apply, 就 Paxos 而言，在 $t_{Paxos}^{safe}$ 或者之后的时间上上不存在写操作。其 $t_{TM}^{safe}$ 使用的是其副本的 leader 的事务管理器的状态，这个状态通过 Paxos 写入过程中的元数据。

如果副本上没有 "准备好但是还没有提交 prepared but not commited" 的事务：即处于两阶段提交的的两个步骤中间的事务，则副本上的 $t_{TM}^{safe}$ 为 $\infty$ (对于一个参与者 slave 服务器来说 $t_{TM}^{safe}$ 实际上使用的是其副本 leader 的事务管理器的状态，这个状态可以通过 Paxos 写操作传递的元数据来推断)。如果存在这样的事务，这些事务对状态的影响是不确定的：参与者副本还不知道这个事务是否会提交。如之前所描述过的，提交协议确保每个参与者知道一个 prepared 事务的时间戳下限。对于一个组 g 每个参与者 leader 给事务的 prepare 记录分配一个 prepare 时间戳 $s_{i,g}^{prepare}$ 协调 leader 确保在组 g 内的所有参与者上，事务的提交时间 $s_{i} \ge s_{i,g}^{prepare}$ 因此 g 中的任何副本，对于在 g 上 prepare 的所有事务 $T_{i}$ 有 $t_{TM}^{safe} = min_{i}(s_{i,g}^{prepare}) - 1$

Assigning Timestamps to RO Transactions#

一个只读事务的执行分为两个阶段：分配一个时间戳 $s_{read}$ 然后在 $s_{read}$ 将事务读作为快照读执行。快照读可以在任何足够新的副本上执行。s_read 可以在事务开始后的任何时间赋值为 $s_{read} = TT.now().latest$ 通过类似之前讨论写的情况一样提供外部一致性。然而，如果 $t_{safe}$ 还没有足够新 (advanced sufficiently)(译注：即比 $s_{read}$ 小) 则数据读取操作需要阻塞在 $s_{read}$ (此外，选择一个自定义的 $s_{read}$ 值可能会提升 $s_{max}$ 以保持不相交性 disjointness)。为了减少阻塞的机会，Spanner 应该分配最老的时间戳来保护外部一致性。4.2.2 解释了如何选择这样一个时间戳。

Details#

这一段解释了之前忽略的读写事务和只读事务的一些实践细节，和一种用于实现原子性 schema 变更的特殊事务的实现。然后描述了一些之前描述的基本方案的改进。

Read-Write Transaction#

和 Bigtable 相似，事务中的写操作会在客户端中缓存直到提交。最终，事务中的读操作不会看到事务中写操作的效果。这种设计在 Spanner 中工作的不错，因为一个读操作返回任何读取到的数据的时间戳，而未提交写还没有被分配时间戳。

读写事务中的读操作使用 woundwait 来避免死锁。客户端向对应 group 的副本 leader 发起读操作请求，申请一个读锁然后读取最近的数据。如果一个客户端事务保持打开，它会发送一个 keepalive 消息以避免参与者 leader 将其事务超时。当一个客户端完成了所有的读操作，缓存了所有写操作，就开始两阶段提交。客户端选择一个协调组并且向每个参与者 leader 发送 commit 消息：包括协调者标识和所有的写操作。使用客户端驱动两阶段提可以交避免跨区域传输数据两次。

一个非协调员参与者 (non-coordinator-participant) leader 首先申请一个写锁，然后选择一个必须大于它给之事务分配的所有时间戳的 prepare 时间戳 (保证单调性)，然后通过 Paxos 添加一条 prepare 记录日志。每个参与者将其 prepare 时间戳通知给协调员。

协调员 leader 首先也要申请一个写锁，但是跳过 prepare 阶段。在收到所有其他参与 leader 的消息后，它给整个事务选择一个时间戳。提交时间戳 $s$ 必须大于等于所有的 prepare 时间戳 (满足一致性)，大于协调者在收到其 commit 消息时的 $TT.now().latest$ , 大于 leader 已经给之前事务分配过的所有时间戳 (再一次，保证单调性)。然后协调 leader 通过 Paxos 记录提交日志 (或者中断，如果在等待其他参与者时超时)。

在允许任何协调者副本应用提交记录之前，协调 leader 等到 $TT.after(s)$ 为 true 来遵守 4.1.2 中描述的 commit-wait 规则。由于协调 leader 根据 $TT.now().latest$ 来选择提交时间戳 s 并且现在等待直到这个时间戳在过去 (译注：要等到当前的绝对时间一定大于 s)，所以预期的等待时间是 $2 * \bar{\varepsilon}$ (译注: Section 3 提到的平均误差时间)。这个等待时间通常和与 Paxos 的通信时间重叠。在提交等待之后，协调者将提交时间戳发送到客户端和所有其他参与 leader, 每个参与 leader 通过 Paxos 记录事务的结果。所有参与者应用相同的时间戳，然后释放锁。

Read-Only Transactions#

赋值一个时间戳需要在读操作涉及到的所有的 Paxos 组之间有一个沟通阶段 (negotiation phase) 最终，Spanner 需要每个只读事务都有一个 scope 表达式，这个表达式概括了整个事务要读取的键的集合。Spanner 会为单个请求自动推导这个 scope. 如果 scope 的值可以通过单个 Paxos 组提供，则客户端可以向这个组的 leader 发起只读事务请求 (目前的 Spanner 实现只在 Paxos leader 上给只读事务选择一个时间戳)。这个 leader 分配 $s_{read}$ 时间戳，然后执行读操作。对于单点读取，Spanner 有一个比直接调用 $TT.now().latest$ 更好的分配时间戳的方法。定义 $LastTS()$ 为 Paxos 组上最后一次写提交的时间戳。如果没有 prepare 事务，则直接赋值 $s_{read} = LastTS()$ 轻松满足外部一致性：事务将会看到最后一次写入的结果，并且因此排在它之后。

如果 scope 的值需要多个 Paxos 组提供，会有多种选择。最复杂的选择是跟所有的组 leader 进行一轮通信并基于 $LastTS()$ 协商选择 $s_{read}$ . Spanner 目前实现了一种简单的方式，避免客户端进行一整轮沟通，仅仅是将其读取执行时间设置为 $s_{read} = TT.now().latest$ (可能需要等到安全时间赶上，译注：是说这个时间可能会超过安全时间)。事务中的所有读取都可以被发送到足够新的副本。

Schema-Change Transactions#

TrueTime 使得 Spanner 支持原子性 schema 修改。使用一个标准的事务是不可行的，因为参与者的数量 (数据库中的组数量) 的数据可能有数百万。Bigtable 支持在一个数据中心中的原子性 schema 修改，但是它的 schema 修改会阻塞所有操作。而 Spanner 的 schema-change 事务通常是一个非阻塞标准事务的变体 (variant)。

首先，它显式分配一个未来的时间戳，注册在 prepare 阶段，最终跨越数千台服务器的 schema 修改可以在对其他并行活动产生非常小的中断的情况下完成。其次，读写操作，显式依赖 schema.

其次，任何隐式依赖模式的读写操作，在时间 $t$ 时与任何注册过的 schema-change 同步：如果它们的时间戳在 $t$ 之前，可能会执行，否则它们必须阻塞到 schemachange 事务之后 (译注：因为此事务时间比 $t$ 大，所以一定要等 schemachange 事务先执行完保证提交等待)。没有 TrueTime (这样一个稳定且全局一致的时间 API) 定义 schemachange 在时间 $t$ 发生没有意义。

上面我们定义的 $t_{safe}^{TM}$ 有一个弱点，即一个 prepared 事务可以阻止了 $t_{safe}$ 前进。最终，在后续的时间戳中不能执行任何读操作，即使读操作跟事务没有任何冲突。这种错误的冲突可以通过增加一个细粒度的，从键范围到 prepare 事务时间戳的映射来移除。这个信息可以存储在 lock 表中，这个表已经将键范围映射到 lock 元数据。当一个读操作到达，它只需要检查其冲突的键范围对应的细粒度安全时间。

之前定义的 $LastTS()$ 有一个类似的弱点：如果一个事务刚刚提交，一个没有冲突的只读事务必须将 $s_{read}$ 赋值成这个事务的时间戳。最终，读操作可能会被延迟 (译注：这个事务刚提交，可能还没有在所有参与者上同步，在某个副本上读的时候可能需要等待)。这个弱点同样可以通过类似的在 lock 表中给 $LastTS()$ 添加一个细粒度的从键范围到提交时间戳的映射来补救 (我们目前还没有实现这个优化)。当一个只读事务到达，它的时间戳可以被赋值为具有键范围冲突的 $LastTS()$ 的最大值，除非当前有一个冲突的 prepare 事务 (可以通过细粒度的安全时间来确定)。

之前定义的 $t_{safe}^{Paxos}$ 有一个弱点是在没有 Paxos 写操作时无法增加 (译注: $t_{safe}^{Paxos}$ 用的是最后的写操作时间戳)。即一个在 $t$ 的快照读不能在最后的写操作在 $t$ 之前的 Paxos 组上执行。Spanner 利用 leader-lease 间隔的不相交性来解决这个问题。每个 Paxos leader 通过维护一个阈值，并且使未来的写操作时间戳一定高于这个阈值来推进 $t_{safe}^{Paxos}$ 增长：它维护一个从 Paxos 序列号 n 到可能分配给未来的 Paxos 序列号 n+1 的最小时间戳的映射 $MinNextTS(n)$ 副本在已经应用了第 n 序列号后可以将自己的 $t_{safe}^{Paxos}$ 推进到 $MinNextTS(n)−1$

单个 leader 可以轻松的执行 $MinNextTS()$ 承诺，因为 $MinNextTS()$ 许诺的时间戳在 leader 的租约内，不相交不变性 (译注：每个 leader 的租约时间不会重叠) 使得可以在 leader 之间执行 $MinNextTS()$ 承诺。如果一个 leader 想要将 $MinNextTS()$ 推进到超出其 leader-lease 必须将其租约续期。注意 $s_{max}$ 总是超过 $MinNextTS()$ 中的最大值以保证不相交性。

leader 默认每 8s 推进一次 $MinNextTS()$ 值，因此在缺失 prepared 事务的情况下，一个空闲的 Paxos 组中的健康的 slave 在最糟糕的情况下，可以为大于最旧时间戳 8s 的时间戳提供读服务。leader 也可以根据 slave 的需求提升 $MinNextTS()$ 值的时间。

Evaluation#

省略...

(译注：这一部分大多是和其他一些数据库的比较，在原论文中可以找到引用链接)

Megastore 和 DynamoDB 已经提供了跨数据中心一致性赋值的存储服务。DynamoDB 提供了一个 key-value 接口，并且仅在一个 region 内复制。Spanner 遵循 Megastore 的方式提供了半关系型数据模型和相似的 schema 语言。Megastore 没有达到高性能。它构建在 Bigtable 之上，因此带来了很高的通信开销。它也不支持 long-lived leaders: 多个副本可能发起写操作。在 Paxos 协议中，不同的副本上写操作会产生冲突，即使它们并没有逻辑上的冲突：每秒钟数次的写会使得 Paxos 组的吞吐量崩溃。Spanner 提供了高性能通用事务和外部一致性。

在复制存储之上添加事务的想法最远可以追溯到 Gifford 的博士论文。Scatter 是一个最近的基于 DHT 的 key-value 存储，它在一致性复制上添加了事务层。Spanner 专注于提供比 Scatter 更高层级的接口。Gray 和 Lamport 描述了一个基于 Paxos 的非阻塞提交协议。他们的协议导致了比两阶段提交更高的消息消耗 (messaging costs)，会加重大范围分布式组的提交的成本。Walter 提供了一个快照隔离的变体，适用于数据中心内部，但是不能跨数据中心。相比之下，我们的只读事务提供了更自然的语义，因为我们对所有操作提供外部一致性。

最近有大量工作致力于减少或者消除锁开销。Calvin 消除了并发控制：它预先分配时间戳，并且按照时间戳顺序执行所有事务。HStore 和 Granola 各自支持自己的类型分类，其中一些可以避免锁。这些系统中没有一个支持外部一致性。Spanner 通过提供快照隔离解决竞争问题。

VoltDB 是一个内存分片数据，支持异地主从复制，用于灾难恢复，但不支持更加通用的复制配置。这是 NewSQL 的一个例子，也是市场推动支持可扩展 SQL 的举措。

许多数据库实现了过去时读取的功能，比如 MarkLogic 和 Oracle 的 Total Recall, Lomet 和 Li 描述了这种时态数据库的一种实现策略。

Farsite 相对于可信时钟源派生了时钟不确定性 (比 TrueTime 宽松)：Farsite 中服务器租约的维护方式和 Spanner 中 Paxos 维护租约的方式相同。过去的工作曾使用松弛同步时钟进行并发控制，我们已经展示了 TrueTime 可以让人对跨 Paxos 状态机集群的全局时间进行推理。

Future Work#

去年我们花费了大部分的时间和 F1 组一起将 Google 的广告后端从 MySQL 迁移到 Spanner. 我们正在积极改善监控和支持工具，也优化了它的性能。此外，我们也改善备份和恢复系统的功能和性能。我们目前正在实现 Spanner schema language, 自动化辅佐索引的维护，和基于负载的自动化重新分片。长远来看，我们计划研究很多新特性。乐观并行读取可能是一个比较有价值的策略，但是初步的实验表明正确的实现可能并不简单。此外，我们计划最终支持直接修改 Paxos 配置的。

考虑到我们预期许多应用会在非常相近的数据中心复制他们的数据，TrueTime $\varepsilon$ 可能会显著的影响性能。我们没有看到将 $\varepsilon$ 降低到 1ms 有什么不可逾越的障碍。Time-master-query (译注：向 time-master 请求校准时间) 间隔可以减少，更好的石英钟也相对便宜。Time-master-query 延迟可以通过改善网络拓扑来改善，甚至可能通过替代的 time-distribution 技术来避免。

最终，有很多明显的地方可以改善。尽管 Spanner 可以在节点数量上进行扩展，但是 node-local 数据结构对复杂 SQL 查询的性能相对较差，因为他们是为简单的 key-value 访问而设计的。来自数据库文献的算法和数据结构可以极大的改善单节点的性能。其次，根据客户端负载在数据中心之间自动移动数据一直是我们的一个目标，但是为了高效实现这个目标，我们仍然需要自动化，协调式的在数据中心之间迁移客户端应用进程的能力。迁移进程带来了在数据中心之间管理资源申请和分配这个更加严峻的问题。

Conclusions#

总之 Spanner 结合并扩展来自两个社区的研究：从数据库社区获得了熟悉的，易用的半关系型接口，事务和基于 SQL 的查询语言；从系统社区获取了可扩展性，自动分片，错误容忍，一致性复制，外部一致性和广域分布。

从 Spanner 启动开始，我们花费了超过 5 年的时间迭代到当前的设计和实现。如此长迭代的部分原因是我们逐渐意识到 Spanner 不应该只是解决全局复制命名空间的问题，也应该专注于 Bigtable 缺失的数据库特性。

我们设计的表明：实现 Spanner 各种 feature 的关键因素是 TrueTime. 我们已经展示了，在时间 API 中具象化时钟不确定性，会使得构建的分布式系统有更健壮的时间语义。此外，随着底层系统对时钟不确定性执行更强的约束，实现较强语义的开销也会减小。作为一个社区，在设计分布式算法时，我们不应该再依赖松散同步的时钟和弱时间 API.