復(fù)制狀態(tài)機(jī)
共識(shí)算法是從復(fù)制狀態(tài)機(jī)的背景下提出的雀扶。在這種方法中荠卷，一組服務(wù)器上的狀態(tài)機(jī)產(chǎn)生相同狀態(tài)的副本幻林，并且在一些機(jī)器宕掉的情況下也可以繼續(xù)運(yùn)行。復(fù)制狀態(tài)機(jī)在分布式系統(tǒng)中被用于解決很多容錯(cuò)的問(wèn)題镀赌。
復(fù)制狀態(tài)機(jī)通常都是基于復(fù)制日志實(shí)現(xiàn)的氯哮，如上圖。每一個(gè)服務(wù)器存儲(chǔ)一個(gè)包含一系列指令的日志商佛，并且按照日志的順序進(jìn)行執(zhí)行喉钢。每一個(gè)日志都按照相同的順序包含相同的指令，所以每一個(gè)服務(wù)器都執(zhí)行相同的指令序列良姆。因?yàn)槊總€(gè)狀態(tài)機(jī)都是確定的肠虽，每一次執(zhí)行操作都產(chǎn)生相同的狀態(tài)和同樣的序列。
保證復(fù)制日志相同就是共識(shí)算法的工作了玛追。在一臺(tái)服務(wù)器上税课，共識(shí)模塊接收客戶(hù)端發(fā)送來(lái)的指令然后增加到自己的日志中去。它和其他服務(wù)器上的共識(shí)模塊進(jìn)行通信來(lái)保證每一個(gè)服務(wù)器上的日志最終都以相同的順序包含相同的請(qǐng)求豹缀，盡管有些服務(wù)器會(huì)宕機(jī)伯复。一旦指令被正確的復(fù)制慨代，每一個(gè)服務(wù)器的狀態(tài)機(jī)按照日志順序處理他們邢笙，然后輸出結(jié)果被返回給客戶(hù)端。因此侍匙，服務(wù)器集群看起來(lái)形成一個(gè)高可靠的狀態(tài)機(jī)氮惯。
實(shí)際系統(tǒng)中使用的共識(shí)算法通常含有以下特性：
- 安全性保證（絕對(duì)不會(huì)返回一個(gè)錯(cuò)誤的結(jié)果）：在非拜占庭錯(cuò)誤情況下，包括網(wǎng)絡(luò)延遲想暗、分區(qū)妇汗、丟包、冗余和亂序等錯(cuò)誤都可以保證正確说莫。
- 可用性：集群中只要有大多數(shù)的機(jī)器可運(yùn)行并且能夠相互通信杨箭、和客戶(hù)端通信，就可以保證可用储狭。因此互婿，一個(gè)典型的包含 5 個(gè)節(jié)點(diǎn)的集群可以容忍兩個(gè)節(jié)點(diǎn)的失敗捣郊。服務(wù)器被停止就認(rèn)為是失敗。他們當(dāng)有穩(wěn)定的存儲(chǔ)的時(shí)候可以從狀態(tài)中恢復(fù)回來(lái)并重新加入集群慈参。
- 不依賴(lài)時(shí)序來(lái)保證一致性：物理時(shí)鐘錯(cuò)誤或者極端的消息延遲在可能只有在最壞情況下才會(huì)導(dǎo)致可用性問(wèn)題呛牲。
- 通常情況下，一條指令可以盡可能快的在集群中大多數(shù)節(jié)點(diǎn)響應(yīng)一輪遠(yuǎn)程過(guò)程調(diào)用時(shí)完成驮配。小部分比較慢的節(jié)點(diǎn)不會(huì)影響系統(tǒng)整體的性能娘扩。
Raft特性
- 強(qiáng)領(lǐng)導(dǎo)者：和其他共識(shí)算法相比，Raft 使用一種更強(qiáng)的領(lǐng)導(dǎo)能力形式壮锻。比如琐旁，日志條目只從領(lǐng)導(dǎo)者發(fā)送給其他的服務(wù)器。這種方式簡(jiǎn)化了對(duì)復(fù)制日志的管理并且使得 Raft 算法更加易于理解猜绣。
- 領(lǐng)導(dǎo)選舉：Raft 算法使用一個(gè)隨機(jī)計(jì)時(shí)器來(lái)選舉領(lǐng)導(dǎo)者旋膳。這種方式只是在任何共識(shí)算法都必須實(shí)現(xiàn)的心跳機(jī)制上增加了一點(diǎn)機(jī)制。在解決沖突的時(shí)候會(huì)更加簡(jiǎn)單快捷途事。
- 關(guān)系調(diào)整：Raft 使用一種共同一致的方法來(lái)處理集群成員變換的問(wèn)題验懊，在這種方法中，兩種不同的配置都要求的大多數(shù)機(jī)器會(huì)重疊尸变。這就使得集群在成員變換的時(shí)候依然可以繼續(xù)工作义图。
Raft設(shè)計(jì)
Raft 通過(guò)選舉一個(gè)領(lǐng)導(dǎo)人，然后給予他全部的管理復(fù)制日志的責(zé)任來(lái)實(shí)現(xiàn)一致性召烂。領(lǐng)導(dǎo)人從客戶(hù)端接收日志條目碱工，把日志條目復(fù)制到其他服務(wù)器上，并且當(dāng)保證安全性的時(shí)候告訴其他的服務(wù)器應(yīng)用日志條目到他們的狀態(tài)機(jī)中奏夫。
擁有一個(gè)領(lǐng)導(dǎo)人大大簡(jiǎn)化了對(duì)復(fù)制日志的管理怕篷。例如，領(lǐng)導(dǎo)人可以決定新的日志條目需要放在日志中的什么位置而不需要和其他服務(wù)器商議酗昼，并且數(shù)據(jù)都從領(lǐng)導(dǎo)人流向其他服務(wù)器廊谓。而且領(lǐng)導(dǎo)人可以宕機(jī)，可以和其他服務(wù)器失去連接麻削，這時(shí)一個(gè)新的領(lǐng)導(dǎo)人會(huì)被選舉出來(lái)蒸痹。
通過(guò)領(lǐng)導(dǎo)人的方式，Raft 將一致性問(wèn)題分解成了三個(gè)相對(duì)獨(dú)立的子問(wèn)題：
- 領(lǐng)導(dǎo)選舉：當(dāng)先存的領(lǐng)導(dǎo)人宕機(jī)的時(shí)候呛哟，一個(gè)新的領(lǐng)導(dǎo)人需要被選舉出來(lái)
- 日志復(fù)制：領(lǐng)導(dǎo)人必須從客戶(hù)端接收日志然后復(fù)制到集群中的其他節(jié)點(diǎn)叠荠，并且強(qiáng)制要求其他節(jié)點(diǎn)的日志保持和自己相同。
- 安全性：在 Raft 中安全性的關(guān)鍵是在下表中展示的狀態(tài)機(jī)安全：如果有任何的服務(wù)器節(jié)點(diǎn)已經(jīng)應(yīng)用了一個(gè)確定的日志條目到它的狀態(tài)機(jī)中扫责，那么其他服務(wù)器節(jié)點(diǎn)不能在同一個(gè)日志索引位置應(yīng)用一個(gè)不同的指令榛鼎。
| 特性 | 解釋 |
|---|---|
| 選舉安全特性 | 對(duì)于一個(gè)給定的任期號(hào)，最多只會(huì)有一個(gè)領(lǐng)導(dǎo)人被選舉出來(lái) |
| 領(lǐng)導(dǎo)人只附加原則 | 領(lǐng)導(dǎo)人絕對(duì)不會(huì)刪除或者覆蓋自己的日志，只會(huì)增加 |
| 日志匹配原則 | 如果兩個(gè)日志在相同的索引位置的日志條目的任期號(hào)相同者娱，那么我們就認(rèn)為這個(gè)日志從頭到這個(gè)索引位置之間全部完全相同 |
| 領(lǐng)導(dǎo)人完全特性 | 如果某個(gè)日志條目在某個(gè)任期號(hào)中已經(jīng)被提交蜘渣，那么這個(gè)條目必然出現(xiàn)在更大任期號(hào)的所有領(lǐng)導(dǎo)人中 |
| 狀態(tài)機(jī)安全特性 | 如果一個(gè)領(lǐng)導(dǎo)人已經(jīng)在給定的索引值位置的日志條目應(yīng)用到狀態(tài)機(jī)中，那么其他任何的服務(wù)器在這個(gè)索引位置不會(huì)提交一個(gè)不同的日志 |
狀態(tài)：
| 狀態(tài) | 所有服務(wù)器上持久存在的 |
|---|---|
| currentTerm | 服務(wù)器最后一次知道的任期號(hào)（初始化為 0肺然，持續(xù)遞增） |
| votedFor | 在當(dāng)前獲得選票的候選人的 Id |
| log[] | 日志條目集蔫缸；每一個(gè)條目包含一個(gè)用戶(hù)狀態(tài)機(jī)執(zhí)行的指令，和收到時(shí)的任期號(hào) |
| 狀態(tài) | 所有服務(wù)器上經(jīng)常變的 |
|---|---|
| commitIndex | 已知的最大的已經(jīng)被提交的日志條目的索引值 |
| lastApplied | 最后被應(yīng)用到狀態(tài)機(jī)的日志條目索引值（初始化為 0际起，持續(xù)遞增） |
| 狀態(tài) | 在領(lǐng)導(dǎo)人里經(jīng)常改變的 （選舉后重新初始化） |
|---|---|
| nextIndex[] | 對(duì)于每一個(gè)服務(wù)器拾碌，需要發(fā)送給他的下一個(gè)日志條目的索引值（初始化為領(lǐng)導(dǎo)人最后索引值加一） |
| matchIndex[] | 對(duì)于每一個(gè)服務(wù)器，已經(jīng)復(fù)制給他的日志的最高索引值 |
附加日志 RPC：
由領(lǐng)導(dǎo)人負(fù)責(zé)調(diào)用來(lái)復(fù)制日志指令街望；也會(huì)用作heartbeat
| 參數(shù) | 解釋 |
|---|---|
| term | 領(lǐng)導(dǎo)人的任期號(hào) |
| leaderId | 領(lǐng)導(dǎo)人的 Id校翔，以便于跟隨者重定向請(qǐng)求 |
| prevLogIndex | 新的日志條目上一條的索引值 |
| prevLogTerm | prevLogIndex 條目的任期號(hào) |
| entries[] | 準(zhǔn)備存儲(chǔ)的日志條目（表示心跳時(shí)為空；一次性發(fā)送多個(gè)是為了提高效率） |
| leaderCommit | 領(lǐng)導(dǎo)人已經(jīng)提交的日志的索引值 |
| 返回值 | 解釋 |
|---|---|
| term | 當(dāng)前的任期號(hào)灾前，用于領(lǐng)導(dǎo)人去更新自己 |
| success | 跟隨者包含了匹配上 prevLogIndex 和 prevLogTerm 的日志時(shí)為真 |
接收者實(shí)現(xiàn)：
- 如果
term < currentTerm就返回 false - 如果日志在 prevLogIndex 位置處的日志條目的任期號(hào)和 prevLogTerm 不匹配防症，則返回 false
- 如果已經(jīng)已經(jīng)存在的日志條目和新的產(chǎn)生沖突（相同偏移量但是任期號(hào)不同），刪除這一條和之后所有的
- 附加任何在已有的日志中不存在的條目
- 如果
leaderCommit > commitIndex哎甲，令 commitIndex 等于 leaderCommit 和 新日志條目索引值中較小的一個(gè)
請(qǐng)求投票 RPC：
由候選人負(fù)責(zé)調(diào)用用來(lái)征集選票（5.2 節(jié)）
| 參數(shù) | 解釋 |
|---|---|
| term | 候選人的任期號(hào) |
| candidateId | 請(qǐng)求選票的候選人的 Id |
| lastLogIndex | 候選人的最后日志條目的索引值 |
| lastLogTerm | 候選人最后日志條目的任期號(hào) |
| 返回值 | 解釋 |
|---|---|
| term | 當(dāng)前任期號(hào)蔫敲，以便于候選人去更新自己的任期號(hào) |
| voteGranted | 候選人贏得了此張選票時(shí)為真 |
接收者實(shí)現(xiàn)：
- 如果
term < currentTerm返回 false （5.2 節(jié)） - 如果 votedFor 為空或者就是 candidateId，并且候選人的日志也自己一樣新炭玫，那么就投票給他
所有服務(wù)器需遵守的規(guī)則：
所有服務(wù)器：
- 如果
commitIndex > lastApplied奈嘿，那么就 lastApplied 加一，并把log[lastApplied]應(yīng)用到狀態(tài)機(jī)中 - 如果接收到的 RPC 請(qǐng)求中吞加，任期號(hào)
T > currentTerm裙犹，那么就令 currentTerm 等于 T，并切換狀態(tài)為跟隨者
跟隨者：
- 響應(yīng)來(lái)自候選人和領(lǐng)導(dǎo)者的請(qǐng)求
- 如果在超過(guò)選舉超時(shí)時(shí)間的情況之前都沒(méi)有收到領(lǐng)導(dǎo)人的心跳衔憨，或者是候選人請(qǐng)求投票的叶圃，就自己變成候選人
候選人：
- 在轉(zhuǎn)變成候選人后就立即開(kāi)始選舉過(guò)程
- 自增當(dāng)前的任期號(hào)（currentTerm）
- 給自己投票
- 重置選舉超時(shí)計(jì)時(shí)器
- 發(fā)送請(qǐng)求投票的 RPC 給其他所有服務(wù)器
- 如果接收到大多數(shù)服務(wù)器的選票，那么就變成領(lǐng)導(dǎo)人
- 如果接收到來(lái)自新的領(lǐng)導(dǎo)人的附加日志 RPC践图，轉(zhuǎn)變成跟隨者
- 如果選舉過(guò)程超時(shí)掺冠，再次發(fā)起一輪選舉
領(lǐng)導(dǎo)人：
- 一旦成為領(lǐng)導(dǎo)人：發(fā)送空的附加日志 RPC（心跳）給其他所有的服務(wù)器；在一定的空余時(shí)間之后不停的重復(fù)發(fā)送平项，以阻止跟隨者超時(shí)（5.2 節(jié)）
- 如果接收到來(lái)自客戶(hù)端的請(qǐng)求：附加條目到本地日志中赫舒，在條目被應(yīng)用到狀態(tài)機(jī)后響應(yīng)客戶(hù)端（5.3 節(jié)）
- 如果對(duì)于一個(gè)跟隨者，最后日志條目的索引值大于等于 nextIndex闽瓢，那么：發(fā)送從 nextIndex 開(kāi)始的所有日志條目：
- 如果成功：更新相應(yīng)跟隨者的 nextIndex 和 matchIndex
- 如果因?yàn)槿罩静灰恢露。瑴p少 nextIndex 重試
- 如果存在一個(gè)滿(mǎn)足
N > commitIndex的 N心赶，并且大多數(shù)的matchIndex[i] ≥ N成立扣讼，并且log[N].term == currentTerm成立，那么令 commitIndex 等于這個(gè) N
Raft日志一致性
日志匹配特性
- 如果在不同的日志中的兩個(gè)條目擁有相同的索引和任期號(hào)缨叫，那么他們存儲(chǔ)了相同的指令椭符。
- 如果在不同的日志中的兩個(gè)條目擁有相同的索引和任期號(hào)荔燎，那么他們之前的所有日志條目也全部相同。
第一個(gè)特性來(lái)自這樣的一個(gè)事實(shí)销钝，領(lǐng)導(dǎo)人最多在指定的一個(gè)日志索引位置創(chuàng)建一條日志條目有咨，同時(shí)日志條目在日志中的位置也從來(lái)不會(huì)改變。第二個(gè)特性由附加日志 RPC 的一個(gè)簡(jiǎn)單的一致性檢查所保證蒸健。在發(fā)送附加日志 RPC 的時(shí)候座享，領(lǐng)導(dǎo)人會(huì)把新的日志條目緊接著之前的條目的索引位置和任期號(hào)包含在里面。如果跟隨者在它的日志中找不到包含相同索引位置和任期號(hào)的條目似忧，那么他就會(huì)拒絕接收新的日志條目渣叛。一致性檢查就像一個(gè)歸納步驟：一開(kāi)始空的日志狀態(tài)肯定是滿(mǎn)足日志匹配特性的，然后一致性檢查保護(hù)了日志匹配特性當(dāng)日志擴(kuò)展的時(shí)候盯捌。因此淳衙，每當(dāng)附加日志 RPC 返回成功時(shí)，領(lǐng)導(dǎo)人就知道跟隨者的日志一定是和自己相同的了饺著。
在 Raft 算法中箫攀，領(lǐng)導(dǎo)人處理不一致是通過(guò)強(qiáng)制跟隨者直接復(fù)制自己的日志來(lái)解決了。這意味著在跟隨者中的沖突的日志條目會(huì)被領(lǐng)導(dǎo)人的日志覆蓋幼衰。領(lǐng)導(dǎo)人必須找到最后兩者達(dá)成一致的地方匠童，然后刪除從那個(gè)點(diǎn)之后的所有日志條目，發(fā)送自己的日志給跟隨者塑顺。所有的這些操作都在進(jìn)行附加日志 RPCs 的一致性檢查時(shí)完成汤求。領(lǐng)導(dǎo)人針對(duì)每一個(gè)跟隨者維護(hù)了一個(gè) nextIndex，這表示下一個(gè)需要發(fā)送給跟隨者的日志條目的索引地址严拒。當(dāng)一個(gè)領(lǐng)導(dǎo)人剛獲得權(quán)力的時(shí)候扬绪，他初始化所有的 nextIndex 值為自己的最后一條日志的index加1（圖 7 中的 11）。如果一個(gè)跟隨者的日志和領(lǐng)導(dǎo)人不一致裤唠，那么在下一次的附加日志 RPC 時(shí)的一致性檢查就會(huì)失敗挤牛。在被跟隨者拒絕之后，領(lǐng)導(dǎo)人就會(huì)減小 nextIndex 值并進(jìn)行重試种蘸。最終 nextIndex 會(huì)在某個(gè)位置使得領(lǐng)導(dǎo)人和跟隨者的日志達(dá)成一致墓赴。當(dāng)這種情況發(fā)生，附加日志 RPC 就會(huì)成功航瞭，這時(shí)就會(huì)把跟隨者沖突的日志條目全部刪除并且加上領(lǐng)導(dǎo)人的日志诫硕。一旦附加日志 RPC 成功，那么跟隨者的日志就會(huì)和領(lǐng)導(dǎo)人保持一致刊侯，并且在接下來(lái)的任期里一直繼續(xù)保持章办。
領(lǐng)導(dǎo)人知道一條當(dāng)前任期內(nèi)的日志記錄是可以被提交的，只要它被存儲(chǔ)到了大多數(shù)的服務(wù)器上。如果一個(gè)領(lǐng)導(dǎo)人在提交日志條目之前崩潰了藕届，未來(lái)后續(xù)的領(lǐng)導(dǎo)人會(huì)繼續(xù)嘗試復(fù)制這條日志記錄挪蹭。然而，一個(gè)領(lǐng)導(dǎo)人不能斷定一個(gè)之前任期里的日志條目被保存到大多數(shù)服務(wù)器上的時(shí)候就一定已經(jīng)提交了休偶。上圖展示了一種情況梁厉，一條已經(jīng)被存儲(chǔ)到大多數(shù)節(jié)點(diǎn)上的老日志條目，也依然有可能會(huì)被未來(lái)的領(lǐng)導(dǎo)人覆蓋掉踏兜。
上圖的時(shí)間序列展示了為什么領(lǐng)導(dǎo)人無(wú)法通過(guò)老的日志的任期號(hào)來(lái)判斷其提交狀態(tài)词顾。在 (a) 中，S1 是領(lǐng)導(dǎo)者庇麦，部分的復(fù)制了索引位置 2 的日志條目计技。在 (b) 中，S1 崩潰了山橄，然后 S5 在任期 3 里通過(guò) S3垮媒、S4 和自己的選票贏得選舉，然后從客戶(hù)端接收了一條不一樣的日志條目放在了索引 2 處航棱。然后到 (c)睡雇，S5 又崩潰了；S1 重新啟動(dòng)饮醇，選舉成功它抱，開(kāi)始復(fù)制日志。在這時(shí)朴艰，來(lái)自任期 2 的那條日志已經(jīng)被復(fù)制到了集群中的大多數(shù)機(jī)器上观蓄，但是還沒(méi)有被提交。如果 S1 在 (d) 中又崩潰了祠墅，S5 可以重新被選舉成功（通過(guò)來(lái)自 S2侮穿，S3 和 S4 的選票），然后覆蓋了他們?cè)谒饕?2 處的日志毁嗦。但是亲茅，在崩潰之前，如果 S1 在自己的任期里復(fù)制了日志條目到大多數(shù)機(jī)器上狗准，如 (e) 中克锣，然后這個(gè)條目就會(huì)被提交（S5 就不可能選舉成功）。 在這個(gè)時(shí)候腔长，之前的所有日志就會(huì)被正常提交處理袭祟。
