尋找一種易于理解的一致性算法（擴展版）

摘要

Raft 是一種為了管理復(fù)制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能营搅，但是它的算法結(jié)構(gòu)和 Paxos 不同云挟，使得 Raft 算法更加容易理解并且更容易構(gòu)建實際的系統(tǒng)。為了提升可理解性转质，Raft 將一致性算法分解成了幾個關(guān)鍵模塊园欣，例如領(lǐng)導(dǎo)人選舉、日志復(fù)制和安全性休蟹。同時它通過實施一個更強的一致性來減少需要考慮的狀態(tài)的數(shù)量沸枯。從一個用戶研究的結(jié)果可以證明，對于學(xué)生而言赂弓，Raft 算法比 Paxos 算法更加容易學(xué)習(xí)绑榴。Raft 算法還包括一個新的機制來允許集群成員的動態(tài)改變，它利用重疊的大多數(shù)來保證安全性拣展。

1 介紹

一致性算法允許一組機器像一個整體一樣工作彭沼，即使其中一些機器出現(xiàn)故障也能夠繼續(xù)工作下去。正因為如此备埃，一致性算法在構(gòu)建可信賴的大規(guī)模軟件系統(tǒng)中扮演著重要的角色姓惑。在過去的 10 年里，Paxos 算法統(tǒng)治著一致性算法這一領(lǐng)域：絕大多數(shù)的實現(xiàn)都是基于 Paxos 或者受其影響按脚。同時 Paxos 也成為了教學(xué)領(lǐng)域里講解一致性問題時的示例于毙。

但是不幸的是，盡管有很多工作都在嘗試降低它的復(fù)雜性辅搬，但是 Paxos 算法依然十分難以理解唯沮。并且，Paxos 自身的算法結(jié)構(gòu)需要進行大幅的修改才能夠應(yīng)用到實際的系統(tǒng)中堪遂。這些都導(dǎo)致了工業(yè)界和學(xué)術(shù)界都對 Paxos 算法感到十分頭疼介蛉。

和 Paxos 算法進行過努力之后，我們開始尋找一種新的一致性算法溶褪，可以為構(gòu)建實際的系統(tǒng)和教學(xué)提供更好的基礎(chǔ)币旧。我們的做法是不尋常的，我們的首要目標(biāo)是可理解性：我們是否可以在實際系統(tǒng)中定義一個一致性算法猿妈，并且能夠比 Paxos 算法以一種更加容易的方式來學(xué)習(xí)吹菱。此外巍虫，我們希望該算法方便系統(tǒng)構(gòu)建者的直覺的發(fā)展。不僅一個算法能夠工作很重要鳍刷，而且能夠顯而易見的知道為什么能工作也很重要占遥。

Raft 一致性算法就是這些工作的結(jié)果。在設(shè)計 Raft 算法的時候输瓜，我們使用一些特別的技巧來提升它的可理解性瓦胎，包括算法分解（Raft 主要被分成了領(lǐng)導(dǎo)人選舉，日志復(fù)制和安全三個模塊）和減少狀態(tài)機的狀態(tài)（相對于 Paxos前痘，Raft 減少了非確定性和服務(wù)器互相處于非一致性的方式）凛捏。一份針對兩所大學(xué) 43 個學(xué)生的研究表明 Raft 明顯比 Paxos 算法更加容易理解担忧。在這些學(xué)生同時學(xué)習(xí)了這兩種算法之后芹缔，和 Paxos 比起來，其中 33 個學(xué)生能夠回答有關(guān)于 Raft 的問題瓶盛。

Raft 算法在許多方面和現(xiàn)有的一致性算法都很相似（主要是 Oki 和 Liskov 的 Viewstamped Replication）最欠，但是它也有一些獨特的特性：

• 強領(lǐng)導(dǎo)者：和其他一致性算法相比，Raft 使用一種更強的領(lǐng)導(dǎo)能力形式惩猫。比如芝硬，日志條目只從領(lǐng)導(dǎo)者發(fā)送給其他的服務(wù)器。這種方式簡化了對復(fù)制日志的管理并且使得 Raft 算法更加易于理解轧房。
• 領(lǐng)導(dǎo)選舉：Raft 算法使用一個隨機計時器來選舉領(lǐng)導(dǎo)者拌阴。這種方式只是在任何一致性算法都必須實現(xiàn)的心跳機制上增加了一點機制。在解決沖突的時候會更加簡單快捷奶镶。
• 成員關(guān)系調(diào)整：Raft 使用一種共同一致的方法來處理集群成員變換的問題迟赃，在這種方法下，處于調(diào)整過程中的兩種不同的配置集群中大多數(shù)機器會有重疊厂镇，這就使得集群在成員變換的時候依然可以繼續(xù)工作纤壁。

我們相信，Raft 算法不論出于教學(xué)目的還是作為實踐項目的基礎(chǔ)都是要比 Paxos 或者其他一致性算法要優(yōu)異的捺信。它比其他算法更加簡單酌媒，更加容易理解；它的算法描述足以實現(xiàn)一個現(xiàn)實的系統(tǒng)迄靠；它有好多開源的實現(xiàn)并且在很多公司里使用秒咨；它的安全性已經(jīng)被證明；它的效率和其他算法比起來也不相上下掌挚。

接下來雨席，這篇論文會介紹以下內(nèi)容：復(fù)制狀態(tài)機問題（第 2 節(jié)），討論 Paxos 的優(yōu)點和缺點（第 3 節(jié)）疫诽，討論我們?yōu)榱死斫饽芰Χ褂玫姆椒ǎǖ?4 節(jié)）舅世，闡述 Raft 一致性算法（第 5-8 節(jié)）旦委，評價 Raft 算法（第 9 節(jié)），以及一些相關(guān)的工作（第 10 節(jié)）雏亚。

2 復(fù)制狀態(tài)機

一致性算法是從復(fù)制狀態(tài)機的背景下提出的（參考英文原文引用37）缨硝。在這種方法中，一組服務(wù)器上的狀態(tài)機產(chǎn)生相同狀態(tài)的副本罢低，并且在一些機器宕掉的情況下也可以繼續(xù)運行查辩。復(fù)制狀態(tài)機在分布式系統(tǒng)中被用于解決很多容錯的問題。例如网持，大規(guī)模的系統(tǒng)中通常都有一個集群領(lǐng)導(dǎo)者宜岛，像 GFS、HDFS 和 RAMCloud功舀，典型應(yīng)用就是一個獨立的的復(fù)制狀態(tài)機去管理領(lǐng)導(dǎo)選舉和存儲配置信息并且在領(lǐng)導(dǎo)人宕機的情況下也要存活下來萍倡。比如 Chubby 和 ZooKeeper。

圖 1

圖 1 ：復(fù)制狀態(tài)機的結(jié)構(gòu)辟汰。一致性算法管理著來自客戶端指令的復(fù)制日志列敲。狀態(tài)機從日志中處理相同順序的相同指令，所以產(chǎn)生的結(jié)果也是相同的帖汞。

復(fù)制狀態(tài)機通常都是基于復(fù)制日志實現(xiàn)的戴而，如圖 1。每一個服務(wù)器存儲一個包含一系列指令的日志翩蘸，并且按照日志的順序進行執(zhí)行所意。每一個日志都按照相同的順序包含相同的指令，所以每一個服務(wù)器都執(zhí)行相同的指令序列催首。因為每個狀態(tài)機都是確定的扶踊，每一次執(zhí)行操作都產(chǎn)生相同的狀態(tài)和同樣的序列状原。

保證復(fù)制日志相同就是一致性算法的工作了克懊。在一臺服務(wù)器上两曼，一致性模塊接收客戶端發(fā)送來的指令然后增加到自己的日志中去原杂。它和其他服務(wù)器上的一致性模塊進行通信來保證每一個服務(wù)器上的日志最終都以相同的順序包含相同的請求长捧，盡管有些服務(wù)器會宕機踪蹬。一旦指令被正確的復(fù)制搀暑，每一個服務(wù)器的狀態(tài)機按照日志順序處理他們假褪，然后輸出結(jié)果被返回給客戶端歼疮。因此杂抽，服務(wù)器集群看起來形成一個高可靠的狀態(tài)機。

實際系統(tǒng)中使用的一致性算法通常含有以下特性：

• 安全性保證（絕對不會返回一個錯誤的結(jié)果）：在非拜占庭錯誤情況下韩脏，包括網(wǎng)絡(luò)延遲缩麸、分區(qū)、丟包赡矢、冗余和亂序等錯誤都可以保證正確杭朱。
• 可用性：集群中只要有大多數(shù)的機器可運行并且能夠相互通信阅仔、和客戶端通信，就可以保證可用弧械。因此八酒，一個典型的包含 5 個節(jié)點的集群可以容忍兩個節(jié)點的失敗。服務(wù)器被停止就認(rèn)為是失敗刃唐。他們當(dāng)有穩(wěn)定的存儲的時候可以從狀態(tài)中恢復(fù)回來并重新加入集群羞迷。
• 不依賴時序來保證一致性：物理時鐘錯誤或者極端的消息延遲在可能只有在最壞情況下才會導(dǎo)致可用性問題。
• 通常情況下画饥，一條指令可以盡可能快的在集群中大多數(shù)節(jié)點響應(yīng)一輪遠程過程調(diào)用時完成衔瓮。小部分比較慢的節(jié)點不會影響系統(tǒng)整體的性能。

3 Paxos算法的問題

在過去的 10 年里抖甘，Leslie Lamport 的 Paxos 算法幾乎已經(jīng)成為一致性的代名詞：Paxos 是在課程教學(xué)中最經(jīng)常使用的算法热鞍，同時也是大多數(shù)一致性算法實現(xiàn)的起點。Paxos 首先定義了一個能夠達成單一決策一致的協(xié)議单山，比如單條的復(fù)制日志項碍现。我們把這一子集叫做單決策 Paxos幅疼。然后通過組合多個 Paxos 協(xié)議的實例來促進一系列決策的達成米奸。Paxos 保證安全性和活性，同時也支持集群成員關(guān)系的變更爽篷。Paxos 的正確性已經(jīng)被證明悴晰，在通常情況下也很高效。

不幸的是逐工，Paxos 有兩個明顯的缺點铡溪。第一個缺點是 Paxos 算法特別的難以理解。完整的解釋是出了名的不透明泪喊；通過極大的努力之后棕硫，也只有少數(shù)人成功理解了這個算法。因此袒啼，有了幾次用更簡單的術(shù)語來解釋 Paxos 的嘗試哈扮。盡管這些解釋都只關(guān)注了單決策的子集問題，但依然很具有挑戰(zhàn)性蚓再。在 2012 年 NSDI 的會議中的一次調(diào)查顯示滑肉，很少有人對 Paxos 算法感到滿意，甚至在經(jīng)驗老道的研究者中也是如此摘仅。我們自己也嘗試去理解 Paxos靶庙；我們一直沒能理解 Paxos 直到我們讀了很多對 Paxos 的簡化解釋并且設(shè)計了我們自己的算法之后，這一過程花了近一年時間娃属。

我們假設(shè) Paxos 的不透明性來自它選擇單決策問題作為它的基礎(chǔ)六荒。單決策 Paxos 是晦澀微妙的护姆，它被劃分成了兩種沒有簡單直觀解釋和無法獨立理解的情景。因此掏击，這導(dǎo)致了很難建立起直觀的感受為什么單決策 Paxos 算法能夠工作签则。構(gòu)成多決策 Paxos 增加了很多錯綜復(fù)雜的規(guī)則。我們相信铐料，在多決策上達成一致性的問題（一份日志而不是單一的日志記錄）能夠被分解成其他的方式并且更加直接和明顯渐裂。

Paxos算法的第二個問題就是它沒有提供一個足夠好的用來構(gòu)建一個現(xiàn)實系統(tǒng)的基礎(chǔ)。一個原因是還沒有一種被廣泛認(rèn)同的多決策問題的算法钠惩。Lamport 的描述基本上都是關(guān)于單決策 Paxos 的柒凉；他簡要描述了實施多決策 Paxos 的方法，但是缺乏很多細節(jié)篓跛。當(dāng)然也有很多具體化 Paxos 的嘗試膝捞，但是他們都互相不一樣，和 Paxos 的概述也不同愧沟。例如 Chubby 這樣的系統(tǒng)實現(xiàn)了一個類似于 Paxos 的算法蔬咬，但是大多數(shù)的細節(jié)并沒有被公開。

