缘起

最近研究Spanner，发现国内对Spanner论文的翻译很多，但是美中不足的是，每个人都在做论文的搬运工和翻译者，没有加入自己的思考和设想，实在是令人悲哀。因此决定自己去重新阅读和理解Spanner的论文，加入自己的思考，重新理解Spanner的精髓和思想。
本文翻译过程中参考了前人对Spanner论文的翻译和理解，对其翻译欠失真或者语义不同的地方进行了改进，并加入了自己的思考。
感谢前人做的工作。

摘要

Spanner是谷歌研发的可横向扩展的、支持多版本的、可在全球范围进行分布式部署的、同步进行数据复制的分布式数据库。Spanner是世界上第一个可以在全球范围内进行数据分布式管理并且支持外部一致性分布式事务的数据库产品。这篇论文描述了Spanner的基础架构、功能特性、各种设计背后的基本原理和一个新颖的时间API（这个时间API在承认并且暴露了时间的不确定性）。Spanner中分布式事务的外部一致性和很多重要的特性（例如：历史数据的非阻塞读、无锁只读事务和schema信息的原子性变更等）均依赖于这个时间API。

1 简介

Spanner是谷歌设计、构建和部署的、可横向扩展的、全球分布式数据库。从一个最高的抽象层级来看，Spanner将数据散布在很多Paxos [21] 的状态机中，这些 Paxos 状态机位于遍布在全球的数据中心里。 通过Replication保证全球可用性和数据的就近访问（数据本地性）；Spanner的Client端可以在多个副本之间自动完成故障切换，并自动从故障的副本重新定向到正常的副本上进行数据访问。当数据量或者服务器的数据发生变化的时候Spanner可以自动完成数据在状态机之间的重分布，并且Spanner还自动在多个状态机之间（甚至可以在多个数据中心之间）进行数据迁移从而进行负载均衡和故障处理。 Spanner被设计为：可扩展到跨数百个数据中心的上百个服务器，并且可以处理和管理数万亿数据行数据。
应用程序在使用Spanner的时候，即使面临大范围的自然灾害也可以借助于Spanner中跨大陆的数据复制机制来实现数据库服务的高可用。Spanner的第一个用户是F1 [35],F1是对Google广告后台服务的重新实现。F1在Spanner中的数据在美国国内部署了5个副本。
大多数其他的应用会在一个地理区域内的3到5个数据中心之间放置数据副本，但是高可用性相对就会比较弱。也就是对于大部分的应用来说，只要能够从1-2个数据中心不可用情况下进行服务恢复，相对于高可用而言，他们更倾向于保证低延时。
Spanner的主要工作就是管理跨数据中心的数据副本，但是我们基于分布式系统基础架构也花费的很大的时间和精力来设计和实现重要的数据库功能特性。虽然在google内部有很多项目都在很愉快地使用Bigtable [9]，我们还是会不断的收到来自于Bigtable的用户的抱怨，这些客户抱怨Bigtable 无法很好的服务于一些应用：Schema很复杂且多变的应用或者对跨地域复制具有强一致性要求的应用(其他的用户也有类似的抱怨 [37]) 。在Google内部的很多应用选择使用，虽然在Google Megastore 的写入吞吐量比较低，但是由于其半关系型数据模型和对同步复制的支持，很多应用仍然选择使用 Megastore [5]。因此Spanner已经从一个类似BigTable的多版本的Key-Value存储演变成了一个带有时间属性的多版本数据库。 数据存储在模式化的半关系型存储表中；通过不同的提交时间戳将数据划分为不同的版本；根据配置的不同的垃圾回收策略，对不同的老版本的数据进行垃圾回收；并且应用也可以通过指定特定的时间戳读取老版本的数据。Spanner支持通用的事务，并且提供了基于SQL的查询语句。
作为一个全球范围的分布式数据库，Spanner提供了一些很有意思的特性。
第一：应用程序可以在很细的粒度上对数据的副本数进行动态的控制。应用程序可以指定：
【1】哪些数据中心包含哪些数据
【2】数据离用户多远（为了保证读延时）
【3】每个数据副本之间的距离有多远（为了保证写延时）
【4】总共维护多少个数据副本（为了保证可用性和读性能）
数据也可以在不同的数据中心之间动态地、透明地来回迁移，从而能够动态地平衡各个数据中心的资源使用率。
第二：Spanner还具备两个独有的特性：提供外部一致性[16]读写和基于某个时间戳的跨数据库的全球一致性读。这两个特性使得Spanner可以在全球范围内或者在事务正在执行的同时都可以执行一致性备份、一致性MapReduce执行[12]和原子性Schema信息变更。
这些特性得益于Spanner对于所有的事务（即使是分布式事务）都赋予全球范围一致的时间戳。时间戳反映了序列化的顺序。此外这种序列化顺序也满足了外部一致性（幂等性，线性化[20]）的要求；若事务T1在另一个事务T2之前提交，那么T1的提交时间就要被T2的提交时间要小。Spanner是第一个在全球范围内提交这种保证的系统。
实现这种保证的关键就是一个全新的TrueTime API。该API直接提供一个不确定时钟，而Spanner对事务顺序性的保证就依赖于不确定时钟的波动边界。若时钟的波动时间窗口很大，则Spanner就会一直等待直到晚于不确定时钟的波动时间窗口的最后时间再做后续处理，如下图所示：

这个TrueTime API由谷歌的集群管理软件实现并提供，其通过多时钟值参考对比（GPS和原子钟），选出相对而言最准确的时钟值，从而保证不确定时钟的时间窗口的宽度足够小（通常小于10ms）。
本文的第二部分描述了Spanner的架构、特性和工程设计决策。第三部分描述了新的TrueTime API以及该TrueTime API的大体实现。第四部分说明了spanner如何利用TrueTime API来实现分布式事务的外部一致性，无锁只读事务和Schema的原子性变更。第五部分提供了Spanner和True Time API的benchmark性能基准测试报告并讨论了F1。第6,7,8部分说明了未来的一些相关工作计划和文章总结。

2 实现

本节描述了Spanner的架构和底层实现原理，并对spanner中的目录进行了详细说明，Spanner通过目录来管理数据的副本和本地性，目录也是spanner中数据异动的基本单元。本节最后将会讨论Spanner的数据模型，并说明为什么Spanner看起来更像是一个关系型数据库，而不是key-value存储，以及应用程序如何控制数据的本地性。
一个Spanner集群的部署我们称之为一个Universe。若Spanner管理全球范围的数据，那么Spanner Universe的个数并不会很多。我们目前运行了一个测试环境Universe、一个预发布Universe和一个生产环境Universe。
一个Spanner的Universe由一系列的Zone组成，每个Zone相当于一个BigTable的一个部署集群[9]。Zone是Spanner部署管理的基本单元。一份数据可以在一个Zone集合中的各个Zone之间进行复制。当运行中的Spanner集群加入一些新的数据中心或者关闭一些老的数据中心时，就会加入或者移除一些Zone。Zone也是Spanner中物理隔离的单元：在一个数据中心可能有一个或者多个Zone，例如，属于不同应用的数据必须被分区到同一个机房的不同到服务器集合中。

图1显示了在一个Spanner Universe中的服务器。每个Zone都有一个ZoneMaster和100到数千个的SpannerServer。ZoneMaster将数据分配给SpannerServer，SpannerServer将数据提供给各个Client端。Client端利用每个Zone中的Location Proxy来定位可以为Client端提供数据的SpannerServer。目前universe master和placement driver都各自只有一个服务实例（存在单点问题）。 universe master 主要是一个控制台程序，用来展示用于交互式debug所需要的所有Zone的状态信息。placement driver 每几分钟都会自动进行跨Zone的数据迁移。placement driver会周期性的与spanservers 进行通讯，从而找出需要被移动的数据进行迁移，从而满足最新的数据副本约束条件或者从而实现负载均衡。优于篇幅有限，我们只对Spanserver的一些核心实现细节进行说明。

