Google Spanner 2012 記 (1) 總覽

來自專欄分散式和存儲的那些事39 人贊了文章

本系列基本是根據google spanner 2012年的paper[1]進行的一些總結。

What?

spanner是什麼？大概沒有哪句話可以比paper本身說的更明白了。

Spanner is Google』s scalable, multi-version, globally distributed, and synchronously-replicated database... Applications can use Spanner for high availability, even in the face of wide-area natural disasters, by replicating their data within or even across continents...

看著好像很厲害，抗自然災害、跨洲際複製…又有點過於平淡了。畢竟，一個分散式資料庫，不貼上什麼replication啊，scalability啊，highly available啊的標籤都不好意思出門。因此在講spanner怎麼做這些功能前，我認為更重要的是理解它的意義：

• 為什麼google需要一個這樣的db？換句話說，沒有spanner之前，google在用的db有哪些好的設計、特性可以借鑒繼承？又有哪些不足、痛點，需要spanner去解決？
• spanner還有哪些新特性？
• spanner是怎麼設計實現這些特性的？

Why?

從introduction中可以看出，spanner可以看成是大名鼎鼎的bigtable[2]和默默無聞（相比bigtable）的megastore[3]的延伸。尤其是bigtable，對spanner設計影響之深遠在文中隨處可見。

雖是同門手足，作為一篇paper，該黑的時候自然不能手軟。讓我們看看文中列舉了bigtable的哪些「劣跡」（具體參見[1] section 2.3）：

1. bigtable只能說是一個key-value storage。相比之下，megastore的schematized tables用著更舒服，也更容易支持SQL
2. bigtable在進行跨數據中心的備份（replication）時是非同步的（asynchronous），因此只能做到最終一致性（eventual consistency）。
3. bigtable只支持單行（single row）的transaction

而megastore呢？支持schematized tables, 支持同步備份（synchronous replication），但是寫的吞吐量（write throughput）不太夠看。雖然我並不清楚這個吞吐量究竟有多差，但按照google一貫的極（tu）致（hao）風格，沒什麼能比寫一個更好的更加誘人了，所以我們就繼續忽略megastore好了。

總結下來，spanner大概需要做到這麼幾件事：

1. 表現的得像一個資料庫，支持schema的定義更改，以及SQL
2. 同步的（synchronous）、一致的（consistent）備份，而且可以跨數據中心、甚至是全球範圍內
3. 更好的transaction，比如跨多行、一致性等。在後續的文章中我們就會見到spanner的精髓之一：外部一致的（externally-consistent）transaction

在談及系統設計與構架前，我們再來理解下Spanner的數據模型（仍見[1] section 2.3）

Each database can contain an unlimited number of schematized tables...

Spanner』s data model is not purely relational, in that rows must have names. More precisely, every table is required to have an ordered set of one or more primary-key

columns...

可以看到，spanner中的一個資料庫（database）中是可以包含數量不限個表（table）的。每個表都需要定義好schema。這是它和一個關係型資料庫的相似之處。

然而每個spanner table中的每一行（row）仍然必須對應到一個可排序的key。換句話說，spanner table本質上仍是一個map，只是每個key都映射到了一系列schematized columns上。從這個角度來講，它仍有key-value store的影子。

對比之下，bigtable中不同行的columns是完全獨立的，因此bigtable的表是schemaless，也是它完全是一個key-value store的原因。

Goolge Spanner

| key | name | age ||------|----------|-------|| goog | Google | 20 || fb | Facebook | 14 |...

Google Bigtable

"goog": {name: "Google" }"fb" : {age: 14, location: "Menlo Park, CA"}"amzn": {url: "www.amazon.com"}...

How?

啰嗦了這麼多，讓我們先一睹spanner構架真容：

（嗯，長得果然跟bigtable有幾分神似...）

這些方塊兒們究竟各司何職呢？

