TIDB 架構(gòu)及分布式協(xié)議Paxos和Raft對(duì)比

近來(lái)newsql大熱，尤以TIDB最火，pingcap不斷打磨TiDB，現(xiàn)如今版本已經(jīng)迭代到3.0，產(chǎn)品已經(jīng)基本趨于成熟。
對(duì)于TiDB，整體架構(gòu)圖如下圖所示

是由四個(gè)模塊組成，TiDB Server，PD Server，TiKV Server，TiSpark。

• TiDB Server負(fù)責(zé)接受SQL請(qǐng)求，處理SQL的相關(guān)邏輯，并通過(guò)PD找到存儲(chǔ)計(jì)算所需數(shù)據(jù)的TiKV地址，與TiKV交互獲取數(shù)據(jù)，最終返回結(jié)果。TiDB Server是無(wú)狀態(tài)的，其本身并不存儲(chǔ)數(shù)據(jù)，只負(fù)責(zé)計(jì)算，可以無(wú)限水平擴(kuò)展，可以通過(guò)負(fù)載均衡組件（如LVD，HAPROXY，F(xiàn)5等）對(duì)外提供統(tǒng)一的接入地址。推薦部署倆個(gè)實(shí)例，前端通過(guò)負(fù)載均衡組件對(duì)外提供服務(wù)，當(dāng)單個(gè)實(shí)例失效時(shí)，會(huì)影響正在這個(gè)實(shí)例上進(jìn)行的session，從應(yīng)用的角度看，會(huì)出現(xiàn)單次請(qǐng)求失敗的情況，重新連接后即可繼續(xù)獲得服務(wù)。
• Placement Driver (簡(jiǎn)稱 PD)，是整個(gè)集群的管理模塊，其主要的工作有三個(gè)，一是存儲(chǔ)集群的元信息，（某個(gè)Key存儲(chǔ)在哪個(gè)TiKV節(jié)點(diǎn)上）；二是對(duì)TiKV集群進(jìn)行調(diào)度和負(fù)載均衡（如數(shù)據(jù)的遷移，Raft group leader的遷移等），三是分配全局唯一且遞增的事務(wù)ID。PD 通過(guò) Raft 協(xié)議保證數(shù)據(jù)的安全性。Raft 的 leader server 負(fù)責(zé)處理所有操作，其余的 PD server 僅用于保證高可用。單個(gè)實(shí)例失效時(shí)，如果這個(gè)實(shí)例不是 Raft 的 leader，那么服務(wù)完全不受影響；如果這個(gè)實(shí)例是 Raft 的 leader，會(huì)重新選出新的 Raft leader，自動(dòng)恢復(fù)服務(wù)。PD 在選舉的過(guò)程中無(wú)法對(duì)外提供服務(wù)，這個(gè)時(shí)間大約是3秒鐘。推薦至少部署三個(gè) PD 實(shí)例。
• TiKV Server 負(fù)責(zé)存儲(chǔ)數(shù)據(jù)，從外部看 TiKV 是一個(gè)分布式的提供事務(wù)的 Key-Value 存儲(chǔ)引擎。存儲(chǔ)數(shù)據(jù)的基本單位是 Region，每個(gè) Region 負(fù)責(zé)存儲(chǔ)一個(gè) Key Range（從 StartKey 到 EndKey 的左閉右開(kāi)區(qū)間）的數(shù)據(jù)，每個(gè) TiKV 節(jié)點(diǎn)會(huì)負(fù)責(zé)多個(gè) Region。TiKV 使用 Raft 協(xié)議做復(fù)制，保持?jǐn)?shù)據(jù)的一致性和容災(zāi)。副本以 Region 為單位進(jìn)行管理，不同節(jié)點(diǎn)上的多個(gè) Region 構(gòu)成一個(gè) Raft Group，互為副本。數(shù)據(jù)在多個(gè) TiKV 之間的負(fù)載均衡由 PD 調(diào)度，這里也是以 Region 為單位進(jìn)行調(diào)度。TiKV 是一個(gè)集群，通過(guò) Raft 協(xié)議保持?jǐn)?shù)據(jù)的一致性（副本數(shù)量可配置，默認(rèn)保存三副本），并通過(guò) PD 做負(fù)載均衡調(diào)度。單個(gè)節(jié)點(diǎn)失效時(shí)，會(huì)影響這個(gè)節(jié)點(diǎn)上存儲(chǔ)的所有 Region。對(duì)于 Region 中的 Leader 結(jié)點(diǎn)，會(huì)中斷服務(wù)，等待重新選舉；對(duì)于 Region 中的 Follower 節(jié)點(diǎn)，不會(huì)影響服務(wù)。當(dāng)某個(gè) TiKV 節(jié)點(diǎn)失效，并且在一段時(shí)間內(nèi)（默認(rèn) 30 分鐘）無(wú)法恢復(fù)，PD 會(huì)將其上的數(shù)據(jù)遷移到其他的 TiKV 節(jié)點(diǎn)上。
• TiSpark作為 TiDB 中解決用戶復(fù)雜 OLAP 需求的主要組件，將 Spark SQL 直接運(yùn)行在 TiDB 存儲(chǔ)層上，同時(shí)融合 TiKV 分布式集群的優(yōu)勢(shì)，并融入大數(shù)據(jù)社區(qū)生態(tài)。至此，TiDB 可以通過(guò)一套系統(tǒng)，同時(shí)支持 OLTP 與 OLAP，免除用戶數(shù)據(jù)同步的IO損耗。