2.1 Spanserver 的软件栈

本节主要描述spanserver的实现，进而说明我们是如何基于BigTable进行改造从而实现复制和分布式事务的。SpanServer的软件栈如图2所示

图2中展示了SpanServer的软件堆栈。从图的底部，您可以看出每个SpanServer管理100到1000个Tablet。Spanner中的Tablet与BigTable中的Tablet类似，也实现了像下面这样的映射关系：
(key:string, timestamp:int64) → string
和Bigtable不同的是，Spanner会将时间戳信息也记录到key中，通过这种方式Spanner更像是一个支持多版本数据的数据库，而不是一个单纯的Key-Value存储。
Tablet的状态存储在一系列以B-Tree组织的文件集合和WAL（Write-Ahead-Log）文件中，而所有的这些文件都存储在名为Colossus（Google File System[15]的升级版）的分布式文件系统中。
为了支持复制，每个Spanserver在每个Tablet的上层都实现了一个单独的Paxos状态机（Spanserver的先前版本在每个Tablet上层都实现了多个Paxos状态机，从而允许进行更灵活复制策略的配置，但是由于这种设计过于负责，我们抛弃了）。每个状态机中将状态机的状态和日志信息记录到其对应的Tablet中。Spanner的Paxos实现支持了长寿leader，长寿leader是通过基于时间的leader租约（默认租约长度是10秒）实现的。当前Spanner的实现中会对每次Paxos的写入操作记录两次：一次记录在tablet的log中，一次记录在Paxos的log中。这种方式支持权宜之计，最终我们会进行改善。
Spanner中对Paxos的实现是管道化的，这样可以在WAN（广域网）存在网络延时的情况下可以提升Spanner的吞吐量；但是Paxos会把所有的写操作都按照顺序执行（我们将会在第四节进行详细讲解）。
Spanner中的Paxos状态机主要用来实现数据的一致性复制。每份复制数据的Key-Value映射状态都存储在它相应的Tablet中。写操作必须在Paxos leader上初始化Paxos协议；读操作可以直接从底层的任意一个最新的Tablet副本中访问其状态信息。一份数据的副本集合我们称之为一个Paxos Group。
在任意一个leader 副本上，每个Spanserver通过一张lock table来控制并发。这张lock table中包含了二阶段锁的状态：它将某个范围的key映射到相应的锁状态。（注意：只有拥有一个长寿的leader才可以有效的管理lock table），无论是在bigtable中还是在spanner中，我们都设计了长事务（例如，当生成报表时，整个事务可能持续很多分钟），这些长事务采用了乐观锁，但是当存在冲突时，性能会比较差。
需要同步执行的操作：如事务性读取，都需要从lock table中获得锁；而其他的操作均不需要考虑从lock table中获得锁。
对于每个处于leader位置的副本，每个SpanServer都会实现一个事务管理器来支持分布式事务。该事务管理器作为participant leader；Paxos Group中的其他的副本（leader之外的副本）作为participant slaves。若一个事务只涉及到一个Paxos group（大部分的事务都只涉及到一个Paxos Group），该事务可以直接跳过事务管理器，因为lock table和Paxos一起就足以保证事务性。若一个事务涉及到多个Paxos Group，这些Paxos Group的leader就会相互协调，从而完成二阶段提交。其中的一个参与Paxos Group被选为coordinator：该Group的participant leader（实际上就是spanserver为每个leader副本实现的事务管理器） 就是coordinator leader, 而该Group的slaves就是coordinator slaves。每个事务管理器的状态都存储在底层的Paxos group中(也就是存储在一个Paxos Group的各个副本中)。

2.2 目录以及数据分布

在所有的Key-Value映射的上层，Spanner实现了一层被称为directory的bucketing 抽象，一个directory是一批连续的具有相同前缀的key的集合。（可能叫做bucket更为合适）在2.3节我们将会对directory的前缀进行说明。Spanner中的Directory特性使得应用端可以通过小心地选择key进而精确地控制他们需要访问的数据的本地性。
一个directory 就是数据存储和异动的一个基本单元。在同一个directory 中的所有数据都拥有相同的副本配置。当数据在Paxos group之间移动时, 也是一个directory一个directory 移动的，就如图3所示。

Spanner可能会将一个directory 从负载高的Paxos group中迁走，从而降低该Paxos group的负载；也可能将被频繁地同时且一起访问的多个directory 都放到一个Paxos group；也可能将一个directory移动到里访问者更近的一个Paxos group中。Spanner可以在用户的操作正在进行的同事进行directory的迁移。一个50MB大小的directory可以在几秒中之内迁移完成。
实际上一个 Paxos group可能会包含多个directory，这也就意味着spanner中的tablet与hbase中的tablet是不同的：
Spanner中的tablet相当于是包含了一个行空间中一个或者多个独立的partitons的容器，多个Partition中，每个Partition内部的key值是有序连续的，但是不同的Partition的key的范围不需要连续。Spanner中的tablet不是单独的一个partition（partition的key值按照字典顺序排序）。这种设计可以让多个被频繁一起访问的directory可以被整合到一起。
我们可以做出简单的逻辑推断：Spanner会针对每个Tablet创建一个Paxos group对其进行一致性复制，而每个Paxos group中可以包含多个directory，一个Tablet中又包含多个独立顺序key范围的partition，因此这四者之间的对应关系如下图所示：

从上图中可以看出每个Paxos Group与一个Tablet对应，而每个Directory与一个Partition对应。
Movedir 是后台任务，用于在不同的Paxos groups [14]之间移动directory。 Movedir也经常被用来向Paxos groups 中添加副本或者从Paxos groups 中删除副本,因为目前Spanner还不支持在 Paxos内部执行配置的变更。 Movedir 并不是作为一个单独事务来实现的，这样可以避免由于移动某一块数据而阻塞在块数据上正在执行的事务读或者事务写操作。相反，movedir 会注册一个事实（fact），声明movedir 已经开始移动数据了，并且在后台移动数据。 When it has moved all but a nominal amount of the data, it uses a transaction to atomically move that nominal amount and update the metadata for
the two Paxos groups（这句话没有读明白，只明白开始移动数据的时候是没有启动事务的，当数据移动的差不多的时候，再启动一个事务执行原子性的操作：完成数据移动并更新元数据）.
directory也是应用可以指定的地理复制属性（数据分布或放置策略）的最小单元。Spanner中设计了数据分布描述语言，而数据分布描述语言将数据副本配置管理的功能作为单独的模块分离出来进行设计。Spanner的Administrator主要控制副本的两个维度信息：
【1】副本的数量和类型
【2】副本的地理存放位置
基于这两个维度，Spanner提供了一系列可自由组合的配置项（例如：北美地区、1主5副本）。应用程序通过在每个数据库或者directory上打上这些配置项的组合标签来控制数据的复制方式。 例如应用可以将每个终端用户的数据存储在用户自己的Directory中，并且可以让A用户的数据在欧洲地区存放3个副本，让用户B的数据在北美存放5个副本。
实际上，当Directory中的数据太多的时候，Spanner会将Directory分裂成多个Fragment（分片）。多个分片会分布在不同的Paxos Groups中（也分布在不同的服务器上），因此Movedir实际上是在不同的Paxos Groups之间移动Fragment，而不是整个的Directory ，Directory与Fragment的具体结构和关系如下图所示：

Directory与Fragment关系图

2.3 数据模型

