目錄

Paxos 是什么（What）

Paxos 的目的（Why）

角色與職責（Who）

基本流程（How）

常見問題與對策

什么是多數派（Quorum）

Paxos vs Raft 異同點

---

Paxos 是什么（What）

核心問題：在節點可能宕機、網絡可能亂序/丟失的環境里，讓副本對一個值達成一致（共識），并保證安全性：系統絕不會最終選出兩個不同的值；在條件穩定時還要有活性：最終能選出一個值。

Safety（安全性）：永遠不會發生壞事。在共識里指不會選出兩個不同的值、不會破壞不變量。

Liveness（活性）：好事最終會發生。只要條件穩定（如有多數派、網絡穩定），最終會選出一個值。

Single-Decree Paxos：只為一次決議選擇一個值（例如第 k 個位置的值是什么）。它證明：一旦某值被多數派接受，這個值就是全局唯一的被選定值。

Multi-Paxos：把單次決議按槽位/索引重復，形成一條復制日志（slot 0、1、2…）。實踐里通常選出一個穩定 Leader：第一步先做一次準備（Phase 1），隨后大量槽位直接走接受階段（Phase 2），從而把消息輪次降到近似兩個來回/條目。

與 2PC 的關系：兩階段提交（2PC）假定可靠協調者，一旦協調者崩潰就可能阻塞；Paxos 則通過多數派 + 可搶占編號 + 持久化承諾/接受來保證崩潰容錯下的安全性（即使協調者樣的角色失敗，也不會選出兩個值），在網絡穩定時還能繼續前進。

槽位/索引（slot/index）：Multi-Paxos 中每一次決議對應的位置
可搶占編號：誰的排隊號大，誰就能接著推進
持久化承諾 / 接受：說過的話、同意的事，要寫在紙上存好，不能反悔。也就是會存到硬盤里

用一段話區分共識（決定一個值）與復制日志（決定很多值）

共識（決定一個值）關注的是對某一個槽位最終選哪個值，確保系統在任何時刻都不會出現兩個不同的被選定值；達成一次就結束。復制日志（決定很多值）則把對單個槽位的共識按序多次執行，為每個槽位各自達成一次共識，進而得到一條全體副本順序一致的操作序列；只要狀態機是確定性的，把這條日志在各副本重放，就能得到同樣的狀態與輸出。因此，共識是原子“磚塊”，復制日志是把許多磚塊按順序砌成墻；Multi-Paxos 是用 Paxos 磚塊去砌這堵一致的日志之墻。

狀態機是確定性的：同樣的初始狀態 + 同樣的指令順序，一定會得到同樣的結果和最終狀態

Paxos 的目的（Why）

目標
Safety（安全性）永遠成立：協議在任何時刻都不會讓同一槽位產生兩個不同的被選定值。Liveness（活性）在良好條件下成立：出現穩定時期、有可達多數派、且競爭趨緩/穩定 Leader時，最終會選出一個值。

可達的意思是指節點之間能夠正常通信

非目標
不承諾最短/固定時間內完成決定（無有界終止時間保證）
在強競爭（多主互搶）、網絡分區或不到多數派時可能無進展，但不會出錯（Safety 仍保留）

角色與職責（Who）

Proposer（提議者）
生成提案（編號 n，值 v），發起兩階段；在 Multi-Paxos 中常由Leader擔任，負責連續多個槽位（日志索引）

Acceptor（接受者）
作為“法官”投票：對較大的 n 做承諾（Promise），并在不違背承諾的前提下接受（Accept）某個 (n, v)。安全性核心在它。

Learner（學習者）
收集“Accepted”證據，當獲知多數派接受同一 (n, v) 即學習/提交該值；不參與仲裁。

Distinguished Proposer / Leader（特殊提議者 / 領導者）（工程常見）
通過選主把并發沖突降到最低；穩定后可在多數派上一次 Phase-1，多次 Phase-2（Multi-Paxos）

Acceptor 必須落盤保證安全；Proposer/Learner 可不落盤，只影響活性與恢復體驗（工程上常做適度持久化更穩定）

如果leader被替換，acceptor又接受了這個leader的提案怎么辦？

