[[385285]]

筆者開源了自己實(shí)現(xiàn)的Java版Raft算法框架raft-core

項(xiàng)目鏈接：https://github.com/wujiuye/delay-scheduler/tree/main/raft/raft-core

該項(xiàng)目代碼是delay-scheduler(分布式延遲調(diào)度中間件)的子模塊，水平有限，建議只學(xué)習(xí)使用。

關(guān)于CAP原理

C(一致性)A(可用性)P(分區(qū)容忍性)原理是分布式系統(tǒng)永遠(yuǎn)繞不開的話題，在任何的分布式系統(tǒng)中，可用性、一致性和分區(qū)容忍性這三個(gè)方面都是相互矛盾的，三者不可兼得，最多只能取其二。

AP：如果要求系統(tǒng)高可用(A)和分區(qū)容錯(P)，那么就必須放棄一致性(C);

CP：如果要求數(shù)據(jù)強(qiáng)一致(C)，由于網(wǎng)絡(luò)分區(qū)會導(dǎo)致同步時(shí)間無限延長(P)，可用性就得不到保障，那么就要放棄可用性(A);

CA：如果不存在網(wǎng)絡(luò)分區(qū)(分區(qū)指不同機(jī)房/國家/地區(qū))(P)，那么強(qiáng)一致性(C)和可用性(A)可以同時(shí)滿足。

Raft一致性算法簡介

在Raft集群中，每個(gè)節(jié)點(diǎn)都對應(yīng)一個(gè)角色，要么是Leader(領(lǐng)導(dǎo)節(jié)點(diǎn))，要么是Follower(跟隨節(jié)點(diǎn))，在未選舉出Leader之前，每個(gè)節(jié)點(diǎn)都可以是Candidate(候選節(jié)點(diǎn))。

Raft算法約定Raft集群只能有一個(gè)Leader節(jié)點(diǎn)，并且只能由Leader節(jié)點(diǎn)處理客戶端的讀寫請求，將寫請求轉(zhuǎn)譯為操作日記，由Leader節(jié)點(diǎn)將操作日記復(fù)制給其它Follower節(jié)點(diǎn)，當(dāng)Leader節(jié)點(diǎn)成功將一條操作日記同步到多數(shù)節(jié)點(diǎn)上時(shí)(包括自己在內(nèi)的多數(shù)節(jié)點(diǎn))，就可以將操作日記應(yīng)用到狀態(tài)機(jī)，由狀態(tài)機(jī)執(zhí)行寫操作(執(zhí)行命令)，以此保證數(shù)據(jù)的最終一致性。

我們可以把Binlog看成Mysql數(shù)據(jù)庫執(zhí)行的寫操作的命令，而MyISAM存儲引擎是Binlog的狀態(tài)機(jī)，用于執(zhí)行命令。

實(shí)現(xiàn)Raft算法需要實(shí)現(xiàn)的兩個(gè)RPC接口：

• RequestVoteRpc：選舉時(shí)由當(dāng)前候選節(jié)點(diǎn)向其它節(jié)點(diǎn)發(fā)起拉票請求;
• AppendEmtriesRpc：由Leader節(jié)點(diǎn)向其它Follower節(jié)點(diǎn)發(fā)送日記復(fù)制請求、心跳請求以及提交日記請求。

定時(shí)心跳計(jì)時(shí)器

Leader節(jié)點(diǎn)需要定時(shí)向其它Follower節(jié)點(diǎn)發(fā)送心跳包，以刷新其它Follower節(jié)點(diǎn)上的選舉超時(shí)計(jì)時(shí)。

心跳計(jì)時(shí)器在節(jié)點(diǎn)成為Leader節(jié)點(diǎn)時(shí)啟動，而在節(jié)點(diǎn)變?yōu)镕ollower節(jié)點(diǎn)時(shí)停止。要求心跳超時(shí)時(shí)間間隔要比超時(shí)選舉時(shí)間間隔長，即Heartbeat Timeout(心跳包廣播時(shí)間)< Election Timeout(選舉超時(shí)時(shí)間)。