Spanner 中数据模型的特点包括：
【1】结构化的半关系型表
【2】支持查询语言
【3】支持通用事务
多种因素驱动着Spanner的数据模型必须具备如上三个特点。
Megastore [5]在Google内部的大规模使用驱使着Spanner必须支持结构化的半关系型表和同步复制。在Google内部至少有300个应用在使用Megastore服务（虽然Megastore的性能比较低），因为在表的管理方面，Megastore的数据模型比Bigtable的更简单，并且MegaStore还支持跨数据中心的同步复制（Bigtable跨数据中心的数据复制只能保证最终一致性，不能保证同步复制）。使用MegaStore服务的比较知名的应用包括： Gmail, Picasa, Calendar, Android 应用市场, 和 AppEngine。
Dremel [28] 在Google内部作为交互式分析和查询工具而被广泛使用，驱使着Spanner必须支持SQL查询语句。
由于BigTable中不支持跨行的事务，导致了用户一直对其抱怨；Percolator [32]就是为了解决跨行事务的问题。Spanner采用常规二阶段提交，但是Spanner的开发人员声称这会将会极大地降低Spanner的性能和可用性 [9, 10, 19]. 但是我们认为最好还是由应用程序的开发人员去解决由于过于使用业务而导致的性能问题，而不是一直进行无事务研发。另外，在Paxos 执行二阶段提交会极大地缓解可用性问题。
应用端的数据模型构建在Spanner 的通过Directory进行分桶的Key-Value数据模型之上的。一个应用可以在一个Universe中创建一个或者多个database。每个database中可以包含无限个结构化表。这些表和传统数据库中的表很像，有行、列和多个版本的值。Spanner中的查询语言也和SQL语句很像，但是我们对其做了一些扩展，可以让表的某一列的类型为：protocol-buffer 的值类型。
Spanner的数据模型并不是纯粹的关系型的，Spanner中的行必须有名字。更准确的说，Spanner中的每个表都必须有一个由一个或者多个主键列组成的有序集合。正式这个限制，使得Spanner看起来还像一个Key-Value的存储：这些主键组成了一行的名字，每个表都定义了从多个主键列（相当于Key）到多个非主键列（相当于Value）的映射。
只有针对行中的key定义了相应的value（即使这些value的值为null），我们才认为该行是存在的。这种架构设计的一个优点就是：允许应用程序简单地选择一些key的值或者范围就可以控制数据访问的本地性。

图4展示了Spanner中的一个典型的schema示例，该schema示例存储了照片的元数据信息，照片的元数据是基于一个用户对应一个相册的方式进行组织的。Spanner中的Schema描述信息与MegaStore的描述信息很像，但是有一个特有的要求：Spanner中的每个database都必须被client端分成一个或者多个具有层级结构的表。Client端通过INTERLEAVE IN 语法声明database中的表的层级结构。在顶层的表是一个目录表。在目录表中的每一行都有一个键：K。目录表的下一层表叫做目录表的子表，子表中的每一行也都有键：K',K'可能以K开头，也可能不以K开头，Spanner会将子表中含有以K开头的键的行和目录表中含有以K开头的键的行放在一起（以字典顺序排序），构成了一个目录。 ON DELETE CASCADE语法意味着：若删除目录表中的一行，也会级联删除子孙表中的相关联的行。这个图也展示出了示例数据库的数据布局关系：例如：Albums(2,1) 代表着表Albums 中的一行数据，这一行数据中的uid为2，aid为1。
Spanner这种通过对有关联关系的两张表交叉组织在一起，并形成目录的数据组织方式对Spanner来说是非常重要的，因此这样就可以让client端通过指定多张表之间的局部关联关系，就可以精确地访问到部分数据，避免了对全量数据的扫描，这种特性对于提高分布式可分片的数据库系统的性能来说是至关重要的。若没有这种数据组织结构，Spanner将无法精确的定位到所需要访问的所有关联数据的位置、也无法极大地缩小数据扫描的范围。

3 TrueTime

本节主要对TrueTime API进行说明，并对它的实现方式进行简要概述。关于其实现细节有专门的其他论文进行说明，我们的目的是为了说明这个TrueTime API的主要价值在哪。 Table 1 列出了TrueTime API的方法。TrueTime 认为时间应该被表述成一个时间区间，而不是一个时间点，而这个时间区间TrueTime称之为TTinterval。TTinterval是一个具有有限时间不确定性的时间区间（也可以叫做有边界的时间不确定性区间，承认给出的时间是不确定的，但是偏差的大小是确定的。而不像其他标准的时间接口，他们根本就不承认时间具有不确定性）。 因此TTinterval有不确定性的上限和下限，上限和下限都是TTstamp（类似于TimeStamp）类型，也就是说上限和下限都是时间点。例如：方法 TT.now() 就返回一个TTinterval对象，该TTinterval对象保证包含在调用TT.now() 方法时的绝对时间。这个绝对时间和Unix的时间（考虑了闰秒涂抹）类似。TT.now()返回的TTinterval的即时误差是TTinterval宽度的一半。方法TT.after() 和 TT.before() 是基于 TT.now()方法的二次封装，提供了用于判断是否已经超过了指定时间和是否还没有到达指定时间的便捷方法。
假设函数tabs(e)返回的是事件e发生的绝对时间。那么使用更加专业的方式来描述就是：对于一次调用： tt = TT.now()，TrueTime能够保证tt.earliest ≤ tabs(enow) ≤ tt.latest,其中enow就表示这次调用，tabs(enow) 就表示调用发生的绝对时间。
TrueTime底层使用的是GPS时间和原子钟时间。TrueTime 之所以使用两种类型的时间，是因为他们都有可能在不同的场景下获取时间失败。GPS时间获取失败或者获取时间不准确的原因包括：天线和接收器失效、当地电磁干扰、其他一些设计上的原因（例如：不能正确进行跳点处理和GPS欺骗）和GPS系统宕机 。
原子钟也会失败，但是其失败的原因与GPS失败的原因完全不一样，而且各个原子钟也都是独立的没有彼此相关性。原子钟一种最常见的失败原因是：由于原子钟的频率错误（原子钟的频率错误不会导致时间马上出现错误），而导致经过长时间之后，原子钟的时间才出现明显的偏差。
在每个数据中心都有一系列的 time master服务器，在每个 time master服务器上都有一个time slave后台进程，TrueTime就是由位于各个数据中心的time master服务器上的各个time slave后台进程实现的。
大多数的time master服务器上都带有GPS接收器（每个GPS接收器上都有专用的天线）；这些time master服务器在地域上被分开放置，从而避免由于天线失效、无线电干扰和GPS欺骗等原因而引起大范围的影响。剩下的time master服务器(我们称之为世界末日master，可能是为了应对世界末日到来时，GPS不管用的情况，但是若世界末日真的到来了，难道还有人使用google吗？呵呵) 上都装备有原子钟。其实一个原子钟也不是很贵：一个世界末日time master的费用与一个GPS time master的费用相当。所有time master服务器上的时间都会彼此进行比对。 每个time master 服务器还会比对本地时钟和其他服务器时钟的频率进行交叉检查，若发现本地时钟频率与其他服务器的时钟频率相差太大，则将自己驱逐（个人认为不是与一个其他时钟服务器的频率进行对比，而是与多个时钟服务器的频率对比，只有发现其他时钟服务器的频率都相近，只有自己的频率与其他时钟服务器的频率相差甚远时，才会将自己驱逐）。 在时钟同步的过程中，末日master服务器时间的不确定性缓慢增加，这主要是由于最坏情况下进行时钟漂移策略导致的。而GPS在时钟同步的过程中，则可以基本保证不确定性为0。
每个slave后台进程都会从很多的time master服务器上收集时间参考值，从而减少或者避免由于某一台time master故障而导致的误差，收集时间参考值的这个过程我们称之为收集投票。有些GPS time master服务器是从附近的数据中心选取的；剩下的GPS time master 服务器是从较远的数据中心选取的，还有一些世界末日 time master服务器也是从较远的数据中心选取的。
每个slave后台进程会使用一种 Marzullo [27]算法的变种算法来探测和拒绝欺骗，并将本地时间同步到非欺骗的time master 服务器。
为了防止损坏或者故障时钟服务器对整体的时间准确性产生巨大影响，当某台时钟服务器的时钟频率的误差超过某一个标准误差范围的时候，这台时钟服务器就会被驱逐。
在时钟同步的过程中，time slave后台进程表现出时间不确定性的缓慢增加，而这种时间不确定性不仅取决于保守的最差情况下的本地时钟漂移策略还取决于各个 time-master服务器的不确定性和各个服务器之间的通讯延时。在spanner的线上生产环境中，时间不确定性表现为一个时间锯齿状函数，时间不确定性在每轮收集投票的过程中都会在1到7ms之间来回波动，因此大部分情况下，时间不确定性的平均值为4ms。后台进程收集投票的间隔为30秒，当前的时钟频率的漂移比率为200微秒/秒，所以每轮投票间隔内，其时间不确定性的值就会在0到6ms之间来回波动。剩下的1毫秒主要是由于各个time master服务器之间的通讯延时产生的。当某些故障发生时，时间不确定性也会偶尔超出锯齿的边界。 例如，某个time-master服务器的偶尔不可用，有可能导致整个数据中心范围的时间不确定性的增加。类似的，机器负载过高和网络问题也会导致时间不确定性的偶尔增大。