分布式協(xié)議Paxos和Raft
算法演進(jìn)過(guò)程

Paxos

Paxos算法是Leslie Lamport在1990年提出的一種基于消息傳遞的一致性算法。由于算法難以理解，起初并沒(méi)有引起大家的重視，Lamport在1998年將論文重新發(fā)表到TOCS上，即便如此Paxos算法還是沒(méi)有得到重視，2001年Lamport用可讀性比較強(qiáng)的敘述性語(yǔ)言給出算法描述。

06年Google發(fā)布了三篇論文，其中在Chubby鎖服務(wù)使用Paxos作為Chubby Cell中的一致性算法，Paxos的人氣從此一路狂飆。

基于Paxos協(xié)議的數(shù)據(jù)同步與傳統(tǒng)主備方式最大的區(qū)別在于：Paxos只需超過(guò)半數(shù)的副本在線且相互通信正常，就可以保證服務(wù)的持續(xù)可用，且數(shù)據(jù)不丟失。

Basic-Paxos

Basic-Paxos解決的問(wèn)題：在一個(gè)分布式系統(tǒng)中，如何就一個(gè)提案達(dá)成一致。

需要借助兩階段提交實(shí)現(xiàn)：

Prepare階段：

Proposer選擇一個(gè)提案編號(hào)n并將prepare請(qǐng)求發(fā)送給 Acceptor。
Acceptor收到prepare消息后，如果提案的編號(hào)大于它已經(jīng)回復(fù)的所有prepare消息，則Acceptor將自己上次接受的提案回復(fù)給Proposer，并承諾不再回復(fù)小于n的提案。

Accept階段：

當(dāng)一個(gè)Proposer收到了多數(shù)Acceptor對(duì)prepare的回復(fù)后，就進(jìn)入批準(zhǔn)階段。它要向回復(fù)prepare請(qǐng)求的Acceptor發(fā)送accept請(qǐng)求，包括編號(hào)n和根據(jù)prepare階段決定的value（如果根據(jù)prepare沒(méi)有已經(jīng)接受的value，那么它可以自由決定value）。
在不違背自己向其他Proposer的承諾的前提下，Acceptor收到accept請(qǐng)求后即接受這個(gè)請(qǐng)求。

Mulit-Paxos

Mulit-Paxos解決的問(wèn)題：在一個(gè)分布式系統(tǒng)中，如何就一批提案達(dá)成一致。

當(dāng)存在一批提案時(shí)，用Basic-Paxos一個(gè)一個(gè)決議當(dāng)然也可以，但是每個(gè)提案都經(jīng)歷兩階段提交，顯然效率不高。Basic-Paxos協(xié)議的執(zhí)行流程針對(duì)每個(gè)提案（每條redo log）都至少存在三次網(wǎng)絡(luò)交互：1. 產(chǎn)生log ID；2. prepare階段；3. accept階段。

所以，Mulit-Paxos基于Basic-Paxos做了優(yōu)化，在Paxos集群中利用Paxos協(xié)議選舉出唯一的leader，在leader有效期內(nèi)所有的議案都只能由leader發(fā)起。

這里強(qiáng)化了協(xié)議的假設(shè)：即leader有效期內(nèi)不會(huì)有其他server提出的議案。因此，對(duì)于后續(xù)的提案，我們可以簡(jiǎn)化掉產(chǎn)生log ID階段和Prepare階段，而是由唯一的leader產(chǎn)生log ID，然后直接執(zhí)行Accept，得到多數(shù)派確認(rèn)即表示提案達(dá)成一致（每條redo log可對(duì)應(yīng)一個(gè)提案）。

相關(guān)產(chǎn)品

X-DB、OceanBase、Spanner都是使用Multi-Paxos來(lái)保障數(shù)據(jù)一致性。

MySQL Group Replication的xcom中也使用了Multi-Paxos。

PaxosStore

PaxosStore是騰訊WXG基于Paxos實(shí)現(xiàn)的分布式一致性中間件，在微信的用戶賬號(hào)管理、用戶關(guān)系管理、即使消息、社交網(wǎng)絡(luò)、在線支付等場(chǎng)景中廣泛應(yīng)用。

Raft

Raft是斯坦福大學(xué)的Diego Ongaro、John Ousterhout兩個(gè)人以易理解為目標(biāo)設(shè)計(jì)的一致性算法，在2013年發(fā)布了論文：《In Search of an Understandable Consensus Algorithm》。從2013年發(fā)布到現(xiàn)在，已經(jīng)有了十幾種語(yǔ)言的Raft算法實(shí)現(xiàn)框架，較為出名的有etcd，Google的Kubernetes也是用了etcd作為他的服務(wù)發(fā)現(xiàn)框架。

