Raft一種用于復(fù)制日志的共識算法

Raft:AConsensusAlgorithm

forReplicatedLogs日志復(fù)制同步（Replicatedlog）=>副本狀態(tài)機(jī)（replicatedstatemachine）所有服務(wù)器以相同順序執(zhí)行相同的命令共識模塊可確保正確的日志復(fù)制只要大多數(shù)服務(wù)器可用，系統(tǒng)就具備可進(jìn)展性失敗模型：失敗停止（不是拜占庭），延遲/丟失的消息Slide2目標(biāo):日志復(fù)制同步（ReplicatedLog）addjmpmovshlLog共識模塊狀態(tài)機(jī)addjmpmovshlLogaddjmpmovshlLog服務(wù)器客戶端shl共識模塊狀態(tài)機(jī)共識模塊狀態(tài)機(jī)一般達(dá)成共識有兩種方式:對稱式，無領(lǐng)導(dǎo)者:所有服務(wù)器的角色相同客戶端可以和任何服務(wù)器通信非對稱式，基于領(lǐng)導(dǎo)者:在任何時(shí)候，只有一個(gè)服務(wù)器負(fù)責(zé)接收客戶端請求并作出決策，其他服務(wù)器則只需接受它的決策?？蛻舳伺c領(lǐng)導(dǎo)者通信Raft采用一個(gè)領(lǐng)導(dǎo)者:分解問題（普通操作，領(lǐng)導(dǎo)者變更）簡化普通操作（無沖突）比無領(lǐng)導(dǎo)者的方式更高效Slide3達(dá)成共識的方式領(lǐng)導(dǎo)者選舉:選擇其中一個(gè)服務(wù)器作為領(lǐng)導(dǎo)者檢測崩潰，選擇新的領(lǐng)導(dǎo)者普通操作(基本的日志復(fù)制同步)領(lǐng)導(dǎo)者變更后的安全性和一致性平衡舊領(lǐng)導(dǎo)者客戶端交互實(shí)現(xiàn)線性化的語義配置變更:

添加或移除服務(wù)器Slide4Raft概覽在任何時(shí)候，每個(gè)服務(wù)器都處于以下三種狀態(tài)中的一種:Leader:處理所有客戶端的交互，日志復(fù)制同步任何時(shí)候最多有一個(gè)領(lǐng)導(dǎo)人Follower:完全被動（不發(fā)出RPC，響應(yīng)傳入的RPC）Candidate:用于選舉新領(lǐng)導(dǎo)者普通操作:1leader,N-1followersSlide5服務(wù)器狀態(tài)FollowerCandidateLeaderstarttimeout,

startelectionreceivevotesfrom

majorityofserverstimeout,

newelectiondiscoverserverwith

highertermdiscovercurrentserver

orhigherterm“step

down”時(shí)序被分割為多個(gè)領(lǐng)導(dǎo)者任期:領(lǐng)導(dǎo)者選舉（Elections）單一領(lǐng)導(dǎo)下的正常操作（NormalOperation）每個(gè)任期最多1個(gè)領(lǐng)導(dǎo)者有些任期沒有領(lǐng)導(dǎo)者（選舉失敗）每個(gè)服務(wù)器維護(hù)當(dāng)前任期的值術(shù)語的關(guān)鍵作用：判斷過時(shí)的信息Slide6領(lǐng)導(dǎo)者任期Term1Term2Term3Term4Term5timeElectionsNormalOperationSplitVoteSlide7RespondtoRPCsfromcandidatesandleaders.Converttocandidateifelectiontimeoutelapseswithouteither:ReceivingvalidAppendEntriesRPC,orGrantingvotetocandidate FollowersIncrementcurrentTerm,voteforselfResetelectiontimeoutSendRequestVoteRPCstoallotherservers,waitforeither:Votesreceivedfrommajorityofservers:becomeleaderAppendEntriesRPCreceivedfromnewleader:stepdownElectiontimeoutelapseswithoutelectionresolution:incrementterm,startnewelectionDiscoverhigherterm:stepdownCandidatesEachserverpersiststhefollowingtostablestoragesynchronouslybeforerespondingtoRPCs:currentTerm latesttermserverhasseen(initializedto0onfirstboot)votedFor candidateIdthatreceivedvoteincurrentterm(ornullifnone)log[] logentries PersistentStateterm

termwhenentrywasreceivedbyleaderindex

positionofentryinthelogcommand

commandforstatemachineLogEntryInvokedbycandidatestogathervotes.Arguments:candidateId candidaterequestingvoteterm candidate'stermlastLogIndex indexofcandidate'slastlogentrylastLogTerm termofcandidate'slastlogentryResults:term currentTerm,forcandidatetoupdateitselfvoteGranted