4 并发控制

本节描述TrueTime是如何用来保证并发控制的正确性的，以及如何利用这种属性来实现诸如：外部一致性事务、无锁只读事务和对历史数据的非阻塞读。这些特性可以保证在某个时间t进行数据库的读，一定可以看到在t时间之前提交的所有事务。
进一步说，将Paxos看到的写操作（除非上下文明确指出是Client端写操作，否则我们认为所有的写操作都是Paxos看到的写操作）和Spanner客户端的写操作区分开非常的重要。例如，两阶段提交保证在spanner client端还没有进行写操作的时候，就发起一次Paxos写。

4.1 时间戳管理

表2列出了Spanner支持的所有的操作的类型。Spanner支持读写事务，只读事务（预先声明的快照隔离事务）和快照读。
单独的写时通过读写事务来执行的；非快照读是通过只读事务来实现的。两者都是在内部进行重试的（客户端不需要写重试逻辑）。
只读事务具有快照隔离级别[6]的性能优势。一个只读事务必须事先声明不会包含任何的写操作；只读事务并不是一个简单的不包含写操作的读写事务。在只读事务中的读操作在执行的时候会在没锁的情况下获得一个系统时间戳，所以在读操作获取时间戳的过程中，不会阻塞任何的写操作。只读事务中的读操作可以在任何最新的数据副本上执行（4.1.3节）。
快照读操作时针对于历史数据的读取，快照读操作执行的时候不需要锁。客户端可以指定一个时间戳，从而让快照读只读取该时间戳对应的历史数据，或者也可以提供一个想要读取的历史数据的时间范围，让Spanner自己选择一个合适的时间戳。不管是哪种情况，快照读都会在一个最新的副本数据上执行。
对于只读事务和快照读而言，一旦选择了时间戳，那么提交就是不可避免的，除非指定的时间戳对应的数据已经被垃圾回收。
因此，Client端不需要在重试逻辑中缓存结果。当一台服务器宕机的时候，Client端内部就会自动继续根据指定的时间戳和当前读取的位置从另一台不同的服务器上继续读取数据。

4.1.1 Paxos Leader 租约

在Spanner的 Paxos实现中，使用了时间租约来实现leader地位的长时间存在（默认10秒钟）。潜在的leader会发起时间租约的投票；一旦发起投票的潜在leader获得了指定树龄的投票后，该leader就认为自己获得了时间租约。当一个PaxosGroup内个一个副本完成了一次写入，就会隐式的进行一次租约延期。当一个leader的租约块到期的时候，他就要主动请求进行租约延期。 当一个leader收到了指定数量的选票的时候就是leader时间租约区间开始的时间，当一个leader不在拥有指定数量的租约选票的时候，就是leader时间租约结束的时间（因为有些选票已经过期了）。
Spanner依赖于下述的不相交特性：
任意两个PaxosGroup的leader的时间租约区间都是不相交的。附录A描述了如何实现这种不相交性。
Spanner允许Paxos leader通过将slave从租约投票中释放的方式进行leader退位。但是为了保证上述的不相交性，Spanner会对Paxos leader的退位时机进行限制。
Spanner定义Smax为一个leader可以使用的最大时间戳。从后续的章节将会知道，一旦指定了 Smax ，只有当TT.after(Smax)为true时，当前的leader才可以退位。

4.1.2 为读写事务指定时间戳

事务性读和写使用两阶段锁。因此在读写事务获得锁之后，释放锁之前，我们可以为之指定任意的时间戳。对于任意一个事务Spanner都会为其指定一个时间戳，该时间戳是Paxos为Paxos写操作指定的时间戳，代表着事务的提交时间。
Spanner依赖于以下单调性：
在每个PaxosGroup内部，Spanner会以单调递增的顺序为每次的Paxos的写操作分配一个时间戳，即使是跨多个Paxos Leader，其分配的时间戳也是单调递增的。这种单调性在跨越多个leader的场景下是通过利用时间租约的不相交性来实现的：一个leader只能为其指指定一个在其时间租约以内的时间戳。需要注意的是：一旦指定了一个时间戳S，Smax就需要被增加到S来保证不相交性。
Spanner也实现了以下所描述的外部一致性：
若事务T2的开始时间在事务T1的提交时间之后，那么事务T2的提交时间一定比事务T1的提交时间要晚。
执行事务的协议和分配时间戳的协议遵循两条原则，这两条原则一起保证了事务的外部一致性，如下面描述。我们定义写操作Ti的commit request到达coordinator leader的事件为e_i_server.因此上述的两条原则如下：
Start coordinator leader 会为写操作Ti分配一个不小于TT.now().latest的时间戳：Si。TT.now().latest的值是在事件e_i_server之后计算得到的。participant leaders在这条规则里并不重要；4.2.1 节中将会描述participant leaders是如何参与到下一条规则的实现的。
Commit Wait coordinator leader 必须确保在TT.after(si)的返回值为true之前，Client端是永远不可能看到任何提交的数据的。Commit wait就是要确保si比Ti的绝对提交时间要小。 commit wait 的实现细节将会在4.2.1节中进行描述，证明如下：
s1 < Tabs(e_1_commit ) (commit wait)
Tabs(e_1_commit) < Tabs(e_2_start) (假设)
Tabs(e_2_start) ≤ Tabs(e_2_server) (因果关系)
Tabs(e_2_server) ≤ s2 （Start规则）
s1 < s2 (推导)

4.1.3 基于某个时间戳进行读操作

在4.1.2节中提到的单调递增性和不变性，使得Spanner可以准确的判断一个数据副本是否足够新从而可以服务于某次读取请求。每个数据副本都会记录一个名为安全时间的额变量：T_safe。T_safe的值是数据副本最近一次更新后的最大时间戳。若一个读操作的时间戳是T，当满足T<=T_safe的时候，这个数据副本才可以被当前的这个读操作进行读取。
我们定义T_safe=min(T_paxos_safe,T_tm_safe)，在该定义中T_paxos_safe代表每个Paxos状态机的安全事件，而T_tm_safe则代表每个事务管理器的安全时间。T_paxos_safe 比较简单：它的值就是最新的应用的Paxos Write的时间戳。由于时间戳是单调递增的而且写入操作也是被顺序执行的，因此当时间戳小于或者等于T_paxos_safe的时候，不会发生新的写入。
对于一个数据副本而言，若没有prepare 事务（未提交），那么T_tm_safe的值就是无穷大。当T_tm_safe的值为无穷大的时候，此时的事务正处于两阶段提交中的两个阶段之间。(对于一个参与的Slave而言，T_tm_safe实际上是指副本的leader的事务管理器的时间，而事务管理器的状态可以通过Paxos write操作传入的元数据推断出来) 。若存在这样的事务，那么被这些事务影响的状态是不确定的：一个参与者副本无法知道某个事务是否将要提交。正如4.2.1节中讨论的那样，提交协议会保证每个参与者都知道每个预提交事务的时间戳的下界。事务Ti的参与leader（对于一个Group g来说）会为预提交记录分配一个预提交时间戳：S_prepare_i_g。协调者leader会确保所有参与者组的事务的提交时间戳Si>= S_prepare_i_g。所以在组g内的所有的预提交事务Ti，都满足：T_tm_safe=Min_i(S_prepare_i_g)-1。

