• 為什么需要 Raft听怕？
• Raft 是什么奸焙？
• Raft 的目標(biāo)
• 前置條件：復(fù)制狀態(tài)機(jī)
• Raft 基礎(chǔ)
• Leader 選舉（選舉安全特性）
• 日志復(fù)制（Leader只附加福扬、日志匹配）
• 安全
• 學(xué)習(xí)資料
• 使用 Raft 的應(yīng)用惠毁？
• 擴(kuò)展：ZooKeeper ZAB 協(xié)議
• 擴(kuò)展：ZooKeeper 是什么圾旨？

為什么需要 Raft季稳？

• 要提高系統(tǒng)的容錯(cuò)率，需要分布式系統(tǒng)
• 分布式系統(tǒng)有多個(gè)實(shí)例，對(duì)于給定的一組操作狰住，需要協(xié)議讓所有實(shí)例達(dá)成一致（分布式一致性）
• Paxos 是分布式一致性協(xié)議的標(biāo)準(zhǔn)，但難以理解齿梁、實(shí)現(xiàn)
• Raft 提供了和 Paxos 算法相同的功能催植，但更好理解、構(gòu)建實(shí)際的系統(tǒng)

Raft 是什么勺择？

• Replicated And Fault Tolerant创南，復(fù)制和容錯(cuò)
• 管理復(fù)制日志的一致性算法

Raft 的目標(biāo)

• 簡單易理解
• 提供完整的實(shí)現(xiàn)系統(tǒng)，減少開發(fā)者的工作量
• 保證所有條件下都是安全的省核，在大部分情況下是可用的
• 常用操作是高效的

前置條件：復(fù)制狀態(tài)機(jī)

• Raft 相當(dāng)于復(fù)制狀態(tài)機(jī)中的“一致性模塊”
• 一致性模塊（Consensus Module）：管理來自客戶端的指令稿辙，接入 log
• 日志（Log）
• 狀態(tài)機(jī)（State Machine）：執(zhí)行日志的指令，得到 Server 狀態(tài)

Raft 基礎(chǔ)

• 節(jié)點(diǎn)狀態(tài)：
  • Leader（領(lǐng)導(dǎo)者）：系統(tǒng)只有一個(gè)節(jié)點(diǎn)處是 Leader气忠，處理所有客戶端的請(qǐng)求并同步給 Follower
  • Follower（跟隨者）：只響應(yīng)其他服務(wù)器（Leader邻储、Candidate）的請(qǐng)求
  • Candidate（候選者）：在選舉領(lǐng)導(dǎo)的時(shí)候出現(xiàn)
• term（任期）：
  • 一段選舉的任期（選舉開始+正常工作）
  • term 號(hào)自動(dòng) +1
  • 如果選票均分，則該 term 直接結(jié)束旧噪，進(jìn)入下一個(gè) term
  • Raft 中的「邏輯時(shí)鐘」吨娜，可發(fā)現(xiàn)過期信息，規(guī)則：
    • 每個(gè)節(jié)點(diǎn)會(huì)存儲(chǔ)當(dāng)前 term 號(hào)淘钟，term 編號(hào)單調(diào)遞增
    • 節(jié)點(diǎn)間通信宦赠，交換 term 號(hào)
    • （1）節(jié)點(diǎn)當(dāng)前 term 號(hào) < 他人 term 號(hào)，更新 term 號(hào)
    • （2）節(jié)點(diǎn)當(dāng)前 term 號(hào) > 他人 term 號(hào)米母，拒絕請(qǐng)求
    • （3）Candidate勾扭、Leader 發(fā)現(xiàn)自己的 term < 他人 term，立即變成 Follower
• 節(jié)點(diǎn)通信：使用 RPC
  • 請(qǐng)求投票（RequestVote） RPCs：選舉階段铁瞒，Candidate 節(jié)點(diǎn)發(fā)送給他人
  • 附加條目（AppendEntries）RPCs：非選舉階段妙色，Leader 發(fā)給所有節(jié)點(diǎn)，復(fù)制日志+心跳
• 特性（Raft 保證在任何時(shí)候都成立）
  • 選舉安全：對(duì)一個(gè)給定的 term 號(hào)精拟，最多選舉出一個(gè) Leader
  • Leader 只附加原則：Leader 不會(huì)刪除燎斩、覆蓋自己的日志虱歪，只會(huì)增加
  • 日志匹配：若兩個(gè)日志在相同索引位置的日志的 term 號(hào)相同，則日志從頭到該索引位置全部相同
  • Leader 完整特性：選舉出的 Leader栅表，會(huì)包含所有已提交的日志
  • 狀態(tài)機(jī)安全特性：Leader 已經(jīng)將給定的索引值位置的日志條目應(yīng)用到狀態(tài)機(jī)笋鄙，其他任何服務(wù)器都已執(zhí)行

