定義共識問題的安全性與活性性質，說明 FLP 不可能結果的含意與實務上的繞法。
解釋複寫狀態機（replicated state machine）為何是共識最重要的應用形式。
走一遍單值 Paxos 的兩個階段並說明多數決交集為何保證安全。
完整描述 Raft：任期、領導者選舉、日誌複寫、commit 規則、選舉限制，以及 Figure 8 的微妙之處。
理解成員變更、快照、唯讀查詢的正確處理與 PreVote/CheckQuorum 等工程修正。
說明失效偵測、租約與 fencing token，以及它們在 PostgreSQL 高可用（Patroni + etcd）中的角色。
共識問題
一群節點要對一個值（或一串值）達成一致，即使部分節點當機、網路延遲或分割。正確的共識演算法滿足：
Safety：Agreement（所有決定的節點決定同一個值）、Validity（決定的值是某個節點提議過的）、Integrity（每個節點最多決定一次）。
Liveness：Termination（所有未失效的節點最終都會決定）。
FLP 不可能結果（Fischer, Lynch, Paterson 1985）：在完全非同步的系統中，只要可能有一個節點當機，就沒有確定性演算法能保證終止。 實務的繞法是假設部分同步（timeout 最終會可靠）並使用隨機化（Raft 的隨機選舉逾時）——演算法永遠保證安全性，活性則在網路「夠好」時成立。
共識、原子廣播（所有節點以相同順序收到相同訊息）、linearizable 的 compare-and-set 暫存器、以及領導者選舉在計算能力上互相等價。 資料庫用它來：選主（避免腦裂）、複寫日誌（讓複本一致）、儲存叢集設定與分片對照表、實作分散式鎖。
複寫狀態機
複寫狀態機（RSM）是共識在資料庫中的標準形態：客戶端命令先進入共識模組，共識保證所有伺服器的日誌一致， 每台伺服器把已 commit 的日誌依序餵給確定性的狀態機（可以是 KV 儲存、資料庫的 WAL 套用器、設定儲存）。 只要多數節點存活，系統就能持續服務，且任何存活節點的狀態都可以重建出來。
Paxos
Lamport 的 Paxos（1989 年寫成、1998 年發表、2001 年 ）是第一個被證明正確的實用共識演算法。 角色：Proposer（提議值）、Acceptor（投票；通常 \(2f+1\) 個，容忍 \(f\) 個失效）、Learner（得知結果）。 單值（single-decree）Paxos 分兩階段，提案編號 \(n\) 全域唯一且遞增：
Phase 1a Prepare(\(n\))：proposer 向 acceptors 送出編號 \(n\)。
Phase 1b Promise：acceptor 若 \(n\) 大於它見過的任何編號，承諾不再接受編號 \(< n\) 的提案，並回覆它已接受的最高編號提案 \((n', v')\)（若有）。Phase 2a Accept(\(n\), \(v\))：收到多數 promise 後，proposer 選值：若任何回覆帶有已接受的值，必須採用其中編號最高的 \(v'\)；否則可用自己的值。
Phase 2b Accepted：acceptor 若未承諾過更高編號，接受 \((n, v)\) 並通知 learners。多數 acceptor 接受同一 \((n, v)\) 即選定（chosen）。
安全性的核心：任兩個多數集合必有交集。若值 \(v\) 已被選定（多數接受），之後任何 prepare(\(n'\)) 的多數回覆中必有至少一個 acceptor 回報 \(v\)（或更新但同樣源自 \(v\) 的提案）， proposer 被迫沿用 \(v\)，所以永遠不會選定第二個值。活性問題：兩個 proposer 輪流以更高編號互相搶先（dueling proposers）可能永不終止—— 解法是選出一個distinguished proposer（leader），這就把問題帶回領導者選舉，但選舉本身不需要安全（錯選只影響活性）。
Multi-Paxos：對日誌的每個位置跑一次 Paxos 太貴；穩定的 leader 只需跑一次 Phase 1 涵蓋所有未來位置，之後每筆命令只需 Phase 2 的一輪往返。 但論文沒有規定 leader 選舉、日誌補洞、成員變更、快照的細節，每個實作（Chubby、Spanner、Neon 的 safekeeper）都自行發明—— Google 的 詳述從論文到生產系統的鴻溝。這正是 Raft 誕生的動機。
Raft
Ongaro 與 Ousterhout（2014）以可理解性為設計目標：強領導者、把問題分解為選舉、日誌複寫、安全性三部分，並以 term 與日誌索引保持狀態簡單。
狀態與任期
時間切成遞增的 term（任期），每個 term 以一次選舉開始，最多一個 leader。每個 RPC 都帶 term：收到更高 term 的節點立刻更新並退回 follower；收到較低 term 的請求則拒絕。 Term 是 Raft 的邏輯時鐘，用來識別過期的 leader 與訊息。
領導者選舉
Follower 在隨機化的選舉逾時（如 150–300 ms）內沒收到 leader 的心跳（空的 ），就自增 term、轉為 candidate、投自己一票並向所有節點送 。 每個節點在一個 term 內只投一票（先到先得，且須持久化），獲得多數票者成為 leader 並立刻發心跳。隨機逾時讓分票（split vote）很快自行化解。 Election Safety：一個 term 最多一個 leader——因為多數票不可能同時給兩人。
日誌複寫
客戶端命令到 leader，leader 追加到自己的日誌（持久化），平行送 給所有 followers。
Follower 檢查 處的 term 是否等於 （一致性檢查）；是則追加（刪除衝突的後續 entries），回覆成功。
Entry 被多數節點存下後，leader 推進 並套用到狀態機、回覆客戶端；followers 從下一次 RPC 的 得知並套用。
Log Matching 性質：若兩份日誌在某 index 的 entry 有相同 term，則它們在該 index 之前完全相同——由「leader 在一個 term 內對一個 index 最多建立一筆」加上一致性檢查歸納得到。
安全性：選舉限制與 commit 規則
選舉限制： 帶上 candidate 最後一筆 entry 的 (term, index)；投票者只在 candidate 的日誌至少與自己一樣新 （最後 term 較大，或 term 相同而日誌較長）時才投票。因為已 commit 的 entry 存在於多數節點，而 candidate 需要多數票， 所以新 leader 必定擁有所有已 commit 的 entries——Leader Completeness。Raft 的日誌只從 leader 流向 follower，leader 永不覆寫自己的日誌。
Commit 規則（Figure 8）：leader 不能僅因為「舊 term 的 entry 已複製到多數」就 commit 它——那個多數可能在之後被擁有更高 term 的 candidate 覆蓋。 Leader 只透過計數 commit 當前 term 的 entry；一旦當前 term 的某筆 entry commit，Log Matching 使其之前的所有 entry 也間接 commit。 實務上 leader 上任時立刻追加一筆當前 term 的 no-op entry 以盡快 commit 前任遺留的 entries。
State Machine Safety：若某節點在 index \(i\) 套用了某 entry，其他節點在 \(i\) 不會套用不同的 entry。
工程上必須處理的事
持久化：、、日誌必須在回覆 RPC 前 fsync——這是 Raft 的 WAL。
日誌壓縮：狀態機定期產生快照（含 last included index/term），截斷之前的日誌；落後太多的 follower 以 追上。
成員變更：直接從舊設定切到新設定可能出現兩個不相交的多數。Raft 提供 joint consensus（過渡期需新舊兩組多數）或較簡單的單節點變更（一次只加減一台）。
客戶端語意：命令可能已 commit 但回覆遺失，重送會重複執行；客戶端為每個命令帶唯一 id，狀態機去重，才有 linearizable 語意。
唯讀查詢：leader 直接讀自己的狀態機可能是過期讀（它可能已被罷免而不自知）。正確做法：讀之前先與多數交換一輪心跳確認仍是 leader（ReadIndex）， 或使用領導者租約（假設時鐘漂移有界，在租約期內免心跳）；follower read 可透過 ReadIndex 向 leader 取得 commitIndex 後等待套用。
PreVote 與 CheckQuorum（etcd）：被分割後重新加入的節點 term 已經很高，會把現任 leader 打下台（disruptive server）；PreVote 讓它先詢問「若我參選能否勝出」，CheckQuorum 讓失去多數聯繫的 leader 主動下台。
效能：批次（一個 RPC 多筆 entries）、pipelining（不等回覆連續送）、平行 fsync 與網路傳送、leader 只需等多數即可 commit（慢的 follower 不拖累）。
Raft 與 Paxos 的比較
P2.4cmP5.6cmP5.6cm & (Multi-)Paxos & Raft
領導者 & 可選（提升效能），任何節點可提議 & 必須；所有寫入經由 leader
日誌 & 允許空洞，各 slot 獨立決定；需要補洞 & 嚴格連續，無空洞
選舉 & 論文未規定；實作各異 & 明確定義，附帶選舉限制
誰能當 leader & 任何節點，之後補齊缺少的 entries & 只有日誌最新的節點
理解與驗證 & 困難；多個生產系統有過 bug & 設計目標即可理解性；有 TLA+ 規格與數十個實作
變體 & Flexible Paxos（quorum 只需 \(|Q_1| + |Q_2| > N\)）、EPaxos（無領導者）、Mencius & etcd/raft、TiKV raft-rs、HashiCorp raft、Kafka KRaft
Howard 與 Mortier（2020）指出：撇開表述方式，兩者的核心機制幾乎同構，差別主要在 leader 選舉的策略與日誌是否允許空洞。 其他家族成員：Viewstamped Replication（1988，比 Paxos 發表更早、與 Raft 極為相似）、ZAB（ZooKeeper 的原子廣播）。
失效偵測、租約與 fencing
心跳與逾時：唯一的偵測手段，但無法區分「死了」「很慢」「網路斷了」。逾時太短 \(\to\) 誤判與頻繁選舉；太長 \(\to\) 失效後長時間不可用。
\(\phi\) accrual 偵測器（Hayashibara 2004）：以歷史心跳間隔的分佈輸出「懷疑程度」而非布林值，應用程式自選門檻；Cassandra、Akka 採用。
SWIM（Das 2002）：隨機 ping 加間接 ping、以 gossip 傳播成員狀態，訊息量不隨節點數線性成長；Consul/Serf、memberlist 採用。
租約（lease）：leader 在一段時間內被授權獨占；依賴「時鐘漂移有界」的假設。
Fencing token：鎖服務每次授權附上遞增編號，儲存端拒絕較舊編號的寫入——即使持鎖者因 GC 暫停、網路延遲而「以為自己還持有鎖」也不會造成損害 （Kleppmann 對 Redlock 的批評即在此：沒有 fencing 的分散式鎖無法保證安全）。
PostgreSQL 核心沒有內建共識：同步複寫保證資料不遺失，但不會自動選主，也不防止腦裂。 高可用由外部工具補足——Patroni 把「誰是 primary」存在 etcd/Consul/ZooKeeper（統稱 DCS）的一把帶 TTL 的鎖中： primary 必須在 TTL 內持續更新租約，否則自我降級（ 或 watchdog 重啟機器）；其他節點透過 DCS 競爭成為新 primary，並以 讓舊 primary 回來當 standby。 這是「以共識儲存做領導者選舉 + 租約 + fencing」的教科書應用。 Neon 則更進一步，把 WAL 寫入一組以 Paxos 複寫的 safekeepers，計算節點無狀態、可任意重啟。
採用共識的系統
協調服務：etcd（Raft；Kubernetes、Patroni 的後端）、ZooKeeper（ZAB；Kafka 舊版、HBase、Hadoop）、Consul（Raft）。
分散式資料庫（Multi-Raft）：每個分片（range / region）一個 Raft 群組——TiKV（數萬個 region，心跳合併）、CockroachDB（leaseholder 處理讀取、follower reads 以 closed timestamp）、YugabyteDB。
Paxos 系：Google Chubby、Spanner（每個 Paxos 群組一個 tablet）、Megastore、Azure Cosmos DB、Neon safekeepers。
訊息系統：Kafka KRaft（2022 起取代 ZooKeeper 管理 metadata）、Pulsar/BookKeeper（quorum 寫入）。
MongoDB：複本集選舉與複寫協定是 Raft 的變體（pull-based 複寫）。
把 v7 的「leader 串流 WAL」升級為 Raft：每筆交易的 WAL 記錄（或整個 commit group）作為一個 Raft entry， commit 後才回覆客戶端並套用到本地儲存引擎。實作順序建議依 MIT 6.5840 Lab 3：(A) 選舉與心跳、(B) 日誌複寫與 commit、(C) 持久化、(D) 快照。 測試是重點：模擬網路分割、訊息延遲與重排、節點重啟，檢查「已回覆成功的寫入永不遺失」「任一時刻最多一個 leader 能 commit」兩個不變量。 raft.github.io 的互動視覺化與 TLA+ 規格是除錯時的好朋友。
5 個 acceptor 的 Paxos：proposer P1 以 \(n=1\) 讓 A1、A2、A3 接受值 X；P2 以 \(n=2\) 向 A3、A4、A5 做 prepare。P2 會得到什麼回覆？它可以提議自己的值 Y 嗎？為什麼？
畫出 Raft 論文 Figure 8 的情境（5 節點、S1 在 term 2 的 entry 被複製到多數後 S1 崩潰……），說明若 leader 以「舊 term entry 到達多數」為 commit 條件會如何違反安全性。
3 節點 Raft 叢集，follower C 與其他節點分割 10 分鐘後重新連上。沒有 PreVote 時會發生什麼？PreVote 如何避免？
為什麼 Raft 要求投票給「日誌至少一樣新」的 candidate，而 Multi-Paxos 允許任何節點當 leader？各自的代價是什麼？
Leader 收到唯讀請求 ，直接回傳本地狀態機的值。構造一個違反 linearizability 的情境；再說明 ReadIndex 與租約兩種修法的假設差異。
一個 Raft 群組的寫入延遲由什麼決定？跨三個資料中心（往返 30 ms、80 ms）部署 5 節點時，leader 應放在哪裡？follower 數量增加會讓寫入更快還是更慢？
設計 Patroni 式的 failover：primary 的租約 TTL 為 30 s、更新間隔 10 s。最壞情況下服務中斷多久？若 primary 的程序被 GC/磁碟 I/O 卡住 40 秒後恢復，會發生什麼？fencing 在哪一步生效？
D. Ongaro, J. Ousterhout, , USENIX ATC 2014：https://raft.github.io/raft.pdf； Raft 官網（視覺化、實作清單、TLA+）：https://raft.github.io/；D. Ongaro 博士論文 Consensus: Bridging Theory and Practice, Stanford 2014（成員變更、客戶端互動、效能的完整處理）。
L. Lamport, , 2001：https://lamport.azurewebsites.net/pubs/paxos-simple.pdf；, ACM TOCS 1998。
T. Chandra, R. Griesemer, J. Redstone, , PODC 2007。
M. Fischer, N. Lynch, M. Paterson, , JACM 1985。
H. Howard, R. Mortier, , PaPoC 2020：https://arxiv.org/abs/2004.05074； H. Howard et al., , 2016。
B. Oki, B. Liskov, , PODC 1988；B. Liskov, J. Cowling, , 2012。
N. Hayashibara et al., , SRDS 2004；A. Das, I. Gupta, A. Motivala, , DSN 2002。
M. Kleppmann, How to do distributed locking, 2016（fencing token）：https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
The Secret Lives of Data: Raft 互動式教學：https://thesecretlivesofdata.com/raft/
MIT 6.5840 Lab 3 Raft（Go 實作與測試框架）：https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
etcd raft 函式庫：https://github.com/etcd-io/raft；TiKV ：https://github.com/tikv/raft-rs；Patroni 文件 Replication modes 與 Watchdog。