[[402526]]

Raft 日志格式

在 Raft 算法中，需要實(shí)現(xiàn)分布式一致性的數(shù)據(jù)被稱作日志，我們 Java 后端絕大部分人談到日志，一般會(huì)聯(lián)想到項(xiàng)目通過 log4j 等日志框架輸出的信息，而 Raft 算法中的數(shù)據(jù)提交記錄，他們會(huì)按照時(shí)間順序進(jìn)行追加，Raft 也是嚴(yán)格按照時(shí)間順序并已一定的格式寫入日志文件中：

如上圖所示，Raft 的日志以日志項(xiàng)(LogEntry)的形式來組織，每個(gè)日志項(xiàng)包含一條命令、任期信息、日志項(xiàng)在日志中的位置信息(索引值 LogIndex)。

• 指令：由客戶端請(qǐng)求發(fā)送的執(zhí)行指令，有點(diǎn)繞口，我覺得理解成客戶端需要存儲(chǔ)的日志數(shù)據(jù)即可。
• 索引值：日志項(xiàng)在日志中的位置，需要注意索引值是一個(gè)連續(xù)并且單調(diào)遞增的整數(shù)。
• 任期編號(hào)：創(chuàng)建這條日志項(xiàng)的領(lǐng)導(dǎo)者的任期編號(hào)。

日志復(fù)制過程

Raft 的復(fù)制過程大致如下：

領(lǐng)導(dǎo)者接收到客戶端發(fā)來的請(qǐng)求，創(chuàng)建一個(gè)新的日志項(xiàng)，并將其追加到本地日志中，接著領(lǐng)導(dǎo)者通過追加條目 RPC 請(qǐng)求，將新的日志項(xiàng)復(fù)制到跟隨者的本地日志中，當(dāng)領(lǐng)導(dǎo)者收到大多數(shù)跟隨者的成功響應(yīng)之后，則將這條日志項(xiàng)應(yīng)用到狀態(tài)機(jī)中，可以理解成該條日志寫成功了，最后領(lǐng)導(dǎo)者返回日志寫成功的消息響應(yīng)客戶端，流程如下圖所示：

可以看出，Raft 的復(fù)制過程中，領(lǐng)導(dǎo)者接收到大多數(shù)跟隨者成功響應(yīng)，并且將日志項(xiàng)應(yīng)用到狀態(tài)機(jī)之后，不需要將結(jié)果響應(yīng)給跟隨者，而是直接將成功消息響應(yīng)給客戶端，這是一種優(yōu)化方式，同時(shí) Raft 會(huì)在下一次 RPC 追加日志請(qǐng)求中附加上本次的日志項(xiàng)信息。

以上僅僅只是一種沒有發(fā)生任何問題的復(fù)制過程，在這過程中難免會(huì)發(fā)生節(jié)點(diǎn)宕機(jī)等問題，在這種情況下，Raft 是如何處理的呢?

如何保證日志的一致性?

上面講到，在正常情況下，領(lǐng)導(dǎo)者的日志追加 RPC 請(qǐng)求響應(yīng)都成功的情況下，領(lǐng)導(dǎo)人和跟隨者的日志保持一致性。然而在領(lǐng)導(dǎo)者突然宕機(jī)的情況下有可能會(huì)造成領(lǐng)導(dǎo)者與跟隨者日志不一致的情況，這種情況會(huì)隨著后續(xù)領(lǐng)導(dǎo)者一些列宕機(jī)的情況下加劇問題的嚴(yán)重：

注：例子來源于 Raft 論文。

如上所示，當(dāng)一個(gè)領(lǐng)導(dǎo)者成功當(dāng)選時(shí)，跟隨者有可能是 a-f 的情況：

1. a-b 表示跟隨者的日志項(xiàng)落后于當(dāng)前領(lǐng)導(dǎo)者;
2. c-d 表示跟隨者有些日志項(xiàng)沒有被提交;
3. e-f 情況稍微有點(diǎn)復(fù)雜，以上兩種情況它們都存在。

下面我來還原上面圖所表示的情況是怎么發(fā)生的：

假設(shè)一開始 e 為領(lǐng)導(dǎo)者，在任期 2 時(shí)，f 被推選為領(lǐng)導(dǎo)者，寫入了若干日志項(xiàng)之后，在追加 RPC 請(qǐng)求中崩潰了，重啟后又被選舉為領(lǐng)導(dǎo)者(任期號(hào) 3)，又在寫入了若干日志項(xiàng)之后奔潰了;e 此時(shí)又重新選舉為領(lǐng)導(dǎo)者(任期號(hào)為 4)，成功復(fù)制了若干日志項(xiàng)，同時(shí)還有一部分沒有成功追加到大多數(shù)跟隨者又崩潰了，同時(shí)跟隨者 b 復(fù)制了一部分日志項(xiàng)之后崩潰了;假設(shè) a 在任期 5 時(shí)被選舉為領(lǐng)導(dǎo)者，c 在任期 6 時(shí)被選舉為領(lǐng)導(dǎo)者，還未全部將本地日志復(fù)制到其他跟隨者之前又崩潰了，在任期 7 時(shí) d 被選擇為領(lǐng)導(dǎo)者，寫入了若干日志項(xiàng)之后，在追加 RPC 請(qǐng)求中崩潰了，最后形成了上圖的情況。

