Raft
In Search of an Understandable Consensus Algorithm (Extended Version)
1. Introduction
一致性算法。一個機(jī)器集合如何對外提供一致性，并具有容錯性(容忍某些節(jié)點失效).
Raft把一致性分為三個關(guān)鍵元素：leader election, log replication, safety
Raft 關(guān)鍵的特性：
- Strong leader
- Leader election
- Membership changes
2. Replicated state machines
在 replicated state machines 的場景下討論一致性算法售淡。在server集合上的狀態(tài)機(jī)扔仓，在一樣的狀態(tài)上進(jìn)行相同的計算 踏志，并且在少數(shù)server掛掉后，仍能對外提供服務(wù)。用于在分布式系統(tǒng)中提供容錯性。
replicated state machines 一般使用 replicated log來實現(xiàn)庶灿。每個server存儲狀態(tài)機(jī)按照順序執(zhí)行的一系列命令的日志。每個日志都按照相同的順序存儲命令吃衅。一致性算法的職責(zé)就是保持 replicated log 的一致性往踢。
典型的一致性算法具有以下屬性
- 在所有非拜占庭(non-Byzantine)條件下都是保證安全的，包括：網(wǎng)絡(luò)延遲徘层，分區(qū)峻呕，丟包，重復(fù)趣效，亂序
- 在大多數(shù)server在運作瘦癌，并可以相互通訊，與客戶端通訊的情況下跷敬，能夠?qū)ν馓峁┓?wù)讯私。
- 不依賴于時間來保證logs的一致性：因為不一致的時鐘，計算情況下的網(wǎng)絡(luò)延遲會導(dǎo)致
- 一般情況下西傀，一條命了在集群中大多數(shù)響應(yīng)后即完成斤寇。即少數(shù)慢的服務(wù)器不會影響整體系統(tǒng)性能。
3. What's wrong with Paxos?
- Paxos 難以理解
- 沒有為實現(xiàn)提供好的基礎(chǔ)
4. Designing for understandability
5. The Raft consensus algorithm
一致性算法的關(guān)鍵屬性(Figure 3)：
- Election safety：(5.2節(jié))在一個term期間最多只會選出一個leader
- Leader Append-Only：(5.3節(jié))leader只會新增(append)entries拥褂，而永遠(yuǎn)不會覆蓋或刪除entries娘锁。
- Log Matching：(5.3節(jié))如果兩個logs包含一個具有相同index及term的entry，那么這兩者肿仑，在該index項及之前的所有entries都是一致的
- Leader Completeness：(5.4節(jié))if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-number terms致盟？
- State Machine Safety：(5.4.3節(jié))如果一個server 在某一index上對狀態(tài)機(jī)applied 了 log entry碎税，不會有其它server 用同樣的index尤慰，apply一個不一致的log entry
Raft的做法是首先選出leader，全權(quán)負(fù)責(zé)管理replicated log雷蹂。包括接收客戶端的log entries伟端，復(fù)制log entries至其他server，告知他們何時可以 apply log entries to their state machines. 在 leader 掛掉或者與其他server失去鏈接的情況下匪煌，選舉出新的leader责蝠。
Raft把一致性問題拆分為三個子問題：
- Leader election：在當(dāng)前 leader 掛掉后選出一個新的 leader
- Log replication：leader 從客戶端接收 log entries 并在集群內(nèi)進(jìn)行復(fù)制，讓其他 logs 與leader的log保持一致
- Safety：關(guān)鍵需要保證 Figure 3 中的 State Machine Safety. 5.4節(jié)描述 Raft 如何保證這一點萎庭。為了保證這一點霜医，在 5.2 節(jié)選舉的方式中也會額外添加了一些限制。
5.1 Raft basics
server 有三個狀態(tài)：leader驳规，follower肴敛，candidate。一般情況下有且僅有一個leader，其它server都是follower医男。
Leader 負(fù)責(zé)處理對外所有客戶端的請求(如果client向follwer發(fā)起請求砸狞，follower把client重定向給leader)。
Follower被動地接收leader及candidates的請求镀梭。
Candidate用于選舉出新的leader
Raft把時間劃分為任意長度的term刀森。每個term以選舉開始，如果有candidate贏得選舉报账，其在term內(nèi)當(dāng)選leader研底；在某些情況下發(fā)生了split vote，該term以沒有l(wèi)eader結(jié)束笙什，并在較短時間內(nèi)發(fā)起新的選舉飘哨。term在Raft中扮演著邏輯始終的角色(logical clock)。
基本的一致性算法琐凭，Raft server 之間只需要兩類型的RPC調(diào)用芽隆。而在第7節(jié)為在server間轉(zhuǎn)移snapshots添加了第三種RPC。
- RequestVote：在選舉期間由candidates發(fā)起
- AppendEntries：由leader發(fā)起的復(fù)制log entries以及heartbeat统屈。
