[toc]

Raft 論文解讀

Q&A

Q: 如果一個older leader不知道新的leader被選出來了怎么辦？

A : 因為new leader被選出，那么或有超過一半的服務(wù)器知道有新的leader了，所以當(dāng)older leader發(fā)送AppendEntries RPC時，不會有超過一半的accept，所以該entry不會被提交，但是會在少部分服務(wù)器的log中存在

1. Introduction

提到了Paxos算法非常困難而raft比較容易理解，最初raft發(fā)明的初衷是understandbility,希望這個算法容易理解。

在設(shè)計Raft的時候為了簡單做了一些分解，將leader election, log replication 和 safety這三個部分拆開，另外還做了一些state space reduction(相比較于Paxos，raft減少了一些不確定性和servers互相通信保持一致的方法)。

Raft和Viewstamped Replication有很多相似，但是多了下面的一些新特性

• strong leader: Raft使用一個更強制的leader屬性，例如log只能從leader發(fā)送到其他的server
• leader election：Raft使用隨機timer來選舉leader，通過稍微修改一下心跳包的機制來實現(xiàn)
• membership changes：Raft使用一種新的機制joint consensus來解決集群中服務(wù)器的變化，通過兩次term之間服務(wù)器會有重疊的方法

2. Replicated state machines

[圖片上傳失敗...(image-8a68ba-1652515917505)]

replicated state machine 在single leader的系統(tǒng)中經(jīng)常使用，每一個server都會有一個operation log記錄操作，leader接收client的操作，通過一個共識模塊來保證所有follower的log中日志和leader是一樣的，這樣的結(jié)果就是，所有的機器都按同樣的順序執(zhí)行相同的指令，理論上來說這樣下來所有機器的狀態(tài)也都是相同的，就達到了replication的目的

3. What's wrong with Paxos?

Paxos的優(yōu)點：支持多決策(multi-Paxos)，safety，liveness(?不理解，中文是活躍性)，支持集群中的服務(wù)器發(fā)生更改，被證明是正確的并且是高效的

Paxos的缺點：1.很難理解，作者認為是Paxos將每一個操作都單獨看成一個單獨的決策而導(dǎo)致的，Paxos算法的兩個階段不夠直觀并且不能夠單獨開來理解，multi-Paxos算法更是增加了額外的復(fù)雜度。 2. 很難構(gòu)建一個這樣的系統(tǒng)實現(xiàn)，一個原因是因為原作者之提出了single-decree Paxos，對于multi-Paxos只提了一個草圖，而不同的人對于multi-Paxos提出了不同的算法。另外由于最初的Paxos論文是single-decree的也就是說，每次只做一個決定，這和現(xiàn)實生活是不一樣的，所有人們往往都是從Paxos算法開始，最后的結(jié)果和Paxos算法有很大的區(qū)別。另外，因為Paxos算法是沒有l(wèi)eader的，這在做多決策的時候，往往有一個leader來協(xié)調(diào)這些決策會使得系統(tǒng)設(shè)計更加的簡單

4. Designing for understandability

Raft的設(shè)計目標：

• 提供完整實際的基礎(chǔ)來幫助構(gòu)建系統(tǒng)，減少設(shè)計者的復(fù)旦
• 在所有情況下都是安全的，并且在大多數(shù)情況下可用
• 在通常情況下高效
• 最重要的目標：understandility，容易理解，并且非常直觀

在設(shè)計時使用兩種主要的技術(shù)

1. decomposition：將問題分解成可以被相對獨立的解決和解釋的子問題，raft將一致性分解為了leader election, log replication, safety, and membership changes這些問題
2. simplify the state space：減少狀態(tài)空間，大概的意思就是減少需要考慮的情況，減少nondeterministic的情況。在raft設(shè)計中，logs不允許有holes(空位)，并且限制了servers之間可能出現(xiàn)不一致的情況數(shù)量。雖然nondeterministic是不可避免的，例如隨機化就會導(dǎo)致不確定性，設(shè)計者采用“choose any; it doesn’t matter”的思想來解決這些問題。

5. The Raft consensus algorithm

raft將共識的問題分解為三個子問題：

• Leader election：一個新的leader要被選出，在當(dāng)前的leader宕機時
• Log replication：leader必須要接受client的請求并且將他們復(fù)制到集群上，強迫其他服務(wù)器的log和自己一致
• Safety：如果一個server的log在index I上放的是操作A，任何其他server在該index上都是放的操作A

