關於Paxos "幽靈復現"問題看法

來自專欄資料庫前沿技術37 人贊了文章

由於郁白之前寫的關於Multi-Paxos 的文章流傳非常廣, 具體地址: http://oceanbase.org.cn/?p=111 原文提出了一個叫"幽靈復現" 的問題, 認為這個是一個很詭異的問題, 後續和很多人交流關於一致性協議的時候, 也經常會提起這個問題, 但是其實這個問題我認為就是常見的"第三態"問題加了一層包裝而已.

幽靈復現問題

來自郁白的博客:

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

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

1. 第一輪中A被選為Leader，寫下了1-10號日誌，其中1-5號日誌形成了多數派，並且已給客戶端應答，而對於6-10號日誌，客戶端超時未能得到應答。
2. 第二輪，A宕機，B被選為Leader，由於B和C的最大的logID都是5，因此B不會去重確認6-10號日誌，而是從6開始寫新的日誌，此時如果客戶端來查詢的話，是查詢不到6-10號日誌內容的，此後第二輪又寫入了6-20號日誌，但是只有6號和20號日誌在多數派上持久化成功。
3. 第三輪，A又被選為Leader，從多數派中可以得到最大logID為20，因此要將7-20號日誌執行重確認，其中就包括了A上的7-10號日誌，之後客戶端再來查詢的話，會發現上次查詢不到的7-10號日誌又像幽靈一樣重新出現了。

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

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

第三態問題

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

1. 成功
2. 失敗
3. 超時未知

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

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

1. 對於每一個請求都加上一個唯一的序列號的標識, 然後server的狀態機會記錄之前已經執行過序列號. 當一個請求超時的時候, 默認的client 的邏輯會重試這個邏輯, 在收到重試的邏輯以後, 由於server 的狀態機記錄了之前已經執行過的序列號信息, 因此不會再次執行這條指令, 而是直接返回給客戶端
2. 由於上述方法需要在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 的不同做法產生的. 關於一致性協議在不同階段的做法可以看這個文章 http://baotiao.github.io/2018/01/02/consensus-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 提交造成的幽靈復現的問題, 本質是沒有處理好這個第三態的請求.