摘要：和的關聯一個組可以包含多個目錄，這意味著一個是不同于一個的。的軟件架構和的概念一個部署稱為一個。是管理部署的基本單元。表示一個事件的絕對時間，可以利用函數。提交等待，就是要確保會比的絕對提交時間小。為了減少阻塞的概率，應該分配可以保持外部一

本文不是一篇Spanner的介紹文章，主要想對于Spanner和F1解決的幾個有代表性的問題做一個概括和梳理。接下來的行文安排將主要以問答的形式展開。對Spanner和F1不熟悉的盆友可以參考最后一節列出的引用。

嚴格的CP系統以及遠超5個9的可用性

基于2PC協議的內部順序一致性

外部一致性，支持讀寫事務、只讀事務、快照讀

全球化的分布式存儲系統，延遲是能夠接受的

基于模式化的半關系表的數據模型

在一系列鍵值映射的上層，Spanner 實現支持一個被稱為“目錄”的桶抽象，也就是包含公共前綴的連續鍵的集合。一個目錄是數據放置的基本單元。屬于一個目錄的所有數據，都具有相同的副本配置。 當數據在不同的 Paxos 組之間進行移動時，會一個目錄一個目錄地轉移。

一個 Paxos 組可以包含多個目錄，這意味著一個 Spanner tablet 是不同于一個 BigTable tablet 的。一個 Spanner tablet 沒有必要是一個行空間內按照詞典順序連續的分區，相反，它可以是行空間內的多個分區。這樣做可以讓多個被頻繁一起訪問的目錄被整合到一起，也就是說多個directory會被映射到一個tablet上。

每個表都和關系數據庫表類似，具備行、列和版本值。每個表都需 要有包含一個或多個主鍵列的排序集合。主鍵形成了一個行的名稱，每個表都定義了從主鍵列到非主鍵列的映射。當一個行存在時，必須要求已經給行的一些鍵定義了一些值(即使是 NULL)。

Spanner中的表具有層次結構，這有些類似于傳統關系數據庫中一對多關系。戶端應用會使用 INTERLEAVE IN 語句在數據庫模式中聲明這個層次結構。這個層次結構上面的表，是一個目錄表。目錄表中的每行都具有鍵 K，和子孫表中的所有以 K 開始(以字典順序排序)的行一起，構成了一個目錄。這樣做是想把想關聯的表放在同樣的位置，利用數據的局部性提高性能，畢竟單個Paxos組內的操作比跨paxos組要來的高效。

一個 Spanner 部署稱為一個 universe。假設 Spanner 在全球范圍內管理數據，那么，將會只有可數的、運行中的 universe。我們當前正在運行一個測試用的 universe，一個部署/線上用的 universe 和一個只用于線上應用的 universe。

Spanner 被組織成許多個 zone 的集合，每個 zone 都大概像一個 BigTable 服務器的部署。 zone 是管理部署的基本單元。zone 的集合也是數據可以被復制到的位置的集合。當新的數據中心加入服務，或者老的數據中心被關閉時，zone 可以被加入到一個運行的系統中，或者從中移除。zone 也是物理隔離的單元，在一個數據中心中，可能有一個或者多個 zone， 例如，當屬于不同應用的數據必須被分區存儲到同一個數據中心的不同服務器集合中時，一個數據中心就會有多個 zone 。

spanner數據的實際存儲依靠于分布式文件系統Colossus，在一個存儲分區分區單元tablet上運行一個Paxos狀態機，基于Paxos實現備份和容錯。我們的 Paxos 實現支持長壽命的領導者（采用基于時間的領導者租約），時間通常在 0 到 10 秒之間。當前的 Spanner 實現中，會對每個 Paxos 寫操作進行兩次記錄:一次是寫入到 tablet 日志中，一次是寫入到 Paxos 日志中。

Spanner 的 Paxos 實現中使用了時間化的租約，來實現長時間的領導者地位(默認是 10秒)。一個潛在的領導者會發起請求，請求時間化的租約投票，在收到指定數量的投票后，這個領導者就可以確定自己擁有了一個租約。一個副本在成功完成一個寫操作后，會隱式地延期自己的租約。對于一個領導者而言，如果它的租約快要到期了，就要顯示地請求租約延期。另一個領導者的租約有個時間區間，這個時間區間的起點就是這個領導者獲得指定數量的投票那一刻，時間區間的終點就是這個領導者失去指定數量的投票的那一刻(因為有些投 票已經過期了)。Spanner 依賴于下面這些“不連貫性”:對于每個 Paxos組，每個Paxos領導者的租約時間區間，是和其他領導者的時間區間完全隔離的。

