緣起

最近研究Spanner粪滤，發(fā)現(xiàn)國內(nèi)對Spanner論文的翻譯很多昙篙，但是美中不足的是设哗，每個人都在做論文的搬運工和翻譯者吮铭，沒有加入自己的思考和設想绞旅，實在是令人悲哀。因此決定自己去重新閱讀和理解Spanner的論文，加入自己的思考，重新理解Spanner的精髓和思想营勤。
本文翻譯過程中參考了前人對Spanner論文的翻譯和理解，對其翻譯欠失真或者語義不同的地方進行了改進壹罚，并加入了自己的思考葛作。
感謝前人做的工作。

摘要

Spanner是谷歌研發(fā)的可橫向擴展的猖凛、支持多版本的赂蠢、可在全球范圍進行分布式部署的、同步進行數(shù)據(jù)復制的分布式數(shù)據(jù)庫形病。Spanner是世界上第一個可以在全球范圍內(nèi)進行數(shù)據(jù)分布式管理并且支持外部一致性分布式事務的數(shù)據(jù)庫產(chǎn)品客年。這篇論文描述了Spanner的基礎架構、功能特性漠吻、各種設計背后的基本原理和一個新穎的時間API（這個時間API在承認并且暴露了時間的不確定性）量瓜。Spanner中分布式事務的外部一致性和很多重要的特性（例如：歷史數(shù)據(jù)的非阻塞讀、無鎖只讀事務和schema信息的原子性變更等）均依賴于這個時間API途乃。

1 簡介

Spanner是谷歌設計绍傲、構建和部署的、可橫向擴展的耍共、全球分布式數(shù)據(jù)庫烫饼。從一個最高的抽象層級來看，Spanner將數(shù)據(jù)散布在很多Paxos [21] 的狀態(tài)機中试读，這些 Paxos 狀態(tài)機位于遍布在全球的數(shù)據(jù)中心里杠纵。 通過Replication保證全球可用性和數(shù)據(jù)的就近訪問（數(shù)據(jù)本地性）；Spanner的Client端可以在多個副本之間自動完成故障切換钩骇，并自動從故障的副本重新定向到正常的副本上進行數(shù)據(jù)訪問比藻。當數(shù)據(jù)量或者服務器的數(shù)據(jù)發(fā)生變化的時候Spanner可以自動完成數(shù)據(jù)在狀態(tài)機之間的重分布，并且Spanner還自動在多個狀態(tài)機之間（甚至可以在多個數(shù)據(jù)中心之間）進行數(shù)據(jù)遷移從而進行負載均衡和故障處理倘屹。 Spanner被設計為：可擴展到跨數(shù)百個數(shù)據(jù)中心的上百個服務器银亲，并且可以處理和管理數(shù)萬億數(shù)據(jù)行數(shù)據(jù)。
應用程序在使用Spanner的時候纽匙，即使面臨大范圍的自然災害也可以借助于Spanner中跨大陸的數(shù)據(jù)復制機制來實現(xiàn)數(shù)據(jù)庫服務的高可用务蝠。Spanner的第一個用戶是F1 [35],F1是對Google廣告后臺服務的重新實現(xiàn)。F1在Spanner中的數(shù)據(jù)在美國國內(nèi)部署了5個副本烛缔。
大多數(shù)其他的應用會在一個地理區(qū)域內(nèi)的3到5個數(shù)據(jù)中心之間放置數(shù)據(jù)副本馏段，但是高可用性相對就會比較弱。也就是對于大部分的應用來說践瓷，只要能夠從1-2個數(shù)據(jù)中心不可用情況下進行服務恢復毅弧，相對于高可用而言，他們更傾向于保證低延時当窗。
Spanner的主要工作就是管理跨數(shù)據(jù)中心的數(shù)據(jù)副本够坐，但是我們基于分布式系統(tǒng)基礎架構也花費的很大的時間和精力來設計和實現(xiàn)重要的數(shù)據(jù)庫功能特性。雖然在google內(nèi)部有很多項目都在很愉快地使用Bigtable [9]崖面，我們還是會不斷的收到來自于Bigtable的用戶的抱怨元咙，這些客戶抱怨Bigtable 無法很好的服務于一些應用：Schema很復雜且多變的應用或者對跨地域復制具有強一致性要求的應用(其他的用戶也有類似的抱怨 [37]) 。在Google內(nèi)部的很多應用選擇使用巫员，雖然在Google Megastore 的寫入吞吐量比較低庶香，但是由于其半關系型數(shù)據(jù)模型和對同步復制的支持，很多應用仍然選擇使用 Megastore [5]简识。因此Spanner已經(jīng)從一個類似BigTable的多版本的Key-Value存儲演變成了一個帶有時間屬性的多版本數(shù)據(jù)庫赶掖。 數(shù)據(jù)存儲在模式化的半關系型存儲表中感猛；通過不同的提交時間戳將數(shù)據(jù)劃分為不同的版本；根據(jù)配置的不同的垃圾回收策略奢赂，對不同的老版本的數(shù)據(jù)進行垃圾回收陪白；并且應用也可以通過指定特定的時間戳讀取老版本的數(shù)據(jù)。Spanner支持通用的事務膳灶，并且提供了基于SQL的查詢語句咱士。
作為一個全球范圍的分布式數(shù)據(jù)庫，Spanner提供了一些很有意思的特性轧钓。
第一：應用程序可以在很細的粒度上對數(shù)據(jù)的副本數(shù)進行動態(tài)的控制序厉。應用程序可以指定：
【1】哪些數(shù)據(jù)中心包含哪些數(shù)據(jù)
【2】數(shù)據(jù)離用戶多遠（為了保證讀延時）
【3】每個數(shù)據(jù)副本之間的距離有多遠（為了保證寫延時）
【4】總共維護多少個數(shù)據(jù)副本（為了保證可用性和讀性能）
數(shù)據(jù)也可以在不同的數(shù)據(jù)中心之間動態(tài)地、透明地來回遷移毕箍，從而能夠動態(tài)地平衡各個數(shù)據(jù)中心的資源使用率弛房。
第二：Spanner還具備兩個獨有的特性：提供外部一致性[16]讀寫和基于某個時間戳的跨數(shù)據(jù)庫的全球一致性讀。這兩個特性使得Spanner可以在全球范圍內(nèi)或者在事務正在執(zhí)行的同時都可以執(zhí)行一致性備份而柑、一致性MapReduce執(zhí)行[12]和原子性Schema信息變更庭再。
這些特性得益于Spanner對于所有的事務（即使是分布式事務）都賦予全球范圍一致的時間戳。時間戳反映了序列化的順序牺堰。此外這種序列化順序也滿足了外部一致性（冪等性拄轻，線性化[20]）的要求；若事務T1在另一個事務T2之前提交伟葫，那么T1的提交時間就要被T2的提交時間要小恨搓。Spanner是第一個在全球范圍內(nèi)提交這種保證的系統(tǒng)。
實現(xiàn)這種保證的關鍵就是一個全新的TrueTime API筏养。該API直接提供一個不確定時鐘斧抱，而Spanner對事務順序性的保證就依賴于不確定時鐘的波動邊界。若時鐘的波動時間窗口很大渐溶，則Spanner就會一直等待直到晚于不確定時鐘的波動時間窗口的最后時間再做后續(xù)處理辉浦，如下圖所示：

這個TrueTime API由谷歌的集群管理軟件實現(xiàn)并提供，其通過多時鐘值參考對比（GPS和原子鐘）茎辐，選出相對而言最準確的時鐘值宪郊，從而保證不確定時鐘的時間窗口的寬度足夠小（通常小于10ms）拖陆。
本文的第二部分描述了Spanner的架構弛槐、特性和工程設計決策。第三部分描述了新的TrueTime API以及該TrueTime API的大體實現(xiàn)依啰。第四部分說明了spanner如何利用TrueTime API來實現(xiàn)分布式事務的外部一致性乎串，無鎖只讀事務和Schema的原子性變更。第五部分提供了Spanner和True Time API的benchmark性能基準測試報告并討論了F1速警。第6,7,8部分說明了未來的一些相關工作計劃和文章總結叹誉。

2 實現(xiàn)

本節(jié)描述了Spanner的架構和底層實現(xiàn)原理鸯两，并對spanner中的目錄進行了詳細說明，Spanner通過目錄來管理數(shù)據(jù)的副本和本地性长豁，目錄也是spanner中數(shù)據(jù)異動的基本單元钧唐。本節(jié)最后將會討論Spanner的數(shù)據(jù)模型，并說明為什么Spanner看起來更像是一個關系型數(shù)據(jù)庫蕉斜，而不是key-value存儲逾柿，以及應用程序如何控制數(shù)據(jù)的本地性缀棍。
一個Spanner集群的部署我們稱之為一個Universe宅此。若Spanner管理全球范圍的數(shù)據(jù)，那么Spanner Universe的個數(shù)并不會很多爬范。我們目前運行了一個測試環(huán)境Universe父腕、一個預發(fā)布Universe和一個生產(chǎn)環(huán)境Universe。
一個Spanner的Universe由一系列的Zone組成青瀑，每個Zone相當于一個BigTable的一個部署集群[9]璧亮。Zone是Spanner部署管理的基本單元。一份數(shù)據(jù)可以在一個Zone集合中的各個Zone之間進行復制斥难。當運行中的Spanner集群加入一些新的數(shù)據(jù)中心或者關閉一些老的數(shù)據(jù)中心時枝嘶，就會加入或者移除一些Zone。Zone也是Spanner中物理隔離的單元：在一個數(shù)據(jù)中心可能有一個或者多個Zone哑诊，例如群扶，屬于不同應用的數(shù)據(jù)必須被分區(qū)到同一個機房的不同到服務器集合中。