5.1 Raft basics

一個Raft集群會包含許多servers(通常是5個，這樣可以容忍2臺服務(wù)器宕機)。

[站外圖片上傳中...(image-2315e9-1652515917505)]

一臺服務(wù)器有以下三個狀態(tài)，leader，follower和candidate，只有l(wèi)eader才處理clients的請求，并將它們轉(zhuǎn)發(fā)給其他follower，follower是被動的，不會發(fā)出請求，只會回復(fù)leader和candidate的請求。candidate是為了選出新的leader的狀態(tài)。

[圖片上傳失敗...(image-941a04-1652515917505)]

raft將時間分為一個個term(任期)，用連續(xù)的數(shù)字來表示，每一個任期由一個election開始，每次選舉至多有一個leader選出，可能同時有兩個candidate把選票分了，導(dǎo)致沒有選出leader，這種情況一個新的term會快速開始(term++)，然后開始下一輪選舉

不同的服務(wù)器可能會在不同的時間發(fā)現(xiàn)term的變化，每一個server都會存儲一個current term的變量，每次server之間交流時都會帶上這個變量，如果一個server的current term比另外一個小，那就會換成大的term，如果一個candidate或是leader發(fā)現(xiàn)自己的term過時了，它會立刻變?yōu)閒ollower的狀態(tài)，如果一個server'收到了一個帶著舊的term的請求，它會拒絕該請求

Raftserver使用RPC來交流，主要用兩個RequestVote 和 AppendEntries，還有一個是用來傳輸snapshot的

5.2 Leader election

Raft 使用心跳包的機制來觸發(fā)選舉，leader會周期性發(fā)送AppendEntries的RPC但是不帶有任何log

entries來抑制follower觸發(fā)選舉，如果一個follower很長時間沒有收到心跳包(election timeout)，他會認為leader掛了，然后將自己的term++，進入Candidate狀態(tài)，想其它的servers發(fā)送RequestVoteRPC 開始選舉，并且會先投自己一票。選舉有三個結(jié)果：1.它贏了變成了leader；2.它輸了，另外一個服務(wù)器變成了leader；3.這輪選舉沒有選出leader

當(dāng)一個candidate收到超過半數(shù)的選票是，它就會變成leader，它會向所有的server發(fā)送心跳包確立自己的權(quán)威并且抑制其他的server發(fā)生選舉

當(dāng)一個candidate在等待投票的過程中，收到了其他server的AppendEntries RPC，如果該RPC中的term number 大于等于 candidate的term number，candidate認為leader已經(jīng)選出來了，就回退到follower的狀態(tài)。如果RPC中的term小于candidate的term，candidate 拒絕該RPC并且繼續(xù)保持在candidate狀態(tài)

第三種情況是，這輪term沒選出leader，因為可能有很多個candidate來分選票，導(dǎo)致沒有一個candidate獲得超過一半的選票，這時，candidate的選舉timer會超時，然后將term++，重新開始新的一輪選舉

Raft使用randomized elections timeout來確保split votes的情況很少出現(xiàn)，即使出現(xiàn)了，也可以使用randomized elections timeout來解決這個問題

最初raft的作者使用一種rank的機制，在選舉時低rank的服務(wù)器會給高rank的服務(wù)器讓步，但是這樣會有一些可用性的問題，并且調(diào)整了很多次都沒有完全解決，于是就換用了randomized retry 的方法

5.3 Log replication

[圖片上傳失敗...(image-f2507e-1652515917505)]

所有的機器上都有一個log，每一個log中的一格有一個index標志位置，里面會存儲一個entry和一個term號表示該entry是什么時候被leader received的。

leader會將client發(fā)給他的entry轉(zhuǎn)發(fā)給其他server，讓他們把entry加入log，當(dāng)leader收到了超過一半的server的回復(fù)時，這條log entry就是committed的狀態(tài)了，leader就會執(zhí)行entry，返回結(jié)果給client，并且通知其他server也執(zhí)行entry。leader會保存一個最大的已經(jīng)committed的index，并且會在AppendEntries RPC信息中帶上這個信息

[圖片上傳失敗...(image-8fc0b7-1652515917505)]

Raft的log有以下的性質(zhì)，構(gòu)成了Log Matching Property：

• If two entries in different logs have the same index and term, then they store the same command.
• If two entries in different logs have the same index and term, then the logs are identical in all preceding entries

