Paxos 演算法

引言：希臘議會

20 世紀 80 年代，萊斯利·蘭波特 (Leslie Lamport) 構思了一個發生在希臘 Paxos 小島上的虛擬立法系統。那裡的立法者（節點）經常缺席或表現得反覆無常，但她們仍需通過法律（達成共識）。

Paxos 是第一個在數學上被證明能解決不可靠網路中「共識問題」的方案。她以極難理解而著稱，但她卻是幾乎所有現代分散式系統（如 Google 的 Spanner）賴以生存的根基。

演算法要解決什麼問題？

• 輸入： 多個節點提議不同的值。
• 輸出： 所有節點對 單個 值達成一致。
• 承諾： 安全性 (Safety，只有被提議的值才會被選中) 和 活性 (Liveness，最終一定會有一個值才會被選中)。

核心思想 (直覺版)

Paxos 透過 三階段協定 執行：

1. 準備 (Prepare)： 提議者發送一個帶有唯一編號 ($N$) 的提議給大多數接受者。
2. 承諾 (Promise)： 如果編號 $N$ 是接受者見過的最高的，她就承諾永遠不再接受編號更低的提議。
3. 接受 (Accept)： 一旦提議者收到了足夠多的承諾，她就請求接受者正式「接受」這個值。

這就像一場 拍賣會：除非你的競價編號比別人都高，否則你無法獲勝；而一旦大多數人點頭，這筆交易就成交了。

如何運作 (Multi-Paxos)

原始的 Paxos 只能決定 一個 值。為了構建現實中的系統（如資料庫），我們使用 Multi-Paxos：

• 節點們先選出一個「領導者」（提議者）。
• 之後，領導者可以跳過後續值的「準備」階段，使其執行速度與 Raft 相當。

典型業務場景

• ✅ 高端分散式儲存： Google 的 Chubby 和 Spanner 是 Paxos 最著名的實現。

• ✅ 資料庫核心： Microsoft SQL Server 和 Oracle 的內部複製機制使用了 Paxos 變體。

• ✅ 協定的標竿： 如果你正在設計一個新的分散式協定，你必須證明她是「Paxos 等價的」。

• ❌ 開發者自行實現： 除非你是分散式系統研究員，否則 永遠不要 嘗試為生產環境從零實現 Paxos。請使用 Raft 或成熟的組件如 Zookeeper。

性能與複雜度總結

• 複雜度： 極高。「世界上只有一種共識演算法，那就是 Paxos。其他所有的一致性演算法都是 Paxos 的特例。」
• 效率： 在 Multi-Paxos 形式下，效率與 Raft 類似。

小結：一句話記住它

「Paxos 是分散式系統的『教父』。她提供了共識可能的數學證明，儘管可能需要一個博士學位才能解釋清楚她到底是怎麼運作的。」