[[385285]]

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

項目鏈接：https://github.com/wujiuye/delay-scheduler/tree/main/raft/raft-core

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

關(guān)于CAP原理

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

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

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

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

Raft一致性算法簡介

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

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

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

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

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

定時心跳計時器

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

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

超時選舉計時器

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

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

Leader選舉流程

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

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

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

• term：拉票方(候選節(jié)點)的當(dāng)前任期號;
• candidateId：拉票方的節(jié)點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。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Raft日志復(fù)制流程

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

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

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

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é)點創(chuàng)建該日記條目時的任期號;
• leaderId：Leader節(jié)點的ID，為了其它Follower節(jié)點能夠重定向客戶端請求到Leader節(jié)點;
• prevLogIndex：Leader節(jié)點已提交的日記中最新一條日記的索引;
• prevLogTerm：Leader節(jié)點已提交的日記中最新一條日記的任期號;
• leaderCommit：Leader節(jié)點為每個Follower都維護一個leaderCommit，表示Leader節(jié)點認為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本地維護的term)，用于Leader節(jié)點更新自己的任期號，一旦Leader節(jié)點發(fā)現(xiàn)任期號比自己的要大，就表明自己是一個過時的Leader，需要停止發(fā)送心跳包，主動切換為Follower;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一致性

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

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

Multi Raft

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

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

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

參考文獻

華為云容器服務(wù)團隊.《云原生分布式存儲基石：etcd深入解析》 (云計算技術(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ù)公眾號。