圖1顯示了在一個Spanner Universe中的服務器镀裤。每個Zone都有一個ZoneMaster和100到數(shù)千個的SpannerServer竞阐。ZoneMaster將數(shù)據(jù)分配給SpannerServer，SpannerServer將數(shù)據(jù)提供給各個Client端暑劝。Client端利用每個Zone中的Location Proxy來定位可以為Client端提供數(shù)據(jù)的SpannerServer骆莹。目前universe master和placement driver都各自只有一個服務實例（存在單點問題）。 universe master 主要是一個控制臺程序担猛，用來展示用于交互式debug所需要的所有Zone的狀態(tài)信息幕垦。placement driver 每幾分鐘都會自動進行跨Zone的數(shù)據(jù)遷移。placement driver會周期性的與spanservers 進行通訊傅联，從而找出需要被移動的數(shù)據(jù)進行遷移智嚷，從而滿足最新的數(shù)據(jù)副本約束條件或者從而實現(xiàn)負載均衡。優(yōu)于篇幅有限纺且，我們只對Spanserver的一些核心實現(xiàn)細節(jié)進行說明盏道。

2.1 Spanserver 的軟件棧

本節(jié)主要描述spanserver的實現(xiàn)，進而說明我們是如何基于BigTable進行改造從而實現(xiàn)復制和分布式事務的载碌。SpanServer的軟件棧如圖2所示

圖2中展示了SpanServer的軟件堆棧猜嘱。從圖的底部衅枫，您可以看出每個SpanServer管理100到1000個Tablet。Spanner中的Tablet與BigTable中的Tablet類似朗伶，也實現(xiàn)了像下面這樣的映射關系：
(key:string, timestamp:int64) → string
和Bigtable不同的是弦撩，Spanner會將時間戳信息也記錄到key中，通過這種方式Spanner更像是一個支持多版本數(shù)據(jù)的數(shù)據(jù)庫论皆，而不是一個單純的Key-Value存儲益楼。
Tablet的狀態(tài)存儲在一系列以B-Tree組織的文件集合和WAL（Write-Ahead-Log）文件中，而所有的這些文件都存儲在名為Colossus（Google File System[15]的升級版）的分布式文件系統(tǒng)中点晴。
為了支持復制感凤，每個Spanserver在每個Tablet的上層都實現(xiàn)了一個單獨的Paxos狀態(tài)機（Spanserver的先前版本在每個Tablet上層都實現(xiàn)了多個Paxos狀態(tài)機，從而允許進行更靈活復制策略的配置粒督，但是由于這種設計過于負責陪竿，我們拋棄了）。每個狀態(tài)機中將狀態(tài)機的狀態(tài)和日志信息記錄到其對應的Tablet中屠橄。Spanner的Paxos實現(xiàn)支持了長壽leader族跛，長壽leader是通過基于時間的leader租約（默認租約長度是10秒）實現(xiàn)的。當前Spanner的實現(xiàn)中會對每次Paxos的寫入操作記錄兩次：一次記錄在tablet的log中锐墙，一次記錄在Paxos的log中礁哄。這種方式支持權宜之計，最終我們會進行改善溪北。
Spanner中對Paxos的實現(xiàn)是管道化的桐绒，這樣可以在WAN（廣域網(wǎng)）存在網(wǎng)絡延時的情況下可以提升Spanner的吞吐量；但是Paxos會把所有的寫操作都按照順序執(zhí)行（我們將會在第四節(jié)進行詳細講解）刻盐。
Spanner中的Paxos狀態(tài)機主要用來實現(xiàn)數(shù)據(jù)的一致性復制掏膏。每份復制數(shù)據(jù)的Key-Value映射狀態(tài)都存儲在它相應的Tablet中。寫操作必須在Paxos leader上初始化Paxos協(xié)議敦锌；讀操作可以直接從底層的任意一個最新的Tablet副本中訪問其狀態(tài)信息馒疹。一份數(shù)據(jù)的副本集合我們稱之為一個Paxos Group。
在任意一個leader 副本上乙墙，每個Spanserver通過一張lock table來控制并發(fā)颖变。這張lock table中包含了二階段鎖的狀態(tài)：它將某個范圍的key映射到相應的鎖狀態(tài)。（注意：只有擁有一個長壽的leader才可以有效的管理lock table）听想，無論是在bigtable中還是在spanner中腥刹，我們都設計了長事務（例如，當生成報表時汉买，整個事務可能持續(xù)很多分鐘）衔峰，這些長事務采用了樂觀鎖，但是當存在沖突時，性能會比較差垫卤。
需要同步執(zhí)行的操作：如事務性讀取威彰，都需要從lock table中獲得鎖；而其他的操作均不需要考慮從lock table中獲得鎖穴肘。
對于每個處于leader位置的副本歇盼，每個SpanServer都會實現(xiàn)一個事務管理器來支持分布式事務。該事務管理器作為participant leader评抚；Paxos Group中的其他的副本（leader之外的副本）作為participant slaves豹缀。若一個事務只涉及到一個Paxos group（大部分的事務都只涉及到一個Paxos Group），該事務可以直接跳過事務管理器慨代，因為lock table和Paxos一起就足以保證事務性邢笙。若一個事務涉及到多個Paxos Group，這些Paxos Group的leader就會相互協(xié)調(diào)鱼响，從而完成二階段提交鸣剪。其中的一個參與Paxos Group被選為coordinator：該Group的participant leader（實際上就是spanserver為每個leader副本實現(xiàn)的事務管理器） 就是coordinator leader, 而該Group的slaves就是coordinator slaves组底。每個事務管理器的狀態(tài)都存儲在底層的Paxos group中(也就是存儲在一個Paxos Group的各個副本中)丈积。

2.2 目錄以及數(shù)據(jù)分布

在所有的Key-Value映射的上層，Spanner實現(xiàn)了一層被稱為directory的bucketing 抽象债鸡，一個directory是一批連續(xù)的具有相同前綴的key的集合江滨。（可能叫做bucket更為合適）在2.3節(jié)我們將會對directory的前綴進行說明。Spanner中的Directory特性使得應用端可以通過小心地選擇key進而精確地控制他們需要訪問的數(shù)據(jù)的本地性厌均。
一個directory 就是數(shù)據(jù)存儲和異動的一個基本單元唬滑。在同一個directory 中的所有數(shù)據(jù)都擁有相同的副本配置。當數(shù)據(jù)在Paxos group之間移動時, 也是一個directory一個directory 移動的棺弊，就如圖3所示晶密。

Spanner可能會將一個directory 從負載高的Paxos group中遷走，從而降低該Paxos group的負載模她；也可能將被頻繁地同時且一起訪問的多個directory 都放到一個Paxos group稻艰；也可能將一個directory移動到里訪問者更近的一個Paxos group中。Spanner可以在用戶的操作正在進行的同事進行directory的遷移侈净。一個50MB大小的directory可以在幾秒中之內(nèi)遷移完成尊勿。
實際上一個 Paxos group可能會包含多個directory，這也就意味著spanner中的tablet與hbase中的tablet是不同的：
Spanner中的tablet相當于是包含了一個行空間中一個或者多個獨立的partitons的容器畜侦，多個Partition中元扔，每個Partition內(nèi)部的key值是有序連續(xù)的，但是不同的Partition的key的范圍不需要連續(xù)旋膳。Spanner中的tablet不是單獨的一個partition（partition的key值按照字典順序排序）澎语。這種設計可以讓多個被頻繁一起訪問的directory可以被整合到一起。
我們可以做出簡單的邏輯推斷：Spanner會針對每個Tablet創(chuàng)建一個Paxos group對其進行一致性復制，而每個Paxos group中可以包含多個directory擅羞，一個Tablet中又包含多個獨立順序key范圍的partition盯孙，因此這四者之間的對應關系如下圖所示：