為了保持這種彼此隔離的不連貫性，Spanner 會對什么時候退位做出限制。把 smax 定義為一個領導者可以使用的最大的時間戳。在退位之前，一個領導者必須等到 TT.after(smax)是真。

上面是論文中關于領導著租約的解釋，這里我們的問題是為什么需要一個長期的leader lease，不加入這個特性是否可以？下面是我個人的一些看法：

Multi-Paxos協議本身在只有一個proposer的時候，對于每個instance可以將兩階段變為一階段，提高Paxos協議的效率。當然這只是微小的一方面，畢竟谷歌使用的Paxos實現應該是標準的變體。

Leader變動頻率下降有助于減少在操作中查詢leader的次數，有助于減輕元信息管理服務的壓力

這種做法的前提必定是故障的頻率低，如果故障時常發生，一個較長的租約時間將使得故障的發現和處理變慢

如果一個事務 T2 在事務 T1 提交以后開始執行， 那么，事務 T2 的時間戳一定比事務 T1 的時間戳大。

TrueTime 會顯式地把時間表達成 TTinterval，這是一個時間區間，具有有界限的時間不確定性。表示一個事件 e 的絕對時間，可以利用函數 tabs(e)。如果用更加形式化的術語，TrueTime 可以保證，對于一個調用 tt=TT.now()，有 tt.earliest≤tabs(enow)≤tt.latest，其中， enow 是調用的事件。

這里需要再問一個問題：

每個節點在同一時刻調用TT.now()等到的區間是相同的嗎？顯然不是，如果那樣不就等同于得到一個全球相同的時間點了，但這不影響外部一致性正確的證明。

我們先來講做法：是基于時間戳分配和commit wait實現的。

Start. 為一個事務 Ti 擔任協調者的領導者分配一個提交時間戳 si，不會小于 TT.now().latest 的值，TT.now().latest的值是在esierver事件之后計算得到的。要注意，擔任參與者的領導者， 在這里不起作用。第 4.2.1 節描述了這些擔任參與者的領導者是如何參與下一條規則的實現的。

Commit Wait. 擔任協調者的領導者，必須確保客戶端不能看到任何被 Ti 提交的數據，直到 TT.after(si)為真。提交等待，就是要確保 si 會比 Ti 的絕對提交時間小。

那么證明如下：

讀事務可以分為只讀事務讀當前最新的值，以及快照讀。前者可以通過分配時間戳轉變為后者，所以我們先討論快照讀的實現。

首先問一個問題，讀必須走Paxos Group 的Leader嗎？不是的，首先在同一個Paxos Group內，寫操作時間戳的單調性是毫無疑問的,那么只需要找到足夠新的副本。這就有一個新問題：

如何判斷一個副本是否足夠新？

每個副本都會跟蹤記錄一個值，這個值被稱為安全時間 tsafe，它是一個副本最近更新后的最大時間戳。如果一個讀操作的時間戳是 t，當滿足 t<=tsafe 時， 這個副本就可以被這個讀操作讀取。這種情形下小于t的寫操作必定已經被該副本catch up了（基于Paxos協議）。

這一小節內容請先參閱讀寫事務部分。

tsafe可以從兩個值推導而來，Paxos狀態機最大的apply操作的時間戳（這一部分象征著已經生效的寫），和事務管理器決定的tasfe(TM)，tsafe=min(tsafe(Paxos),tsafe(TM))，后者是什么意思呢？

如果現在該replica沒有參與任何事務中，那么理應這一部分不造成任何影響，所以tsafe(TM)=無窮大。（記住tsafe越大，讀越容易通過）。如果當前replica參與了一個讀寫事務Ti，那么本Paxos組的leader會分配一個準備時間戳（見后文讀寫事務），那么理應tsafe比所有正在參與的事務Ti的準備時間戳都小，并且是滿足這個條件時間戳里的最大一個。答案呼之欲出了。

