最近看了Ongaro在2014年的博士論文《CONSENSUS: BRIDGING THEORY AND PRACTICE》的部分章節(jié)，對raft有了初步的理解俄占。其中論文中提到用于教學(xué)的user study，個(gè)人感覺非常不錯玩荠，言簡意賅肩狂，特此分享出來。本文基本與原講解一致沼头，又加上了筆者的一點(diǎn)理解。
資源來源于Ongaro和Ousterhout在youtube上的分享（http://youtu.be/YbZ3zDzDnrw）书劝，共有31個(gè)slide进倍，因篇幅字?jǐn)?shù)限制分為上下：
slide 15：
這一節(jié)開始講leader changes，即leader的變更過程中如何保證log的一致性：
1）需要明白的是购对，新leader上任后猾昆，各個(gè)server的log狀態(tài)很可能是不一致的；因?yàn)榕fleader可能只完成了部分server的log復(fù)制就掛掉了骡苞；（新君即位垂蜗，一片狼藉）
2）需要特別注意的是楷扬，raft中新leader上任后，并不會立即對不一致的舊log進(jìn)行clean up贴见，而仍然是正常開始normal operation烘苹；clean up是在normal operation的過程中進(jìn)行的；原因在于：新leader上任后片部，可能有些server仍然是宕機(jī)狀態(tài)镣衡，新leader沒有辦法立即對其進(jìn)行clean up（因?yàn)槟切﹕erver宕機(jī)或網(wǎng)絡(luò)不通，無法進(jìn)行通訊）档悠，只能等到這些server恢復(fù)正常后再進(jìn)行clean up廊鸥；而新leader不知道這些server什么時(shí)候能恢復(fù)正常求豫，如果傻傻地苦苦等待该贾，很可能會導(dǎo)致整個(gè)系統(tǒng)無法運(yùn)行；所以岳服，我們設(shè)計(jì)的系統(tǒng)缘回，必須要確保新leader上任后要立即開始normal operation助被，而在normal operation的過程中要確保最終所有l(wèi)og一致；
3）raft的做法是：總是認(rèn)為leader的log是對的Ｇ芯鳌（皇帝總是對的）
4）raft認(rèn)為leader的log總是對的揩环，總是包含所有重要的信息，因此leader的重任就是最終使得所有follower的日志與之完全相同幅虑。（皇帝總是對的丰滑，皇帝總是試圖廣播自己的想法，讓其他所有人的想法與之最終一致）
5）但是新leader在clean up的過程中也有可能宕機(jī)倒庵，再有新的leader上任褒墨，它也可能還沒完成重任就又宕機(jī)了；如此循環(huán)擎宝；長時(shí)間如此郁妈，最終會導(dǎo)致各個(gè)server的log混亂不堪，如圖實(shí)例绍申。
（備注：注意圖中示例噩咪，只標(biāo)注了某個(gè)entry的index和term，為什么不標(biāo)注command了极阅？因?yàn)榍懊嬉呀?jīng)說了胃碾，只要entry的index和term相同，則其command一定相同筋搏，所以沒必要標(biāo)注仆百；圖中展示的log混亂不堪，點(diǎn)評分析如下：term1時(shí)期的log都是一致的奔脐，誰是leader無從知曉俄周；term2時(shí)期只有S4和S5兩個(gè)server吁讨，但S5的entry更多，記住信息總是從leader流向follower峦朗，所以leader必定是S5建丧；term3只有S5，無疑它就是leader甚垦，這種情況很可能是當(dāng)選leader后與其他server網(wǎng)絡(luò)隔離了茶鹃；同理term4時(shí)期S4是leader涣雕，term5時(shí)期S3是leader艰亮，term6時(shí)期S1是leader，term7時(shí)期S2是leader挣郭；另外從圖中場景來看迄埃，很可能在中間某段時(shí)間，S4兑障、S5的網(wǎng)絡(luò)侄非，與S1、S2流译、S3的網(wǎng)絡(luò)不通逞怨，即產(chǎn)生了網(wǎng)絡(luò)隔離；）
需要特別注意的是福澡，圖中entry(1,1)叠赦、entry(2,1)、entry(3,5)都是已提交的（標(biāo)記方法是entry(index,term)革砸，這些entry所在server數(shù)都已過半）除秀，而其余所有的entry都是未提交的；我們一定要確保的是那些已提交的entry必須保存下來且不可再變更算利；而那些未提交的entry册踩，因?yàn)檫€未傳給任何state machine執(zhí)行過，client更沒有收到執(zhí)行結(jié)果效拭，所以是保存還是丟棄都無關(guān)緊要暂吉；
例如圖中S2成為term7時(shí)期的leader后，如果能夠與其他所有server通信缎患，那它最終要保證其他所有server的log與它的log相同借笙，這就意味著與之有沖突的log entry必須被清除；后續(xù)會詳細(xì)講解leader如何進(jìn)行clean up使得followers的log與之相同较锡；特別強(qiáng)調(diào)一下correctness和safety业稼，我們怎樣才能確保系統(tǒng)正常運(yùn)行，確保不丟失重要信息呢蚂蕴？如我們剛才為了保證一致性低散，丟棄了一些log俯邓，我們怎樣做才是安全的呢？下節(jié)講熔号。
slide 16：
任何實(shí)現(xiàn)了replicated logs的系統(tǒng)都必須遵守的最基本的safety requirement原則是：
Once a log entry has been applied to a state machine, no other state machine must apply a different value for that log entry;即一旦某條log entry已經(jīng)被某一個(gè)state machine執(zhí)行稽鞭，則其他任何state machine也必須執(zhí)行這同一條log entry；即所有state machine都必須按照相同的順序引镊，執(zhí)行完全相同的entry朦蕴；（執(zhí)行entry指的就是執(zhí)行entry中的command）
為了實(shí)現(xiàn)這個(gè)整體的safety要求，raft采取了更嚴(yán)苛的準(zhǔn)則弟头，即如下的safety property：
如果某個(gè)leader發(fā)現(xiàn)某條log entry已經(jīng)被提交吩抓，則這條entry必須存在于所有后續(xù)的leader中。這意味著赴恨，一旦某個(gè)leader即位疹娶，則在它的整個(gè)term時(shí)期內(nèi)，它一定含有所有的已提交的log entries伦连；
顯而易見雨饺，只要leader滿足了這條safety property，則一定能滿足上面的safety requirement惑淳。（因?yàn)檫@是一個(gè)更窄的要求额港，簡單推理：一個(gè)leader發(fā)現(xiàn)某條entry已被提交，則后續(xù)所有l(wèi)eader中都一定要有這條entry歧焦；這意味著leader中總是有所有的已提交entry移斩；而raft能保證follower中的log最終一定與leader中的一致；所以所有server最終都會有這些已提交entry倚舀；而entry只有被提交后才能被state machine執(zhí)行叹哭；所以最終所有的state machine必將按照相同的順序執(zhí)行相同的命令）
為了實(shí)現(xiàn)這一點(diǎn)，raft能夠保證的safety requirement有：
1）leaders永遠(yuǎn)不會修改自己log中的entries痕貌，只能添加风罩；（備注：這意思就是leader中的entry是不可變的；但注意舵稠，leader只是一種角色超升，是動態(tài)的不是永久的；只是說某個(gè)server當(dāng)leader期間哺徊，它的entry是不可變的室琢；而一旦下臺，其entry是有可能被修改的落追；這類似于繞口令坝巍；）這條性質(zhì)叫AppendOnlyProperty,即leader只能添加entry，但不能修改entry巢钓；這意味著leaders中l(wèi)og entries永遠(yuǎn)不會被修改病苗；
2）只有l(wèi)eaders中的log才能被提交；言外之意是症汹，某條entry即使過半server都存在了硫朦，但在leader中不存在，也是不能被提交的背镇；（有人會想咬展，會有這種情況嗎？entry不都是從leader發(fā)給follower的嗎瞒斩，怎么會過半followers中有而leader中沒有呢破婆？再次強(qiáng)調(diào)，leader和follower只是角色济瓢，是動態(tài)的荠割；正常情況下當(dāng)然不會有這種情況妹卿，但是leader變更的時(shí)候就可能會出現(xiàn)旺矾，后續(xù)會有這種case）
3）entries在被提交給state machine執(zhí)行之前，必須已被提交夺克；即只有已被提交的entry才能被執(zhí)行箕宙；
匯總1）、2）铺纽、3）柬帕，我們可以保證上面的安全性。真的如此嗎狡门？有這三個(gè)條件就夠了嗎陷寝？
事實(shí)上，到現(xiàn)在的講述為止其馏，raft有這三個(gè)約束凤跑，并不能保證上面的安全性；我們必須增加額外的約束條件才能保證上面所述的安全性叛复，后面會詳細(xì)講述我們是怎么解決的仔引。先再回頭想想我們需要達(dá)到的目標(biāo)：
某個(gè)entry已被提交? ->? 這條entry必定在后續(xù)leader中存在
為了實(shí)現(xiàn)這個(gè)安全性目標(biāo)，我們必須從兩方面修正raft算法：
a. 對leader election增加約束條件：如果某個(gè)server的log中缺少某個(gè)已提交entry褐奥，則不允許這個(gè)server當(dāng)leader咖耘；
b. 必須改變對committed的定義：前面說的已過半即是committed，這是不夠的撬码；有時(shí)候我們必須延遲committed儿倒，直到我們認(rèn)為安全了才能committed；所謂的安全呜笑，就是說我們認(rèn)為能夠保證后續(xù)leader有這條entry夫否；
（點(diǎn)評：這兩個(gè)約束條件非常繞口找筝，大家認(rèn)真領(lǐng)悟下：約束a是排除了某些server當(dāng)leader，即不含有已提交entry的server不允許當(dāng)leader慷吊；顯而易見袖裕，只有約束a是不夠的，因?yàn)閍說的只是最低安全性條件溉瓶，照此條件急鳄，有可能一個(gè)leader都選不出來；而b是對committed條件的加強(qiáng)堰酿，意味著對committed施加更嚴(yán)苛的條件疾宏，也意味著給更多server成為leader的機(jī)會，即能夠保證最終能選出leader触创；后續(xù)會有相應(yīng)case）
slide 17：
接著上個(gè)slide坎藐，先講leader election過程的修正：
我們怎樣挑選leader，才能保證這個(gè)leader有所有的已提交entries呢哼绑？
這個(gè)問題非常難岩馍，因?yàn)槲覀冇袝r(shí)候根本無法判斷某條entry是否已提交了！
看上圖：圖中有3個(gè)server抖韩，但是突然server3掛掉了蛀恩，必須從server1和server2中挑選一個(gè)leader；而對于entry5而言茂浮，根本無法判斷entry5是否是已提交的双谆！因?yàn)檫@取決于server3，如果server3中有entry5席揽，則是已提交的顽馋，如果server3中無entry5，則不是已提交的幌羞；而server3已宕機(jī)或網(wǎng)絡(luò)不通寸谜，根本無法與server3通訊，所以根本不可能知道server3上到底有沒有entry5新翎，所以根本無法判斷entry5是否是已提交程帕！
既然我們根本無法判斷某條entry是否是已提交，我們怎么挑選leader來確保leader中一定有所有已提交entry呢地啰？我們只能盡我們所能愁拭，挑選最有可能含有所有已提交entry的server做leader，即挑選the best leader! 我們此處先從直覺上這樣理解亏吝，下面會更精確詳細(xì)地證明岭埠。
我們挑選best leader的方式就是通過對log進(jìn)行比較，即comparing logs：
1）candidate發(fā)起的RequestVote RPC投票請求包含其log中最后一條entry的index和term：回憶我們前面所說，最后一條entry的index和term能唯一標(biāo)記整條log惜论，即如果last entry的index和term相同许赃，則這兩條log必定相同；（需從前面兩個(gè)結(jié)論推知: a. ?index和term唯一標(biāo)記一條entry; b. 某個(gè)entry相同馆类，則其之前的entries也必定相同）
2）當(dāng)其他server收到投票請求時(shí)混聊，需要將收到的（index,term)與自己的相比較，如果認(rèn)為自己的log更完整乾巧，則拒絕投票句喜；更準(zhǔn)確的定義如下：voting server V 收到candidate C的RequestVote請求，如果出現(xiàn)下面兩種情況之一：
a. lastTerm_v > lastTerm_c 即server v的last entry所在term沟于，即lastTerm比candidate的大咳胃；
b.? (lastTerm_v == lastTerm_c) && (lastIndex_v > lastIndex_c) 即server v的lastTerm與candidate相同，但是lastIndex值比candidate大旷太；
一旦出現(xiàn)a或b展懈，則server V認(rèn)為自己的log更c(diǎn)omplete，直接否決candidate的投票請求供璧；
（點(diǎn)評：此處非常關(guān)鍵存崖，務(wù)必理解；回想我們的目的是pick the best leader,即要求candidate的日志盡可能最complete嗜傅！最顯然直觀的理解當(dāng)然就是誰的log最長誰的最完整了金句；然而檩赢，不盡如此吕嘀；還有一個(gè)更重要的要求是more informative！只最多是沒用的贞瞒，首先要確保的是你的信息是最權(quán)威的偶房、最informative的；在raft中我們引入了term的概念军浆，且總是認(rèn)為更晚term的信息比更早term的信息權(quán)威棕洋，所以挑選leader的首要條件就是看，誰的term更晚更大乒融，即a掰盘；第二才是比較誰的log更長，即b）
3）結(jié)合1）赞季、2）最終確保選舉出來的leader將會是大多數(shù)server中l(wèi)og“最完整”的（most complete）愧捕；
聽懂沒？不要擔(dān)心申钩，下面上實(shí)例次绘。
slide 18：
考慮最有趣的一種場景：leader剛剛確定某條entry被committed了（即剛收到來自大多數(shù)server的AppendEntries響應(yīng)），就掛了。這種場景可以再分成兩種獨(dú)立case：1）這條entry屬于current term邮偎；2）這條entry屬于prior term管跺；
先說case1，如圖：
S1是term2時(shí)期的leader禾进，剛把entry4復(fù)制到S2豁跑、S3成功，立馬宣布entry4已安全（即在大多數(shù)server中都有泻云，已被committed）贩绕，立即在state machine上執(zhí)行entry4；這意味著entry4是已提交的壶愤，后續(xù)的leader中必須包含這條entry淑倾，我們怎么確保呢？就是通過上一個(gè)slide中的leader election中的pick the best leader;設(shè)想征椒，此時(shí)S1突然網(wǎng)絡(luò)不通娇哆，需要重新選舉leader，我們逐個(gè)分析：
a. S5絕不可能成為leader勃救，因?yàn)槠渌鹲erver都處于term2碍讨，它還在term1，即其他server的lastTerm更大蒙秒，會直接拒絕給它投票勃黍；
b. S4處于term2，但它若想成為leader晕讲，還需要至少2臺server給它投票覆获，而它最多只能得到S5的投票；因?yàn)槠渌鹲erver也都處于term2瓢省，但是log更長弄息，即lastIndex更大，所以都會拒絕投票勤婚；因此S4加上自身最多得2票摹量，也不可能成為leader；
c. S2和S3都可能成為leader馒胆，例如收到來自S4缨称、S5的投票；顯然祝迂，S1也可能成為leader睦尽；
綜合abc發(fā)現(xiàn)，可能成為leader的server都含有entry4液兽，即新的term3時(shí)期的leader必定含有entry4骂删；換言之掌动，最終新leader必定含有已committed的entry；
slide 19：
現(xiàn)在考慮case 2：leader盡力使得一條entry被提交宁玫，而這條entry來自上一個(gè)term時(shí)期粗恢。
如圖：
1）S1是term2時(shí)期的leader，S1剛將entry3復(fù)制到S2欧瘪，就掛掉了眷射，即此時(shí)entry3只在S1、S2兩個(gè)server上有佛掖；
2）接著S5發(fā)起leader競選妖碉，收到來自S3、S4的投票（此時(shí)S3芥被、S4欧宜、S5都只有term1時(shí)期的entry1、entry2拴魄，所以不會拒絕投票）冗茸，成功當(dāng)選成為term3時(shí)期的leader；接著S5收到client請求匹中，在本地log中產(chǎn)生了3條entry夏漱，但由于種種原因（如與其他server網(wǎng)絡(luò)忽然不通），并未復(fù)制到其他server上就掛掉了顶捷；
3）接著S1再次競選挂绰，成功當(dāng)選為term4時(shí)期的leader；S1成為leader后服赎，會盡力使得其他server的log與之相同葵蒂，所以會將entry3、entry4復(fù)制到其他server上专肪；一旦將entry3復(fù)制到server3上刹勃，則此時(shí)entry3已經(jīng)形成大多數(shù)，即是已被committed了嚎尤；entry3上的command就會被state machines執(zhí)行，client就會收到entry3的執(zhí)行結(jié)果伍宦。
最危險(xiǎn)的情況出現(xiàn)了芽死！注意，這種場景下entry3并不能認(rèn)為是safely committed次洼！因?yàn)樗钥赡鼙桓采w关贵，仍可能丟失！
考慮接下來可能發(fā)生的情況卖毁，就會明白為什么了：
4）S1成為term4時(shí)期的leader后揖曾，剛在本地產(chǎn)生entry4就掛掉了落萎；而此時(shí)，S5可以再次當(dāng)選炭剪，成為term5時(shí)期的leader（考慮下可能性练链，是完全有可能的，雖然entry3是committed了奴拦，但是S5很可能并不知道媒鼓；因?yàn)榭赡芫W(wǎng)絡(luò)分割，S1無法與其他server通信错妖，只有S2绿鸣、S3、S4暂氯、S5可以互相通信潮模，此時(shí)S5不可能知道entry3是否已committed，S5完全可以當(dāng)選leader）
5）S5當(dāng)選leader之后痴施，就會盡力使得其他server的log與之相同再登，就會term3時(shí)期的entry3、entry4晾剖、entry5復(fù)制到其他server锉矢；
很顯然，之前的term2時(shí)期的entry3雖然已被認(rèn)為是committed了齿尽，但仍會被覆蓋導(dǎo)致丟失沽损！顯然，這與我們要求的safety原則相悖循头，無法容忍绵估！必須加上新的限制條件，避免這種情況發(fā)生卡骂。
slide 20：
接前文国裳；目前為止，new leader election rules并不足以保證安全性全跨，我們必須還要修改已有的commitment rules缝左！
回想一下，到目前為止浓若，我們的commitment rules是：
1）只要leader看到某條entry存在majority of servers上(過半即可)渺杉，則認(rèn)為這條entry是committed；
為了保證安全性挪钓，我們必須添加一個(gè)額外的rule：
2）leader必須看到至少一條來自leader term（即leader的current term）的entry也存在于大多數(shù)的server上是越；
同時(shí)，rule 1）之前是充要條件碌上，現(xiàn)在變成了必要非充分條件倚评，新的commitment ruels是：
1）leader必須看到某條entry存在于大多數(shù)server上浦徊；
2）另外，leader必須看到至少一條來自其current term的entry也存在于大多數(shù)server上天梧；
只有同時(shí)滿足1）2）才能認(rèn)為某條entry是committed的盔性。
很明顯，新加的rule 2）主要是針對上面說的case2場景的腿倚，即當(dāng)新leader看到某條來自之前term的entry已經(jīng)存在于大多數(shù)server上時(shí)纯出，它不能再認(rèn)為這條entry是committed了，必須等到來自其自身term的第一條entry也存在于大多數(shù)server上敷燎，才能認(rèn)為之前term的那條entry是committed的暂筝；這其實(shí)相當(dāng)于一種leader change場景下的延遲commitment吧，或者換種思路硬贯，相當(dāng)于將上一個(gè)term時(shí)期的entry的commitment與當(dāng)前term時(shí)期的commitment綁定在了一起焕襟。
回到前面的case2，接著看新commitment rules是如何保證安全性的：
1）當(dāng)S5成為term4時(shí)期的leader后饭豹，它將entry3復(fù)制到S3鸵赖，此時(shí)entry3已經(jīng)存在于過半server上，但是并不能認(rèn)為entry3是committed的拄衰，即并不會將entry3傳給state machines執(zhí)行它褪；
2）必須等到entry4也復(fù)制到過半機(jī)器上，此時(shí)才能認(rèn)為entry3翘悉、entry4是committed了（相當(dāng)于延遲與綁定）茫打。
那這樣就是安全的了嗎？是的妖混。設(shè)想一下：
1）如果S1復(fù)制完成entry3老赤、entry4到大多數(shù)server上，即entry3制市、entry4都已被committed了抬旺，此時(shí)S1掛掉了；那么顯然祥楣，S4开财、S5不可能成為新的leader（因?yàn)閠erm太低會被拒絕投票），只有S1荣堰、S2床未、S3有可能成為新leader，而這些server上都有entry3振坚、entry4，所以entry3斋扰、entry4是安全的渡八；
2）那么如果S1還沒將entry3啃洋、entry4復(fù)制到大多數(shù)server上就掛了呢？那S5有可能成為新leader屎鳍，即意味著entry3宏娄、entry4可能會被覆蓋。這有什么關(guān)系呢逮壁？這種情況下entry3孵坚、entry4并沒被認(rèn)為是committed的，其命令被沒有被state machine執(zhí)行窥淆，client更沒有收到其執(zhí)行結(jié)果卖宠；這種情況下，entry3忧饭、entry4被覆蓋而丟失是無關(guān)緊要的扛伍；
我們只保證已committed的entries的safety，并不對未committed的entries的安全性做任何保證词裤。
因此刺洒，據(jù)上分析可知，new commitment rules是能夠保證committed entries的safety的吼砂。
綜上可知逆航，new election rules和new commitment rules結(jié)合起來，能夠保證raft的safety特性總是成立渔肩；即因俐，一旦leader認(rèn)為某條entry已被committed衷恭，則這條entry必然存在于后續(xù)所有l(wèi)eader的log中（就是說已committe的entries永不丟失）九默；雖然我們這里只證明了已committed的entry必然存在于緊接著它的后續(xù)一個(gè)leader中崖媚，但很顯然容易證明搀绣，這條entry在后續(xù)所有l(wèi)eader中都會有慌植；
而一旦raft的safety特性成立盅蝗，根據(jù)我們之前所說状植，所有的replicated logs都是安全的优炬。
（點(diǎn)評：raft的safety property是整個(gè)raft系統(tǒng)的基石袍嬉，是整個(gè)系統(tǒng)運(yùn)行可靠性的最基本要求境蔼；需要認(rèn)真理解領(lǐng)悟，結(jié)合實(shí)例認(rèn)真體會raft是如何面對這些問題的伺通，如何一步步修正完善rules來保證安全性的）
slide 21：
現(xiàn)在箍土，我們保證了raft的safety，并且知道leader的log永遠(yuǎn)是對的罐监，那么我們怎么使得followers的log與leader的log相同呢吴藻？
首先讓我們看下，followers的log有哪些與leader可能不同的情況呢：
1）missing entries：即follower的log與leader相比缺少某些entries弓柱，如圖中的a/b/e follower沟堡；
2）extraneous entries：即follower的log與leader相比多出某些entries侧但，如圖中的c/d/f follower;
我們需要做的是：刪除所有follower log中的多余entries，并用leader log中的entries填充follower中缺失的entries航罗。
slide 22：
接上文繼續(xù)講述禀横，leader到底如何修復(fù)follower的logs使其與之相同呢？
上個(gè)slide已說了粥血，leader為了保證follower的log與之相同柏锄，必須：
1）刪除follower中的多余entries；
2）用自己的entries填充follower中的缺失entries复亏；
那leader具體是如何做的呢趾娃？
為了恢復(fù)log一致性，leader為集群中所有follower都保存一個(gè)狀態(tài)變量蜓耻，即nextIndex：
1）nextIndex是leader準(zhǔn)備向某個(gè)follower發(fā)送的下一個(gè)log entry的index茫舶；
2）當(dāng)leader剛剛即位后，nextIndex的初始值是（1+leader's last index）刹淌；
如圖舉例：
某個(gè)server成為term7時(shí)期的新leader饶氏，其log中的最后一條是entry10，所以這個(gè)leader會將所有follower的nextIndex都設(shè)為11有勾；
leader可以通過AppendEntries RPC請求發(fā)現(xiàn)log之間的一致性問題疹启；回想前面說過的，follower收到AppendEntries RPC請求的時(shí)候蔼卡，會進(jìn)行l(wèi)og一致性檢查喊崖，所以一旦有不一致情況就會被檢查出來；
因此雇逞，當(dāng)leader試圖與集群中的follower通訊時(shí)候荤懂，會帶上nextIndex前面的一個(gè)entry的index和term（回想下，這是之前說過的塘砸，AppendEntries RPC請求會帶上前一個(gè)entry的index和term用于進(jìn)行一致性檢查节仿，這里的前一個(gè)entry就是entry10，對應(yīng)的index和term分別是10和6）掉蔬；
順便說下廊宪，新leader即位后，立即發(fā)出的請求很可能是heartbeat（心跳請求）女轿！回憶之前說的箭启，心跳請求跟普通的AppendEntries RPC是一樣的，只是不帶新values而已蛉迹，但心跳請求仍然可以進(jìn)行一致性檢查傅寡；
因此，當(dāng)這個(gè)請求（可能是心跳也可能是普通的AppendEntries ）到達(dá)follower a時(shí)，follower會拿這個(gè)index和term（這里就是(10,6）)與自己的log相比較赏僧；很顯然大猛，follower a中沒有與之相匹配的扭倾；所以follower a會直接拒絕這個(gè)請求淀零！
當(dāng)leader看到請求被拒絕時(shí)，其動作非常簡單：只需將nextIndex-1膛壹，再次嘗試驾中。
如此往復(fù)，再失敗模聋，nextIndex再減1肩民，再重試；直到nextIndex=5链方，此時(shí)leader會帶上（4,4）這個(gè)entry持痰，follower a發(fā)現(xiàn)能與之匹配，所以接收祟蚀；一旦follower a接受工窍，則最終后續(xù)所有的missing entry都會被添加上；
follower b的情況也類似前酿，當(dāng)nextIndex=11時(shí)患雏，一致性檢查會失敗罢维；每次失敗leader都會將nextIndex-1淹仑，然后重試；直到nextIndex=4肺孵，才會成功匀借；最終follower b中的log也會被重新填充上；
slide 23：
接上文平窘，修復(fù)log的過程中吓肋，需要注意的一點(diǎn)是：
一旦follower收到某個(gè)log entry，且這條entry會覆蓋掉follower 自身的與之不一致的entry初婆，則follower會刪掉自己所有后續(xù)的entries蓬坡；
如圖舉例：當(dāng)leader將entry4發(fā)送給follower，則follower的對應(yīng)位置的entry與之沖突（仍處于term2而不是term4）磅叛，因此entry4會覆蓋follower的entry屑咳，且會將follower中entry4后面的所有entries都刪除掉（即圖中的before變成after）；因?yàn)槲覀冎辣浊伲硹l多余的entry后面的所有entry也都是多余的兆龙。
這里簡要總結(jié)下leader change這部分的關(guān)鍵點(diǎn)：
有兩個(gè)overall problems我們需要處理：一是確保系統(tǒng)的safety，即怎么挑選leader、何時(shí)認(rèn)為某條entry是committed的紫皇；二是當(dāng)新leader上任后慰安，會盡力使所有followers的log與之相匹配，而AppendEntries一致性檢查提供了所有我們需要的信息聪铺。
slide 24：
raft協(xié)議的第4部分也是關(guān)于leader change的化焕，即old leader可能并沒有真的死掉。如：
1）可能存在網(wǎng)絡(luò)隔離或不穩(wěn)定铃剔，導(dǎo)致leader暫時(shí)性地?cái)嗑W(wǎng)撒桨，即無法與其他servers通信；
2）其余servers等待到election timeout键兜，然后選舉出新的leader凤类；
3）這時(shí)，如果舊leader的網(wǎng)絡(luò)恢復(fù)了普气，它并不知道已經(jīng)進(jìn)行了選舉谜疤，并不知道已有新的leader了；所以它仍認(rèn)為自己是leader现诀，并像leader一樣行動夷磕，如嘗試復(fù)制log entries；
事實(shí)上赶盔，確實(shí)還可能有client請求舊leader：舊leader接收到請求企锌，記錄到自己的log里，并嘗試復(fù)制到集群中的其他servers中于未；我們必須阻止這種情況發(fā)生撕攒，方法就是使用term。
terms被用來識別過期的leader和candidate：
1）所有RPC請求都會帶上sender（發(fā)送者）的term信息烘浦；當(dāng)receiver收到RPC請求時(shí)抖坪，會將sender的term與其自身的term相比較，一旦不匹配闷叉，過期的一方必須更新term擦俐；
2）如果sender的term更低（更老），意味著sender是過期的握侧；此時(shí)receiver會立即拒絕該請求蚯瞧，即不會執(zhí)行該請求；并再給sender的response中帶上receiver的term信息品擎；當(dāng)sender收到response之后埋合，會意識到它的term已經(jīng)過時(shí)，因此會主動下臺萄传，再次回到follower狀態(tài)甚颂，同時(shí)更新自己的term；此時(shí)其term狀態(tài)與其他servers是一致的；
3）相反振诬，如果receiver的term更舊蹭睡，則：如果此時(shí)receiver不是follower的狀態(tài)，它也會主動下臺赶么，再次回到follower狀態(tài)肩豁，同時(shí)更新自己的term（如果本來就是follower只需更新term即可）；接著正常處理該RPC請求禽绪；這種情況下receiver不會拒絕RPC請求蓖救，因?yàn)樗鼪]有必要這樣做；它只需主動下臺且更新term即可印屁；
有趣的是，leader election過程會使得集群中大多數(shù)server都更新term斩例，因?yàn)楫?dāng)candidate請求投票時(shí)雄人，它必須與集群中大多數(shù)server通信；而RequestVote RPC會帶上candidate的term信息念赶；而所有的接收者都會更新自身的term信息使之與candidate的相同础钠；因此，當(dāng)新leader上任后叉谜，集群中的大多數(shù)server都會反映出新的term信息旗吁；這意味著，一旦新的leader election完成停局，舊leader就不可能再接受請求并復(fù)制log entries到其他server了很钓。因?yàn)闉榱藦?fù)制log entries，舊leader必須與具有新term的server中的至少一臺通訊董栽，而一旦這樣做码倦，就會被發(fā)現(xiàn)term不匹配，而導(dǎo)致舊leader下臺锭碳。（此處較為拗口袁稽，道理很顯然，新的leader當(dāng)選必然意味著過半server的term都是最新的擒抛；而舊leader復(fù)制log也必須與過半server通訊推汽；而過半與過半之間，必然有至少一個(gè)公共server歧沪；而這個(gè)server的term檢查就會使得舊leader暴露歹撒，從而下臺）
因此，綜上所述槽畔，可以用term檢查識別過期信息栈妆。
（點(diǎn)評：分布式系統(tǒng)中的時(shí)期、任期的概念非常關(guān)鍵，如raft中的term鳞尔、zab中的epoch等嬉橙，道理都是類似的；其核心用意只有一個(gè)寥假，即識別過期信息）
slide 25：
現(xiàn)在講raft的第5部分市框，即client如何與raft系統(tǒng)交互。
大部分情況下糕韧，這都很簡單枫振，即：client將command請求發(fā)送給leader，然后接收leader的response萤彩。
但是粪滤，如果client不知道誰是leader呢？沒關(guān)系雀扶，client可以請求集群中的任意server杖小；如果那個(gè)server不是leader，它會告訴client誰是leader愚墓；然后client可以重新請求leader予权。
之前說過，leader并不會立即響應(yīng)client浪册，直到：command被記錄到log中扫腺，并復(fù)制到大多數(shù)server上，即被committed村象，接著leader的state machine執(zhí)行該command笆环。此時(shí)，leader才會向client返回請求結(jié)果煞肾。
唯一需要注意的地方是咧织，如果此時(shí)請求超時(shí)了（如leader突然掛掉導(dǎo)致），會怎么樣籍救？答案是：
1）client會請求集群中任意一個(gè)server习绢，不斷重試；
2）最終蝙昙，client會發(fā)現(xiàn)集群中的新leader闪萄；
3）client會向新leader重試請求；
新leader會執(zhí)行client的command奇颠，并發(fā)送請求結(jié)果败去。因此這能保證，command總是能夠被執(zhí)行烈拒。
slide 26：
然而圆裕，上一個(gè)slide中說的广鳍，總能保證command最終被執(zhí)行，會帶來command被重復(fù)執(zhí)行的風(fēng)險(xiǎn)吓妆。
問題的關(guān)鍵是：leader可能在執(zhí)行完某個(gè)command赊时，但是還未向client發(fā)送結(jié)果時(shí)掛掉。而一旦出現(xiàn)這種情況行拢，client不可能知道這個(gè)command到底是否被執(zhí)行了祖秒，所以它會不斷重試，并最終請求到新leader上舟奠，而這會導(dǎo)致該command被執(zhí)行兩次竭缝。
顯然，這是無法接受的沼瘫！我們要求command必須最終被執(zhí)行抬纸，且只能執(zhí)行一次（once and exactly once）。
raft的解決思路是：client為每個(gè)command生成一個(gè)唯一id晕鹊，并在發(fā)送command時(shí)候帶上該id松却。
1）當(dāng)leader記錄command時(shí)，會將command的id也記錄到log entry中溅话；
2）在leader接受command之前，會先檢查log中是否有帶該id的entry歌焦；
3）leader一旦發(fā)現(xiàn)log中已有該id的entry飞几，則會忽略這個(gè)new command，并將old command的結(jié)果返回給client（如果此時(shí)old command還沒執(zhí)行完独撇，會等待其完成再返回）屑墨；
因此，只要client不crash纷铣，我們就能實(shí)現(xiàn)exactly-once語義卵史，即每個(gè)command只會被執(zhí)行一次。這也是我們希望系統(tǒng)具有的搜立，被叫做linearize ability以躯。
（點(diǎn)評：類似于冪等性，即client重試不會導(dǎo)致重復(fù)執(zhí)行啄踊。系統(tǒng)本身要支持這種重入忧设、重試，保證有且僅有一次執(zhí)行颠通。）
slide 27：
這是raft協(xié)議的第6部分：系統(tǒng)配置的變更機(jī)制址晕。
系統(tǒng)配置指的是組成集群的各個(gè)server的信息。如每個(gè)server的id顿锰、用于通訊的網(wǎng)絡(luò)地址等谨垃。這些信息非常重要启搂，因?yàn)檫@些決定了集群中“大多數(shù)”（majority）的組成，而選舉leader刘陶、commit log entry等都取決于majority vote胳赌。
我們必須要支持系統(tǒng)配置變更，因?yàn)闄C(jī)器可能宕機(jī)易核，我們需要用新機(jī)器替代老機(jī)器匈织；或集群管理員想更改集群的degree of replication（復(fù)制因子、副本系數(shù)）牡直。我們想讓系統(tǒng)自動而安全（automatic and safe）地完成這些缀匕，而不至于變更配置導(dǎo)致系統(tǒng)崩潰。
slide 28：
重要的是碰逸，我們必須意識到：我們不能直接地將舊配置切換成新配置乡小。為什么呢？看圖中例子：
設(shè)想系統(tǒng)正在運(yùn)行饵史，系統(tǒng)配置中有3臺機(jī)器满钟，即server1/server2/server3；而我們現(xiàn)在想添加2臺機(jī)器胳喷，即添加后應(yīng)該有5臺機(jī)器組成新的集群湃番。
如果我們要求每個(gè)server直接更改配置，從舊配置改為新配置吭露，就會產(chǎn)生問題吠撮。問題就是我們沒辦法做到所有server同時(shí)更改配置，變更過程總要花點(diǎn)時(shí)間讲竿，而這會導(dǎo)致conflicting majoritys（大多數(shù)沖突）泥兰。
例如圖中某個(gè)時(shí)刻，server1题禀、server2仍是舊配置鞋诗；而server3、server4迈嘹、server5已經(jīng)是新配置削彬。這樣server1、server2能夠形成舊集群中的大多數(shù)江锨，它們可以基于此進(jìn)行l(wèi)eader election吃警、commit log entry等；而與此同時(shí)啄育，另外3臺機(jī)器酌心，即server3、server4挑豌、server5已經(jīng)是新配置了安券，它們也可以形成新配置集群中的大多數(shù)墩崩，也可能commit與前2臺server相同位置的log entry，而這很可能會產(chǎn)生沖突侯勉。
這意味著鹦筹，我們必須用two-phase protocol（兩階段協(xié)議），我們沒辦法在one-phase中完成址貌。當(dāng)然铐拐，所有的分布式系統(tǒng)中的decision-making都會采取這種典型辦法；如果有人告訴你练对，他能在one-phase中完成分布式系統(tǒng)的decision-making遍蟋，你需要提出嚴(yán)重質(zhì)疑！要么是他錯了螟凭，要么是他發(fā)現(xiàn)了這個(gè)世界上從來沒人知道的新東西虚青！
（點(diǎn)評：two-phase protocol即兩階段協(xié)議，是所有分布式系統(tǒng)中做decision-making的套路螺男。問題的核心與關(guān)鍵就在于“分布式”棒厘，意味著系統(tǒng)中不是一個(gè)單一的個(gè)體，而是眾多個(gè)體組成的整體下隧；而遺憾的是這個(gè)整體不可能像單一個(gè)體那樣行為奢人，例如眾多個(gè)體不可能同時(shí)完成某項(xiàng)動作，也即不可能完全地把一個(gè)整體等價(jià)于一個(gè)個(gè)體淆院；而client又需要整體像一個(gè)體一樣地運(yùn)行达传。）
slide 29：
raft采用2-phase的方式進(jìn)行配置變更：
raft先立即進(jìn)入一個(gè)中間狀態(tài)，叫joint-consensus迫筑；這個(gè)狀態(tài)包含舊配置和新配置的所有機(jī)器；但是decision-making宗弯，如leader election和log commitment脯燃，需要同時(shí)滿足舊配置的大多數(shù)和新配置的大多數(shù)（need majority of both old and new configurations for election and commitment）;
如圖中舉例說明：
集群最初的已有配置是Cold，而在某個(gè)時(shí)刻蒙保，由client發(fā)起集群配置變更辕棚，即client向leader發(fā)送配置變更請求（類似普通的operation請求）；當(dāng)leader接收到配置變更請求時(shí)邓厕，就向自己的log中插入一條entry（跟普通的log entry是一樣的）逝嚎，用于描述配置變更，如Cold+new详恼；然后leader通過AppendEntries RPC請求將該配置變更log entry復(fù)制到其他server上（跟普通的AppendEntries RPC復(fù)制log entry一樣）补君；需要特別注意的是，配置變更立即生效昧互！即一旦server將新配置的log entry寫入自己的log挽铁，它就立即生存在新的配置之下伟桅；它不需要等待大多數(shù)server都有這條entry，即不需要等待這條entry提交叽掘，一旦寫入自己的log中就立即生效（這點(diǎn)與普通entry不同楣铁，普通的entry必須等到已提交才能被執(zhí)行而生效）；
回到圖中的時(shí)間線更扁，leader將新配置的log entry寫入自己的log盖腕，并立即生效；之后leader所做的所有decisions浓镜，都必須基于old+new的配置溃列，如后續(xù)某條普通的entry要想被提交，必須同時(shí)存在于大多數(shù)的舊配置的server上竖哩，和大多數(shù)的新配置的server上哭廉；
過一小段時(shí)間，Cold+new這條log entry總會復(fù)制到大多數(shù)的server上而變成被提交狀態(tài)相叁；而在此之前遵绰，decision-making有可能是基于Cold，也有可能是基于Cold+new增淹；如leader剛收到Cold+new的配置變更椿访，還沒來得及復(fù)制到更多server上就宕機(jī)了，此時(shí)處于Cold配置的server有可能當(dāng)選并掌控集群虑润；
但是成玫，總有一個(gè)時(shí)間點(diǎn)，最終Cold+new這條entry能夠復(fù)制到大多數(shù)server上而成為committed狀態(tài)拳喻；一旦Cold+new被提交哭当，則意味著任何server都不能再僅僅基于Cold來make decision了。簡單解釋：如果一個(gè)server想成為leader冗澈，它必須具有所有的已committed的log entries钦勘，而Cold+new一旦被committed，就保證了后續(xù)任何leader都一定有Cold+new這條entry亚亲，這意味著那個(gè)leader必定在Cold+new的配置下生存（living by it）彻采，即leader選舉過程必須獲得old配置中的大多數(shù)和new配置中的大多數(shù)同時(shí)投票，某條entry提交也必須要求這條entry存在于old配置中的大多數(shù)servers和new配置中的大多數(shù)servers上捌归；因此肛响，集群中不可能再有任何server僅僅基于old配置中的大多數(shù)來做決定。
所以在Cold+new已被committed的之后惜索，集群就會在joint-consensus（聯(lián)合一致性）下運(yùn)行特笋；而一旦joint-consensus被committed，leader就會傳播Cnew這條log entry门扇，即將配置變更為Cnew這條entry寫入自己的log雹有，并復(fù)制到其他servers上偿渡；
同樣，在其后一段時(shí)間內(nèi)霸奕，集群有可能在joint-consensus下運(yùn)行（即Cold+new下）溜宽，有可能在Cnew下運(yùn)行；但最終质帅，Cnew這條entry總能被committed适揉；而一旦Cnew被committed，后續(xù)的所有decision-making都必須基于Cnew了煤惩；
因此嫉嘀，這里的關(guān)鍵點(diǎn)在于：決不允許Cold和Cnew都能make decision，而不互相consult（參考魄揉、詢問）剪侮！最初的一段時(shí)間，僅僅依靠Cold就可以make decison洛退；最終的一段時(shí)間瓣俯，僅僅依靠Cnew就可以make decison；但是我們能確保這兩個(gè)時(shí)間段沒有重疊兵怯。而在這兩段時(shí)間之間彩匕，兩個(gè)配置必須互相consult，這就確保了集群在任何時(shí)候都不可能同時(shí)形成兩個(gè)獨(dú)立的consensus媒区。
另外說明下驼仪，這種2-phase特性是非常基本的袜漩，任何一致性算法都會采用某種形式的2-phase來變更配置绪爸。事實(shí)上，任何形式的distributed agreement都要求two phases宙攻；如果有人發(fā)明了新的distributed agreement algorithm毡泻，并聲稱可以在single phase內(nèi)完成，你需要嚴(yán)重質(zhì)疑他：要么他們錯了粘优，要么他們發(fā)現(xiàn)了我們都不知道的新東西。
（點(diǎn)評：joint-consensus的核心關(guān)鍵點(diǎn)在于：如何避免新舊配置同時(shí)存在而產(chǎn)生majority conflict呻顽，進(jìn)而導(dǎo)致decision conflict雹顺，從而產(chǎn)生不一致。這里采用了過渡方法廊遍，認(rèn)真思考嬉愧，其實(shí)單獨(dú)地只有2種形式的decison-making依據(jù)：a.獲取Cold中的majority的支持? b.獲得Cnew中的majority的支持；但是如果簡單粗暴地從a切換到b喉前，其實(shí)是做不到的没酣，因?yàn)椴豢赡苁且粋€(gè)原子操作王财，中間必然有一段時(shí)間，會存在a和b都生效裕便，那么就可能會產(chǎn)生沖突绒净。這里采用了一種漸進(jìn)的思路：
a -> a || (a&b) -> a&b -> (a&b) || b -> b
實(shí)質(zhì)上，將整個(gè)集群可能的decison-making依賴的majority狀態(tài)空間分成了5個(gè)階段偿衰，分別是：
old中大多數(shù)做決定 -> （old中的大多數(shù)做決定） 或者 （old和new中的大多數(shù)同時(shí)做決定） ->
（old和new中的大多數(shù)同時(shí)做決定）-> （old和new中的大多數(shù)同時(shí)做決定） 或者 （new中的大多數(shù)做決定） -> new中的大多數(shù)做決定
這種狀態(tài)變遷的核心與關(guān)鍵在于：這種變遷是漸進(jìn)的挂疆，每一個(gè)階段都不會產(chǎn)生decison-conflict，從而保證變更過程的平穩(wěn)下翎。如果不這樣做缤言，直接變更 a ->b，顯然這種粗暴的做法會導(dǎo)致decison-conflict视事。）
slide 30：
Joint-consensus這部分還有一些細(xì)節(jié)：
1）在變更的過程中胆萧，來自新舊配置的server都有可能成為leader；
2）如果當(dāng)前l(fā)eader不在Cnew配置里面俐东，則一旦Cnew提交跌穗，它必須step down（下臺）；
這意味著犬性，舊leader不再是新配置的成員之后瞻离，還有可能繼續(xù)服務(wù)一小段時(shí)間；即舊leader可能在Cnew配置下繼續(xù)當(dāng)leader（雖然實(shí)質(zhì)上并不是leader乒裆，但仍發(fā)揮leader的作用）套利，直到Cnew的entry能夠復(fù)制到足夠多的server上而被committed；
slide 31：
Congratulations鹤耍！終于介紹完了raft肉迫。這里簡要回顧下raft的6個(gè)部分：
1）leader election：我們確保任何時(shí)間，一個(gè)term內(nèi)至多只有一個(gè)leader稿黄；
2）normal operation：leader接收client的請求喊衫，寫log并復(fù)制到集群中其他機(jī)器；注意AppendEntries時(shí)非常重要的consistency check杆怕，用于確保log的一致性族购，并在log不一致時(shí)用來恢復(fù)一致性；
3）safety and consistency：主要講leader changeovers陵珍，涉及兩個(gè)重大問題寝杖。一是保證系統(tǒng)safety，我們展示了如何保證某條entry一旦被committed就永久存在互纯；二是確保一致性瑟幕，即leader如何確保最終所有followers的log都與其完全相同；
4）neutralize old leaders：一旦有新leader，舊leader就不能再發(fā)號施令只盹。
5）client protocol：簡要介紹了client與raft的交互辣往，特別是raft中server crash之后，client需要怎么做殖卑；
6）configuration changes：講了raft如何自動并安全地進(jìn)行配置變更站削。
最后，對整個(gè)raft算法進(jìn)行整體評論：這個(gè)算法的核心是系統(tǒng)必須完美運(yùn)行懦鼠，即使只有majority的servers在線钻哩。這意味著，永遠(yuǎn)不能依賴全部server的信息肛冶，因?yàn)榭偪赡軙衧erver宕機(jī)街氢，這完全是未知的，算法必須考慮到這點(diǎn)并完美處理睦袖。
（點(diǎn)評：raft的核心思想跟其他一致性算法是相同的珊肃，即你不能要求系統(tǒng)中所有個(gè)體都運(yùn)行良好，你必須要做出讓步馅笙，即不要求系統(tǒng)中所有個(gè)體良好伦乔，只要系統(tǒng)中大部分個(gè)體良好，系統(tǒng)就要能良好地運(yùn)行下去董习。而如何保證系統(tǒng)中大多數(shù)行為一致烈和，就能達(dá)到最終系統(tǒng)所有個(gè)體作為一個(gè)整體行為一致呢呼猪？這其實(shí)就是分布式一致性算法需要解決的問題执解，其實(shí)是提出了更高的要求。其中最核心的要求就是兩點(diǎn)：一是safety审丘，即無論如何都要保證系統(tǒng)不出問題窝趣；二是liveness疯暑，即系統(tǒng)要前進(jìn)、要運(yùn)行哑舒、要為client服務(wù)妇拯，不能只是不出問題，還要保證能及時(shí)地干活洗鸵、能良好地運(yùn)轉(zhuǎn)下去越锈。）
