Spanner是谷歌研發(fā)的、可擴展的、多版本、全球分布式、同步復(fù)制數(shù)據(jù)庫。它是第一個把數(shù)據(jù)分布在全球范圍內(nèi)的系統(tǒng)，并且支持外部一致性的分布式事務(wù)。本文描述了Spanner的架構(gòu)、特性、不同設(shè)計決策的背后機理和一個新的時間API，這個API可以暴露時鐘的不確定性。這個API及其實現(xiàn)，對于支持外部一致性和許多強大特性而言，是非常重要的，這些強大特性包括：非阻塞的讀、不采用鎖機制的只讀事務(wù)、原子模式變更。
介紹
Spanner是一個可擴展的、全球分布式的數(shù)據(jù)庫，是在谷歌設(shè)計、開發(fā)和部署的。在最高抽象層面，Spanner就是一個數(shù)據(jù)庫，把數(shù)據(jù)分片存儲在許多Paxos狀態(tài)機上，這些機器位于遍布全球的數(shù)據(jù)中心內(nèi)。復(fù)制技術(shù)可以用來服務(wù)于全球可用性和地理局部性?？蛻舳藭詣釉诟北局g進(jìn)行失敗恢復(fù)。隨著數(shù)據(jù)的變化和服務(wù)器的變化，Spanner會自動把數(shù)據(jù)進(jìn)行重新分片，從而有效應(yīng)對負(fù)載變化和處理失敗。Spanner被設(shè)計成可以擴展到幾百萬個機器節(jié)點，跨越成百上千個數(shù)據(jù)中心，具備幾萬億數(shù)據(jù)庫行的規(guī)模。應(yīng)用可以借助于Spanner來實現(xiàn)高可用性，通過在一個洲的內(nèi)部和跨越不同的洲之間復(fù)制數(shù)據(jù)，保證即使面對大范圍的自然災(zāi)害時數(shù)據(jù)依然可用。我們最初的客戶是F1，一個谷歌廣告后臺的重新編程實現(xiàn)。一級方程式錦標(biāo)賽使用了跨越美國的5個副本。絕大多數(shù)其他應(yīng)用很可能會在屬于同一個地理范圍內(nèi)的3-5個數(shù)據(jù)中心內(nèi)放置數(shù)據(jù)副本，采用相對獨立的失敗模式。也就是說，許多應(yīng)用都會首先選擇低延遲，而不是高可用性，只要系統(tǒng)能夠從1-2個數(shù)據(jù)中心失敗中恢復(fù)過來。 Spanner的主要工作，就是管理跨越多個數(shù)據(jù)中心的數(shù)據(jù)副本，但是，在我們的分布式系統(tǒng)體系架構(gòu)之上設(shè)計和實現(xiàn)重要的數(shù)據(jù)庫特性方面，我們也花費了大量的時間。盡管有許多項目可以很好地使用BigTable，我們也不斷收到來自客戶的抱怨，客戶反映BigTable無法應(yīng)用到一些特定類型的應(yīng)用上面，比如具備復(fù)雜可變的模式，或者對于在大范圍內(nèi)分布的多個副本數(shù)據(jù)具有較高的一致性要求。其他研究人員也提出了類似的抱怨。谷歌的許多應(yīng)用已經(jīng)選擇使用Megastore，主要是因為它的半關(guān)系數(shù)據(jù)模型和對同步復(fù)制的支持，盡管Megastore具備較差的寫操作吞吐量。由于上述多個方面的因素，Spanner已經(jīng)從一個類似BigTable的單一版本的鍵值存儲，演化成為一個具有時間屬性的多版本的數(shù)據(jù)庫。數(shù)據(jù)被存儲到模式化的、半關(guān)系的表中，數(shù)據(jù)被版本化，每個版本都會自動以提交時間作為時間戳，舊版本的數(shù)據(jù)會更容易被垃圾回收。應(yīng)用可以讀取舊版本的數(shù)據(jù)。Spanner支持通用的事務(wù)，提供了基于SQL的查詢語言。作為一個全球分布式數(shù)據(jù)庫，Spanner提供了幾個有趣的特性：
第一，在數(shù)據(jù)的副本配置方面，應(yīng)用可以在一個很細(xì)的粒度上進(jìn)行動態(tài)控制。應(yīng)用可以詳細(xì)規(guī)定，哪些數(shù)據(jù)中心包含哪些數(shù)據(jù)，數(shù)據(jù)距離用戶有多遠(yuǎn)（控制用戶讀取數(shù)據(jù)的延遲），不同數(shù)據(jù)副本之間距離有多遠(yuǎn)（控制寫操作的延遲），以及需要維護(hù)多少個副本（控制可用性和讀操作性能）。數(shù)據(jù)也可以被動態(tài)和透明地在數(shù)據(jù)中心之間進(jìn)行移動，從而平衡不同數(shù)據(jù)中心內(nèi)資源的使用。
第二，Spanner有兩個重要的特性，很難在一個分布式數(shù)據(jù)庫上實現(xiàn)，即Spanner提供了讀和寫操作的外部一致性，以及在一個時間戳下面的跨越數(shù)據(jù)庫的全球一致性的讀操作。這些特性使得Spanner可以支持一致的備份、一致的MapReduce執(zhí)行和原子模式變更，所有都是在全球范圍內(nèi)實現(xiàn)，即使存在正在處理中的事務(wù)也可以。之所以可以支持這些特性，是因為Spanner可以為事務(wù)分配全球范圍內(nèi)有意義的提交時間戳，即使事務(wù)可能是分布式的。這些時間戳反映了事務(wù)序列化的順序。除此以外，這些序列化的順序滿足了外部一致性的要求：如果一個事務(wù)T1在另一個事務(wù)T2開始之前就已經(jīng)提交了，那么，T1的時間戳就要比T2的時間戳小。Spanner是第一個可以在全球范圍內(nèi)提供這種保證的系統(tǒng)。實現(xiàn)這種特性的關(guān)鍵技術(shù)就是一個新的TrueTime API及其實現(xiàn)。這個API可以直接暴露時鐘不確定性，Spanner時間戳的保證就是取決于這個API實現(xiàn)的界限。如果這個不確定性很大，Spanner就降低速度來等待這個大的不確定性結(jié)束。谷歌的簇管理器軟件提供了一個TrueTime API的實現(xiàn)。這種實現(xiàn)可以保持較小的不確定性（通常小于10ms），主要是借助于現(xiàn)代時鐘參考值（比如GPS和原子鐘）。第2部分描述了Spanner實現(xiàn)的結(jié)構(gòu)、特性集和工程方面的決策；第3部分介紹我們的新的TrueTime API，并且描述了它的實現(xiàn)；第4部分描述了Spanner如何使用TrueTime來實現(xiàn)外部一致性的分布式事務(wù)、不用鎖機制的只讀事務(wù)和原子模式更新。第5部分提供了測試Spanner性能和TrueTime行為的測試基準(zhǔn)，并討論了一級方程式錦標(biāo)賽的經(jīng)驗。第6、7和8部分討論了相關(guān)工作，并給出總結(jié)。
實現(xiàn)
本部分內(nèi)容描述了Spanner的結(jié)構(gòu)和背后的實現(xiàn)機理，然后描述了目錄抽象，它被用來管理副本和局部性，并介紹了數(shù)據(jù)的轉(zhuǎn)移單位。最后，將討論我們的數(shù)據(jù)模型，從而說明，為什么Spanner看起來更加像一個關(guān)系數(shù)據(jù)庫，而不是一個鍵值數(shù)據(jù)庫；還會討論應(yīng)用如何可以控制數(shù)據(jù)的局部性。一個Spanner部署稱為一個universe。假設(shè)Spanner在全球范圍內(nèi)管理數(shù)據(jù)，那么，將會只有可數(shù)的、運行中的universe。我們當(dāng)前正在運行一個測試用的universe，一個部署/線上用的universe和一個只用于線上應(yīng)用的universe。 Spanner被組織成許多個zone的集合，每個zone都大概像一個BigTable服務(wù)器的部署。zone是管理部署的基本單元。zone的集合也是數(shù)據(jù)可以被復(fù)制到的位置的集合。當(dāng)新的數(shù)據(jù)中心加入服務(wù)，或者老的數(shù)據(jù)中心被關(guān)閉時，zone可以被加入到一個運行的系統(tǒng)中，或者從中移除。zone也是物理隔離的單元，在一個數(shù)據(jù)中心中，可能有一個或者多個zone，例如，屬于不同應(yīng)用的數(shù)據(jù)可能必須被分區(qū)存儲到同一個數(shù)據(jù)中心的不同服務(wù)器集合中。
圖1顯示了在一個Spanner的universe中的服務(wù)器。一個zone包括一個zonemaster，和一百至幾千個spanserver。Zonemaster把數(shù)據(jù)分配給spanserver，spanserver把數(shù)據(jù)提供給客戶端?？蛻舳耸褂妹總€zone上面的location proxy來定位可以為自己提供數(shù)據(jù)的spanserver。Universe master和placement driver，當(dāng)前都只有一個。Universe master主要是一個控制臺，它顯示了關(guān)于zone的各種狀態(tài)信息，可以用于相互之間的調(diào)試。Placement driver會周期性地與spanserver進(jìn)行交互，來發(fā)現(xiàn)那些需要被轉(zhuǎn)移的數(shù)據(jù)，或者是為了滿足新的副本約束條件，或者是為了進(jìn)行負(fù)載均衡。
2.1 Spanserver軟件棧
本部分內(nèi)容主要關(guān)注spanserver實現(xiàn)，來解釋復(fù)制和分布式事務(wù)是如何被架構(gòu)到我們的基于BigTable的實現(xiàn)之上的。圖2顯示了軟件棧。在底部，每個spanserver負(fù)載管理100-1000個稱為tablet的數(shù)據(jù)結(jié)構(gòu)的實例。一個tablet就類似于BigTable中的tablet，也實現(xiàn)了下面的映射：
與BigTable不同的是，Spanner會把時間戳分配給數(shù)據(jù)，這種非常重要的方式，使得Spanner更像一個多版本數(shù)據(jù)庫，而不是一個鍵值存儲。一個tablet的狀態(tài)是存儲在類似于B-樹的文件集合和寫前(write-ahead)的日志中，所有這些都會被保存到一個分布式的文件系統(tǒng)中，這個分布式文件系統(tǒng)被稱為Colossus，它繼承自谷歌 File System。為了支持復(fù)制，每個spanserver會在每個tablet上面實現(xiàn)一個單個的Paxos狀態(tài)的機器。一個之前實現(xiàn)的Spanner可以支持在每個tablet上面實現(xiàn)多個Paxos狀態(tài)機，它可以允許更加靈活的復(fù)制配置，但是，這種設(shè)計過于復(fù)雜，被我們舍棄了。每個狀態(tài)機器都會在相應(yīng)的tablet中保存自己的元數(shù)據(jù)和日志。我們的Paxos實現(xiàn)支持采用基于時間的領(lǐng)導(dǎo)者租約的長壽命的領(lǐng)導(dǎo)者，時間通常在0到10秒之間。當(dāng)前的Spanner實現(xiàn)中，會對每個Paxos寫操作進(jìn)行兩次記錄：一次是寫入到tablet日志中，一次是寫入到Paxos日志中。這種做法只是權(quán)宜之計，我們以后會進(jìn)行完善。我們在Paxos實現(xiàn)上采用了管道化的方式，從而可以在存在廣域網(wǎng)延遲時改進(jìn)Spanner的吞吐量，但是，Paxos會把寫操作按照順序的方式執(zhí)行?！axos狀態(tài)機是用來實現(xiàn)一系列被一致性復(fù)制的映射。每個副本的鍵值映射狀態(tài)，都會被保存到相應(yīng)的tablet中。寫操作必須在領(lǐng)導(dǎo)者上初始化Paxos協(xié)議，讀操作可以直接從底層的任何副本的tablet中訪問狀態(tài)信息，只要這個副本足夠新。副本的集合被稱為一個Paxos group。對于每個是領(lǐng)導(dǎo)者的副本而言，每個spanserver會實現(xiàn)一個鎖表來實現(xiàn)并發(fā)控制。這個鎖表包含了兩階段鎖機制的狀態(tài)：它把鍵的值域映射到鎖狀態(tài)上面。注意，采用一個長壽命的Paxos領(lǐng)導(dǎo)者，對于有效管理鎖表而言是非常關(guān)鍵的。在BigTable和Spanner中，我們都專門為長事務(wù)做了設(shè)計，比如，對于報表操作，可能要持續(xù)幾分鐘，當(dāng)存在沖突時，采用樂觀并發(fā)控制機制會表現(xiàn)出很差的性能。對于那些需要同步的操作，比如事務(wù)型的讀操作，需要獲得鎖表中的鎖，而其他類型的操作則可以不理會鎖表。對于每個扮演領(lǐng)導(dǎo)者角色的副本，每個spanserver也會實施一個事務(wù)管理器來支持分布式事務(wù)。這個事務(wù)管理器被用來實現(xiàn)一個participant leader，該組內(nèi)的其他副本則是作為participant slaves。如果一個事務(wù)只包含一個Paxos組（對于許多事務(wù)而言都是如此），它就可以繞過事務(wù)管理器，因為鎖表和Paxos二者一起可以保證事務(wù)性。如果一個事務(wù)包含了多于一個Paxos組，那些組的領(lǐng)導(dǎo)者之間會彼此協(xié)調(diào)合作完成兩階段提交。其中一個參與者組，會被選為協(xié)調(diào)者，該組的participant leader被稱為coordinator leader，該組的participant slaves被稱為coordinator slaves。每個事務(wù)管理器的狀態(tài)，會被保存到底層的Paxos組。
2.2 目錄和放置
在一系列鍵值映射的上層，Spanner實現(xiàn)支持一個被稱為“目錄”的桶抽象，也就是包含公共前綴的連續(xù)鍵的集合。（選擇“目錄”作為名稱，主要是由于歷史沿襲的考慮，實際上更好的名稱應(yīng)該是“桶”）。我們會在第2.3節(jié)解釋前綴的源頭。對目錄的支持，可以讓應(yīng)用通過選擇合適的鍵來控制數(shù)據(jù)的局部性。一個目錄是數(shù)據(jù)放置的基本單元。屬于一個目錄的所有數(shù)據(jù)，都具有相同的副本配置。當(dāng)數(shù)據(jù)在不同的Paxos組之間進(jìn)行移動時，會一個目錄一個目錄地轉(zhuǎn)移，如圖3所示。Spanner可能會移動一個目錄從而減輕一個Paxos組的負(fù)擔(dān)，也可能會把那些被頻繁地一起訪問的目錄都放置到同一個組中，或者會把一個目錄轉(zhuǎn)移到距離訪問者更近的地方。當(dāng)客戶端操作正在進(jìn)行時，也可以進(jìn)行目錄的轉(zhuǎn)移。我們可以預(yù)期在幾秒內(nèi)轉(zhuǎn)移50MB的目錄。
一個Paxos組可以包含多個目錄，這意味著一個Spanner tablet是不同于一個BigTable tablet的。一個Spanner tablet沒有必要是一個行空間內(nèi)按照詞典順序連續(xù)的分區(qū)，相反，它可以是行空間內(nèi)的多個分區(qū)。我們做出這個決定，是因為這樣做可以讓多個被頻繁一起訪問的目錄被整合到一起。 Movedir是一個后臺任務(wù)，用來在不同的Paxos組之間轉(zhuǎn)移目錄。Movedir也用來為Paxos組增加和刪除副本，因為Spanner目前還不支持在一個Paxos內(nèi)部進(jìn)行配置的變更。Movedir并不是作為一個事務(wù)來實現(xiàn)，這樣可以避免在一個塊數(shù)據(jù)轉(zhuǎn)移過程中阻塞正在進(jìn)行的讀操作和寫操作。相反，Movedir會注冊一個事實(fact)，表明它要轉(zhuǎn)移數(shù)據(jù)，然后在后臺運行轉(zhuǎn)移數(shù)據(jù)。當(dāng)它幾乎快要轉(zhuǎn)移完指定數(shù)量的數(shù)據(jù)時，就會啟動一個事務(wù)來自動轉(zhuǎn)移那部分?jǐn)?shù)據(jù)，并且為兩個Paxos組更新元數(shù)據(jù)。一個目錄也是一個應(yīng)用可以指定的地理復(fù)制屬性（即放置策略）的最小單元。我們的放置規(guī)范語言的設(shè)計，把管理復(fù)制的配置這個任務(wù)單獨分離出來。管理員需要控制兩個維度：副本的數(shù)量和類型，以及這些副本的地理放置屬性。他們在這兩個維度里面創(chuàng)建了一個命名選項的菜單。通過為每個數(shù)據(jù)庫或單獨的目錄增加這些命名選項的組合，一個應(yīng)用就可以控制數(shù)據(jù)的復(fù)制。例如，一個應(yīng)用可能會在自己的目錄里存儲每個終端用戶的數(shù)據(jù)，這就有可能使得用戶A的數(shù)據(jù)在歐洲有三個副本，用戶B的數(shù)據(jù)在北美有5個副本。為了表達(dá)的清晰性，我們已經(jīng)做了盡量簡化。事實上，當(dāng)一個目錄變得太大時，Spanner會把它分片存儲。每個分片可能會被保存到不同的Paxos組上（因此就意味著來自不同的服務(wù)器）。Movedir在不同組之間轉(zhuǎn)移的是分片，而不是轉(zhuǎn)移整個目錄。
2.3 數(shù)據(jù)模型
Spanner會把下面的數(shù)據(jù)特性集合暴露給應(yīng)用：基于模式化的半關(guān)系表的數(shù)據(jù)模型，查詢語言和通用事務(wù)。支持這些特性的動機，是受到許多因素驅(qū)動的。需要支持模式化的半關(guān)系表是由Megastore的普及來支持的。在谷歌內(nèi)部至少有300個應(yīng)用使用Megastore（盡管它具有相對低的性能），因為它的數(shù)據(jù)模型要比BigTable簡單，更易于管理，并且支持在跨數(shù)據(jù)中心層面進(jìn)行同步復(fù)制。BigTable只可以支持跨數(shù)據(jù)中心的最終事務(wù)一致性。使用Megastore的著名的谷歌應(yīng)用是gmail,Picasa,Calendar,Android Market, AppEngine。在Spanner中需要支持SQL類型的查詢語言，也很顯然是非常必要的，因為Dremel作為交互式分析工具已經(jīng)非常普及。最后，在BigTable中跨行事務(wù)的缺乏來導(dǎo)致了用戶頻繁的抱怨；Percolator的開發(fā)就是用來部分解決這個問題的。一些作者都在抱怨，通用的兩階段提交的代價過于昂貴，因為它會帶來可用性問題和性能問題。我們認(rèn)為，最好讓應(yīng)用程序開發(fā)人員來處理由于過度使用事務(wù)引起的性能問題，而不是總是圍繞著“缺少事務(wù)”進(jìn)行編程。在Paxos上運行兩階段提交弱化了可用性問題。應(yīng)用的數(shù)據(jù)模型是架構(gòu)在被目錄桶裝的鍵值映射層之上。一個應(yīng)用會在一個universe中創(chuàng)建一個或者多個數(shù)據(jù)庫。每個數(shù)據(jù)庫可以包含無限數(shù)量的模式化的表。每個表都和關(guān)系數(shù)據(jù)庫表類似，具備行、列和版本值。我們不會詳細(xì)介紹Spanner的查詢語言，它看起來很像SQL，只是做了一些擴展?！panner的數(shù)據(jù)模型不是純粹關(guān)系型的，它的行必須有名稱。更準(zhǔn)確地說，每個表都需要有包含一個或多個主鍵列的排序集合。這種需求，讓Spanner看起來仍然有點像鍵值存儲：主鍵形成了一個行的名稱，每個表都定義了從主鍵列到非主鍵列的映射。當(dāng)一個行存在時，必須要求已經(jīng)給行的一些鍵定義了一些值（即使是NULL）。采用這種結(jié)構(gòu)是很有用的，因為這可以讓應(yīng)用通過選擇鍵來控制數(shù)據(jù)的局部性。
圖4包含了一個Spanner模式的實例，它是以每個用戶和每個相冊為基礎(chǔ)存儲圖片元數(shù)據(jù)。這個模式語言和Megastore的類似，同時增加了額外的要求，即每個Spanner數(shù)據(jù)庫必須被客戶端分割成一個或多個表的層次結(jié)構(gòu)（hierarchy）。客戶端應(yīng)用會使用INTERLEAVE IN語句在數(shù)據(jù)庫模式中聲明這個層次結(jié)構(gòu)。這個層次結(jié)構(gòu)上面的表，是一個目錄表。目錄表中的每行都具有鍵K，和子孫表中的所有以K開始（以字典順序排序）的行一起，構(gòu)成了一個目錄。ON DELETE CASCADE意味著，如果刪除目錄中的一個行，也會級聯(lián)刪除所有相關(guān)的子孫行。這個圖也解釋了這個實例數(shù)據(jù)庫的交織層次（interleaved layout），例如Albums(2,1)代表了來自Albums表的、對應(yīng)于user_id=2和album_id=1的行。這種表的交織層次形成目錄，是非常重要的，因為它允許客戶端來描述存在于多個表之間的位置關(guān)系，這對于一個分片的分布式數(shù)據(jù)庫系統(tǒng)的性能而言是很重要的。沒有它的話，Spanner就無法知道最重要的位置關(guān)系。
并發(fā)控制
本部分內(nèi)容描述TrueTime如何可以用來保證并發(fā)控制的正確性，以及這些屬性如何用來實現(xiàn)一些關(guān)鍵特性，比如外部一致性的事務(wù)、無鎖機制的只讀事務(wù)、針對歷史數(shù)據(jù)的非阻塞讀。這些特性可以保證，在時間戳為t的時刻的數(shù)據(jù)庫讀操作，一定只能看到在t時刻之前已經(jīng)提交的事務(wù)。進(jìn)一步說，把Spanner客戶端的寫操作和Paxos看到的寫操作這二者進(jìn)行區(qū)分，是非常重要的，我們把Paxos看到的寫操作稱為Paxos寫操作。例如，兩階段提交會為準(zhǔn)備提交階段生成一個Paxos寫操作，這時不會有相應(yīng)的客戶端寫操作。
總結(jié)
總的來說，Spanner對來自兩個研究群體的概念進(jìn)行了結(jié)合和擴充：一個是數(shù)據(jù)庫研究群體，包括熟悉易用的半關(guān)系接口，事務(wù)和基于SQL的查詢語言；另一個是系統(tǒng)研究群體，包括可擴展性，自動分區(qū)，容錯，一致性復(fù)制，外部一致性和大范圍分布。自從Spanner概念成形，我們花費了5年以上的時間來完成當(dāng)前版本的設(shè)計和實現(xiàn)?；ㄙM這么長的時間，一部分原因在于我們慢慢意識到，Spanner不應(yīng)該僅僅解決全球復(fù)制的命名空間問題，而且也應(yīng)該關(guān)注BigTable中所丟失的數(shù)據(jù)庫特性。
參考資料 >