當(dāng)機(jī)房 A 修改了一條數(shù)據(jù)的同時，機(jī)房 B 也對該數(shù)據(jù)進(jìn)行了更新，Otter 會通過合并邏輯來處理沖突的數(shù)據(jù)行或字段，以達(dá)到合并效果。為了避免這種沖突，我們在上節(jié)課對客戶端提出了要求：用戶客戶端在一定時間內(nèi)只能連接一個機(jī)房。然而，如果業(yè)務(wù)對“事務(wù)和強(qiáng)一致性”有極高的需求，例如庫存不允許超賣的場景，通常只有兩種選擇：一種是將服務(wù)部署為本地服務(wù)，但這并不適用于所有業(yè)務(wù)；另一種是使用多機(jī)房架構(gòu)，但必須采用分布式強(qiáng)一致性算法以確保多個副本之間的一致性。

在業(yè)界，最知名的分布式強(qiáng)一致性算法是 Paxos。盡管它的原理非常抽象，經(jīng)過多次修改后往往會與最初設(shè)計(jì)產(chǎn)生很大偏離，使得很多人難以判斷這些修改是否合理。通常需要一到兩年的實(shí)踐經(jīng)驗(yàn)才能完全掌握該算法。隨著對分布式多副本同步需求的增加，Paxos 的抽象性已無法完全滿足市場需求，因此 Raft 算法應(yīng)運(yùn)而生。相比于 Paxos，Raft 更易于理解，同時能夠保證操作的順序一致性，因此被廣泛應(yīng)用于分布式數(shù)據(jù)服務(wù)中，像 etcd 和 Kafka 等知名基礎(chǔ)組件都使用了 Raft 算法。

如何選舉 Leader？

圖片

如圖所示，我們啟動了五個 Raft 分布式數(shù)據(jù)服務(wù)節(jié)點(diǎn)：S1、S2、S3、S4 和 S5。每個節(jié)點(diǎn)可以處于以下三種狀態(tài)之一：

• Leader：負(fù)責(zé)處理數(shù)據(jù)修改，并主動將變更同步到其他 Follower 節(jié)點(diǎn)。
• Follower：接收并應(yīng)用 Leader 推送的變更數(shù)據(jù)。
• Candidate：當(dāng)集群中沒有 Leader 時，F(xiàn)ollower 節(jié)點(diǎn)會進(jìn)入選舉模式。

如果某個 Follower 節(jié)點(diǎn)在規(guī)定時間內(nèi)未收到 Leader 的心跳信號，則意味著當(dāng)前 Leader 可能已失效，集群無法繼續(xù)更新數(shù)據(jù)。在這種情況下，F(xiàn)ollower 節(jié)點(diǎn)會進(jìn)入選舉模式，并在多個 Follower 節(jié)點(diǎn)之間選出一個新的 Leader，確保服務(wù)集群中始終有一個 Leader，確保數(shù)據(jù)變更的唯一決策進(jìn)程。

那么 Leader 是如何選舉出來的呢？在進(jìn)入選舉模式后，這五個節(jié)點(diǎn)會各自隨機(jī)等待一段時間。等待時間一到，當(dāng)前節(jié)點(diǎn)會先為自己投一票，并將其任期（term）加 1（如圖中的 term:4 表示第四任 Leader），然后通過發(fā)送 RequestVote RPC（即請求投票的遠(yuǎn)程過程調(diào)用）向其他節(jié)點(diǎn)拉票。

圖片

S1失去聯(lián)系，S5最先超時發(fā)起選舉

當(dāng)服務(wù)節(jié)點(diǎn)收到投票請求時，如果該請求節(jié)點(diǎn)的任期和日志同步進(jìn)度都領(lǐng)先或相同，則會向其投票，并將自己的當(dāng)前任期更新為新的任期。在此期間，收到投票請求的節(jié)點(diǎn)將不會再發(fā)起投票，而是等待其他節(jié)點(diǎn)的投票邀請。需要注意的是，每個節(jié)點(diǎn)在同一任期內(nèi)只能投出一票。

如果所有節(jié)點(diǎn)在選舉過程中都未獲得多數(shù)票（即超過半數(shù)的票數(shù)），則在選舉超時后，節(jié)點(diǎn)會將任期加 1 并重新發(fā)起選舉。最終，獲得多數(shù)票且最早結(jié)束選舉倒計(jì)時的節(jié)點(diǎn)將當(dāng)選為新的 Leader。該 Leader 隨即廣播通知其他節(jié)點(diǎn)，并同步新的任期和日志進(jìn)度。

在成為 Leader 后，新的 Leader 會定期發(fā)送心跳信號，確保各個 Follower 節(jié)點(diǎn)保持連接狀態(tài)，不因超時而進(jìn)入選舉模式。在選舉過程中，如果有節(jié)點(diǎn)收到了前一任 Leader 的心跳信號，便會停止當(dāng)前的選舉并拒絕新的選舉請求。選舉結(jié)束后，所有節(jié)點(diǎn)進(jìn)入數(shù)據(jù)同步狀態(tài)，確保日志一致性。