超時(shí)選舉計(jì)時(shí)器

當(dāng)計(jì)時(shí)達(dá)到超時(shí)(Election Timeout)閾值時(shí)觸發(fā)Leader選舉，當(dāng)前節(jié)點(diǎn)將任期號+1，并嘗試給自己投一票(如果還未將票投給其它候選人)，給自己投票成功則將自己變成候選人，并向其它節(jié)點(diǎn)發(fā)起拉票請求。

超時(shí)選舉計(jì)時(shí)器的當(dāng)前計(jì)時(shí)可被重置，在接收到AppendEntriesRPC(含心跳請求)請求時(shí)重新計(jì)時(shí)。要求每個(gè)節(jié)點(diǎn)的超時(shí)閾值要不一樣，避免同時(shí)發(fā)起拉票請求，導(dǎo)致多輪選舉都未能選出Leader的情況發(fā)生。

Leader選舉流程

Leader通過投票選舉機(jī)制選舉，每個(gè)任期號每個(gè)節(jié)點(diǎn)都只能有一票，每個(gè)節(jié)點(diǎn)都優(yōu)先考慮投給自己，獲得多數(shù)選票的節(jié)點(diǎn)將成為Leader節(jié)點(diǎn)，因此Raft集群要求至少3個(gè)節(jié)點(diǎn)，并且Raft集群節(jié)點(diǎn)總數(shù)最好是奇數(shù)。

RequestVoteRpc請求數(shù)據(jù)包(拉票數(shù)據(jù)包)：

public class RequestVote { 
    private long term; 
    private int candidateId; 
    private long lastLogIndex; 
    private long lastLogTerm; 
} 

• term：拉票方(候選節(jié)點(diǎn))的當(dāng)前任期號;
• candidateId：拉票方的節(jié)點(diǎn)ID;
• lastLogIndex：拉票方最新日記條目的索引值;
• lastLogTerm：拉票方最新日記條目對應(yīng)的任期號。

RequestVoteRpc響應(yīng)數(shù)據(jù)包(投票數(shù)據(jù)包)：

public class RequestVoteResp { 
    private long term; 
    private boolean voteGranted; 
} 

• term：投票方的當(dāng)前任期號，用于告知拉票方更新term值;
• voteGranted：如果投票方將選票投給拉票方，則voteGranted為true，否則為false。

在選舉計(jì)時(shí)器超時(shí)時(shí)發(fā)起拉票請求流程如下：

1)將自己本地維護(hù)的當(dāng)前任期號(term)加1;

2)為自己投票，投票成功再將自己的狀態(tài)切換到候選節(jié)點(diǎn)(Candidate)，因此每個(gè)候選節(jié)點(diǎn)的第一張選票來自于它自己;

3)向其所在集群中的其他節(jié)點(diǎn)發(fā)送RequestVoteRPC請求(拉票請求)，要求它們投票給自己。

每個(gè)節(jié)點(diǎn)接收到其它候選節(jié)點(diǎn)發(fā)來的拉票請求時(shí)需根據(jù)節(jié)點(diǎn)當(dāng)前任期號、日記同步情況、是否已經(jīng)將當(dāng)前期的一票投給了其它節(jié)點(diǎn)(包括自己)等作出如下反應(yīng)：

1)、如果拉票方的term小于自身的當(dāng)前term，返回false，提醒拉票方term過時(shí)，并明確告訴拉票方，這張選票不會投給它;

2)、如果拉票方的term大于自身的當(dāng)前term，且如果之前沒有把選票投給任何人(包括自己)，則將選票投給該節(jié)點(diǎn)，返回拉票方的term和true;

3)、否則如果拉票方的term等于自身的當(dāng)前term，如果已經(jīng)把選票投給了拉票方(重復(fù)發(fā)起請求場景)，并且請求方的日記和自己的日記一樣新，則返回拉票方的term和true;