而且沐寺，Paxos 算法的結(jié)構(gòu)也不是十分易于構(gòu)建實踐的系統(tǒng)林艘；單決策分解也會產(chǎn)生其他的結(jié)果。例如混坞，獨立的選擇一組日志條目然后合并成一個序列化的日志并沒有帶來太多的好處狐援，僅僅增加了不少復(fù)雜性。圍繞著日志來設(shè)計一個系統(tǒng)是更加簡單高效的究孕；新日志條目以嚴(yán)格限制的順序增添到日志中去啥酱。另一個問題是，Paxos 使用了一種對等的點對點的方式作為它的核心（盡管它最終提議了一種弱領(lǐng)導(dǎo)人的方法來優(yōu)化性能）厨诸。在只有一個決策會被制定的簡化世界中是很有意義的镶殷，但是很少有現(xiàn)實的系統(tǒng)使用這種方式。如果有一系列的決策需要被制定微酬，首先選擇一個領(lǐng)導(dǎo)人绘趋，然后讓他去協(xié)調(diào)所有的決議，會更加簡單快速得封。

因此埋心，實際的系統(tǒng)中很少有和 Paxos 相似的實踐。每一種實現(xiàn)都是從 Paxos 開始研究忙上，然后發(fā)現(xiàn)很多實現(xiàn)上的難題拷呆，再然后開發(fā)了一種和 Paxos 明顯不一樣的結(jié)構(gòu)。這樣非常費時和容易出錯的，并且理解 Paxos 的難度是的這個問題更加糟糕茬斧。Paxos 算法在理論上被證明是正確可行的腰懂，但是現(xiàn)實的系統(tǒng)和 Paxos 差別是如此的大，以至于這些證明沒有什么太大的價值项秉。下面來自 Chubby 實現(xiàn)非常典型：

在Paxos算法描述和實現(xiàn)現(xiàn)實系統(tǒng)中間有者巨大的鴻溝绣溜。最終的系統(tǒng)建立在一種沒有經(jīng)過證明的算法之上。

由于以上問題娄蔼，我們認(rèn)為 Paxos 算法既沒有提供一個良好的基礎(chǔ)給實踐的系統(tǒng)怖喻，也沒有給教學(xué)很好的幫助∷晁撸基于一致性問題在大規(guī)模軟件系統(tǒng)中的重要性锚沸，我們決定看看我們是否可以設(shè)計一個擁有更好特性的替代 Paxos 的一致性算法。Raft算法就是這次實驗的結(jié)果涕癣。

4 為了可理解性的設(shè)計

設(shè)計 Raft 算法我們有幾個初衷：它必須提供一個完整的實際的系統(tǒng)實現(xiàn)基礎(chǔ)哗蜈，這樣才能大大減少開發(fā)者的工作；它必須在任何情況下都是安全的并且在大多數(shù)的情況下都是可用的坠韩；并且它的大部分操作必須是高效的距潘。但是我們最重要也是最大的挑戰(zhàn)是可理解性。它必須保證對于普遍的人群都可以十分容易的去理解只搁。另外音比，它必須能夠讓人形成直觀的認(rèn)識，這樣系統(tǒng)的構(gòu)建者才能夠在現(xiàn)實中進行必然的擴展须蜗。

在設(shè)計 Raft 算法的時候硅确，有很多的點需要我們在各種備選方案中進行選擇。在這種情況下明肮，我們評估備選方案基于可理解性原則：解釋各個備選方案有多大的難度（例如，Raft 的狀態(tài)空間有多復(fù)雜缭付，是否有微妙的暗示）柿估？對于一個讀者而言，完全理解這個方案和暗示是否容易陷猫？

我們意識到對這種可理解性分析上具有高度的主觀性秫舌；盡管如此，我們使用了兩種通常適用的技術(shù)來解決這個問題绣檬。第一個技術(shù)就是眾所周知的問題分解：只要有可能足陨，我們就將問題分解成幾個相對獨立的，可被解決的娇未、可解釋的和可理解的子問題墨缘。例如，Raft 算法被我們分成領(lǐng)導(dǎo)人選舉，日志復(fù)制镊讼，安全性和角色改變幾個部分宽涌。

我們使用的第二個方法是通過減少狀態(tài)的數(shù)量來簡化需要考慮的狀態(tài)空間，使得系統(tǒng)更加連貫并且在可能的時候消除不確定性蝶棋。特別的卸亮，所有的日志是不允許有空洞的，并且 Raft 限制了日志之間變成不一致狀態(tài)的可能玩裙。盡管在大多數(shù)情況下我們都試圖去消除不確定性兼贸，但是也有一些情況下不確定性可以提升可理解性。尤其是吃溅，隨機化方法增加了不確定性寝受，但是他們有利于減少狀態(tài)空間數(shù)量，通過處理所有可能選擇時使用相似的方法罕偎。我們使用隨機化去簡化 Raft 中領(lǐng)導(dǎo)人選舉算法很澄。

5 Raft 一致性算法

Raft 是一種用來管理章節(jié) 2 中描述的復(fù)制日志的算法。圖 2 為了參考之用颜及，總結(jié)這個算法的簡略版本甩苛，圖 3 列舉了這個算法的一些關(guān)鍵特性。圖中的這些元素會在剩下的章節(jié)逐一介紹俏站。

Raft 通過選舉一個高貴的領(lǐng)導(dǎo)人讯蒲，然后給予他全部的管理復(fù)制日志的責(zé)任來實現(xiàn)一致性。領(lǐng)導(dǎo)人從客戶端接收日志條目肄扎，把日志條目復(fù)制到其他服務(wù)器上墨林，并且當(dāng)保證安全性的時候告訴其他的服務(wù)器應(yīng)用日志條目到他們的狀態(tài)機中。擁有一個領(lǐng)導(dǎo)人大大簡化了對復(fù)制日志的管理犯祠。例如旭等，領(lǐng)導(dǎo)人可以決定新的日志條目需要放在日志中的什么位置而不需要和其他服務(wù)器商議，并且數(shù)據(jù)都從領(lǐng)導(dǎo)人流向其他服務(wù)器衡载。一個領(lǐng)導(dǎo)人可以宕機搔耕，可以和其他服務(wù)器失去連接，這時一個新的領(lǐng)導(dǎo)人會被選舉出來痰娱。

通過領(lǐng)導(dǎo)人的方式弃榨，Raft 將一致性問題分解成了三個相對獨立的子問題，這些問題會在接下來的子章節(jié)中進行討論：

• 領(lǐng)導(dǎo)選舉：一個新的領(lǐng)導(dǎo)人需要被選舉出來梨睁，當(dāng)現(xiàn)存的領(lǐng)導(dǎo)人宕機的時候（章節(jié) 5.2）
• 日志復(fù)制：領(lǐng)導(dǎo)人必須從客戶端接收日志然后復(fù)制到集群中的其他節(jié)點鲸睛，并且強制要求其他節(jié)點的日志保持和自己相同。
• 安全性：在 Raft 中安全性的關(guān)鍵是在圖 3 中展示的狀態(tài)機安全：如果有任何的服務(wù)器節(jié)點已經(jīng)應(yīng)用了一個確定的日志條目到它的狀態(tài)機中坡贺，那么其他服務(wù)器節(jié)點不能在同一個日志索引位置應(yīng)用一個不同的指令官辈。章節(jié) 5.4 闡述了 Raft 算法是如何保證這個特性的箱舞；這個解決方案涉及到一個額外的選舉機制（5.2 節(jié)）上的限制。

在展示一致性算法之后钧萍，這一章節(jié)會討論可用性的一些問題和系統(tǒng)中的候選人角色的問題褐缠。

狀態(tài)：

附加日志 RPC：

由領(lǐng)導(dǎo)人負責(zé)調(diào)用來復(fù)制日志指令；也會用作heartbeat

接收者實現(xiàn)：

1. 如果 term < currentTerm 就返回 false （5.1 節(jié)）
2. 如果日志在 prevLogIndex 位置處的日志條目的任期號和 prevLogTerm 不匹配酗捌，則返回 false （5.3 節(jié)）
3. 如果已經(jīng)存在的日志條目和新的產(chǎn)生沖突（索引值相同但是任期號不同）呢诬，刪除這一條和之后所有的 （5.3 節(jié)）
4. 附加任何在已有的日志中不存在的條目
5. 如果 leaderCommit > commitIndex，令 commitIndex 等于 leaderCommit 和 新日志條目索引值中較小的一個

請求投票 RPC：

由候選人負責(zé)調(diào)用用來征集選票（5.2 節(jié)）

接收者實現(xiàn)：

1. 如果term < currentTerm返回 false （5.2 節(jié)）
2. 如果 votedFor 為空或者就是 candidateId尚镰，并且候選人的日志至少和自己一樣新，那么就投票給他（5.2 節(jié)哪廓，5.4 節(jié)）

所有服務(wù)器需遵守的規(guī)則：

所有服務(wù)器：

• 如果commitIndex > lastApplied狗唉，那么就 lastApplied 加一，并把log[lastApplied]應(yīng)用到狀態(tài)機中（5.3 節(jié)）
• 如果接收到的 RPC 請求或響應(yīng)中涡真，任期號T > currentTerm分俯，那么就令 currentTerm 等于 T，并切換狀態(tài)為跟隨者（5.1 節(jié)）

跟隨者（5.2 節(jié)）：

• 響應(yīng)來自候選人和領(lǐng)導(dǎo)者的請求
• 如果在超過選舉超時時間的情況之前都沒有收到領(lǐng)導(dǎo)人的心跳缸剪，或者是候選人請求投票的，就自己變成候選人

候選人（5.2 節(jié)）：

• 在轉(zhuǎn)變成候選人后就立即開始選舉過程
  • 自增當(dāng)前的任期號（currentTerm）
  • 給自己投票
  • 重置選舉超時計時器
  • 發(fā)送請求投票的 RPC 給其他所有服務(wù)器
• 如果接收到大多數(shù)服務(wù)器的選票讥此，那么就變成領(lǐng)導(dǎo)人
• 如果接收到來自新的領(lǐng)導(dǎo)人的附加日志 RPC，轉(zhuǎn)變成跟隨者
• 如果選舉過程超時谣妻，再次發(fā)起一輪選舉

領(lǐng)導(dǎo)人：

• 一旦成為領(lǐng)導(dǎo)人：發(fā)送空的附加日志 RPC（心跳）給其他所有的服務(wù)器萄喳；在一定的空余時間之后不停的重復(fù)發(fā)送，以阻止跟隨者超時（5.2 節(jié)）
• 如果接收到來自客戶端的請求：附加條目到本地日志中蹋半，在條目被應(yīng)用到狀態(tài)機后響應(yīng)客戶端（5.3 節(jié)）
• 如果對于一個跟隨者他巨，最后日志條目的索引值大于等于 nextIndex厅翔，那么：發(fā)送從 nextIndex 開始的所有日志條目：
  • 如果成功：更新相應(yīng)跟隨者的 nextIndex 和 matchIndex
  • 如果因為日志不一致而失敗，減少 nextIndex 重試
• 如果存在一個滿足N > commitIndex的 N蠢琳，并且大多數(shù)的matchIndex[i] ≥ N成立姻僧，并且log[N].term == currentTerm成立，那么令 commitIndex 等于這個 N （5.3 和 5.4 節(jié)）

圖 2：一個關(guān)于 Raft 一致性算法的濃縮總結(jié)（不包括成員變換和日志壓縮）份企。

圖 3：Raft 在任何時候都保證以上的各個特性骂远。

5.1 Raft 基礎(chǔ)

一個 Raft 集群包含若干個服務(wù)器節(jié)點囚霸；通常是 5 個，這允許整個系統(tǒng)容忍 2 個節(jié)點的失效激才。在任何時刻拓型，每一個服務(wù)器節(jié)點都處于這三個狀態(tài)之一：領(lǐng)導(dǎo)人、跟隨者或者候選人瘸恼。在通常情況下劣挫，系統(tǒng)中只有一個領(lǐng)導(dǎo)人并且其他的節(jié)點全部都是跟隨者。跟隨者都是被動的：他們不會發(fā)送任何請求钞脂，只是簡單的響應(yīng)來自領(lǐng)導(dǎo)者或者候選人的請求揣云。領(lǐng)導(dǎo)人處理所有的客戶端請求（如果一個客戶端和跟隨者聯(lián)系，那么跟隨者會把請求重定向給領(lǐng)導(dǎo)人）冰啃。第三種狀態(tài)邓夕，候選人，是用來在 5.2 節(jié)描述的選舉新領(lǐng)導(dǎo)人時使用阎毅。圖 4 展示了這些狀態(tài)和他們之前轉(zhuǎn)換關(guān)系焚刚；這些轉(zhuǎn)換關(guān)系會在接下來進行討論。

圖 4

圖 4：服務(wù)器狀態(tài)扇调。跟隨者只響應(yīng)來自其他服務(wù)器的請求矿咕。如果跟隨者接收不到消息，那么他就會變成候選人并發(fā)起一次選舉狼钮。獲得集群中大多數(shù)選票的候選人將成為領(lǐng)導(dǎo)者碳柱。在一個任期內(nèi),領(lǐng)導(dǎo)人一直都會是領(lǐng)導(dǎo)人直到自己宕機了。

圖 5

