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

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

嚴格的CP系統(tǒng)以及遠超5個9的可用性

基于2PC協(xié)議的內(nèi)部順序一致性

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

全球化的分布式存儲系統(tǒng)，延遲是能夠接受的

基于模式化的半關(guān)系表的數(shù)據(jù)模型

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

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

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

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

一個 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， 例如，當(dāng)屬于不同應(yīng)用的數(shù)據(jù)必須被分區(qū)存儲到同一個數(shù)據(jù)中心的不同服務(wù)器集合中時，一個數(shù)據(jù)中心就會有多個 zone 。

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

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

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

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

Multi-Paxos協(xié)議本身在只有一個proposer的時候，對于每個instance可以將兩階段變?yōu)橐浑A段，提高Paxos協(xié)議的效率。當(dāng)然這只是微小的一方面，畢竟谷歌使用的Paxos實現(xiàn)應(yīng)該是標準的變體。

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

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

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

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

這里需要再問一個問題：

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

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

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

Commit Wait. 擔(dān)任協(xié)調(diào)者的領(lǐng)導(dǎo)者，必須確?？蛻舳瞬荒芸吹饺魏伪?Ti 提交的數(shù)據(jù)，直到 TT.after(si)為真。提交等待，就是要確保 si 會比 Ti 的絕對提交時間小。

那么證明如下：

讀事務(wù)可以分為只讀事務(wù)讀當(dāng)前最新的值，以及快照讀。前者可以通過分配時間戳轉(zhuǎn)變?yōu)楹笳?，所以我們先討論快照讀的實現(xiàn)。

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

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

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

這一小節(jié)內(nèi)容請先參閱讀寫事務(wù)部分。

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

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

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

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

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

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

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

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

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

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

無論事務(wù)讀不讀，都按讀寫事務(wù)來處理

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

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

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

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

讀操作結(jié)束，緩沖所有寫操作，開始2PC,選擇協(xié)調(diào)組發(fā)送緩沖信息

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

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

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

在提交等待之后，協(xié)調(diào)者就會發(fā)送一個提交時間戳給客戶端和所有其他參與的領(lǐng)導(dǎo)者。每個參與的領(lǐng)導(dǎo)者會通過 Paxos 把事務(wù)結(jié)果寫入日志。所有的參與者會在同一個時間戳進行提交，然后釋放鎖。

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

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

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

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

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

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

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

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

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

首先，由于分區(qū)很少發(fā)生，那么在系統(tǒng)不存在分區(qū)的情況下沒什么理由犧牲C或A。

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

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

CAP理論的經(jīng)典解釋，是忽略網(wǎng)絡(luò)延遲的，但在實際中延遲和分區(qū)緊密相關(guān)。CAP從理論變?yōu)楝F(xiàn)實的場景發(fā)生在操作的間歇，系統(tǒng)需要在這段時間內(nèi)做出關(guān)于分區(qū)的一個重要決定：

取消操作因而降低系統(tǒng)的可用性，還是

繼續(xù)操作，以冒險損失系統(tǒng)一致性為代價

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

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

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

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

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

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

綜上，Spanner在技術(shù)上是個CP系統(tǒng)，但實際效果上可以說其是CA的。

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

如何判斷分區(qū)

分區(qū)問題的主要來源

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

首先，考慮單Paxos組內(nèi)事務(wù)，出現(xiàn)分區(qū)后會出現(xiàn)兩種情形：

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

無法維持一個多數(shù)人群體，那么事務(wù)將暫停，新的事務(wù)不會被接受，系統(tǒng)不可用

再考慮跨Paxos組的事務(wù)

對跨組事務(wù)使用2PC還意味著組內(nèi)成員的網(wǎng)絡(luò)分區(qū)可以阻止提交。舍棄可用性保證系統(tǒng)數(shù)據(jù)是安全的。

對于快照讀，快照讀對網(wǎng)絡(luò)分區(qū)而言更加健壯。特別的，快照讀能在以下情況下正常工作：

對于發(fā)起讀操作的一側(cè)網(wǎng)絡(luò)分區(qū)，每個組至少存在一個副本

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

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

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

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

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

F1支持層級表結(jié)構(gòu)和protobuf復(fù)合數(shù)據(jù)域，示例如下：

這樣做的好處主要是：

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

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

protobuf支持重復(fù)字段，這樣也是為了對于array一類的結(jié)構(gòu)在取數(shù)據(jù)時提升性能

最后，對于索引：

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

索引分兩種類型:

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

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

同步的模式變更可行嗎？

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

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

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

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

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

定義的中間狀態(tài)：

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

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

reorg:取到當(dāng)前時刻的snapshot，為每條數(shù)據(jù)補寫對應(yīng)的索引

演化過程：

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

F1支持三種事務(wù)

快照事務(wù)

悲觀事務(wù)

樂觀事務(wù)

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

其優(yōu)勢主要如下：

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

樂觀事務(wù)的狀態(tài)值都在client端,即使F1 Server處理事務(wù)失敗了,client也能很好轉(zhuǎn)移到另一臺F1 Server繼續(xù)運行.

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

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

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

F1的運算都在內(nèi)存中執(zhí)行,再加上管道的運用,沒有中間數(shù)據(jù)會存放在磁盤上,但缺點也是所有內(nèi)存數(shù)據(jù)庫都有的--一個節(jié)點掛就會導(dǎo)致整個SQL失敗要重新再來.F1的實際運行經(jīng)驗表明執(zhí)行時間不遠超過1小時的SQL一般足夠穩(wěn)定。

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

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

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

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

全球分布式數(shù)據(jù)庫：Google Spanner（論文翻譯）

Spanner: CAP, TrueTime and Transaction

【譯文】Spanner, TrueTime 和CAP理論

CAP理論十二年回顧："規(guī)則"變了

理解Google F1: Schema變更算法

TiDB 的異步 schema 變更實現(xiàn)

Google NewSQL之F1