第一點是因為，一個leader在一個term中最多只能在log的某個位置寫入一個entry，并且之后就不會修改了

第二點因為，leader在發(fā)送AppendEntries RPC時，leader會將new entry的上一條entry的term和index包含在RPC中，servers回去看該index里有沒有該term號的命令，如果沒找到，就會拒絕執(zhí)行new entry，也就是說，我一定要有上一條的log，我才可以把下一條log加進來

整個過程就像一個歸納的過程，因為一開始的狀態(tài)滿足Log Match Property，并且每一步都會保證它滿足Log Match Property，所以最后的狀態(tài)是只要server成功返回，那么該server從該index往前的命令都是和leader一樣的

有時候，leader接收了client的entry，然后在它將entry轉(zhuǎn)發(fā)給所有server之前就宕機了，這樣就有部分server沒有收到這個entry，就會造成不一致，這樣的情況會有很多，如下圖所示

[圖片上傳失敗...(image-d237bb-1652515917505)]

在Raft中，leader通過強制讓follower的log復(fù)制自己的log來解決不一致性，任何和leader log有沖突的地方都會用leader log覆蓋。為了實現(xiàn)這點，leader需要知道log和它在哪些地方都是相等的，然后將follower開始出現(xiàn)不相等的地方全部刪除，然后將leader后面的log entry全部發(fā)給follower。這些事情都是在AppendEntries RPC中完成的，leader會為每一個follower維護一個nextIndex變量，指示下一步該發(fā)哪個index的log給follower，leader會首先將這個值初始化為自己上一個寫入entry的index + 1,在Figure 7 中就是11.如果一個follower發(fā)現(xiàn)自己的log和leader的不一樣，那么他就reject該AppendEntries RPC，然后leader會將nextIndex--，然后重試，直到成功為止，哪此時的位置就是它們兩個可以達成共識的位置，然后就可以將leader 后續(xù)的log發(fā)給它來同步了

5.4 Safety

前面的章節(jié)講述了如何選舉和如何做log replication，但是這樣還是會有問題，例如一個follower可能宕機了，然后錯過了一些entry，然后它被選成了leader，于是它用自己的log來強迫別人跟它同步，這樣就會出問題了。

問題出在將這樣的follower選成了leader，所以這章添加了一些限制，關(guān)于什么樣的follower才有資格成為leader，這些限制保證leader有Leader Completeness Property這個性質(zhì)，即對于一個給定term的entry，你可以在term號更高的leader中找到它

5.4.1 Election restriction

在任何leader-based的共識算法中，leader最終一定會有所有的committed log entries，在一些算法中，leader開始可以允許只有一部分committed entries，但是在選舉中或是選舉后的一段時間，leader會有所有的committed log entries，但這種方法引入了大量額外的機制和復(fù)雜性。Raft使用一個更簡單的機制：它保證leader擁有上個term所有的committed log entries，這樣就不需要將log entry發(fā)給leader，數(shù)據(jù)只會有l(wèi)eader流向follower

Raft在投票的過程中實現(xiàn)上面這一點，一個candidate只有包含了所有的committed log entries才能贏得選舉，并且它必須獲得超半數(shù)的follower的支持，這就意味了每個committed log entry至少在這些半數(shù)服務(wù)器中出現(xiàn)過一次。如果該candidate的log狀態(tài)至少和它們一樣新(at least as up-to-date as any other log)，那么它就會包含所有的committed log entries，也就可以贏得選舉。在Candidate發(fā)送RequestVote RPC時，會將自己的log最大的index和term發(fā)過去，follower會那這些和自己做比較，如果哪個log的term大，哪個就更新，如果term一樣，那更長的log(index更大)就更新

5.4.2 Committing entries from previous terms

假如一個leader將entry復(fù)制到了大半部分的服務(wù)器，然后在提交之前掛了，新的leader選出了，然后新的leader會嘗試完成那個entry的replcation，新的leader沒法知道這個entry是否被提交了，F(xiàn)igure 8 展示了這樣的場景：log entry已經(jīng)存儲在大半的服務(wù)器當(dāng)中，但是還是被重寫了。
[圖片上傳失敗...(image-95c8ba-1652581155892)]

為了解決這個問題，Raft不會通過計算副本數(shù)量的方式來提交一起term的entry，只有當(dāng)前term的entry才能通過這種方式提交，一旦leader提交了一個當(dāng)前term的entry，根據(jù)Log Matching Property之前的log都會算作提交，所以上個term的log也算是間接被提交了

