393
spanner 的前世今生
spanner的前身是big table，讓我們先來看看big table這個老子的方方麵麵，然後再來看看兒子spanner為啥一出世就吸引了全球技術人員的眼球。
2006年，google 發表了big table [1]的文章，為什麼要做big table，下麵有一個簡短的總結[2]：
就是一個問題：數據太多，訪問量太大，規模問題出現。規模是問題的源泉，是後續故事的核心，在此基礎上才碰到了動態schema（semi-structure帶來的問題，比如big table支持的schema change），全局可用，數據一致讀寫等問題。
big table的數據模型是 <row, column, timestamp> -> cell content ，每個cell都是一個三維空間中的一個點，每個維度都是動態可配置的(行可以隨意增加，列可以隨意增加，時間序列可以隨意增加），非常靈活自由。
big table 的係統架構，解決數據和訪問在一個cluster內部如何分配：將數據分片，每台tablet server load 若幹分片，有一個核心節點master來做全局信息同步。
在big table 論文發布之後，big table一直在改進，主要是致力於提供更好的scalability；加入了跨cluster（一般是跨機房的cluster）的數據異步複製以及Coprocessor（HBase的coprocess應該也是從這裏引入）。
google 大哥在成長，工程師需要更好用的結構化存儲，big table 看來在以下幾個方麵做的不夠好：
1. 分布式transaction：比如A給B發送了一個消息，那麼A的發件箱和B的收件箱應該同時有一封信件，這是一個完整的事務，應該遵循事務的ACID原則，但是big table無法支持，其隻支持single-row-transactions。這也也好理解，在啥都沒有的情況下，big table的出世就足以讓人興奮，誰會為分布式transaction傷腦筋呢？不過日子越過越好，人們的要求也越來越高，這件事情就逃避不掉了。
2. 強一致性數據同步：即使某些用戶不要求分布式transaction，那麼強一致性也是希望提供的，也就是說在數據沒有同時主、備集群寫入之前，不要返回client成功的消息。應用有此需求也容易理解，如果你主集群寫完就返回，然後主集群掛了，我最新的數據不是丟了嗎？
3. SQL語言支持：大家都很懶
4. 全球負載均衡：負載均衡是個很大的話題，包括存儲負載（存儲空間全球數據中心共享）、調度負載（在全球數據中心內平衡CPU/MEM利用）、網絡負載（在全球數據中心內平衡網絡流量）、距離負載（讓數據緊貼應用進行全球移動）
不得不說，係統真的是一步步進步的，人們的需求真的是一步步提高的，如果不是big table做出來，這些問題估計沒人敢想。也正是因為這些問題的存在，Spanner[3]橫空出世。
看看spanner解決了哪些問題：
Spanner is Google’s scalable, multi-version, globally distributed, and synchronously-replicated database
Spanner’s main focus is managing cross-datacenter replicated data, providing externally consistent [16] reads and writes, and
globally-consistent reads across the database.
最核心的是兩點：
1. 分布式transaction
2. 全球自動化負載均衡（細粒度切分和全球數據複製都是為這個目的服務的）
Spanner 體係架構：
A Spanner deployment is called a universe. 全球隻有三個spanner，分別用於測試、開發/生產（VS dark launching from Facebook ?）和生產。
Spanner is organized as a set of zones, where each zone is the rough analog of a deployment of Bigtable. 全球big table 集群（類比）被統一管理，統一調度起來就是spanner。
The universe master is primarily a console that displays status information about all the zones for interactive debugging. universe master並不是用來服務係統的，更像是個管理工具。
tablet和paxos state machine共存，多個互為replica的tablet和paxos state machine形成了paxos group，其中有一個是leader，也就是用於寫的tablet，保管lock table等。該leader同時也是一個transaction manager，用於實現分布式transaction。當實現分布式transaction時候，有不止一個paxos group參與進來，這時候有一個group會被選作coordinator group，則該group的leader就是coordinator leader，該group的slave就是coordinator slave。(這部分跟Spanner沒多少關係，是distributed transaction的經典內容）
在big table中，tablet隻是行數據的容器，tablet內部的行都是一視同仁的；而spanner對tablet進行了進一步的結構劃分，多了一層dictionary結構，用以區分那些PK前綴相同的行（比如，所有以Alice開頭的行都在一個dictionary裏麵）。dictionary是數據複製和placement配置的基本單位，比如某個dictionary要分布在亞洲和美洲，共4份拷貝。
spanner中負載均衡的最小單位也是dictionary，同時提供方法MoveDir可以手動將一個dictionary移動到指定的zone。文中提到dictionary隻是一層抽象目錄，下麵還有fragment才是真正的物理目錄，有點詫異。細粒度當然可以更加優化負載均衡以及數據恢複，但是太細的粒度也意味著複雜度成倍增加，這是不是值得呢？可能的原因是某些用戶的dictionary目錄裏麵數據還是太多，而同時反正分布式transaction已經實現，不同fragment之間交互也順便可以借點光，沒有增加太多的實現負擔，不過我仍然感覺到這點做的太複雜了。
另外，文中雖然沒寫，根據之前的一些資料，dictionary應該也是權限控製的最小單元。
關於數據模型：
關於big table 不實現傳統transaction的理由是：我們認為這些transaction太複雜，程序員會過度使用transaction從而導致性能太差，所以不實現。
而這裏spanner實現傳統的transaction的理由是：係統的職責是實現應該有的功能，如果程序員用錯了，那麼改正就行了；但是如果係統不實現，誰也沒辦法用。
上麵應該是經典的需求實現問題，不同的人會有不同的理解。
spanner的行模型是 (key:string, timestamp:int64) -> row content，可以看到跟big table的模型最大的不同是這裏強化了row的概念，不再突出column；這樣spanner的timestamp是賦給整行數據的，是有物理意義的，這使得spanner更像一個實現多版本並發的數據庫，而在big table中，timestamp僅僅用於保存多個版本的key-value，跟並發完全無關；我覺得這也是為什麼spanner稱自己為semi-relational 數據庫，而big table隻稱自己是semi-structure 數據庫的原因。
下麵是spanner的數據表模式，其中user是一張父親表，album一張子表（不存在沒有user的album），這非常像一個樹形結構，user樹枝，blbum是樹葉，多麼清晰，好的東西都是易於理解的，大部分時候也是難於實現的。
關於TrueTime：隻要知道兩點就可以了：
1. 一堆機器投票來決定當前時間應該是多少，然後按人頭計數，人多者勝。
2. 跟傳統投票不同的是，每個人不是報來一個數字，而是根據一般誤差報上一個範圍來，比如A報[3-4], B 報[4-5], C報[3-5]，結果就會變成4，因為每人都同意現在是4點。再詳細的話請看原論文吧。
並發控製：
1. 對於什麼是external consistency, 我理解不深，覺得就當成serializable transaction的一種實現協議，和基於lock的、基於MVCC啥的並列，就可以了。解釋：provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point between its invocation and its response, implying that the meaning of a concurrent object's operations can be given by pre- and post-conditions.
2. 一個paxos group內的leader通過投票選出來，通過不停的延長lease繼續擔當leader的角色，文中提到paxos group內任何兩個paxos leader必須保證disjointness invariant，這是為什麼呢？因為每個leader都要給自己這個group內執行的transaction分配一個timestamp, 如果兩個leader的interval有重疊，那麼就不能保證所有leader在分配timestamp時候全局單調遞增。其實就是說，咱們倆一人一個時間段，這個時間段內的時間點隨便我們分配，隻要我們各自保證分配的時間單調遞增，則咱倆都是單調遞增的。
3. 文中一堆時間，簡單抽象一下就是：spanner不依靠事件通信來保證transaction一致性，而是依靠嚴格的時間序列。
一個極端簡單的例子：某個partition內部最新commit的一個transaction的完成時間是3點，當前還有兩個transaction繼續在執行，不知道什麼時候結束，那麼如果這時候有一個讀請求過來，那麼我們隻能認讓這個讀的請求看到(visible)3點之前的數據，因為3點之後的數據可能隻寫了一半，是不允許讀的。那麼文中那麼多的時間序列和假設就是為了保證讀請求過來的時候，我們能準確的找到3點這個數字。很容易？如果是單機當然容易，如果有一堆機器參與了分布式transaction，找到3這個數字並不是輕而易舉。
4. 幾種操作
讀寫操作：最典型的操作，基於鎖的並發控製，隻不過使用樂觀鎖，如果出現衝突，某些低優先級的transaction先終止（係統會自動再重試），高優先級的先完成。在準備寫之前，依然是決定timestamp，如果不是分布式transaction，則自己選一個時間就可以了；如果是分布式transaction，則同時收取所有participant的建議，選一個最大的，再跟cooperator自己的now比較選個大的，繼續向下進行。
隻讀操作：跟上麵舉的例子類似，就是找個最近剛commit的transaction的時間點，然後返回該時間點之前寫入的數據。值得注意的是，這時候，因為所有的replica都已經完成了寫入，所以該時間點隻要找到了之後，可以隨便挑一個replica進行讀。
SnapshotRead：這就不用說了，時間點都省的找了，client會提供；不過如果client提供的時間點還未到來呢？根據係統實現可以選擇報錯或者block，不過我想報錯更合理吧，讀取未來數據的業務沒見過。
這部分transaction看起來複雜，因為主要是細節問題，宏觀問題都是清楚明白的。
不得不說，Google的創新力很可怕，Spanner恐怕兩年內不會有開源的實現，因為其不僅依靠軟件、而且依靠硬件，更主要的是，開源界可能沒有那麼緊迫的需求推動。
逐步搬之前的文章過來：https://www.cnblogs.com/raymondshiquan/articles/2697956.html
[1] Bigtable: A Distributed Storage System for Structured Data
[2] jeff notes 2009
[3] Spanner
最後更新：2017-04-01 13:38:49