truemeanscandidatereceivedvoteImplementation:Ifterm>currentTerm,currentTerm←term

(stepdownifleaderorcandidate)Ifterm==currentTerm,votedForisnullorcandidateId,andcandidate'slogisatleastascompleteaslocallog,grantvoteandresetelectiontimeoutRequestVoteRPCInvokedbyleadertoreplicatelogentriesanddiscoverinconsistencies;alsousedasheartbeat.Arguments:term leader'stermleaderId sofollowercanredirectclientsprevLogIndex indexoflogentryimmediatelyprecedingnewonesprevLogTerm termofprevLogIndexentryentries[] logentriestostore(emptyforheartbeat)commitIndex

lastentryknowntobecommittedResults:term currentTerm,forleadertoupdateitselfsuccess trueiffollowercontainedentrymatchingprevLogIndexandprevLogTermImplementation:Returnifterm<currentTermIfterm>currentTerm,currentTerm←termIfcandidateorleader,stepdownResetelectiontimeoutReturnfailureiflogdoesn’tcontainanentryatprevLogIndexwhosetermmatchesprevLogTermIfexistingentriesconflictwithnewentries,deleteallexistingentriesstartingwithfirstconflictingentryAppendanynewentriesnotalreadyinthelogAdvancestatemachinewithnewlycommittedentriesAppendEntriesRPCRaft協(xié)議總覽InitializenextIndexforeachtolastlogindex+1SendinitialemptyAppendEntriesRPCs(heartbeat)toeachfollower;repeatduringidleperiodstopreventelectiontimeoutsAcceptcommandsfromclients,appendnewentriestolocallogWheneverlastlogindex≥nextIndexforafollower,sendAppendEntriesRPCwithlogentriesstartingatnextIndex,updatenextIndexifsuccessfulIfAppendEntriesfailsbecauseofloginconsistency,decrementnextIndexandretryMarklogentriescommittedifstoredonamajorityofserversandatleastoneentryfromcurrenttermisstoredonamajorityofserversStepdownifcurrentTermchangesLeaders服務(wù)器作為跟隨者啟動跟隨者希望從領(lǐng)導(dǎo)者或候選人那里接收RPC請求領(lǐng)導(dǎo)者必須發(fā)送心跳（空的AppendEntriesRPC）以保持其領(lǐng)導(dǎo)者的地位如果在選舉超時(shí)（electionTimeout）時(shí)間內(nèi)，未收到RPC:跟隨者假設(shè)領(lǐng)導(dǎo)者已經(jīng)崩潰跟隨者開始新的選舉超時(shí)通常為100-500毫秒Slide8心跳檢測及超時(shí)處理增加當(dāng)前任期號轉(zhuǎn)換到候選者狀態(tài)投票給自己發(fā)送RequestVoteRPC調(diào)用給所有其他服務(wù)器，重試，直至滿足以下條件之一:接收大多數(shù)服務(wù)器的投票:成為領(lǐng)導(dǎo)者發(fā)送AppendEntries心跳給所有其他服務(wù)器收到來自于有效領(lǐng)導(dǎo)者的RPC調(diào)用:回到跟隨者的狀態(tài)沒有人贏得選舉（選舉超時(shí)）:增加當(dāng)前任期號，重新開始新的選舉Slide9選舉Safety:最多只有一個(gè)候選者可以在某一任期內(nèi)贏得領(lǐng)導(dǎo)者地位每臺服務(wù)器在每個(gè)任期只投一次票(持久化到磁盤)兩個(gè)候選者不能在同一任期內(nèi)都獲取到多數(shù)票Liveness:一定有候選者最終獲勝在[T,2T]中隨機(jī)選擇選舉超時(shí)總會有一臺服務(wù)器先超時(shí)，并在其他服務(wù)器參與競爭之前就完成選舉這個(gè)過程當(dāng)超時(shí)時(shí)間T遠(yuǎn)大于廣播投票請求的時(shí)間時(shí)，這個(gè)策略會變得更為有效Slide10選舉,續(xù)ServersVotedforcandidateABcan’talsogetmajorityLogentry=index,term,command日志通常存儲于磁盤或其他一些穩(wěn)定的存儲介質(zhì)中;崩潰恢復(fù)某日志條目已存儲于大多數(shù)服務(wù)器，稱該條目已提交（committed）耐久性，最終由狀態(tài)機(jī)執(zhí)行Slide11日志結(jié)構(gòu)1

add123456783

jmp1

cmp1

ret2

mov3

div3

shl3

sub1