Leader 選舉（選舉安全特性）

• Raft 使用心跳機(jī)制觸發(fā) Leader 選舉
  • 集群存在 Leader，Leader 節(jié)點(diǎn)周期性發(fā)心跳包
  • 一個(gè) Follower 沒有收到任何消息（固定區(qū)間隨機(jī)的時(shí)間）怪瓶，發(fā)起選舉
• 集群啟動(dòng)時(shí)萧落，所有節(jié)點(diǎn)都處于 Follower 狀態(tài)
• 節(jié)點(diǎn)到達(dá)超時(shí)時(shí)間后，會(huì)進(jìn)入 Candidate 狀態(tài)洗贰，增加自己的 term 號(hào)找岖，發(fā)送請(qǐng)求投票給自己
• Candidate 狀態(tài)機(jī)
  • 節(jié)點(diǎn)得票最多的，變成 Leader
  • 收到來自其他節(jié)點(diǎn)的“聲明自己是 Leader”的請(qǐng)求
  • 一段時(shí)間后敛滋，沒有獲得多數(shù)票许布，也沒有收到其他節(jié)點(diǎn)的 Leader 通知（平分選票）
• 避免選舉的平分選票：隨機(jī)選舉超時(shí)時(shí)間
  • 每個(gè)節(jié)點(diǎn)隨機(jī)選擇選舉超時(shí)時(shí)間，到達(dá)時(shí)間后成為 Candidate
  • 大多數(shù)情況下绎晃，只有一個(gè)節(jié)點(diǎn)率先進(jìn)入 Candidate

日志復(fù)制（Leader只附加蜜唾、日志匹配）

• Leader 會(huì)接收客戶端的請(qǐng)求，請(qǐng)求指令作為一個(gè)“日志條目”添加到日志中
• 向所有 Follower 發(fā)送附加條目 RPC庶艾，讓他們復(fù)制這個(gè)日志條目
• 得到大多數(shù)節(jié)點(diǎn)回復(fù)后袁余，Leader 會(huì)把日志寫入復(fù)制狀態(tài)機(jī)，持久化咱揍，把執(zhí)行結(jié)果返回給客戶端
• 日志非安全的颖榜；進(jìn)入狀態(tài)機(jī)中是安全的（已提交），最終會(huì)被所有可用的狀態(tài)機(jī)執(zhí)行煤裙。

index = 7 的日志已經(jīng)被大多數(shù)節(jié)點(diǎn)復(fù)制掩完，狀態(tài)為已提交。

安全

• 選舉限制（Leader 完整性）：每次選舉出來的 Leader积暖，必須包含所有已提交的日志
  • 只有已經(jīng)被大部分節(jié)點(diǎn)復(fù)制的日志藤为，才會(huì)變成“已提交”
  • 一個(gè) Candidate 必須得到大部分節(jié)點(diǎn)投票，才能變成 Leader
  • 投票時(shí)夺刑，節(jié)點(diǎn)不會(huì)把票投給沒有自己的日志新的 Candidate
• Follower 或 Candidate 崩潰：無限重試
• 超時(shí)和可用性：broadcastTime（廣播時(shí)間）<< electionTimeout（選舉超時(shí)時(shí)間）<< MTBF（平均故障間隔時(shí)間)

學(xué)習(xí)資料

• 生動(dòng)形象的網(wǎng)站：http://thesecretlivesofdata.com/raft/
• 論文：https://raft.github.io/raft.pdf

使用 Raft 的應(yīng)用？

• 服務(wù)發(fā)現(xiàn)框架：consul分别、etcd
• 日志：RocketMQ
• 數(shù)據(jù)存儲(chǔ)：Tidb遍愿、k8s

擴(kuò)展：ZooKeeper ZAB 協(xié)議

• 支持崩潰恢復(fù)的原子廣播協(xié)議：ZooKeeper Atomic Broadcast protocol
• ZooKeeper 適合讀多寫少的場景，客戶端隨機(jī)連到 ZK 集群的一個(gè)節(jié)點(diǎn)
  • 從當(dāng)前節(jié)點(diǎn)讀
  • 寫入到 leader耘斩，leader 廣播事務(wù)沼填，半數(shù)節(jié)點(diǎn)成功才會(huì)被提交
• 整體流程類似于 Raft，只是細(xì)節(jié)和實(shí)現(xiàn)的區(qū)別

擴(kuò)展：ZooKeeper 是什么括授？

官方定義: A Distributed Coordination Service for Distributed Applications坞笙。本質(zhì)：基于內(nèi)存的 KV 系統(tǒng)岩饼，以 path 為 key。

代碼薛夜、思維導(dǎo)圖筆記下載

代碼和思維導(dǎo)圖在 GitHub 項(xiàng)目中籍茧，歡迎大家 star！