實現分布式共識算法-Raft算法
筆者開源了自己實現的Java版Raft算法框架raft-core
項目鏈接：https://github.com/wujiuye/delay-scheduler/tree/main/raft/raft-core
該項目代碼是delay-scheduler(分布式延遲調度中間件)的子模塊，水平有限，建議只學習使用。
關于CAP原理
C(一致性)A(可用性)P(分區容忍性)原理是分布式系統永遠繞不開的話題，在任何的分布式系統中，可用性、一致性和分區容忍性這三個方面都是相互矛盾的，三者不可兼得，最多只能取其二。
AP：如果要求系統高可用(A)和分區容錯(P)，那么就必須放棄一致性(C);
CP：如果要求數據強一致(C)，由于網絡分區會導致同步時間無限延長(P)，可用性就得不到保障，那么就要放棄可用性(A);
CA：如果不存在網絡分區(分區指不同機房/國家/地區)(P)，那么強一致性(C)和可用性(A)可以同時滿足。
Raft一致性算法簡介
在Raft集群中，每個節點都對應一個角色，要么是Leader(領導節點)，要么是Follower(跟隨節點)，在未選舉出Leader之前，每個節點都可以是Candidate(候選節點)。
Raft算法約定Raft集群只能有一個Leader節點，并且只能由Leader節點處理客戶端的讀寫請求，將寫請求轉譯為操作日記，由Leader節點將操作日記復制給其它Follower節點，當Leader節點成功將一條操作日記同步到多數節點上時(包括自己在內的多數節點)，就可以將操作日記應用到狀態機，由狀態機執行寫操作(執行命令)，以此保證數據的最終一致性。
我們可以把Binlog看成Mysql數據庫執行的寫操作的命令，而MyISAM存儲引擎是Binlog的狀態機，用于執行命令。
實現Raft算法需要實現的兩個RPC接口：
- RequestVoteRpc：選舉時由當前候選節點向其它節點發起拉票請求;
- AppendEmtriesRpc：由Leader節點向其它Follower節點發送日記復制請求、心跳請求以及提交日記請求。
定時心跳計時器
Leader節點需要定時向其它Follower節點發送心跳包，以刷新其它Follower節點上的選舉超時計時。
心跳計時器在節點成為Leader節點時啟動，而在節點變為Follower節點時停止。要求心跳超時時間間隔要比超時選舉時間間隔長，即Heartbeat Timeout(心跳包廣播時間)< Election Timeout(選舉超時時間)。
超時選舉計時器
當計時達到超時(Election Timeout)閾值時觸發Leader選舉，當前節點將任期號+1，并嘗試給自己投一票(如果還未將票投給其它候選人)，給自己投票成功則將自己變成候選人，并向其它節點發起拉票請求。
超時選舉計時器的當前計時可被重置，在接收到AppendEntriesRPC(含心跳請求)請求時重新計時。要求每個節點的超時閾值要不一樣，避免同時發起拉票請求，導致多輪選舉都未能選出Leader的情況發生。
Leader選舉流程
Leader通過投票選舉機制選舉，每個任期號每個節點都只能有一票，每個節點都優先考慮投給自己，獲得多數選票的節點將成為Leader節點，因此Raft集群要求至少3個節點，并且Raft集群節點總數最好是奇數。
RequestVoteRpc請求數據包(拉票數據包)：
- public class RequestVote {
- private long term;
- private int candidateId;
- private long lastLogIndex;
- private long lastLogTerm;
- }
- term：拉票方(候選節點)的當前任期號;
- candidateId：拉票方的節點ID;
- lastLogIndex：拉票方最新日記條目的索引值;
- lastLogTerm：拉票方最新日記條目對應的任期號。
RequestVoteRpc響應數據包(投票數據包)：
- public class RequestVoteResp {
- private long term;
- private boolean voteGranted;
- }
- term：投票方的當前任期號，用于告知拉票方更新term值;
- voteGranted：如果投票方將選票投給拉票方，則voteGranted為true，否則為false。
在選舉計時器超時時發起拉票請求流程如下：
1)將自己本地維護的當前任期號(term)加1;
2)為自己投票，投票成功再將自己的狀態切換到候選節點(Candidate)，因此每個候選節點的第一張選票來自于它自己;
3)向其所在集群中的其他節點發送RequestVoteRPC請求(拉票請求)，要求它們投票給自己。
每個節點接收到其它候選節點發來的拉票請求時需根據節點當前任期號、日記同步情況、是否已經將當前期的一票投給了其它節點(包括自己)等作出如下反應：
1)、如果拉票方的term小于自身的當前term，返回false，提醒拉票方term過時，并明確告訴拉票方，這張選票不會投給它;
2)、如果拉票方的term大于自身的當前term，且如果之前沒有把選票投給任何人(包括自己)，則將選票投給該節點，返回拉票方的term和true;
3)、否則如果拉票方的term等于自身的當前term，如果已經把選票投給了拉票方(重復發起請求場景)，并且請求方的日記和自己的日記一樣新，則返回拉票方的term和true;
4)、否則，如果在此之前，已經把選票投給了其他人，則這張選票不能投給請求方，并明確告訴請求方，這張選票不會投給它。
候選節點廣播發起拉票請求后需根據最終投票結果作出如下反應：
1)、如果多數節點連接異常，則繼續當前期重新發起一次拉票，即多數節點掛掉選舉異常;
2)、得到大多數節點的選票成為Leader，包括自己投給自己的一票，但每個節點只有一票，投給了自己就不能投給其它節點;
3)、發現其它節點贏得了選舉(當拉票請求響應的term大于當前候選節點的term時，認為其它節點贏得了選舉)則主動切換回Follower;
4)、當超時選舉計時器又觸發超時選舉時，說明沒有接收到Leader的心跳包，最后一次選舉沒有節點贏得選舉成為Leader，那么繼續發起選舉。
如果是其它節點成為當前期的Leader，Leader會通過發送心跳包告知自己，要留給Leader足夠時間發送心跳包給自己，因此選舉超時要大于心跳超時，也就是：Heartbeat Timeout(心跳包廣播時間)< Election Timeout(選舉超時時間)。
在選舉結束后，每個Follower節點必須記錄當前期的Leader節點是哪個，Leader節點必須記錄其它所有Follower節點。Leader節點需要向其它Follower節點發送心跳包以及日記同步請求，而其它Follower節點在接收到客戶端請求時需要告知客戶端重定向到Leader節點發送請求。
Raft日志復制流程
在Raft集群中，Leader節點負責接收客戶端的讀寫請求，如果是Follower接收請求，則需要將請求重定向到Leader節點。
如果Leader節點接收的是讀請求，則Leader節點可直接查詢數據響應給客戶端;如果Leader節點接收的是寫請求，則Leader節點先將寫請求轉譯為一條操作日記，并將操作日記Append到本地，同時向其它節點發起AppendEntriesRPC調用，將該操作日記復制給其它節點，在成功復制多數節點后，Leader節點提交該操作日記，提交成功則應用到狀態機，再異步的向其它節點發起AppendEntriesRPC調用，告知其它Follower節點該日記已經提交，Follower節點接收提交請求后，先將日記改為已提交狀態，再將日記應用到狀態機。
AppendEntriesRPC請求數據包(Leader節點向其它Follower節點發起rpc請求，要求其它Follower節點復制這個日記條目)：
- public class AppendEntries implements Cloneable {
- private long term;
- private int leaderId;
- private long prevLogIndex;
- private long prevLogTerm;
- private long leaderCommit;
- private CommandLog[] entries;
- }
- term：Leader節點創建該日記條目時的任期號;
- leaderId：Leader節點的ID，為了其它Follower節點能夠重定向客戶端請求到Leader節點;
- prevLogIndex：Leader節點已提交的日記中最新一條日記的索引;
- prevLogTerm：Leader節點已提交的日記中最新一條日記的任期號;
- leaderCommit：Leader節點為每個Follower都維護一個leaderCommit，表示Leader節點認為Follower已經提交的日記條目索引值;
- entries：將要追加到Follower上的日記條目，如果是心跳包，則entries為空。
AppendEntriesRPC響應數據包(AppendEntries RPC響應)：
- public class AppendEntriesResp {
- private long term;
- private boolean success;
- }
term：當前任期號，取值為Max(AppendEntries請求攜帶的term，Follower本地維護的term)，用于Leader節點更新自己的任期號，一旦Leader節點發現任期號比自己的要大，就表明自己是一個過時的Leader，需要停止發送心跳包，主動切換為Follower;
success：接收者(Follower)是否能夠匹配prevLogIndex和prevLogTerm，匹配即說明請求成功。
Leader節點處理客戶端寫請求以及將寫請求日記復制給Follower的流程：
0)、客戶端向Leader發送寫請求;
1)、Leader將寫請求解析成操作指令日記追加到本地日志文件中;
2)、Leader異步向其它Follower節點發送AppendEntriesRPC請求;
3)、阻塞等待多數節點響應成功，多數節點至少是節點總數除以2加1，由于Leader節點自己也算一個，因此只需要節點總數除以2個節點響應成功即可;
4)、如果多數節點響應成功：Leader將該日志條目提交并應用到本地狀態機，異步告知其它Follower節點日記已經提交，之后立即向客戶端返回操作結果;
5)、否則：響應失敗給客戶端。
Follower節點處理日記復制請求流程：
0)、接收到任何AppendEntriesRPC請求(包含心跳包請求、提交日記請求、追加日記請求)，都重置選舉超時計時器的當前計時;
1)、如果自身的term大于請求參數term，另本地記錄的Leader的任期號小于自身，則返回自身的term，且success為false(告知請求方：你已經是過期的Leader);
2)、否則如果Follower自身在prevLogIndex日記的任期號與請求參數prevLogTerm不匹配，返回自身的term，且success為false(當前Follower節點的日記落后了);
3)、否則如果當前只是一個心跳包，說明是接收到Leader的心跳，說明自己已經是Follower，如果需要則將自己從候選節點切換為Follower節點，返回自身的term，且success為true;
4)、否則，Follower進行日記一致性檢查，刪除已經存在但不一致的日記，添加任何在已有的日記中不存在的條目，刪除多余的條目，并且，如果是復制已經提交的條目，復制成功時直接提交;
5)、如果請求參數的leaderCommit大于自身的當前commitIndex，則將commitIndex更新為Max(leaderCommit,commitIndex)，樂觀地將本地已提交日記的commitIndex躍進到領導人為該Follower跟蹤記得的值，用于Follower剛從故障中恢復過來的場景。
如果Follower節點向Leader節點響應日記追加失敗且Follower節點的當前期號小于等于Leader的當前期號，Leader節點將請求參數prevLogIndex遞減，然后重新發起AppendEntriesRPC請求，直到AppendEntriesRPC返回成功為止，這才表明在prevLogIndex位置的日志條目中領導人與追隨者的保持一致。這時，Follower節點上prevLogIndex位置之前的日志條目將全部保留，在prevLogIndex位置之后(與Leader有沖突)的日志條目將被Follower全部刪除，并且從該位置起追加Leader上在prevLogIndex位置之后的所有日志條目。因此，一旦AppendEntriesRPC返回成功，Leader和Follower的日志就可以保持一致了。
一致性
由于一個候選節點必須是得到多數節點投票才能成為Leader，且投票時節點不會把票投給沒有自己的日志新的候選節點，再者Leader只在已經將日記成功同步給多數節點(包括自己)才提交日記(將日記變成已提交狀態，同時應用到狀態機)，因此每次選舉出來的Leader就都是包含所有已提交日志的節點。
當新的Leader節點將新日記同步給某個Follower節點時，如果該Follower節點的日記落后很多，該Follower節點會主動移除Leader上沒有的日記，并且同步Leader節點日記給Follower。對于Leader節點已經標志為已提交的日記，Follower在接收時就可以直接應用到狀態機，以保持數據最終一致性。
Multi Raft
假設有三臺機器，每臺機器部署一個Raft節點服務，由于讀寫請求都由Leader節點處理，那么不就只能有一臺機器工作?
我們可以給一個節點服務啟動多個Raft服務(注意不是多個進程)，構造成多個Raft集群，即Multi Raft，這樣每個Raft集群的Leader節點就可能均勻分布在多臺機器上。例如：
| 機器 | Raft節點 |
Raft節點 |
Raft節點 |
|---|---|---|---|
機器1 |
Raft服務A節點1（Leader） |
Raft服務B節點1（Follower） |
Raft服務C節點1（Follower） |
機器2 |
Raft服務A節點2（Follower） |
Raft服務B節點2（Leader） |
Raft服務C節點2（Follower） |
機器3 |
Raft服務A節點3（Follower） |
Raft服務B節點3（Follower） |
Raft服務C節點3（Leader） |
在分布式數據庫TiDB中，就采用了Multi Raft，將數據進行分片處理，讓每個Raft集群單獨負責一部分數據。
參考文獻
華為云容器服務團隊.《云原生分布式存儲基石：etcd深入解析》 (云計算技術系列叢書)
Raft論文地址
Raft論文中文版：https://github.com/maemual/raft-zh_cn
圖片來源
圖片來源：https://github.com/maemual/raft-zh_cn/tree/master/images
本文轉載自微信公眾號「Java藝術」，可以通過以下二維碼關注。轉載本文請聯系Java藝術公眾號。