從上圖中可以看出每個Paxos Group與一個Tablet對應，而每個Directory與一個Partition對應祟滴。
Movedir 是后臺任務振惰，用于在不同的Paxos groups [14]之間移動directory。 Movedir也經(jīng)常被用來向Paxos groups 中添加副本或者從Paxos groups 中刪除副本,因為目前Spanner還不支持在 Paxos內(nèi)部執(zhí)行配置的變更垄懂。 Movedir 并不是作為一個單獨事務來實現(xiàn)的骑晶，這樣可以避免由于移動某一塊數(shù)據(jù)而阻塞在塊數(shù)據(jù)上正在執(zhí)行的事務讀或者事務寫操作。相反草慧，movedir 會注冊一個事實（fact）桶蛔，聲明movedir 已經(jīng)開始移動數(shù)據(jù)了，并且在后臺移動數(shù)據(jù)漫谷。 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（這句話沒有讀明白仔雷，只明白開始移動數(shù)據(jù)的時候是沒有啟動事務的，當數(shù)據(jù)移動的差不多的時候舔示，再啟動一個事務執(zhí)行原子性的操作：完成數(shù)據(jù)移動并更新元數(shù)據(jù)）.
directory也是應用可以指定的地理復制屬性（數(shù)據(jù)分布或放置策略）的最小單元碟婆。Spanner中設計了數(shù)據(jù)分布描述語言，而數(shù)據(jù)分布描述語言將數(shù)據(jù)副本配置管理的功能作為單獨的模塊分離出來進行設計惕稻。Spanner的Administrator主要控制副本的兩個維度信息：
【1】副本的數(shù)量和類型
【2】副本的地理存放位置
基于這兩個維度竖共，Spanner提供了一系列可自由組合的配置項（例如：北美地區(qū)镊叁、1主5副本）脖镀。應用程序通過在每個數(shù)據(jù)庫或者directory上打上這些配置項的組合標簽來控制數(shù)據(jù)的復制方式。 例如應用可以將每個終端用戶的數(shù)據(jù)存儲在用戶自己的Directory中洋措，并且可以讓A用戶的數(shù)據(jù)在歐洲地區(qū)存放3個副本蜘渣，讓用戶B的數(shù)據(jù)在北美存放5個副本淌铐。
實際上，當Directory中的數(shù)據(jù)太多的時候蔫缸，Spanner會將Directory分裂成多個Fragment（分片）腿准。多個分片會分布在不同的Paxos Groups中（也分布在不同的服務器上），因此Movedir實際上是在不同的Paxos Groups之間移動Fragment捂龄，而不是整個的Directory 释涛，Directory與Fragment的具體結構和關系如下圖所示：

Directory與Fragment關系圖

2.3 數(shù)據(jù)模型

Spanner 中數(shù)據(jù)模型的特點包括：
【1】結構化的半關系型表
【2】支持查詢語言
【3】支持通用事務
多種因素驅動著Spanner的數(shù)據(jù)模型必須具備如上三個特點。
Megastore [5]在Google內(nèi)部的大規(guī)模使用驅使著Spanner必須支持結構化的半關系型表和同步復制倦沧。在Google內(nèi)部至少有300個應用在使用Megastore服務（雖然Megastore的性能比較低）唇撬，因為在表的管理方面，Megastore的數(shù)據(jù)模型比Bigtable的更簡單展融，并且MegaStore還支持跨數(shù)據(jù)中心的同步復制（Bigtable跨數(shù)據(jù)中心的數(shù)據(jù)復制只能保證最終一致性窖认，不能保證同步復制）。使用MegaStore服務的比較知名的應用包括： Gmail, Picasa, Calendar, Android 應用市場, 和 AppEngine。
Dremel [28] 在Google內(nèi)部作為交互式分析和查詢工具而被廣泛使用扑浸，驅使著Spanner必須支持SQL查詢語句烧给。
由于BigTable中不支持跨行的事務，導致了用戶一直對其抱怨喝噪；Percolator [32]就是為了解決跨行事務的問題础嫡。Spanner采用常規(guī)二階段提交，但是Spanner的開發(fā)人員聲稱這會將會極大地降低Spanner的性能和可用性 [9, 10, 19]. 但是我們認為最好還是由應用程序的開發(fā)人員去解決由于過于使用業(yè)務而導致的性能問題酝惧，而不是一直進行無事務研發(fā)榴鼎。另外，在Paxos 執(zhí)行二階段提交會極大地緩解可用性問題晚唇。
應用端的數(shù)據(jù)模型構建在Spanner 的通過Directory進行分桶的Key-Value數(shù)據(jù)模型之上的巫财。一個應用可以在一個Universe中創(chuàng)建一個或者多個database。每個database中可以包含無限個結構化表哩陕。這些表和傳統(tǒng)數(shù)據(jù)庫中的表很像平项，有行、列和多個版本的值悍及。Spanner中的查詢語言也和SQL語句很像闽瓢，但是我們對其做了一些擴展，可以讓表的某一列的類型為：protocol-buffer 的值類型并鸵。
Spanner的數(shù)據(jù)模型并不是純粹的關系型的鸳粉，Spanner中的行必須有名字扔涧。更準確的說园担，Spanner中的每個表都必須有一個由一個或者多個主鍵列組成的有序集合。正式這個限制枯夜，使得Spanner看起來還像一個Key-Value的存儲：這些主鍵組成了一行的名字弯汰，每個表都定義了從多個主鍵列（相當于Key）到多個非主鍵列（相當于Value）的映射。
只有針對行中的key定義了相應的value（即使這些value的值為null）湖雹，我們才認為該行是存在的咏闪。這種架構設計的一個優(yōu)點就是：允許應用程序簡單地選擇一些key的值或者范圍就可以控制數(shù)據(jù)訪問的本地性。

圖4展示了Spanner中的一個典型的schema示例摔吏，該schema示例存儲了照片的元數(shù)據(jù)信息鸽嫂，照片的元數(shù)據(jù)是基于一個用戶對應一個相冊的方式進行組織的。Spanner中的Schema描述信息與MegaStore的描述信息很像征讲，但是有一個特有的要求：Spanner中的每個database都必須被client端分成一個或者多個具有層級結構的表据某。Client端通過INTERLEAVE IN 語法聲明database中的表的層級結構。在頂層的表是一個目錄表诗箍。在目錄表中的每一行都有一個鍵：K癣籽。目錄表的下一層表叫做目錄表的子表，子表中的每一行也都有鍵：K',K'可能以K開頭，也可能不以K開頭筷狼，Spanner會將子表中含有以K開頭的鍵的行和目錄表中含有以K開頭的鍵的行放在一起（以字典順序排序）瓶籽，構成了一個目錄。 ON DELETE CASCADE語法意味著：若刪除目錄表中的一行埂材，也會級聯(lián)刪除子孫表中的相關聯(lián)的行塑顺。這個圖也展示出了示例數(shù)據(jù)庫的數(shù)據(jù)布局關系：例如：Albums(2,1) 代表著表Albums 中的一行數(shù)據(jù)，這一行數(shù)據(jù)中的uid為2俏险，aid為1茬暇。
Spanner這種通過對有關聯(lián)關系的兩張表交叉組織在一起，并形成目錄的數(shù)據(jù)組織方式對Spanner來說是非常重要的寡喝，因此這樣就可以讓client端通過指定多張表之間的局部關聯(lián)關系糙俗，就可以精確地訪問到部分數(shù)據(jù)，避免了對全量數(shù)據(jù)的掃描预鬓，這種特性對于提高分布式可分片的數(shù)據(jù)庫系統(tǒng)的性能來說是至關重要的巧骚。若沒有這種數(shù)據(jù)組織結構，Spanner將無法精確的定位到所需要訪問的所有關聯(lián)數(shù)據(jù)的位置格二、也無法極大地縮小數(shù)據(jù)掃描的范圍劈彪。

3 TrueTime