圖 5：時間被劃分成一個個的任期熬芜，每個任期開始都是一次選舉莲镣。在選舉成功后，領(lǐng)導(dǎo)人會管理整個集群直到任期結(jié)束涎拉。有時候選舉會失敗瑞侮，那么這個任期就會沒有領(lǐng)導(dǎo)人而結(jié)束的圆。任期之間的切換可以在不同的時間不同的服務(wù)器上觀察到。

Raft 把時間分割成任意長度的任期半火，如圖 5越妈。任期用連續(xù)的整數(shù)標(biāo)記。每一段任期從一次選舉開始钮糖，就像章節(jié) 5.2 描述的一樣梅掠，一個或者多個候選人嘗試成為領(lǐng)導(dǎo)者。如果一個候選人贏得選舉藐鹤，然后他就在接下來的任期內(nèi)充當(dāng)領(lǐng)導(dǎo)人的職責(zé)瓤檐。在某些情況下，一次選舉過程會造成選票的瓜分娱节。在這種情況下挠蛉，這一任期會以沒有領(lǐng)導(dǎo)人結(jié)束；一個新的任期（和一次新的選舉）會很快重新開始肄满。Raft 保證了在一個給定的任期內(nèi)谴古，最多只有一個領(lǐng)導(dǎo)者。

不同的服務(wù)器節(jié)點可能多次觀察到任期之間的轉(zhuǎn)換稠歉，但在某些情況下掰担，一個節(jié)點也可能觀察不到任何一次選舉或者整個任期全程。任期在 Raft 算法中充當(dāng)邏輯時鐘的作用怒炸，這會允許服務(wù)器節(jié)點查明一些過期的信息比如陳舊的領(lǐng)導(dǎo)者带饱。每一個節(jié)點存儲一個當(dāng)前任期號，這一編號在整個時期內(nèi)單調(diào)的增長阅羹。當(dāng)服務(wù)器之間通信的時候會交換當(dāng)前任期號勺疼；如果一個服務(wù)器的當(dāng)前任期號比其他人小，那么他會更新自己的編號到較大的編號值捏鱼。如果一個候選人或者領(lǐng)導(dǎo)者發(fā)現(xiàn)自己的任期號過期了执庐，那么他會立即恢復(fù)成跟隨者狀態(tài)。如果一個節(jié)點接收到一個包含過期的任期號的請求导梆，那么他會直接拒絕這個請求轨淌。

Raft 算法中服務(wù)器節(jié)點之間通信使用遠程過程調(diào)用（RPCs），并且基本的一致性算法只需要兩種類型的 RPCs看尼。請求投票（RequestVote） RPCs 由候選人在選舉期間發(fā)起（章節(jié) 5.2）递鹉，然后附加條目（AppendEntries）RPCs 由領(lǐng)導(dǎo)人發(fā)起，用來復(fù)制日志和提供一種心跳機制（章節(jié) 5.3）藏斩。第 7 節(jié)為了在服務(wù)器之間傳輸快照增加了第三種 RPC梳虽。當(dāng)服務(wù)器沒有及時的收到 RPC 的響應(yīng)時，會進行重試灾茁， 并且他們能夠并行的發(fā)起 RPCs 來獲得最佳的性能窜觉。

5.2 領(lǐng)導(dǎo)人選舉

Raft 使用一種心跳機制來觸發(fā)領(lǐng)導(dǎo)人選舉。當(dāng)服務(wù)器程序啟動時北专，他們都是跟隨者身份禀挫。一個服務(wù)器節(jié)點繼續(xù)保持著跟隨者狀態(tài)如果他從領(lǐng)導(dǎo)人或者候選者處接收到有效的 RPCs。領(lǐng)導(dǎo)者周期性的向所有跟隨者發(fā)送心跳包（不包含日志項內(nèi)容的附加日志項 RPCs）來維持自己的權(quán)威拓颓。如果一個跟隨者在一段時間里沒有接收到任何消息语婴，也就是選舉超時，然后他就會認(rèn)為系統(tǒng)中沒有可用的領(lǐng)導(dǎo)者然后開始進行選舉以選出新的領(lǐng)導(dǎo)者驶睦。

要開始一次選舉過程砰左，跟隨者先要增加自己的當(dāng)前任期號并且轉(zhuǎn)換到候選人狀態(tài)。然后他會并行的向集群中的其他服務(wù)器節(jié)點發(fā)送請求投票的 RPCs 來給自己投票场航。候選人會繼續(xù)保持著當(dāng)前狀態(tài)直到以下三件事情之一發(fā)生：(a) 他自己贏得了這次的選舉缠导，(b) 其他的服務(wù)器成為領(lǐng)導(dǎo)者，(c) 一段時間之后沒有任何一個獲勝的人溉痢。這些結(jié)果會分別的在下面的段落里進行討論僻造。

當(dāng)一個候選人從整個集群的大多數(shù)服務(wù)器節(jié)點獲得了針對同一個任期號的選票，那么他就贏得了這次選舉并成為領(lǐng)導(dǎo)人孩饼。每一個服務(wù)器最多會對一個任期號投出一張選票髓削，按照先來先服務(wù)的原則（注意：5.4 節(jié)在投票上增加了一點額外的限制）。要求大多數(shù)選票的規(guī)則確保了最多只會有一個候選人贏得此次選舉（圖 3 中的選舉安全性）镀娶。一旦候選人贏得選舉立膛，他就立即成為領(lǐng)導(dǎo)人。然后他會向其他的服務(wù)器發(fā)送心跳消息來建立自己的權(quán)威并且阻止新的領(lǐng)導(dǎo)人的產(chǎn)生梯码。

在等待投票的時候宝泵，候選人可能會從其他的服務(wù)器接收到聲明它是領(lǐng)導(dǎo)人的附加日志項 RPC。如果這個領(lǐng)導(dǎo)人的任期號（包含在此次的 RPC中）不小于候選人當(dāng)前的任期號忍些，那么候選人會承認(rèn)領(lǐng)導(dǎo)人合法并回到跟隨者狀態(tài)鲁猩。 如果此次 RPC 中的任期號比自己小，那么候選人就會拒絕這次的 RPC 并且繼續(xù)保持候選人狀態(tài)罢坝。

第三種可能的結(jié)果是候選人既沒有贏得選舉也沒有輸：如果有多個跟隨者同時成為候選人廓握，那么選票可能會被瓜分以至于沒有候選人可以贏得大多數(shù)人的支持。當(dāng)這種情況發(fā)生的時候嘁酿，每一個候選人都會超時隙券，然后通過增加當(dāng)前任期號來開始一輪新的選舉。然而闹司，沒有其他機制的話娱仔，選票可能會被無限的重復(fù)瓜分。

Raft 算法使用隨機選舉超時時間的方法來確保很少會發(fā)生選票瓜分的情況游桩，就算發(fā)生也能很快的解決牲迫。為了阻止選票起初就被瓜分耐朴，選舉超時時間是從一個固定的區(qū)間（例如 150-300毫秒）隨機選擇。這樣可以把服務(wù)器都分散開以至于在大多數(shù)情況下只有一個服務(wù)器會選舉超時盹憎；然后他贏得選舉并在其他服務(wù)器超時之前發(fā)送心跳包筛峭。同樣的機制被用在選票瓜分的情況下。每一個候選人在開始一次選舉的時候會重置一個隨機的選舉超時時間陪每，然后在下次選舉之前一直等待影晓；這樣減少了在新的選舉中另外的選票瓜分的可能性。9.3 節(jié)展示了這種方案能夠快速的選出一個領(lǐng)導(dǎo)人檩禾。

選舉是一個用來展示在選擇設(shè)計替代方案的時候可理解性是如何指導(dǎo)我們的例子挂签。起初我們計劃使用一種排名系統(tǒng)：每一個候選人都被賦予一個唯一的排名，排名用來在候選人之間競爭時進行選擇盼产。如果一個候選人發(fā)現(xiàn)另一個候選人擁有更高的排名饵婆，那么他就會回到跟隨者狀態(tài)，這樣高排名的候選人能夠更加容易的贏得下一次選舉辆飘。但是我們發(fā)現(xiàn)這種方法在可用性方面會有一點問題（一個低排名的服務(wù)器可能會再次的超時并成為候選人當(dāng)高排名的服務(wù)器宕機時啦辐，但是如果他這么做太快，他會重置掉一個選舉過程）蜈项。我們針對算法進行了多次調(diào)整芹关，但是每次調(diào)整之后都會有新的問題。最終我們認(rèn)為隨機重試的方法是更加明顯和易于理解的紧卒。

5.3 日志復(fù)制

一旦一個領(lǐng)導(dǎo)人被選舉出來侥衬，他就開始為客戶端提供服務(wù)∨芊迹客戶端的每一個請求都包含一條被復(fù)制狀態(tài)機執(zhí)行的指令轴总。領(lǐng)導(dǎo)人把這條指令作為一條新的日志條目附加到日志中去，然后并行的發(fā)起附加條目 RPCs 給其他的服務(wù)器博个，讓他們復(fù)制這條日志條目怀樟。當(dāng)這條日志條目被安全的復(fù)制（下面會介紹），領(lǐng)導(dǎo)人會應(yīng)用這條日志條目到它的狀態(tài)機中然后把執(zhí)行的結(jié)果返回給客戶端盆佣。如果跟隨者崩潰或者運行緩慢往堡，再或者網(wǎng)絡(luò)丟包，領(lǐng)導(dǎo)人會不斷的重復(fù)嘗試附加日志條目 RPCs （盡管已經(jīng)回復(fù)了客戶端）直到所有的跟隨者都最終存儲了所有的日志條目共耍。

圖 6

圖 6：日志由有序序號標(biāo)記的條目組成虑灰。每個條目都包含創(chuàng)建時的任期號（圖中框中的數(shù)字），和一個狀態(tài)機需要執(zhí)行的指令痹兜。一個條目當(dāng)可以安全的被應(yīng)用到狀態(tài)機中去的時候穆咐，就認(rèn)為是可以提交了。

日志以圖 6 展示的方式組織。每一個日志條目存儲一條狀態(tài)機指令和從領(lǐng)導(dǎo)人收到這條指令時的任期號对湃。在日志中的任期號是用來檢查不一致情況崖叫，同時也用來保證圖 3 中的某些性質(zhì)。每一條日志條目同時也都有一個整數(shù)索引值來表明它在日志中的位置熟尉。

領(lǐng)導(dǎo)人來決定什么時候把日志條目應(yīng)用到狀態(tài)機中是安全的归露；這種日志條目被稱為已提交。Raft 算法保證所有已提交的日志條目都是持久化的并且最終會被所有可用的狀態(tài)機執(zhí)行斤儿。在領(lǐng)導(dǎo)人將創(chuàng)建的日志條目復(fù)制到大多數(shù)的服務(wù)器上的時候，日志條目就會被提交（例如在圖 6 中的條目 7）恐锦。同時往果，領(lǐng)導(dǎo)人的日志中之前的所有日志條目也都會被提交，包括由其他領(lǐng)導(dǎo)人創(chuàng)建的條目一铅。5.4 節(jié)會討論某些當(dāng)在領(lǐng)導(dǎo)人改變之后應(yīng)用這條規(guī)則的隱晦內(nèi)容陕贮，同時他也展示了這種提交的定義是安全的。領(lǐng)導(dǎo)人跟蹤了最大的將會被提交的日志項的索引潘飘，并且索引值會被包含在未來的所有附加日志 RPCs （包括心跳包）肮之，這樣其他的服務(wù)器才能最終知道領(lǐng)導(dǎo)人的提交位置。一旦跟隨者知道一條日志條目已經(jīng)被提交卜录，那么他也會將這個日志條目應(yīng)用到本地的狀態(tài)機中（按照日志的順序）戈擒。

我們設(shè)計了 Raft 的日志機制來維護一個不同服務(wù)器的日志之間的高層次的一致性。這么做不僅簡化了系統(tǒng)的行為也使得更加可預(yù)計艰毒，同時他也是安全性保證的一個重要組件筐高。Raft 維護著以下的特性，這些同時也組成了圖 3 中的日志匹配特性：

• 如果在不同的日志中的兩個條目擁有相同的索引和任期號丑瞧，那么他們存儲了相同的指令柑土。
• 如果在不同的日志中的兩個條目擁有相同的索引和任期號，那么他們之前的所有日志條目也全部相同绊汹。

第一個特性來自這樣的一個事實稽屏，領(lǐng)導(dǎo)人最多在一個任期里在指定的一個日志索引位置創(chuàng)建一條日志條目，同時日志條目在日志中的位置也從來不會改變西乖。第二個特性由附加日志 RPC 的一個簡單的一致性檢查所保證狐榔。在發(fā)送附加日志 RPC 的時候，領(lǐng)導(dǎo)人會把新的日志條目緊接著之前的條目的索引位置和任期號包含在里面浴栽。如果跟隨者在它的日志中找不到包含相同索引位置和任期號的條目荒叼，那么他就會拒絕接收新的日志條目。一致性檢查就像一個歸納步驟：一開始空的日志狀態(tài)肯定是滿足日志匹配特性的典鸡，然后一致性檢查保護了日志匹配特性當(dāng)日志擴展的時候被廓。因此，每當(dāng)附加日志 RPC 返回成功時萝玷，領(lǐng)導(dǎo)人就知道跟隨者的日志一定是和自己相同的了嫁乘。

