一致性协议raft详解（二）：安全性
一致性協(xié)議raft詳解（二）：安全性
- 前言
- 安全性
- log recovery
- 為什么no-op能解決不一致的問(wèn)題？
- 成員變更
- Single mempership change
- raft用到的隨機(jī)時(shí)間
- raft 腦裂
- 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)前
- 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，但未復(fù)制到 Follower 節(jié)點(diǎn)
- 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，成功復(fù)制到 Follower 所有節(jié)點(diǎn)，但還未向 Leader 響應(yīng)接收
- 數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，成功復(fù)制到 Follower 部分節(jié)點(diǎn)，但還未向 Leader 響應(yīng)接收
前言
有關(guān)一致性協(xié)議的資料網(wǎng)上有很多，當(dāng)然錯(cuò)誤也有很多。筆者在學(xué)習(xí)的過(guò)程中走了不少?gòu)澛贰，F(xiàn)在回過(guò)頭來(lái)看，最好的學(xué)習(xí)資料就是Leslie Lamport和Diego Ongaro的數(shù)篇論文、Ongaro在youtube上發(fā)的三個(gè)視頻講解，以及何登成的ppt。
本系列文章是只是筆者在學(xué)習(xí)一致性協(xié)議過(guò)程中的摘抄和總結(jié)，有疏漏之處敬請(qǐng)諒解，歡迎討論。
安全性
raft的log replication機(jī)制并不能充分的保證每一個(gè)狀態(tài)機(jī)會(huì)按照相同的順序執(zhí)行相同的指令。例如，一個(gè)follower可能會(huì)進(jìn)入不可用狀態(tài)同時(shí)leader已經(jīng)提交了若干的日志條目，然后這個(gè)follower可能會(huì)被選舉為leader并且覆蓋這些日志條目；因此，不同的狀態(tài)機(jī)可能會(huì)執(zhí)行不同的指令序列。
我們通過(guò)在leader election增加限制來(lái)完善raft算法。在任何基于leader的一致性算法中，leader都必須存儲(chǔ)所有已經(jīng)提交的日志條目（或者通過(guò)額外的機(jī)制保證leader丟失的日志條目可以同步給leader）。Raft 使用了一種更加簡(jiǎn)單的方法，它可以保證所有之前的任期號(hào)中已經(jīng)提交的日志條目在選舉的時(shí)候都會(huì)出現(xiàn)在新的leader中，不需要傳送這些日志條目給leader。這意味著日志條目的傳送是單向的，只從leader傳給跟隨者，并且leader從不會(huì)覆蓋自身本地日志中已經(jīng)存在的條目。
**由于raft節(jié)點(diǎn)中的日志是順序添加的，那么raft在leader election的時(shí)候通過(guò)比較兩份日志中最后一條日志目錄的索引號(hào)index和任期號(hào)term，就可以判斷出誰(shuí)的日志更新。**只有最新的人才有權(quán)利作為leader。候選人為了贏得選舉必須聯(lián)系集群中的大部分節(jié)點(diǎn)，這意味著每一個(gè)已經(jīng)提交額度日志條目至少會(huì)存在于這些節(jié)點(diǎn)中的至少一個(gè)上。如果候選人的日志至少和大多數(shù)的服務(wù)器節(jié)點(diǎn)一樣新，那么他一定持有了所有已經(jīng)提交的日志條目。
log recovery
以下摘自baidu braft文章
Log Recovery這里分為current Term修復(fù)和prev Term修復(fù)，Log Recovery就是要保證一定已經(jīng)Committed的數(shù)據(jù)不會(huì)丟失，未Committed的數(shù)據(jù)轉(zhuǎn)變?yōu)镃ommitted，但不會(huì)因?yàn)樾迯?fù)過(guò)程中斷又重啟而影響節(jié)點(diǎn)之間一致性。
- current Term修復(fù)主要是解決某些Follower節(jié)點(diǎn)重啟加入集群，或者是新增Follower節(jié)點(diǎn)加入集群，Leader需要向Follower節(jié)點(diǎn)傳輸漏掉的Log Entry，如果Follower需要的Log Entry已經(jīng)在Leader上Log Compaction清除掉了，Leader需要將上一個(gè)Snapshot和其后的Log Entry傳輸給Follower節(jié)點(diǎn)。
- prev Term修復(fù)主要是在保證Leader切換前后數(shù)據(jù)的一致性。通過(guò)上面RAFT的選主可以看出，每次選舉出來(lái)的Leader一定包含已經(jīng)committed的數(shù)據(jù)（抽屜原理，選舉出來(lái)的Leader是多數(shù)中數(shù)據(jù)最新的，一定包含已經(jīng)在多數(shù)節(jié)點(diǎn)上commit的數(shù)據(jù)），新的Leader將會(huì)覆蓋其他節(jié)點(diǎn)上不一致的數(shù)據(jù)。雖然新選舉出來(lái)的Leader一定包括上一個(gè)Term的Leader已經(jīng)Committed的Log Entry，但是可能也包含上一個(gè)Term的Leader未Committed的Log Entry。這部分Log Entry需要轉(zhuǎn)變?yōu)镃ommitted，相對(duì)比較麻煩，需要考慮Leader多次切換且未完成Log Recovery，需要保證最終提案是一致的，確定的。 **RAFT中增加了一個(gè)約束：對(duì)于之前Term的未Committed數(shù)據(jù)，修復(fù)到多數(shù)節(jié)點(diǎn)，且在新的Term下至少有一條新的Log Entry被復(fù)制或修復(fù)到多數(shù)節(jié)點(diǎn)之后，才能認(rèn)為之前未Committed的Log Entry轉(zhuǎn)為Committed。**下圖就是一個(gè)prev Term Recovery的過(guò)程：
為了避免4-1中的現(xiàn)象，協(xié)議又強(qiáng)化了一個(gè)限制：
- 只有當(dāng)前 Term 的 LogEntry 提交條件為：滿足多數(shù)派響應(yīng)之后（一半以上節(jié)點(diǎn) Append LogEntry 到日志）設(shè)置為 commit；
- 前一輪 Term 未 Commit 的 LogEntry 的 Commit 依賴于高輪 Term LogEntry 的 Commit。
也就是說(shuō)，我們要通過(guò)提交 NO-OP LogEntry 提交系統(tǒng)可用性
在 Leader 通過(guò)競(jìng)選剛剛成為 Leader 的時(shí)候，有一些等待提交的 LogEntry （即 SN > CommitPt 的 LogEntry），有可能是 Commit 的，也有可能是未 Commit 的（PS: 因?yàn)樵?Raft 協(xié)議中 CommitPt 不用實(shí)時(shí)刷盤）。
所以為了防止出現(xiàn)非線性一致性（Non Linearizable Consistency）；即之前已經(jīng)響應(yīng)客戶端的已經(jīng) Commit 的請(qǐng)求回退，并且為了避免出現(xiàn)上面4-1中的 Corner Case(已經(jīng)commit的日志被覆蓋)，往往我們需要通過(guò)下一個(gè) Term 的 LogEntry 的 Commit 來(lái)實(shí)現(xiàn)之前的 Term 的 LogEntry 的 Commit （隱式commit），才能保障提供線性一致性。
但是有可能接下來(lái)的客戶端的寫請(qǐng)求不能及時(shí)到達(dá)，那么為了保障 Leader 快速提供讀服務(wù)，系統(tǒng)可首先發(fā)送一個(gè) no-op LogEntry 來(lái)保障快速進(jìn)入正常可讀狀態(tài)。
為什么no-op能解決不一致的問(wèn)題？
剛當(dāng)選的leader發(fā)送no-op,如果這個(gè)no-op可以commit成功那么可以認(rèn)為這個(gè)節(jié)點(diǎn)之前所有的日志都已經(jīng)commit成功了。換句話說(shuō)，大部分節(jié)點(diǎn)已經(jīng)將當(dāng)前這個(gè)leader寫入了log中。
也就是說(shuō)，通過(guò)這個(gè)no-op commit，我們commit了leader節(jié)點(diǎn)上所有的log。就算后面再有figure8中的覆蓋問(wèn)題，覆蓋的也是這個(gè)no-op
詳情可以看我寫的另外一篇文章：raft引入no-op解決了什么問(wèn)題
成員變更
一文看盡 Raft 一致性協(xié)議的關(guān)鍵點(diǎn)
可從數(shù)學(xué)上嚴(yán)格證明，只要每次只允許增加或刪除一個(gè)成員，Cold與Cnew不可能形成兩個(gè)不相交的多數(shù)派。這種方式比較簡(jiǎn)單，也是etcd的做法。
如果每次增加超過(guò)兩個(gè)。會(huì)導(dǎo)致變更過(guò)程中出現(xiàn)多個(gè)多數(shù)派，所以要引入用兩階段成員變更
系統(tǒng)狀態(tài)變化同paxos一樣通過(guò)日志同步
add node
catch up
transition Cold和Cnew需要同時(shí)達(dá)成多數(shù)派，log replication才算是成功。
Single mempership change
論文中提以下幾個(gè)關(guān)鍵點(diǎn)：
注意：
raft用到的隨機(jī)時(shí)間
raft 腦裂
Raft 協(xié)議強(qiáng)依賴 Leader 節(jié)點(diǎn)的可用性來(lái)確保集群數(shù)據(jù)的一致性。數(shù)據(jù)的流向只能從 Leader 節(jié)點(diǎn)向 Follower 節(jié)點(diǎn)轉(zhuǎn)移。當(dāng) Client 向集群 Leader 節(jié)點(diǎn)提交數(shù)據(jù)后，Leader 節(jié)點(diǎn)接收到的數(shù)據(jù)處于未提交狀態(tài)（Uncommitted），接著 Leader 節(jié)點(diǎn)會(huì)并發(fā)向所有 Follower 節(jié)點(diǎn)復(fù)制數(shù)據(jù)并等待接收響應(yīng)，確保至少集群中超過(guò)半數(shù)節(jié)點(diǎn)已接收到數(shù)據(jù)后再向 Client 確認(rèn)數(shù)據(jù)已接收。一旦向 Client 發(fā)出數(shù)據(jù)接收 Ack 響應(yīng)后，表明此時(shí)數(shù)據(jù)狀態(tài)進(jìn)入已提交（Committed），Leader 節(jié)點(diǎn)再向 Follower 節(jié)點(diǎn)發(fā)通知告知該數(shù)據(jù)狀態(tài)已提交。
在這個(gè)過(guò)程中，主節(jié)點(diǎn)可能在任意階段掛掉，看下 Raft 協(xié)議如何針對(duì)不同階段保障數(shù)據(jù)一致性的。
數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)前
這個(gè)階段 Leader 掛掉不影響一致性，不多說(shuō)。
數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，但未復(fù)制到 Follower 節(jié)點(diǎn)
這個(gè)階段 Leader 掛掉，數(shù)據(jù)屬于未提交狀態(tài)，Client 不會(huì)收到 Ack 會(huì)認(rèn)為超時(shí)失敗可安全發(fā)起重試。Follower 節(jié)點(diǎn)上沒(méi)有該數(shù)據(jù)，重新選主后 Client 重試重新提交可成功。原來(lái)的 Leader 節(jié)點(diǎn)恢復(fù)后作為 Follower 加入集群重新從當(dāng)前任期的新 Leader 處同步數(shù)據(jù)，強(qiáng)制保持和 Leader 數(shù)據(jù)一致。
數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，成功復(fù)制到 Follower 所有節(jié)點(diǎn)，但還未向 Leader 響應(yīng)接收
這個(gè)階段 Leader 掛掉，雖然數(shù)據(jù)在 Follower 節(jié)點(diǎn)處于未提交狀態(tài)（Uncommitted）但保持一致，重新選出 Leader 后可完成數(shù)據(jù)提交，此時(shí) Client 由于不知到底提交成功沒(méi)有，可重試提交。針對(duì)這種情況 Raft 要求 RPC 請(qǐng)求實(shí)現(xiàn)冪等性（idempotent），也就是要實(shí)現(xiàn)內(nèi)部去重機(jī)制（client如果發(fā)了個(gè)請(qǐng)求，就要一直無(wú)限重試知道成功，并且raft集群也會(huì)在自己恢復(fù)之前嘗試commit但是可能因?yàn)楣?jié)點(diǎn)crash沒(méi)有commit成功的log（Figure 8）。也就是說(shuō)raft節(jié)點(diǎn)會(huì)忽略自己已經(jīng)commit的log的rpc請(qǐng)求，直接返回成功？）。
數(shù)據(jù)到達(dá) Leader 節(jié)點(diǎn)，成功復(fù)制到 Follower 部分節(jié)點(diǎn)，但還未向 Leader 響應(yīng)接收
這個(gè)階段 Leader 掛掉，數(shù)據(jù)在 Follower 節(jié)點(diǎn)處于未提交狀態(tài)（Uncommitted）且不一致，Raft 協(xié)議要求投票只能投給擁有最新數(shù)據(jù)的節(jié)點(diǎn)。所以擁有最新數(shù)據(jù)的節(jié)點(diǎn)會(huì)被選為 Leader 再?gòu)?qiáng)制同步數(shù)據(jù)到 Follower，數(shù)據(jù)不會(huì)丟失并最終一致。
疑問(wèn)：
總結(jié)
以上是生活随笔為你收集整理的一致性协议raft详解（二）：安全性的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 一致性协议raft详解（一）：raft整
- 下一篇： 一致性协议raft详解（三）：raft中