Paxos(Multi-Paxos)在工程實現中需要注意哪些問題？

一個工業級別的Paxos(Multi-Paxos)實現需要注意哪些影響正確性的問題和優化點？

寫過oceanbase第一版的基於multi-paxos的高可用模塊，強答一發，拋磚引玉，歡迎各位前輩拍磚。

multi-paxos在basic-paxos的模型基礎之上，增加了「連續遞增」value的元素；換言之，basic-paxos至始至終都是說單個value達成一致的過程，而multi-paxos說的是多個value達成一致，並且這些value還有個特點：value有id標記，而且id連續遞增。

用資料庫redo 日誌的模型來描述這個模型就是：資料庫不停寫入多個事務，每個事務insert一條記錄，每個insert都會在資料庫引擎內部產生一條redo日誌，這個redo日誌就是一個value，redo日誌會被順序標記遞增的log_id。

介紹完背景，現在可以來看看正確性和可優化的地方：

先說協議正確性容易被忽視的地方：

0. 有些值必須持久化存儲

這個似乎是廢話，需要持久化哪些值呢？prepare 記錄 ，accept記錄。。。

1.全局唯一的proposal_id

Basic-paxos要求proposal_id全局唯一（否則會有不一致風險），如何保證唯一呢， ip+本地時間戳是個可選方案；

2.prepare請求應該包含哪些信息？

multi-paxos的prepare請求，可以理解為basic-paxos對於一批value發送prepare請求，那這個「一批」具體如何設定呢，答案是[start_id, 無窮大)這個連續區間。Start_id指的是什麼呢？就是當前proposer 中value序列連續形成多數派的最大值，舉個栗子，比如本地形成多數派的是{123,5}，未形成多數派的是{4， 7}，那麼此時start_id就是3。

是否這一區間的每一個value都需要指定一個proposal_id呢？當然不是，共享一個相同的proposal_id，這裡是multi-paxos的關鍵。

3. acceptor 如何響應收到的一個prepare請求？

如何響應prepare請求，basic-paxos已經有詳細說明，不再贅述。現在只說multi-paoxs的情況下，acceptor響應的注意點。

acceptor收到prepare請求後，首先當然要比較proposal_id，通過檢查後，下面就是關鍵操作了。這個關鍵操作其實在basic-paxos中有清楚的說明，就是返回給存在的已經accepted的最大的proposal_id的value，如果不存在，則返回NULL。當有basic到multi後，返回結果則變為一個集合了。如果集合元素太多怎麼辦？此處有個優化手段是，acceptor返回一個max_log_id，此id的含義是本地存在的accept記錄的最大值。proposer拿到這個值後，就知道哪些value需要找acceptor去要，哪些可以自己隨便生成了。

下面說實現上的優化問題：

滑動窗口

Multi-paxos大部分應用場景就是數據流，既然是數據流傳輸，其實相關優化都可以在tcp滑動窗口上找到相應點，滑動窗口中存儲的就是value：

1.批量並發網路發送：proposal可以同時發送多個value的accept請求；

2.批量發送accept ack

3.proposal超時重推（push），acceptor超時拉取（pull）

已經從滑動窗口出去的value，是明確已經形成多數派不會被改寫的value；滑動窗口中的，可能是空洞或者還有可能被改寫的value，滑動窗口外是還未收到或者還未產生的value；

commit消息

另外一個重要的優化是commit 消息，當某個value確認形成多數派後，proposer可以發送commit消息給acceptor，便於acceptor將其清除出buff，並且加速此acceptor轉換到proposal並且能夠正常提供寫入的恢復時間。為什麼能加速呢？這要聯繫前面講的proposal 發送prepare請求的過程，proposal在發送prepare前，要獲取start_id，如果沒有commit消息，start_id的確定就非常困難了。

Group commit

這個不是multi-paxos特有的優化，但凡是傳輸速度有差異的介質轉換都有這個優化存在的空間，比如內存到磁碟（無論是機械還是SSD）。

基本原因是，磁碟的I/O ps是有上限的，機械盤200左右，SSD 幾千左右，比起內存和網路太低了。怎麼辦呢？把幾百幾千幾萬個value放在一個I/O buff裡面刷到磁碟去，I/Ops成倍提升。

成員組變更

成員組指的是本來acceptor是{A BC}，我想安全的變成{D EF},怎麼實現呢？raft給出了完美的實現方式，但multi-paxos在實現上不能照搬，有兩點需要注意：

1.成員變更的信息也是value序列中的一個，只不過內容比較特殊，描述的是成員組變更信息，簡稱做change_value。Change_value需要是一個barrier，就是說，change_value被accept之前，需要之前的value都accept，這個水很深，可以再開一個問題討論；

2.raft中成員變更是兩階段的，其實沒必要的，想實現一階段安全的成員變更，只需要限制變更成員的數量就可以，即{ABC}可以變為{ABD}，但不能變為{ADE}。連續變多次，就可以從{ABC}到{DEF}了。

請參考系列博客吧
[Paxos三部曲之一] 使用Basic-Paxos協議的日誌同步與恢復

[Paxos三部曲之二] 使用Multi-Paxos協議的日誌同步與恢復

[Paxos三部曲之三] Paxos成員組變更

架構師需要了解的Paxos原理、歷程及實戰

@張帥 已經答得挺全面了，我補充幾個點：

1. 謹記paxos協議，對空洞日誌的重確認，要用新的proposal id
2. 與raft不同，multi-paxos對選主沒有特別要求，誰當都可以，甚至可以外部指定，過一輪完整paxos就行
3. 使用multi-paxos的上層應用要支持亂序提交和亂序回放，否則難以發揮性能優勢
4. redolog本地是亂序存儲的，因此你可能需要配合一個的日誌內容索引文件，以提供方便的旁路日誌導出
5. 由於亂序確認的機制，網路層面在主備之間建立多條TCP鏈接更能發揮優勢
6. 主切換為備，仔細考慮回放起點和未決事務如何處理；同樣備切換為主時，也要仔細考慮重確認起點和未決事務
7. 儘管leader有效期內只需要accept過程即可，仍然要記得備機要嚴格按照P2b的約束進行檢查，避免不小心接受了上一任leader的消息；同樣的，主機也要有機制避免接受過期的備機應答消息