TIDB 架構及分布式協議Paxos和Raft對比

近來newsql大熱，尤以TIDB最火，pingcap不斷打磨TiDB，現如今版本已經迭代到3.0，產品已經基本趨于成熟。
對于TiDB，整體架構圖如下圖所示

是由四個模塊組成，TiDB Server，PD Server，TiKV Server，TiSpark。

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

分布式協議Paxos和Raft
算法演進過程

Paxos

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

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

基于Paxos協議的數據同步與傳統主備方式最大的區別在于：Paxos只需超過半數的副本在線且相互通信正常，就可以保證服務的持續可用，且數據不丟失。

Basic-Paxos

Basic-Paxos解決的問題：在一個分布式系統中，如何就一個提案達成一致。

需要借助兩階段提交實現：

Prepare階段：

Proposer選擇一個提案編號n并將prepare請求發送給 Acceptor。
Acceptor收到prepare消息后，如果提案的編號大于它已經回復的所有prepare消息，則Acceptor將自己上次接受的提案回復給Proposer，并承諾不再回復小于n的提案。

Accept階段：

當一個Proposer收到了多數Acceptor對prepare的回復后，就進入批準階段。它要向回復prepare請求的Acceptor發送accept請求，包括編號n和根據prepare階段決定的value（如果根據prepare沒有已經接受的value，那么它可以自由決定value）。
在不違背自己向其他Proposer的承諾的前提下，Acceptor收到accept請求后即接受這個請求。

Mulit-Paxos

Mulit-Paxos解決的問題：在一個分布式系統中，如何就一批提案達成一致。

當存在一批提案時，用Basic-Paxos一個一個決議當然也可以，但是每個提案都經歷兩階段提交，顯然效率不高。Basic-Paxos協議的執行流程針對每個提案（每條redo log）都至少存在三次網絡交互：1. 產生log ID；2. prepare階段；3. accept階段。

所以，Mulit-Paxos基于Basic-Paxos做了優化，在Paxos集群中利用Paxos協議選舉出唯一的leader，在leader有效期內所有的議案都只能由leader發起。

這里強化了協議的假設：即leader有效期內不會有其他server提出的議案。因此，對于后續的提案，我們可以簡化掉產生log ID階段和Prepare階段，而是由唯一的leader產生log ID，然后直接執行Accept，得到多數派確認即表示提案達成一致（每條redo log可對應一個提案）。

相關產品

X-DB、OceanBase、Spanner都是使用Multi-Paxos來保障數據一致性。

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

PaxosStore

PaxosStore是騰訊WXG基于Paxos實現的分布式一致性中間件，在微信的用戶賬號管理、用戶關系管理、即使消息、社交網絡、在線支付等場景中廣泛應用。

Raft

Raft是斯坦福大學的Diego Ongaro、John Ousterhout兩個人以易理解為目標設計的一致性算法，在2013年發布了論文：《In Search of an Understandable Consensus Algorithm》。從2013年發布到現在，已經有了十幾種語言的Raft算法實現框架，較為出名的有etcd，Google的Kubernetes也是用了etcd作為他的服務發現框架。

與Paxos相比，Raft強調的是易理解、易實現，Raft和Paxos一樣只要保證超過半數的節點正常就能夠提供服務。

眾所周知，當問題較為復雜時，可以把問題分解為幾個小問題來處理，Raft也使用了分而治之的思想，把算法分為三個子問題：

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

分解后，整個raft算法變得易理解、易論證、易實現。

相關產品

etcd使用Raft來保障數據一致性。

Mulit-Raft

許多NewSQL數據庫的數據規模上限都定位在100TB以上，為了負載均衡，都會對數據進行分片（sharding），所以就需要使用多個Raft集群（即Multi-Raft），每個Raft集群對應一個分片。

在多個Raft集群間可增加協同來減少資源開銷、提升性能（如：共享通信鏈接、合并消息等）。

相關產品

TiDB、CockroachDB、PolarDB都是使用Mulit-Raft來保障數據一致性。

Raft和Multi-Paxos的區別

Raft是基于對Multi-Paxos的兩個限制形成的：

發送的請求的是連續的, 也就是說Raft的append 操作必須是連續的， 而Paxos可以并發 (這里并發只是append log的并發, 應用到狀態機還是有序的)。
Raft選主有限制,必須包含最新、最全日志的節點才能被選為leader. 而Multi-Paxos沒有這個限制，日志不完備的節點也能成為leader。

Raft可以看成是簡化版的Multi-Paxos。

Multi-Paxos允許并發的寫log,當leader節點故障后，剩余節點有可能都有日志空洞。所以選出新leader后, 需要將新leader里沒有的log補全,在依次應用到狀態機里。

Raft選舉過程
Raft協議中，一個節點有三個狀態：Leader、Follower和Candidate，但同一時刻只能處于其中一種狀態。Raft選舉實際是指選舉Leader，選舉是由候選者（Candidate）主動發起，而不是由其它第三者。

并且約束只有Leader才能接受寫和讀請求，只有Candidate才能發起選舉。如果一個Follower和它的Leader失聯（失聯時長超過一個Term），則它自動轉為Candidate，并發起選舉。

發起選舉的目的是Candidate請求（Request）其它所有節點投票給自己，如果Candidate獲得多數節點（a majority of nodes）的投票（Votes），則自動成為Leader，這個過程即叫Leader選舉。

在Raft協議中，正常情況下Leader會周期性（不能大于Term）的向所有節點發送AppendEntries RPC，以維持它的Leader地位。

相應的，如果一個Follower在一個Term內沒有接收到Leader發來的AppendEntries RPC，則它在延遲隨機時間（150ms~300ms）后，即向所有其它節點發起選舉。

采取隨機時間的目的是避免多個Followers同時發起選舉，而同時發起選舉容易導致所有Candidates都未能獲得多數Followers的投票（腦裂，比如各獲得了一半的投票，誰也不占多數，導致選舉無效需重選），因而延遲隨機時間可以提高一次選舉的成功性。