圖 7

圖 7：當(dāng)一個領(lǐng)導(dǎo)人成功當(dāng)選時昆婿，跟隨者可能是任何情況（a-f）。每一個盒子表示是一個日志條目蜓斧；里面的數(shù)字表示任期號仓蛆。跟隨者可能會缺少一些日志條目（a-b），可能會有一些未被提交的日志條目（c-d）挎春，或者兩種情況都存在（e-f）看疙。例如，場景 f 可能這樣發(fā)生直奋，那個服務(wù)器在任期 2 的時候是領(lǐng)導(dǎo)人能庆，附加了一些日志條目到自己的日志中，在提交之前就崩潰了脚线；很快這個機器就重啟了搁胆，在任期 3 重新被選為領(lǐng)導(dǎo)人，并且又增加了一些日志條目到自己的日志中邮绿；在這些任期 2 和任期 3 重點日志被提交之前渠旁，這個服務(wù)器又宕機了，然后的幾個任期里一直處于宕機狀態(tài)船逮。

在正常的操作中顾腊，領(lǐng)導(dǎo)人和跟隨者的日志保持一致性，所以附加日志 RPC 的一致性檢查從來不會失敗傻唾。然而投慈，領(lǐng)導(dǎo)人崩潰的情況會使得日志處于不一致的狀態(tài)（老的領(lǐng)導(dǎo)人可能還沒有完全復(fù)制所有的日志條目）。這種不一致問題會在一系列的領(lǐng)導(dǎo)人和跟隨者崩潰的情況下加劇冠骄。圖 7 展示了跟隨者的日志可能和新的領(lǐng)導(dǎo)人不同的方式伪煤。跟隨者可能會丟失一些在新的領(lǐng)導(dǎo)人中有的日志條目，他也可能擁有一些領(lǐng)導(dǎo)人沒有的日志條目凛辣，或者兩者都發(fā)生抱既。丟失或者多出日志條目可能會持續(xù)多個任期。

在 Raft 算法中扁誓，領(lǐng)導(dǎo)人處理不一致是通過強制跟隨者直接復(fù)制自己的日志來解決了防泵。這意味著在跟隨者中的沖突的日志條目會被領(lǐng)導(dǎo)人的日志覆蓋。5.4 節(jié)會闡述如何通過增加一些限制來使得這樣的操作是安全的蝗敢。

要使得跟隨者的日志進入和自己一致的狀態(tài)捷泞，領(lǐng)導(dǎo)人必須找到最后兩者達成一致的地方，然后刪除從那個點之后的所有日志條目寿谴，發(fā)送自己的日志給跟隨者锁右。所有的這些操作都在進行附加日志 RPCs 的一致性檢查時完成。領(lǐng)導(dǎo)人針對每一個跟隨者維護了一個 nextIndex，這表示下一個需要發(fā)送給跟隨者的日志條目的索引地址咏瑟。當(dāng)一個領(lǐng)導(dǎo)人剛獲得權(quán)力的時候拂到，他初始化所有的 nextIndex 值為自己的最后一條日志的index加1（圖 7 中的 11）。如果一個跟隨者的日志和領(lǐng)導(dǎo)人不一致码泞，那么在下一次的附加日志 RPC 時的一致性檢查就會失敗兄旬。在被跟隨者拒絕之后，領(lǐng)導(dǎo)人就會減小 nextIndex 值并進行重試余寥。最終 nextIndex 會在某個位置使得領(lǐng)導(dǎo)人和跟隨者的日志達成一致领铐。當(dāng)這種情況發(fā)生，附加日志 RPC 就會成功劈狐，這時就會把跟隨者沖突的日志條目全部刪除并且加上領(lǐng)導(dǎo)人的日志罐孝。一旦附加日志 RPC 成功，那么跟隨者的日志就會和領(lǐng)導(dǎo)人保持一致肥缔，并且在接下來的任期里一直繼續(xù)保持。

如果需要的話汹来，算法可以通過減少被拒絕的附加日志 RPCs 的次數(shù)來優(yōu)化续膳。例如，當(dāng)附加日志 RPC 的請求被拒絕的時候收班，跟隨者可以包含沖突的條目的任期號和自己存儲的那個任期的最早的索引地址臼隔。借助這些信息滑废，領(lǐng)導(dǎo)人可以減小 nextIndex 越過所有那個任期沖突的所有日志條目；這樣就變成每個任期需要一次附加條目 RPC 而不是每個條目一次。在實踐中厚满，我們十分懷疑這種優(yōu)化是否是必要的，因為失敗是很少發(fā)生的并且也不大可能會有這么多不一致的日志戴甩。

通過這種機制舍败，領(lǐng)導(dǎo)人在獲得權(quán)力的時候就不需要任何特殊的操作來恢復(fù)一致性。他只需要進行正常的操作兄世，然后日志就能自動的在回復(fù)附加日志 RPC 的一致性檢查失敗的時候自動趨于一致啼辣。領(lǐng)導(dǎo)人從來不會覆蓋或者刪除自己的日志（圖 3 的領(lǐng)導(dǎo)人只附加特性）。

日志復(fù)制機制展示出了第 2 節(jié)中形容的一致性特性：Raft 能夠接受御滩，復(fù)制并應(yīng)用新的日志條目只要大部分的機器是工作的鸥拧；在通常的情況下，新的日志條目可以在一次 RPC 中被復(fù)制給集群中的大多數(shù)機器削解；并且單個的緩慢的跟隨者不會影響整體的性能富弦。

5.4 安全性

前面的章節(jié)里描述了 Raft 算法是如何選舉和復(fù)制日志的。然而氛驮，到目前為止描述的機制并不能充分的保證每一個狀態(tài)機會按照相同的順序執(zhí)行相同的指令腕柜。例如，一個跟隨者可能會進入不可用狀態(tài)同時領(lǐng)導(dǎo)人已經(jīng)提交了若干的日志條目，然后這個跟隨者可能會被選舉為領(lǐng)導(dǎo)人并且覆蓋這些日志條目媳握；因此碱屁，不同的狀態(tài)機可能會執(zhí)行不同的指令序列。

這一節(jié)通過在領(lǐng)導(dǎo)選舉的時候增加一些限制來完善了 Raft 算法蛾找。這一限制保證了任何的領(lǐng)導(dǎo)人對于給定的任期號娩脾，都擁有了之前任期的所有被提交的日志條目（圖 3 中的領(lǐng)導(dǎo)人完整特性）。增加這一選舉時的限制打毛，我們對于提交時的規(guī)則也更加清晰柿赊。最終，我們展示對于領(lǐng)導(dǎo)人完整特性的簡要證明并且說明領(lǐng)導(dǎo)人是如何領(lǐng)導(dǎo)復(fù)制狀態(tài)機的正確行為的幻枉。

5.4.1 選舉限制

在任何基于領(lǐng)導(dǎo)人的一致性算法中碰声，領(lǐng)導(dǎo)人都必須存儲所有已經(jīng)提交的日志條目。在某些一致性算法中熬甫，例如 Viewstamped Replication胰挑，一個人可以被選舉為領(lǐng)導(dǎo)人即使他一開始并沒有包含所有已經(jīng)提交的日志條目。這種算法包含一些額外的機制來識別丟失的日志條目并把他們傳送給新的領(lǐng)導(dǎo)人椿肩，要么是在選舉階段要么在之后很快進行瞻颂。不幸的是，這種方法會導(dǎo)致相當(dāng)大的額外的機制和復(fù)雜性郑象。Raft 使用了一種更加簡單的方法贡这，它可以保證所有之前的任期號中已經(jīng)提交的日志條目在選舉的時候都會出現(xiàn)在新的領(lǐng)導(dǎo)人中，不需要傳送這些日志條目給領(lǐng)導(dǎo)人厂榛。這意味著日志條目的傳送是單向的盖矫，只從領(lǐng)導(dǎo)人傳給跟隨者，并且領(lǐng)導(dǎo)人從不會覆蓋本地日志中已經(jīng)存在的條目击奶。

Raft 使用投票的方式來阻止候選人贏得選舉除非這個候選人包含了所有已經(jīng)提交的日志條目辈双。候選人為了贏得選舉必須聯(lián)系集群中的大部分節(jié)點，這意味著每一個已經(jīng)提交的日志條目肯定在這些服務(wù)器節(jié)點中至少存在一個上面正歼。如果候選人的日志至少和大多數(shù)的服務(wù)器節(jié)點一樣新（這個新的定義會在下面討論）辐马，那么他一定持有了所有已經(jīng)提交的日志條目。請求投票 RPC 實現(xiàn)了這樣的限制： RPC 中包含了候選人的日志信息局义，然后投票人會拒絕掉那些日志沒有自己新的投票請求喜爷。

Raft 通過比較兩份日志中最后一條日志條目的索引值和任期號定義誰的日志比較新。如果兩份日志最后的條目的任期號不同萄唇，那么任期號大的日志更加新檩帐。如果兩份日志最后的條目任期號相同，那么日志比較長的那個就更加新另萤。

5.4.2 提交之前任期內(nèi)的日志條目

如同 5.3 節(jié)介紹的那樣湃密，領(lǐng)導(dǎo)人知道一條當(dāng)前任期內(nèi)的日志記錄是可以被提交的诅挑，只要它被存儲到了大多數(shù)的服務(wù)器上。如果一個領(lǐng)導(dǎo)人在提交日志條目之前崩潰了泛源，未來后續(xù)的領(lǐng)導(dǎo)人會繼續(xù)嘗試復(fù)制這條日志記錄拔妥。然而，一個領(lǐng)導(dǎo)人不能斷定一個之前任期里的日志條目被保存到大多數(shù)服務(wù)器上的時候就一定已經(jīng)提交了达箍。圖 8 展示了一種情況没龙，一條已經(jīng)被存儲到大多數(shù)節(jié)點上的老日志條目，也依然有可能會被未來的領(lǐng)導(dǎo)人覆蓋掉缎玫。

圖 8

圖 8：如圖的時間序列展示了為什么領(lǐng)導(dǎo)人無法通過老的日志的任期號來判斷其提交狀態(tài)硬纤。在 (a) 中，S1 是領(lǐng)導(dǎo)者赃磨，部分的復(fù)制了索引位置 2 的日志條目筝家。在 (b) 中，S1 崩潰了邻辉，然后 S5 在任期 3 里通過 S3溪王、S4 和自己的選票贏得選舉，然后從客戶端接收了一條不一樣的日志條目放在了索引 2 處值骇。然后到 (c)在扰，S5 又崩潰了；S1 重新啟動雷客，選舉成功，開始復(fù)制日志桥狡。在這時搅裙，來自任期 2 的那條日志已經(jīng)被復(fù)制到了集群中的大多數(shù)機器上，但是還沒有被提交裹芝。如果 S1 在 (d) 中又崩潰了部逮，S5 可以重新被選舉成功（通過來自 S2，S3 和 S4 的選票）嫂易，然后覆蓋了他們在索引 2 處的日志兄朋。但是，在崩潰之前怜械，如果 S1 在自己的任期里復(fù)制了日志條目到大多數(shù)機器上颅和，如 (e) 中，然后這個條目就會被提交（S5 就不可能選舉成功）缕允。 在這個時候峡扩，之前的所有日志就會被正常提交處理。

為了消除圖 8 里描述的情況障本，Raft 永遠不會通過計算副本數(shù)目的方式提交一個之前任期內(nèi)的日志條目教届。只有領(lǐng)導(dǎo)人當(dāng)前任期里的日志條目通過計算副本數(shù)目可以被提交响鹃；一旦當(dāng)前任期的日志條目以這種方式被提交，那么由于日志匹配特性案训，之前的日志條目也都會被間接的提交买置。在某些情況下，領(lǐng)導(dǎo)人可以安全的知道一個老的日志條目是否已經(jīng)被提交（例如强霎，該條目是否存儲到所有服務(wù)器上）忿项，但是 Raft 為了簡化問題使用一種更加保守的方法。

當(dāng)領(lǐng)導(dǎo)人復(fù)制之前任期里的日志時脆栋，Raft 會在提交規(guī)則上產(chǎn)生額外的復(fù)雜性是因為所有的日志條目都保留原始的任期號倦卖。在其他的一致性算法中，如果一個新的領(lǐng)導(dǎo)人要重新復(fù)制之前的任期里的日志時椿争，它必須使用當(dāng)前新的任期號怕膛。Raft 使用的方法更加容易判斷出日志，因為他們?nèi)潭际褂猛粋€任期號秦踪。另外褐捻，和其他的算法相比，Raft 中的新領(lǐng)導(dǎo)人只需要發(fā)送更少日志條目（其他算法中必須在他們被提交之前發(fā)送更多的冗余日志條目來給他們重新編號）椅邓。