但是，上述的方法依然存在問題，一個未完成的事務將阻止tsafe增長，之后的以有讀事務將被阻塞，即使它讀的值和該事務寫的值沒啥關系。這里有點類似于Java對ConcurrentHashMap做的優化了——分段加鎖，好了，我們繼續接著往下看。我們可以對一個范圍的key range來維護參與事務的準備時間戳，那么對于一個讀操作，只用檢查和它沖突的key range的準備時間戳就好。

tsafe(Paxos)也有一個問題，那就是缺乏Paxos寫的時候，也沒法增長。如果上次的apply時間在讀被分配的時間戳t之前，接下來沒有Paxos寫的話，快照讀t沒法執行，這就尷尬了。可以為每一個instance n預估一個將分配給n+1的時間戳。那這里要有一個問題了，預估的這個時間需要滿足什么條件呢？個人認為首先是要超過時間戳的最大誤差值。

之前提到過對于只讀事務可以通過分配時間戳來轉化為快照讀，那么該如何分配呢，首先看這種分配需要滿足什么？

滿足寫后讀一致性，也就是其分配的時間戳要大于所有已提交事務的時間戳

在一個事務開始后的任意時刻，可以簡單地分配 sread=TT.now().latest。但這樣有一個問題，對于時間戳 sread 而言，如果 tsafe 沒有增加到足夠大，可能需要對 sread 時刻的讀操作進行阻塞。擇一個 sread 的值可 能也會增加 smax 的值，從而保證不連貫性。為了減少阻塞的概率，_Spanner 應該分配可以保持外部一致性的最老（小）的時間戳_。

分配一個時間戳需要一個協商階段，這個協商發生在所有參與到該讀操作中的 Paxos 組之間。其過程如下：

對于單個Paxos組內的讀操作，把 LastTS()定義為在 Paxos 組中最后提交的寫操作的時間戳。如果沒有準備提交的事務，這個分配到的時間戳 sread=LastTS()就很容易滿足外部一致性要求

對于跨Paxos組的讀操作，最復雜的做法是基于多Paxos Leader的LastTS()協商得出；但實際采用的簡單做法是采用TT.now().latest，允許某種程度上的阻塞。

無論事務讀不讀，都按讀寫事務來處理

這種情況下只需要給讀寫事務分配時間戳，進行快照讀，最后發生在一個事務中的寫操作會在客戶端進行緩存，直到提交。由此導致的結果是，在一個事務中的讀操作，不會看到這個事務的寫操作的結果。這種設計在 Spanner 中可以很好地工作，因為一個讀操作可以返回任何數據讀的時間戳，未提交的寫操作還沒有被分配時間戳。

至于讀寫事務如何分配時間戳，請參照True Time一章。

客戶端對需要讀的Paxos組Leader申請加讀鎖，按分配時間戳讀取最新數據。

客戶端向leader持續發送“保持活躍信息“，防止leader認為會話過時

讀操作結束，緩沖所有寫操作，開始2PC,選擇協調組發送緩沖信息

對于參與協調的非領導者而言，獲取寫鎖，會選擇一個比之前分配給其他事務的任何時間戳都要大的預備時間戳，并且通過 Paxos 把準備提交記錄寫入日志。然后把自己的準備時間戳通知給協調者。

對于協調者，也會首先獲得寫鎖，但是，會跳過準備階段。在從所有其他的、扮演參與者的領導者那里獲得信息后，它就會為整個事務選擇一個時間戳。這個提交時間戳s必須大于或等于所有的準備時間戳,并且s應該大于這個領導者為之前的其他所有事務分配的時間戳，之后就會通過 Paxos 在日志中寫入一個提交記錄。

在允許任何協調者副本去提交記錄之前，扮演協調者的領導者會一直等待到 TT.after(s)，滿足提交等待條件。

在提交等待之后，協調者就會發送一個提交時間戳給客戶端和所有其他參與的領導者。每個參與的領導者會通過 Paxos 把事務結果寫入日志。所有的參與者會在同一個時間戳進行提交，然后釋放鎖。