本節(jié)主要對TrueTime API進行說明，并對它的實現(xiàn)方式進行簡要概述顶猜。關于其實現(xiàn)細節(jié)有專門的其他論文進行說明沧奴，我們的目的是為了說明這個TrueTime API的主要價值在哪。 Table 1 列出了TrueTime API的方法长窄。TrueTime 認為時間應該被表述成一個時間區(qū)間滔吠，而不是一個時間點，而這個時間區(qū)間TrueTime稱之為TTinterval挠日。TTinterval是一個具有有限時間不確定性的時間區(qū)間（也可以叫做有邊界的時間不確定性區(qū)間疮绷，承認給出的時間是不確定的，但是偏差的大小是確定的嚣潜。而不像其他標準的時間接口冬骚，他們根本就不承認時間具有不確定性）。 因此TTinterval有不確定性的上限和下限懂算，上限和下限都是TTstamp（類似于TimeStamp）類型只冻，也就是說上限和下限都是時間點。例如：方法 TT.now() 就返回一個TTinterval對象计技，該TTinterval對象保證包含在調(diào)用TT.now() 方法時的絕對時間喜德。這個絕對時間和Unix的時間（考慮了閏秒涂抹）類似。TT.now()返回的TTinterval的即時誤差是TTinterval寬度的一半酸役。方法TT.after() 和 TT.before() 是基于 TT.now()方法的二次封裝住诸，提供了用于判斷是否已經(jīng)超過了指定時間和是否還沒有到達指定時間的便捷方法驾胆。
假設函數(shù)tabs(e)返回的是事件e發(fā)生的絕對時間。那么使用更加專業(yè)的方式來描述就是：對于一次調(diào)用： tt = TT.now()贱呐，TrueTime能夠保證tt.earliest ≤ tabs(enow) ≤ tt.latest,其中enow就表示這次調(diào)用丧诺，tabs(enow) 就表示調(diào)用發(fā)生的絕對時間。
TrueTime底層使用的是GPS時間和原子鐘時間奄薇。TrueTime 之所以使用兩種類型的時間驳阎，是因為他們都有可能在不同的場景下獲取時間失敗。GPS時間獲取失敗或者獲取時間不準確的原因包括：天線和接收器失效馁蒂、當?shù)仉姶鸥蓴_呵晚、其他一些設計上的原因（例如：不能正確進行跳點處理和GPS欺騙）和GPS系統(tǒng)宕機 。
原子鐘也會失敗沫屡，但是其失敗的原因與GPS失敗的原因完全不一樣饵隙，而且各個原子鐘也都是獨立的沒有彼此相關性。原子鐘一種最常見的失敗原因是：由于原子鐘的頻率錯誤（原子鐘的頻率錯誤不會導致時間馬上出現(xiàn)錯誤）沮脖，而導致經(jīng)過長時間之后金矛，原子鐘的時間才出現(xiàn)明顯的偏差。
在每個數(shù)據(jù)中心都有一系列的 time master服務器勺届，在每個 time master服務器上都有一個time slave后臺進程驶俊，TrueTime就是由位于各個數(shù)據(jù)中心的time master服務器上的各個time slave后臺進程實現(xiàn)的。
大多數(shù)的time master服務器上都帶有GPS接收器（每個GPS接收器上都有專用的天線）免姿；這些time master服務器在地域上被分開放置饼酿，從而避免由于天線失效、無線電干擾和GPS欺騙等原因而引起大范圍的影響胚膊。剩下的time master服務器(我們稱之為世界末日master故俐，可能是為了應對世界末日到來時，GPS不管用的情況澜掩，但是若世界末日真的到來了购披，難道還有人使用google嗎？呵呵) 上都裝備有原子鐘肩榕。其實一個原子鐘也不是很貴：一個世界末日time master的費用與一個GPS time master的費用相當。所有time master服務器上的時間都會彼此進行比對惩妇。 每個time master 服務器還會比對本地時鐘和其他服務器時鐘的頻率進行交叉檢查株汉，若發(fā)現(xiàn)本地時鐘頻率與其他服務器的時鐘頻率相差太大，則將自己驅逐（個人認為不是與一個其他時鐘服務器的頻率進行對比歌殃，而是與多個時鐘服務器的頻率對比乔妈，只有發(fā)現(xiàn)其他時鐘服務器的頻率都相近，只有自己的頻率與其他時鐘服務器的頻率相差甚遠時氓皱，才會將自己驅逐）路召。 在時鐘同步的過程中勃刨，末日master服務器時間的不確定性緩慢增加，這主要是由于最壞情況下進行時鐘漂移策略導致的股淡。而GPS在時鐘同步的過程中身隐，則可以基本保證不確定性為0。
每個slave后臺進程都會從很多的time master服務器上收集時間參考值唯灵，從而減少或者避免由于某一臺time master故障而導致的誤差贾铝，收集時間參考值的這個過程我們稱之為收集投票。有些GPS time master服務器是從附近的數(shù)據(jù)中心選取的埠帕；剩下的GPS time master 服務器是從較遠的數(shù)據(jù)中心選取的垢揩，還有一些世界末日 time master服務器也是從較遠的數(shù)據(jù)中心選取的。
每個slave后臺進程會使用一種 Marzullo [27]算法的變種算法來探測和拒絕欺騙敛瓷，并將本地時間同步到非欺騙的time master 服務器叁巨。
為了防止損壞或者故障時鐘服務器對整體的時間準確性產(chǎn)生巨大影響，當某臺時鐘服務器的時鐘頻率的誤差超過某一個標準誤差范圍的時候呐籽，這臺時鐘服務器就會被驅逐俘种。
在時鐘同步的過程中，time slave后臺進程表現(xiàn)出時間不確定性的緩慢增加绝淡，而這種時間不確定性不僅取決于保守的最差情況下的本地時鐘漂移策略還取決于各個 time-master服務器的不確定性和各個服務器之間的通訊延時宙刘。在spanner的線上生產(chǎn)環(huán)境中，時間不確定性表現(xiàn)為一個時間鋸齒狀函數(shù)牢酵，時間不確定性在每輪收集投票的過程中都會在1到7ms之間來回波動悬包，因此大部分情況下，時間不確定性的平均值為4ms馍乙。后臺進程收集投票的間隔為30秒布近，當前的時鐘頻率的漂移比率為200微秒/秒，所以每輪投票間隔內(nèi)丝格，其時間不確定性的值就會在0到6ms之間來回波動撑瞧。剩下的1毫秒主要是由于各個time master服務器之間的通訊延時產(chǎn)生的。當某些故障發(fā)生時显蝌，時間不確定性也會偶爾超出鋸齒的邊界预伺。 例如，某個time-master服務器的偶爾不可用曼尊，有可能導致整個數(shù)據(jù)中心范圍的時間不確定性的增加酬诀。類似的，機器負載過高和網(wǎng)絡問題也會導致時間不確定性的偶爾增大骆撇。

4 并發(fā)控制

本節(jié)描述TrueTime是如何用來保證并發(fā)控制的正確性的瞒御，以及如何利用這種屬性來實現(xiàn)諸如：外部一致性事務、無鎖只讀事務和對歷史數(shù)據(jù)的非阻塞讀神郊。這些特性可以保證在某個時間t進行數(shù)據(jù)庫的讀肴裙，一定可以看到在t時間之前提交的所有事務趾唱。
進一步說，將Paxos看到的寫操作（除非上下文明確指出是Client端寫操作蜻懦，否則我們認為所有的寫操作都是Paxos看到的寫操作）和Spanner客戶端的寫操作區(qū)分開非常的重要甜癞。例如，兩階段提交保證在spanner client端還沒有進行寫操作的時候阻肩，就發(fā)起一次Paxos寫带欢。

4.1 時間戳管理

表2列出了Spanner支持的所有的操作的類型。Spanner支持讀寫事務烤惊，只讀事務（預先聲明的快照隔離事務）和快照讀乔煞。
單獨的寫時通過讀寫事務來執(zhí)行的；非快照讀是通過只讀事務來實現(xiàn)的柒室。兩者都是在內(nèi)部進行重試的（客戶端不需要寫重試邏輯）渡贾。
只讀事務具有快照隔離級別[6]的性能優(yōu)勢。一個只讀事務必須事先聲明不會包含任何的寫操作雄右；只讀事務并不是一個簡單的不包含寫操作的讀寫事務空骚。在只讀事務中的讀操作在執(zhí)行的時候會在沒鎖的情況下獲得一個系統(tǒng)時間戳，所以在讀操作獲取時間戳的過程中擂仍，不會阻塞任何的寫操作囤屹。只讀事務中的讀操作可以在任何最新的數(shù)據(jù)副本上執(zhí)行（4.1.3節(jié)）。
快照讀操作時針對于歷史數(shù)據(jù)的讀取逢渔，快照讀操作執(zhí)行的時候不需要鎖肋坚。客戶端可以指定一個時間戳肃廓，從而讓快照讀只讀取該時間戳對應的歷史數(shù)據(jù)智厌，或者也可以提供一個想要讀取的歷史數(shù)據(jù)的時間范圍，讓Spanner自己選擇一個合適的時間戳盲赊。不管是哪種情況铣鹏，快照讀都會在一個最新的副本數(shù)據(jù)上執(zhí)行。
對于只讀事務和快照讀而言哀蘑，一旦選擇了時間戳诚卸，那么提交就是不可避免的，除非指定的時間戳對應的數(shù)據(jù)已經(jīng)被垃圾回收递礼。
因此惨险，Client端不需要在重試邏輯中緩存結果。當一臺服務器宕機的時候脊髓，Client端內(nèi)部就會自動繼續(xù)根據(jù)指定的時間戳和當前讀取的位置從另一臺不同的服務器上繼續(xù)讀取數(shù)據(jù)。

4.1.1 Paxos Leader 租約

在Spanner的 Paxos實現(xiàn)中栅受，使用了時間租約來實現(xiàn)leader地位的長時間存在（默認10秒鐘）将硝。潛在的leader會發(fā)起時間租約的投票恭朗；一旦發(fā)起投票的潛在leader獲得了指定樹齡的投票后，該leader就認為自己獲得了時間租約依疼。當一個PaxosGroup內(nèi)個一個副本完成了一次寫入痰腮，就會隱式的進行一次租約延期。當一個leader的租約塊到期的時候律罢，他就要主動請求進行租約延期膀值。 當一個leader收到了指定數(shù)量的選票的時候就是leader時間租約區(qū)間開始的時間，當一個leader不在擁有指定數(shù)量的租約選票的時候误辑，就是leader時間租約結束的時間（因為有些選票已經(jīng)過期了）沧踏。
Spanner依賴于下述的不相交特性：
任意兩個PaxosGroup的leader的時間租約區(qū)間都是不相交的。附錄A描述了如何實現(xiàn)這種不相交性巾钉。
Spanner允許Paxos leader通過將slave從租約投票中釋放的方式進行l(wèi)eader退位翘狱。但是為了保證上述的不相交性，Spanner會對Paxos leader的退位時機進行限制砰苍。
Spanner定義Smax為一個leader可以使用的最大時間戳潦匈。從后續(xù)的章節(jié)將會知道，一旦指定了 Smax 赚导，只有當TT.after(Smax)為true時茬缩，當前的leader才可以退位。