5.4.3 安全性論證

在給定了完整的 Raft 算法之后柠逞，我們現(xiàn)在可以更加精確的討論領(lǐng)導(dǎo)人完整性特性（這一討論基于 9.2 節(jié)的安全性證明）。我們假設(shè)領(lǐng)導(dǎo)人完全性特性是不存在的景馁，然后我們推出矛盾來板壮。假設(shè)任期 T 的領(lǐng)導(dǎo)人（領(lǐng)導(dǎo)人 T）在任期內(nèi)提交了一條日志條目，但是這條日志條目沒有被存儲到該領(lǐng)導(dǎo)人未來某個任期的日志中合住。設(shè)大于 T 的最小任期 U 的領(lǐng)導(dǎo)人 U 沒有這條日志條目绰精。

圖 9

圖 9：如果 S1 （任期 T 的領(lǐng)導(dǎo)者）提交了一條新的日志在它的任期里，然后 S5 在之后的任期 U 里被選舉為領(lǐng)導(dǎo)人透葛，然后至少會有一個機器笨使，如 S3，既擁有來自 S1 的日志僚害，也給 S5 投票了硫椰。

1. 在領(lǐng)導(dǎo)人 U 選舉的時候一定沒有那條被提交的日志條目（領(lǐng)導(dǎo)人從不會刪除或者覆蓋任何條目）。
2. 領(lǐng)導(dǎo)人 T 復(fù)制這條日志條目給集群中的大多數(shù)節(jié)點萨蚕，同時靶草，領(lǐng)導(dǎo)人U 從集群中的大多數(shù)節(jié)點贏得了選票。因此门岔，至少有一個節(jié)點（投票者爱致、選民）同時接受了來自領(lǐng)導(dǎo)人T 的日志條目，并且給領(lǐng)導(dǎo)人U 投票了寒随，如圖 9糠悯。這個投票者是產(chǎn)生這個矛盾的關(guān)鍵帮坚。
3. 這個投票者必須在給領(lǐng)導(dǎo)人 U 投票之前先接受了從領(lǐng)導(dǎo)人 T 發(fā)來的已經(jīng)被提交的日志條目；否則他就會拒絕來自領(lǐng)導(dǎo)人 T 的附加日志請求（因為此時他的任期號會比 T 大）互艾。
4. 投票者在給領(lǐng)導(dǎo)人 U 投票時依然保有這條日志條目试和，因為任何中間的領(lǐng)導(dǎo)人都包含該日志條目（根據(jù)上述的假設(shè)），領(lǐng)導(dǎo)人從不會刪除條目纫普，并且跟隨者只有和領(lǐng)導(dǎo)人沖突的時候才會刪除條目阅悍。
5. 投票者把自己選票投給領(lǐng)導(dǎo)人 U 時，領(lǐng)導(dǎo)人 U 的日志必須和投票者自己一樣新昨稼。這就導(dǎo)致了兩者矛盾之一节视。
6. 首先，如果投票者和領(lǐng)導(dǎo)人 U 的最后一條日志的任期號相同假栓，那么領(lǐng)導(dǎo)人 U 的日志至少和投票者一樣長寻行，所以領(lǐng)導(dǎo)人 U 的日志一定包含所有投票者的日志。這是另一處矛盾匾荆，因為投票者包含了那條已經(jīng)被提交的日志條目拌蜘，但是在上述的假設(shè)里，領(lǐng)導(dǎo)人 U 是不包含的牙丽。
7. 除此之外简卧，領(lǐng)導(dǎo)人 U 的最后一條日志的任期號就必須比投票人大了。此外烤芦，他也比 T 大举娩，因為投票人的最后一條日志的任期號至少和 T 一樣大（他包含了來自任期 T 的已提交的日志）。創(chuàng)建了領(lǐng)導(dǎo)人 U 最后一條日志的之前領(lǐng)導(dǎo)人一定已經(jīng)包含了那條被提交的日志（根據(jù)上述假設(shè)构罗，領(lǐng)導(dǎo)人 U 是第一個不包含該日志條目的領(lǐng)導(dǎo)人）晓铆。所以，根據(jù)日志匹配特性绰播，領(lǐng)導(dǎo)人 U 一定也包含那條被提交當(dāng)然日志，這里產(chǎn)生矛盾尚困。
8. 這里完成了矛盾蠢箩。因此，所有比 T 大的領(lǐng)導(dǎo)人一定包含了所有來自 T 的已經(jīng)被提交的日志事甜。
9. 日志匹配原則保證了未來的領(lǐng)導(dǎo)人也同時會包含被間接提交的條目谬泌，例如圖 8 (d) 中的索引 2。

通過領(lǐng)導(dǎo)人完全特性逻谦，我們就能證明圖 3 中的狀態(tài)機安全特性掌实，即如果已經(jīng)服務(wù)器已經(jīng)在某個給定的索引值應(yīng)用了日志條目到自己的狀態(tài)機里，那么其他的服務(wù)器不會應(yīng)用一個不一樣的日志到同一個索引值上邦马。在一個服務(wù)器應(yīng)用一條日志條目到他自己的狀態(tài)機中時贱鼻，他的日志必須和領(lǐng)導(dǎo)人的日志宴卖，在該條目和之前的條目上相同，并且已經(jīng)被提交×谛現(xiàn)在我們來考慮在任何一個服務(wù)器應(yīng)用一個指定索引位置的日志的最小任期症昏；日志完全特性保證擁有更高任期號的領(lǐng)導(dǎo)人會存儲相同的日志條目，所以之后的任期里應(yīng)用某個索引位置的日志條目也會是相同的值父丰。因此肝谭，狀態(tài)機安全特性是成立的。

最后蛾扇，Raft 要求服務(wù)器按照日志中索引位置順序應(yīng)用日志條目攘烛。和狀態(tài)機安全特性結(jié)合起來看，這就意味著所有的服務(wù)器會應(yīng)用相同的日志序列集到自己的狀態(tài)機中镀首，并且是按照相同的順序坟漱。

5.5 跟隨者和候選人崩潰

到目前為止，我們都只關(guān)注了領(lǐng)導(dǎo)人崩潰的情況蘑斧。跟隨者和候選人崩潰后的處理方式比領(lǐng)導(dǎo)人要簡單的多靖秩，并且他們的處理方式是相同的。如果跟隨者或者候選人崩潰了竖瘾，那么后續(xù)發(fā)送給他們的 RPCs 都會失敗沟突。Raft 中處理這種失敗就是簡單的通過無限的重試；如果崩潰的機器重啟了捕传，那么這些 RPC 就會完整的成功惠拭。如果一個服務(wù)器在完成了一個 RPC，但是還沒有響應(yīng)的時候崩潰了庸论，那么在他重新啟動之后就會再次收到同樣的請求职辅。Raft 的 RPCs 都是冪等的，所以這樣重試不會造成任何問題聂示。例如一個跟隨者如果收到附加日志請求但是他已經(jīng)包含了這一日志域携，那么他就會直接忽略這個新的請求。

5.6 時間和可用性

Raft 的要求之一就是安全性不能依賴時間：整個系統(tǒng)不能因為某些事件運行的比預(yù)期快一點或者慢一點就產(chǎn)生了錯誤的結(jié)果鱼喉。但是秀鞭，可用性（系統(tǒng)可以及時的響應(yīng)客戶端）不可避免的要依賴于時間。例如扛禽，如果消息交換在服務(wù)器崩潰時花費更多的時間锋边，候選人將不會等待太長的時間來贏得選舉；沒有一個穩(wěn)定的領(lǐng)導(dǎo)人编曼，Raft 將無法工作豆巨。

領(lǐng)導(dǎo)人選舉是 Raft 中對時間要求最為關(guān)鍵的方面。Raft 可以選舉出并維持一個穩(wěn)定的領(lǐng)導(dǎo)人除非整個系統(tǒng)滿足下面的時間要求：

廣播時間（broadcastTime） << 選舉超時時間（electionTimeout） << 平均故障間隔時間（MTBF）

在這個不等式中掐场，廣播時間指的是從一個服務(wù)器并行的發(fā)送 RPCs 給集群中的其他服務(wù)器并接收響應(yīng)的平均時間往扔；選舉超時時間就是在 5.2 節(jié)中介紹的選舉的超時時間限制贩猎；然后平均故障間隔時間就是對于一臺服務(wù)器而言，兩次故障之間的平均時間瓤球。廣播時間必須比選舉超時時間小一個量級融欧，這樣領(lǐng)導(dǎo)人才能夠發(fā)送穩(wěn)定的心跳消息來阻止跟隨者開始進入選舉狀態(tài)；通過隨機化選舉超時時間的方法卦羡，這個不等式也使得選票瓜分的情況變得不可能噪馏。選舉超時時間應(yīng)該要比平均故障間隔時間小上幾個數(shù)量級，這樣整個系統(tǒng)才能穩(wěn)定的運行绿饵。當(dāng)領(lǐng)導(dǎo)人崩潰后欠肾，整個系統(tǒng)會大約相當(dāng)于選舉超時的時間里不可用；我們希望這種情況在整個系統(tǒng)上是很小的情況拟赊。

廣播時間和平均故障間隔時間是由系統(tǒng)決定的刺桃，但是選舉超時時間是我們自己選擇的。Raft 的 RPCs 需要接收方將信息持久化的保存到穩(wěn)定存儲中去吸祟，所以廣播時間大約是 0.5 毫秒到 20 毫秒瑟慈，取決于存儲的技術(shù)。因此屋匕，選舉超時時間可能需要在 10 毫秒到 500 毫秒之間葛碧。大多數(shù)的服務(wù)器的平均故障間隔時間都在幾個月甚至更長，很容易滿足時間的需求过吻。

6 集群成員變化

到目前為止进泼，我們都假設(shè)集群的配置（加入到一致性算法的服務(wù)器集合）是固定不變的。但是在實踐中纤虽，偶爾是會改變集群的配置的乳绕，例如替換那些宕機的機器或者改變復(fù)制級別。盡管可以通過暫停整個集群逼纸，更新所有配置洋措，然后重啟整個集群的方式來實現(xiàn)习勤，但是在更改的時候集群會不可用塞弊。另外，如果存在手工操作步驟匣沼，那么就會有操作失誤的風(fēng)險专缠。為了避免這樣的問題，我們決定自動化配置改變并且將其納入到 Raft 一致性算法中來淑仆。

為了讓配置修改機制能夠安全涝婉，那么在轉(zhuǎn)換的過程中不能夠存在任何時間點使得兩個領(lǐng)導(dǎo)人同時被選舉成功在同一個任期里。不幸的是蔗怠，任何服務(wù)器直接從舊的配置直接轉(zhuǎn)換到新的配置的方案都是不安全的墩弯。一次性自動的轉(zhuǎn)換所有服務(wù)器是不可能的吩跋，所以在轉(zhuǎn)換期間整個集群存在劃分成兩個獨立的大多數(shù)群體的可能性（見圖 10）。

圖 10

圖 10：直接從一種配置轉(zhuǎn)到新的配置是十分不安全的渔工，因為各個機器可能在任何的時候進行轉(zhuǎn)換锌钮。在這個例子中，集群配額從 3 臺機器變成了 5 臺引矩。不幸的是梁丘，存在這樣的一個時間點，兩個不同的領(lǐng)導(dǎo)人在同一個任期里都可以被選舉成功旺韭。一個是通過舊的配置氛谜，一個通過新的配置。

為了保證安全性区端，配置更改必須使用兩階段方法值漫。目前有很多種兩階段的實現(xiàn)。例如织盼，有些系統(tǒng)在第一階段停掉舊的配置所以集群就不能處理客戶端請求杨何；然后在第二階段在啟用新的配置。在 Raft 中沥邻，集群先切換到一個過渡的配置危虱，我們稱之為共同一致；一旦共同一致已經(jīng)被提交了谋国，那么系統(tǒng)就切換到新的配置上槽地。共同一致是老配置和新配置的結(jié)合：

• 日志條目被復(fù)制給集群中新、老配置的所有服務(wù)器芦瘾。
• 新捌蚊、舊配置的服務(wù)器都可以成為領(lǐng)導(dǎo)人。
• 達成一致（針對選舉和提交）需要分別在兩種配置上獲得大多數(shù)的支持近弟。

共同一致允許獨立的服務(wù)器在不影響安全性的前提下缅糟，在不同的時間進行配置轉(zhuǎn)換過程。此外祷愉，共同一致可以讓集群在配置轉(zhuǎn)換的過程人依然響應(yīng)服務(wù)器請求窗宦。

