Spanner是谷歌公司研发的、可扩展的、多版本、全球分布式、同步复制数据库。它支持外部一致性的分布式事务。本文描述了Spanner的架构、特性、不同设计决策的背后机理和一个新的时间API，这个API可以暴露时钟的不确定性。这个API及其实现，对于支持外部一致性和许多强大特性而言，是非常重要的，这些强大特性包括：非阻塞的读、不采用锁机制的只读事务、原子模式变更。

Spanner是一个可扩展的、全球分布式的数据库，是在谷歌公司设计、开发和部署的。在最高抽象层面，Spanner就是一个数据库，把数据分片存储在许多Paxos[21]状态机上，这些机器位于遍布全球的数据中心内。复制技术可以用来服务于全球可用性和地理局部性。客户端会自动在副本之间进行失败恢复。随着数据的变化和服务器的变化，Spanner会自动把数据进行重新分片，从而有效应对负载变化和处理失败。Spanner被设计成可以扩展到几百万个机器节点，跨越成百上千个数据中心，具备几万亿数据库行的规模。　应用可以借助于Spanner来实现高可用性，通过在一个洲的内部和跨越不同的洲之间复制数据，保证即使面对大范围的自然灾害时数据依然可用。我们最初的客户是F1[35]，一个谷歌广告后台的重新编程实现。F1使用了跨越美国的5个副本。绝大多数其他应用很可能会在属于同一个地理范围内的3-5个数据中心内放置数据副本，采用相对独立的失败模式。也就是说，许多应用都会首先选择低延迟，而不是高可用性，只要系统能够从1-2个数据中心失败中恢复过来。　Spanner的主要工作，就是管理跨越多个数据中心的数据副本，但是，在我们的分布式系统体系架构之上设计和实现重要的数据库特性方面，我们也花费了大量的时间。尽管有许多项目可以很好地使用BigTable[9]，我们也不断收到来自客户的抱怨，客户反映BigTable无法应用到一些特定类型的应用上面，比如具备复杂可变的模式，或者对于在大范围内分布的多个副本数据具有较高的一致性要求。其他研究人员也提出了类似的抱怨[37]。谷歌的许多应用已经选择使用Megastore[5]，主要是因为它的半关系数据模型和对同步复制的支持，尽管Megastore具备较差的写操作吞吐量。由于上述多个方面的因素，Spanner已经从一个类似BigTable的单一版本的键值存储，演化成为一个具有时间属性的多版本的数据库。数据被存储到模式化的、半关系的表中，数据被版本化，每个版本都会自动以提交时间作为时间戳，旧版本的数据会更容易被垃圾回收。应用可以读取旧版本的数据。Spanner支持通用的事务，提供了基于SQL的查询语言。　作为一个全球分布式数据库，Spanner提供了几个有趣的特性：

第一，在数据的副本配置方面，应用可以在一个很细的粒度上进行动态控制。应用可以详细规定，哪些数据中心包含哪些数据，数据距离用户有多远（控制用户读取数据的延迟），不同数据副本之间距离有多远（控制写操作的延迟），以及需要维护多少个副本（控制可用性和读操作性能）。数据也可以被动态和透明地在数据中心之间进行移动，从而平衡不同数据中心内资源的使用。

第二，Spanner有两个重要的特性，很难在一个分布式数据库上实现，即Spanner提供了读和写操作的外部一致性，以及在一个时间戳下面的跨越数据库的全球一致性的读操作。这些特性使得Spanner可以支持一致的备份、一致的MapReduce执行[12]和原子模式变更，所有都是在全球范围内实现，即使存在正在处理中的事务也可以。　之所以可以支持这些特性，是因为Spanner可以为事务分配全球范围内有意义的提交时间戳，即使事务可能是分布式的。这些时间戳反映了事务序列化的顺序。除此以外，这些序列化的顺序满足了外部一致性的要求：如果一个事务T1在另一个事务T2开始之前就已经提交了，那么，T1的时间戳就要比T2的时间戳小。Spanner是第一个可以在全球范围内提供这种保证的系统。　实现这种特性的关键技术就是一个新的TrueTime API及其实现。这个API可以直接暴露时钟不确定性，Spanner时间戳的保证就是取决于这个API实现的界限。如果这个不确定性很大，Spanner就降低速度来等待这个大的不确定性结束。谷歌的簇管理器软件提供了一个TrueTime API的实现。这种实现可以保持较小的不确定性（通常小于10ms），主要是借助于现代时钟参考值（比如GPS和原子钟）。　第2部分描述了Spanner实现的结构、特性集和工程方面的决策；第3部分介绍我们的新的TrueTime API，并且描述了它的实现；第4部分描述了Spanner如何使用TrueTime来实现外部一致性的分布式事务、不用锁机制的只读事务和原子模式更新。第5部分提供了测试Spanner性能和TrueTime行为的测试基准，并讨论了F1的经验。第6、7和8部分讨论了相关工作，并给出总结。