如果 Leader 被替換，Acceptor 也會把自己曾經接受過的提案報告給新 Leader，新 Leader 必須繼承這些值；因此 Paxos 保證：舊 Leader 已經多數派接受的值不會丟，沒形成多數的值可以被覆蓋，否則會破壞 Safety。

基本流程（How）

Phase 1｜Prepare/Promise
Proposer 發送 Prepare(n)；任何接到的 Acceptor 若 n > promised_n，則：
將 promised_n ← n（持久化），承諾不再接受 < n 的提案
用 Promise 回應，并攜帶自己已接受過的最高對 (accepted_n, accepted_value)（如果有）

Phase 2｜Accept/Accepted
Proposer 收到多數 Promise 后：
若看到任何已接受值，則取編號最高的那個值 v；否則可用自己的值
發送 Accept(n, v)；Acceptor 若不違背承諾（n ≥ promised_n）則：
accepted_n ← n，accepted_value ← v（持久化），并回 Accepted(n, v)

決議/學習
當多數 Acceptor 對同一 (n, v) 回 Accepted，該值 v 被選定；Learner 收斂/提交

常見問題與對策

1. 多主競爭導致活鎖
現象：多個 Proposer 同時用不同編號發起 Prepare/Accept，互相搶占，提案不斷被更大編號打斷，遲遲難以完成一次決議。
對策：選主（Leader）集中出提案；或加退避/隨機化與編號躍遷策略，減少碰撞。

退避

現象：多個 Proposer 同時沖突 → 都收不到多數 → 繼續發更大編號提案 → 無限搶占 → 活鎖。

退避策略：當 Proposer 發現自己提案被搶占（比如收到了更大編號的 Promise），就不要立刻重試，而是等待一段時間再試。

意義：給對方機會先跑完一輪，避免無限搶占循環。

隨機化

問題：如果大家都用同樣的退避時間，可能同時醒來 → 再次沖突。

隨機化策略：把等待時間加點隨機抖動，例如退避時間 = 基礎延遲 + 隨機數。

效果：減少同步碰撞，提升協議最終達成的概率。

編號躍遷

現象：一個 Proposer收到更大編號的 Prepare/Promise，說明自己落后。

編號躍遷：它可以直接把自己下一次提案編號調得遠遠更大（而不是簡單 +1），確保下一次不會再次被眼前的競爭者壓制。

效果：快速超車，減少多次小幅度沖突。工程里常設計為 <term, proposerId> 形式，保證全局有序。

2. 網絡分區 / 少數派可達
現象：無法觸達多數派時，協議無法前進，但不會產出沖突決定。
對策：維持 CP 取舍（犧牲部分可用性換一致性），等待多數派恢復再推進。

3. 崩潰與恢復
現象：節點重啟若丟失承諾/已接受狀態，會破壞歷史約束。
對策：Acceptor 必須落盤 promised_n / accepted_n / accepted_value，恢復后嚴格遵守已承諾語義。

為什么競爭只影響活性而不破壞安全？

1. Paxos 的安全性建立在多數派交集 + 承諾單調 + 值繼承三件套上，這些約束與消息時序無關，因此永遠成立。
2. 即使多個 Proposer 并發競爭、頻繁搶占編號，Acceptor 仍舊遵守承諾后不再接受小編號這一不可回退規則。
3. 新一輪 Proposer 在進入 Phase 2 前必須繼承在多數派回復中觀測到的最高編號已接受值，因此無法繞過歷史去提出相反的值。
4. 由于任意兩個多數派集合必有交集，任何已被多數接受過的值都會被后繼提案看見，從而被延續而非被覆蓋。
5. 于是，并發競爭所造成的只是不斷被更大編號打斷，表現為延遲變大/無進展（活性受損），但不會產生兩個不同的被選定值。
6. 在網絡分區或只觸達少數派的情況下，協議選擇不前進而不是各自決定，因此寧停不亂，安全不失。
7. 崩潰恢復后，Acceptor 通過持久化狀態繼續履行既有承諾，保證歷史不被遺忘，也就不可能因為重啟而“選出另一個值”。

什么是多數派（Quorum）