4.1.4 对只读事务指定时间戳

一个只读事务的执行分为两个阶段：指定一个时间戳S_read[8]，然后执行基于时间戳S_read上的快照读。可以在任意一个最新的数据副本上执行快照读。指定S_read的值的简单方式就是：S_read = TT.now().latest, 并且事务一旦开始，就采用类似于4.1.2节中对写操作保持事务一致性相似的方式保证只读事务的一致性。
但是，若T_safe不是足够大，那么基于S_read的数据读操作将会阻塞。 (此外，我们应该意识到当设置一个S_read的值的时候，由于我们需要保证不相交性和递增性，可能会间接地增加S_max的值。) 为了减少基于S_read的快照读阻塞的概率，Spanner会在保证外部事务一致性的前提下分配一个最大的时间戳。4.2.2节会详细解释怎么选择这样一个时间戳。

4.2 细节

本节将会对前面提到的读写事务和只读事务的实现细节，以及用于实现原子性模式变更事务的实现方式。最后将会说明基本模式的改进细节。
4.2.1 Read-Write Transactions
像Bigtable一样，一个事务中的写操作，在提交之前都会缓存在client端的。因此在事务写提交之前，另一个事务中的读不会看到事务写产生的变更。 Spanner中的这种设计之所以工作的很好是因为读操作会返回读取中的数据中带回来的时间戳，而未提交的写操作这是还未被指定时间戳。
读写事务中的读操作采用伤停等待（wound wait [33] ）来避免死锁。Client端向合适的Paxos Group的leader发起读操作，该次读操作将会请求获得锁并且读取最新的数据。当一个Client端的事务保持open期间，Client端会不停的向leader不停的发送keepalive消息，从而避免leader在该事务期间超时。当一个Client端已经完成了所有的读操作并且缓存的所有的写操作，它就开始进行两阶段提交。Client端会选择一个协调Group并且向各个参与Group的leader发送commit消息，该消息中携带了协调者信息和缓存的写操作。让Client端发起二阶段提交可以避免在各个连接上普遍的发送起两次数据，从而避免了大范围的网络数据传输。
一个非协调的参与Group的leader首先会请求获得写锁。然后该leader会选择一个预备时间戳，该预备时间戳必须比该leader分配给先前的任何事务的时间戳都要大（为了保证单调递增性）,并且将预备记录通过Paxos写入日志。最后每个参与leader都会将自己的预备时间戳通知给协调leader。
协调Group的leader也会首先要求获得写锁，但是会跳过预备阶段。在收到各个参与Group leader的消息后，协调Group的leader会为整个事务分配一个时间戳。commit时间戳s必须大于或者等于所有的预备时间戳（为了满足4.1.3节中的约束）, 也要大于协调组的leader收到commit消息时 TT.now().latest 的值，也要比leader为之前的事务分配的所有的所有的时间戳都要大。 协调组的leader会通过Paxos在日志中写入提交记录（或者当等待其他参与者超时的时候，在日志中写入一个退出记录）。
在协调组的leader一直等到TT.after(s)返回true之前，协调组的任何副本都不会应用commit记录，从而遵循4.1.2节中所述的commit-wait原则。
因为协调组的leader基于TT.now().latest来指定s的值，并且要一直等待s的时间戳成为过去式，预计的等待时间是2倍的时间偏差。这个等待的时间通常和paxos的通讯时间重叠。在提交等待之后，协调组会将commit时间戳发送给Client端和其他所有的参与者leader。每个参与者leader都会通过Paxos将事务的结果写入日志。所有的参与者leader都会在同一时间戳进行提交，然后释放锁。

4.2.2 只读事务

分配一个明确的时间戳需要在read操作涉及到的所有Paxos组之间进行一次协调。因此Spanner需要为每个只读事务提供一个scope表达式，该表达式说明了在整个只读事务中需要被读取的所有keys。Spanner 会自动推算出所有独立查询的查询范围。
若Scope的值是由单个Paxos组提供的，那么Client端就会向那个组的leader发起一个只读事务(当前Spanner的实现，只会为Paxos leader中的只读事务指定一个时间戳。) ，那个leader指定S-read并且执行Read操作。对于一次单个位置的读操作，Spanner通常比TT.now().latest做的更好。我们定义LastTS() 为在一个Paxos Group上执行最后一次commit write的时间戳。若没有预提交事务，那么赋值S_read=LastTS()就可以满足外部一致性：
事务将会看到最后一次写入的结果，因此在最后一次写入之后进行排序。
若Scope的值由多个Paxos组提供，我们可以通过几种方式来最终确定Scope的值。其中最复杂的一种方式就是让所有Group的leader针对各自的LastTS()的值进行协商，并最终得出S_read的值。
Spanner目前实现了一种简单的方式。Client端不需要询问所有Group的leader，而是在S_read=TT.now().latest(这可能会导致等待安全时间的增加)的时候去执行read。事务中的所有读都可以被发送到足够新的数据副本上执行。

4.2.3 Schema信息变更事务

TrueTime 使得Spanner具备了原子性Schema信息变更的能力。采用标准的事务模型来执行Schema信息的变更是完全行不通的，因此一次schema信息的变更涉及到的参与者（数据库中group的个数）可能会成千上万个。Bigtable 可以实现在一个数据中心内部的原子性schema信息变更，但是它在执行schema信息变更的时候，将会阻塞所有其他的操作。
Spanner 的Schema信息变更事务是一个非阻塞的标准事务的变种。首先Spanner会显式的分配一个未来的时间戳 ，该时间戳将会在准备阶段进行注册。因此，涉及到数千台服务器的schema信息变更将会在不影响其他并发的活动的前提下完成。 其次，读写操作，他们都是隐式的依赖于shema信息，它们都会和任何注册的schema信息变更时间戳t保持同步：当读写操作的时间早于t，读写操作会正常执行，但是当读写操作的时间晚于t，读写操作将会被阻塞。若没有TrueTime，那么定义schema信息变更的时间戳，将没有任何意义。

4.2.4 改进