4)、否則，如果在此之前，已經(jīng)把選票投給了其他人，則這張選票不能投給請求方，并明確告訴請求方，這張選票不會投給它。

候選節(jié)點(diǎn)廣播發(fā)起拉票請求后需根據(jù)最終投票結(jié)果作出如下反應(yīng)：

1)、如果多數(shù)節(jié)點(diǎn)連接異常，則繼續(xù)當(dāng)前期重新發(fā)起一次拉票，即多數(shù)節(jié)點(diǎn)掛掉選舉異常;

2)、得到大多數(shù)節(jié)點(diǎn)的選票成為Leader，包括自己投給自己的一票，但每個(gè)節(jié)點(diǎn)只有一票，投給了自己就不能投給其它節(jié)點(diǎn);

3)、發(fā)現(xiàn)其它節(jié)點(diǎn)贏得了選舉(當(dāng)拉票請求響應(yīng)的term大于當(dāng)前候選節(jié)點(diǎn)的term時(shí)，認(rèn)為其它節(jié)點(diǎn)贏得了選舉)則主動切換回Follower;

4)、當(dāng)超時(shí)選舉計(jì)時(shí)器又觸發(fā)超時(shí)選舉時(shí)，說明沒有接收到Leader的心跳包，最后一次選舉沒有節(jié)點(diǎn)贏得選舉成為Leader，那么繼續(xù)發(fā)起選舉。

如果是其它節(jié)點(diǎn)成為當(dāng)前期的Leader，Leader會通過發(fā)送心跳包告知自己，要留給Leader足夠時(shí)間發(fā)送心跳包給自己，因此選舉超時(shí)要大于心跳超時(shí)，也就是：Heartbeat Timeout(心跳包廣播時(shí)間)< Election Timeout(選舉超時(shí)時(shí)間)。

在選舉結(jié)束后，每個(gè)Follower節(jié)點(diǎn)必須記錄當(dāng)前期的Leader節(jié)點(diǎn)是哪個(gè)，Leader節(jié)點(diǎn)必須記錄其它所有Follower節(jié)點(diǎn)。Leader節(jié)點(diǎn)需要向其它Follower節(jié)點(diǎn)發(fā)送心跳包以及日記同步請求，而其它Follower節(jié)點(diǎn)在接收到客戶端請求時(shí)需要告知客戶端重定向到Leader節(jié)點(diǎn)發(fā)送請求。

Raft日志復(fù)制流程

在Raft集群中，Leader節(jié)點(diǎn)負(fù)責(zé)接收客戶端的讀寫請求，如果是Follower接收請求，則需要將請求重定向到Leader節(jié)點(diǎn)。

如果Leader節(jié)點(diǎn)接收的是讀請求，則Leader節(jié)點(diǎn)可直接查詢數(shù)據(jù)響應(yīng)給客戶端;如果Leader節(jié)點(diǎn)接收的是寫請求，則Leader節(jié)點(diǎn)先將寫請求轉(zhuǎn)譯為一條操作日記，并將操作日記Append到本地，同時(shí)向其它節(jié)點(diǎn)發(fā)起AppendEntriesRPC調(diào)用，將該操作日記復(fù)制給其它節(jié)點(diǎn)，在成功復(fù)制多數(shù)節(jié)點(diǎn)后，Leader節(jié)點(diǎn)提交該操作日記，提交成功則應(yīng)用到狀態(tài)機(jī)，再異步的向其它節(jié)點(diǎn)發(fā)起AppendEntriesRPC調(diào)用，告知其它Follower節(jié)點(diǎn)該日記已經(jīng)提交，F(xiàn)ollower節(jié)點(diǎn)接收提交請求后，先將日記改為已提交狀態(tài)，再將日記應(yīng)用到狀態(tài)機(jī)。

