本文為RAFT一致性算法論文的譯文症昏，原文是《In search of an Understandable Consensus Algorithm (Extended Version)》踊赠，作者為 Diego Ongaro 和 John Ousterhout 。
摘要
Raft 是一種用于管理日志復(fù)制的一致性算法替蔬，它與 Paxos 算法在效果和性能上相近。但得益于其獨(dú)特的結(jié)構(gòu)，Raft 比 Paxos 更易于理解，且更易于在實(shí)際項(xiàng)目中落地哑蔫。為了便于理解，Raft 將一致性算法的關(guān)鍵部分分為：leader 選取弧呐，日志復(fù)制闸迷，安全性。并且俘枫，Raft 通過(guò)使用更強(qiáng)的一致性以減少必須考慮的狀態(tài)腥沽。因此，對(duì)于學(xué)生群體鸠蚪，Raft 比 Paxos 更易于學(xué)習(xí)今阳，這在一項(xiàng)用戶調(diào)查研究中得到了印證师溅。此外，Raft 引入了新的機(jī)制——重疊多數(shù)（overlapping majorities）原則來(lái)保證安全地動(dòng)態(tài)調(diào)整集群成員盾舌。
1 引言
一致性算法保證一組機(jī)器像一個(gè)整體一樣工作墓臭，即使其中一些機(jī)器出現(xiàn)故障。因此妖谴，一致性算法是建立可靠的大規(guī)模軟件系統(tǒng)的關(guān)鍵窿锉。在過(guò)去的十年中 Paxos 一直主導(dǎo)著有關(guān)一致性算法的討論：大多數(shù)一致性算法的實(shí)現(xiàn)都基于它或者受它影響，并且 Paxos 也成為了教學(xué)中關(guān)于一致性知識(shí)的主要工具膝舅。
然而嗡载，盡管研究人員在降低它的復(fù)雜性方面做了許多努力，Paxos 依舊很難理解仍稀。并且洼滚，Paxos 需要經(jīng)過(guò)復(fù)雜的修改才能應(yīng)用于實(shí)際系統(tǒng)中。這些導(dǎo)致了系統(tǒng)構(gòu)建者和學(xué)生都對(duì) Paxos 十分頭疼技潘。
在被 Paxos 折磨之后遥巴，我們開(kāi)始尋找一種新的在系統(tǒng)構(gòu)建和教學(xué)上更好的一致性算法。與常規(guī)方法不同享幽，我們的首要目標(biāo)是讓一致性算法易于理解：我們能不能定義一種面向?qū)嶋H系統(tǒng)的挪哄、比 Paxos 更容易學(xué)習(xí)的一致性算法呢？此外琉闪，我們希望這種算法直觀易懂迹炼，這對(duì)一個(gè)系統(tǒng)構(gòu)建者來(lái)說(shuō)是十分必要的。對(duì)于一個(gè)算法颠毙，不僅要能夠?qū)崿F(xiàn)并且正常工作斯入，還要清楚地明白其中的原理。
這項(xiàng)工作的結(jié)果是一種新的一致性算法蛀蜜，叫做 Raft刻两。在設(shè)計(jì) Raft 的過(guò)程中我們應(yīng)用了許多專門(mén)的技巧來(lái)便于理解，包括算法分解（分為領(lǐng)導(dǎo)選取滴某，日志復(fù)制和安全性）和約簡(jiǎn)狀態(tài)空間（state space reduction磅摹，相對(duì)于 Paxos，Raft 減少了非確定性的程度和導(dǎo)致服務(wù)器之間不一致的可能）霎奢。在針對(duì)兩所大學(xué)43名學(xué)生的用戶調(diào)查中發(fā)現(xiàn)户誓，Raft 比 Paxos 更易于理解：在學(xué)習(xí)了兩種算法之后，回答問(wèn)題時(shí)幕侠，其中的33個(gè)學(xué)生對(duì) Raft 的問(wèn)題回答的更好帝美。
Raft 算法與現(xiàn)在一些已有的算法在某些地方很相似（主要是 Oki 和 Liskov 的 Viewstamped Replication），但是 Raft 有如下新特性：
- 強(qiáng)領(lǐng)導(dǎo)者（Strong Leader）：Raft 使用一種比其他算法更強(qiáng)的領(lǐng)導(dǎo)形式晤硕。例如悼潭，日志只從 leader 發(fā)送給其他服務(wù)器庇忌。這簡(jiǎn)化了對(duì)日志復(fù)制的管理，使得 Raft 更易于理解舰褪。
- 領(lǐng)導(dǎo)選冉哉睢（Leader Selection）：Raft 使用隨機(jī)定時(shí)器來(lái)選取 leader 。這種方式僅僅是在所有一致性算法都需要的心跳機(jī)制上進(jìn)行些許改進(jìn)占拍，然而這使得 Raft 在解決沖突時(shí)更簡(jiǎn)單和快速略就。
- 成員調(diào)整（Membership Change）：在實(shí)現(xiàn)調(diào)整集群中成員的機(jī)制時(shí)，Raft 使用了新的聯(lián)合一致性（joint consensus）的方法刷喜，這種方法中大多數(shù)不同配置的機(jī)器在轉(zhuǎn)換關(guān)系的時(shí)候會(huì)交疊（overlap）残制。這使得在配置發(fā)生改變的時(shí)候立砸，集群能夠繼續(xù)正常工作掖疮。
我們認(rèn)為，在教學(xué)和實(shí)際實(shí)現(xiàn)方面颗祝，Raft 比 Paxos 和其他算法更優(yōu)秀浊闪。Raft 比其他算法更簡(jiǎn)單，更易于理解螺戳；它能滿足一個(gè)實(shí)際系統(tǒng)的需求搁宾；它擁有許多開(kāi)源的實(shí)現(xiàn)并且被許多公司使用；它的安全特性已經(jīng)被證明倔幼；并且它的效率和其他算法相比也具有競(jìng)爭(zhēng)力盖腿。
這篇論文剩下的部分會(huì)講如下內(nèi)容：復(fù)制狀態(tài)機(jī)（replicated state machine）問(wèn)題（第2節(jié)），討論 Paxos 的優(yōu)缺點(diǎn)（第3節(jié)）损同，討論為了使算法更便于理解所用的方法（第4節(jié)）翩腐，陳述 Raft 一致性算法（第5~8節(jié)），評(píng)價(jià) Raft 算法（第9節(jié)）膏燃，對(duì)相關(guān)工作的討論（第10節(jié)）茂卦。
2 復(fù)制狀態(tài)機(jī)（Replicated State Machine）
一致性算法是在復(fù)制狀態(tài)機(jī)的背景下提出來(lái)的。在這個(gè)方法中组哩，一組服務(wù)器的狀態(tài)機(jī)計(jì)算產(chǎn)生相同狀態(tài)的副本等龙，即使其中一些服務(wù)器崩潰，這組服務(wù)器也還能繼續(xù)運(yùn)行伶贰。復(fù)制狀態(tài)機(jī)用于解決分布式系統(tǒng)中多種容錯(cuò)相關(guān)的問(wèn)題蛛砰。例如，GFS黍衙，HDFS和 RAMCloud 之類(lèi)大規(guī)模系統(tǒng)都是用獨(dú)立的復(fù)制狀態(tài)機(jī)來(lái)管理 leader 選取暴备，以及存儲(chǔ)配置信息來(lái)應(yīng)對(duì) leader 崩潰的情況。 Chubby 和 ZooKeeper 就是使用復(fù)制狀態(tài)機(jī)的例子们豌。
如圖1所示，復(fù)制狀態(tài)機(jī)是通過(guò)復(fù)制日志來(lái)實(shí)現(xiàn)的涛浙。每一臺(tái)服務(wù)器保存著一份日志康辑，日志中包含一系列的命令，狀態(tài)機(jī)會(huì)按順序執(zhí)行這些命令轿亮。因?yàn)槊恳慌_(tái)計(jì)算機(jī)的狀態(tài)機(jī)都是確定的疮薇，所以每個(gè)狀態(tài)機(jī)通過(guò)計(jì)算得到相同的狀態(tài)，最后的輸出結(jié)果也就一致了我注。
一致性算法的工作就是保證復(fù)制的日志一致按咒。在一臺(tái)服務(wù)器上，一致性模塊接收到客戶端的指令后把指令寫(xiě)入到日志中但骨，并與其他服務(wù)器上的一致性模塊通信励七，以確保每一個(gè)日志最終包含一致的請(qǐng)求序列，即使有某些服務(wù)器宕機(jī)奔缠。一旦這些指令被正確的復(fù)制了掠抬，每一個(gè)服務(wù)器的狀態(tài)機(jī)都會(huì)按同樣的順序去執(zhí)行它們，然后將結(jié)果返回給客戶端校哎。最終两波，這些服務(wù)器看起來(lái)就像一臺(tái)可靠的狀態(tài)機(jī)。在實(shí)際系統(tǒng)中應(yīng)用的一致性算法一般有以下特性：
- 確保安全性（從來(lái)不會(huì)返回一個(gè)錯(cuò)誤的結(jié)果）闷哆，即使在所有的非拜占庭（Non-Byzantine）情況下腰奋，包括網(wǎng)絡(luò)延遲、分區(qū)阳准、丟包氛堕、冗余和亂序。
- 高可用性野蝇，只要集群中的大部分機(jī)器都能運(yùn)行讼稚，可以互相通信并且可以和客戶端通信，這個(gè)集群就可用绕沈。因此锐想，一般來(lái)說(shuō)，一個(gè)擁有 5 臺(tái)機(jī)器的集群可以容忍至多兩臺(tái)機(jī)器宕機(jī)乍狐。服務(wù)器可以通過(guò)備份還原并在此加入到集群中赠摇。
- 保證一致性且不依賴時(shí)序，在最壞的情況下，時(shí)鐘錯(cuò)誤和極端的消息延遲才會(huì)引起可用性問(wèn)題藕帜。
- 通常情況下烫罩，在單輪 RPC 中，只要集群中大多數(shù)節(jié)點(diǎn)對(duì) RPC 做出響應(yīng)洽故，那么這條指令就算完成了贝攒，一小部分慢的服務(wù)器不會(huì)影響系統(tǒng)的整體性能。