注意，這里的每個協調者其實都是一個Paxos組，2PC本身是一個反可用性的協議（也就是它要求沒有故障才能順利完成），但是Paxos協議能夠在協調者故障時快速選出新主，由于信息已經通過Paxos日志同步了，新主可以繼續參與2PC過程，提升了可用性。

原子模式變更。使用一個標準的事務是不可行的，因為參與者的數量(即數據庫中組的數量)可能達到幾百萬個。在一個數據中心內進行原子模式變更，這個操作會阻塞所有其他操作。

一個 Spanner 模式變更事務通常是一個標準事務的、非阻塞的變種。首先，它會顯式地分配一個未來的時間戳，這個時間戳會在準備階段進行注冊。由此，跨越幾千個服務器的模式變更，可以在不打擾其他并發活動的前提下完成。其次，讀操作和寫操作，它們都是隱式地依賴于模式，它們都會和任何注冊的模式變更時間戳t保持同步:當它們的時間戳小于 t 時， 讀寫操作就執行到時刻 t;當它們的時間戳大于時刻 t 時，讀寫操作就必須阻塞，在模式變更事務后面進行等待。

那么，接下來又有幾個問題：

如何為模式變更選擇時間戳？選擇的時間戳需要滿足哪些條件？

上述的方法會造成服務不可用嗎？如果是，不可用的時間區間是多少？

兩次模式變更之間在重合的時間段里有重合組的時候，通過什么方式協調？樂觀還是悲觀的并發控制？會造成死鎖嗎，會導致在分配的時間戳之后無法按時完成嗎？還是說在準備階段就偵測這種情況，阻塞下一次模式變更？

關于模式變更的細節在spanner的論文中并沒有詳細提及，而是在另一篇文章中闡述，如果之后有時間的話會多帶帶就模式變更再寫一篇博客來回答這些問題。

“三選二”的觀點在幾個方面起了誤導作用，

首先，由于分區很少發生，那么在系統不存在分區的情況下沒什么理由犧牲C或A。

其次，C與A之間的取舍可以在同一系統內以非常細小的粒度反復發生，而每一次的決策可能因為具體的操作，乃至因為牽涉到特定的數據或用戶而有所不同。

最后，這三種性質都可以在程度上衡量，并不是非黑即白的有或無。可用性顯然是在0%到100%之間連續變化的，一致性分很多級別，連分區也可以細分為不同含義，如系統內的不同部分對于是否存在分區可以有不一樣的認知。

CAP理論的經典解釋，是忽略網絡延遲的，但在實際中延遲和分區緊密相關。CAP從理論變為現實的場景發生在操作的間歇，系統需要在這段時間內做出關于分區的一個重要決定：

取消操作因而降低系統的可用性，還是

繼續操作，以冒險損失系統一致性為代價

依靠多次嘗試通信的方法來達到一致性，比如Paxos算法或者兩階段事務提交，僅僅是推遲了決策的時間。系統終究要做一個決定；無限期地嘗試下去，本身就是選擇一致性犧牲可用性的表現。

CAP理論經常在不同方面被人誤解，對于可用性和一致性的作用范圍的誤解尤為嚴重，可能造成不希望看到的結果。如果用戶根本獲取不到服務，那么其實談不上C和A之間做取舍，除非把一部分服務放在客戶端上運行。

“三選二”的時候取CA而舍P是否合理？已經有研究者指出了其中的要害——怎樣才算“舍P”含義并不明確。設計師可以選擇不要分區嗎？哪怕原來選了CA，當分區出現的時候，你也只能回頭重新在C和A之間再選一次。我們最好從概率的角度去理解：選擇CA意味著我們假定，分區出現的可能性要比其他的系統性錯誤（如自然災難、并發故障）低很多，打個比方你在單機下就永遠不會假設分區，同一機架內部的通信有時我們也認為分區不會出現。

純粹主義的答案是“否”，因為網絡分區總是可能發生，事實上在Google也確實發生過。在網絡分區時，Spanner選擇C而放棄了A。因此從技術上來說，它是一個CP系統。我們下面探討網絡分區的影響。考慮到始終提供一致性（C），Spanner聲稱為CA的真正問題是，它的核心用戶是否認可它的可用性（A）。如果實際可用性足夠高，用戶可以忽略運行中斷，則Spanner是可以聲稱達到了“有效CA”的。

