簡介
傳統(tǒng)數(shù)據(jù)庫已無法滿足大規(guī)模數(shù)據(jù)的需求。傳統(tǒng)的解決方案是分片，事務(wù)只能局限在一個分片節(jié)點。且通常需要人工維護。分片的方式會有成百上千個節(jié)點，節(jié)點數(shù)量多導(dǎo)致小概率事件變成大概率事件。因此需要實現(xiàn)高可用性和錯誤容忍。一個解決方案是使用同步備份策略（一個主多從，寫數(shù)據(jù)需要從機確認(rèn)后才能返回寫成功）。然而這種策略在有些場景下會失去一致性。
1. 傳統(tǒng)策略的問題
1.1 傳統(tǒng)同步備份的問題
傳統(tǒng)的兩路同步備份思路，
同步一主機一從機，寫確認(rèn)需要從機確認(rèn)。如果從機宕機，主機繼續(xù)提供服務(wù)；如果主機宕機，則從機一定處于最新的狀態(tài)，因此可以由從機繼續(xù)提供服務(wù)。
使得這種模式出現(xiàn)不一致的場景：
- 主機接受命令m1， 從機接受命令m1
- 從機失敗，主機繼續(xù)工作
- 主機接受命令m2
- 在主機將m2復(fù)制到從機之前，主機宕機，同時從機恢復(fù)
- 此時只有一臺機器處于宕機狀態(tài)（主機），但由于主機已經(jīng)接受的命令沒有
拷貝到從機，從機不能接受命令。
同步一主兩從，假定有三個節(jié)點A，B，C
假定有以下命令序列[1,2,3], 三個節(jié)點狀態(tài)按如下順序變化
1 1 1 (A，B，C均正常服務(wù))
2 2 1（A， B正常，C宕機）
3 2 1 （A正常，B宕機，C恢復(fù)，命令未完成復(fù)制）
3 2 1 （A宕機，B恢復(fù)，C恢復(fù)）此時無法接受命令，雖然只有一個節(jié)點處于宕機狀態(tài)。
多機一致性的問題研究了近30年，Paxos協(xié)議家族目前被認(rèn)為是唯一保證了正確性的協(xié)議，它能保證在有2F+1個節(jié)點時，能夠容忍F個節(jié)點宕機（少數(shù)）。然而，Paxos算法還沒有被應(yīng)用在數(shù)據(jù)庫的復(fù)制中，因為通常認(rèn)為它太復(fù)雜并且很慢。(本文發(fā)表于2011年，貌似阿里的oceanbase中是使用Paxos協(xié)議來實現(xiàn)數(shù)據(jù)庫備份)。
1.2 強一致性 vs 最終一致性
強一致性是指所有副本都對應(yīng)用表現(xiàn)的完全一致。然而根據(jù)CAP理論，強一致性跟可用性和網(wǎng)絡(luò)分區(qū)容忍不能共存。
數(shù)據(jù)庫系統(tǒng)如Dynamo使用了最終一致性模型，客戶端可能會看到多個不同舊版本的數(shù)據(jù)，作為結(jié)果，客戶端需要自己處理好沖突檢查。我們所熟悉的數(shù)據(jù)庫ACID事務(wù)并不被支持。
盡管有些系統(tǒng)可以接受最終一致性，但是大部分應(yīng)用仍然需要強一致性的保障。并且需要有一定的事務(wù)支持。
在單數(shù)據(jù)中心中，網(wǎng)絡(luò)分區(qū)現(xiàn)象很少見。因此選擇CA可能比選擇AP+最終一致性更合適。
1.3 Spinnaker
基于key的range partitioning
3路副本
帶事務(wù)的get-put,可選強一致或time-line一致性（取舍：提高性能，允許可能返回舊版本數(shù)據(jù)）
使用Paxos確保大多數(shù)節(jié)點存活時的可用性
在CAP中選擇CA
2. 相關(guān)工作
2.1 兩階段提交
2PC允許每一個參與者都是一個獨立的資源管理器
缺陷：
一個節(jié)點失敗會導(dǎo)致全局失敗
每一個事務(wù)都需要2PC會導(dǎo)致性能很差
2PC有coordinator角色，當(dāng)coordinator宕機時會阻塞。3PC是非阻塞的，但是因為性能差很少再實踐中使用。
3 數(shù)據(jù)模型和API
數(shù)據(jù)模型
類似多版本關(guān)系數(shù)據(jù)庫。表+行。每個column有對應(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分片，每個分片默認(rèn)3個副本分布在不同的節(jié)點
4.1 節(jié)點架構(gòu)
每個節(jié)點包含多個組件，且每個組件都是線程安全的。
每一條log由LSN唯一標(biāo)志
commit queue位于內(nèi)存，log只有在多數(shù)節(jié)點確認(rèn)時才能提交，在此期間它們存儲在commit queue中。
committed log存儲結(jié)構(gòu)：memtable + SSTable(GFS)
4.2 Zookeeper
提供錯誤容忍，分布式協(xié)調(diào)服務(wù)
5 副本協(xié)議
每個分片有一個Leader，兩個Follower
協(xié)議有兩個階段：Leader選舉階段和投票提交階段，Leader提議Follower投票。在沒有出現(xiàn)錯誤的情況下（服務(wù)器宕機，網(wǎng)絡(luò)分片等），Leader不需要改變，只需要執(zhí)行投票階段。
當(dāng)客戶端需要寫數(shù)據(jù)時，總是會被路由到Leader（只有一個節(jié)點寫數(shù)據(jù)）。
Leader將寫命令A(yù)ppend到commit queue中。持久化到硬盤。
Leader發(fā)起提議，
Follower接收到提議，持久化log，將命令放到commit queue。返回ACK
Leader接收到多數(shù)人的ACK，此時可以確認(rèn)commit->將命令應(yīng)用到memtable。
Leader階段性的發(fā)送異步的commit message給follower，follower相應(yīng)的將寫命令應(yīng)用到memtable。
強一致性讀需要從Leader讀，timeline 一致性讀可以從副本中讀取。
6. 恢復(fù)
6.1 Follower恢復(fù)
Follower恢復(fù)有兩個階段。
- 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因為磁盤錯誤丟失了所有的數(shù)據(jù)，那么Follower直接進入Catch Up階段。
在Catch Up階段，F(xiàn)ollower告訴Leader它的f.cmt的值，Leader將Follower缺的f.cmt之后的所有l(wèi)og發(fā)回Follower。在catch up的最終階段，Leader會臨時的阻塞寫操作，從而確保Follower能完整的catch up。
在實踐中，Leader由于會執(zhí)行l(wèi)og壓縮，從而有些Follower需要的log記錄已經(jīng)不能獲得。此時的處理是直接將合適的SSTable發(fā)送給Follower，并從SSTable記錄開始恢復(fù)。
當(dāng)選出新的Leader的時候，f.cmt之后的有些記錄可能并沒有被Leader Apply，因此這些記錄需要丟棄。那么是否可以直接截斷f.cmt之后的log呢？答案是不能。
原因是這些log可能屬于不同的分片。
6.2 Leader 接管
新Leader選舉時會確保新的Leader包含了所有的舊Leader已經(jīng)commit的log。這一點會在第七節(jié)介紹。
舊Leader恢復(fù)時需要執(zhí)行Follower恢復(fù)流程。
新Leader需要為舊Leader發(fā)送那些已經(jīng)被commit但是commit message還沒有
發(fā)送的commit的commit message。使用如下算法。
7 Leader選舉
Leader選舉會在一個分片的Leader出錯時發(fā)生。
Leader選舉必須達成共識只有一個Leader。
Leader選舉必須保證選舉出來的Leader必須擁有所有的已經(jīng)commit的log。
7.1 Zookeeper 數(shù)據(jù)模型和API簡介
Zookeeper的數(shù)據(jù)模型類似文件系統(tǒng)中的目錄樹。每一個節(jié)點由其路徑標(biāo)志。
舉個例子 /a/b/c。每一個znode節(jié)點可以設(shè)置關(guān)聯(lián)數(shù)據(jù)。
客戶端可以創(chuàng)建或刪除znode節(jié)點。
znode節(jié)點可以是持久化的節(jié)點或臨時節(jié)點。當(dāng)客戶端斷開鏈接時，Zookeeper會自動刪除臨時節(jié)點，而持久化的節(jié)點需要客戶端顯式刪除。znode可以包含一個連續(xù)屬性，從而允許唯一性，單調(diào)性的需求。
znode提供了watcher，客戶端可以監(jiān)聽znode或者其children的事件。
7.2 Leader選舉協(xié)議
每一個Spinner的節(jié)點都包含了一個Zookeeper的客戶端，用于實現(xiàn)Leader的選舉。
r代表分片的范圍（比如圖2中的[1, 199]）
選舉r分片所需的信息會存儲的Zookeeper的/r目錄
首先清除所有的前一次選舉的狀態(tài)信息
然后，每一個節(jié)點都宣稱自己是備選人(candidate)，使用自己的n.lst，創(chuàng)建在/r/candidates目錄下。
然后給目錄/r/candidates設(shè)置一個watcher，一旦目錄信息發(fā)生變化通知分片節(jié)點。
當(dāng)大多數(shù)節(jié)點的信息出現(xiàn)在此目錄時。即可選出新Leader，選舉規(guī)則是哪個的n.lst最大就選哪個。
然后新Leader將其host信息寫入/r/leader,并執(zhí)行Leader 接管算法。
使用臨時的節(jié)點可以應(yīng)對新選出來的Leader潛在的可能出錯。
最終，所有的Follower從/r/leader中讀取leader信息。
這個算法是可以保證
- 所有節(jié)點對Leader達成共識
- 新的Leader擁有所有舊的Leader已經(jīng)commit的log
第一條很顯然。
第二條依賴的就是兩個多數(shù)人的集合必然有交集。舊Leader已經(jīng)commit的log必然在新Leader的candidate目錄中必然至少有一個包含了舊Leader所有的commit log。而選擇的新Leader擁有最大的lst，因此新Leader log要么就是至少的那一個，要么比至少的那一個還要長。于是可以得出結(jié)論新的Leader必然包含了所有已經(jīng)commit的log。
8 可用性和持久性保障
對于三路復(fù)制。
寫操作至少需要兩個節(jié)點存活。
強一致讀需要重定向到Leader節(jié)點，也至少需要兩個節(jié)點存活。
timeline一致性允許讀到舊數(shù)據(jù)，只要有一個節(jié)點存活即可。