本部分内容描述了Spanner的结构和背后的实现机理，然后描述了目录抽象，它被用来管理副本和局部性，并介绍了数据的转移单位。最后，将讨论我们的数据模型，从而说明，为什么Spanner看起来更加像一个关系数据库，而不是一个键值数据库；还会讨论应用如何可以控制数据的局部性。　一个Spanner部署称为一个universe。假设Spanner在全球范围内管理数据，那么，将会只有可数的、运行中的universe。我们当前正在运行一个测试用的universe，一个部署/线上用的universe和一个只用于线上应用的universe。　Spanner被组织成许多个zone的集合，每个zone都大概像一个BigTable服务器的部署。zone是管理部署的基本单元。zone的集合也是数据可以被复制到的位置的集合。当新的数据中心加入服务，或者老的数据中心被关闭时，zone可以被加入到一个运行的系统中，或者从中移除。zone也是物理隔离的单元，在一个数据中心中，可能有一个或者多个zone，例如，属于不同应用的数据可能必须被分区存储到同一个数据中心的不同服务器集合中。

在一个Spanner的universe中的服务器。一个zone包括一个zonemaster，和一百至几千个spanserver。Zonemaster把数据分配给spanserver，spanserver把数据提供给客户端。客户端使用每个zone上面的location proxy来定位可以为自己提供数据的spanserver。Universe master和placement driver，当前都只有一个。Universe master主要是一个控制台，它显示了关于zone的各种状态信息，可以用于相互之间的调试。Placement driver会周期性地与spanserver进行交互，来发现那些需要被转移的数据，或者是为了满足新的副本约束条件，或者是为了进行负载均衡。

2.1 Spanserver软件栈

本部分内容主要关注spanserver实现，来解释复制和分布式事务是如何被架构到我们的基于BigTable的实现之上的。图1显示了软件栈。在底部，每个spanserver负载管理100-1000个称为tablet的数据结构的实例。一个tablet就类似于BigTable中的tablet，也实现了下面的映射：

与BigTable不同的是，Spanner会把时间戳分配给数据，这种非常重要的方式，使得Spanner更像一个多版本数据库，而不是一个键值存储。一个tablet的状态是存储在类似于B-树的文件集合和写前(write-ahead)的日志中，所有这些都会被保存到一个分布式的文件系统中，这个分布式文件系统被称为Colossus，它继承自Google File System。　为了支持复制，每个spanserver会在每个tablet上面实现一个单个的Paxos状态的机器。一个之前实现的Spanner可以支持在每个tablet上面实现多个Paxos状态机，它可以允许更加灵活的复制配置，但是，这种设计过于复杂，被我们舍弃了。每个状态机器都会在相应的tablet中保存自己的元数据和日志。我们的Paxos实现支持采用基于时间的领导者租约的长寿命的领导者，时间通常在0到10秒之间。当前的Spanner实现中，会对每个Paxos写操作进行两次记录：一次是写入到tablet日志中，一次是写入到Paxos日志中。这种做法只是权宜之计，我们以后会进行完善。我们在Paxos实现上采用了管道化的方式，从而可以在存在广域网延迟时改进Spanner的吞吐量，但是，Paxos会把写操作按照顺序的方式执行。　Paxos状态机是用来实现一系列被一致性复制的映射。每个副本的键值映射状态，都会被保存到相应的tablet中。写操作必须在领导者上初始化Paxos协议，读操作可以直接从底层的任何副本的tablet中访问状态信息，只要这个副本足够新。副本的集合被称为一个Paxos group。　对于每个是领导者的副本而言，每个spanserver会实现一个锁表来实现并发控制。这个锁表包含了两阶段锁机制的状态：它把键的值域映射到锁状态上面。注意，采用一个长寿命的Paxos领导者，对于有效管理锁表而言是非常关键的。在BigTable和Spanner中，我们都专门为长事务做了设计，比如，对于报表操作，可能要持续几分钟，当存在冲突时，采用乐观并发控制机制会表现出很差的性能。对于那些需要同步的操作，比如事务型的读操作，需要获得锁表中的锁，而其他类型的操作则可以不理会锁表。　对于每个扮演领导者角色的副本，每个spanserver也会实施一个事务管理器来支持分布式事务。这个事务管理器被用来实现一个participant leader，该组内的其他副本则是作为participant slaves。如果一个事务只包含一个Paxos组（对于许多事务而言都是如此），它就可以绕过事务管理器，因为锁表和Paxos二者一起可以保证事务性。如果一个事务包含了多于一个Paxos组，那些组的领导者之间会彼此协调合作完成两阶段提交。其中一个参与者组，会被选为协调者，该组的participant leader被称为coordinator leader，该组的participant slaves被称为coordinator slaves。每个事务管理器的状态，会被保存到底层的Paxos组。