4.1.2 為讀寫事務指定時間戳

事務性讀和寫使用兩階段鎖吼旧。因此在讀寫事務獲得鎖之后凰锡，釋放鎖之前，我們可以為之指定任意的時間戳黍少。對于任意一個事務Spanner都會為其指定一個時間戳寡夹，該時間戳是Paxos為Paxos寫操作指定的時間戳，代表著事務的提交時間厂置。
Spanner依賴于以下單調(diào)性：
在每個PaxosGroup內(nèi)部菩掏，Spanner會以單調(diào)遞增的順序為每次的Paxos的寫操作分配一個時間戳，即使是跨多個Paxos Leader昵济，其分配的時間戳也是單調(diào)遞增的智绸。這種單調(diào)性在跨越多個leader的場景下是通過利用時間租約的不相交性來實現(xiàn)的：一個leader只能為其指指定一個在其時間租約以內(nèi)的時間戳。需要注意的是：一旦指定了一個時間戳S访忿，Smax就需要被增加到S來保證不相交性瞧栗。
Spanner也實現(xiàn)了以下所描述的外部一致性：
若事務T2的開始時間在事務T1的提交時間之后，那么事務T2的提交時間一定比事務T1的提交時間要晚海铆。
執(zhí)行事務的協(xié)議和分配時間戳的協(xié)議遵循兩條原則迹恐，這兩條原則一起保證了事務的外部一致性，如下面描述卧斟。我們定義寫操作Ti的commit request到達coordinator leader的事件為e_i_server.因此上述的兩條原則如下：
Start coordinator leader 會為寫操作Ti分配一個不小于TT.now().latest的時間戳：Si殴边。TT.now().latest的值是在事件e_i_server之后計算得到的憎茂。participant leaders在這條規(guī)則里并不重要；4.2.1 節(jié)中將會描述participant leaders是如何參與到下一條規(guī)則的實現(xiàn)的锤岸。
Commit Wait coordinator leader 必須確保在TT.after(si)的返回值為true之前竖幔，Client端是永遠不可能看到任何提交的數(shù)據(jù)的。Commit wait就是要確保si比Ti的絕對提交時間要小是偷。 commit wait 的實現(xiàn)細節(jié)將會在4.2.1節(jié)中進行描述藏研，證明如下：
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規(guī)則）
s1 < s2 (推導)

4.1.3 基于某個時間戳進行讀操作

在4.1.2節(jié)中提到的單調(diào)遞增性和不變性沃斤，使得Spanner可以準確的判斷一個數(shù)據(jù)副本是否足夠新從而可以服務于某次讀取請求猖腕。每個數(shù)據(jù)副本都會記錄一個名為安全時間的額變量：T_safe诗芜。T_safe的值是數(shù)據(jù)副本最近一次更新后的最大時間戳。若一個讀操作的時間戳是T戒职，當滿足T<=T_safe的時候栗恩，這個數(shù)據(jù)副本才可以被當前的這個讀操作進行讀取。
我們定義T_safe=min(T_paxos_safe,T_tm_safe)洪燥，在該定義中T_paxos_safe代表每個Paxos狀態(tài)機的安全事件磕秤，而T_tm_safe則代表每個事務管理器的安全時間。T_paxos_safe 比較簡單：它的值就是最新的應用的Paxos Write的時間戳捧韵。由于時間戳是單調(diào)遞增的而且寫入操作也是被順序執(zhí)行的市咆，因此當時間戳小于或者等于T_paxos_safe的時候，不會發(fā)生新的寫入再来。
對于一個數(shù)據(jù)副本而言蒙兰，若沒有prepare 事務（未提交），那么T_tm_safe的值就是無窮大芒篷。當T_tm_safe的值為無窮大的時候搜变，此時的事務正處于兩階段提交中的兩個階段之間。(對于一個參與的Slave而言针炉，T_tm_safe實際上是指副本的leader的事務管理器的時間挠他，而事務管理器的狀態(tài)可以通過Paxos write操作傳入的元數(shù)據(jù)推斷出來) 。若存在這樣的事務篡帕，那么被這些事務影響的狀態(tài)是不確定的：一個參與者副本無法知道某個事務是否將要提交殖侵。正如4.2.1節(jié)中討論的那樣，提交協(xié)議會保證每個參與者都知道每個預提交事務的時間戳的下界镰烧。事務Ti的參與leader（對于一個Group g來說）會為預提交記錄分配一個預提交時間戳：S_prepare_i_g拢军。協(xié)調(diào)者leader會確保所有參與者組的事務的提交時間戳Si>= S_prepare_i_g。所以在組g內(nèi)的所有的預提交事務Ti怔鳖，都滿足：T_tm_safe=Min_i(S_prepare_i_g)-1茉唉。

4.1.4 對只讀事務指定時間戳

一個只讀事務的執(zhí)行分為兩個階段：指定一個時間戳S_read[8]，然后執(zhí)行基于時間戳S_read上的快照讀《脑可以在任意一個最新的數(shù)據(jù)副本上執(zhí)行快照讀魏铅。指定S_read的值的簡單方式就是：S_read = TT.now().latest, 并且事務一旦開始昌犹，就采用類似于4.1.2節(jié)中對寫操作保持事務一致性相似的方式保證只讀事務的一致性坚芜。
但是，若T_safe不是足夠大斜姥，那么基于S_read的數(shù)據(jù)讀操作將會阻塞鸿竖。 (此外，我們應該意識到當設置一個S_read的值的時候铸敏，由于我們需要保證不相交性和遞增性缚忧，可能會間接地增加S_max的值。) 為了減少基于S_read的快照讀阻塞的概率杈笔，Spanner會在保證外部事務一致性的前提下分配一個最大的時間戳闪水。4.2.2節(jié)會詳細解釋怎么選擇這樣一個時間戳。

4.2 細節(jié)

本節(jié)將會對前面提到的讀寫事務和只讀事務的實現(xiàn)細節(jié)蒙具，以及用于實現(xiàn)原子性模式變更事務的實現(xiàn)方式球榆。最后將會說明基本模式的改進細節(jié)。
4.2.1 Read-Write Transactions
像Bigtable一樣禁筏，一個事務中的寫操作持钉，在提交之前都會緩存在client端的。因此在事務寫提交之前篱昔，另一個事務中的讀不會看到事務寫產(chǎn)生的變更每强。 Spanner中的這種設計之所以工作的很好是因為讀操作會返回讀取中的數(shù)據(jù)中帶回來的時間戳，而未提交的寫操作這是還未被指定時間戳州刽。
讀寫事務中的讀操作采用傷停等待（wound wait [33] ）來避免死鎖空执。Client端向合適的Paxos Group的leader發(fā)起讀操作，該次讀操作將會請求獲得鎖并且讀取最新的數(shù)據(jù)穗椅。當一個Client端的事務保持open期間辨绊，Client端會不停的向leader不停的發(fā)送keepalive消息，從而避免leader在該事務期間超時房待。當一個Client端已經(jīng)完成了所有的讀操作并且緩存的所有的寫操作邢羔，它就開始進行兩階段提交。Client端會選擇一個協(xié)調(diào)Group并且向各個參與Group的leader發(fā)送commit消息桑孩，該消息中攜帶了協(xié)調(diào)者信息和緩存的寫操作拜鹤。讓Client端發(fā)起二階段提交可以避免在各個連接上普遍的發(fā)送起兩次數(shù)據(jù)，從而避免了大范圍的網(wǎng)絡數(shù)據(jù)傳輸流椒。
一個非協(xié)調(diào)的參與Group的leader首先會請求獲得寫鎖敏簿。然后該leader會選擇一個預備時間戳，該預備時間戳必須比該leader分配給先前的任何事務的時間戳都要大（為了保證單調(diào)遞增性）,并且將預備記錄通過Paxos寫入日志。最后每個參與leader都會將自己的預備時間戳通知給協(xié)調(diào)leader惯裕。
協(xié)調(diào)Group的leader也會首先要求獲得寫鎖温数，但是會跳過預備階段。在收到各個參與Group leader的消息后蜻势，協(xié)調(diào)Group的leader會為整個事務分配一個時間戳撑刺。commit時間戳s必須大于或者等于所有的預備時間戳（為了滿足4.1.3節(jié)中的約束）, 也要大于協(xié)調(diào)組的leader收到commit消息時 TT.now().latest 的值，也要比leader為之前的事務分配的所有的所有的時間戳都要大握玛。 協(xié)調(diào)組的leader會通過Paxos在日志中寫入提交記錄（或者當?shù)却渌麉⑴c者超時的時候够傍，在日志中寫入一個退出記錄）。
在協(xié)調(diào)組的leader一直等到TT.after(s)返回true之前挠铲，協(xié)調(diào)組的任何副本都不會應用commit記錄冕屯，從而遵循4.1.2節(jié)中所述的commit-wait原則。
因為協(xié)調(diào)組的leader基于TT.now().latest來指定s的值拂苹，并且要一直等待s的時間戳成為過去式安聘，預計的等待時間是2倍的時間偏差。這個等待的時間通常和paxos的通訊時間重疊瓢棒。在提交等待之后浴韭，協(xié)調(diào)組會將commit時間戳發(fā)送給Client端和其他所有的參與者leader。每個參與者leader都會通過Paxos將事務的結果寫入日志音羞。所有的參與者leader都會在同一時間戳進行提交囱桨，然后釋放鎖。