定義：在 N 個 Acceptor 中，每次需要一個法定集合同意才能推進；若法定集合大小取 > N/2，則任意兩個法定集合必有交集（至少一個共同成員）
意義：交集節點會把自己已接受過的最高編號值報告給后續 Proposer，使后者必須繼承歷史值，從而維持一致性。

任意兩個多數派集合必有交集，交集的作用是：
假設某個值 v 已經在多數派 A 被接受（chosen 的候選）
后續任何新 Proposer 都必須再從另一個多數派 B收集 Promise
因為 A ∩ B ≠ ?，所以至少有一個 Acceptor 會記得?v
新 Proposer 必須繼承這個歷史值 v（規則：繼承已接受的最高編號的值）
因此 Paxos 能保證一旦某個值可能被多數派選中，之后所有被選定的值都必須與它一致

為什么后續任何新 Proposer 都必須再從另一個多數派 B收集 Promise？

因為不知道歷史上的多數派是哪一組，為了保證能看見那段歷史，必須向多數派?B 收集Promise，這樣可保證?B 與多數派 A必有交集。
一旦兩組都是多數派，就有 A∩B≠?。交集里的某個 Acceptor 會把自己已接受的最高對 (n_a, v_a)?報告給Proposer ，Proposer 就被迫繼承該值，安全性因此成立。

5 句自然語言證明多數派交集不會選出兩個不同的值

1. 假設某值 v 已在一個法定集合 Q1內被多數 Acceptor 接受。
2.?之后任何新的 Proposer 想要繼續推進，必須從另一個法定集合 Q2收集承諾。
3.?因為法定集合都是多數，故 Q1? 與 Q2?必有交集，存在至少一個共同的 Acceptor。
4.?該交集 Acceptor 會按規則報告它已接受過的最高編號值，于是新 Proposer 必須繼承該值進入 Phase 2。
5.?因此，任何后來被選定的值都與 v 一致，不可能再選出與 v 不同的第二個值，故多數派交集不會選出兩個不同的值。

Paxos vs Raft 異同點

相同點
目標一致：都要實現崩潰容錯的復制狀態機
依賴條件：需要多數派可用，節點維護持久化元數據（承諾/日志/任期）才能保證崩潰恢復后 Safety。
結果保證：在部分同步網絡中，Safety 永遠成立，Liveness 在穩定時期成立。

不同點（工程視角）

可理解性
Paxos：抽象層次高，核心論文偏“數學證明”；需要額外補充選主、多槽位日志等細節才能變成可用系統。
Raft：設計目標就是易于理解。明確提出了 Leader-based 流程：任期、心跳、日志匹配、選主、成員變更。

日志與成員變更
Paxos：基本論文只解決單次決議，Multi-Paxos + 工程補丁才形成日志復制；成員變更沒有標準化方案。
Raft：把日志復制、任期切換、Joint Consensus（聯合共識的配置變更）都標準化為協議的一部分。

實現生態

工業界常見的 Multi-Paxos 實現 ≈ Leader 驅動復制，體驗上和 Raft 很像，但實現復雜度高。
Raft 的落地實現有完整生態；Paxos 系統更多是歷史遺產或大廠定制。

若從零做復制，為什么可能更偏向 Raft？
因為 Raft 在設計時就把 Leader 選舉、日志復制、任期、配置變更全部納入協議核心，流程直觀、易實現、社區支持豐富；對一個新項目來說，可以快速實現一個可維護的高可用系統。相比之下，Paxos 雖然理論完備，但要從論文到工程落地，還需要自己拼接 Multi-Paxos、Leader 選主、重配置等模塊，復雜度高。

若接手已有 Paxos 系統，我需要重點關注什么？
必須清楚它是基于 Multi-Paxos 的哪個變體（是否有穩定 Leader、是否支持批量/流水線）；明確 Acceptor 的持久化語義；確認系統是否已經實現了重配置機制（例如 Joint Consensus 或自研方案）；同時要評估其沖突處理和活性優化手段（退避、編號躍遷、Leader 心跳）。只有弄清這些工程化補丁，才能確保 Paxos 系統在實際環境里安全且有足夠活性。