2.2 目录和放置

在一系列键值映射的上层，Spanner实现支持一个被称为“目录”的桶抽象，也就是包含公共前缀的连续键的集合。（选择“目录”作为名称，主要是由于历史沿袭的考虑，实际上更好的名称应该是“桶”）。我们会在第2.3节解释前缀的源头。对目录的支持，可以让应用通过选择合适的键来控制数据的局部性。　一个目录是数据放置的基本单元。属于一个目录的所有数据，都具有相同的副本配置。当数据在不同的Paxos组之间进行移动时，会一个目录一个目录地转移，如图2所示。Spanner可能会移动一个目录从而减轻一个Paxos组的负担，也可能会把那些被频繁地一起访问的目录都放置到同一个组中，或者会把一个目录转移到距离访问者更近的地方。当客户端操作正在进行时，也可以进行目录的转移。我们可以预期在几秒内转移50MB的目录。

一个Paxos组可以包含多个目录，这意味着一个Spanner tablet是不同于一个BigTable tablet的。一个Spanner tablet没有必要是一个行空间内按照词典顺序连续的分区，相反，它可以是行空间内的多个分区。我们做出这个决定，是因为这样做可以让多个被频繁一起访问的目录被整合到一起。　Movedir是一个后台任务，用来在不同的Paxos组之间转移目录[14]。Movedir也用来为Paxos组增加和删除副本[25]，因为Spanner目前还不支持在一个Paxos内部进行配置的变更。Movedir并不是作为一个事务来实现，这样可以避免在一个块数据转移过程中阻塞正在进行的读操作和写操作。相反，Movedir会注册一个事实(fact)，表明它要转移数据，然后在后台运行转移数据。当它几乎快要转移完指定数量的数据时，就会启动一个事务来自动转移那部分数据，并且为两个Paxos组更新元数据。　一个目录也是一个应用可以指定的地理复制属性（即放置策略）的最小单元。我们的放置规范语言的设计，把管理复制的配置这个任务单独分离出来。管理员需要控制两个维度：副本的数量和类型，以及这些副本的地理放置属性。他们在这两个维度里面创建了一个命名选项的菜单。通过为每个数据库或单独的目录增加这些命名选项的组合，一个应用就可以控制数据的复制。例如，一个应用可能会在自己的目录里存储每个终端用户的数据，这就有可能使得用户A的数据在欧洲有三个副本，用户B的数据在北美有5个副本。　为了表达的清晰性，我们已经做了尽量简化。事实上，当一个目录变得太大时，Spanner会把它分片存储。每个分片可能会被保存到不同的Paxos组上（因此就意味着来自不同的服务器）。Movedir在不同组之间转移的是分片，而不是转移整个目录。

2.3 数据模型