4.2.2 只讀事務

分配一個明確的時間戳需要在read操作涉及到的所有Paxos組之間進行一次協(xié)調(diào)嗅绰。因此Spanner需要為每個只讀事務提供一個scope表達式舍肠，該表達式說明了在整個只讀事務中需要被讀取的所有keys。Spanner 會自動推算出所有獨立查詢的查詢范圍窘面。
若Scope的值是由單個Paxos組提供的翠语，那么Client端就會向那個組的leader發(fā)起一個只讀事務(當前Spanner的實現(xiàn)，只會為Paxos leader中的只讀事務指定一個時間戳财边。) 肌括，那個leader指定S-read并且執(zhí)行Read操作。對于一次單個位置的讀操作酣难，Spanner通常比TT.now().latest做的更好谍夭。我們定義LastTS() 為在一個Paxos Group上執(zhí)行最后一次commit write的時間戳。若沒有預提交事務憨募，那么賦值S_read=LastTS()就可以滿足外部一致性：
事務將會看到最后一次寫入的結果紧索，因此在最后一次寫入之后進行排序。
若Scope的值由多個Paxos組提供菜谣，我們可以通過幾種方式來最終確定Scope的值珠漂。其中最復雜的一種方式就是讓所有Group的leader針對各自的LastTS()的值進行協(xié)商晚缩，并最終得出S_read的值。
Spanner目前實現(xiàn)了一種簡單的方式媳危。Client端不需要詢問所有Group的leader荞彼，而是在S_read=TT.now().latest(這可能會導致等待安全時間的增加)的時候去執(zhí)行read。事務中的所有讀都可以被發(fā)送到足夠新的數(shù)據(jù)副本上執(zhí)行待笑。

4.2.3 Schema信息變更事務

TrueTime 使得Spanner具備了原子性Schema信息變更的能力鸣皂。采用標準的事務模型來執(zhí)行Schema信息的變更是完全行不通的，因此一次schema信息的變更涉及到的參與者（數(shù)據(jù)庫中group的個數(shù)）可能會成千上萬個滋觉。Bigtable 可以實現(xiàn)在一個數(shù)據(jù)中心內(nèi)部的原子性schema信息變更签夭，但是它在執(zhí)行schema信息變更的時候，將會阻塞所有其他的操作椎侠。
Spanner 的Schema信息變更事務是一個非阻塞的標準事務的變種。首先Spanner會顯式的分配一個未來的時間戳 措拇，該時間戳將會在準備階段進行注冊我纪。因此，涉及到數(shù)千臺服務器的schema信息變更將會在不影響其他并發(fā)的活動的前提下完成丐吓。 其次浅悉，讀寫操作，他們都是隱式的依賴于shema信息券犁，它們都會和任何注冊的schema信息變更時間戳t保持同步：當讀寫操作的時間早于t术健，讀寫操作會正常執(zhí)行，但是當讀寫操作的時間晚于t粘衬，讀寫操作將會被阻塞荞估。若沒有TrueTime，那么定義schema信息變更的時間戳稚新，將沒有任何意義勘伺。

4.2.4 改進

前面對T_tm_safe的定義有一個缺點：在一個單獨的預提交事務中將會導致T_tm_safe無法進一步增加。產(chǎn)生的其他影響就是褂删，即使在T_tm_safe之后的讀操作與該預提交事務不存在任何沖突飞醉，這些讀操作也無法執(zhí)行，這種沖突我們稱之為：假沖突屯阀。通過為T_tm_safe增加一個從從鍵域（key range）到預提交事務時間戳的細粒度的映射關系缅帘，我們可以消除這種假沖突。這個信息可以被存儲在鎖表中（lock table）, 鎖表中其實早已經(jīng)存在了鍵域到鎖信息的映射难衰。當執(zhí)行read操作的時候钦无，只需要針對基于鍵域定義的細粒度的安全時間和讀操作的沖突時間進行檢測即可。
前面定義的LastTS() 方法也有類似的缺點：若一個事務剛剛被提交召衔，一個非沖突的只讀事務必須被分配一個S_read铃诬，從而可以跟在剛提交的事務后面。因此，read操作的執(zhí)行將會被推遲趣席。該缺點也可以采用類似的方法進行補救：通過為LastTS() 方法增加一個從鍵域（key range）到鎖表中提交時間戳的細粒度的映射（目前spanner還么有真正實現(xiàn)該優(yōu)化）兵志。當接收到一個只讀事務的時候，就需要為該事務分配一個時間戳宣肚，該時間戳的值的選擇方式是：若有一個沖突的預提交事務想罕，則從該預提交事務的細粒度的T_tm_safe時間中選擇，否則就從與該事務沖突的鍵域中LastTS()的最大值中選擇霉涨。
前面定義的T_paxos_safe有一個缺點：當存在Paxos寫操作的時候按价，該值無法增加。也就是說笙瑟，在時間t的快照讀不能在這樣Paxos Group（這種Paxos Group中的寫操作發(fā)生在t之前）中執(zhí)行楼镐。Spanner 通過充分的利用leader租約間的隔離性解決了該問題。每個Paxos leader都會通過維護一個閾值的方式來增加T_paxo_safe的值往枷，未來的一些寫操作可能會觸碰到該閾值： 它維護了一個從Paxos序列號n 到可以分配給下一個Paxos（序列號是n+1）的最小時間的映射關系MinNextTS（n）框产。位于序列號n的Paxos Group中的數(shù)據(jù)副本可以將其T_paxos_safe的值增加到MinNextTS(n) -1。
一個單獨的leader可以簡單的強制指定LastTS() 的值错洁。因為LastTS() 承諾的時間戳一定會位于一個leader的租期內(nèi)秉宿， 因此LastTS() 也保證了各個不同leader之間的不相交性。若一個leader想要將LastTS() 值增加到其leader 租期之外屯碴，那么它需要首先增加其leader租期描睦。需要注意到：為了保證不相交性，S_max的值也不可能超過LastTS() 的最大值导而。
默認情況下leader會每8秒鐘增加一次MinNextTS() 的值忱叭， 因此當不存在預提交事務的時候，在空閑LastTS() 中的健康的slave在最壞的情況下也可以在最近8秒以內(nèi)的時間戳上提供read服務嗡载。一個leader也可以根據(jù)slave的要求增加 MinNextTS() 的值窑多。

5 測試與評估

我們首先評估Spanner在復制、事務和可用性等方面的性能表現(xiàn). 然后提供一些TrueTime的實驗數(shù)據(jù)洼滚，最后對我們的第一個用戶F1埂息，在使用過程中的一些數(shù)據(jù)和經(jīng)驗進行說明和研究。

5.1 MicroBenchmarks

Table 3 展示了Spanner的microbenchmarks 的測試數(shù)據(jù)遥巴。這些測試時在分時服務器上完成的：每個SpanServer都運行在4GB內(nèi)存和四核（AMD Barcelona 2200MHz）的調(diào)度單元上千康。有多個Client，并且每個Client都運行在單獨的服務器上铲掐。 每個Zone都包含一個SpanServer拾弃。Clients和Zones都在一個數(shù)據(jù)中心里面，而一個數(shù)據(jù)中心里面網(wǎng)絡延時不會超過1ms摆霉。 (這種布局非常普遍：大多數(shù)的應用都不需要實現(xiàn)全球分布式豪椿。)測試數(shù)據(jù)庫中含有50個Paxos Group奔坟，一共有2500個directory。 操作都是單獨的4KB大小的讀寫操作搭盾。若有的讀都是在讀取的數(shù)據(jù)在Spanner中完成壓縮之后才讀取出去的咳秉，所以我們支持在測試Spanner中方法調(diào)用堆棧的性能開銷（可以忽略網(wǎng)絡開銷）。此外鸯隅，在正式測試之前澜建，我們會首先對所有數(shù)據(jù)全部都去取一遍，來填充所有位置的緩存蝌以。

