Spanner: Google’s Globally-Distributed Database——MIT6-824

Spanner: Google’s Globally-Distributed Database

Spanner是谷歌提出的一个可扩展、多版本、全球分布和支持同步复制的数据库。这是第一个在全球范围内分发数据并支持外部一致性的分布式系统

Introduction

Spanner作为一个数据库，它由遍布全球的数据中心的许多Paxos状态机进行数据分片。Spanner会随着数据量或者服务器数量的变化自动在计算机之间重新分片数据，并自动在计算机之间迁移数据。应用程序可以通过跨大洲复制数据的方式来使用Spanner实现高可用性。

Spanner的主要重心在于管理跨数据中心的复制数据，但也花了不少时间在分布式系统架构上设计和实现重要的数据库功能。

作为全球分布的数据库，Spanner提供了一些有趣的功能。应用程序可以细粒度动态地控制数据的复制配置，支持在数据中心透明地移动数据，平衡资源使用，也对外提供外部一致的读写等等。

Spanner会为事务分配具有全局意义的提交时间戳，这里关键因素是新的TrueTime API及其实现。下面会重点介绍。

Implementation

本章主要介绍Spanner实现的基础架构和原理。然后描述了目录抽象，最后则是描述了数据模型。

一个Spanner的部署被称为Universe，Spanner则被组织为一组区域，这是管理部署的单位和物理隔离的单位。下图描述了Spanner Universe的服务器，一个区域具有一个zone master和若干个spanserver，通过location proxy来定位提供服务的spannerver。universe master 和 placement driver则是一个单例，前者主要是一个控制台，后者则是定期与spanserver通信，以找出需要移动的数据。

Spanserver Software Stack

这一章主要讲spanserver的实现，软件架构如图所示，底部为每个spanserver负责的100-1000个称为tablet的数据结构，它实现了一组以下的的映射：

(key:string, timestamp:int64) → string

tablet的状态存储在一个类似B树的文件和一个预写日志中，所有这些都存在一个叫Colossus的组件里。

为了支持复制，Spanserver都在每个tablet的顶部实现了Paxos状态机，用来存储其元数据和tablet的日志。这里的Paxos实现通过基于时间的leader租约来支持生命周期长的leader。Spanner的实现中会写两次Paxos日志，一次在tablet中，一次在Paxos日志里。

在leader副本中，Spanserver会实现一个锁表来做并发控制，这包含了两阶段锁的状态，能将key的范围映射到锁的状态。需要同步的操作（例如事务性读取）会在锁表中获取锁；其余操作绕过锁表。

另外，在leader副本中，spansever还实现了一个事务管理器来支持分布式事务。如果一个事物仅仅涉及到一个Paxos组，则可以绕过事务管理器。否则这些组的leader会协调执行两阶段提交。

Directories and Placement

在一系列键值映射的上层，Spanner 实现支持一个被称为“目录”的桶抽象，为包含公共前缀的连续键的集合。一个目录是数据放置的基本单位，同一个目录下的所有数据具有相同的副本配置。当数据在不同的paxos组间移动时，会进行逐个目录的移动。如下图所示：

一个Paxos组包含了若干个目录，tablet不一定是一个行空间内按照字典顺序排序的分区，可以是行空间内的多个分区。Movedir 是一个后台任务，用来在不同的 Paxos 组之间转移目录，也可以用来为Paxos组增加或删除副本。

一个目录也是应用可以指定的放置策略的最小单元，一个应用就可以控制数据的复制。例如，一个应用可能会在自己的目录里存储每个终端用户的数据，这就有可能使得用户 A 的数据在欧洲有三个副本，用户 B 的数据在北美有 5 个副本。

当一个目录变得太大时，Spanner会进行分片存储。每个分片可能被保存到不同的Paxos组。Movedir在不同组之间不再是转移目录，而是转移分片。

Data Model

Spanner暴露给应用的数据特性包括了：基于模式化的半关系表数据模型，SQL类型的查询语言和通用事务。

应用的数据模型是在被目录桶装的键值层之上，一个应用会在一个universe中创建若干个数据库，每个数据库可以包含无限的模式化表。每个表都和关系数据库表类似，具备行、列和版本值。

TrueTime

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

本章主要讲TrueTime API，但更多的内容在另一篇论文里。上面的表列出了API的方法，TrueTime是一款高度可用的分布式时钟，面向所有Google服务器上的应用提供，会把时间表达成一个时间区间TTinterval，具有一个有限的时间不确定性。TT.now()方法会返回一个 TTinterval，它可以保证包含调用TT.now()方法时的绝对时间。

在底层，TrueTime使用的时间是基于GPS和原子钟实现的，这两种类型的时间具有不同的失败模式。GPS的弱点是天线和接收器失效、局部电磁干扰等等。而由于频率误差，在经过很长的时间以后，原子钟也会产生明显误差。

TrueTime是由每个数据中心里的许多time master机器和每个机器上的一个timeslave daemon实现的。大多数master都具备专门的相互隔离的GPS接收器，而剩余的master则会配置了原子钟。所有master的时间参考值会进行彼此校对，每个master也会交叉检查时间参考值和本地时间的比值，如果二者差别太大，就会把自己踢出去。

每个daemon会从许多master中收集投票，获知时间参考值，根据确定的界限，来剔除本地时钟误差较大的机器。