如何保證多副本寫一致？

當(dāng)服務(wù)節(jié)點(diǎn)收到投票請求時，如果該請求節(jié)點(diǎn)的任期和日志同步進(jìn)度都領(lǐng)先或相同，則會向其投票，并將自己的當(dāng)前任期更新為新的任期。在此期間，收到投票請求的節(jié)點(diǎn)將不會再發(fā)起投票，而是等待其他節(jié)點(diǎn)的投票邀請。需要注意的是，每個節(jié)點(diǎn)在同一任期內(nèi)只能投出一票。

如果所有節(jié)點(diǎn)在選舉過程中都未獲得多數(shù)票（即超過半數(shù)的票數(shù)），則在選舉超時后，節(jié)點(diǎn)會將任期加 1 并重新發(fā)起選舉。最終，獲得多數(shù)票且最早結(jié)束選舉倒計(jì)時的節(jié)點(diǎn)將當(dāng)選為新的 Leader。該 Leader 隨即廣播通知其他節(jié)點(diǎn)，并同步新的任期和日志進(jìn)度。

在成為 Leader 后，新的 Leader 會定期發(fā)送心跳信號，確保各個 Follower 節(jié)點(diǎn)保持連接狀態(tài)，不因超時而進(jìn)入選舉模式。在選舉過程中，如果有節(jié)點(diǎn)收到了前一任 Leader 的心跳信號，便會停止當(dāng)前的選舉并拒絕新的選舉請求。選舉結(jié)束后，所有節(jié)點(diǎn)進(jìn)入數(shù)據(jù)同步狀態(tài)，確保日志一致性。

圖片

具體來說，當(dāng) Leader 成功修改數(shù)據(jù)后，它會生成一條對應(yīng)的日志，并將該日志發(fā)送給所有 Follower 節(jié)點(diǎn)進(jìn)行同步。只要超過半數(shù)的 Follower 返回同步成功的反饋，Leader 就會將該預(yù)提交的日志正式提交（commit），并向客戶端確認(rèn)數(shù)據(jù)修改成功。

在下一個心跳中，Leader 會通過消息中的 leader commit 字段，將當(dāng)前最新提交的日志索引（Log index）告知各 Follower 節(jié)點(diǎn)。Follower 節(jié)點(diǎn)依據(jù)該提交的索引更新數(shù)據(jù)，僅對外提供被 Leader 最終提交的數(shù)據(jù)，未被提交的數(shù)據(jù)不會被持久化或展示。

如果在數(shù)據(jù)同步期間，客戶端繼續(xù)向 Leader 發(fā)送其他修改請求，這些請求會進(jìn)入隊(duì)列等待處理，因?yàn)榇藭r Leader 正在等待其他節(jié)點(diǎn)的同步響應(yīng)，導(dǎo)致暫時的阻塞。

圖片

不過，這種阻塞等待的設(shè)計(jì)使得 Raft 算法對網(wǎng)絡(luò)性能的依賴性較強(qiáng)，因?yàn)槊看螖?shù)據(jù)修改都需要向多個節(jié)點(diǎn)發(fā)出并發(fā)請求，等待大多數(shù)節(jié)點(diǎn)成功同步。最糟糕的情況是，返回的往返時延（RTT）會受到最慢節(jié)點(diǎn)的網(wǎng)絡(luò)響應(yīng)時間影響，例如“兩地三中心”的一次同步時間可能達(dá)到約 100ms。此外，由于主節(jié)點(diǎn)只有一個，這限制了 Raft 服務(wù)的整體性能。

為了解決這個問題，我們可以通過減少數(shù)據(jù)量和對數(shù)據(jù)進(jìn)行切片來提升集群的修改性能。需要注意的是，當(dāng)大多數(shù) Follower 與 Leader 的日志進(jìn)度差異過大時，數(shù)據(jù)變更請求將會處于等待狀態(tài)，直到超過一半的 Follower 與 Leader 的進(jìn)度一致后，才會返回修改成功的結(jié)果。當(dāng)然，這種情況并不常見。

服務(wù)之間如何同步日志進(jìn)度？

講到這我們不難看出，在 Raft 的數(shù)據(jù)同步機(jī)制中，日志發(fā)揮著重要的作用。在同步數(shù)據(jù)時，Raft 采用的日志是一個有順序的指令日志 WAL（Write Ahead Log），類似 MySQL 的 binlog。該日志中記錄著每次修改數(shù)據(jù)的指令和修改任期，并通過 Log Index 標(biāo)注了當(dāng)前是第幾條日志，以此作為同步進(jìn)度的依據(jù)。