Raft 在提交規(guī)則上引入了額外的復(fù)雜性，因為log entry會保持原來的term當(dāng)一個leader在重復(fù)以前term的entry時

5.4.3 Safety argument

[站外圖片上傳中...(image-ca88b7-1652515917505)]

該小節(jié)作者通過反證法證明了Raft的Leader Completeness是成立的，假設(shè)term T的leader提交了一個log，但是這個log首次不在term U(U > T)的leader中，也就是說在T之后U之前的leader都有這條entry

1. 在leaderU 選舉的時候，它一定沒有這個entry，因為leader是append-only的，所以如果一旦它成為了leader，他就不會覆蓋或者刪除自己的log
2. leaderT將這個log entry成功復(fù)制到了過半的服務(wù)器中，leaderU獲得了過半服務(wù)器的投票，所以至少有一個server同時有這個log entry并且投票給了leaderU，如Figure 9所示，這個voter(Figure 9 中的S3)是推導(dǎo)出矛盾的關(guān)鍵
   [站外圖片上傳中...(image-3600c8-1652515917505)]
3. voter一定已經(jīng)accepted leaderT的log entry在投票給U之前，否則因為U比T大，voter會拒絕accept 該log entry
4. voter 在給leaderU投票時還存著這個entry，因為每個中間的leader都有這個entry(基于假設(shè)),leader不會刪除entries，followers只會在和leader沖突時刪除entry
5. voter投票給了leaderU，說明leaderU的log至少和voter的一樣新，這會導(dǎo)致兩個矛盾之一
6. 首先，如果voter和leaderU有一樣的last log term，那么leaderU的log至少和voter的一樣新，所以它也會有該entry，這是一個矛盾
7. 否則，leaderU的last log term一定要比voter的大(根據(jù)選舉規(guī)則)，U也比T大，因為voter的last log term至少是T，因為它有T的那條entry。創(chuàng)建了leaderU最后一條日志的leader也一定有那條leaderT的entry(基于假設(shè))，然后，基于Log Matching Property，LeaderU的log也會有那條entry，得到另一個矛盾

Log Matching Property

If two entries in different logs have the same index and term, then they store the same command.

If two entries in different logs have the same index and term, then the logs are identical in all preceding entries

1. 上述過程證明了矛盾，所以比term T大的leader必須有所有在Term T提交的entry
2. Log Matching Property保證了未來的leader會有間接提交的entry，例如Figure 8(d)的index2位置

有了Leader Completeness的性質(zhì)，我們可以證明Figure 3中的State Machine Saftey Property，即：如果一個服務(wù)器將給定index的日志條目應(yīng)用到了其狀態(tài)機中，那么不會有另一臺應(yīng)用了index相同但內(nèi)容不同的日志條目的服務(wù)器。當(dāng)服務(wù)器將一個entry應(yīng)用到其狀態(tài)機時，從這條entry往前所有的entry都應(yīng)該與leader相同（因為Log Matching Property只要index i處的entry相同，那么之前的entry都相同），且該條目必須是被提交的。現(xiàn)在考慮任何服務(wù)器都應(yīng)用了給定index的日志條目的最小的term；“日志完整性性質(zhì)”確保了所有term更高的leader都保存了相同的這個條目，所以在之后的term中應(yīng)用了該條目的服務(wù)器將會應(yīng)用相同的值。因此，“狀態(tài)機安全性性質(zhì)”成立。

最后，Raft要求服務(wù)器按照日志index的順序應(yīng)用條目。結(jié)合“狀態(tài)機安全性質(zhì)”，這意味著服務(wù)器會精確地按照相同的順序?qū)⑾嗤娜罩緱l目應(yīng)用到它們的狀態(tài)機中。

5.5 Follower and candidate crashes

之前的章節(jié)都在關(guān)注leader的宕機，follower和candidate的宕機要容易的多，都是用相同的辦法處理的。如果一個follower或是candidate宕機了，這樣發(fā)給他的RequestVote and AppendEntries RPCs 就會失敗，發(fā)送者會不斷的重試直到成功，等到宕機的server重啟，就會收到相同的請求，因為RPC請求時冪等的，所以如果一些server已經(jīng)完成了請求，但是沒來及回復(fù)(例如已經(jīng)將entry加到自己log中，然后就宕機了)，那也沒有什么問題。