add3

jmp1

cmp1

ret2

mov1

add3

jmp1

cmp1

ret2

mov3

div3

shl3

sub1

add1

cmp1

add3

jmp1

cmp1

ret2

mov3

div3

shlleaderlogindexfollowerscommittedentriestermcommand客戶端給領(lǐng)導(dǎo)者發(fā)送命令領(lǐng)導(dǎo)者將命令追加到日志中領(lǐng)導(dǎo)者給所有的跟隨者發(fā)送AppendEntriesRPC調(diào)用一旦一個(gè)新的日志條目被提交:Leader將命令傳遞給其狀態(tài)機(jī)，將結(jié)果返回給客戶端領(lǐng)導(dǎo)者在后續(xù)的AppendEntriesRPC中通知跟隨者已提交的日志條目跟隨者將已提交的命令傳遞給其狀態(tài)機(jī)跟隨者崩潰了或處于慢響應(yīng)狀態(tài)?領(lǐng)導(dǎo)者重試RPC調(diào)用直至成功在一般情況下，性能是最佳的:一個(gè)成功的RPC調(diào)用只需等待大多數(shù)服務(wù)器的應(yīng)答Slide12普通操作日志間高度一致性:如果不同服務(wù)器上的日志條目具有相同的索引（index）和任期號（term），那么:它們存儲相同的命令所有前面的條目中的日志都是相同的如果提交了給定的條目，則所有前面的條目也同樣被提交了。Slide13日志一致性1

add1234563

jmp1

cmp1

ret2

mov3

div4

sub1

add3

jmp1

cmp1

ret2

mov每一個(gè)AppendEntriesRPC調(diào)用除了新創(chuàng)建的新日志條目，它還包括當(dāng)前新條目前序條目的下標(biāo)位置索引以及任期號追隨者必須包含匹配的條目;否則它拒絕請求實(shí)現(xiàn)歸納步驟，確保一致性Slide14AppendEntries一致性檢查1

add3

jmp1

cmp1

ret2

mov1

add1

cmp1

ret2

movleaderfollower123451

add3

jmp1

cmp1

ret2

mov1

add1

cmp1

ret1

shlleaderfollowerAppendEntriessucceeds:matchingentryAppendEntriesfails:mismatch新領(lǐng)導(dǎo)者任期開始時(shí):舊領(lǐng)導(dǎo)者可能會留下部分復(fù)制的條目在新的領(lǐng)導(dǎo)者被選出之前，不會有任何特別的操作始終認(rèn)為領(lǐng)導(dǎo)者的日志總是正確的最終會使跟隨者的日志與領(lǐng)導(dǎo)者的日志相同多次崩潰可能會留下許多無關(guān)的日志條目:Slide15領(lǐng)導(dǎo)者變更12345678logindex1111556666115514111772233327terms1s2s3s4s5一旦將日志條目應(yīng)用于狀態(tài)機(jī)后，其他任何狀態(tài)機(jī)都不能為該日志條目應(yīng)用不同的值Raft安全屬性:如果領(lǐng)導(dǎo)者已決定提交日志條目，則該條目將出現(xiàn)在所有未來領(lǐng)導(dǎo)者的日志中，并且也處于已提交狀態(tài)這保證了安全性要求領(lǐng)導(dǎo)者從不覆蓋它們?nèi)罩局械臈l目。只有領(lǐng)導(dǎo)者日志中的條目才能提交在應(yīng)用到狀態(tài)機(jī)之前，必須提交條目。Slide16安全性的要求Committed→Presentinfutureleaders’logsRestrictionson

commitmentRestrictionson

leaderelection無法分辨哪些條目已提交!在選舉期間，選擇最有可能包含所有已提交條目的日志的候選人候選者將日志信息（位置索引index以及最后一條日志條目的任期號term）包含在RequestVoteRPC調(diào)用中投票服務(wù)器V如果其日志“更完整”則拒絕投票:

(lastTermV>lastTermC)||

(lastTermV==lastTermC)&&(lastIndexV>lastIndexC)在多數(shù)選舉中，領(lǐng)導(dǎo)者將擁有“最完整”的日志。Slide17挑選最好的領(lǐng)導(dǎo)者1211212345121112112unavailableduringleadertransitioncommitted?案例#1/2:領(lǐng)導(dǎo)者提交當(dāng)前任期中的日志條目安全性:下一任期3的領(lǐng)導(dǎo)者必需包含日志條目4Slide18提交的記錄是在當(dāng)前任期12345611111112111s1s2s3s4s52222222AppendEntriesjust

succeededCan’tbeelectedas

leaderforterm3Leaderfor

