Spanner:Google’sGlobally-DistributedDatabase
JamesC.Corbett,JeffreyDean,MichaelEpstein,AndrewFikes,ChristopherFrost,JJFurman,SanjayGhemawat,AndreyGubarev,ChristopherHeiser,PeterHochschild,WilsonHsieh,SebastianKanthak,EugeneKogan,HongyiLi,AlexanderLloyd,SergeyMelnik,DavidMwaura,DavidNagle,SeanQuinlan,RajeshRao,LindsayRolig,YasushiSaito,MichalSzymaniak,ChristopherTaylor,RuthWang,DaleWoodford
GoogleInc.
[请到本网页的底部的“附件”中下载：GoogleSpanner的英文版原文和中文版的PDF文件]
中文关键词：谷歌，分布式数据库
英文关键词:Google,Spanner,Bigtable,DistributedDatabase
全文目录结构
本部分内容描述了Spanner的结构和背后的实现机理，然后描述了目录抽象，它被用来管理副本和局部性，并介绍了数据的转移单位。最后，将讨论我们的数据模型，从而说明，为什么Spanner看起来更加像一个关系数据库，而不是一个键值数据库；还会讨论应用如何可以控制数据的局部性。
一个Spanner部署称为一个universe。假设Spanner在全球范围内管理数据，那么，将会只有可数的、运行中的universe。我们当前正在运行一个测试用的universe，一个部署/线上用的universe和一个只用于线上应用的universe。
Spanner被组织成许多个zone的集合，每个zone都大概像一个BigTable服务器的部署。zone是管理部署的基本单元。zone的集合也是数据可以被复制到的位置的集合。当新的数据中心加入服务，或者老的数据中心被关闭时，zone可以被加入到一个运行的系统中，或者从中移除。zone也是物理隔离的单元，在一个数据中心中，可能有一个或者多个zone，例如，属于不同应用的数据可能必须被分区存储到同一个数据中心的不同服务器集合中。
图1显示了在一个Spanner的universe中的服务器。一个zone包括一个zonemaster，和一百至几千个spanserver。Zonemaster把数据分配给spanserver，spanserver把数据提供给客户端。客户端使用每个zone上面的locationproxy来定位可以为自己提供数据的spanserver。Universemaster和placementdriver，当前都只有一个。Universemaster主要是一个控制台，它显示了关于zone的各种状态信息，可以用于相互之间的调试。Placementdriver会周期性地与spanserver进行交互，来发现那些需要被转移的数据，或者是为了满足新的副本约束条件，或者是为了进行负载均衡。
(key:string,timestamp:int64)->string
Paxos状态机是用来实现一系列被一致性复制的映射。每个副本的键值映射状态，都会被保存到相应的tablet中。写操作必须在领导者上初始化Paxos协议，读操作可以直接从底层的任何副本的tablet中访问状态信息，只要这个副本足够新。副本的集合被称为一个Paxosgroup。
对于每个是领导者的副本而言，每个spanserver会实现一个锁表来实现并发控制。这个锁表包含了两阶段锁机制的状态：它把键的值域映射到锁状态上面。注意，采用一个长寿命的Paxos领导者，对于有效管理锁表而言是非常关键的。在BigTable和Spanner中，我们都专门为长事务做了设计，比如，对于报表操作，可能要持续几分钟，当存在冲突时，采用乐观并发控制机制会表现出很差的性能。对于那些需要同步的操作，比如事务型的读操作，需要获得锁表中的锁，而其他类型的操作则可以不理会锁表。
对于每个扮演领导者角色的副本，每个spanserver也会实施一个事务管理器来支持分布式事务。这个事务管理器被用来实现一个participantleader，该组内的其他副本则是作为participantslaves。如果一个事务只包含一个Paxos组（对于许多事务而言都是如此），它就可以绕过事务管理器，因为锁表和Paxos二者一起可以保证事务性。如果一个事务包含了多于一个Paxos组，那些组的领导者之间会彼此协调合作完成两阶段提交。其中一个参与者组，会被选为协调者，该组的participantleader被称为coordinatorleader，该组的participantslaves被称为coordinatorslaves。每个事务管理器的状态，会被保存到底层的Paxos组。
在一系列键值映射的上层，Spanner实现支持一个被称为“目录”的桶抽象，也就是包含公共前缀的连续键的集合。（选择“目录”作为名称，主要是由于历史沿袭的考虑，实际上更好的名称应该是“桶”）。我们会在第2.3节解释前缀的源头。对目录的支持，可以让应用通过选择合适的键来控制数据的局部性。
一个目录是数据放置的基本单元。属于一个目录的所有数据，都具有相同的副本配置。当数据在不同的Paxos组之间进行移动时，会一个目录一个目录地转移，如图3所示。Spanner可能会移动一个目录从而减轻一个Paxos组的负担，也可能会把那些被频繁地一起访问的目录都放置到同一个组中，或者会把一个目录转移到距离访问者更近的地方。当客户端操作正在进行时，也可以进行目录的转移。我们可以预期在几秒内转移50MB的目录。
一个Paxos组可以包含多个目录，这意味着一个Spannertablet是不同于一个BigTabletablet的。一个Spannertablet没有必要是一个行空间内按照词典顺序连续的分区，相反，它可以是行空间内的多个分区。我们做出这个决定，是因为这样做可以让多个被频繁一起访问的目录被整合到一起。
Movedir是一个后台任务，用来在不同的Paxos组之间转移目录[14]。Movedir也用来为Paxos组增加和删除副本[25]，因为Spanner目前还不支持在一个Paxos内部进行配置的变更。Movedir并不是作为一个事务来实现，这样可以避免在一个块数据转移过程中阻塞正在进行的读操作和写操作。相反，Movedir会注册一个事实(fact)，表明它要转移数据，然后在后台运行转移数据。当它几乎快要转移完指定数量的数据时，就会启动一个事务来自动转移那部分数据，并且为两个Paxos组更新元数据。
一个目录也是一个应用可以指定的地理复制属性（即放置策略）的最小单元。我们的放置规范语言的设计，把管理复制的配置这个任务单独分离出来。管理员需要控制两个维度：副本的数量和类型，以及这些副本的地理放置属性。他们在这两个维度里面创建了一个命名选项的菜单。通过为每个数据库或单独的目录增加这些命名选项的组合，一个应用就可以控制数据的复制。例如，一个应用可能会在自己的目录里存储每个终端用户的数据，这就有可能使得用户A的数据在欧洲有三个副本，用户B的数据在北美有5个副本。
为了表达的清晰性，我们已经做了尽量简化。事实上，当一个目录变得太大时，Spanner会把它分片存储。每个分片可能会被保存到不同的Paxos组上（因此就意味着来自不同的服务器）。Movedir在不同组之间转移的是分片，而不是转移整个目录。
Spanner会把下面的数据特性集合暴露给应用：基于模式化的半关系表的数据模型，查询语言和通用事务。支持这些特性的动机，是受到许多因素驱动的。需要支持模式化的半关系表是由Megastore[5]的普及来支持的。在谷歌内部至少有300个应用使用Megastore（尽管它具有相对低的性能），因为它的数据模型要比BigTable简单，更易于管理，并且支持在跨数据中心层面进行同步复制。BigTable只可以支持跨数据中心的最终事务一致性。使用Megastore的著名的谷歌应用是Gmail,Picasa,Calendar,AndroidMarket,AppEngine。在Spanner中需要支持SQL类型的查询语言，也很显然是非常必要的，因为Dremel[28]作为交互式分析工具已经非常普及。最后，在BigTable中跨行事务的缺乏来导致了用户频繁的抱怨；Percolator[32]的开发就是用来部分解决这个问题的。一些作者都在抱怨，通用的两阶段提交的代价过于昂贵，因为它会带来可用性问题和性能问题[9][10][19]。我们认为，最好让应用程序开发人员来处理由于过度使用事务引起的性能问题，而不是总是围绕着“缺少事务”进行编程。在Paxos上运行两阶段提交弱化了可用性问题。
应用的数据模型是架构在被目录桶装的键值映射层之上。一个应用会在一个universe中创建一个或者多个数据库。每个数据库可以包含无限数量的模式化的表。每个表都和关系数据库表类似，具备行、列和版本值。我们不会详细介绍Spanner的查询语言，它看起来很像SQL，只是做了一些扩展。
Spanner的数据模型不是纯粹关系型的，它的行必须有名称。更准确地说，每个表都需要有包含一个或多个主键列的排序集合。这种需求，让Spanner看起来仍然有点像键值存储：主键形成了一个行的名称，每个表都定义了从主键列到非主键列的映射。当一个行存在时，必须要求已经给行的一些键定义了一些值（即使是NULL）。采用这种结构是很有用的，因为这可以让应用通过选择键来控制数据的局部性。
进一步说，把Spanner客户端的写操作和Paxos看到的写操作这二者进行区分，是非常重要的，我们把Paxos看到的写操作称为Paxos写操作。例如，两阶段提交会为准备提交阶段生成一个Paxos写操作，这时不会有相应的客户端写操作。
林子雨注：上面是GoogleSpanner（中文版）的核心内容，第4节“并发控制”的剩余内容，没有在网页中给出，而是放在PDF文件中（请到本网页的底部“附件”中下载PDF文件），因为，第4节“并发控制”的剩余内容，公式太多，无法放入网页。而且，根据本人的阅读，上述给出的内容已经可以帮助读者基本了解GoogleSpanner的概貌，剩余的内容是一些琐碎的细节，个人感觉读起来比较晦涩，如果不是深入研究需要，可以不用继续阅读第4节“并发控制”的剩余内容。
我们对Spanner性能进行了测试，包括复制、事务和可用性。然后，我们提供了一些关于TrueTime的实验数据，并且提供了我们的第一个用例——F1。
表3给出了一个用于Spanner的微测试基准(microbenchmark)。这些测试是在分时机器上实现的：每个spanserver采用4GB内存和四核CPU（AMDBarcelona2200MHz）。客户端运行在单独的机器上。每个zone都包含一个spanserver。客户端和zone都放在一个数据中心集合内，它们之间的网络距离不会超过1ms。（这种布局是很普通的，许多数据并不需要把数据分散存储到全球各地）。测试数据库具有50个Paxos组和2500个目录。操作都是独立的4KB大小的读和写。Allreadswereservedoutofmemoryafteracompaction，从而使得我们只需要衡量Spanner调用栈的开销。此外，还会进行一轮读操作，来预热任何位置的缓存。
对于延迟实验而言，客户端会发起足够少量的操作，从而避免在服务器中发生排队。从1个副本的实验中，提交等待大约是5ms，Paxos延迟大约是9ms。随着副本数量的增加，延迟大约保持不变，只具有很少的标准差，因为在一个组的副本内，Paxos会并行执行。随着副本数量的增加，获得指定投票数量的延迟，对一个slave副本的慢速度不会很敏感。
表4显示了两阶段提交可以扩展到合理数量的参与者：它是对一系列实验的总结，这些实验运行在3个zone上，每个zone具有25个spanserver。扩展到50个参与者，无论在平均值还是第99个百分位方面，都是合理的。在100个参与者的情形下，延迟开始明显增加。
关于TrueTime，必须回答两个问题：ε是否就是时钟不确定性的边界？ε会变得多糟糕？对于第一个问题，最严峻的问题就是，如果一个局部的时钟漂移大于200us/sec，那就会破坏TrueTime的假设。我们的机器统计数据显示，坏的CPU的出现概率要比坏的时钟出现概率大6倍。也就是说，与更加严峻的硬件问题相比，时钟问题是很少见的。由此，我们也相信，TrueTime的实现和Spanner其他软件组件一样，具有很好的可靠性，值得信任。
图6显示了TrueTime数据，是从几千个spanserver中收集的，这些spanserver跨越了多个数据中心，距离2200公里以上。图中描述了ε的第90个、99个和99.9个百分位的情况，是在对timemaster进行投票后立即对timeslavedaemon进行样本抽样的。这些抽样数据没有考虑由于时钟不确定性带来的ε值的锯齿，因此测量的是timemaster不确定性（通常是0）再加上通讯延迟。
图6中的数据显示了，在决定ε的基本值方面的上述两个问题，通常都不会是个问题。但是，可能会存在明显的拖尾延迟问题，那会引起更高的ε值。图中，3月30日拖尾延迟的降低，是因为网络的改进，减少了瞬间网络连接的拥堵。在4月13日ε的值增加了，持续了大约1个小时，主要是因为例行维护时关闭了两个timemaster。我们会继续调研并且消除引起TrueTime突变的因素。
F1团队选择使用Spanner有几个方面的原因。首先，Spanner不需要手工分区。其次，Spanner提供了同步复制和自动失败恢复。在采用MySQL的master-slave复制方法时，很难进行失败恢复，会有数据丢失和当机的风险。再次，F1需要强壮的事务语义，这使得使用其他NoSQL系统是不实际的。应用语义需要跨越任意数据的事务和一致性读。F1团队也需要在他们的数据上构建二级索引（因为Spanner没有提供对二级索引的自动支持），也有能力使用Spanner事务来实现他们自己的一致性全球索引。
所有应用写操作，现在都是默认从F1发送到Spanner。而不是发送到基于MySQL的应用栈。F1在美国的西岸有两个副本，在东岸有三个副本。这种副本位置的选择，是为了避免发生自然灾害时出现服务停止问题，也是出于前端应用的位置的考虑。实际上，Spanner的失败自动恢复，几乎是不可见的。在过去的几个月中，尽管有不在计划内的机群失效，但是，F1团队最需要做的工作仍然是更新他们的数据库模式，来告诉Spanner在哪里放置Paxos领导者，从而使得它们尽量靠近应用前端。
表5显示了F1中每个目录的分片数量的分布情况。每个目录通常对应于F1上的应用栈中的一个用户。绝大多数目录（同时意味着绝大多数用户）都只会包含一个分片，这就意味着，对于这些用户数据的读和写操作只会发生在一个服务器上。多于100个分片的目录，是那些包含F1二级索引的表：对这些表的多个分片进行写操作，是极其不寻常的。F1团队也只是在以事务的方式进行未经优化的批量数据加载时，才会碰到这种情形。
表6显示了从F1服务器来测量的Spanner操作的延迟。在东海岸数据中心的副本，在选择Paxos领导者方面会获得更高的优先级。表6中的数据是从这些数据中心的F1服务器上测量得到的。写操作延迟分布上存在较大的标准差，是由于锁冲突引起的肥尾效应（fattail）。在读操作延迟分布上存在更大的标准差，部分是因为Paxos领导者跨越了两个数据中心，只有其中的一个是采用了固态盘的机器。此外，测试内容还包括系统中的每个针对两个数据中心的读操作：字节读操作的平均值和标准差分别是1.6KB和119KB。
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的键值存储，可以在一致性复制上面实现事务。Spanner则要比Scatter在更高的层次上提供接口。Gray和Lamport[18]描述了一个基于Paxos的非阻塞的提交协议，他们的协议会比两阶段提交协议带来更多的代价，而两阶段提交协议在大范围分布式的组中的代价会进一步恶化。Walter[36]提供了一个快照隔离的变种，但是无法跨越数据中心。相反，我们的只读事务提供了一个更加自然的语义，因为，我们对于所有的操作都支持外部语义。
我们希望许多应用都可以跨越数据中心进行复制，并且这些数据中心彼此靠近。TrueTimeε可能会明显影响性能。把ε值降低到1ms以内，并不存在不可克服的障碍。Time-master-query间隔可以继续减少，Time-master-query延迟应该随着网络的改进而减少，或者通过采用分时技术来避免延迟。
许多人帮助改进了这篇论文：JonHowell，AtulAdya,FayChang,FrankDabek,SeanDorward,BobGruber,DavidHeld,NickKline,AlexThomson,andJoelWein.我们的管理层对于我们的工作和论文发表都非常支持：AristotleBalogh,BillCoughran,UrsH¨olzle,DoronMeyer,CosNicolaou,KathyPolizzi,SridharRamaswany,andShivakumarVenkataraman.
我们的工作是在Bigtable和Megastore团队的工作基础之上开展的。F1团队，尤其是JeffShute
，和我们一起工作，开发了数据模型，跟踪性能和纠正漏洞。Platforms团队，尤其是LuizBarroso和BobFelderman，帮助我们一起实现了TrueTime。最后，许多谷歌员工都曾经在我们的团队工作过，包括KenAshcraft,PaulCychosz,KrzysztofOstrowski,AmirVoskoboynik,MatthewWeaver,TheoVassilakis,andEricVeach;orhavejoinedourteamrecently:NathanBales,AdamBeberg,VadimBorisov,KenChen,BrianCooper,CianCullinan,Robert-JanHuijsman,MilindJoshi,AndreyKhorlin,DawidKuroczko,LaramieLeavitt,EricLi,MikeMammarella,SunilMushran,SimonNielsen,OvidiuPlaton,AnanthShrinivas,VadimSuvorov,andMarcelvanderHolst.
[1]AzzaAbouzeidetal.“HadoopDB:anarchitecturalhybridofMapReduceandDBMStechnologiesforanalyticalworkloads”.Proc.ofVLDB.2009,pp.922–933.
[2]A.Adyaetal.“Efficientoptimisticconcurrencycontrolusinglooselysynchronizedclocks”.Proc.ofSIGMOD.1995,pp.23–34.
[3]Amazon.AmazonDynamoDB.2012.
[4]MichaelArmbrustetal.“PIQL:Success-TolerantQueryProcessingintheCloud”.Proc.ofVLDB.2011,pp.181–192.
[5]JasonBakeretal.“Megastore:ProvidingScalable,HighlyAvailableStorageforInteractiveServices”.Proc.ofCIDR.2011,pp.223–234.
[6]HalBerensonetal.“AcritiqueofANSISQLisolationlevels”.Proc.ofSIGMOD.1995,pp.1–10.
[7]MatthiasBrantneretal.“BuildingadatabaseonS3”.Proc.ofSIGMOD.2008,pp.251–264.
[8]A.ChanandR.Gray.“ImplementingDistributedRead-OnlyTransactions”.IEEETOSESE-11.2(Feb.1985),pp.205–212.
[9]FayChangetal.“Bigtable:ADistributedStorageSystemforStructuredData”.ACMTOCS26.2(June2008),4:1–4:26.
[10]BrianF.Cooperetal.“PNUTS:Yahoo!’shosteddataservingplatform”.Proc.ofVLDB.2008,pp.1277–1288.
[11]JamesCowlingandBarbaraLiskov.“Granola:Low-OverheadDistributedTransactionCoordination”.Proc.ofUSENIXATC.2012,pp.223–236.
[12]JeffreyDeanandSanjayGhemawat.“MapReduce:aflexibledataprocessingtool”.CACM53.1(Jan.2010),pp.72–77.
[13]JohnDouceurandJonHowell.ScalableByzantine-Fault-QuantifyingClockSynchronization.Tech.rep.MSR-TR-2003-67.MSResearch,2003.
[14]JohnR.DouceurandJonHowell.“DistributeddirectoryserviceintheFarsitefilesystem”.Proc.ofOSDI.2006,pp.321–334.
[15]SanjayGhemawat,HowardGobioff,andShun-TakLeung.“TheGooglefilesystem”.Proc.ofSOSP.Dec.2003,pp.29–43.
[16]DavidK.Gifford.InformationStorageinaDecentralizedComputerSystem.Tech.rep.CSL-81-8.PhDdissertation.XeroxPARC,July1982.
[17]LisaGlendenningetal.“ScalableconsistencyinScatter”.Proc.ofSOSP.2011.
[18]JimGrayandLeslieLamport.“Consensusontransactioncommit”.ACMTODS31.1(Mar.2006),pp.133–160.
[19]PatHelland.“LifebeyondDistributedTransactions:anApostate’sOpinion”.Proc.ofCIDR.2007,pp.132–141.
[20]MauriceP.HerlihyandJeannetteM.Wing.“Linearizability:acorrectnessconditionforconcurrentobjects”.ACMTOPLAS12.3(July1990),pp.463–492.
[21]LeslieLamport.“Thepart-timeparliament”.ACMTOCS16.2(May1998),pp.133–169.
[22]LeslieLamport,DahliaMalkhi,andLidongZhou.“Reconfiguringastatemachine”.SIGACTNews41.1(Mar.2010),pp.63–73.
[23]BarbaraLiskov.“Practicalusesofsynchronizedclocksindistributedsystems”.Distrib.Comput.6.4(July1993),pp.211–219.
[24]DavidB.LometandFeifeiLi.“ImprovingTransaction-TimeDBMSPerformanceandFunctionality”.Proc.ofICDE(2009),pp.581–591.
[25]JacobR.Lorchetal.“TheSMARTwaytomigratereplicatedstatefulservices”.Proc.ofEuroSys.2006,pp.103–115.
[26]MarkLogic.MarkLogic5ProductDocumentation.2012.
[27]KeithMarzulloandSusanOwicki.“Maintainingthetimeinadistributedsystem”.Proc.ofPODC.1983,pp.295–305.
[28]SergeyMelniketal.“Dremel:InteractiveAnalysisofWeb-ScaleDatasets”.Proc.ofVLDB.2010,pp.330–339.
[29]D.L.Mills.TimesynchronizationinDCNEThosts.InternetProjectReportIEN–173.COMSATLaboratories,Feb.1981.
[30]Oracle.OracleTotalRecall.2012.
[31]AndrewPavloetal.“Acomparisonofapproachestolarge-scaledataanalysis”.Proc.ofSIGMOD.2009,pp.165–178.
[32]DanielPengandFrankDabek.“Large-scaleincrementalprocessingusingdistributedtransactionsandnotifications”.Proc.ofOSDI.2010,pp.1–15.
[33]DanielJ.Rosenkrantz,RichardE.Stearns,andPhilipM.LewisII.“Systemlevelconcurrencycontrolfordistributeddatabasesystems”.ACMTODS3.2(June1978),pp.178–198.
[34]AlexanderShraeretal.“DynamicReconfigurationofPrimary/BackupClusters”.Proc.ofSENIXATC.2012,pp.425–438.
[35]JeffShuteetal.“F1—TheFault-TolerantDistributedRDBMSSupportingGoogle’sAdBusiness”.Proc.ofSIGMOD.May2012,pp.777–778.
[36]YairSovranetal.“Transactionalstorageforgeo-replicatedsystems”.Proc.ofSOSP.2011,pp.385–400.
[37]MichaelStonebraker.WhyEnterprisesAreUninterestedinNoSQL.2010.
[38]MichaelStonebraker.SixSQLUrbanMyths.2010.
[39]MichaelStonebrakeretal.“Theendofanarchitecturalera:(it’stimeforacompleterewrite)”.Proc.ofVLDB.2007,pp.1150–1160.
[40]AlexanderThomsonetal.“Calvin:FastDistributedTransactionsforPartitionedDatabaseSystems”.Proc.ofSIGMOD.2012,pp.1–12.
[41]AshishThusooetal.“Hive—APetabyteScaleDataWarehouseUsingHadoop”.Proc.ofICDE.2010,pp.996–1005.