前面对T_tm_safe的定义有一个缺点：在一个单独的预提交事务中将会导致T_tm_safe无法进一步增加。产生的其他影响就是，即使在T_tm_safe之后的读操作与该预提交事务不存在任何冲突，这些读操作也无法执行，这种冲突我们称之为：假冲突。通过为T_tm_safe增加一个从从键域（key range）到预提交事务时间戳的细粒度的映射关系，我们可以消除这种假冲突。这个信息可以被存储在锁表中（lock table）, 锁表中其实早已经存在了键域到锁信息的映射。当执行read操作的时候，只需要针对基于键域定义的细粒度的安全时间和读操作的冲突时间进行检测即可。
前面定义的LastTS() 方法也有类似的缺点：若一个事务刚刚被提交，一个非冲突的只读事务必须被分配一个S_read，从而可以跟在刚提交的事务后面。因此，read操作的执行将会被推迟。该缺点也可以采用类似的方法进行补救：通过为LastTS() 方法增加一个从键域（key range）到锁表中提交时间戳的细粒度的映射（目前spanner还么有真正实现该优化）。当接收到一个只读事务的时候，就需要为该事务分配一个时间戳，该时间戳的值的选择方式是：若有一个冲突的预提交事务，则从该预提交事务的细粒度的T_tm_safe时间中选择，否则就从与该事务冲突的键域中LastTS()的最大值中选择。
前面定义的T_paxos_safe有一个缺点：当存在Paxos写操作的时候，该值无法增加。也就是说，在时间t的快照读不能在这样Paxos Group（这种Paxos Group中的写操作发生在t之前）中执行。Spanner 通过充分的利用leader租约间的隔离性解决了该问题。每个Paxos leader都会通过维护一个阈值的方式来增加T_paxo_safe的值，未来的一些写操作可能会触碰到该阈值： 它维护了一个从Paxos序列号n 到可以分配给下一个Paxos（序列号是n+1）的最小时间的映射关系MinNextTS（n）。位于序列号n的Paxos Group中的数据副本可以将其T_paxos_safe的值增加到MinNextTS(n) -1。
一个单独的leader可以简单的强制指定LastTS() 的值。因为LastTS() 承诺的时间戳一定会位于一个leader的租期内， 因此LastTS() 也保证了各个不同leader之间的不相交性。若一个leader想要将LastTS() 值增加到其leader 租期之外，那么它需要首先增加其leader租期。需要注意到：为了保证不相交性，S_max的值也不可能超过LastTS() 的最大值。
默认情况下leader会每8秒钟增加一次MinNextTS() 的值， 因此当不存在预提交事务的时候，在空闲LastTS() 中的健康的slave在最坏的情况下也可以在最近8秒以内的时间戳上提供read服务。一个leader也可以根据slave的要求增加 MinNextTS() 的值。

5 测试与评估

我们首先评估Spanner在复制、事务和可用性等方面的性能表现. 然后提供一些TrueTime的实验数据，最后对我们的第一个用户F1，在使用过程中的一些数据和经验进行说明和研究。

5.1 MicroBenchmarks

Table 3 展示了Spanner的microbenchmarks 的测试数据。这些测试时在分时服务器上完成的：每个SpanServer都运行在4GB内存和四核（AMD Barcelona 2200MHz）的调度单元上。有多个Client，并且每个Client都运行在单独的服务器上。 每个Zone都包含一个SpanServer。Clients和Zones都在一个数据中心里面，而一个数据中心里面网络延时不会超过1ms。 (这种布局非常普遍：大多数的应用都不需要实现全球分布式。)测试数据库中含有50个Paxos Group，一共有2500个directory。 操作都是单独的4KB大小的读写操作。若有的读都是在读取的数据在Spanner中完成压缩之后才读取出去的，所以我们支持在测试Spanner中方法调用堆栈的性能开销（可以忽略网络开销）。此外，在正式测试之前，我们会首先对所有数据全部都去取一遍，来填充所有位置的缓存。

在进行延时测试的时候，Client端会发送尽量少的操作，从而避免在server端进行排序。在1个副本的环境下，提交等待时间大概是5ms，Paxos的延时大概是9ms。当副本数增加的时候，延时基本保持不变，并且标准差会变小。这是因为 Paxos在Group的各个副本之间是并行执行各种操作的。随着副本数的增加，某个slave缓慢对整个Paxos组中选出leader产生的影响变得越来越小。
在进行吞吐量实验的时候，Client端发出足够多的操作，从而使Server的CPU达到饱和。快照读可以在任意一个足够新的数据副本上执行，因此快照读的吞吐量会随着副本数的增加而线性增加。单个读的只读事务只能在leader上执行，因为其时间戳只能在leader上指派。只读事务的吞吐量会随着副本数的增加而增加：在实验环境设置中，SpanServer的数量与副本的数量相同，并且leader随机分布在不同的Zone中。这种实验环境的设置对于写操作的吞吐量有益（当副本数从3增加到5的时候，写操作的吞吐量增加了，正说明了这一点），但是随着副本数的增加每个写操作需要完成的工作量也会线性增加，前面实验环境的设置而带来的这种收益也会被这种增加的工作量而抵消。
Table 4 说明了二阶段提交可以扩展到一定数量的参与者：它是对运行在3个zones中的25个Spanservers测试数据的汇总。当扩展到50个参与者的时候，无论是在延时平均值还是在99%的延时时间上表现都还不错，但是当增加到100个参与者的时候，延时就开始明显升高了。

5.2 可用性

图 5 展示了当在多个数据中心间运行Spanner的时候产生的可用性收益。该图展示了当数据中心宕机的情况下的三种实验结果，所有的实验结果都重叠的叠放在相同的时间轴上。测试universe 包含5个Zones：Zi，每个Zone中含有25个SpanServers。测试数据库被分为1250 个Paxos groups，并且有100个测试Clients持续地以50000读/秒的速度不停地执行非快照读操作。 所有的leader都被明确的放在Z1中。每种测试进行5秒钟之后，在一个Zone中的所有Server都被Kill掉: non-leader测试中会 kill掉 Z2中所有的Servers;在 leader-hard测试中会 kill掉 Z1中所有的Servers; leader-soft kills Z1,只不过在leader-soft测试中，kill Z1中的leaders之前，会首先通知所有的服务器他们将会交出领导权。

Kill Z2中的Servers对Read吞吐量没有任何影响。在Kill Z1之前，会首选给Z1中的leaders一些时间来将领导权交给其他的Zone，这样会有一个小小的影响：吞吐量会有稍微的下降，在图上看不出来，下降的吞吐量大概是3-4%。另外，不进行提前预警，而直接杀掉Z1有一个很严重的影响：
完成率几乎下降到了0（完成率是什么鬼？还不清楚，有清楚的小伙伴可以email我）。随着重新选举出leaders，系统的吞吐率重新回升到了大概100K 读/秒 ，这主要是因为实验的两个设置：系统有一个额外的能力就是当leader不可用的时候，所有的操作都会排队。 因此，系统的吞吐率会一直回升，直到达到一个很定的速率。我们也可以看看将Paxos leader的任期租约延长到10秒钟的效果。当我们kill掉Zone的时候，属于该Zone的各个Paxos Groups中的leader的租约过期时间会均匀的分布在下一个10秒钟内。 当一个已经死亡的leader的租约一旦过期，就会马上选举出一个新的leader。大约在kill掉一个Zone之后的10秒钟，所有的Paxos Groups都会拥有leader，并且吞吐量得到了恢复。更短的leader租约时间将会降低由leader死亡而导致的可用性的影响,但是由于其需要更加频繁的更新租约信息，因此增加了网络开销。我们正在设计并实现一种机制：当leader一旦失效，就可以让slave马上释放Paxos leader租约。

5.3 TrueTime

关于TrueTime，必须回答两个问题：ε是否就是时钟不确定性的边界？ε（时间不确定性区间绝对值）最糟糕的情况下会有多大？对于第一个问题，最严峻的问题就是，如果一个局部的时钟漂移大于200us/sec，那就会破坏TrueTime的假设。我们的服务器统计数据显示，CPU出故障的概率要比时钟出故障的概率高出6倍。也就是说，相比而言硬件出故障的概率要比时钟出故障的概率大的多。因此，我们也相信，TrueTime也和Spanner依赖的其他基础软件服务一样，具备完备的稳定性和可信赖性。
图6显示了从数千个跨多个数据中心的SpanServer上收集来的，这些数据中心相互之间的距离超过2200公里。图中展示了ε（时间不确定性区间绝对值）的90%、99%和99.9%数数值波动情况，图中的数据是在time slave daemon线程完成了对time master的投票之后，对time slave daemon线程立即进行采样收集的。这些采样数据中不包含由于本地时钟不确定性而引入的锯齿数据。这些抽样数据没有考虑由于时钟不确定性带来的ε值的锯齿，因此测量到的数据的值是：time-master的不确定性（通常是0）再加上通讯延迟。