在同步期间，一个daemon会表现出逐渐增加的时间不确定性。ε是从应用的最差时钟漂移中得到的。ε取决于time master的不确定性，以及与time master之间的通讯延迟。论文提到的线上应用环境里，ε通常是一个关于时间的锯齿函数，在1到7ms之间变化。

Concurrency Control

本章主要讲trueTime是如何保证并发控制的正确性，简单来说则是实现这样的特性：在时间戳为t的读操作，一定能看到在t时刻之前提交的事务。

Timestamp Management

Spanner支持三种操作类型：读写事务、只读事务和快照读取。独立的写操作会被当作读写事务执行，而非快照的独立读取操作则会被当作只读事务执行。

一个只读事务是不需要锁机制的，通过选取系统的时间戳来执行，不会阻塞后续到达的写操作。而快照读操作同样不需要锁机制。这两个都可以在任意足够新的副本上执行。

Paxos Leader Leases

Spanner的Paxos实现中通过时间化的租约，来确保长时间的leader角色（默认10s）。

一个潜在的leader可以发起请求，请求时间化的租约投票，在收到一定数量的投票后，就可以确保自己拥有租约。另外，当一个副本成功完成一个写操作，会隐式延长自己的租约。而租约快要到期时，则会显式请求延长租约。leader的租约有一个时间区间，起点是收到指定数量投票的那一刻，终点则是由于租约过期而失去一定数量投票的那一刻。注意，每个Paxos leader的租约时间区间和其他leader的时间区间是完全隔离的。

而Paxos leader的退位则可以通过将slave从投票集合中释放的方式来实现，一个leader必须等到TT.after(smax)是真才能发起退位。

Assigning Timestamps to RW Transactions

事务读写会采用两阶段锁协议，获得所有的锁之后，就可以给事务分配时间戳，这个时间戳是Paxos写操作的，代表了事务提交的时间。在每个Paxos组内，会以单调递增的方式分配时间戳，这个比较好实现。而对于跨越多个leader的情况，一个leader只能分配属于自己租约区间的时间戳。一旦时间戳s被分配，上面提到的smax会变成s。

另外，Spanner也实现了外部一致性：如果一个事务T2在事务T1提交以后开始执行，那么事务T2的时间戳一定大于事务T1的时间戳。简单来说，写进去的数据能够立即被读到，在被修改之前，读到的数据都是一样的。

Serving Reads at a Timestamp

上面提到的特性，可以使得spanner可以正确地确定副本是否足够新，每个副本会记录一个安全时间值Tsafe，表示副本最近更新后的最大时间，当读操作的时间戳t小于或等于Tsafe的时候，读操作就可以在这个副本上读取。

Assigning Timestamps to RO Transactions

只读事务会分成两个阶段执行：分配时间戳sread，然后按照sread的快照读去执行事务操作。在事务开始后的任意时刻，可以分配sread=TT.now().latese。由于Tsafe的存在，或者smax的变化，sread时刻的读操作有可能被阻塞。因为Spanner最好是分配一个可以保持外部一致性的最大时间戳。

Details

Read-Write Transactions

Spanner的读写事务，客户端对位于合适位置的组内leader副本发起读操作时，会先获取读锁，然后读取最新的数据。当一个客户端完成了所有的读操作后，会在客户端缓存所有的写操作，开始两阶段提交。客户端选择一个协调组，并且发送提交信息给所有参与的协调者leader，同时发送信息给所有缓冲的写操作。

每个参与其中的、非协调者leader会先获取写锁，然后选择一个合适的时间戳，并通过Paxos将准备提交记录写入日志。最后，这些leader会将自己的准备时间戳告诉协调者。

此时，扮演协调者的leader也会先获取写锁，然后选择一个事务时间戳，这个时间戳s必须大于或等于从前面获取到的准备时间戳信息，并且应该大于TT.now().latest。这样，这个leader，就会通过Paxos写入一个提交记录到日志，然后开始commit wait，即该leader会一直等待到TT.after(s)为true，最后发送一个提交时间戳给客户端和所有参与的leader。

每个参与的领导者会通过Paxos把事务结果写入日志。所有的参与者会在同一个时间戳进行提交，释放锁。

Read-Only Transactions

分配只读事务的时间戳存在三种方案：

• 事务开始时，根据一个表达式确定事务参与者，然后这些参与者的Paxos组之间协调，根据各自的LastTS()进行协商选出一个合适的时间戳；
• 对于在单个Paxos组上的读取，直接获取该Paxos组的最后提交的写操作的时间戳；
• TT.now().latest；

通过选择一个合适的时间戳，然后在相应的节点确认不会发生读写冲突、不会有复制协议的落后的情况下，可以处理这个读请求了。

Schema-Change Transactions

TrueTime允许Spanner支持原子模式变更。模式变更事务通常是一个标准事务的、非阻塞的变种。它会显式地分配注册一个未来的时间戳，由于读写操作都会依赖于模式，因此当它们的时间戳小于t时，读写操作就会执行到时刻t；大于t时，读写操作必须阻塞，在模式变更事务后进行等待。

总结

Spanner的理论最大亮点还是trueTime，相当于用基于原子钟的时间戳当做版本号，提高数据库的并发效率。Spanner实现的是Multi-Paxos，会有一个long-live的leader，但Spanner对Paxos的实现提及不多。