AppendEntriesRPC請求數(shù)據(jù)包(Leader節(jié)點(diǎn)向其它Follower節(jié)點(diǎn)發(fā)起rpc請求，要求其它Follower節(jié)點(diǎn)復(fù)制這個(gè)日記條目)：

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節(jié)點(diǎn)創(chuàng)建該日記條目時(shí)的任期號;
• leaderId：Leader節(jié)點(diǎn)的ID，為了其它Follower節(jié)點(diǎn)能夠重定向客戶端請求到Leader節(jié)點(diǎn);
• prevLogIndex：Leader節(jié)點(diǎn)已提交的日記中最新一條日記的索引;
• prevLogTerm：Leader節(jié)點(diǎn)已提交的日記中最新一條日記的任期號;
• leaderCommit：Leader節(jié)點(diǎn)為每個(gè)Follower都維護(hù)一個(gè)leaderCommit，表示Leader節(jié)點(diǎn)認(rèn)為Follower已經(jīng)提交的日記條目索引值;
• entries：將要追加到Follower上的日記條目，如果是心跳包，則entries為空。

AppendEntriesRPC響應(yīng)數(shù)據(jù)包(AppendEntries RPC響應(yīng))：

public class AppendEntriesResp { 
    private long term; 
    private boolean success; 
} 

term：當(dāng)前任期號，取值為Max(AppendEntries請求攜帶的term，F(xiàn)ollower本地維護(hù)的term)，用于Leader節(jié)點(diǎn)更新自己的任期號，一旦Leader節(jié)點(diǎn)發(fā)現(xiàn)任期號比自己的要大，就表明自己是一個(gè)過時(shí)的Leader，需要停止發(fā)送心跳包，主動切換為Follower;

success：接收者(Follower)是否能夠匹配prevLogIndex和prevLogTerm，匹配即說明請求成功。

Leader節(jié)點(diǎn)處理客戶端寫請求以及將寫請求日記復(fù)制給Follower的流程：

0)、客戶端向Leader發(fā)送寫請求;

1)、Leader將寫請求解析成操作指令日記追加到本地日志文件中;

2)、Leader異步向其它Follower節(jié)點(diǎn)發(fā)送AppendEntriesRPC請求;

3)、阻塞等待多數(shù)節(jié)點(diǎn)響應(yīng)成功，多數(shù)節(jié)點(diǎn)至少是節(jié)點(diǎn)總數(shù)除以2加1，由于Leader節(jié)點(diǎn)自己也算一個(gè)，因此只需要節(jié)點(diǎn)總數(shù)除以2個(gè)節(jié)點(diǎn)響應(yīng)成功即可;

4)、如果多數(shù)節(jié)點(diǎn)響應(yīng)成功：Leader將該日志條目提交并應(yīng)用到本地狀態(tài)機(jī)，異步告知其它Follower節(jié)點(diǎn)日記已經(jīng)提交，之后立即向客戶端返回操作結(jié)果;

5)、否則：響應(yīng)失敗給客戶端。

Follower節(jié)點(diǎn)處理日記復(fù)制請求流程：

0)、接收到任何AppendEntriesRPC請求(包含心跳包請求、提交日記請求、追加日記請求)，都重置選舉超時(shí)計(jì)時(shí)器的當(dāng)前計(jì)時(shí);

1)、如果自身的term大于請求參數(shù)term，另本地記錄的Leader的任期號小于自身，則返回自身的term，且success為false(告知請求方：你已經(jīng)是過期的Leader);

2)、否則如果Follower自身在prevLogIndex日記的任期號與請求參數(shù)prevLogTerm不匹配，返回自身的term，且success為false(當(dāng)前Follower節(jié)點(diǎn)的日記落后了);

3)、否則如果當(dāng)前只是一個(gè)心跳包，說明是接收到Leader的心跳，說明自己已經(jīng)是Follower，如果需要則將自己從候選節(jié)點(diǎn)切換為Follower節(jié)點(diǎn)，返回自身的term，且success為true;

4)、否則，F(xiàn)ollower進(jìn)行日記一致性檢查，刪除已經(jīng)存在但不一致的日記，添加任何在已有的日記中不存在的條目，刪除多余的條目，并且，如果是復(fù)制已經(jīng)提交的條目，復(fù)制成功時(shí)直接提交;