Spanner会把下面的数据特性集合暴露给应用：基于模式化的半关系表的数据模型，查询语言和通用事务。支持这些特性的动机，是受到许多因素驱动的。需要支持模式化的半关系表是由Megastore[5]的普及来支持的。在谷歌内部至少有300个应用使用Megastore（尽管它具有相对低的性能），因为它的数据模型要比BigTable简单，更易于管理，并且支持在跨数据中心层面进行同步复制。BigTable只可以支持跨数据中心的最终事务一致性。使用Megastore的著名的谷歌应用是Gmail,Picasa,Calendar,Android Market, AppEngine。在Spanner中需要支持SQL类型的查询语言，也很显然是非常必要的，因为Dremel[28]作为交互式分析工具已经非常普及。最后，在BigTable中跨行事务的缺乏来导致了用户频繁的抱怨；Percolator[32]的开发就是用来部分解决这个问题的。一些作者都在抱怨，通用的两阶段提交的代价过于昂贵，因为它会带来可用性问题和性能问题[9][10][19]。我们认为，最好让应用程序开发人员来处理由于过度使用事务引起的性能问题，而不是总是围绕着“缺少事务”进行编程。在Paxos上运行两阶段提交弱化了可用性问题。　应用的数据模型是架构在被目录桶装的键值映射层之上。一个应用会在一个universe中创建一个或者多个数据库。每个数据库可以包含无限数量的模式化的表。每个表都和关系数据库表类似，具备行、列和版本值。我们不会详细介绍Spanner的查询语言，它看起来很像SQL，只是做了一些扩展。　Spanner的数据模型不是纯粹关系型的，它的行必须有名称。更准确地说，每个表都需要有包含一个或多个主键列的排序集合。这种需求，让Spanner看起来仍然有点像键值存储：主键形成了一个行的名称，每个表都定义了从主键列到非主键列的映射。当一个行存在时，必须要求已经给行的一些键定义了一些值（即使是NULL）。采用这种结构是很有用的，因为这可以让应用通过选择键来控制数据的局部性。

图3包含了一个Spanner模式的实例，它是以每个用户和每个相册为基础存储图片元数据。这个模式语言和Megastore的类似，同时增加了额外的要求，即每个Spanner数据库必须被客户端分割成一个或多个表的层次结构（hierarchy）。客户端应用会使用INTERLEAVE IN语句在数据库模式中声明这个层次结构。这个层次结构上面的表，是一个目录表。目录表中的每行都具有键K，和子孙表中的所有以K开始（以字典顺序排序）的行一起，构成了一个目录。ON DELETE CASCADE意味着，如果删除目录中的一个行，也会级联删除所有相关的子孙行。这个图也解释了这个实例数据库的交织层次（interleaved layout），例如Albums(2,1)代表了来自Albums表的、对应于user_id=2和album_id=1的行。这种表的交织层次形成目录，是非常重要的，因为它允许客户端来描述存在于多个表之间的位置关系，这对于一个分片的分布式数据库的性能而言是很重要的。没有它的话，Spanner就无法知道最重要的位置关系。

本部分内容描述TrueTime如何可以用来保证并发控制的正确性，以及这些属性如何用来实现一些关键特性，比如外部一致性的事务、无锁机制的只读事务、针对历史数据的非阻塞读。这些特性可以保证，在时间戳为t的时刻的数据库读操作，一定只能看到在t时刻之前已经提交的事务。　进一步说，把Spanner客户端的写操作和Paxos看到的写操作这二者进行区分，是非常重要的，我们把Paxos看到的写操作称为Paxos写操作。例如，两阶段提交会为准备提交阶段生成一个Paxos写操作，这时不会有相应的客户端写操作。

总的来说，Spanner对来自两个研究群体的概念进行了结合和扩充：一个是数据库研究群体，包括熟悉易用的半关系接口，事务和基于SQL的查询语言；另一个是系统研究群体，包括可扩展性，自动分区，容错，一致性复制，外部一致性和大范围分布。自从Spanner概念成形，我们花费了5年以上的时间来完成当前版本的设计和实现。花费这么长的时间，一部分原因在于我们慢慢意识到，Spanner不应该仅仅解决全球复制的命名空间问题，而且也应该关注Bigtable中所丢失的数据库特性。