由于郁白之前寫的關于Multi-Paxos 的文章流傳非常廣, 原文提出了一個叫"幽靈復現" 的問題, 認為這個是一個很詭異的問題, 后續和很多人交流關于一致性協議的時候, 也經常會提起這個問題, 但是其實這個問題我認為就是常見的"第三態"問題加了一層包裝而已.

幽靈復現問題

來自郁白的博客:

使用Paxos協議處理日志的備份與恢復，可以保證確認形成多數派的日志不丟失，但是無法避免一種被稱為“幽靈復現”的現象，如下圖所示：

?LeaderABC

第一輪	A	1-10	1-5	1-5
第二輪	B	宕機	1-6,20	1-6,20
第三輪	A	1-20	1-20	1-20

第一輪中A被選為Leader，寫下了1-10號日志，其中1-5號日志形成了多數派，并且已給客戶端應答，而對于6-10號日志，客戶端超時未能得到應答。

第二輪，A宕機，B被選為Leader，由于B和C的最大的logID都是5，因此B不會去重確認6-10號日志，而是從6開始寫新的日志，此時如果客戶端來查詢的話，是查詢不到6-10號日志內容的，此后第二輪又寫入了6-20號日志，但是只有6號和20號日志在多數派上持久化成功。

第三輪，A又被選為Leader，從多數派中可以得到最大logID為20，因此要將7-20號日志執行重確認，其中就包括了A上的7-10號日志，之后客戶端再來查詢的話，會發現上次查詢不到的7-10號日志又像幽靈一樣重新出現了。

對于將Paxos協議應用在數據庫日志同步場景的情況，幽靈復現問題是不可接受，一個簡單的例子就是轉賬場景，用戶轉賬時如果返回結果超時，那么往往會查詢一下轉賬是否成功，來決定是否重試一下。如果第一次查詢轉賬結果時，發現未生效而重試，而轉賬事務日志作為幽靈復現日志重新出現的話，就造成了用戶重復轉賬。

為了處理“幽靈復現”問題，我們在每條日志的內容中保存一個generateID，leader在生成這條日志時以當前的leader ProposalID作為generateID。按logID順序回放日志時，因為leader在開始服務之前一定會寫一條StartWorking日志，所以如果出現generateID相對前一條日志變小的情況，說明這是一條“幽靈復現”日志（它的generateID會小于StartWorking日志），要忽略掉這條日志。

第三態問題

第三態問題也是我們之前經常講的問題, 其實在網絡系統里面, 對于一個請求都有三種返回結果

成功

失敗

超時未知

前面兩種狀態由于服務端都有明確的返回結果, 所以非常好處理, 但是如果是第三種狀態的返回, 由于是超時狀態, 所以服務端可能對于這個命令是請求是執行成功, 也有可能是執行失敗的, 所以如果這個請求是一個寫入操作, 那么下一次的讀取請求可能讀到這個結果, 也可能讀到的結果是空的

就像在 raft phd 那個論文里面說的, 這個問題其實是和 raft/multi-paxos 協議無關的內容, 只要在分布式系統里面都會存在這個問題, 所以大部分的解決方法是兩個

對于每一個請求都加上一個唯一的序列號的標識, 然后server的狀態機會記錄之前已經執行過序列號. 當一個請求超時的時候, 默認的client 的邏輯會重試這個邏輯, 在收到重試的邏輯以后, 由于server 的狀態機記錄了之前已經執行過的序列號信息, 因此不會再次執行這條指令, 而是直接返回給客戶端

由于上述方法需要在server 端維護序列號的信息, 這個序列號是隨著請求的多少遞增的, 大小可想而知(當然也可以做一些只維護最近的多少條序列號個數的優化). 常見的工程實現是讓client 的操作是冪等的, 直接重試即可, 比如floyd 里面的具體實現

那么對應于raft 中的第三態問題是, 當最后log Index 為4 的請求超時的時候, 狀態機中出現的兩種場景都是可能的

所以下一次讀取的時候有可能讀到log Index 4 的內容, 也有可能讀不到, 所以如果在發生了超時請求以后, 默認client 需要進行重試直到這個操作成功以后, 接下來才可以保證讀到的寫入結果. 這也是工程實現里面常見的做法

對應于幽靈問題, 其實是由于6-10 的操作產生了超時操作, 由于產生了超時操作以后, client 并沒有對這些操作進行確認, 而是接下來去讀取這個結果, 那么讀取不到這個里面的內容, 由于后續的寫入和切主操作有重新能夠讀取到這個6-10 的內容了, 造成了幽靈復現, 導致這個問題的原因還是因為沒有進行對超時操作的重確認.

回到幽靈復現問題

那么Raft 有沒有可能出現這個幽靈復現問題呢?

其實在早期Raft 沒有引入新的Leader 需要寫入一個包含自己的空的Entry 的時候也一樣會出現這個問題

Log Index 4,5 客戶端超時未給用戶返回, 存在以下日志場景

然后 (a) 節點宕機, 這個時候client 是查詢不到 Log entry 4, 5 里面的內容

在(b)或(c) 成為Leader 期間, 沒有寫入任何內容, 然后(a) 又恢復, 并且又重新選主, 那么就存在一下日志, 這個時候client 再查詢就查詢到Log entry 4,5 里面的內容了

那么Raft 里面加入了新Leader 必須寫入一條當前Term 的Log Entry 就可以解決這個問題, 其實和之前郁白提到的寫入一個StartWorking 日志是一樣的做法, 由于(b), (c) 有一個Term 3的日志, 就算(a) 節點恢復過來, 也無法成了Leader, 那么后續的讀也就不會讀到Log Entry 4, 5 里面的內容

那么這個問題的本質是什么呢?

其實這個問題的本質是對于一致性協議在recovery 的不同做法產生的.?

也就是說對于一個在多副本里面未達成一致的Log entry, 在Recovery 需要如何處理這一部分未達成一致的log entry.

對于這一部分log entry 其實可以是提交, 也可以是不提交, 因為會產生這樣的log entry, 一定是之前對于這個client 的請求超時返回了.

常見的Multi-Paxos 在對這一部分日志進行重確認的時候, 默認是將這部分的內容提交的, 也就是通過重確認的過程默認去提交這些內容

而Raft 的實現是默認對這部分的內容是不提交的, 也就是增加了一個當前Term 的空的Entry, 來把之前leader 多余的log 默認不提交了, 幽靈復現里面其實也是通過增加一個空的當前Leader 的Proposal ID 來把之前的Log Entry 默認不提交

所以這個問題只是對于返回超時, 未達成一致的Log entry 的不同的處理方法造成的.

在默認去提交這些日志的場景, 在寫入超時以后讀取不到內容, 但是通過recovery 以后又能夠讀取到這個內容, 就產生了幽靈復現的問題

但是其實之所以會出現幽靈復現的問題是因為在有了一個超時的第三態的請求以后, 在沒有處理好這個第三態請求之前, 出現成功和失敗都是有可能的.

所以本質是在Multi-Paxos 實現中, 在recovery 階段, 將未達成一致的Log entry 提交造成的幽靈復現的問題, 本質是沒有處理好這個第三態的請求.

?

一站式開發者服務，海量學習資源0元起！
阿里熱門開源項目、機器學習干貨、開發者課程/工具、小微項目、移動研發等海量資源；更有開發者福利Kindle、技術圖書幸運抽獎，100%中--》https://www.aliyun.com/acts/product-section-2019/developer?utm_content=g_1000047140

原文鏈接
本文為云棲社區原創內容，未經允許不得轉載。

總結

以上是生活随笔為你收集整理的关于Paxos 幽灵复现问题的看法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。