從Google Spanner漫談分布式存儲與數據庫技術
Spanner 的設計反映了 Google 多年來在分布式存儲系統領域上經驗的積累和沉淀，它采用了 Megastore 的數據模型，Chubby 的數據復制和一致性算法，而在數據的可擴展性上使用了 BigTable 中的技術。新穎之處在于，它使用高精度和可觀測誤差的本地時鐘來判斷分布式系統中事件的先后順序。Spanner 代表了分布式數據庫領域的新趨勢——NewSQL。
Spanner 是 Google 最近公開的新一代分布式數據庫，它既具有 NoSQL 系統的可擴展性，也具有關系數據庫的功能。例如，它支持類似 SQL 的查詢語言、支持表連接、支持事務（包括分布式事務）。Spanner 可以將一份數據復制到全球范圍的多個數據中心，并保證數據的一致性。一套 Spanner 集群可以擴展到上百個數據中心、百萬臺服務器和上T條數據庫記錄的規模。目前，Google 廣告業務的后臺（F1）已從 MySQL 分庫分表方案遷移到了 Spanner 上。
數據模型
傳統的 RDBMS（例如 MySQL）采用關系模型，有豐富的功能，支持 SQL 查詢語句。而 NoSQL 數據庫多是在 key-value 存儲之上增加有限的功能，如列索引、范圍查詢等，但具有良好的可擴展性。Spanner 繼承了 Megastore 的設計，數據模型介于 RDBMS 和 NoSQL 之間，提供樹形、層次化的數據庫 schema，一方面支持類 SQL 的查詢語言，提供表連接等關系數據庫的特性，功能上類似于 RDBMS；另一方面整個數據庫中的所有記錄都存儲在同一個 key-value 大表中，實現上類似于 BigTable，具有 NoSQL 系統的可擴展性。
在 Spanner 中，應用可以在一個數據庫里創建多個表，同時需要指定這些表之間的層次關系。例如，圖 1 中創建的兩個表——用戶表（Users）和相冊表（Albums），并且指定用戶表是相冊表的父節點。父節點和子節點間存在著一對多的關系，用戶表中的一 條記錄（一個用戶）對應著相冊表中的多條記錄（多個相冊）。此外，要求子節點的主鍵必須以父節點的主鍵作為前綴。例如，用戶表的主鍵（用戶 ID）就是相冊表主鍵（用戶 ID+ 相冊 ID）的前綴。
圖 1 schema 示例，表之間的層次關系，記錄排序后交錯的存儲
顯然所有表的主鍵都將根節點的主鍵作為前綴，Spanner 將根節點表中的一條記錄，和以其主鍵作為前綴的其他表中的所有記錄的集合稱作一個 Directory。例如，一個用戶的記錄及該用戶所有相冊的記錄組成了一個 Directory。Directory 是 Spanner 中對數據進行分區、 復制和遷移的基本單位，應用可以指定一個 Directory 有多少個副本，分別存放在哪些機房中，例如把用戶的 Directory 存放在這個用戶所在地區附近的幾個機房中。
這樣的數據模型具有以下好處。
- 一個 Directory 中所有記錄的主鍵都具有相同前綴。在存儲到底層 key-value 大表時，會被分配到相鄰的位置。如果數據量不是非常大，會位于同一個節點上，這不僅提高了數據訪問的局部性，也保證了在一個 Directory 中發生的事務都是單機的。
- Directory 還實現了從細粒度上對數據進行分區。整個數據庫被劃分為百萬個甚至更多個 Directory，每個 Directory 可以定義自己的復制策略。這種 Directory-based 的數據分區方式比 MySQL 分庫分表時 Table-based 的粒度要細，而比 Yahoo!的 PNUTS 系統中 Row-based 的粒度要粗。
- Directory 提供了高效的表連接運算方式。在一個 Directory 中，多張表上的記錄按主鍵排序，交錯（interleaved）地存儲在一起，因此進行表連接運算時無需排序即可在表間直接進行歸并。
復制和一致性
Spanner 使用 Paxos 協議在多個副本間同步 redo 日志，從而保證數據在多個副本上是一致的。Google 的工程師鐘情于 Paxos 協議，Chubby、Megastore 和 Spanner 等一系列產品都是在 Paxos 協議的基礎上實現一致性的。
Paxos 的基本協議很簡單。協議中有三個角色：Proposer、Acceptor 和 Learner，Learner 和 Proposer 分別是讀者和寫者，Acceptor 相當于存儲節點。整個協議描述的是，當系統中有多個 Proposer 和 Acceptor 時，每次 Proposer 寫一個變量就會啟動一輪決議過程（Paxos instance），如圖 2 所示。決議過程可以保證即使多個 Proposer 同時寫，結果也不會在 Acceptor 節點上不一致。確切地說，一旦某個 Proposer 提交的值被大多數 Acceptor 接受，那么這個值就被選中，在整輪決議的過程中該變量就不會再被修改為其他值。如果另一個 Proposer 要寫入其他值，必須啟動下一輪決議過程，而決議過程之間是串行（serializable）的。
圖 2 Paxos 協議正常執行流程
一輪決議過程分為兩個階段，即 prepare 階段和 accept 階段。
- 第一階段A：Proposer 向所有 Acceptor 節點廣播 prepare 消息，消息中只包含一個序號——N。Proposer 需要保證這個序號在這輪決議過程中是全局唯一的（這很容易做到，假如系統中有兩個 Proposer，那么一個 Proposer 使用1，3，5，7，9，……，另一個 Proposer 則使用0，2，4，6，8，……）。
- 第一階段B：Acceptor 接收到 prepare 消息后，如果N是到目前為止見過的最大序號，就返回一個 promise 消息，承諾不會接受序號小于N的請求；如果已接受過其他 Proposer 提交的值，則會將這個值連同提交這個值的請求的序號一同返回。
- 第二階段A：當 Proposer 從大多數 Acceptor 節點收到了 promise 消息后，就可以選擇接下來要向 Acceptor 提交的值了。一般情況下，當然選原本打算寫入的值，但如果從收到的 promise 消息中發現已經有其他值被 Acceptor 接受了，那么為了避免造成數據不一致的風險，這時 Proposer 就必須“大義滅親”，放棄自己打算寫入的值，從其他 Proposer 提交的序號中選擇一個最大的值。接下來 Proposer 向所有的 Acceptor 節點發送 accept 包，其中包含在第一階段中挑選的序號N和剛才選擇的值V。
- 第二階段B：Acceptor 收到 accept 包之后，如果N的大小不違反對其他 Proposer 的承諾，就接受這個請求，記錄下值V和序號N，返回一個 ack 消息。反之，則返回一個 reject 消息。
如果 Proposer 從大多數 Acceptor 節點收到了 ack 消息，說明寫操作成功。而如果在寫操作過程中失敗，Proposer 可以增大序號，重新執行第一階段。
基本的 Paxos 協議可以保證值一旦被選出后就一定不會改變，但不能保證一定會選出值來。換句話說，這個投票算法不一定收斂。有兩個方法可以加速收斂的過程：一個是在出現 沖突后通過隨機延遲把機會讓給其他 Proposer，另一個是盡量讓系統中只有一個 Proposer 去提交。在 Chubby 和 Spanner 系統中這兩種方法都用上了，先用隨機延遲的方法通過一輪 Paxos 協議，在多個 Proposer 中選舉出一個 leader 節點。接下來所有的寫操作都通過這個 leader 節點，而 leader 節點一般還是比較“長壽”的，在廣域網環境下平均“任期”可以達到一天以上。而 Megastore 系統中沒有很好地解決這個問題，所有的 Proposer 都可以發起寫操作，這是 Megastore 寫入性能不高的原因之一。
基本的 Paxos 協議還存在性能上的問題，一輪決議過程通常需要進行兩個回合通信，而一次跨機房通信的代價為幾十到一百毫秒不等，因此兩個回合的通信就有點開銷過高了。不 過幸運的是，絕大多數情況下，Paxos 協議可以優化到僅需一個回合通信。決議過程的第一階段是不需要指定值的，因此可以把 prepare/promise 的過程捎帶在上一輪決議中完成，或者更進一步，在執行一輪決議的過程中隱式地涵蓋接下來一輪或者幾輪決議的第一階段。這樣，當一輪決議完成之后，其他決議 的第一階段也已經完成了。如此看來，只要 leader 不發生更替，Paxos 協議就可以在一個回合內完成。為了支持實際的業務，Paxos 協議還需要支持并發，多輪決議過程可以并發執行，而代價是故障恢復會更加復雜。
因為 leader 節點上有最新的數據，而在其他節點上為了獲取最新的數據來執行 Paxos 協議的第一階段，需要一個回合的通信代價。因此，Chubby 中的讀寫操作，以及 Spanner 中的讀寫事務都僅在 leader 節點上執行。而為了提高讀操作的性能，減輕 leader 節點的負載，Spanner 還提供了只讀事務和本地讀。只讀事務只在 leader 節點上獲取時間戳信息，再用這個時間戳在其他節點上執行讀操作；而本地讀則讀取節點上最新版本的數據。
與 Chubby、 Spanner 這種讀寫以 leader 節點為中心的設計相比，Megastore 體現了一定的“去中心化”設計。每個客戶端都可以發起 Paxos 寫操作， 而讀操作則盡可能在本地執行。如果客戶端發現本地數據不是最新的，會啟動 catchup 流程更新數據，再執行本地讀操作返回給客戶端。
最后，對比下其他系統中 replication 的實現。在 BigTable 系統中每個 tablet 服務器是沒有副本的，完全依賴底層 GFS 把數據存到多臺機器上。數據的讀寫都通過單個 tablet 服務器，在 tablet 服務器出現故障的時需要 master 服務器將 tablet 指派到其他 tablet 服務器上才能恢復可用。Dynamo 系統則貫徹了“去中心化”的思想，將數據保存在多個副本上，每個副本都可以寫入（update everywhere）。而不同副本同時寫入的數據可能會存在不一致，則需要使用版本向量（version vector）記錄不同的值和時間戳，由應用去解釋或合并不一致的數據。盡管 Dynamo 系統還提供了 NWR 的方式來支持有一致性保證的讀寫操作，但總的來說 Dynamo 為了高可用性犧牲了一致性。ZooKeeper、MongoDB 與 Chubby、Spanner 類似，通過 leader 選舉協議從多個副本中選擇一個 leader，所有寫操作都在經過 leader 節點序列化后，同步到其他副本上。ZooKeeper 則是在寫入大多數節點后返回，而 MongoDB 主要采用異步的主從復制方式。
分布式事務
Spanner 系統中的分布式事務通過兩階段提交協議（2PC）實現。2PC 是一類特殊的一致性協議，假設一個分布式事務涉及了多個數據節點，2PC 可以保證在這些節點上的操作要么全部提交，要么全部失敗，從而保證了整個分布式事務的原子性（ACID 里的A）。協議中包含兩個角色：協調者（coordinator）和參與者（participant/cohort）。協調者是分布式事務的發起者，而參 與者是參與了事務的數據節點。在協議最基本的形式中，系統中有一個協調者和多個參與者。
顧名思義，2PC 也包含兩個階段，即投票階段和提交階段（如圖 3 所示）。
圖 3 兩階段提交協議
- 在第一階段，協調者向所有的參與者發送投票請求，每個參與者決定是否要提交事務。如果打算提交的話需要寫好 redo、undo 等日志，并向協調者回復 yes 或 no。
- 在第二階段，協調者收到所有參與者的回復，如果都是 yes，那么決定提交這個事務，寫好日志后向所有參與者廣播提交事務的通知。反之，則中止事務并且通知所有參與者。參與者收到提交/中止事務的命令后，執行相應操作，如果提交的話還需要寫日志。
協議過程包括兩回合的通信，在協調者和參與者端需要多次寫日志，而且整個過程中所有參與者都占有讀鎖、寫鎖，可見 2PC 開銷不菲。
2PC 最令人詬病之處還不在于性能，而是在有些故障條件下，會造成所有參與者占有讀鎖、寫鎖堵塞在第二階段，需要人工干預才能繼續，存在嚴重的可用性隱患。假設 故障發生在第二階段，協調者在做出決定后，通知完一個參與者就宕機了，更糟糕的是被通知的這位參與者在執行完“上級指示”之后也宕機了，這時對其他參與者 來說，就必須堵塞在那里等待結果。
Spanner 利用基于 Paxos 協議的復制技術，改善了 2PC 的可用性問題。2PC 協議過程中的協調者和參與者生成的日志都會利用 Paxos 協議復制到所有副本中，這樣無論是協調者或參與者宕機，都會有其他副本代替它們，完成 2PC 過程而不至于堵塞。在 Paxos 協議上實現 2PC 這一思路很巧妙，Paxos 協議保證了大多數節點在線情況下的可用性，而 2PC 保證了分布式協議的一致性。
事件的順序
傳統上，在設計一個分布式系統時，都會假設每個節點的運行速度和時鐘的快慢各不相同的情況，并且在節點之間進行同步的唯一方法就是異步通信。系 統中的每個節點都扮演著觀察者的角色，并從其他節點接收事件發生的通知。判斷系統中兩個事件的先后順序主要依靠分析它們的因果關系，包括 Lamport 時鐘、向量時鐘等算法，而這一切都存在通信開銷。
因此，Spanner 提出了一種新的思路，在不進行通信的情況下，利用高精度和可觀測誤差的本地時鐘 （TrueTime API）給事件打上時間戳，并且以此比較分布式系統中兩個事件的先后順序。利用這個方法，Spanner 實現了事務之間的外部一致性（external consistency）（如圖 4 所示），也就是說，一個事務結束后另一個事務才開始，Spanner 可以保證第一個事務的時間戳比第二個事務的時間戳要早，從而兩個事務被串行化后也一定能保持正確的順序。
圖 4 事務外部一致性的實現
TrueTime API 是一個提供本地時間的接口，但與 Linux 上 gettimeofday 接口不一樣的是，它除了可以返回一個時間戳t，還會給出一個誤差ε。例如，返回的時間戳是 1 分 30 秒 350 毫秒，而誤差是 5 毫秒，那么真實的時間在 1 分 30 秒 345 毫秒到 355 毫秒之間。真實的系統中ε平均下來是 4 毫秒。
利用 TrueTime API，Spanner 可以保證給出的事務標記的時間戳介于事務開始的真實時間和事務結束的真實時間之間。假如事務開始時 TrueTime API 返回的時間是{t1, ε1}，此時真實時間在 t1-ε1到 t1+ε1之間；事務結束時 TrueTime API 返回的時間是{t2, ε2}，此時真實時間在 t2-ε2到 t2+ε2之間。Spanner 會在 t1+ε1和 t2-ε2之間選擇一個時間點作為事務的時間戳，但這需要保證 t1+ε1小于 t2-ε2，為了保證這點，Spanner 會在事務執行過程中等待，直到 t2-ε2大于 t1+ε1時才提交事務。由此可以推導出，Spanner 中一個事務至少需要2ε的時間（平均 8 毫秒）才能完成。
由此可見，這種新方法雖然避免了通信開銷，卻引入了等待時間。為了保證外部一致性，寫延遲是不可避免的，這也印證了 CAP 定理所揭示的法則，一致性與延遲之間是需要權衡的。
最后介紹一下 TrueTime API 的實現。TrueTime API 的實現大體上類似于網絡時間協議（NTP），但只有兩個層次。第一層次，服務器是擁有高精度計時設備的，每個機房若干臺，大部分機器都裝備了 GPS 接收器，剩下少數機器是為 GPS 系統全部失效的情況而準備的，叫做“末日”服務器，裝備了原子鐘。所有的 Spanner 服務器都屬于第二層，定期向多個第一層的時間服務器獲取時間來校正本地時鐘，先減去通信時間，再去除異常值，最后求交集。
NewSQL
六年前，BigTable 展示了一個簡潔、優美、具有高可擴展性的分布式數據庫系統，引起了 NoSQL 浪潮。然而 Spanner 的設計者們指出了 BigTable 在應用中遇到的一些阻力。
- 缺少類似 SQL 的界面，缺少關系數據庫擁有的豐富的功能。
- 只支持單行事務，缺少跨行事務。
- 需要在跨數據中心的多個副本間保證一致性。
這些來自應用開發者的需求催生了 Spanner，一個既擁有 key-value 系統的高可擴展性，也擁有關系數據庫的豐富功能（包括事務、一致性等特性）的系統。這類兼顧可擴展性和關系數據庫功能的產品被稱為 “NewSQL”，Spanner 的公開會不會開啟 NewSQL 的時代呢？我們拭目以待。
總結
最后從 CAP 定理的角度來分析下 Spanner。
CAP 定理是指在網絡可能出現分區故障的情況下，一致性和可用性不可得兼。形式化地說就是，P => 非(A與P)，可以更進一步地總結為，一致性和延遲之間必須進行權衡。Paxos 協議在C和A之間選擇了嚴格的一致性，而A則降級為大多數一致性 （majority available）。
Spanner 還通過在事務中增加延遲的方法實現了外部一致性，每個事務需要至少兩倍的時鐘誤差才能完成。如果時鐘出現故障造成誤差增長，那么完成事務所需的時間也就隨 之增長。在這里，時鐘故障也應當認為是P的一種形式。在發生時鐘故障（P）的情況下，為了保證一致性（C），而必須增加延遲（A），這一點充分印證了 CAP 定理。
從 Spanner 系統中，我們可以學習到一些經驗。
- MegaStore、Spanner 和 F1 系統所選擇的樹形、層次化的數據庫 schema 是很精妙的，它能支持高效的表連接，這既提供了類似關系模型的范式，也提供了一個合適的粒度進行數據分區，具有好的可擴展性，H-Store 也采用了這樣的 schema。
- 跨數據中心的多個副本間保持一致是可行的，Paxos 協議的性能可以優化到一個可接受的范圍。
- 在 Paxos 協議的基礎之上實現的兩階段提交的可用性得到了提高。
- 在一個分布式系統中，本地時鐘的作用可以比我們之前想象的大很多。
作者曹偉，淘寶核心系統數據庫組技術專家，從事高性能服務器、IM、P2P、微博等各類型分布式系統、海量存儲產品的開發，關注系統高可用性和一致性及分布式事務領域。