在進行延時測試的時候炕舵，Client端會發(fā)送盡量少的操作，從而避免在server端進行排序跟畅。在1個副本的環(huán)境下咽筋，提交等待時間大概是5ms，Paxos的延時大概是9ms碍彭。當副本數(shù)增加的時候晤硕，延時基本保持不變，并且標準差會變小庇忌。這是因為 Paxos在Group的各個副本之間是并行執(zhí)行各種操作的。隨著副本數(shù)的增加舰褪，某個slave緩慢對整個Paxos組中選出leader產(chǎn)生的影響變得越來越小皆疹。
在進行吞吐量實驗的時候，Client端發(fā)出足夠多的操作占拍，從而使Server的CPU達到飽和略就。快照讀可以在任意一個足夠新的數(shù)據(jù)副本上執(zhí)行晃酒，因此快照讀的吞吐量會隨著副本數(shù)的增加而線性增加表牢。單個讀的只讀事務只能在leader上執(zhí)行，因為其時間戳只能在leader上指派贝次。只讀事務的吞吐量會隨著副本數(shù)的增加而增加：在實驗環(huán)境設置中崔兴，SpanServer的數(shù)量與副本的數(shù)量相同，并且leader隨機分布在不同的Zone中蛔翅。這種實驗環(huán)境的設置對于寫操作的吞吐量有益（當副本數(shù)從3增加到5的時候敲茄，寫操作的吞吐量增加了，正說明了這一點）山析，但是隨著副本數(shù)的增加每個寫操作需要完成的工作量也會線性增加堰燎，前面實驗環(huán)境的設置而帶來的這種收益也會被這種增加的工作量而抵消。
Table 4 說明了二階段提交可以擴展到一定數(shù)量的參與者：它是對運行在3個zones中的25個Spanservers測試數(shù)據(jù)的匯總笋轨。當擴展到50個參與者的時候秆剪，無論是在延時平均值還是在99%的延時時間上表現(xiàn)都還不錯赊淑，但是當增加到100個參與者的時候，延時就開始明顯升高了仅讽。

5.2 可用性

圖 5 展示了當在多個數(shù)據(jù)中心間運行Spanner的時候產(chǎn)生的可用性收益陶缺。該圖展示了當數(shù)據(jù)中心宕機的情況下的三種實驗結果，所有的實驗結果都重疊的疊放在相同的時間軸上何什。測試universe 包含5個Zones：Zi组哩，每個Zone中含有25個SpanServers。測試數(shù)據(jù)庫被分為1250 個Paxos groups处渣，并且有100個測試Clients持續(xù)地以50000讀/秒的速度不停地執(zhí)行非快照讀操作伶贰。 所有的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书幕，系統(tǒng)的吞吐率重新回升到了大概100K 讀/秒 新荤，這主要是因為實驗的兩個設置：系統(tǒng)有一個額外的能力就是當leader不可用的時候，所有的操作都會排隊台汇。 因此苛骨，系統(tǒng)的吞吐率會一直回升，直到達到一個很定的速率励七。我們也可以看看將Paxos leader的任期租約延長到10秒鐘的效果智袭。當我們kill掉Zone的時候，屬于該Zone的各個Paxos Groups中的leader的租約過期時間會均勻的分布在下一個10秒鐘內(nèi)掠抬。 當一個已經(jīng)死亡的leader的租約一旦過期吼野，就會馬上選舉出一個新的leader。大約在kill掉一個Zone之后的10秒鐘两波，所有的Paxos Groups都會擁有l(wèi)eader瞳步，并且吞吐量得到了恢復闷哆。更短的leader租約時間將會降低由leader死亡而導致的可用性的影響,但是由于其需要更加頻繁的更新租約信息，因此增加了網(wǎng)絡開銷单起。我們正在設計并實現(xiàn)一種機制：當leader一旦失效抱怔，就可以讓slave馬上釋放Paxos leader租約。

5.3 TrueTime

關于TrueTime嘀倒，必須回答兩個問題：ε是否就是時鐘不確定性的邊界屈留？ε（時間不確定性區(qū)間絕對值）最糟糕的情況下會有多大？對于第一個問題测蘑，最嚴峻的問題就是灌危，如果一個局部的時鐘漂移大于200us/sec，那就會破壞TrueTime的假設碳胳。我們的服務器統(tǒng)計數(shù)據(jù)顯示勇蝙，CPU出故障的概率要比時鐘出故障的概率高出6倍。也就是說挨约，相比而言硬件出故障的概率要比時鐘出故障的概率大的多味混。因此，我們也相信诫惭，TrueTime也和Spanner依賴的其他基礎軟件服務一樣翁锡，具備完備的穩(wěn)定性和可信賴性荚孵。
圖6顯示了從數(shù)千個跨多個數(shù)據(jù)中心的SpanServer上收集來的玲昧，這些數(shù)據(jù)中心相互之間的距離超過2200公里芯侥。圖中展示了ε（時間不確定性區(qū)間絕對值）的90%莲兢、99%和99.9%數(shù)數(shù)值波動情況，圖中的數(shù)據(jù)是在time slave daemon線程完成了對time master的投票之后落恼，對time slave daemon線程立即進行采樣收集的。這些采樣數(shù)據(jù)中不包含由于本地時鐘不確定性而引入的鋸齒數(shù)據(jù)。這些抽樣數(shù)據(jù)沒有考慮由于時鐘不確定性帶來的ε值的鋸齒梨熙，因此測量到的數(shù)據(jù)的值是：time-master的不確定性（通常是0）再加上通訊延遲。

從圖6中的數(shù)據(jù)可以看出：在確定ε的基本值的時候的兩個重要因素都不是問題刀诬。但是咽扇，可能會存在明顯的tail-latency（拖尾延遲？什么叫tail-latency陕壹？這個我還沒有研究明白质欲，有清楚的同學可以告訴我）問題，而這個問題又會導致ε值升高糠馆。圖中嘶伟，3月30日tail-latency(拖尾延遲)的降低，是因為網(wǎng)絡的改進又碌，減少了瞬間網(wǎng)絡連接的擁堵九昧。在4月13日ε的值增加了绊袋，持續(xù)了大約1個小時，主要是因為例行維護時關閉了兩個time master铸鹰。我們會繼續(xù)調(diào)研并且消除引起TrueTime突發(fā)波動峰值的因素癌别。

5.4 F1

Spanner在2011年早期開始進行在線負載測試評估，當時它是作為谷歌廣告后臺F1[35]的重新實現(xiàn)的一部分蹋笼。這個后臺最開始是基于MySQL數(shù)據(jù)庫的展姐，在許多方面都采用手工數(shù)據(jù)分區(qū)。未經(jīng)壓縮的數(shù)據(jù)可以達到幾十TB剖毯，雖然幾十TB的數(shù)據(jù)量對于NoSQL產(chǎn)品而言數(shù)據(jù)量是很小的圾笨，但是，對于采用數(shù)據(jù)分區(qū)的MySQL而言速兔，數(shù)據(jù)量已經(jīng)大到難以支撐墅拭。MySQL的數(shù)據(jù)分片機制，會把每個客戶和所有相關的數(shù)據(jù)分配給一個固定的分區(qū)涣狗。這種部署方式谍婉，可以針對單個用戶的數(shù)據(jù)充分地利用索引并執(zhí)行復雜的查詢處理，但是需要在應用系統(tǒng)的業(yè)務邏輯代碼中摻雜著復雜的分區(qū)邏輯镀钓。隨著客戶數(shù)量的增長穗熬，對數(shù)據(jù)進行重新分區(qū)，代價是很大的丁溅。最近一次的重新分區(qū)唤蔗，花費了兩年的時間，為了降低風險窟赏，在多個團隊之間進行了大量的合作和測試妓柜。這種操作太復雜了，無法常常執(zhí)行涯穷，由此導致的結果是棍掐，團隊必須限制MySQL數(shù)據(jù)庫的增長，方法是拷况，把一些數(shù)據(jù)存儲在外部的Bigtable中作煌，這就會犧牲事務和查詢所有數(shù)據(jù)的能力。
F1團隊出于多個原因選擇使用Spanner赚瘦。首先粟誓，使用Spanner不需要手動進行reshard。其次起意，Spanner提供了同步復制和自動FailOver鹰服。 而若使用MySQL原生的主從復制很難實現(xiàn)FailOver，并且還有數(shù)據(jù)丟失和宕機的風險杜恰。最后获诈， F1需要強事務語義仍源，這NoSQL提供不了強事務語義保證。應用程序需要跨任意數(shù)據(jù)的事務性保證和一致性讀舔涎。F1團隊還需要在他們的數(shù)據(jù)上構建二級索引 (因為Spanner并沒有提供對二級索引的自動支持), 并且也有能力使用Spanner的事務來實現(xiàn)自己的全局一致性索引笼踩。
現(xiàn)在所有應用程序的寫入操作都不再通過MySQL的技術堆棧執(zhí)行而是通過F1發(fā)送給Spanner。F1 在美國西海岸地區(qū)有2個副本亡嫌，在東海岸有3個副本嚎于。 復制站點的選擇主要考慮對重大自然災害的應對以及前端應用服務器站點的位置。實際上挟冠，Spanner的自動FailOver對F1團隊來說是不可見的于购。盡管在過去的幾個月，Spanner有一些突發(fā)集群失效的情況知染，但是對F1團隊完全沒有影響肋僧。F1團隊只需要更新他們的數(shù)據(jù)庫Schema信息告知Spanner在哪里方式Paxos leader，從而保證這些leader盡量地離前端應用服務器近一些控淡。
Spanner的TimeStamp語義可以使其為F1在內(nèi)存中高效地維護從數(shù)據(jù)庫狀態(tài)計算得到數(shù)據(jù)結構嫌吠。F1 會為所有變更都維護一個邏輯歷史日志，它會作為每個事務的一部分寫入到Spanner掺炭。F1 會得到某個時間戳下的數(shù)據(jù)的完整快照辫诅，來初始化它的數(shù)據(jù)結構，然后根據(jù)數(shù)據(jù)的增量變化來更新這個數(shù)據(jù)結構涧狮。

