本博客在http://doc001.com/同步更新谷羞。
本文主要內(nèi)容翻譯自MySQL開發(fā)者Ulf Wendel在PHP Submmit 2013上所做的報(bào)告「Scaling database to million of nodes」前普。翻譯過程中沒有全盤照搬原PPT，按照自己的理解進(jìn)行了部分改寫摊腋。水平有限，如有錯(cuò)誤和疏漏，歡迎指正霎桅。
本文是系列的第四篇内贮，本系列所有文章如下：
- 百萬節(jié)點(diǎn)數(shù)據(jù)庫擴(kuò)展之道(4): Google Spanner
Google Spanner
概述
Google Spanner是繼承自Bigtable的全球分布式數(shù)據(jù)庫成艘。
Bigtable之后，Google設(shè)計(jì)了MegaStore贺归。MegaStore構(gòu)建在Bigtable之上淆两，提供數(shù)據(jù)中心間的同步、強(qiáng)一致性的副本拂酣，它還進(jìn)一步提供了事務(wù)支持和SQL查詢語言秋冰。MegaStore很快變得很流行，開發(fā)者們顯然很喜歡這種跨數(shù)據(jù)中心的一致性保證婶熬，盡管副本同步并不是很快剑勾。這導(dǎo)致Google進(jìn)一步開發(fā)了Spanner。Spanner首先被應(yīng)用于F1廣告系統(tǒng)赵颅。在這之前虽另，F(xiàn)1使用的是MySQL數(shù)據(jù)庫。MySQL的分區(qū)過于復(fù)雜饺谬，且副本數(shù)據(jù)同步是異步進(jìn)行的捂刺，很難故障轉(zhuǎn)移。
Spanner有以下特征：
- 分布式鍵值存儲(chǔ)
- 分布式多維映射表：(key[,timestamp]) -> string
- 格式化的半關(guān)系表
- ACID事務(wù)
- 聲明式SQL查詢語言
- MapReduce
- 獨(dú)一無二的TrueTime API
- 跨數(shù)據(jù)中心的同步副本
系統(tǒng)視圖
一個(gè)Spanner部署稱為一個(gè)宇宙(universe)。universe monitor負(fù)責(zé)監(jiān)控和調(diào)試系統(tǒng)族展。
一個(gè)universe包含很多地區(qū)(zone)森缠。zone是物理隔離的單位，每一個(gè)數(shù)據(jù)中心可以有一個(gè)或多個(gè)zone仪缸，副本操作在zone之間進(jìn)行贵涵。
每一個(gè)zone由一個(gè)zone master和100~1000個(gè)span server組成。zone master有一個(gè)熱備恰画。
客戶端向位置代理(location proxy)查詢數(shù)據(jù)宾茂。
GFS分布式文件系統(tǒng)被Colossus取代。一個(gè)安置驅(qū)動(dòng)(placement driver)負(fù)責(zé)均衡數(shù)據(jù)拴还。
分層數(shù)據(jù)模型
在分布式系統(tǒng)中刻炒，join操作代價(jià)昂貴。受限于物理規(guī)律自沧，再精細(xì)的查詢優(yōu)化也無法避免join操作中的網(wǎng)絡(luò)數(shù)據(jù)傳輸坟奥。在全球分布式數(shù)據(jù)庫中，大量數(shù)據(jù)的傳輸代價(jià)更是極度昂貴拇厢。因此爱谁，節(jié)點(diǎn)之間巧妙的位置協(xié)調(diào)是必須的，兩個(gè)經(jīng)常關(guān)聯(lián)的表在物理上應(yīng)該存儲(chǔ)在一起孝偎，以較少甚至消除join操作的網(wǎng)絡(luò)通信代價(jià)访敌。
為了做到這點(diǎn)，Spanner中可以將關(guān)聯(lián)的兩個(gè)表定義為一個(gè)父表和一個(gè)派生表衣盾，派生表必須將父表的主鍵作為它自己主鍵的前綴寺旺。下圖的例子中，就定義了一個(gè)父表——用戶表和一個(gè)派生表——專輯表势决。
子表和目錄
由于Spanner和Bigtable一樣阻塑，按照行健存儲(chǔ)數(shù)據(jù)，前綴的trick能夠保證父表和派生表的關(guān)聯(lián)記錄在物理存儲(chǔ)層面上緊挨在一起果复。例如陈莽，uid = 1的用戶表行后緊跟著所有uid = 1的專輯表行。這使得join操作被轉(zhuǎn)化為更廉價(jià)的磁盤掃描操作虽抄。
Spanner分區(qū)數(shù)據(jù)時(shí)充分尊重?cái)?shù)據(jù)模型中的分級(jí)結(jié)構(gòu)走搁。這些分區(qū)被稱之為目錄(directory)。負(fù)載均衡和數(shù)據(jù)分布以目錄為基礎(chǔ)迈窟。
每一個(gè)子表(tablet)是目錄的容器私植，包含多個(gè)頻繁一起訪問的目錄。注意车酣，這里的tablet概念不同于Bigtable中的tablet曲稼。
ACID事務(wù)完全支持
Spanner除支持快照讀外索绪，還支持ACID事務(wù)讀寫操作!!!所有的讀操作都是非阻塞、無鎖的躯肌。讀操作使用了多版本技術(shù)者春，版本號(hào)就是時(shí)鐘時(shí)間破衔。
寫操作使用兩階段鎖(后面會(huì)說明)清女。這個(gè)選擇有利于MapReduce作業(yè)。純粹的多版本并發(fā)控制機(jī)制難以處理長時(shí)間運(yùn)行的事務(wù)晰筛。因?yàn)槠潋?yàn)證操作發(fā)生在事務(wù)結(jié)束時(shí)嫡丙，想象一些，你運(yùn)行了10分鐘的MapReduce作業(yè)读第，在完成時(shí)才看到?jīng)_突曙博，心里肯定會(huì)F**K...
TrueTime
想象一下，你正在運(yùn)行一個(gè)廣告系統(tǒng)怜瞒，該系統(tǒng)有一張競價(jià)表和一張點(diǎn)擊表父泳。為了提高性能，你應(yīng)該將點(diǎn)擊表按照區(qū)域進(jìn)行分區(qū)吴汪。來自歐洲用戶的點(diǎn)擊應(yīng)該被歐洲的服務(wù)器記錄惠窄，同理，美國用戶的點(diǎn)擊應(yīng)該被美國的服務(wù)器記錄漾橙。
進(jìn)一步杆融，我們構(gòu)造一個(gè)兩個(gè)事務(wù)需要被正確排序的場景。這兩個(gè)事務(wù)在不同的大陸由不同的服務(wù)器執(zhí)行霜运。第一個(gè)事務(wù)新建了一個(gè)競價(jià)脾歇，第二個(gè)事務(wù)記錄這個(gè)競價(jià)的一次點(diǎn)擊。緊接著淘捡，第三個(gè)事務(wù)需要去讀取第二個(gè)事務(wù)的結(jié)果藕各，顯然它也需要知道第一個(gè)事務(wù)的結(jié)果。因此焦除，這些事務(wù)的順序必須是一定的座韵，只能是事務(wù)一、事務(wù)二踢京、事務(wù)三誉碴，不能亂套。
在Dynamo中瓣距，我們無法簡單地使用墻上時(shí)間(wall clock)黔帕，因?yàn)檫@些時(shí)間并不是完全同步的。Dynamo為此選擇了向量鐘蹈丸。
向量鐘的問題在于它們必須被每一個(gè)消息捎帶成黄，以檢測依賴關(guān)系呐芥，在這個(gè)場景中是這樣的：
- 事務(wù)T1執(zhí)行，競價(jià)在美國的服務(wù)器被創(chuàng)建
- 廣告出現(xiàn)奋岁，用戶在歐洲點(diǎn)擊廣告
瀏覽器中的廣告必須包含T1的向量鐘
JavaScript點(diǎn)擊記錄必須將向量鐘發(fā)送給歐洲服務(wù)器的數(shù)據(jù)庫 - 歐洲服務(wù)器使用事務(wù)T2寫入點(diǎn)擊信息
數(shù)據(jù)庫將T2思瘟、T1的向量鐘、自己的向量鐘一起存儲(chǔ) - 讀取T2事務(wù)也必須讀取T1事務(wù)結(jié)果闻伶，因?yàn)門1發(fā)生在T2前
數(shù)據(jù)庫必須檢查向量鐘之間的關(guān)系
你會(huì)發(fā)現(xiàn)滨攻，到處都是向量鐘，整個(gè)過程的向量鐘處理不能有一丁點(diǎn)出錯(cuò)蓝翰。太糟糕了光绕！
由于向量鐘存在的問題，Google決定承擔(dān)同步墻上時(shí)間的代價(jià)畜份。如果墻上時(shí)間是單調(diào)遞增(不允許出現(xiàn)跳躍)诞帐、全球可用的，那它可以被用于在全球范圍內(nèi)可靠地序列化事務(wù)爆雹。為了做到這一點(diǎn)停蕉，Google綜合使用GPS和原子時(shí)鐘開發(fā)了TrueTime服務(wù)，能夠給出精確時(shí)間的精準(zhǔn)估計(jì)钙态。
TrueTime接口并不返回一個(gè)準(zhǔn)確的時(shí)間慧起，相反，返回一個(gè)準(zhǔn)確時(shí)間的估計(jì)范圍驯绎。這個(gè)時(shí)間誤差在0~6ms間完慧，90%的情況下小于2ms。
Spanner提供三個(gè)TrueTime接口：
- $TT.now()$：準(zhǔn)確時(shí)間的估計(jì)區(qū)間[earliest,latest]
- $TT.after(t)$：如果t肯定已經(jīng)過去了剩失，返回真
- $TT.before(t)$：如果t時(shí)間還未到來屈尼，返回真
使用函數(shù)$t_{abs}(e)$標(biāo)示事件e的絕對時(shí)間。TrueTime可以保證拴孤，對于一個(gè)調(diào)用$tt=TT.now()$脾歧，有$tt.earliest≤tabs(e_{now})≤tt.latest$，其中演熟，e_{now}是現(xiàn)在調(diào)用的事件鞭执。
TrueTime在底層使用了GPS和原子時(shí)鐘。TrueTime使用兩種形式的計(jì)時(shí)方式是因?yàn)樗鼈冇胁煌氖∧Ｊ矫⒋狻PS參考時(shí)間會(huì)受到天線兄纺、接收器失效等因素的影響。原子時(shí)鐘與GPS化漆、其它原子時(shí)鐘無關(guān)估脆，但是頻率錯(cuò)誤可能導(dǎo)致長時(shí)間的時(shí)間偏移。
TrueTime由每個(gè)數(shù)據(jù)中心的一組time master機(jī)器和每個(gè)機(jī)器上的timeslave saemon組成座云。大部分time master裝有專用天線的GPS疙赠，其它的time master(Armageddon master)裝備有原子時(shí)鐘付材。所有master的時(shí)間參考值都會(huì)進(jìn)行彼此校對。每個(gè)master也會(huì)交叉檢查時(shí)間參考值和本地時(shí)間的比值圃阳，如果二者差別太大厌衔，就會(huì)把自己驅(qū)逐出系統(tǒng)。在同步期間捍岳，Armageddon master會(huì)表現(xiàn)出一個(gè)逐漸增加的時(shí)間不確定性富寿，這是由時(shí)鐘漂移引起的。而GPS master表現(xiàn)出的時(shí)間不確定性幾乎接近于0祟同。
每個(gè)機(jī)器使用一個(gè)本地的daemon從多個(gè)master校時(shí)作喘，部分GPS master選自較遠(yuǎn)的數(shù)據(jù)中心理疙，部分選擇附近的數(shù)據(jù)中心晕城，部分來自Armageddon master。為了受到錯(cuò)誤的本地時(shí)鐘干擾窖贤，那些時(shí)間誤差頻繁高于容忍限度的機(jī)器將會(huì)被系統(tǒng)驅(qū)逐砖顷。
在兩次同步期間，一個(gè)daemon也會(huì)表現(xiàn)出逐漸增加的時(shí)間不確定性赃梧。本身deamon校準(zhǔn)得到是一個(gè)時(shí)間范圍滤蝠，而deamon以最壞的情況估計(jì)時(shí)間，所以授嘀，時(shí)間范圍不斷在擴(kuò)大物咳。
兩階段提交(two-phase commit，2PC)
Spanner的事務(wù)提交機(jī)制與2PC類似蹄皱。2PC是一個(gè)分布式事務(wù)提交協(xié)議览闰，包含準(zhǔn)備、提交/終止兩個(gè)階段巷折。
考慮一個(gè)多節(jié)點(diǎn)參與的事務(wù)压鉴。為了決定事務(wù)的結(jié)果，協(xié)調(diào)者(coordinator)發(fā)送一個(gè)準(zhǔn)備請求給所有的參與者锻拘。參與者分別檢查它們可以提交事務(wù)油吭，還是需要終止事務(wù)。一旦參與者做出可以提交的決定署拟，就回復(fù)可以提交婉宰，同時(shí)進(jìn)入準(zhǔn)備提交狀態(tài)，這個(gè)狀態(tài)就是不可逆轉(zhuǎn)的推穷。理想情況下心包，所有參與者都回復(fù)說可以提交，然后協(xié)調(diào)者就發(fā)送一個(gè)全局提交消息缨恒；否則谴咸，就發(fā)送全局終止消息轮听。這就是2PC的執(zhí)行過程。
2PC是一個(gè)阻塞協(xié)議岭佳，在異步環(huán)境下會(huì)導(dǎo)致很多問題血巍。
最嚴(yán)重的情況就是協(xié)調(diào)者在所有參與者都進(jìn)入準(zhǔn)備提交狀態(tài)后崩潰了。參與者們在協(xié)調(diào)者恢復(fù)之前無法離開準(zhǔn)備提交狀態(tài)珊随，因?yàn)樗鼈儾恢雷罱K的決定是提交還是終止述寡。并且，沒有一個(gè)參與者收到了投票結(jié)果叶洞，因此鲫凶，也無法互相通信進(jìn)行詢問。
2PC的一個(gè)改進(jìn)協(xié)議是三階段提交(three-phase commit衩辟，3PC)螟炫。3PC為事務(wù)設(shè)置了一個(gè)超時(shí)時(shí)間，超過這個(gè)時(shí)間直接終止事務(wù)艺晴。
寫事務(wù)
Spanner使用TrueTime和Paxos對2PC進(jìn)行了改進(jìn)昼钻。寫事務(wù)的流程如下：
- 請求鎖
- 執(zhí)行讀操作，和幻影寫(即先寫數(shù)據(jù)但不提交)
- 獲取事務(wù)啟動(dòng)時(shí)間$ctime_{now}=TT.now()=[t_{earliest},t_{latest}]$
- 使用Paxos多副本寫
- 等待封寞，直到$t_{latest}<TrueTime.now()$
- 確認(rèn)提交
- 執(zhí)行寫操作
- 釋放鎖
當(dāng)一個(gè)寫事務(wù)啟動(dòng)然评，它會(huì)對獲取一些鎖，然后才進(jìn)行讀寫狈究。Spanner為事務(wù)獲取一個(gè)啟動(dòng)時(shí)間戳的估計(jì)范圍碗淌。寫操作使用Paxos來寫多個(gè)副本。如果一切順利抖锥，再次檢查時(shí)間亿眠，一直等待到估計(jì)的啟動(dòng)時(shí)間肯定過去了，才能確認(rèn)提交宁改。通常情況下缕探，同步副本變化的時(shí)間肯定要比啟動(dòng)事件戳的估計(jì)范圍要長，因此还蹲，實(shí)際上Spanner很少等待爹耗。這個(gè)設(shè)計(jì)其實(shí)保證了，同一個(gè)時(shí)間只存在一個(gè)事務(wù)提交數(shù)據(jù)谜喊，所有事務(wù)的提交時(shí)間嚴(yán)格遞增潭兽。
另外一點(diǎn)就是，這個(gè)2PC運(yùn)行在Paxos之上斗遏。Paxos至少需要三個(gè)節(jié)點(diǎn)才能達(dá)成提議山卦，因此該系統(tǒng)至少有三個(gè)副本。既然Paxos能自動(dòng)處理故障诵次，2PC也不再需要額外的故障處理協(xié)議账蓉。Paxos最多能夠承受1/3的節(jié)點(diǎn)失敗枚碗，不超過這個(gè)數(shù)量，2PC不會(huì)阻塞铸本。
寫事務(wù)執(zhí)行的系統(tǒng)視圖
2PC中最棘手的問題是coordinator失敗肮雨。在Spanner中，客戶端充當(dāng)了coordinator的角色箱玷。
在一個(gè)寫事務(wù)的開始怨规，客戶端將讀請求發(fā)送給tablet的leader，這個(gè)leader是Paxos選舉出來的锡足。每一個(gè)tablet的副本是一個(gè)paxos組波丰。leader獲取必要的鎖，然后客戶端執(zhí)行讀操作舶得。
每一個(gè)span server包含一個(gè)participant leader組件掰烟，該組件和客戶端交換心跳信息。
當(dāng)客戶端準(zhǔn)備提交數(shù)據(jù)扩灯，就發(fā)起2PC媚赖，并成為coordinator霜瘪。
如果客戶端未成功發(fā)送keep alive消息珠插，就可以認(rèn)為coordinator已經(jīng)失效，participant leader介入颖对，解決阻塞捻撑。
更多詳細(xì)的細(xì)節(jié)請參見Spanner論文。
總結(jié)
Spanner并沒有打破CAP理論缤底，但是證明了顾患，正確的工程設(shè)計(jì)能夠?qū)⒚黠@地推進(jìn)CAP的邊界，做到一致性个唧、可用性和足夠的分區(qū)容忍性江解。
Spanner實(shí)現(xiàn)的CAP程度如下(強(qiáng)>高>好)：
- 一致性
- 強(qiáng)：顯式同步副本
- 強(qiáng)：ACID事務(wù)
- 強(qiáng)：使用了Colossus文件系統(tǒng)
- 可用性
- 高：跨數(shù)據(jù)中心備份
- 高：可以實(shí)現(xiàn)全球分布
- 高：單分區(qū)副本延時(shí)性能很好
- 好：分區(qū)數(shù)高達(dá)50時(shí)延時(shí)仍然在可接受范圍內(nèi)
- 分區(qū)容忍性
- 高：Paxos
- 高：會(huì)話亞協(xié)議(session sub protocol)
未完待續(xù)...
接下來將是本系列的最后一篇，參見：