5)、如果請求參數(shù)的leaderCommit大于自身的當(dāng)前commitIndex，則將commitIndex更新為Max(leaderCommit,commitIndex)，樂觀地將本地已提交日記的commitIndex躍進(jìn)到領(lǐng)導(dǎo)人為該Follower跟蹤記得的值，用于Follower剛從故障中恢復(fù)過來的場景。

如果Follower節(jié)點(diǎn)向Leader節(jié)點(diǎn)響應(yīng)日記追加失敗且Follower節(jié)點(diǎn)的當(dāng)前期號小于等于Leader的當(dāng)前期號，Leader節(jié)點(diǎn)將請求參數(shù)prevLogIndex遞減，然后重新發(fā)起AppendEntriesRPC請求，直到AppendEntriesRPC返回成功為止，這才表明在prevLogIndex位置的日志條目中領(lǐng)導(dǎo)人與追隨者的保持一致。這時(shí)，F(xiàn)ollower節(jié)點(diǎn)上prevLogIndex位置之前的日志條目將全部保留，在prevLogIndex位置之后(與Leader有沖突)的日志條目將被Follower全部刪除，并且從該位置起追加Leader上在prevLogIndex位置之后的所有日志條目。因此，一旦AppendEntriesRPC返回成功，Leader和Follower的日志就可以保持一致了。

一致性

由于一個(gè)候選節(jié)點(diǎn)必須是得到多數(shù)節(jié)點(diǎn)投票才能成為Leader，且投票時(shí)節(jié)點(diǎn)不會把票投給沒有自己的日志新的候選節(jié)點(diǎn)，再者Leader只在已經(jīng)將日記成功同步給多數(shù)節(jié)點(diǎn)(包括自己)才提交日記(將日記變成已提交狀態(tài)，同時(shí)應(yīng)用到狀態(tài)機(jī))，因此每次選舉出來的Leader就都是包含所有已提交日志的節(jié)點(diǎn)。

當(dāng)新的Leader節(jié)點(diǎn)將新日記同步給某個(gè)Follower節(jié)點(diǎn)時(shí)，如果該Follower節(jié)點(diǎn)的日記落后很多，該Follower節(jié)點(diǎn)會主動移除Leader上沒有的日記，并且同步Leader節(jié)點(diǎn)日記給Follower。對于Leader節(jié)點(diǎn)已經(jīng)標(biāo)志為已提交的日記，F(xiàn)ollower在接收時(shí)就可以直接應(yīng)用到狀態(tài)機(jī)，以保持?jǐn)?shù)據(jù)最終一致性。

Multi Raft

假設(shè)有三臺機(jī)器，每臺機(jī)器部署一個(gè)Raft節(jié)點(diǎn)服務(wù)，由于讀寫請求都由Leader節(jié)點(diǎn)處理，那么不就只能有一臺機(jī)器工作?

我們可以給一個(gè)節(jié)點(diǎn)服務(wù)啟動多個(gè)Raft服務(wù)(注意不是多個(gè)進(jìn)程)，構(gòu)造成多個(gè)Raft集群，即Multi Raft，這樣每個(gè)Raft集群的Leader節(jié)點(diǎn)就可能均勻分布在多臺機(jī)器上。例如：

在分布式數(shù)據(jù)庫TiDB中，就采用了Multi Raft，將數(shù)據(jù)進(jìn)行分片處理，讓每個(gè)Raft集群單獨(dú)負(fù)責(zé)一部分?jǐn)?shù)據(jù)。

參考文獻(xiàn)

華為云容器服務(wù)團(tuán)隊(duì).《云原生分布式存儲基石：etcd深入解析》 (云計(jì)算技術(shù)系列叢書)

Raft論文地址

Raft論文中文版：https://github.com/maemual/raft-zh_cn

圖片來源

圖片來源：https://github.com/maemual/raft-zh_cn/tree/master/images

本文轉(zhuǎn)載自微信公眾號「Java藝術(shù)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系Java藝術(shù)公眾號。