5.6 Timing and availability

Raft要求Safety屬性不能依賴于timing(事件發(fā)生的時間點)，也就是說不管時間在什么時間點發(fā)生，都要保證Safety(此處的safety指的時一致性)。但是availability會受到timing的影響。

例如在leader election中，要滿足下面的要求：

broadcastTime指定的server發(fā)送RPC并且收到回復(fù)的平均時間，electionTimeout指的是一場選舉最多持續(xù)多久，MTBF指的是單臺server發(fā)生兩次故障的平均間隔時間，broadcastTime要比electionTimeout小一個數(shù)量級，這樣leader才可以通過心跳包來有效抑制follower發(fā)生選舉，electionTimeout要比MTBF少幾個數(shù)量級的時間。當(dāng)leader宕機時，系統(tǒng)會在electionTimeout的時間段內(nèi)不可用

7. Log compaction

Raft的log會隨著時間線的延長而無限制的增加，所以我們需要定期丟棄過時的log。Raft使用snapshot來解決這一個問題，一個快照記錄了整個系統(tǒng)的狀態(tài)，在這個快照記錄點之前的所有l(wèi)og就可以刪除

下圖展示了Raft的log snapshot

[站外圖片上傳中...(image-32770b-1652515917505)]

如上圖所示，快照會保存一部分metadata：

• last included index：快照最后一個log的index
• last included term：快照最后一個log的term

保存這兩個數(shù)據(jù)是因為這兩個在AppendEntries中需要用到

當(dāng)leader已經(jīng)丟棄了快照之前的log，但是他需要將log發(fā)給follower的時候，leader會偶爾將自己的快照發(fā)給服務(wù)器。正常情況下不會有這個問題，除非是一個落后很多的server或是一個剛剛加入集群的server

leader使用一個叫做InstallSnapshot的RPC來發(fā)送快照給follower，如下所示

[圖片上傳失敗...(image-2465e5-1652581155892)]

當(dāng)server收到leader的快照中包含了新的信息時，server就丟棄自己的log，并且使用leader的快照

如果收到的快照只是自己log的前綴，那么會刪除該創(chuàng)建快照時的所有l(wèi)og(因為log的信息都在快照里面了)，但是會保留快照后面的log

曾經(jīng)的設(shè)計只允許leader發(fā)送快照給follower，但是這樣要傳輸所有的快照很浪費帶寬，使快照操作變慢，并且這樣會增加leader設(shè)計的復(fù)雜度

還有另外兩個性能問題，第一個是創(chuàng)建快照的頻率，不能太快也不能太慢，第二個是寫一個快照要花很多時間，解決方法是使用copy-on-write

8. Client interaction

這個章節(jié)講述了Raft是如何與client交互的，以及如何實現(xiàn)線性一致性(linearizable)的語義

client會先隨機找一臺server，如果那臺server不是leader，就會拒絕請求并給client指出leader是誰

Raft的一個設(shè)計目標是實現(xiàn)線性一致性語義(each operation appears to execute instantaneously, exactly once, at some point between its invocation and its response). 但是Raft可能執(zhí)行一個指令很多遍，例如如果leader以及提交了log entry，在回復(fù)client之前掛了，client會向新的leader重試，導(dǎo)致執(zhí)行被執(zhí)行兩遍。解決方案是給每一個client的請求附加一個序列號，如果server發(fā)現(xiàn)這個請求的序列號已經(jīng)被執(zhí)行了，那么它就不會重復(fù)執(zhí)行這條指令

上面討論的都是寫操作(需要有l(wèi)og的)，如果是只讀操作，也就是不會更改系統(tǒng)狀態(tài)的操作，那就可以不用加到log中。但是，如果沒有保障措施，會讀到舊數(shù)據(jù)，因為leader在處理client時，可能自己已經(jīng)不是leader了。文中提出了兩個措施來解決這個問題，第一，leader需要知道哪些entry是已經(jīng)提交的，Leader Completeness Property可以保證leader term之前的entry都是已經(jīng)提交的，但是在剛剛成為leader時，他并不清楚是哪些（我認為是leader會有所有的committed log，但是不是leader的所有l(wèi)og都是committed的 ）。Raft通過leader在它term的開始發(fā)送一個no-op entry來獲取信息。第二，leader在處理只讀請求前必須確認自己還是不是leader，這個需求通過心跳包來完成