簡介
傳統(tǒng)數(shù)據(jù)庫已無法滿足大規(guī)模數(shù)據(jù)的需求嗤攻。傳統(tǒng)的解決方案是分片，事務(wù)只能局限在一個(gè)分片節(jié)點(diǎn)诽俯。且通常需要人工維護(hù)妇菱。分片的方式會(huì)有成百上千個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)量多導(dǎo)致小概率事件變成大概率事件闯团。因此需要實(shí)現(xiàn)高可用性和錯(cuò)誤容忍房交。一個(gè)解決方案是使用同步備份策略（一個(gè)主多從伐割，寫數(shù)據(jù)需要從機(jī)確認(rèn)后才能返回寫成功）隔心。然而這種策略在有些場景下會(huì)失去一致性硬霍。
1. 傳統(tǒng)策略的問題
1.1 傳統(tǒng)同步備份的問題
傳統(tǒng)的兩路同步備份思路唯卖，
同步一主機(jī)一從機(jī)拜轨，寫確認(rèn)需要從機(jī)確認(rèn)。如果從機(jī)宕機(jī)卵沉，主機(jī)繼續(xù)提供服務(wù)偎箫；如果主機(jī)宕機(jī)淹办，則從機(jī)一定處于最新的狀態(tài)怜森，因此可以由從機(jī)繼續(xù)提供服務(wù)。
使得這種模式出現(xiàn)不一致的場景：
- 主機(jī)接受命令m1姥宝， 從機(jī)接受命令m1
- 從機(jī)失敗腊满，主機(jī)繼續(xù)工作
- 主機(jī)接受命令m2
- 在主機(jī)將m2復(fù)制到從機(jī)之前碳蛋，主機(jī)宕機(jī)肃弟，同時(shí)從機(jī)恢復(fù)
- 此時(shí)只有一臺(tái)機(jī)器處于宕機(jī)狀態(tài)（主機(jī)）零蓉，但由于主機(jī)已經(jīng)接受的命令沒有
拷貝到從機(jī)，從機(jī)不能接受命令箩兽。
同步一主兩從比肄，假定有三個(gè)節(jié)點(diǎn)A囊陡，B撞反，C
假定有以下命令序列[1,2,3], 三個(gè)節(jié)點(diǎn)狀態(tài)按如下順序變化
1 1 1 (A遏片，B吮便，C均正常服務(wù))
2 2 1（A髓需， B正常房蝉，C宕機(jī)）
3 2 1 （A正常微渠，B宕機(jī)逞盆，C恢復(fù)云芦，命令未完成復(fù)制）
3 2 1 （A宕機(jī)焕数，B恢復(fù)堡赔，C恢復(fù)）此時(shí)無法接受命令善已，雖然只有一個(gè)節(jié)點(diǎn)處于宕機(jī)狀態(tài)离例。
多機(jī)一致性的問題研究了近30年，Paxos協(xié)議家族目前被認(rèn)為是唯一保證了正確性的協(xié)議艘包，它能保證在有2F+1個(gè)節(jié)點(diǎn)時(shí)想虎，能夠容忍F個(gè)節(jié)點(diǎn)宕機(jī)（少數(shù)）舌厨。然而裙椭，Paxos算法還沒有被應(yīng)用在數(shù)據(jù)庫的復(fù)制中揉燃，因?yàn)橥ǔＵJ(rèn)為它太復(fù)雜并且很慢炊汤。(本文發(fā)表于2011年，貌似阿里的oceanbase中是使用Paxos協(xié)議來實(shí)現(xiàn)數(shù)據(jù)庫備份)拨拓。
1.2 強(qiáng)一致性 vs 最終一致性
強(qiáng)一致性是指所有副本都對(duì)應(yīng)用表現(xiàn)的完全一致渣磷。然而根據(jù)CAP理論醋界，強(qiáng)一致性跟可用性和網(wǎng)絡(luò)分區(qū)容忍不能共存形纺。
數(shù)據(jù)庫系統(tǒng)如Dynamo使用了最終一致性模型徒欣，客戶端可能會(huì)看到多個(gè)不同舊版本的數(shù)據(jù)，作為結(jié)果脂新，客戶端需要自己處理好沖突檢查粗梭。我們所熟悉的數(shù)據(jù)庫ACID事務(wù)并不被支持滞乙。
盡管有些系統(tǒng)可以接受最終一致性斩启，但是大部分應(yīng)用仍然需要強(qiáng)一致性的保障躬窜。并且需要有一定的事務(wù)支持荣挨。
在單數(shù)據(jù)中心中默垄，網(wǎng)絡(luò)分區(qū)現(xiàn)象很少見口锭。因此選擇CA可能比選擇AP+最終一致性更合適韭寸。
1.3 Spinnaker
基于key的range partitioning
3路副本
帶事務(wù)的get-put,可選強(qiáng)一致或time-line一致性（取舍：提高性能荆隘，允許可能返回舊版本數(shù)據(jù)）
使用Paxos確保大多數(shù)節(jié)點(diǎn)存活時(shí)的可用性
在CAP中選擇CA
2. 相關(guān)工作
2.1 兩階段提交
2PC允許每一個(gè)參與者都是一個(gè)獨(dú)立的資源管理器
缺陷：
一個(gè)節(jié)點(diǎn)失敗會(huì)導(dǎo)致全局失敗
每一個(gè)事務(wù)都需要2PC會(huì)導(dǎo)致性能很差
2PC有coordinator角色晶渠，當(dāng)coordinator宕機(jī)時(shí)會(huì)阻塞褒脯。3PC是非阻塞的番川，但是因?yàn)樾阅懿詈苌僭賹?shí)踐中使用颁督。
3 數(shù)據(jù)模型和API
數(shù)據(jù)模型
類似多版本關(guān)系數(shù)據(jù)庫适篙。表+行嚷节。每個(gè)column有對(duì)應(yīng)的verison
table + row["key"]["column"]["version"]
客戶端API
get(key, column, consistent=strong/timeline)
put(key, colname, colvalue)
delete(key, colname)
conditionalPut(key, colname, value, v)
conditionalDelete(key, colname, v)
4 架構(gòu)
基于key range分片虎锚，每個(gè)分片默認(rèn)3個(gè)副本分布在不同的節(jié)點(diǎn)
4.1 節(jié)點(diǎn)架構(gòu)
每個(gè)節(jié)點(diǎn)包含多個(gè)組件效斑，且每個(gè)組件都是線程安全的缓屠。
每一條log由LSN唯一標(biāo)志
commit queue位于內(nèi)存敌完，log只有在多數(shù)節(jié)點(diǎn)確認(rèn)時(shí)才能提交滨溉，在此期間它們存儲(chǔ)在commit queue中闽撤。
committed log存儲(chǔ)結(jié)構(gòu)：memtable + SSTable(GFS)
4.2 Zookeeper
提供錯(cuò)誤容忍哟旗，分布式協(xié)調(diào)服務(wù)
5 副本協(xié)議
每個(gè)分片有一個(gè)Leader，兩個(gè)Follower
協(xié)議有兩個(gè)階段：Leader選舉階段和投票提交階段绎巨，Leader提議Follower投票场勤。在沒有出現(xiàn)錯(cuò)誤的情況下（服務(wù)器宕機(jī)和媳，網(wǎng)絡(luò)分片等），Leader不需要改變哈街，只需要執(zhí)行投票階段留瞳。
當(dāng)客戶端需要寫數(shù)據(jù)時(shí)，總是會(huì)被路由到Leader（只有一個(gè)節(jié)點(diǎn)寫數(shù)據(jù)）骚秦。
Leader將寫命令A(yù)ppend到commit queue中她倘。持久化到硬盤。
Leader發(fā)起提議作箍，
Follower接收到提議硬梁，持久化log，將命令放到commit queue胞得。返回ACK
Leader接收到多數(shù)人的ACK荧止，此時(shí)可以確認(rèn)commit->將命令應(yīng)用到memtable。
Leader階段性的發(fā)送異步的commit message給follower跃巡，follower相應(yīng)的將寫命令應(yīng)用到memtable递宅。
強(qiáng)一致性讀需要從Leader讀，timeline 一致性讀可以從副本中讀取。
6. 恢復(fù)
6.1 Follower恢復(fù)
Follower恢復(fù)有兩個(gè)階段。
- Local Recovery
- Catch Up
在Local Recovery階段，F(xiàn)ollower能從checkpoint開始，一直應(yīng)用到f.cmt來恢復(fù)memtable的狀態(tài)。f.cmt之后的log可能沒有被Leader commit汗茄，這些log在catch up階段恢復(fù)。如果Follower因?yàn)榇疟P錯(cuò)誤丟失了所有的數(shù)據(jù)纯趋，那么Follower直接進(jìn)入Catch Up階段西剥。
在Catch Up階段，F(xiàn)ollower告訴Leader它的f.cmt的值，Leader將Follower缺的f.cmt之后的所有l(wèi)og發(fā)回Follower。在catch up的最終階段，Leader會(huì)臨時(shí)的阻塞寫操作，從而確保Follower能完整的catch up。
在實(shí)踐中躏精，Leader由于會(huì)執(zhí)行l(wèi)og壓縮箩溃，從而有些Follower需要的log記錄已經(jīng)不能獲得霹陡。此時(shí)的處理是直接將合適的SSTable發(fā)送給Follower浆洗，并從SSTable記錄開始恢復(fù)。
當(dāng)選出新的Leader的時(shí)候买优，f.cmt之后的有些記錄可能并沒有被Leader Apply脂崔，因此這些記錄需要丟棄汇歹。那么是否可以直接截?cái)鄁.cmt之后的log呢痰哨？答案是不能撬讽。
原因是這些log可能屬于不同的分片。
6.2 Leader 接管
新Leader選舉時(shí)會(huì)確保新的Leader包含了所有的舊Leader已經(jīng)commit的log昧捷。這一點(diǎn)會(huì)在第七節(jié)介紹毒返。
舊Leader恢復(fù)時(shí)需要執(zhí)行Follower恢復(fù)流程歉眷。
新Leader需要為舊Leader發(fā)送那些已經(jīng)被commit但是commit message還沒有
發(fā)送的commit的commit message淡溯。使用如下算法。
7 Leader選舉
Leader選舉會(huì)在一個(gè)分片的Leader出錯(cuò)時(shí)發(fā)生琼了。
Leader選舉必須達(dá)成共識(shí)只有一個(gè)Leader。
Leader選舉必須保證選舉出來的Leader必須擁有所有的已經(jīng)commit的log毅戈。
7.1 Zookeeper 數(shù)據(jù)模型和API簡介
Zookeeper的數(shù)據(jù)模型類似文件系統(tǒng)中的目錄樹苇经。每一個(gè)節(jié)點(diǎn)由其路徑標(biāo)志。
舉個(gè)例子 /a/b/c。每一個(gè)znode節(jié)點(diǎn)可以設(shè)置關(guān)聯(lián)數(shù)據(jù)银受。
客戶端可以創(chuàng)建或刪除znode節(jié)點(diǎn)。
znode節(jié)點(diǎn)可以是持久化的節(jié)點(diǎn)或臨時(shí)節(jié)點(diǎn)鲜侥。當(dāng)客戶端斷開鏈接時(shí)互墓，Zookeeper會(huì)自動(dòng)刪除臨時(shí)節(jié)點(diǎn)必尼，而持久化的節(jié)點(diǎn)需要客戶端顯式刪除。znode可以包含一個(gè)連續(xù)屬性篡撵，從而允許唯一性判莉，單調(diào)性的需求。
znode提供了watcher育谬，客戶端可以監(jiān)聽znode或者其children的事件券盅。
7.2 Leader選舉協(xié)議
每一個(gè)Spinner的節(jié)點(diǎn)都包含了一個(gè)Zookeeper的客戶端，用于實(shí)現(xiàn)Leader的選舉膛檀。
r代表分片的范圍（比如圖2中的[1, 199]）
選舉r分片所需的信息會(huì)存儲(chǔ)的Zookeeper的/r目錄
首先清除所有的前一次選舉的狀態(tài)信息
然后锰镀，每一個(gè)節(jié)點(diǎn)都宣稱自己是備選人(candidate)，使用自己的n.lst咖刃，創(chuàng)建在/r/candidates目錄下泳炉。
然后給目錄/r/candidates設(shè)置一個(gè)watcher，一旦目錄信息發(fā)生變化通知分片節(jié)點(diǎn)僵缺。
當(dāng)大多數(shù)節(jié)點(diǎn)的信息出現(xiàn)在此目錄時(shí)胡桃。即可選出新Leader，選舉規(guī)則是哪個(gè)的n.lst最大就選哪個(gè)磕潮。
然后新Leader將其host信息寫入/r/leader,并執(zhí)行Leader 接管算法翠胰。
使用臨時(shí)的節(jié)點(diǎn)可以應(yīng)對(duì)新選出來的Leader潛在的可能出錯(cuò)。
最終自脯，所有的Follower從/r/leader中讀取leader信息之景。
這個(gè)算法是可以保證
- 所有節(jié)點(diǎn)對(duì)Leader達(dá)成共識(shí)
- 新的Leader擁有所有舊的Leader已經(jīng)commit的log
第一條很顯然。
第二條依賴的就是兩個(gè)多數(shù)人的集合必然有交集膏潮。舊Leader已經(jīng)commit的log必然在新Leader的candidate目錄中必然至少有一個(gè)包含了舊Leader所有的commit log锻狗。而選擇的新Leader擁有最大的lst，因此新Leader log要么就是至少的那一個(gè)，要么比至少的那一個(gè)還要長轻纪。于是可以得出結(jié)論新的Leader必然包含了所有已經(jīng)commit的log油额。
8 可用性和持久性保障
對(duì)于三路復(fù)制。
寫操作至少需要兩個(gè)節(jié)點(diǎn)存活刻帚。
強(qiáng)一致讀需要重定向到Leader節(jié)點(diǎn)潦嘶，也至少需要兩個(gè)節(jié)點(diǎn)存活。
timeline一致性允許讀到舊數(shù)據(jù)崇众，只要有一個(gè)節(jié)點(diǎn)存活即可掂僵。
