來源：https://www.cnblogs.com/linbingdong/p/6388621.html
本文由廈門大學計算機系教師林子雨翻譯，翻譯質量很高，本人只對極少數翻譯得不太恰當的地方進行了修改。
【摘要】:Spanner 是谷歌公司研發的、可擴展的、多版本、全球分佈式、同步複製數據庫。它是第一個把數據分佈在全球範圍內的系統，並且支持外部一致性的分佈式事務。本文描述了 Spanner 的架構、特性、不同設計決策的背後機理和一個新的時間 API，這個 API 可以暴露時鐘的不確定性。這個 API 及其實現，對於支持外部一致性和許多強大特性而言，是非常重要的，這些強大特性包括:非阻塞的讀、不採用鎖機制的只讀事務、原子模式變更。
【關鍵詞】Google Spanner, Bigtable, distributed database
1 介紹
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 部分討論了相關工作，並給出總結。
2 實現
本部分內容描述了 Spanner 的結構和背後的實現機理，然後描述了目錄抽象，它被用來管理副本和局部性，並介紹了數據的轉移單位。最後，將討論我們的數據模型，從而說明為什麼 Spanner 看起來更加像一個關係數據庫，而不是一個鍵值數據庫;還會討論應用如何可以控制數據的局部性。
一個 Spanner 部署稱為一個 universe。假設 Spanner 在全球範圍內管理數據，那麼，將會只有可數的、運行中的 universe。我們當前正在運行一個測試用的 universe，一個部署/線上用的 universe 和一個只用於線上應用的 universe。
Spanner 被組織成許多個 zone 的集合，每個 zone 都大概像一個 BigTable 服務器的部署。 zone 是管理部署的基本單元。zone 的集合也是數據可以被複制到的位置的集合。當新的數據中心加入服務，或者老的數據中心被關閉時，zone 可以被加入到一個運行的系統中，或者從中移除。zone 也是物理隔離的單元，在一個數據中心中，可能有一個或者多個 zone， 例如，當屬於不同應用的數據必須被分區存儲到同一個數據中心的不同服務器集合中時，一個數據中心就會有多個 zone 。
圖 1 顯示了在一個 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 的實現之上的。圖 2 顯示了軟件棧。在底部，每個 spanserver 負載管理 100-1000 個稱為 tablet 的數據結構的實例。一個 tablet 就類似於 BigTable 中的 tablet，也實現了下面的映射: (key:string, timestamp:int64)->string
與 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 組之間進行移動時，會一個目錄一個目錄地轉移，如圖 3 所示。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)。採用這種結構是很有用的，因為這可以讓應用通過選擇鍵來控制數據的局部性。
圖 4 包含了一個 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 API，並大概給出它的實現方法。我們把大量細節內容放在另一篇論文中，我們的目標是展示這種 API 的力量。表 1 列出了 API 的方法。TrueTime 會顯式地把時間表達成 TTinterval，這是一個時間區間，具有有界限的時間不確定性(不像其他 的標準時間接口，沒有為客戶端提供―不確定性‖這種概念)。TTinterval 區間的端點是 TTstamp 類型。TT.now()方法會返回一個 TTinterval，它可以保證包含 TT.now()方法在調用時的絕對 時間。這個時間和具備閏秒塗抹(leap-second smearing)的 UNIX 時間一樣。把即時誤差邊 界定義為 ε,平均誤差邊界為ε。TT.after()和 TT.before()方法是針對 TT.now()的便捷的包裝器。
表示一個事件 e 的絕對時間，可以利用函數 tabs(e)。如果用更加形式化的術語，TrueTime 可以保證，對於一個調用 tt=TT.now()，有 tt.earliest≤tabs(enow)≤tt.latest，其中， enow 是調用的事件。
在底層，TrueTime 使用的時間是 GPS 和原子鐘。TrueTime 使用兩種類型的時間，是因為它們有不同的失敗模式。GPS 參考時間的弱點是天線和接收器失效、局部電磁干擾和相關失敗(比如設計上的缺陷導致無法正確處理閏秒和電子欺騙)，以及 GPS 系統運行中斷。原子鐘也會失效，不過失效的方式和 GPS 無關，不同原子鐘之間的失效也沒有彼此關聯。 由於存在頻率誤差，在經過很長的時間以後，原子鐘都會產生明顯誤差。
TrueTime 是由每個數據中心上面的許多 time master 機器和每臺機器上的一個 timeslave daemon 來共同實現的。大多數 master 都有具備專用天線的 GPS 接收器，這些 master 在物理上是相互隔離的，這樣可以減少天線失效、電磁干擾和電子欺騙的影響。剩餘的 master (我們稱為 Armageddon master)則配備了原子鐘。一個原子鐘並不是很昂貴:一個 Armageddon master 的花費和一個 GPS master 的花費是同一個數量級的。所有 master 的時間 參考值都會進行彼此校對。每個 master 也會交叉檢查時間參考值和本地時間的比值，如果二者差別太大，就會把自己驅逐出去。在同步期間，Armageddon master 會表現出一個逐漸增加的時間不確定性，這是由保守應用的最差時鐘漂移引起的。GPS master 表現出的時間不確定性幾乎接近於 0。
每個 daemon 會從許多 master[29]中收集投票，獲得時間參考值，從而減少誤差。被選中的 master 中，有些 master 是 GPS master，是從附近的數據中心獲得的，剩餘的 GPS master 是從遠處的數據中心獲得的;還有一些是 Armageddon master。Daemon 會使用一個 Marzullo 算法[27]的變種，來探測和拒絕欺騙，並且把本地時鐘同步到非撒謊 master 的時間參考值。 為了免受較差的本地時鐘的影響，我們會根據組件規範和運行環境確定一個界限，如果機器的本地時鐘誤差頻繁超出這個界限，這個機器就會被驅逐出去。
在同步期間，一個 daemon 會表現出逐漸增加的時間不確定性。ε 是從保守應用的最差 時鐘漂移中得到的。ε 也取決於 time master 的不確定性，以及與 time master 之間的通訊延遲。在我們的線上應用環境中，ε 通常是一個關於時間的鋸齒形函數。在每個投票間隔中， ε 會在 1 到 7ms 之間變化。因此，在大多數情況下，ε的值是 4ms。Daemon 的投票間隔，在當前是 30 秒，當前使用的時鐘漂移比率是 200 微秒/秒，二者一起意味著 0 到 6ms 的鋸齒形邊界。剩餘的 1ms 主要來自到 time master 的通訊延遲。在失敗的時候，超過這個鋸齒形邊界也是有可能的。例如，偶爾的 time master 不確定性，可能會引起整個數據中心範圍內的 ε 值的增加。類似的，過載的機器或者網絡連接，都會導致 ε 值偶爾地局部增大。
4 併發控制
本部分內容描述 TrueTime 如何可以用來保證併發控制的正確性，以及這些屬性如何用來實現一些關鍵特性，比如外部一致性的事務、無鎖機制的只讀事務、針對歷史數據的非阻塞讀。這些特性可以保證，在時間戳為 t 的時刻的數據庫讀操作，一定只能看到在 t 時刻之 前已經提交的事務。
進一步說，把 Spanner 客戶端的寫操作和 Paxos 看到的寫操作這二者進行區分，是非常重要的，我們把 Paxos 看到的寫操作稱為 Paxos 寫操作。例如，兩階段提交會為準備提交階段生成一個 Paxos 寫操作，這時不會有相應的客戶端寫操作。
4.1 時間戳管理
表 2 列出了 Spanner 支持的操作的類型。Spanner 可以支持讀寫事務、只讀事務(預先聲明的快照隔離事務)和快照讀。獨立寫操作，會被當成讀寫事務來執行。非快照獨立讀操作，會被當成只讀事務來執行。二者都是在內部進行 retry，客戶端不用進行這種 retry loop。
一個只讀事務具備快照隔離的性能優勢[6]。一個只讀事務必須事先被聲明不會包含任何寫操作，它並不是一個簡單的不包含寫操作的讀寫事務。在一個只讀事務中的讀操作，在執行時會採用一個系統選擇的時間戳，不包含鎖機制，因此，後面到達的寫操作不會被阻塞。 在一個只讀事務中的讀操作，可以到任何足夠新的副本上去執行(見第 4.1.3 節)。
一個快照讀操作，是針對歷史數據的讀取，執行過程中，不需要鎖機制。一個客戶端可以為快照讀確定一個時間戳，或者提供一個時間範圍讓 Spanner 來自動選擇時間戳。不管是 哪種情況，快照讀操作都可以在任何具有足夠新的副本上執行。
對於只讀事務和快照讀而言，一旦已經選定一個時間戳，那麼，提交就是不可避免的，除非在那個時間點的數據已經被垃圾回收了。因此，客戶端不必在 retry loop 中緩存結果。 當一個服務器失效的時候，客戶端就可以使用同樣的時間戳和當前的讀位置，在另外一個服務器上繼續執行讀操作。
4.1.1 Paxos 領導者租約
Spanner 的 Paxos 實現中使用了時間化的租約，來實現長時間的領導者地位(默認是 10秒)。一個潛在的領導者會發起請求，請求時間化的租約投票，在收到指定數量的投票後，這個領導者就可以確定自己擁有了一個租約。一個副本在成功完成一個寫操作後，會隱式地延期自己的租約。對於一個領導者而言，如果它的租約快要到期了，就要顯示地請求租約延期。另一個領導者的租約有個時間區間，這個時間區間的起點就是這個領導者獲得指定數量的投票那一刻，時間區間的終點就是這個領導者失去指定數量的投票的那一刻(因為有些投 票已經過期了)。Spanner 依賴於下面這些“不連貫性”:對於每個 Paxos 組，每個 Paxos 領 導者的租約時間區間，是和其他領導者的時間區間完全隔離的。附錄 A 顯示瞭如何強制實現這些不連貫性。
Spanner 實現允許一個 Paxos 領導者通過把 slave 從租約投票中釋放出來這種方式，實現領導者的退位。為了保持這種彼此隔離的不連貫性，Spanner 會對什麼時候退位做出限制。把 smax 定義為一個領導者可以使用的最大的時間戳。在退位之前，一個領導者必須等到 TT.after(smax)是真。
4.1.2 為讀寫事務分配時間戳
事務讀和寫採用兩段鎖協議。當所有的鎖都已經獲得以後，在任何鎖被釋放之前，就可以給事務分配時間戳。對於一個給定的事務，Spanner 會為事務分配時間戳，這個時間戳是 Paxos 分配給 Paxos 寫操作的，它代表了事務提交的時間。
Spanner 依賴下面這些單調性:在每個 Paxos 組內，Spanner 會以單調增加的順序給每個 Paxos 寫操作分配時間戳，即使在跨越多個領導者時也是如此。一個單個的領導者副本，可以很容易地以單調增加的方式分配時間戳。在多個領導者之間就會強制實現彼此隔離的不連 貫:一個領導者必須只能分配屬於它自己租約時間區間內的時間戳。要注意到，一旦一個時間戳 s 被分配，smax 就會被增加到 s，從而保證彼此隔離性(不連貫性)。
Spanner 也會實現下面的外部一致性:如果一個事務 T2 在事務 T1 提交以後開始執行， 那麼，事務 T2 的時間戳一定比事務 T1 的時間戳大。對於一個事務 Ti 而言，定義開始和提交事件eistart和eicommit，事務提交時間為si。對外部一致性的要求就變成了:
tabs(e1commit ) Start. 為一個事務 Ti 擔任協調者的領導者分配一個提交時間戳 si，不會小於 TT.now().latest 的值，TT.now().latest的值是在esierver事件之後計算得到的。要注意，擔任參與者的領導者， 在這裡不起作用。第 4.2.1 節描述了這些擔任參與者的領導者是如何參與下一條規則的實現的。 Commit Wait. 擔任協調者的領導者，必須確保客戶端不能看到任何被 Ti 提交的數據，直到 TT.after(si)為真。提交等待，就是要確保 si 會比 Ti 的絕對提交時間小。提交等待的實現在 4.2.1 節中描述。證明如下:
4.1.3 在某個時間戳下的讀操作
第 4.1.2 節中描述的單調性，使得 Spanner 可以正確地確定一個副本是否足夠新，從而能夠滿足一個讀操作的要求。每個副本都會跟蹤記錄一個值，這個值被稱為安全時間 tsafe，它是一個副本最近更新後的最大時間戳。如果一個讀操作的時間戳是 t，當滿足 t<=tsafe 時， 這個副本就可以被這個讀操作讀取。
。。。
4.1.4 為只讀事務分配時間戳
一個只讀事務分成兩個階段執行:分配一個時間戳 sread[8]，然後當成 sread 時刻的快照讀來執行事務讀操作。快照讀可以在任何足夠新的副本上面執行。
在一個事務開始後的任意時刻，可以簡單地分配 sread=TT.now().latest，通過第 4.1.2 節中描述過的類似的方式來維護外部一致性。但是，對於時間戳 sread 而言，如果 tsafe 沒有增加到足夠大，可能需要對 sread 時刻的讀操作進行阻塞。除此以外還要注意，選擇一個 sread 的值可 能也會增加 smax 的值，從而保證不連貫性。為了減少阻塞的概率，Spanner 應該分配可以保持外部一致性的最老的時間戳。第 4.2.2 節描述瞭如何選擇這種時間戳。
4.2 細節
這部分內容介紹一些讀寫操作和只讀操作的實踐細節，以及用來實現原子模式變更的特定事務的實現方法。然後，描述一些基本模式的細化。
4.2.1 讀寫事務
就像 Bigtable 一樣，發生在一個事務中的寫操作會在客戶端進行緩存，直到提交。由此導致的結果是，在一個事務中的讀操作，不會看到這個事務的寫操作的結果。這種設計在 Spanner 中可以很好地工作，因為一個讀操作可以返回任何數據讀的時間戳，未提交的寫操作還沒有被分配時間戳。
在讀寫事務內部的讀操作，使用傷停等待(wound-wait)[33]來避免死鎖。客戶端對位於合適組內的領導者副本發起讀操作，需要首先獲得讀鎖，然後讀取最新的數據。當一個客戶端事務保持活躍的時候，它會發送“保持活躍”信息，防止那些參與的領導者讓該事務過時。當一個客戶端已經完成了所有的讀操作，並且緩衝了所有的寫操作，它就開始兩階段提交。客戶端選擇一個協調者組，並且發送一個提交信息給每個參與的、具有協調者標識的領導者，併發送提交信息給任何緩衝的寫操作。讓客戶端發起兩階段提交操作，可以避免在大範圍連接內發送兩次數據。
一個參與其中的、扮演非協調者角色的領導者，首先需要獲得寫鎖。然後，它會選擇一 個預備時間戳，這個時間戳應該比之前分配給其他事務的任何時間戳都要大(這樣可以保持 單調性)，並且通過 Paxos 把準備提交記錄寫入日誌。然後，每個參與者就把自己的準備時 間戳通知給協調者。
扮演協調者的領導者，也會首先獲得寫鎖，但是，會跳過準備階段。在從所有其他的、扮演參與者的領導者那裡獲得信息後，它就會為整個事務選擇一個時間戳。這個提交時間戳 s 必須大於或等於所有的準備時間戳(這是為了滿足第 4.1.3 節討論的限制條件)，在協調者收到它的提交信息時，s 應該大於 TT.now().latest，並且 s 應該大於這個領導者為之前的其他 所有事務分配的時間戳(再次指出，這樣做是為了滿足單調性)。這個扮演協調者的領導者，就會通過 Paxos 在日誌中寫入一個提交記錄(或者當等待其他參與者發生超時就在日誌中寫 入終止記錄)。
在允許任何協調者副本去提交記錄之前，扮演協調者的領導者會一直等待到 TT.after(s)， 從而可以保證遵循第 4.1.2 節中描述的提交等待規則。因為，扮演協調者的領導者會根據 TT.now().latest 來選擇 s，而且必須等待直到那個時間戳可以確保成為過去，預期的等待時間 至少是 2*ε。這種等待時間通常會和 Paxos 通信時間發生重疊。在提交等待之後，協調者就會發送一個提交時間戳給客戶端和所有其他參與的領導者。每個參與的領導者會通過 Paxos 把事務結果寫入日誌。所有的參與者會在同一個時間戳進行提交，然後釋放鎖。
4.2.2 只讀事務
分配一個時間戳需要一個協商階段，這個協商發生在所有參與到該讀操作中的 Paxos 組之間。由此導致的結果是，Spanner 需要為每個只讀事務提供一個 scope 表達式，它可以指出整個事務需要讀取哪些鍵。對於單獨的查詢，Spanner 可以自動計算出 scope。
如果 scope 的值是由單個 Paxos 組來提供的，那麼，客戶端就會給那個組的領導者發起一個只讀事務(當前的 Spanner 實現中，只會為 Paxos leader 中的只讀事務選擇一個時間戳)， 為那個領導者分配 sread 並且執行讀操作。對於一個單個位置的讀操作，Spanner 通常會比 TT.now().latest 做得更好。我們把 LastTS()定義為在 Paxos 組中最後提交的寫操作的時間戳。如果沒有準備提交的事務，這個分配到的時間戳 sread=LastTS()就很容易滿足外部一致性要求: 這個事務將可以看見最後一個寫操作的結果，然後排隊排在它之後。
如果 scope 的值是由多個 Paxos 組來提供的，就會有幾種選擇。最複雜的選擇就是，和所有組的領導者進行一輪溝通，大家根據 LastTS()進行協商得到 sread。Spanner 當前實現了一個更加簡單的選擇。這個選擇可以避免一輪協商，讓讀操作在 sread=TT.now().latest 時刻去 執行(這可能會等待安全時間的增加)。這個事務中的所有讀操作，可以被髮送到任何足夠 新的副本上執行。
4.2.3 模式變更事務
TrueTime 允許 Spanner 支持原子模式變更。使用一個標準的事務是不可行的，因為參與者的數量(即數據庫中組的數量)可能達到幾百萬個。Bigtable 可以支持在一個數據中心內進行原子模式變更，但是，這個操作會阻塞所有其他操作。
一個 Spanner 模式變更事務通常是一個標準事務的、非阻塞的變種。首先，它會顯式地分配一個未來的時間戳，這個時間戳會在準備階段進行註冊。由此，跨越幾千個服務器的模式變更，可以在不打擾其他併發活動的前提下完成。其次，讀操作和寫操作，它們都是隱式地依賴於模式，它們都會和任何註冊的模式變更時間戳t保持同步:當它們的時間戳小於 t 時， 讀寫操作就執行到時刻 t;當它們的時間戳大於時刻 t 時，讀寫操作就必須阻塞，在模式變更事務後面進行等待。如果沒有 TrueTime，那麼定義模式變更發生在 t 時刻，就變得毫無意義。
5. 實驗分析
我們對 Spanner 性能進行了測試，包括複製、事務和可用性。然後，我們提供了一些關於 TrueTime 的實驗數據，並且提供了我們的第一個用例——F1。
5.1 微測試基準
表 3 給出了一用於 Spanner 的微測試基準(microbenchmark)。這些測試是在分時機器上實現的:每個 spanserver 採用 4GB 內存和四核 CPU(AMD Barcelona 2200MHz)。客戶端運行在單獨的機器上。每個 zone 都包含一個 spanserver。客戶端和 zone 都放在一個數據中心集合內，它們之間的網絡距離不會超過 1ms。這種佈局是很普通的，許多數據並不需要把數 據分散存儲到全球各地)。測試數據庫具有 50 個 Paxos 組和 2500 個目錄。操作都是獨立的 4KB 大小的讀和寫。All reads were served out of memory after a compaction，從而使得我們只需要衡量 Spanner 調用棧的開銷。此外，還會進行一輪讀操作，來預熱任何位置的緩存。
對於延遲實驗而言，客戶端會發起足夠少量的操作，從而避免在服務器中發生排隊。從 1 個副本的實驗中，提交等待大約是 5ms，Paxos 延遲大約是 9ms。隨著副本數量的增加， 延遲大約保持不變，只具有很少的標準差，因為在一個組的副本內，Paxos 會並行執行。隨著副本數量的增加，獲得指定投票數量的延遲對一個 slave 副本的慢速度不會很敏感。
對於吞吐量的實驗而言，客戶端發起足夠數量的操作，從而使得 CPU 處理能力達到飽和。快照讀操作可以在任何足夠新的副本上進行，因此，快照讀的吞吐量會隨著副本的數量增加而線性增加。單個讀的只讀事務，只會在領導者上執行，因為，時間戳分配必須發生在領導者上。只讀事務吞吐量會隨著副本數量的增加而增加，因為有效的 spanserver 的數量會增加:在這個實驗的設置中，spanserver 的數量和副本的數量相同，領導者會被隨機分配到不同的 zone。寫操作的吞吐量也會從這種實驗設置中獲得收益(副本從 3 變到 5 時寫操作吞吐量增加了，就能夠說明這點)，但是，隨著副本數量的增加，每個寫操作執行時需要完 成的工作量也會線性增加，這就會抵消前面的收益。
表 4 顯示了兩階段提交可以擴展到合理數量的參與者:它是對一系列實驗的總結，這些實驗運行在 3 個 zone 上，每個 zone 具有 25 個 spanserver。擴展到 50 個參與者，無論在平均值還是第 99 個百分位方面，都是合理的。在 100 個參與者的情形下，延遲開發明顯增加。
5.2 可用性
圖 5 顯示了在多個數據中心運行 Spanner 時的可用性方面的收益。它顯示了三個吞吐量實驗的結果，並且存在數據中心失敗的情形，所有三個實驗結果都被重疊放置到一個時間軸 上。測試用的 universe 包含 5 個 zone Zi，每個 zone 都擁有 25 個 spanserver。測試數據庫被 分片成 1250 個 Paxos 組，100 個客戶端不斷地發送非快照讀操作，累積速率是每秒 50K 個讀操作。所有領導者都會被顯式地放置到 Z1。每個測試進行 5 秒鐘以後，一個 zone 中的所有服務器都會被“殺死”:non-leader 殺掉 Z2，leader-hard 殺掉 Z1，leader-soft 殺掉 Z1，但是，它會首先通知所有服務器它們將要交出領導權。
殺掉 Z2 對於讀操作吞吐量沒有影響。殺掉 Z1，給領導者一些時間來把領導權交給另一個 zone 時，會產生一個小的影響:吞吐量會下降，不是很明顯，大概下降 3-4%。另一方面，沒有預警就殺掉 Z1 有一個明顯的影響:完成率幾乎下降到 0。隨著領導者被重新選擇，系統的吞吐量會增加到大約每秒 100K 個讀操作，主要是由於我們的實驗設置:系統中有額外的能力，當找不到領導者時操作會排隊。由此導致的結果是，系統的吞吐量會增加直到到達 系統恆定的速率。
我們可以看看把 Paxos 領導者租約設置為 10ms 的效果。當我們殺掉這個 zone，對於這 個組的領導者租約的過期時間，會均勻地分佈到接下來的 10 秒鐘內。來自一個死亡的領導者的每個租約一旦過期，就會選擇一個新的領導者。大約在殺死時間過去 10 秒鐘以後，所有的組都會有領導者，吞吐量就恢復了。短的租約時間會降低服務器死亡對於可用性的影響， 但是，需要更多的更新租約的網絡通訊開銷。我們正在設計和實現一種機制，它可以在領導者失效的時候，讓 slave 釋放 Paxos 領導者租約。
5.3 TrueTime
關於 TrueTime，必須回答兩個問題: ε 是否就是時鐘不確定性的邊界? ε 會變得多糟糕? 對於第一個問題，最嚴峻的問題就是，如果一個局部的時鐘漂移大於 200us/sec，那就會破壞 TrueTime 的假設。我們的機器統計數據顯示，壞的 CPU 的出現概率要比壞的時鐘出現概率大 6 倍。也就是說，與更加嚴峻的硬件問題相比，時鐘問題是很少見的。由此，我們也相信，TrueTime 的實現和 Spanner 其他軟件組件一樣，具有很好的可靠性，值得信任。
圖 6 顯示了 TrueTime 數據，是從幾千個 spanserver 中收集的，這些 spanserver 跨越了多 個數據中心，距離 2200 公里以上。圖中描述了 ε 的第 90 個、99 個和 99.9 個百分位的情況， 是在對 timemaster 進行投票後立即對 timeslave daemon 進行樣本抽樣的。這些抽樣數據沒有考慮由於時鐘不確定性帶來的 ε 值的鋸齒，因此測量的是 timemaster 不確定性(通常是 0) 再加上通訊延遲。
圖 6 中的數據顯示了，在決定 ε 的基本值方面的上述兩個問題，通常都不會是個問題。 但是，可能會存在明顯的拖尾延遲問題，那會引起更高的 ε 值。圖中，3 月 30 日拖尾延遲的降低，是因為網絡的改進，減少了瞬間網絡連接的擁堵。在 4 月 13 日 ε 的值增加了，持續了大約 1 個小時，主要是因為例行維護時關閉了兩個 time master。我們會繼續調研並且消除引起 TrueTime 突變的因素。
5.4 F1
Spanner 在 2011 年早期開始進行在線負載測試，它是作為谷歌廣告後臺 F1[35]的重新實現的一部分。這個後臺最開始是基於 MySQL 數據庫，在許多方面都採用手工數據分區。未 經壓縮的數據可以達到幾十 TB，雖然這對於許多 NoSQL 實例而言數據量是很小的，但是， 對於採用數據分區的 MySQL 而言，數據量是非常大的。MySQL 的數據分片機制，會把每個客戶和所有相關的數據分配給一個固定的分區。這種佈局方式，可以支持針對單個客戶的 索引構建和複雜查詢處理，但是，需要了解一些商業知識來設計分區。隨著客戶數量的增長， 對數據進行重新分區，代價是很大的。最近一次的重新分區，花費了兩年的時間，為了降低風險，在多個團隊之間進行了大量的合作和測試。這種操作太複雜了，無法常常執行，由此導致的結果是，團隊必須限制 MySQL 數據庫的增長，方法是，把一些數據存儲在外部的 Bigtable 中，這就會犧牲事務和查詢所有數據的能力。
F1 團隊選擇使用 Spanner 有幾個方面的原因。首先，Spanner 不需要手工分區。其次， Spanner 提供了同步複製和自動失敗恢復。在採用 MySQL 的 master-slave 複製方法時，很難進行失敗恢復，會有數據丟失和當機的風險。再次，F1 需要強壯的事務語義，這使得使用 其他 NoSQL 系統是不實際的。應用語義需要跨越任意數據的事務和一致性讀。F1 團隊也需要在他們的數據上構建二級索引(因為 Spanner 沒有提供對二級索引的自動支持)，也有能力使用 Spanner 事務來實現他們自己的一致性全球索引。
所有應用寫操作，現在都是默認從 F1 發送到 Spanner。而不是發送到基於 MySQL 的應 用棧。F1 在美國的西岸有兩個副本，在東岸有三個副本。這種副本位置的選擇，是為了避免發生自然災害時出現服務停止問題，也是出於前端應用的位置的考慮。實際上，Spanner 的失敗自動恢復，幾乎是不可見的。在過去的幾個月中，儘管有不在計劃內的機群失效，但是，F1 團隊最需要做的工作仍然是更新他們的數據庫模式，來告訴 Spanner 在哪裡放置 Paxos 領導者，從而使得它們儘量靠近應用前端。
Spanner 時間戳語義，使得它對於 F1 而言，可以高效地維護從數據庫狀態計算得到的、放在內存中的數據結構。F1 會為所有變更都維護一個邏輯歷史日誌，它會作為每個事務的 一部分寫入到 Spanner。F1 會得到某個時間戳下的數據的完整快照，來初始化它的數據結構， 然後根據數據的增量變化來更新這個數據結構。
表 5 顯示了 F1 中每個目錄的分片數量的分佈情況。每個目錄通常對應於 F1 上的應用棧中的一個用戶。絕大多數目錄(同時意味著絕大多數用戶)都只會包含一個分片，這就意味著，對於這些用戶數據的讀和寫操作只會發生在一個服務器上。多於 100 個分片的目錄，是那些包含 F1 二級索引的表:對這些表的多個分片進行寫操作，是極其不尋常的。F1 團隊也只是在以事務的方式進行未經優化的批量數據加載時，才會碰到這種情形。
表 6 顯示了從 F1 服務器來測量的 Spanner 操作的延遲。在東海岸數據中心的副本，在 選擇 Paxos 領導者方面會獲得更高的優先級。表 6 中的數據是從這些數據中心的 F1 服務器 上測量得到的。寫操作延遲分佈上存在較大的標準差，是由於鎖衝突引起的肥尾效應(fat tail)。在讀操作延遲分佈上存在更大的標準差，部分是因為 Paxos 領導者跨越了兩個數據中心，只有其中的一個是採用了固態盤的機器。此外，測試內容還包括系統中的每個針對兩個 數據中心的讀操作:字節讀操作的平均值和標準差分別是 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 的鍵值存儲，可以在一致性複製上面實現事務。Spanner 則要比 Scatter 在更高的層次上提供接口。Gray 和 Lamport[18]描述了一個基於 Paxos 的非阻塞的提交協議，他們的協議會比兩階段提交協議帶來更多的代價，而兩階段提交協議在大範圍分佈 式的組中的代價會進一步惡化。Walter[36]提供了一個快照隔離的變種，但是無法跨越數據中心。相反，我們的只讀事務提供了一個更加自然的語義，因為我們對於所有的操作都支持外部語義。
最近，在減少或者消除鎖開銷方面已經有大量的研究工作。Calvin[40]消除了併發控制: 它會重新分配時間戳，然後以時間戳的順序執行事務。HStore[39]和 Granola[11]都支持自己的事務類型劃分方法，有些事務類型可以避免鎖機制。但是，這些系統都無法提供外部一致性。Spanner 通過提供快照隔離，解決了衝突問題。
VoltDB[42]是一個分片的內存數據庫，可以支持在大範圍區域內進行主從複製，支持災難恢復，但是沒有提供通用的複製配置方法。它是一個被稱為 NewSQL 的實例，這是實現 可擴展的 SQL[38]的強大的市場推動力。許多商業化的數據庫都可以支持歷史數據讀取，比如 Marklogic[26]和 Oracle’ Total Recall[30]。Lomet 和 Li[24]對於這種時間數據庫描述了一種 實現策略。
Faresite 給出了與一個受信任的時鐘參考值相關的時鐘不確定性的邊界13:Farsite 中的服務器租約的方式，和 Spanner 中維護 Paxos 租約的方式 相同。在之前的工作中[2][23]，寬鬆同步時鐘已經被用來進行併發控制。我們已經展示了 TrueTime 可以從 Paxos 狀態機集合中推導出全球時間。
7. 未來的工作
在過去一年的大部分時間裡，我們都是 F1 團隊一起工作，把谷歌的廣告後臺從 MySQL 遷移到 Spanner。我們正在積極改進它的監控和支撐工具，同時在優化性能。此外，我們已經開展了大量工作來改進備份恢復系統的功能和性能。我們當前正在實現 Spanner 模式語言，自動維護二級索引和自動基於負載的分區。在未來，我們會調研更多的特性。以最優化的方式並行執行讀操作，是我們追求的有價值的策略，但是，初級階段的實驗表明，實現這個目標比較艱難。此外，我們計劃最終可以支持直接變更 Paxos 配置[22]34]。
我們希望許多應用都可以跨越數據中心進行復制，並且這些數據中心彼此靠近。 TrueTime ε 可能會明顯影響性能。把 ε 值降低到 1ms 以內，並不存在不可克服的障礙。 Time-master-query 間隔可以繼續減少，Time-master-query 延遲應該隨著網絡的改進而減少， 或者通過採用分時技術來避免延遲。
最後，還有許多有待改進的方面。儘管 Spanner 在節點數量上是可擴展的，但是與節點相關的數據結構在複雜的 SQL 查詢上的性能相對較差，因為，它們是被設計成服務於簡單的鍵值訪問的。來自數據庫文獻的算法和數據結構，可以極大改進單個節點的性能。另外，根據客戶端負載的變化，在數據中心之間自動轉移數據，已經成為我們的一個目標，但是，為了有效實現這個目標，我們必須具備在數據中心之間自動、協調地轉移客戶端應用進程的能力。轉移進程會帶來更加困難的問題——如何在數據中心之間管理和分配資源。
8. 總結
總的來說，Spanner 對來自兩個研究群體的概念進行了結合和擴充:一個是數據庫研究群體，包括熟悉易用的半關係接口，事務和基於 SQL 的查詢語言;另一個是系統研究群體，包括可擴展性，自動分區，容錯，一致性複製，外部一致性和大範圍分佈。自從 Spanner 概念成形，我們花費了 5 年以上的時間來完成當前版本的設計和實現。花費這麼長的時間，一部分原因在於我們慢慢意識到，Spanner 不應該僅僅解決全球複製的命名空間問題，而且也應該關注 Bigtable 中所丟失的數據庫特性。
我們的設計中一個亮點特性就是 TrueTime。我們已經表明，在時間 API 中明確給出時鐘不確定性，可以以更加強壯的時間語義來構建分佈式系統。此外，因為底層的系統在時鐘不確定性上採用更加嚴格的邊界，實現更強壯的時間語義的代價就會減少。作為一個研究群體，我們在設計分佈式算法時，不再依賴於弱同步的時鐘和較弱的時間 API。
致謝
許多人幫助改進了這篇論文:Jon Howell，Atul Adya, Fay Chang, Frank Dabek, Sean Dorward, Bob Gruber, David Held, Nick Kline, Alex Thomson, and Joel Wein. 我們的管理層對於我們的工作和論文發表都非常支持:Aristotle Balogh, Bill Coughran, Urs H ̈olzle, Doron Meyer, Cos Nicolaou, Kathy Polizzi, Sridhar Ramaswany, and Shivakumar Venkataraman.
我們的工作是在Bigtable和Megastore團隊的工作基礎之上開展的。F1團隊，尤其是Jeff Shute ，和我們一起工作，開發了數據模型，跟蹤性能和糾正漏洞。Platforms團隊，尤其是Luiz Barroso 和Bob Felderman，幫助我們一起實現了TrueTime。最後，許多谷歌員工都曾經在我們的團隊工作過，包括Ken Ashcraft, Paul Cychosz, Krzysztof Ostrowski, Amir Voskoboynik, Matthew Weaver, Theo Vassilakis, and Eric Veach; or have joined our team recently: Nathan Bales, Adam Beberg, Vadim Borisov, Ken Chen, Brian Cooper, Cian Cullinan, Robert-Jan Huijsman, Milind Joshi, Andrey Khorlin, Dawid Kuroczko, Laramie Leavitt, Eric Li, Mike Mammarella, Sunil Mushran, Simon Nielsen, Ovidiu Platon, Ananth Shrinivas, Vadim Suvorov, and Marcel van der Holst.
參考文獻
[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.
[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.
閱讀更多 oscube 的文章