面對(duì)以上的情況，Raft 是如何解決日志的一致性呢?

在 Raft 的日志機(jī)制中，為了簡(jiǎn)化日志一致性的行為，有以下兩點(diǎn)非常重要的特性：

1. 如果在不同的日志中的兩個(gè)條目擁有相同的索引和任期號(hào)，那么他們存儲(chǔ)了相同的指令。
2. 如果在不同的日志中的兩個(gè)條目擁有相同的索引和任期號(hào)，那么他們之前的所有日志條目也全部相同。

第一個(gè)特性是因?yàn)?Raft 日志項(xiàng)在日志中不會(huì)改變，因此只要日志項(xiàng)只要是索引值和任期號(hào)相同，就可以認(rèn)為他們是存儲(chǔ)了相同的指令數(shù)據(jù)信息。

第二個(gè)特性是因?yàn)轭I(lǐng)導(dǎo)者會(huì)通過強(qiáng)制覆蓋的方式讓跟隨者復(fù)制自己的日志來解決日志不一致的問題，領(lǐng)導(dǎo)者在追加 RPC 請(qǐng)求過程中會(huì)附帶需要復(fù)制的日志以及前一個(gè)日志項(xiàng)相關(guān)信息，如果跟隨者匹配不到包含相同索引位置和任期號(hào)的日志項(xiàng)，那么他就會(huì)拒絕接收新的日志條目，接著領(lǐng)導(dǎo)者會(huì)繼續(xù)遞減要復(fù)制的日志項(xiàng)索引值，直至找到相同索引和任期號(hào)的日志項(xiàng)，最后就直接覆蓋跟隨者之后的日志項(xiàng)?？烧J(rèn)為兩個(gè)條目擁有相同的索引和任期號(hào)，那么他們之前的所有日志條目也全部相同。

因此，Raft 的日志追加大致可分為兩個(gè)步驟：

領(lǐng)導(dǎo)者找到跟隨者與自己相同的最大日志項(xiàng)，這意味著跟隨者之前的日志都與領(lǐng)導(dǎo)者的日志相同;

領(lǐng)導(dǎo)者強(qiáng)制覆蓋之后不一致的日志，實(shí)現(xiàn)日志的一致性。

下面我用一個(gè)例子充分表達(dá) Raft 在日志復(fù)制過程中是如何進(jìn)行日志強(qiáng)制覆蓋的。

假設(shè)有一個(gè)領(lǐng)導(dǎo)者和一個(gè)跟隨者，他們的日志項(xiàng)復(fù)制情況如下：

可以看出，跟隨者在任期號(hào) 3 時(shí)是領(lǐng)導(dǎo)者，在追加日志過程中崩潰了，重啟之后成為跟隨者，隨后新的領(lǐng)導(dǎo)者向其追加日志，此時(shí)他的任期號(hào)為 3 最后的一個(gè)日志項(xiàng)將被覆蓋。

先來看下 Raft 追加條目 RPC 的請(qǐng)求參數(shù)：

領(lǐng)導(dǎo)者追加并覆蓋跟隨者過程如下：

領(lǐng)導(dǎo)者通過日志追加 RPC 請(qǐng)求，將當(dāng)前最新的要追加到跟隨者的日志項(xiàng)以及前一個(gè)它的 prevLogIndex=7、prevLogTerm=3 等信息發(fā)送跟跟隨者;

跟隨者判斷當(dāng)前最新的日志的任期號(hào)與 prevLogTerm 不一致，拒絕追加;

領(lǐng)導(dǎo)者繼續(xù)遞減需要復(fù)制的日志項(xiàng)的索引值，此時(shí) prevLogIndex=6、prevLogTerm=3;

跟隨者找到了 LogIndex=6、LogTerm=3 的日志項(xiàng)，跟隨者接受追加請(qǐng)求;

領(lǐng)導(dǎo)者接著會(huì)將跟隨者 LogIndex=6、LogTerm=3 的日志項(xiàng)之后的日志項(xiàng)進(jìn)行追加并覆蓋。

本文轉(zhuǎn)載自微信公眾號(hào)「后端進(jìn)階」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系后端進(jìn)階公眾號(hào)。