Spanner, 真時和CAP理論
Spanner是Google支持高可用的全球關系型數據庫[CDE+12]。Spanner可以管理大規模的復制數據，這種大規模不僅體現數據量方面，還體現在事務數量方面。 Spanner為寫入其中的每條數據分配全局一致的“真時”時間戳，客戶端可以在整個數據庫上無需鎖定的執行全局一致性讀取。
CAP理論[Bre12]指出，在C，A，P三個期望的屬性中，你只能選擇兩個：
- C：一致性，本文中我們可以認為是可串行性;
- A：可用性，指讀取和更新的100%可用;
- P：網絡分區，指對網絡分片的容忍。
基于CAP理論，選擇要拋棄的字母，將會得到三種系統：CA，CP和AP。需要注意的是，你不是必須選擇3個屬性中的2個，許多系統具有零個或一個CAP屬性。
對于“全球規模”的分布式系統，分區通常被認為是不可避免的——盡管這并不是共識[BK14]。一旦你認為分區是不可避免的，任何分布式系統都必須準備放棄一致性(AP)或放棄可用性(CP)，這不是任何人都想要的選擇結果。實際上，CAP理論的出發點是讓設計者認真對待這種權衡。這里給出兩個重要的警告：首先，在真正發生分區的時候，你只需要喪失系統的部分功能而不是全部——當然你必須付出一些代價[Bre12]。其次，CAP理論申明的是100%可用性，而本文討論的有趣之處是真實生產環境中涉及可用性本身的折中和權衡。
Spanner是CA系統
作為一個全球規模分布式系統，Spanner聲稱同時具有一致性和高可用性，這意味著Spanner系統不會發生分區，這很讓人懷疑。這是否意味著Spanner就是CAP定義的CA系統?從技術上來說，直接的答案是“否”，但從效果上來說，答案可以是“是”——即從用戶的角度，可以認為Spanner是一個CA系統。
純粹主義者從技術上來看，答案當然是“否”。因為分區確實可能發生，并且實際上在谷歌也發生過。特別是在發生分區的時候，Spanner的策略是選擇C而放棄A。所以，技術上Spanner是一個CP系統。下面我們將具體展開對分區的探討。
考慮到Spanner永遠提供一致性，Spanner宣稱是CA系統存在的真正問題是用戶對可用性的態度——即用戶是否會對可用性吹毛求疵。如果Spanner的實際可用性很高，宕機事件對用戶來說可以忽略，則Spanner可以證明“實際上是CA系統”聲明的正當性。宣稱CA系統并不意味著100%的可用性(Spanner沒有提供也不會提供)，而是類似5個或更多“9”的可用性(1/106的故障或更少)。反過來，數據庫可用性的真正石蕊試紙是用戶(希望自己的服務高可用)——即用戶是否需要編寫額外的代碼來處理宕機異常。如果用戶沒有編寫額外代碼，也就是說用戶是假設數據庫高可用的。而基于Spanner內部已有的大量用戶，我們可以知道用戶認為Spanner是高可用數據庫。
關于可用性的數據
在我們深入研究Spanner之前，重新回顧Chubby的演進歷程是值得的。Chubby也是一個提供一致性和可用性的全球規模(廣域網絡)系統。原始的Chubby論文[Bur06]提到在700天內出現了30秒或更長時間的9次宕機，其中6次與網絡相關(如[BK14]中所討論的)。這樣的可用性低于最好的5個9可用性，現實一點說，如果我們假設每次宕機的平均值為10分鐘，這樣的可用性低于4個9，更有甚者，如果宕機時間是小時級的，則可用性將會低于3個9。
對于鎖定和一致的讀/寫操作，得益于網絡，架構和運維的各種改進，現在全球地理分布的Chubby單元提供99.99958%的平均可用性(30s+的宕機時間)。從2009年開始，由于“卓越”的可用性，Chubby的SRE工程師開始強制定期停機，以確保我們繼續了解Chubby對故障的依賴和影響。
在Google內部，Spanner提供與Chubby類似的可用性水平。也就是說，好于5個9。云版本的Spanner具有相同的基礎，但添加了一些新的功能，所以在實際生產環境中可能會稍微低一點。
上面的餅圖揭示了Spanner事故的內部原因分類。事故可能是一個意外事件，但并非所有事故都是宕機，一些事故可以很容易地掩蔽。圖表中的權重是事故出現的頻率而不是事故的影響。頻率最高的事故類別(User)是用戶錯誤導致的，例如負載過高或者配置錯誤，并且這些事故大多數只會影響到該特定用戶，而其余類別則可能會影響到區域中的所有用戶。Cluster類別的事故反映底層基礎架構中的非網絡問題，包括服務器和電源的問題。Spanner通過使用多副本機制來自動規避這些事件。然而，有時SRE也需要介入以修復損壞的副本。Operator類別的事故是由SRE引起的事故，例如配置錯誤。Bug類別的事故則是導致一些問題的軟件錯誤。這些事故都可能導致或大或小的宕機，曾經兩起最大的宕機事故都是軟件錯誤，并且同時影響到特定數據庫的所有副本。其他一麻袋的各種問題大多數只發生一次。
Network類別的事故(8%以下)是由網絡分區和網絡配置問題造成的。一部分集群節點和另外一部分集群節點分開的情況從來沒有發生過，也沒有發生過Spanner的法定數節點出現在分區中集群數量較少一邊的情況。但我們確實遇到過個別數據中心或區域與其他網絡斷開的情況。還有就是一些配置錯誤導致臨時預留帶寬不足和一些與硬件故障相關的延遲。我們曾經遇到一個問題：其中單方向的通信失敗導致一個奇怪的分區發生，然后必須通過關閉一些節點來解決。到目前為止，網絡事件沒有引起大的宕機事故。
總而言之，要聲明“實際上是CA”系統，那么，這個系統必須處于這種相對概率狀態：1)系統必須在生產環境中具有非常高的可用性(以便用戶可以忽略異常)，以及2)系統由于分區引起的宕機故障次數應該處于一個比較低的份額。Spanner滿足兩者。
網絡才是根本
許多人認為，Spanner通過使用真時(TrueTime)可以繞過CAP理論。真時(TrueTime)是一種能夠使用全局同步時鐘的服務。雖然真時(TrueTime)很棒，卻對于實現CA系統沒有太大貢獻，它的實際價值會在下文討論。如果說Spanner真有什么特別之處，那就是谷歌的廣域網。在多年的運營改進的基礎上，在生產環境中可以最大程度的減少分區發生，從而實現高可用性。
首先，Google的系統運行在自己的私有全球網絡之上。Spanner不在公共互聯網上運行——實際上，Spanner的每個數據包只流過Google控制的路由器和鏈路(不包括到遠程客戶端的邊緣鏈路)。此外，每個數據中心通常具有至少三個將其連接到私有全球網絡的獨立光纖，以確保每對數據中心的路徑分集(路徑多樣性)。同樣，在數據中心內部存在設備和路徑的冗余。因此，通常災難性事件，例如切斷光纜，不會導致分區或宕機。
因此，帶來分區的真正風險不是網絡路徑斷開，而是某種類型的廣泛配置或軟件升級，這些配置或升級會同時切斷多個網絡路徑。這才是真正的風險，Google一直在努力防止和減輕這種風險。一般的策略是限制任何特定更新的影響范圍(“爆炸半徑”)，以便當我們需要不可避免地推送一個錯誤的更改時，只影響部分路徑或副本，然后我們必須在其他任何更改之前修復這些問題。
雖然Google的基礎網絡可以大大減少分區的風險，但它不能提高光速。跨越廣域網的一致操作具有顯著的最小往返時間，這個時間可以達到幾十毫秒，當跨越大陸時則更長(1000英里的距離約為5百萬英尺，每納秒½英尺，因此最小值為10毫秒)。為了平衡區域內延遲和容災的需求，Google定義“區域”的范圍只具有2ms往返時間。Spanner通過事務流水線管理來緩解延遲，但這并不能減少單事務延遲。對于讀操作來說，由于能夠使用全局時間戳和本地副本(如下所述)，延遲通常較低。
具有弱一致性的模型具有較低的更新延遲。然而，沒有長程往返，弱一致性的模型也有一個較低的持久性窗口，因為在數據復制到另一個區域之前，災難可以同時摧毀本地和遠程多個副本。
網絡分區期間發生什么
為了理解分區，我們需要更多地了解Spanner的工作原理。與大多數ACID數據庫一樣，Spanner使用兩階段提交(2PC)和嚴格的兩階段鎖定，以確保隔離和強一致性。2PC已經被稱為“反可用性”協議[Hel16]，因為2PC要求所有成員節點必須參與工作(即必須可用)。為了緩解這個問題，Spanner為每個2PC成員節點建立Paxos組，這樣就算部分Paxos組成員宕機，2PC的“成員”還是高可用的。同時，數據也被分成組，形成放置和復制的基本單元。
如上所述，一般來說，當發生分區時，Spanner會選擇C而放棄A。在實際生產環境中，這是基于以下考慮：
- 使用Paxos組來實現更新的共識。如果領導節點由于分區而不能維持仲裁(法定數)，則更新被停止，并且系統不可用(通過CAP定義)。最終，在多數節點的分區，會重新選舉新的領導節點。
- 對跨組事務使用2PC意味著分區成員可以阻止事務提交。
分區在生產環境中最可能的結果是，有法定數節點的分區在選舉新的領導節點之后繼續工作，即服務繼續可用，但是少數節點分區一方的用戶則無法訪問服務。這是差別可用性的一個案例：少數節點分區一方的用戶可能有其他重大問題，比如失去連接，或已經宕機。這意味著構建在Spanner之上的多區域服務即使在分區期間也能夠良好工作。一些Paxos組完全不可用的可能性也是有的，但是不大。
只要所有已經建立聯系的組都具有基于法定數選舉的領導節點，并都位于分區的一側，則Spanner中的“事務”可以工作。這意味著有些事務會完美工作，有些事務會超時，但系統總是一致的。Spanner的實現屬性是，任何讀取的返回都是一致的，即使事務稍后中止(包括超時等任何原因)。
除了常規事務之外，Spanner還支持快照讀取——從過去的特定時間讀取。 Spanner隨時間維護數據的多個版本，每個版本都有一個時間戳，因此可以使用正確版本準確地回答快照讀取。特別地，每個副本知道它被寫入的時間(必須的)，并且任何副本可以在該時間戳之前單方面地回答讀取(除非它太舊了，并且已經被垃圾收集)。類似地，很容易在同一時間跨多個組讀取(異步)。快照讀取根本不需要鎖。事實上，只讀事務被實現為在當前時間(在任何最新的副本)的快照上讀取。
因此，快照讀取使分區更加健壯。特別地，快照讀取將會在下列條件下起作用：
- 正在初始化的分區中每個組至少存在一個副本，以及
- 這些副本的時間戳是過時的。
如果領導節點由于分區而失效，并且持續與分區同時失效，則第二條可能不成立，因為不可能在分區的這一側上選舉新的領導節點。在發生分區期間，讀取在分區開始之前時間戳處的數據，很可能在分區的兩側上都成功，因為任何可達副本的數據都滿足需求(譯者注：看來可用性還要看用是否需要最新的數據)。
關于真時(TrueTime)
一般來說，同步時鐘可以避免分布式系統中的通信。Barbara Liskov提供了帶有許多示例的詳細概述[Lis91]。對于我們的目標來說，真時(TrueTime)是一個有界非零誤差的全局同步時鐘：它返回一個時間間隔，這個時間間隔包含了調用執行的實際時間。因此，如果兩個間隔不重疊，則我們知道調用一定是實時排序的。如果間隔重疊，我們將無法知道調用的實際順序。
Spanner的一個精妙之處在于它從分布式鎖獲得串行性，從真時(TrueTime)獲得外部一致性(類似于線性化)。Spanner的外部一致性不變量是指，對任何兩個事務，T1和T2(即使在地球的兩側)：
如果T2在T1提交后開始提交，則T2的時間戳大于T1的時間戳。
借用Liskov[Lis91，第7節]的話：
可以使用同步時鐘可以降低違反外部一致性的概率。本質上來說，主服務器保存租約，對象是整個備份副本組。備份節點發送到主服務器的每條消息將授予主服務器租約。如果主存儲器保存有來自多數備份節點的未到期租約，則主數據庫可以單方面進行讀取操作。......
該系統中的不變量是：每當主服務器節點執行讀取時，它必須保存有來自大多數備份節點的有效租約。如果時鐘不同步，這個不變量將不會成立。
Spanner使用真時(TrueTime)作為時鐘，可以確保不變量成立。特別地，在事務提交期間，領導節點必須等待，直到確認提交時間是過去的(基于誤差范圍)。這種“提交等待”在生產環境中不是長時間的等待，并且與(內部)事務通信并行地進行。一般來說，外部一致性需要單調增加時間戳，而“等待不確定性”是一種常見的模式。
Spanner通過更新租約，延長領導節點的選舉時間，通常為10秒。就像Liskov所討論的，每當法定數節點同意一項決定時，租約被延長，因為參與節點剛剛驗證了領導節點是有效的。當領導節點故障時，有兩個選項：1)等待租約過期，然后選擇新的領導節點，或2)重啟舊領導節點，這可能更快。對于一些故障，我們可以發出“最后一個”UDP數據包來釋放租約，這是用來加速租約的到期。由于計劃外的故障在Google數據中心中很少見，所以長期租約很有意義(譯者注：樂觀方法)。租約還確保領導節點之間的時間單調性，并且使得群組參與節點能夠在租約時間內提供讀取(即使沒有領導節點)。
然而，真時(TrueTime)的真正價值在于它在一致性快照方面的能力。回望過去，多版本并發控制系統(MVCC)[Ree78]的歷史已經很悠久了——單獨保存舊版本，讀取操作從舊的版本中讀取數據，而不需要考慮當前的事務操作。這是一個非常有用和被低估的屬性：特別是，Spanner快照是一致的(對于快照時間)，因此無論系統保存什么樣的不變量，快照也將會保存。這是真的，盡管你不知道什么是不變量!本質上來說，快照來自于連續事務之間，并且反映了快照時間之前的所有內容(更多的就沒有了)。如果沒有事務一致的快照，系統很難從過去的某個時間點重新啟動，因為事務部分提交的內容可能違反了一些不變量或完整性約束。正是缺乏一致性，有時系統很難從備份中還原——沖突的數據需要手動恢復。
例如，考慮使用MapReduce在數據庫上執行大型分析查詢。如果使用Bigtable作為數據庫，盡管Bigtable也存儲數據過去的版本，但數據分片的時間標簽是“鋸齒狀”的，這使得結果不可預測，有時還會導致不一致(特別是對于最近的數據)。如果使用Spanner作為數據庫，同一個MapReduce操作可以選擇精確的時間戳，并獲得可重復和一致的結果。
真時(TrueTime)還使跨多個獨立系統記錄快照成為可能——只要使用(單調遞增)真時(TrueTime)時間戳提交，與快照時間達成一致，并隨時間存儲多個版本(通常在日志中)。這不僅限于Spanner：您可以制作自己的事務系統，并且兩個系統(甚至k系統)上的快照是一致的。一般來說，在這些系統上你需要一個2PC(同時持有鎖)來與快照時間達成一致并確認成功，但系統不需要就其他事項達成一致，可以完全不同。
你還可以使用時間戳作為令牌在工作流中傳遞。例如，如果對系統進行更新，你可以將更新的時間戳傳遞到工作流的下一個階段，以便確定系統是否反映該事件后的時間。在發生分區的情況下，就不一定了。在這種情況下，下一個階段實際上應該等待保持一致性(或繼續工作保持可用性)。如果沒有時間戳令牌，很難知道你需要等待什么。當然，傳遞時間戳不是解決這個問題的唯一方法，但這是一種優雅的，魯棒的方式，同時確保最終一致性。當不同的階段不共享代碼且具有不同的管理員時，這特別有用——兩者可以在沒有通信的情況下對時間達成一致。
快照是關于過去的，Spanner也可以對未來時間達成共識。Spanner的一項功能是，你可以對未來schema變更的時間達成一致。這允許你暫停應用新schema的更改，以便能夠同時服務兩個版本。一旦你準備好了，你可以選擇一個時間點，在所有副本上以原子方式同時切換到新的schema(你也可以選擇之前的時間點，但你不可能在目標時間之前準備好)。至少在理論上，你可以進行未來的操作，例如可見性計劃的刪除或更改。
真時(TrueTime)本身可能受到分區的阻礙。真時(TrueTime)的來源是GPS接收器和原子鐘的組合，兩者都可以通過它們自身的微小漂移來保持精確的時間。由于每個數據中心都有“主時間服務器”(冗余)，因此分區的兩側很可能繼續享有準確的時間。然而，獨立的節點需要到通過網絡連接到時間服務器，否則它們的時鐘將會漂移。因此，在分區期間，基于本地時鐘漂移的速率，獨立節點的間隔隨著時間緩慢地增長。基于真時(TrueTime)的操作，如Paxos領導節點選舉或事務提交，因此必須多等待一段時間，但操作仍能夠完成(假設2PC和法定數仲裁的通信工作良好)。
Eric Brewer
VP, Infrastructure at Google
Professor, UC Berkeley
結論
作為一個全球規模的分布式系統，Spanner只是提供了一致性和大于5個9的可用性，但Spanner宣稱是一個“實際上是CA”系統是合理的。與Chubby一樣，如果你能夠控制整個網絡(盡管全球范圍內不常見)，CA組合在實際生產環境中是可能的。即使這樣，仍舊需要網絡路徑的大量冗余，處理相關故障的架構規劃，以及計劃周密的運維，特別是系統升級的時候。在發生宕機的情況時，Spanner選擇一致性而不是可用性。
Spanner使用2PC來實現串行化，使用真時(TrueTime)實現外部一致性，無鎖一致性讀取，以及一致的快照。
【本文是51CTO專欄作者石頭的原創文章，轉載請通過作者微信公眾號補天遺石(butianys)獲取授權】