實際上，c差異化可用性與spanner的實際可用性是有差距的，即用戶是否確實已經發現Spanner已停掉了。差異化可用性比Spanner的實際可用性還要高，也就是說，Spanner的短暫不可用不一定會立即造成用戶的系統不可用。

另外就是運行中斷是否由于網絡分區造成的。如果Spanner運行中斷的主要原因不是網絡分區，那么聲稱CA就更充分了。對于Spanner，這意味著可用性中斷的發生，實際并非是由于網絡分區，而是一些其它的多種故障（因為單一故障不會造成可用性中斷）。

綜上，Spanner在技術上是個CP系統，但實際效果上可以說其是CA的。

上面已經提到過了，對于分布式系統的節點來說，它很難感知分區，它所能感知的只有延時。那么這里有幾個重要問題：

如何判斷分區

分區問題的主要來源

spanner在面對分區的時候做出了什么樣的選擇

首先，考慮單Paxos組內事務，出現分區后會出現兩種情形：

大多數成員可用，選出了新Leader，事務繼續運行。但處于少數人的一側將再也無法更新它的tsafe了，在某個時間戳之后的讀操作無法在該分區被服務，犧牲了部分可用性，但數據在多數人中保持一致。

無法維持一個多數人群體，那么事務將暫停，新的事務不會被接受，系統不可用

再考慮跨Paxos組的事務

對跨組事務使用2PC還意味著組內成員的網絡分區可以阻止提交。舍棄可用性保證系統數據是安全的。

對于快照讀，快照讀對網絡分區而言更加健壯。特別的，快照讀能在以下情況下正常工作：

對于發起讀操作的一側網絡分區，每個組至少存在一個副本

對于這些副本，讀時間戳是過去的。

如果Leader由于網絡分區而暫停（這可能一直持續到網絡分區結束），這時第2種情況可能就不成立了。因為這一側的網絡分區上可能無法選出新的Leader（譯注：見下節引用的解釋）。在網絡分區期間，時間戳在分區開始之前的讀操作很可能在分區的兩側都能成功，因為任何可達的副本有要讀取的數據就足夠了。

F1是基于Spanner之上的一個分布式類關系數據庫，提供了一套類似于SQL（準確說是SQL的超集）的查詢語句，支持表定義和數據庫事務，同時兼具強大的可擴展性、高可用性、外部事務一致性。接下來主要從幾個方面來簡要說一說F1是怎么在Spanner之上解決傳統數據庫的諸多問題的。

F1本身不負責數據的存儲，只是作為中間層預處理數據并解析SQL生成實際的讀寫任務。我們知道，大多數時候移動數據要比移動計算昂貴的多，F1節點自身不負責數據的底層讀寫，那么節點的加入和移除還有負載均衡就變得廉價了。下面放一張F1的結構圖：

大部分的F1是無狀態的,意味著一個客戶端可以發送不同請求到不同F1 server,只有一種狀況例外:客戶端的事務使用了悲觀鎖,這樣就不能分散請求了,只能在這臺F1 server處理剩余的事務。

F1支持層級表結構和protobuf復合數據域，示例如下：

這樣做的好處主要是：

可以并行化，是因為在子表中可以get到父表主鍵，對于很多查詢可以并行化操作，不用先查父表再查子表

數據局部性，減少跨Paxos組的事務.update一般都有where 字段=XX這樣的條件,在層級存儲方式下相同row值的都在一個directory里

protobuf支持重復字段，這樣也是為了對于array一類的結構在取數據時提升性能

最后，對于索引：

所有索引在F1里都是多帶帶用個表存起來的,而且都為復合索引,因為除了被索引字段,被索引表的主鍵也必須一并包含.除了對常見數據類型的字段索引,也支持對Buffer Protocol里的字段進行索引.

索引分兩種類型:

Local:包含root row主鍵的索引為local索引,因為索引和root row在同一個directory里;同時,這些索引文件也和被索引row放在同一個spanserver里,所以索引更新的效率會比較高.

global:同理可推global索引不包含root row,也不和被索引row在同一個spanserver里.這種索引一般被shard在多個spanserver上;當有事務需要更新一行數據時,因為索引的分布式,必須要2PC了.當需要更新很多行時,就是個災難了,每插入一行都需要更新可能分布在多臺機器上的索引,開銷很大;所以建議插入行數少量多次.