集群配置在復(fù)制日志中以特殊的日志條目來存儲和通信；圖 11 展示了配置轉(zhuǎn)換的過程二鳄。當(dāng)一個領(lǐng)導(dǎo)人接收到一個改變配置從 C-old 到 C-new 的請求赴涵，他會為了共同一致存儲配置（圖中的 C-old,new），以前面描述的日志條目和副本的形式订讼。一旦一個服務(wù)器將新的配置日志條目增加到它的日志中髓窜，他就會用這個配置來做出未來所有的決定（服務(wù)器總是使用最新的配置，無論他是否已經(jīng)被提交）。這意味著領(lǐng)導(dǎo)人要使用 C-old,new 的規(guī)則來決定日志條目 C-old,new 什么時候需要被提交寄纵。如果領(lǐng)導(dǎo)人崩潰了鳖敷，被選出來的新領(lǐng)導(dǎo)人可能是使用 C-old 配置也可能是 C-old,new 配置，這取決于贏得選舉的候選人是否已經(jīng)接收到了 C-old,new 配置程拭。在任何情況下定踱， C-new 配置在這一時期都不會單方面的做出決定。

一旦 C-old,new 被提交恃鞋，那么無論是 C-old 還是 C-new崖媚，在沒有經(jīng)過他人批準(zhǔn)的情況下都不可能做出決定，并且領(lǐng)導(dǎo)人完全特性保證了只有擁有 C-old,new 日志條目的服務(wù)器才有可能被選舉為領(lǐng)導(dǎo)人山宾。這個時候至扰，領(lǐng)導(dǎo)人創(chuàng)建一條關(guān)于 C-new 配置的日志條目并復(fù)制給集群就是安全的了。再者资锰，每個服務(wù)器在見到新的配置的時候就會立即生效敢课。當(dāng)新的配置在 C-new 的規(guī)則下被提交，舊的配置就變得無關(guān)緊要绷杜，同時不使用新的配置的服務(wù)器就可以被關(guān)閉了直秆。如圖 11，C-old 和 C-new 沒有任何機會同時做出單方面的決定鞭盟；這保證了安全性圾结。

圖 11

圖 11：一個配置切換的時間線。虛線表示已經(jīng)被創(chuàng)建但是還沒有被提交的條目齿诉，實線表示最后被提交的日志條目筝野。領(lǐng)導(dǎo)人首先創(chuàng)建了 C-old,new 的配置條目在自己的日志中，并提交到 C-old,new 中（C-old,new 的大多數(shù)和 C-new 的大多數(shù)）粤剧。然后他創(chuàng)建 C-new 條目并提交到 C-new 中的大多數(shù)歇竟。這樣就不存在 C-new 和 C-old 可以同時做出決定的時間點。

在關(guān)于重新配置還有三個問題需要提出抵恋。第一個問題是焕议，新的服務(wù)器可能初始化沒有存儲任何的日志條目。當(dāng)這些服務(wù)器以這種狀態(tài)加入到集群中弧关，那么他們需要一段時間來更新追趕盅安，這時還不能提交新的日志條目。為了避免這種可用性的間隔時間世囊，Raft 在配置更新的時候使用了一種額外的階段别瞭，在這個階段，新的服務(wù)器以沒有投票權(quán)身份加入到集群中來（領(lǐng)導(dǎo)人復(fù)制日志給他們株憾，但是不考慮他們是大多數(shù)）蝙寨。一旦新的服務(wù)器追趕上了集群中的其他機器，重新配置可以像上面描述的一樣處理。

第二個問題是籽慢，集群的領(lǐng)導(dǎo)人可能不是新配置的一員。在這種情況下猫胁，領(lǐng)導(dǎo)人就會在提交了 C-new 日志之后退位（回到跟隨者狀態(tài)）箱亿。這意味著有這樣的一段時間，領(lǐng)導(dǎo)人管理著集群弃秆，但是不包括他自己届惋；他復(fù)制日志但是不把他自己算作是大多數(shù)之一。當(dāng) C-new 被提交時菠赚，會發(fā)生領(lǐng)導(dǎo)人過渡脑豹，因為這時是最早新的配置可以獨立工作的時間點（將總是能夠在 C-new 配置下選出新的領(lǐng)導(dǎo)人）。在此之前衡查，可能只能從 C-old 中選出領(lǐng)導(dǎo)人瘩欺。

第三個問題是，移除不在 C-new 中的服務(wù)器可能會擾亂集群拌牲。這些服務(wù)器將不會再接收到心跳俱饿，所以當(dāng)選舉超時，他們就會進行新的選舉過程塌忽。他們會發(fā)送擁有新的任期號的請求投票 RPCs拍埠，這樣會導(dǎo)致當(dāng)前的領(lǐng)導(dǎo)人回退成跟隨者狀態(tài)。新的領(lǐng)導(dǎo)人最終會被選出來土居，但是被移除的服務(wù)器將會再次超時枣购，然后這個過程會再次重復(fù)，導(dǎo)致整體可用性大幅降低擦耀。

為了避免這個問題棉圈，當(dāng)服務(wù)器確認(rèn)當(dāng)前領(lǐng)導(dǎo)人存在時，服務(wù)器會忽略請求投票 RPCs埂奈。特別的迄损，當(dāng)服務(wù)器在當(dāng)前最小選舉超時時間內(nèi)收到一個請求投票 RPC，他不會更新當(dāng)前的任期號或者投出選票账磺。這不會影響正常的選舉芹敌，每個服務(wù)器在開始一次選舉之前，至少等待一個最小選舉超時時間垮抗。然而氏捞，這有利于避免被移除的服務(wù)器擾亂：如果領(lǐng)導(dǎo)人能夠發(fā)送心跳給集群，那么他就不會被更大的任期號廢黜冒版。

7 日志壓縮

Raft 的日志在正常操作中不斷的增長液茎，但是在實際的系統(tǒng)中，日志不能無限制的增長。隨著日志不斷增長捆等，他會占用越來越多的空間滞造，花費越來越多的時間來重置。如果沒有一定的機制去清除日志里積累的陳舊的信息栋烤，那么會帶來可用性問題谒养。

快照是最簡單的壓縮方法。在快照系統(tǒng)中明郭，整個系統(tǒng)的狀態(tài)都以快照的形式寫入到穩(wěn)定的持久化存儲中买窟，然后到那個時間點之前的日志全部丟棄∈矶ǎ快照技術(shù)被使用在 Chubby 和 ZooKeeper 中始绍，接下來的章節(jié)會介紹 Raft 中的快照技術(shù)。

增量壓縮的方法话侄，例如日志清理或者日志結(jié)構(gòu)合并樹亏推，都是可行的。這些方法每次只對一小部分?jǐn)?shù)據(jù)進行操作满葛，這樣就分散了壓縮的負載壓力径簿。首先，他們先選擇一個已經(jīng)積累的大量已經(jīng)被刪除或者被覆蓋對象的區(qū)域嘀韧，然后重寫那個區(qū)域還活躍的對象篇亭，之后釋放那個區(qū)域。和簡單操作整個數(shù)據(jù)集合的快照相比锄贷，需要增加復(fù)雜的機制來實現(xiàn)译蒂。狀態(tài)機可以實現(xiàn) LSM tree 使用和快照相同的接口，但是日志清除方法就需要修改 Raft 了谊却。

圖 12

圖 12：一個服務(wù)器用新的快照替換了從 1 到 5 的條目柔昼，快照值存儲了當(dāng)前的狀態(tài)⊙妆妫快照中包含了最后的索引位置和任期號捕透。

圖 12 展示了 Raft 中快照的基礎(chǔ)思想。每個服務(wù)器獨立的創(chuàng)建快照碴萧，只包括已經(jīng)被提交的日志乙嘀。主要的工作包括將狀態(tài)機的狀態(tài)寫入到快照中。Raft 也包含一些少量的元數(shù)據(jù)到快照中：最后被包含索引指的是被快照取代的最后的條目在日志中的索引值（狀態(tài)機最后應(yīng)用的日志）破喻，最后被包含的任期指的是該條目的任期號虎谢。保留這些數(shù)據(jù)是為了支持快照前的第一個條目的附加日志請求時的一致性檢查，因為這個條目需要最后的索引值和任期號曹质。為了支持集群成員更新（第 6 節(jié)）婴噩，快照中也將最后的一次配置作為最后一個條目存下來擎场。一旦服務(wù)器完成一次快照，他就可以刪除最后索引位置之前的所有日志和快照了几莽。

盡管通常服務(wù)器都是獨立的創(chuàng)建快照迅办，但是領(lǐng)導(dǎo)人必須偶爾的發(fā)送快照給一些落后的跟隨者。這通常發(fā)生在當(dāng)領(lǐng)導(dǎo)人已經(jīng)丟棄了下一條需要發(fā)送給跟隨者的日志條目的時候章蚣。幸運的是這種情況不是常規(guī)操作：一個與領(lǐng)導(dǎo)人保持同步的跟隨者通常都會有這個條目礼饱。然而一個運行非常緩慢的跟隨者或者新加入集群的服務(wù)器（第 6 節(jié)）將不會有這個條目。這時讓這個跟隨者更新到最新的狀態(tài)的方式就是通過網(wǎng)絡(luò)把快照發(fā)送給他們究驴。

安裝快照 RPC：

在領(lǐng)導(dǎo)人發(fā)送快照給跟隨者時使用到。領(lǐng)導(dǎo)人總是按順序發(fā)送匀伏。

接收者實現(xiàn)：

1. 如果term < currentTerm就立即回復(fù)
2. 如果是第一個分塊（offset 為 0）就創(chuàng)建一個新的快照
3. 在指定偏移量寫入數(shù)據(jù)
4. 如果 done 是 false够颠，則繼續(xù)等待更多的數(shù)據(jù)
5. 保存快照文件熙侍，丟棄索引值小于快照的日志
6. 如果現(xiàn)存的日志擁有相同的最后任期號和索引值，則后面的數(shù)據(jù)繼續(xù)保持
7. 丟棄整個日志
8. 使用快照重置狀態(tài)機

圖 13：一個關(guān)于安裝快照的簡要概述履磨。為了便于傳輸蛉抓，快照都是被分成分塊的；每個分塊都給了跟隨者生命的跡象剃诅，所以跟隨者可以重置選舉超時計時器巷送。

在這種情況下領(lǐng)導(dǎo)人使用一種叫做安裝快照的新的 RPC 來發(fā)送快照給太落后的跟隨者；見圖 13矛辕。當(dāng)跟隨者通過這種 RPC 接收到快照時笑跛，他必須自己決定對于已經(jīng)存在的日志該如何處理。通沉钠罚快照會包含沒有在接收者日志中存在的信息飞蹂。在這種情況下，跟隨者直接丟棄他所有的日志翻屈；這些會被快照所取代陈哑，但是可能會和沒有提交的日志產(chǎn)生沖突。如果接收到的快照是自己日志的前面部分（由于網(wǎng)絡(luò)重傳或者錯誤）伸眶，那么被快照包含的條目將會被全部刪除惊窖，但是快照之后的條目必須正確和保留。

這種快照的方式背離了 Raft 的強領(lǐng)導(dǎo)人原則赚抡，因為跟隨者可以在不知道領(lǐng)導(dǎo)人情況下創(chuàng)建快照爬坑。但是我們認(rèn)為這種背離是值得的。領(lǐng)導(dǎo)人的存在涂臣，是為了解決在達成一致性的時候的沖突盾计，但是在創(chuàng)建快照的時候售担，一致性已經(jīng)達成，這時不存在沖突了署辉，所以沒有領(lǐng)導(dǎo)人也是可以的族铆。數(shù)據(jù)依然是從領(lǐng)導(dǎo)人傳給跟隨者，只是跟隨者可以重新組織他們的數(shù)據(jù)了哭尝。

我們考慮過一種替代的基于領(lǐng)導(dǎo)人的快照方案哥攘，即只有領(lǐng)導(dǎo)人創(chuàng)建快照，然后發(fā)送給所有的跟隨者材鹦。但是這樣做有兩個缺點逝淹。第一，發(fā)送快照會浪費網(wǎng)絡(luò)帶寬并且延緩了快照處理的時間桶唐。每個跟隨者都已經(jīng)擁有了所有產(chǎn)生快照需要的信息栅葡，而且很顯然尤泽，自己從本地的狀態(tài)中創(chuàng)建快照比通過網(wǎng)絡(luò)接收別人發(fā)來的要經(jīng)濟。第二熊咽，領(lǐng)導(dǎo)人的實現(xiàn)會更加復(fù)雜横殴。例如卿拴，領(lǐng)導(dǎo)人需要發(fā)送快照的同時并行的將新的日志條目發(fā)送給跟隨者，這樣才不會阻塞新的客戶端請求巍棱。