• 一個spanner的部署（deployment）稱為一個universe。不同的部署環境（比如test/qa/prod）中的spanner是隔離的。
• 每個universe中的spanner是由一系列zones構成的。一個zone大致對應於一個地點或數據中心（有時同一個數據中心也可以包含多個zones）。數據被備份到這些zones所對應的地點中。zone可以在spanner運行時被動態添加或移除，以支持數據中心的定期維護以及災時處理等情況。
• 一個zone內有一個zonemaster，以及千千萬萬個spanservers。zonemaster是大腦，決定哪塊數據應該分給哪些spanserver。後者則是真正的伺服器，處理用戶的數據請求。
• 此外，每個地點（大致等同於zone）還有一個location proxy。客戶在請求spanserver前，得先問問它究竟要跟哪個spanserver交流。個人猜測這個模塊會根據客戶距離，stickiness等信息分配spanserver，在延遲及spanserver的負載間做一個平衡。
• 最後，在universe這一範圍中，還有zone master和placement driver兩個模塊。前者主要負責一些監測數據，方便debug和維護。後者則更關鍵一些：它定期負責把數據在不同zone之間移動，以滿足備份要求（比如某份數據需要在三個zone內有備份），或者平衡負載。

Spanserver Software Stack (Google S3? :p)

資料庫的核心是，呃，數據。那麼負責讀寫數據的spanserver自然也是spanner的重中之重。[1]-圖2展示了spanserver的整個技術棧。

讓我們用一種自底向上的方式去解讀這些模塊：

• 最底下的colossus是大名鼎鼎的GFS的繼承者，充當著file system的角色。
• 稍微往上一點，每個spanserver負責大概100~1000個一種叫做tablet的數據結構。一個tablet可以看成是一個二維的map，即：(key: string, timestamp: int64) -> string。每個tablet的數據及狀態都存在了colossus中。注意到，spanner的tablet跟bigtable tablet是有區別的，前者中的key range並不一定是連續的。

分散式系統里，synchronous replication基本就是paxos或者raft的同義詞，這在spanner中也不例外。一個spanserver在它負責的每一個tablet上，都維護了一套paxos狀態機，稱為一個replica，即(spanserver, tablet) -> replica。為了提升paxos的效率，spanner的paxos實現存在一個中心化、lease-based leader。一個leader lease的默認時長是10秒。寫（write）請求必須發送到paxos leader上並執行一次paxos協議，而讀（read）請求可以被任意一個數據足夠新的replica處理。所有負責同一個tablet的replicas的集合稱為一個paxos group。

每個paxos group的leader都維護了一個lock table和一個transaction manager，用來進行並發控制（concurrency control）。具體是怎麼玩，讓我們留到下一篇...

/*** 更新 2018-06-16 ***/

備份

為了方便數據的備份與轉移，spanner將一個tablet再次拆分成一個個directory。一個directory由一系列具有共同前綴（common prefix）的鍵所對應的行構成。它是數據遷移與備份的最小單元。

從[1]-圖3可以看出，一個directory可以從一個paxos group遷移到另一個。每個directory下的所有數據行都備份在了其所屬的paxos group中（而不是備份在多個group中）。此外，一個paxos group是跨越多個zones的，雖然這點並非必須。

遷移directory有哪些好處呢？

1. 可以在不同的paxos group之間進行負載均衡。
2. 加強data locality：即經常一起被讀寫的directories應該盡量被放到同一個paxos group內。
3. 可以通過將directory遷移到一個距離用戶較近的paxos group，來降低數據讀寫的延遲。

在兩個paxos groups之間遷移一個directory並不是用一個transaction完成的，否則當遷移的directory很大時，這樣做會長時間阻塞其他的transactions，降低性能。spanner的做法是先複製directory內的大部分數據到新的group中，最後用一個transaction原子性地把剩餘的數據遷移，並且改變該directory在新舊兩個paxos group間的所有權（ownership）。具體流程原文講的並不是很明確，但是可以參考[4]（原文參考文獻中14）

下一篇：西半球飯桶：Google Spanner 2012 記 (2) Transaction前奏

Reference

1. Corbett, James C., et al. "Spanner: Google』s globally distributed database."ACM Transactions on Computer Systems (TOCS)31.3 (2013): 8.
2. Chang, Fay, et al. "Bigtable: A distributed storage system for structured data."ACM Transactions on Computer Systems (TOCS)26.2 (2008): 4.
3. Baker, Jason, et al. "Megastore: Providing scalable, highly available storage for interactive services."CIDR. Vol. 11. 2011.
4. Douceur, John R., and Jon Howell. "Distributed directory service in the Farsite file system." InProceedings of the 7th symposium on Operating systems design and implementation, pp. 321-334. USENIX Association, 2006.

推薦閱讀：