从图6中的数据可以看出：在确定ε的基本值的时候的两个重要因素都不是问题。但是，可能会存在明显的tail-latency（拖尾延迟？什么叫tail-latency？这个我还没有研究明白，有清楚的同学可以告诉我）问题，而这个问题又会导致ε值升高。图中，3月30日tail-latency(拖尾延迟)的降低，是因为网络的改进，减少了瞬间网络连接的拥堵。在4月13日ε的值增加了，持续了大约1个小时，主要是因为例行维护时关闭了两个time master。我们会继续调研并且消除引起TrueTime突发波动峰值的因素。

5.4 F1

Spanner在2011年早期开始进行在线负载测试评估，当时它是作为谷歌广告后台F1[35]的重新实现的一部分。这个后台最开始是基于MySQL数据库的，在许多方面都采用手工数据分区。未经压缩的数据可以达到几十TB，虽然几十TB的数据量对于NoSQL产品而言数据量是很小的，但是，对于采用数据分区的MySQL而言，数据量已经大到难以支撑。MySQL的数据分片机制，会把每个客户和所有相关的数据分配给一个固定的分区。这种部署方式，可以针对单个用户的数据充分地利用索引并执行复杂的查询处理，但是需要在应用系统的业务逻辑代码中掺杂着复杂的分区逻辑。随着客户数量的增长，对数据进行重新分区，代价是很大的。最近一次的重新分区，花费了两年的时间，为了降低风险，在多个团队之间进行了大量的合作和测试。这种操作太复杂了，无法常常执行，由此导致的结果是，团队必须限制MySQL数据库的增长，方法是，把一些数据存储在外部的Bigtable中，这就会牺牲事务和查询所有数据的能力。
F1团队出于多个原因选择使用Spanner。首先，使用Spanner不需要手动进行reshard。其次，Spanner提供了同步复制和自动FailOver。 而若使用MySQL原生的主从复制很难实现FailOver，并且还有数据丢失和宕机的风险。最后， F1需要强事务语义，这NoSQL提供不了强事务语义保证。应用程序需要跨任意数据的事务性保证和一致性读。F1团队还需要在他们的数据上构建二级索引 (因为Spanner并没有提供对二级索引的自动支持), 并且也有能力使用Spanner的事务来实现自己的全局一致性索引。
现在所有应用程序的写入操作都不再通过MySQL的技术堆栈执行而是通过F1发送给Spanner。F1 在美国西海岸地区有2个副本，在东海岸有3个副本。 复制站点的选择主要考虑对重大自然灾害的应对以及前端应用服务器站点的位置。实际上，Spanner的自动FailOver对F1团队来说是不可见的。尽管在过去的几个月，Spanner有一些突发集群失效的情况，但是对F1团队完全没有影响。F1团队只需要更新他们的数据库Schema信息告知Spanner在哪里方式Paxos leader，从而保证这些leader尽量地离前端应用服务器近一些。
Spanner的TimeStamp语义可以使其为F1在内存中高效地维护从数据库状态计算得到数据结构。F1 会为所有变更都维护一个逻辑历史日志，它会作为每个事务的一部分写入到Spanner。F1 会得到某个时间戳下的数据的完整快照，来初始化它的数据结构，然后根据数据的增量变化来更新这个数据结构。

表5显示了F1中每个目录的分片数量的分布情况。每个目录通常对应于F1中应用堆栈中的一个用户。绝大多数目录（同时意味着绝大多数用户）都只会包含一个分片，这就意味着，对于这些用户数据的读和写操作只会发生在一个服务器上。多于100个分片的目录，是那些包含F1二级索引的表：对这些表的多个分片进行写操作的情况并不常见。F1团队也只是在以事务的方式进行未经优化的批量数据加载时，才会碰到过这种情况。

表6展示了从F1服务器上测量的Spanner操作的延迟。在东海岸数据中心的副本，在选择Paxos领导者方面会获得更高的优先级。表6中的数据是从这些数据中心的F1服务器上测量得到的。写操作延迟存在较大的标准差，是由于锁冲突引起的肥尾效应（fat tail）。在读操作延迟上存在更大的标准差，部分是因为Paxos领导者跨越了两个数据中心，而只有其中的一个数据中心是采用了SSD硬盘。此外，测试内容还包括系统中的每个两个数据中心的每个读操作：字节读操作的平均值和标准差分别是1.6KB和119KB。

6 相关工作

Megastore[5]和DynamoDB[3]已经提供了跨越多个数据中心的一致性复制服务。DynamoDB提供了键值存储接口，只能在一个region内部进行复制。Spanner和Megastore一样，都提供了半关系数据模型，甚至采用了类似的模式定义语言。Megastore的性能并不高。Megastore是架构在Bigtable之上，这种方式需要付出很高的通讯代价。Megastore也不支持长寿命的领导者：多个副本可能会发起写操作。来自不同副本的写操作，即使他们不会发生逻辑冲突，在Paxos协议下也一定会发生冲突，：会严重影响吞吐量，在一个Paxos组内每秒钟只能执行几个写操作。Spanner提供了更高的性能，通用的事务和外部一致性。
Pavlo等人[31]对数据库和MapReduce[12]的性能进行了比较。他们指出了几个已经付出的努力：通过分布式键值存储之上融合数据库的功能性[1][4][7][41]，证明了二者可以实现充分的融合。我们比较赞同这个结论，并且认为集成多个层是具有优势的：例如把复制和并发控制集成起来，可以减少Spanner中的提交等待代价。
在一个采用了复制的存储上面实现事务的理念，可以至少追溯到Gifford的论文[16]。Scatter[17]就是目前比较流行的一个基于DHT的键值存储，Scatter在一致性复制的基础上实现了事务。Spanner则比Scatter提供了更高层次的接口。Gray和Lamport[18]描述了一个基于Paxos的非阻塞的提交协议，这种协议与两阶段提交协议相比引入了更多的通讯正本，而两阶段提交协议则会在设计多个Group的时候加剧提交成本。Walter[36]提供了另一种方案，这种方案是快照隔离的变种，但是无法跨越数据中心。相反，我们的只读事务提供了一个更加自然的语义，因为，我们对于所有的操作都支持外部一致性。
在减少或者消除锁开销方面已经进行了一系列的研究工作。Calvin[40]消除了并发控制：它会重新分配时间戳，然后以时间戳的顺序执行事务。HStore[39]和Granola[11]都可以根据自己的事务类型进行分类，有些事务类型可以避免锁机制。但是，这些系统都无法提供外部一致性。Spanner通过提供快照隔离，解决了锁冲突问题。
VoltDB[42]是一个分片的内存数据库，它可以支持广域主从复制，支持灾难恢复，但是没有提供通用的复制配置。VoltDB属于NewSQL的产品，可以支持可扩展的SQL[38]。许多商业数据库都支持历史数据读取，比如：Marklogic[26]和Oracle的Total Recall[30]。Lomet和Li[24]针对这种时序数据库提出了一种实现策略。
Faresite给出了与一个信任的时钟参考值[13]相关的、时钟不确定性的边界（要比TrueTime更加宽松）：Farsite中的服务器租约的维护方式与Spanner中维护Paxos租约的方式相同。在之前的工作中[2][23]，宽松的同步时钟已经被用来进行并发控制。我们已经展示了TrueTime可以从Paxos状态机集合中推导出全球时间。

7. 未来的工作