還有兩個問題影響了快照的性能惑畴。首先，服務(wù)器必須決定什么時候應(yīng)該創(chuàng)建快照航徙。如果快照創(chuàng)建的過于頻繁如贷，那么就會浪費大量的磁盤帶寬和其他資源；如果創(chuàng)建快照頻率太低到踏，他就要承受耗盡存儲容量的風(fēng)險杠袱，同時也增加了從日志重建的時間。一個簡單的策略就是當(dāng)日志大小達到一個固定大小的時候就創(chuàng)建一次快照窝稿。如果這個閾值設(shè)置的顯著大于期望的快照的大小楣富，那么快照對磁盤壓力的影響就會很小了。

第二個影響性能的問題就是寫入快照需要花費顯著的一段時間伴榔，并且我們還不希望影響到正常操作纹蝴。解決方案是通過寫時復(fù)制的技術(shù)庄萎，這樣新的更新就可以被接收而不影響到快照。例如塘安，具有函數(shù)式數(shù)據(jù)結(jié)構(gòu)的狀態(tài)機天然支持這樣的功能糠涛。另外，操作系統(tǒng)的寫時復(fù)制技術(shù)的支持（如 Linux 上的 fork）可以被用來創(chuàng)建完整的狀態(tài)機的內(nèi)存快照（我們的實現(xiàn)就是這樣的）兼犯。

8 客戶端交互

這一節(jié)將介紹客戶端是如何和 Raft 進行交互的切黔，包括客戶端如何發(fā)現(xiàn)領(lǐng)導(dǎo)人和 Raft 是如何支持線性化語義的脓规。這些問題對于所有基于一致性的系統(tǒng)都存在绢陌，并且 Raft 的解決方案和其他的也差不多。

Raft 中的客戶端發(fā)送所有請求給領(lǐng)導(dǎo)人秤掌。當(dāng)客戶端啟動的時候，他會隨機挑選一個服務(wù)器進行通信孟岛。如果客戶端第一次挑選的服務(wù)器不是領(lǐng)導(dǎo)人，那么那個服務(wù)器會拒絕客戶端的請求并且提供他最近接收到的領(lǐng)導(dǎo)人的信息（附加條目請求包含了領(lǐng)導(dǎo)人的網(wǎng)絡(luò)地址）次询。如果領(lǐng)導(dǎo)人已經(jīng)崩潰了送巡，那么客戶端的請求就會超時；客戶端之后會再次重試隨機挑選服務(wù)器的過程。

我們 Raft 的目標(biāo)是要實現(xiàn)線性化語義（每一次操作立即執(zhí)行谷朝，只執(zhí)行一次，在他調(diào)用和收到回復(fù)之間）专钉。但是，如上述菇民，Raft 是可以執(zhí)行同一條命令多次的：例如榜贴，如果領(lǐng)導(dǎo)人在提交了這條日志之后勋眯，但是在響應(yīng)客戶端之前崩潰了志秃，那么客戶端會和新的領(lǐng)導(dǎo)人重試這條指令，導(dǎo)致這條命令就被再次執(zhí)行了钧舌。解決方案就是客戶端對于每一條指令都賦予一個唯一的序列號崭歧。然后，狀態(tài)機跟蹤每條指令最新的序列號和相應(yīng)的響應(yīng)。如果接收到一條指令仔粥，它的序列號已經(jīng)被執(zhí)行了，那么就立即返回結(jié)果麦向，而不重新執(zhí)行指令十办。

只讀的操作可以直接處理而不需要記錄日志。但是件相，在不增加任何限制的情況下，這么做可能會冒著返回臟數(shù)據(jù)的風(fēng)險紊撕，因為領(lǐng)導(dǎo)人響應(yīng)客戶端請求時可能已經(jīng)被新的領(lǐng)導(dǎo)人作廢了对扶，但是他還不知道。線性化的讀操作必須不能返回臟數(shù)據(jù)骡送，Raft 需要使用兩個額外的措施在不使用日志的情況下保證這一點各谚。首先昌渤，領(lǐng)導(dǎo)人必須有關(guān)于被提交日志的最新信息。領(lǐng)導(dǎo)人完全特性保證了領(lǐng)導(dǎo)人一定擁有所有已經(jīng)被提交的日志條目，但是在他任期開始的時候柿汛，他可能不知道那些是已經(jīng)被提交的。為了知道這些信息弱判，他需要在他的任期里提交一條日志條目。Raft 中通過領(lǐng)導(dǎo)人在任期開始的時候提交一個空白的沒有任何操作的日志條目到日志中去來實現(xiàn)遭商。第二，領(lǐng)導(dǎo)人在處理只讀的請求之前必須檢查自己是否已經(jīng)被廢黜了（他自己的信息已經(jīng)變臟了如果一個更新的領(lǐng)導(dǎo)人被選舉出來）大审。Raft 中通過讓領(lǐng)導(dǎo)人在響應(yīng)只讀請求之前，先和集群中的大多數(shù)節(jié)點交換一次心跳信息來處理這個問題姜骡。可選的，領(lǐng)導(dǎo)人可以依賴心跳機制來實現(xiàn)一種租約的機制啥么，但是這種方法依賴時間來保證安全性（假設(shè)時間誤差是有界的）。

9 算法實現(xiàn)和評估

我們已經(jīng)為 RAMCloud 實現(xiàn)了 Raft 算法作為存儲配置信息的復(fù)制狀態(tài)機的一部分氯迂，并且?guī)椭?RAMCloud 協(xié)調(diào)故障轉(zhuǎn)移。這個 Raft 實現(xiàn)包含大約 2000 行 C++ 代碼驰坊，其中不包括測試察藐、注釋和空行悴务。這些代碼是開源的羡疗。同時也有大約 25 個其他獨立的第三方的基于這篇論文草稿的開源實現(xiàn)挖垛，針對不同的開發(fā)場景送矩。同時，很多公司已經(jīng)部署了基于 Raft 的系統(tǒng)。

這一節(jié)會從三個方面來評估 Raft 算法：可理解性、正確性和性能靠汁。

9.1 可理解性

為了和 Paxos 比較 Raft 算法的可理解能力，我們針對高層次的本科生和研究生踢星，在斯坦福大學(xué)的高級操作系統(tǒng)課程和加州大學(xué)伯克利分校的分布式計算課程上五督，進行了一次學(xué)習(xí)的實驗副签。我們分別拍了針對 Raft 和 Paxos 的視頻課程，并準(zhǔn)備了相應(yīng)的小測驗。Raft 的視頻講課覆蓋了這篇論文的所有內(nèi)容除了日志壓縮；Paxos 講課包含了足夠的資料來創(chuàng)建一個等價的復(fù)制狀態(tài)機督笆，包括單決策 Paxos，多決策 Paxos，重新配置和一些實際系統(tǒng)需要的性能優(yōu)化（例如領(lǐng)導(dǎo)人選舉）。小測驗測試一些對算法的基本理解和解釋一些邊角的示例拯钻。每個學(xué)生都是看完第一個視頻污桦，回答相應(yīng)的測試，再看第二個視頻致份，回答相應(yīng)的測試变抽。大約有一半的學(xué)生先進行 Paxos 部分，然后另一半先進行 Raft 部分，這是為了說明兩者獨立的區(qū)別從第一個算法處學(xué)來的經(jīng)驗绍载。我們計算參加人員的每一個小測驗的得分來看參與者是否在 Raft 算法上更加容易理解诡宗。

我們盡可能的使得 Paxos 和 Raft 的比較更加公平。這個實驗偏愛 Paxos 表現(xiàn)在兩個方面：43 個參加者中有 15 個人在之前有一些 Paxos 的經(jīng)驗击儡，并且 Paxos 的視頻要長 14%。如表格 1 總結(jié)的那樣递沪，我們采取了一些措施來減輕這種潛在的偏見圣猎。我們所有的材料都可供審查屋灌。

表 1：考慮到可能會存在的偏見，對于每種情況的解決方法朋譬，和相應(yīng)的材料。

參加者平均在 Raft 的測驗中比 Paxos 高 4.9 分（總分 60秸架，那么 Raft 的平均得分是 25.7喇伯，而 Paxos 是 20.8）事期；圖 14 展示了每個參與者的得分。一對 t -測試表明，擁有 95% 的可信度撩穿，真實的 Raft 分?jǐn)?shù)分布至少比 Paxos 高 2.5 分剑鞍。

圖 14

圖 14：一個散點圖表示了 43 個學(xué)生在 Paxos 和 Raft 的小測驗中的成績抑诸。在對角線之上的點表示在 Raft 獲得了更高分?jǐn)?shù)的學(xué)生。

我們也建立了一個線性回歸模型來預(yù)測一個新的學(xué)生的測驗成績憨降，基于以下三個因素：他們使用的是哪個小測驗，之前對 Paxos 的經(jīng)驗株扛，和學(xué)習(xí)算法的順序叔磷。模型顯示拢驾，對小測驗的選擇會產(chǎn)生 12.5 分的差別在對 Raft 的好感度上。這顯著的高于之前的 4.9 分改基，因為很多學(xué)生在之前都已經(jīng)有了對于 Paxos 的經(jīng)驗繁疤，這相當(dāng)明顯的幫助 Paxos，對 Raft 就沒什么太大影響了秕狰。但是奇怪的是稠腊，模型預(yù)測對于先進性 Paxos 小測驗的人而言，Raft 的小測驗得分會比 Paxos 低 6.3 分鸣哀；我們不知道為什么架忌，但這在統(tǒng)計學(xué)上是這樣的。

我們同時也在測驗之后調(diào)查了參與者我衬，他們認(rèn)為哪個算法更加容易實現(xiàn)和解釋叹放；這個的結(jié)果在圖 15 上。壓倒性的結(jié)果表明 Raft 算法更加容易實現(xiàn)和解釋（41 人中的 33個）挠羔。但是井仰，這種自己報告的結(jié)果不如參與者的成績更加可信，并且參與者可能因為我們的 Raft 更加易于理解的假說而產(chǎn)生偏見破加。

圖 15

圖 15：通過一個 5 分制的問題俱恶，參與者（左邊）被問哪個算法他們覺得在一個高效正確的系統(tǒng)里更容易實現(xiàn)，右邊被問哪個更容易向?qū)W生解釋。

關(guān)于 Raft 用戶學(xué)習(xí)有一個更加詳細的討論合是。

9.2 正確性

在第 5 節(jié)了罪，我們已經(jīng)進行了一個正式的說明，和對一致性機制的安全性證明聪全。這個正式說明讓圖 2 中的信息非常清晰通過 TLA+ 說明語言捶惜。大約 400 行說明充當(dāng)了證明的主題。同時對于任何想實現(xiàn)的人也是十分有用的荔烧。我們非常機械的證明了日志完全特性通過 TLA 證明系統(tǒng)吱七。然而，這個證明依賴的約束前提還沒有被機械證明（例如鹤竭，我們還沒有證明這個說明中的類型安全）踊餐。而且，我們已經(jīng)寫了一個非正式的證明關(guān)于狀態(tài)機安全性質(zhì)是完備的臀稚，并且是相當(dāng)清晰的（大約 3500 個詞）吝岭。

9.3 性能

Raft 和其他一致性算法例如 Paxos 有著差不多的性能。在性能方面吧寺，最重要的關(guān)注點是窜管，當(dāng)領(lǐng)導(dǎo)人被選舉成功時，什么時候復(fù)制新的日志條目稚机。Raft 通過很少數(shù)量的消息包（一輪從領(lǐng)導(dǎo)人到集群大多數(shù)機器的消息）就達成了這個目的幕帆。同時，進一步提升 Raft 的性能也是可行的赖条。例如失乾，很容易通過支持批量操作和管道操作來提高吞吐量和降低延遲。對于其他一致性算法已經(jīng)提出過很多性能優(yōu)化方案纬乍；其中有很多也可以應(yīng)用到 Raft 中來碱茁，但是我們暫時把這個問題放到未來的工作中去。

我們使用我們自己的 Raft 實現(xiàn)來衡量 Raft 領(lǐng)導(dǎo)人選舉的性能并且回答兩個問題仿贬。首先纽竣，領(lǐng)導(dǎo)人選舉的過程收斂是否快速？第二茧泪，在領(lǐng)導(dǎo)人宕機之后蜓氨，最小的系統(tǒng)宕機時間是多久？

圖 16

圖 16：發(fā)現(xiàn)并替換一個已經(jīng)崩潰的領(lǐng)導(dǎo)人的時間调炬。上面的圖考察了在選舉超時時間上的隨機化程度语盈，下面的圖考察了最小超時時間。每條線代表了 1000 次實驗（除了 150-150 毫秒只試了 100 次）缰泡，和相應(yīng)的確定的選舉超時時間刀荒。例如代嗤，150-155 毫秒意思是，選舉超時時間從這個區(qū)間范圍內(nèi)隨機選擇并確定下來缠借。這個實驗在一個擁有 5 個節(jié)點的集群上進行干毅，其廣播時延大約是 15 毫秒。對于 9 個節(jié)點的集群泼返，結(jié)果也差不多硝逢。