term2案例#2/2:領(lǐng)導(dǎo)者試圖完成來自前一任期日志條目的提交日志條目3沒有安全的被提交:s5可能在任期5被選舉為領(lǐng)導(dǎo)者（它的前序任期值3較大，它可以獲得來自于S2、S3、S4的投票）如果當(dāng)選，它會重寫s1,s2和s3上的日志條目3!Slide19提交的記錄是在前序任期12345611111112111s1s2s3s4s522AppendEntriesjust

succeeded343Leaderfor

term43由領(lǐng)導(dǎo)者決定某一條目是否已提交:必須存儲在大多數(shù)服務(wù)器上必須在大多數(shù)服務(wù)器上存儲至少一個(gè)來自當(dāng)前領(lǐng)導(dǎo)者本任期內(nèi)的新條目一旦日志條目4被提交:S5不能當(dāng)選為任期5的領(lǐng)導(dǎo)者日志條目3、4都是安全的（不會像前一頁提到的S5當(dāng)選領(lǐng)導(dǎo)者將它們重寫）Slide20新提交規(guī)則1234511111112111s1s2s3s4s522343Leaderfor

term444選舉規(guī)則和提交規(guī)則的結(jié)合使得Raft安全3領(lǐng)導(dǎo)者變更可能導(dǎo)致日志不一致:Slide21日志的不一致1411455666123456789101112logindexleaderfor

term8141145566141114114556666141145566614114111possible

followers447722333332(a)(b)(c)(d)(e)(f)Extraneous

EntriesMissing

Entries新領(lǐng)導(dǎo)者必須使跟隨者日志與其自身一致剔除所有不同的日志記錄將所有丟失的記錄根據(jù)領(lǐng)導(dǎo)者的日志填充完整領(lǐng)導(dǎo)者為每個(gè)跟隨者維護(hù)一個(gè)nextIndex:要發(fā)送給該跟隨者的下一個(gè)日志條目的索引初始值為1+leader’slastindex當(dāng)AppendEntries一致性檢查失敗時(shí)，遞減nextIndex并再次嘗試:修復(fù)跟隨者的日志1411455666123456789101112logindexleaderforterm71411111followers22333332(a)(b)nextIndexSlide22當(dāng)跟隨者覆蓋不一致的條目時(shí)，它會刪除所有后續(xù)條目:Slide23修復(fù)日志,續(xù)14114556661234567891011logindexleaderforterm7111follower(before)22333332nextIndex111follower(after)4被罷免的領(lǐng)導(dǎo)者可能并不是真的死了:暫時(shí)與網(wǎng)絡(luò)斷開連接其他服務(wù)器選出新的領(lǐng)導(dǎo)者舊的領(lǐng)導(dǎo)者重新連接，嘗試提交日志條目任期用于檢測陳舊的領(lǐng)導(dǎo)者（和候選人）每個(gè)RPC都包含發(fā)送者的任期如果發(fā)送者的任期較舊，則RPC被拒絕，發(fā)送者將恢復(fù)為跟隨者并更新其任期如果接收者的任期較舊，則會恢復(fù)為跟隨者，更新其任期，然后正常處理RPC選舉會更新大多數(shù)服務(wù)器的任期被罷免的服務(wù)器無法提交新的日志條目Slide24平衡舊領(lǐng)導(dǎo)者（NeutralizingOldLeader）發(fā)送命令給領(lǐng)導(dǎo)者如果領(lǐng)導(dǎo)者未知，與任意服務(wù)器通信如果通信的服務(wù)器不是領(lǐng)導(dǎo)者，它將重定向到領(lǐng)導(dǎo)者在命令被記錄，提交和領(lǐng)導(dǎo)者的狀態(tài)機(jī)執(zhí)行之前，領(lǐng)導(dǎo)者不會響應(yīng)如果請求超時(shí)(e.g.,leadercrash):客戶端重新發(fā)送命令給其他服務(wù)器最終被重定向到新的領(lǐng)導(dǎo)者通過新領(lǐng)導(dǎo)者重試請求Slide25客戶端協(xié)議如果領(lǐng)導(dǎo)者在執(zhí)行命令后但在響應(yīng)之前崩潰會怎樣?

不能執(zhí)行命令兩次解決方案:客戶端在每個(gè)命令中嵌入一個(gè)唯一的id服務(wù)器將id保存到日志條目中在接受命令之前，領(lǐng)導(dǎo)者會檢查其日志以查找具有該id的條目如果在日志中找到該id對應(yīng)的條目，則忽略新命令，返回舊命令的響應(yīng)結(jié)果:只要客戶端不崩潰就能保證