在过去一年的大部分时间里，我们都是F1团队一起工作，把谷歌的广告后台从MySQL迁移到Spanner。我们正在积极改进它的监控和支撑工具，同时也在优化性能。此外，我们已经开展了大量工作来改进备份/恢复系统的功能和性能。我们当前正在实现Spanner模式语言，二级索引的自动维护和基于负载的自动Resharding。未来，我们会调研更多的特性。我们一直追求以并行的方式进行乐观读，但是以现阶段来看实现这个目标比较难。此外，我们计划最终可以支持直接变更Paxos配置[22][34]。
我们希望许多应用都可以跨越数据中心（彼此距离比较近的数据中心）进行复制。TrueTime 的ε可能会明显地影响性能。我们可以很轻易地把ε值降低到1ms以内。Time-master-query的间隔可以被进一步减少，而且时钟晶体也会越来越好，越来越便宜。Time-master-query延迟会随着网络的改进而减少，或者通过采用分时技术来避免延迟。
最后，还有许多有待改进的方面。虽然Spanner在节点数量上是可扩展的，其节点本地性的数据结构在执行复杂的SQL查询的时候性能会比较差，因为这些数据结构是针对于简单的键值访问的而设计的。数据库文献中的算法和数据结构，可以极大改进单个节点的性能。另外，我们已经准备实现根据客户端负载的变化在数据中心之间自动转移数据的功能，但是，为了有效实现这个功能，我们必须具备在数据中心之间自动、协调地转移客户端应用进程的能力。转移进程会带来更加困难的问题——如何在数据中心之间管理和分配资源。

8. 总结

总的来说，Spanner对来自两个研究团队的思想和结晶进行了结合和扩充：一个是数据库研究团队，包括熟悉易用的半关系接口，事务和基于SQL的查询语言；另一个是系统研究团队，包括可扩展性，自动分区，容错，一致性复制，外部一致性和广域分布式。自从Spanner产品成型之后，我们花费了5年以上的时间来完成当前版本的设计和实现不断完善和迭代。之所以花费这么长的时间，一部分原因在于我们慢慢意识到，Spanner不仅要解决全局复制的命名空间的问题，还应该关注Bigtable中所丢失的数据库特性。
我们的设计中一个亮点就是TrueTime。我们发现承认时间API中的时钟不确定性可以帮助我们构建具备强时间语义的分布式系统。此外，因为底层的系统在时钟不确定性上采用更加严格的边界，实现更强的时间语义的代价就会减少。作为一个研究群体，我们在设计分布式算法时，不再依赖于弱同步的时钟和弱时间API。

参考文献

[1] Azza Abouzeid et al. “HadoopDB: an architectural hybrid of MapReduce and DBMS technologies for analytical workloads”. Proc. of VLDB. 2009, pp. 922–933.
[2] A. Adya et al. “Efficient optimistic concurrency control using loosely synchronized clocks”. Proc. of SIGMOD. 1995, pp. 23–34.
[3] Amazon. Amazon DynamoDB. 2012.
[4] Michael Armbrust et al. “PIQL: Success-Tolerant Query Processing in the Cloud”. Proc. of VLDB. 2011, pp. 181–192.
[5] Jason Baker et al. “Megastore: Providing Scalable, Highly Available Storage for Interactive Services”. Proc. of CIDR. 2011, pp. 223–234.
[6] Hal Berenson et al. “A critique of ANSI SQL isolation levels”. Proc. of SIGMOD. 1995, pp. 1–10.
[7] Matthias Brantner et al. “Building a database on S3”. Proc. of SIGMOD. 2008, pp. 251–264.
[8] A. Chan and R. Gray. “Implementing Distributed Read-Only Transactions”. IEEE TOSE SE-11.2 (Feb. 1985), pp. 205–212.
[9] Fay Chang et al. “Bigtable: A Distributed Storage System for Structured Data”. ACM TOCS 26.2 (June 2008), 4:1–4:26.
[10] Brian F. Cooper et al. “PNUTS: Yahoo!’s hosted data serving platform”. Proc. of VLDB. 2008, pp. 1277–1288.
[11] James Cowling and Barbara Liskov. “Granola: Low-Overhead Distributed Transaction Coordination”. Proc. of USENIX ATC. 2012, pp. 223–236.
[12] Jeffrey Dean and Sanjay Ghemawat. “MapReduce: a flexible data processing tool”. CACM 53.1 (Jan. 2010), pp. 72–77.
[13] John Douceur and Jon Howell. Scalable Byzantine-Fault-Quantifying Clock Synchronization. Tech. rep. MSR-TR-2003-67. MS Research, 2003.
[14] John R. Douceur and Jon Howell. “Distributed directory service in the Farsite file system”. Proc. of OSDI. 2006, pp. 321–334.
[15] Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. “The Google file system”. Proc. of SOSP. Dec. 2003, pp. 29–43.
[16] David K. Gifford. Information Storage in a Decentralized Computer System. Tech. rep. CSL-81-8. PhD dissertation. Xerox PARC, July 1982.
[17] Lisa Glendenning et al. “Scalable consistency in Scatter”. Proc. of SOSP. 2011.
[18] Jim Gray and Leslie Lamport. “Consensus on transaction commit”. ACM TODS 31.1 (Mar. 2006), pp. 133–160.
[19] Pat Helland. “Life beyond Distributed Transactions: an Apostate’s Opinion”. Proc. of CIDR. 2007, pp. 132–141.
[20] Maurice P. Herlihy and Jeannette M. Wing. “Linearizability: a correctness condition for concurrent objects”. ACM TOPLAS 12.3 (July 1990), pp. 463–492.
[21] Leslie Lamport. “The part-time parliament”. ACM TOCS 16.2 (May 1998), pp. 133–169.
[22] Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. “Reconfiguring a state machine”. SIGACT News 41.1 (Mar. 2010), pp. 63–73.
[23] Barbara Liskov. “Practical uses of synchronized clocks in distributed systems”. Distrib. Comput. 6.4 (July 1993), pp. 211–219.
[24] David B. Lomet and Feifei Li. “Improving Transaction-Time DBMS Performance and Functionality”. Proc. of ICDE (2009), pp. 581–591.
[25] Jacob R. Lorch et al. “The SMART way to migrate replicated stateful services”. Proc. of EuroSys. 2006, pp. 103–115.
[26] MarkLogic. MarkLogic 5 Product Documentation. 2012.
[27] Keith Marzullo and Susan Owicki. “Maintaining the time in a distributed system”. Proc. of PODC. 1983, pp. 295–305.
[28] Sergey Melnik et al. “Dremel: Interactive Analysis of Web-Scale Datasets”. Proc. of VLDB. 2010, pp. 330–339.
[29] D.L. Mills. Time synchronization in DCNET hosts. Internet Project Report IEN–173. COMSAT Laboratories, Feb. 1981.
[30] Oracle. Oracle Total Recall. 2012.
[31] Andrew Pavlo et al. “A comparison of approaches to large-scale data analysis”. Proc. of SIGMOD. 2009, pp. 165–178.
[32] Daniel Peng and Frank Dabek. “Large-scale incremental processing using distributed transactions and notifications”. Proc. of OSDI. 2010, pp. 1–15.
[33] Daniel J. Rosenkrantz, Richard E. Stearns, and Philip M. Lewis II. “System level concurrency control for distributed database systems”. ACM TODS 3.2 (June 1978), pp. 178–198.
[34] Alexander Shraer et al. “Dynamic Reconfiguration of Primary/Backup Clusters”. Proc. of SENIX ATC. 2012, pp. 425–438.
[35] Jeff Shute et al. “F1—The Fault-Tolerant Distributed RDBMS Supporting Google’s Ad Business”. Proc. of SIGMOD. May 2012, pp. 777–778.
[36] Yair Sovran et al. “Transactional storage for geo-replicated systems”. Proc. of SOSP. 2011, pp. 385–400.
[37] Michael Stonebraker. Why Enterprises Are Uninterested in NoSQL. 2010.
[38] Michael Stonebraker. Six SQL Urban Myths. 2010.
[39] Michael Stonebraker et al. “The end of an architectural era: (it’s time for a complete rewrite)”. Proc. of VLDB. 2007, pp. 1150–1160.
[40] Alexander Thomson et al. “Calvin: Fast Distributed Transactions for Partitioned Database Systems”. Proc. of SIGMOD.2012, pp. 1–12.
[41] Ashish Thusoo et al. “Hive — A Petabyte Scale Data Warehouse Using Hadoop”. Proc. of ICDE. 2010, pp. 996–1005.
[42] VoltDB. VoltDB Resources. 2012.