同步的模式變更可行嗎？

顯然是不行的，這違反了我們對可用性的追求。

然而在線的、異步的模式變更會造成哪些問題呢？

所有F1服務器的Schema變更是無法同步的，也就是說不同的F1服務器會在不同的時間點切換至新Schema。由于所有的F1服務器共享同一個kv存儲引擎，Schema的異步更新可能造成嚴重的數據錯亂。例如我們發起給一次添加索引的變更，更新后的節點會很負責地在添加一行數據的同時寫入一條索引，隨后另一個還沒來得及更新的節點收到了刪除同一行數據的請求，這個節點還完全不知道索引的存在，自然也不會去刪除索引了，于是錯誤的索引就被遺留在數據庫中。

在F1 Schema變更的過程中，由于數據庫本身的復雜性，有些變更無法由一個中間狀態隔離，我們需要設計多個逐步遞進的狀態來進行演化。只要我們保證任意相鄰兩個狀態是相互兼容的，整個演化的過程就是可依賴的。

F1中Schema以特殊的kv對存儲于Spanner中，同時每個F1服務器在運行過程中自身也維護一份拷貝。為了保證同一時刻最多只有2份Schema生效，F1約定了長度為數分鐘的Schema租約，所有F1服務器在租約到期后都要重新加載Schema。如果節點無法重新完成續租，它將會自動終止服務并等待被集群管理設施重啟。

定義的中間狀態：

delete-only 指的是Schema元素的存在性只對刪除操作可見。

write-only 指的是Schema元素對寫操作可見，對讀操作不可見。

reorg:取到當前時刻的snapshot，為每條數據補寫對應的索引

演化過程：

absent --> delete only --> write only --(reorg)--> public

F1支持三種事務

快照事務

悲觀事務

樂觀事務

前面兩類都是Spanner直接支持的，這里主要講講樂觀事務，分為兩階段:第一階段是讀,無鎖,可持續任意長時間;第二階段是寫,持續很短.但在寫階段可能會有row記錄值沖突（可能多個事務會寫同一行）,為此,每行都有個隱藏的lock列,包含最后修改的timestamp.任何事務只要commit,都會更新這個lock列,發出請求的客戶端收集這些timestamp并發送給F1 Server,一旦F1 Server發現更新的timestamp與自己事務沖突,就會中斷本身的事務。

其優勢主要如下：

在樂觀事務下能長時間運行而不被超時機制中斷，也不會影響其他客戶端

樂觀事務的狀態值都在client端,即使F1 Server處理事務失敗了,client也能很好轉移到另一臺F1 Server繼續運行.

一個悲觀事務一旦失敗重新開始也需要上層業務邏輯重新處理,而樂觀事務自包含的--即使失敗了重來一次對客戶端也是透明的.

但在高并發的情景下，沖突變得常見，樂觀事務的吞吐率將變得很低。

F1的查詢處理有點類似于Storm一類流式計算系統，先生成可以由有向無環圖表示的執行計劃，下面給出一個示例：

F1的運算都在內存中執行,再加上管道的運用,沒有中間數據會存放在磁盤上,但缺點也是所有內存數據庫都有的--一個節點掛就會導致整個SQL失敗要重新再來.F1的實際運行經驗表明執行時間不遠超過1小時的SQL一般足夠穩定。

F1本身不存儲數據,由Spanner遠程提供給它,所以網絡和磁盤就影響重大了;為了減少網絡延遲,F1使用批處理和管道技術,同時還有一些優化手段：

對于層級表之間的join，一次性取出所有滿足條件的行

支持客戶端多進程并發接受數據,每個進程都會收到自己的那部分結果,為避免多接受或少接受,會有一個endpoint標示.

對protobuf數據的處理，即使是只取部分字段，也必須取整個對象并解析，這也是為了換取減少子表開銷做出的權衡。

全球分布式數據庫：Google Spanner（論文翻譯）

Spanner: CAP, TrueTime and Transaction

【譯文】Spanner, TrueTime 和CAP理論

CAP理論十二年回顧："規則"變了

理解Google F1: Schema變更算法

TiDB 的異步 schema 變更實現

Google NewSQL之F1