表5顯示了F1中每個目錄的分片數(shù)量的分布情況炕矮。每個目錄通常對應于F1中應用堆棧中的一個用戶。絕大多數(shù)目錄（同時意味著絕大多數(shù)用戶）都只會包含一個分片者冤，這就意味著肤视，對于這些用戶數(shù)據(jù)的讀和寫操作只會發(fā)生在一個服務器上。多于100個分片的目錄涉枫，是那些包含F(xiàn)1二級索引的表：對這些表的多個分片進行寫操作的情況并不常見钢颂。F1團隊也只是在以事務的方式進行未經(jīng)優(yōu)化的批量數(shù)據(jù)加載時，才會碰到過這種情況拜银。

表6展示了從F1服務器上測量的Spanner操作的延遲。在東海岸數(shù)據(jù)中心的副本遭垛，在選擇Paxos領導者方面會獲得更高的優(yōu)先級尼桶。表6中的數(shù)據(jù)是從這些數(shù)據(jù)中心的F1服務器上測量得到的。寫操作延遲存在較大的標準差锯仪，是由于鎖沖突引起的肥尾效應（fat tail）泵督。在讀操作延遲上存在更大的標準差，部分是因為Paxos領導者跨越了兩個數(shù)據(jù)中心庶喜，而只有其中的一個數(shù)據(jù)中心是采用了SSD硬盤小腊。此外救鲤，測試內(nèi)容還包括系統(tǒng)中的每個兩個數(shù)據(jù)中心的每個讀操作：字節(jié)讀操作的平均值和標準差分別是1.6KB和119KB。

6 相關工作

Megastore[5]和DynamoDB[3]已經(jīng)提供了跨越多個數(shù)據(jù)中心的一致性復制服務秩冈。DynamoDB提供了鍵值存儲接口本缠，只能在一個region內(nèi)部進行復制。Spanner和Megastore一樣入问，都提供了半關系數(shù)據(jù)模型丹锹，甚至采用了類似的模式定義語言。Megastore的性能并不高芬失。Megastore是架構在Bigtable之上楣黍，這種方式需要付出很高的通訊代價。Megastore也不支持長壽命的領導者：多個副本可能會發(fā)起寫操作棱烂。來自不同副本的寫操作租漂，即使他們不會發(fā)生邏輯沖突，在Paxos協(xié)議下也一定會發(fā)生沖突颊糜，：會嚴重影響吞吐量哩治，在一個Paxos組內(nèi)每秒鐘只能執(zhí)行幾個寫操作。Spanner提供了更高的性能芭析，通用的事務和外部一致性锚扎。
Pavlo等人[31]對數(shù)據(jù)庫和MapReduce[12]的性能進行了比較。他們指出了幾個已經(jīng)付出的努力：通過分布式鍵值存儲之上融合數(shù)據(jù)庫的功能性[1][4][7][41]馁启，證明了二者可以實現(xiàn)充分的融合驾孔。我們比較贊同這個結論，并且認為集成多個層是具有優(yōu)勢的：例如把復制和并發(fā)控制集成起來惯疙，可以減少Spanner中的提交等待代價翠勉。
在一個采用了復制的存儲上面實現(xiàn)事務的理念，可以至少追溯到Gifford的論文[16]霉颠。Scatter[17]就是目前比較流行的一個基于DHT的鍵值存儲对碌，Scatter在一致性復制的基礎上實現(xiàn)了事務。Spanner則比Scatter提供了更高層次的接口蒿偎。Gray和Lamport[18]描述了一個基于Paxos的非阻塞的提交協(xié)議朽们，這種協(xié)議與兩階段提交協(xié)議相比引入了更多的通訊正本，而兩階段提交協(xié)議則會在設計多個Group的時候加劇提交成本诉位。Walter[36]提供了另一種方案骑脱，這種方案是快照隔離的變種，但是無法跨越數(shù)據(jù)中心苍糠。相反叁丧，我們的只讀事務提供了一個更加自然的語義，因為，我們對于所有的操作都支持外部一致性拥娄。
在減少或者消除鎖開銷方面已經(jīng)進行了一系列的研究工作蚊锹。Calvin[40]消除了并發(fā)控制：它會重新分配時間戳，然后以時間戳的順序執(zhí)行事務稚瘾。HStore[39]和Granola[11]都可以根據(jù)自己的事務類型進行分類牡昆，有些事務類型可以避免鎖機制。但是孟抗，這些系統(tǒng)都無法提供外部一致性迁杨。Spanner通過提供快照隔離，解決了鎖沖突問題凄硼。
VoltDB[42]是一個分片的內(nèi)存數(shù)據(jù)庫铅协，它可以支持廣域主從復制，支持災難恢復摊沉，但是沒有提供通用的復制配置狐史。VoltDB屬于NewSQL的產(chǎn)品，可以支持可擴展的SQL[38]说墨。許多商業(yè)數(shù)據(jù)庫都支持歷史數(shù)據(jù)讀取骏全，比如：Marklogic[26]和Oracle的Total Recall[30]。Lomet和Li[24]針對這種時序數(shù)據(jù)庫提出了一種實現(xiàn)策略尼斧。
Faresite給出了與一個信任的時鐘參考值[13]相關的姜贡、時鐘不確定性的邊界（要比TrueTime更加寬松）：Farsite中的服務器租約的維護方式與Spanner中維護Paxos租約的方式相同。在之前的工作中[2][23]棺棵，寬松的同步時鐘已經(jīng)被用來進行并發(fā)控制楼咳。我們已經(jīng)展示了TrueTime可以從Paxos狀態(tài)機集合中推導出全球時間。

7. 未來的工作

在過去一年的大部分時間里烛恤，我們都是F1團隊一起工作母怜，把谷歌的廣告后臺從MySQL遷移到Spanner。我們正在積極改進它的監(jiān)控和支撐工具缚柏，同時也在優(yōu)化性能苹熏。此外，我們已經(jīng)開展了大量工作來改進備份/恢復系統(tǒng)的功能和性能币喧。我們當前正在實現(xiàn)Spanner模式語言轨域，二級索引的自動維護和基于負載的自動Resharding。未來杀餐，我們會調(diào)研更多的特性疙挺。我們一直追求以并行的方式進行樂觀讀，但是以現(xiàn)階段來看實現(xiàn)這個目標比較難怜浅。此外，我們計劃最終可以支持直接變更Paxos配置[22][34]。
我們希望許多應用都可以跨越數(shù)據(jù)中心（彼此距離比較近的數(shù)據(jù)中心）進行復制恶座。TrueTime 的ε可能會明顯地影響性能搀暑。我們可以很輕易地把ε值降低到1ms以內(nèi)。Time-master-query的間隔可以被進一步減少跨琳，而且時鐘晶體也會越來越好自点，越來越便宜。Time-master-query延遲會隨著網(wǎng)絡的改進而減少脉让，或者通過采用分時技術來避免延遲桂敛。
最后，還有許多有待改進的方面溅潜。雖然Spanner在節(jié)點數(shù)量上是可擴展的术唬，其節(jié)點本地性的數(shù)據(jù)結構在執(zhí)行復雜的SQL查詢的時候性能會比較差，因為這些數(shù)據(jù)結構是針對于簡單的鍵值訪問的而設計的滚澜。數(shù)據(jù)庫文獻中的算法和數(shù)據(jù)結構粗仓，可以極大改進單個節(jié)點的性能。另外设捐，我們已經(jīng)準備實現(xiàn)根據(jù)客戶端負載的變化在數(shù)據(jù)中心之間自動轉移數(shù)據(jù)的功能借浊，但是，為了有效實現(xiàn)這個功能萝招，我們必須具備在數(shù)據(jù)中心之間自動蚂斤、協(xié)調(diào)地轉移客戶端應用進程的能力。轉移進程會帶來更加困難的問題——如何在數(shù)據(jù)中心之間管理和分配資源槐沼。

8. 總結

總的來說曙蒸，Spanner對來自兩個研究團隊的思想和結晶進行了結合和擴充：一個是數(shù)據(jù)庫研究團隊，包括熟悉易用的半關系接口母赵，事務和基于SQL的查詢語言逸爵；另一個是系統(tǒng)研究團隊，包括可擴展性凹嘲，自動分區(qū)师倔，容錯，一致性復制周蹭，外部一致性和廣域分布式趋艘。自從Spanner產(chǎn)品成型之后，我們花費了5年以上的時間來完成當前版本的設計和實現(xiàn)不斷完善和迭代凶朗。之所以花費這么長的時間瓷胧，一部分原因在于我們慢慢意識到，Spanner不僅要解決全局復制的命名空間的問題棚愤，還應該關注Bigtable中所丟失的數(shù)據(jù)庫特性搓萧。
我們的設計中一個亮點就是TrueTime杂数。我們發(fā)現(xiàn)承認時間API中的時鐘不確定性可以幫助我們構建具備強時間語義的分布式系統(tǒng)。此外瘸洛，因為底層的系統(tǒng)在時鐘不確定性上采用更加嚴格的邊界揍移，實現(xiàn)更強的時間語義的代價就會減少。作為一個研究群體反肋，我們在設計分布式算法時那伐，不再依賴于弱同步的時鐘和弱時間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.