為了衡量領(lǐng)導(dǎo)人選舉，我們反復(fù)的使一個擁有五個節(jié)點的服務(wù)器集群的領(lǐng)導(dǎo)人宕機绅喉，并計算需要多久才能發(fā)現(xiàn)領(lǐng)導(dǎo)人已經(jīng)宕機并選出一個新的領(lǐng)導(dǎo)人（見圖 16）渠鸽。為了構(gòu)建一個最壞的場景，在每一的嘗試?yán)锊窆蓿?wù)器都有不同長度的日志徽缚，意味著有些候選人是沒有成為領(lǐng)導(dǎo)人的資格的。另外革屠，為了促成選票瓜分的情況凿试，我們的測試腳本在終止領(lǐng)導(dǎo)人之前同步的發(fā)送了一次心跳廣播（這大約和領(lǐng)導(dǎo)人在崩潰前復(fù)制一個新的日志給其他機器很像）。領(lǐng)導(dǎo)人均勻的隨機的在心跳間隔里宕機似芝，也就是最小選舉超時時間的一半那婉。因此，最小宕機時間大約就是最小選舉超時時間的一半党瓮。

圖 16 上面的圖表表明详炬，只需要在選舉超時時間上使用很少的隨機化就可以大大避免選票被瓜分的情況。在沒有隨機化的情況下麻诀，在我們的測試?yán)锖墼ⅲx舉過程往往都需要花費超過 10 秒鐘由于太多的選票瓜分的情況傲醉。僅僅增加 5 毫秒的隨機化時間蝇闭，就大大的改善了選舉過程，現(xiàn)在平均的宕機時間只有 287 毫秒硬毕。增加更多的隨機化時間可以大大改善最壞情況：通過增加 50 毫秒的隨機化時間呻引，最壞的完成情況（1000 次嘗試）只要 513 毫秒。

圖 16 中下面的圖顯示吐咳，通過減少選舉超時時間可以減少系統(tǒng)的宕機時間逻悠。在選舉超時時間為 12-24 毫秒的情況下，只需要平均 35 毫秒就可以選舉出新的領(lǐng)導(dǎo)人（最長的一次花費了 152 毫秒）韭脊。然而童谒，進一步降低選舉超時時間的話就會違反 Raft 的時間不等式需求：在選舉新領(lǐng)導(dǎo)人之前，領(lǐng)導(dǎo)人就很難發(fā)送完心跳包沪羔。這會導(dǎo)致沒有意義的領(lǐng)導(dǎo)人改變并降低了系統(tǒng)整體的可用性饥伊。我們建議使用更為保守的選舉超時時間，比如 150-300 毫秒；這樣的時間不大可能導(dǎo)致沒有意義的領(lǐng)導(dǎo)人改變琅豆，而且依然提供不錯的可用性愉豺。

10 相關(guān)工作

已經(jīng)有很多關(guān)于一致性算法的工作被發(fā)表出來，其中很多都可以歸到下面的類別中：

• Lamport 關(guān)于 Paxos 的原始描述茫因，和嘗試描述的更清晰蚪拦。
• 關(guān)于 Paxos 的更詳盡的描述，補充遺漏的細節(jié)并修改算法冻押，使得可以提供更加容易的實現(xiàn)基礎(chǔ)驰贷。
• 實現(xiàn)一致性算法的系統(tǒng)，例如 Chubby洛巢，ZooKeeper 和 Spanner饱苟。對于 Chubby 和 Spanner 的算法并沒有公開發(fā)表其技術(shù)細節(jié)，盡管他們都聲稱是基于 Paxos 的狼渊。ZooKeeper 的算法細節(jié)已經(jīng)發(fā)表箱熬，但是和 Paxos 著實有著很大的差別。
• Paxos 可以應(yīng)用的性能優(yōu)化狈邑。
• Oki 和 Liskov 的 Viewstamped Replication（VR）城须，一種和 Paxos 差不多的替代算法。原始的算法描述和分布式傳輸協(xié)議耦合在了一起米苹，但是核心的一致性算法在最近的更新里被分離了出來糕伐。VR 使用了一種基于領(lǐng)導(dǎo)人的方法，和 Raft 有很多相似之處蘸嘶。

Raft 和 Paxos 最大的不同之處就在于 Raft 的強領(lǐng)導(dǎo)特性：Raft 使用領(lǐng)導(dǎo)人選舉作為一致性協(xié)議里必不可少的部分良瞧，并且將盡可能多的功能集中到了領(lǐng)導(dǎo)人身上。這樣就可以使得算法更加容易理解训唱。例如褥蚯，在 Paxos 中，領(lǐng)導(dǎo)人選舉和基本的一致性協(xié)議是正交的：領(lǐng)導(dǎo)人選舉僅僅是性能優(yōu)化的手段况增，而且不是一致性所必須要求的赞庶。但是，這樣就增加了多余的機制：Paxos 同時包含了針對基本一致性要求的兩階段提交協(xié)議和針對領(lǐng)導(dǎo)人選舉的獨立的機制澳骤。相比較而言歧强，Raft 就直接將領(lǐng)導(dǎo)人選舉納入到一致性算法中，并作為兩階段一致性的第一步为肮。這樣就減少了很多機制摊册。

像 Raft 一樣，VR 和 ZooKeeper 也是基于領(lǐng)導(dǎo)人的颊艳，因此他們也擁有一些 Raft 的優(yōu)點茅特。但是蟆沫，Raft 比 VR 和 ZooKeeper 擁有更少的機制因為 Raft 盡可能的減少了非領(lǐng)導(dǎo)人的功能。例如温治，Raft 中日志條目都遵循著從領(lǐng)導(dǎo)人發(fā)送給其他人這一個方向：附加條目 RPC 是向外發(fā)送的饭庞。在 VR 中，日志條目的流動是雙向的（領(lǐng)導(dǎo)人可以在選舉過程中接收日志）熬荆；這就導(dǎo)致了額外的機制和復(fù)雜性舟山。根據(jù) ZooKeeper 公開的資料看，它的日志條目也是雙向傳輸?shù)穆笨遥撬膶崿F(xiàn)更像 Raft累盗。

和上述我們提及的其他基于一致性的日志復(fù)制算法中，Raft 的消息類型更少突琳。例如若债，我們數(shù)了一下 VR 和 ZooKeeper 使用的用來基本一致性需要和成員改變的消息數(shù)（排除了日志壓縮和客戶端交互，因為這些都比較獨立且和算法關(guān)系不大）拆融。VR 和 ZooKeeper 都分別定義了 10 中不同的消息類型蠢琳，相對的，Raft 只有 4 中消息類型（兩種 RPC 請求和對應(yīng)的響應(yīng)）镜豹。Raft 的消息都稍微比其他算法的要信息量大傲须，但是都很簡單。另外趟脂，VR 和 ZooKeeper 都在領(lǐng)導(dǎo)人改變時傳輸了整個日志泰讽；所以為了能夠?qū)嵺`中使用，額外的消息類型就很必要了昔期。

Raft 的強領(lǐng)導(dǎo)人模型簡化了整個算法已卸，但是同時也排斥了一些性能優(yōu)化的方法。例如硼一，平等主義 Paxos （EPaxos）在某些沒有領(lǐng)導(dǎo)人的情況下可以達到很高的性能累澡。平等主義 Paxos 充分發(fā)揮了在狀態(tài)機指令中的交換性。任何服務(wù)器都可以在一輪通信下就提交指令欠动，除非其他指令同時被提出了永乌。然而，如果指令都是并發(fā)的被提出具伍，并且互相之間不通信溝通，那么 EPaxos 就需要額外的一輪通信圈驼。因為任何服務(wù)器都可以提交指令人芽，所以 EPaxos 在服務(wù)器之間的負載均衡做的很好，并且很容易在 WAN 網(wǎng)絡(luò)環(huán)境下獲得很低的延遲绩脆。但是萤厅，他在 Paxos 上增加了非常明顯的復(fù)雜性橄抹。

一些集群成員變換的方法已經(jīng)被提出或者在其他的工作中被實現(xiàn)，包括 Lamport 的原始的討論惕味，VR 和 SMART楼誓。我們選擇使用共同一致的方法因為他對一致性協(xié)議的其他部分影響很小，這樣我們只需要很少的一些機制就可以實現(xiàn)成員變換名挥。Lamport 的基于 α 的方法之所以沒有被 Raft 選擇是因為它假設(shè)在沒有領(lǐng)導(dǎo)人的情況下也可以達到一致性疟羹。和 VR 和 SMART 相比較，Raft 的重新配置算法可以在不限制正常請求處理的情況下進行禀倔；相比較的榄融，VR 需要停止所有的處理過程，SMART 引入了一個和 α 類似的方法救湖，限制了請求處理的數(shù)量愧杯。Raft 的方法同時也需要更少的額外機制來實現(xiàn)，和 VR鞋既、SMART 比較而言力九。

11 結(jié)論

算法的設(shè)計通常會把正確性腹纳，效率或者簡潔作為主要的目標(biāo)啃勉。盡管這些都是很有意義的目標(biāo)夹供，但是我們相信践宴，可理解性也是一樣的重要暂殖。在開發(fā)者把算法應(yīng)用到實際的系統(tǒng)中之前薪捍，這些目標(biāo)沒有一個會被實現(xiàn)藐鹤，這些都會必然的偏離發(fā)表時的形式鳍置。除非開發(fā)人員對這個算法有著很深的理解并且有著直觀的感覺蹭沛，否則將會對他們而言很難在實現(xiàn)的時候保持原有期望的特性臂寝。

在這篇論文中，我們嘗試解決分布式一致性問題摊灭，但是一個廣為接受但是十分令人費解的算法 Paxos 已經(jīng)困擾了無數(shù)學(xué)生和開發(fā)者很多年了咆贬。我們創(chuàng)造了一種新的算法 Raft，顯而易見的比 Paxos 要容易理解帚呼。我們同時也相信掏缎，Raft 也可以為實際的實現(xiàn)提供堅實的基礎(chǔ)。把可理解性作為設(shè)計的目標(biāo)改變了我們設(shè)計 Raft 的方式煤杀；這個過程是我們發(fā)現(xiàn)我們最終很少有技術(shù)上的重復(fù)眷蜈，例如問題分解和簡化狀態(tài)空間。這些技術(shù)不僅提升了 Raft 的可理解性沈自，同時也使我們堅信其正確性酌儒。

12 感謝

這項研究必須感謝以下人員的支持：Ali Ghodsi，David Mazie`res枯途，和伯克利 CS 294-91 課程忌怎、斯坦福 CS 240 課程的學(xué)生籍滴。Scott Klemmer 幫我們設(shè)計了用戶調(diào)查，Nelson Ray 建議我們進行統(tǒng)計學(xué)的分析榴啸。在用戶調(diào)查時使用的關(guān)于 Paxos 的幻燈片很大一部分是從 Lorenzo Alvisi 的幻燈片上借鑒過來的孽惰。特別的，非常感謝 DavidMazieres 和 Ezra Hoch鸥印，他們找到了 Raft 中一些難以發(fā)現(xiàn)的漏洞勋功。許多人提供了關(guān)于這篇論文十分有用的反饋和用戶調(diào)查材料，包括 Ed Bugnion辅甥，Michael Chan酝润，Hugues Evrard，Daniel Giffin璃弄，Arjun Gopalan要销，Jon Howell，Vimalkumar Jeyakumar夏块，Ankita Kejriwal疏咐，Aleksandar Kracun，Amit Levy脐供，Joel Martin浑塞，Satoshi Matsushita，Oleg Pesok政己，David Ramos酌壕，Robbert van Renesse，Mendel Rosenblum歇由，Nicolas Schiper卵牍，Deian Stefan，Andrew Stone沦泌，Ryan Stutsman糊昙，David Terei，Stephen Yang谢谦，Matei Zaharia 以及 24 位匿名的會議審查人員（可能有重復(fù)）释牺，并且特別感謝我們的領(lǐng)導(dǎo)人 Eddie Kohler。Werner Vogels 發(fā)了一條早期草稿鏈接的推特回挽，給 Raft 帶來了極大的關(guān)注没咙。我們的工作由 Gigascale 系統(tǒng)研究中心和 Multiscale 系統(tǒng)研究中心給予支持，這兩個研究中心由關(guān)注中心研究程序資金支持厅各，一個是半導(dǎo)體研究公司的程序镜撩，由 STARnet 支持，一個半導(dǎo)體研究公司的程序由 MARCO 和 DARPA 支持队塘，在國家科學(xué)基金會的 0963859 號批準(zhǔn)袁梗，并且獲得了來自 Facebook，Google憔古，Mellanox遮怜，NEC，NetApp鸿市，SAP 和 Samsung 的支持锯梁。Diego Ongaro 由 Junglee 公司，斯坦福的畢業(yè)團體支持焰情。

參考

略