與Paxos相比，Raft強(qiáng)調(diào)的是易理解、易實(shí)現(xiàn)，Raft和Paxos一樣只要保證超過(guò)半數(shù)的節(jié)點(diǎn)正常就能夠提供服務(wù)。

眾所周知，當(dāng)問(wèn)題較為復(fù)雜時(shí)，可以把問(wèn)題分解為幾個(gè)小問(wèn)題來(lái)處理，Raft也使用了分而治之的思想，把算法分為三個(gè)子問(wèn)題：

選舉（Leader election）
日志復(fù)制（Log replication）
安全性（Safety）

分解后，整個(gè)raft算法變得易理解、易論證、易實(shí)現(xiàn)。

相關(guān)產(chǎn)品

etcd使用Raft來(lái)保障數(shù)據(jù)一致性。

Mulit-Raft

許多NewSQL數(shù)據(jù)庫(kù)的數(shù)據(jù)規(guī)模上限都定位在100TB以上，為了負(fù)載均衡，都會(huì)對(duì)數(shù)據(jù)進(jìn)行分片（sharding），所以就需要使用多個(gè)Raft集群（即Multi-Raft），每個(gè)Raft集群對(duì)應(yīng)一個(gè)分片。

在多個(gè)Raft集群間可增加協(xié)同來(lái)減少資源開(kāi)銷、提升性能（如：共享通信鏈接、合并消息等）。

相關(guān)產(chǎn)品

TiDB、CockroachDB、PolarDB都是使用Mulit-Raft來(lái)保障數(shù)據(jù)一致性。

Raft和Multi-Paxos的區(qū)別

Raft是基于對(duì)Multi-Paxos的兩個(gè)限制形成的：

發(fā)送的請(qǐng)求的是連續(xù)的, 也就是說(shuō)Raft的append 操作必須是連續(xù)的， 而Paxos可以并發(fā) (這里并發(fā)只是append log的并發(fā), 應(yīng)用到狀態(tài)機(jī)還是有序的)。
Raft選主有限制,必須包含最新、最全日志的節(jié)點(diǎn)才能被選為leader. 而Multi-Paxos沒(méi)有這個(gè)限制，日志不完備的節(jié)點(diǎn)也能成為leader。

Raft可以看成是簡(jiǎn)化版的Multi-Paxos。

Multi-Paxos允許并發(fā)的寫(xiě)log,當(dāng)leader節(jié)點(diǎn)故障后，剩余節(jié)點(diǎn)有可能都有日志空洞。所以選出新leader后, 需要將新leader里沒(méi)有的log補(bǔ)全,在依次應(yīng)用到狀態(tài)機(jī)里。

Raft選舉過(guò)程
Raft協(xié)議中，一個(gè)節(jié)點(diǎn)有三個(gè)狀態(tài)：Leader、Follower和Candidate，但同一時(shí)刻只能處于其中一種狀態(tài)。Raft選舉實(shí)際是指選舉Leader，選舉是由候選者（Candidate）主動(dòng)發(fā)起，而不是由其它第三者。

并且約束只有Leader才能接受寫(xiě)和讀請(qǐng)求，只有Candidate才能發(fā)起選舉。如果一個(gè)Follower和它的Leader失聯(lián)（失聯(lián)時(shí)長(zhǎng)超過(guò)一個(gè)Term），則它自動(dòng)轉(zhuǎn)為Candidate，并發(fā)起選舉。

發(fā)起選舉的目的是Candidate請(qǐng)求（Request）其它所有節(jié)點(diǎn)投票給自己，如果Candidate獲得多數(shù)節(jié)點(diǎn)（a majority of nodes）的投票（Votes），則自動(dòng)成為L(zhǎng)eader，這個(gè)過(guò)程即叫Leader選舉。

在Raft協(xié)議中，正常情況下Leader會(huì)周期性（不能大于Term）的向所有節(jié)點(diǎn)發(fā)送AppendEntries RPC，以維持它的Leader地位。

相應(yīng)的，如果一個(gè)Follower在一個(gè)Term內(nèi)沒(méi)有接收到Leader發(fā)來(lái)的AppendEntries RPC，則它在延遲隨機(jī)時(shí)間（150ms~300ms）后，即向所有其它節(jié)點(diǎn)發(fā)起選舉。

采取隨機(jī)時(shí)間的目的是避免多個(gè)Followers同時(shí)發(fā)起選舉，而同時(shí)發(fā)起選舉容易導(dǎo)致所有Candidates都未能獲得多數(shù)Followers的投票（腦裂，比如各獲得了一半的投票，誰(shuí)也不占多數(shù)，導(dǎo)致選舉無(wú)效需重選），因而延遲隨機(jī)時(shí)間可以提高一次選舉的成功性。