在 Raft 中，Leader 節(jié)點(diǎn)的日志是永久保留的，所有 Follower 節(jié)點(diǎn)會與 Leader 保持完全一致。如果出現(xiàn)差異，F(xiàn)ollower 的日志將被強(qiáng)制覆蓋以與 Leader 同步。此外，每條日志記錄都經(jīng)過“寫入”和“提交”（commit）兩個階段。在選舉過程中，每個節(jié)點(diǎn)會基于自身未提交的日志索引（Log Index）進(jìn)度優(yōu)先選擇進(jìn)度最靠前的節(jié)點(diǎn)，從而確保當(dāng)選的 Leader 擁有最新、最完整的數(shù)據(jù)。

在 Leader 任期內(nèi)，它會按順序向各 Follower 節(jié)點(diǎn)推送日志以實(shí)現(xiàn)同步。若 Leader 的同步進(jìn)度領(lǐng)先于某個 Follower，該 Follower 將拒絕同步請求。收到拒絕反饋后，Leader 會從日志末尾向前回溯，找出 Follower 未同步或存在差異的日志部分，然后逐條推送覆蓋，直到 Follower 與 Leader 保持一致。

圖片

Leader 和 Follower 的日志同步進(jìn)度是通過日志索引（index）來確認(rèn)的。Leader 對日志的內(nèi)容和順序擁有絕對的決策權(quán)，當(dāng)發(fā)現(xiàn)自己的日志與某個 Follower 的日志存在差異時，為了確保多個副本的數(shù)據(jù)完全一致，Leader 會強(qiáng)制覆蓋該 Follower 的日志。

那么，Leader 是如何識別 Follower 的日志與自己的日志之間的差異呢？在向 Follower 同步日志時，Leader 會同時提供自己上一條日志的任期和索引號，與 Follower 當(dāng)前的同步進(jìn)度進(jìn)行比較。對比主要涉及兩個方面：

• 當(dāng)前日志對比：Leader 會對比自己和 Follower 的當(dāng)前日志中的索引、多條操作日志和任期。
• 上一條日志對比：Leader 會對比自己和 Follower 的上一條日志的索引和任期。

如果以上任意一個方面存在差異，Leader 就會認(rèn)為 Follower 的日志與自己的日志不一致。在這種情況下，Leader 會逐條倒序?qū)Ρ热罩荆钡秸业饺罩緝?nèi)容和任期完全一致的索引，然后從這個索引開始按順序向下覆蓋。

在日志同步期間，Leader 只會提交其當(dāng)前任期內(nèi)的數(shù)據(jù)，之前任期的數(shù)據(jù)則依賴日志同步來逐步恢復(fù)?？梢钥吹?，這種逐條推送的同步方式效率較低，特別是對新啟動的服務(wù)并不友好。因此，Leader 會定期生成快照，將之前的修改日志記錄合并，以降低日志的大小。同時，進(jìn)度差距過大的 Follower 會從 Leader 的最新快照中恢復(fù)數(shù)據(jù)，并按快照最后的索引追趕進(jìn)度。

如何保證讀取數(shù)據(jù)的強(qiáng)一致性？

通過前面的講解，我們了解了 Leader 和 Follower 之間的同步機(jī)制，那么從 Follower 的角度來看，它又是如何確保自己對外提供的數(shù)據(jù)始終是最新的呢？這里有一個小技巧：當(dāng) Follower 收到查詢請求時，會同時向 Leader 請求當(dāng)前最新提交的日志索引（commit log index）。如果這個日志索引大于 Follower 當(dāng)前的同步進(jìn)度，就意味著 Follower 的本地?cái)?shù)據(jù)不是最新的。此時，F(xiàn)ollower 會從 Leader 獲取最新的數(shù)據(jù)并返回給客戶端。

由此可見，保持?jǐn)?shù)據(jù)的強(qiáng)一致性需要付出較大的代價。

圖片

你可能會好奇：如何在業(yè)務(wù)使用時保證讀取數(shù)據(jù)的強(qiáng)一致性呢？其實(shí)我們之前說的 Raft 同步等待 Leader commit log index 的機(jī)制，已經(jīng)確保了這一點(diǎn)。我們只需要向 Leader 正常提交數(shù)據(jù)修改的操作，F(xiàn)ollower 讀取時拿到的就一定是最新的數(shù)據(jù)。

總結(jié)

很多人都說 Raft 是一個分布式一致性算法，但實(shí)際上 Raft 算法是一個共識算法（多個節(jié)點(diǎn)達(dá)成共識），它通過任期機(jī)制、隨機(jī)時間和投票選舉機(jī)制，實(shí)現(xiàn)了服務(wù)動態(tài)擴(kuò)容及服務(wù)的高可用。通過 Raft 采用強(qiáng)制順序的日志同步實(shí)現(xiàn)多副本的數(shù)據(jù)強(qiáng)一致同步，如果我們用 Raft 算法實(shí)現(xiàn)用戶的數(shù)據(jù)存儲層，那么數(shù)據(jù)的存儲和增刪改查，都會具有跨機(jī)房的數(shù)據(jù)強(qiáng)一致性。這樣一來，業(yè)務(wù)層就無需關(guān)心一致性問題，對數(shù)據(jù)直接操作，即可輕松實(shí)現(xiàn)多機(jī)房的強(qiáng)一致同步。