Why Raft never commits log entries from previous terms directly

02-02

熟悉Raft的讀者知道，Raft在子問題Safty中，限制不能簡單的通過收集大多數（Quorum）的方式提交之前term的entry。論文中也給出詳細的例子說明違反這條限制可能會破壞演算法的Machine Safety Property，即任何一個log位置只能有一個值被提交到狀態機。如下圖所示：

簡單的說，c過程中如果S1簡單的通過判斷大多數節點在index為2的位置的AppendEntry成功來commit值2，那麼後續S5成為Leader後，由於自己的值3擁有比2更大的term，導致用值3將已經commit的2覆蓋。因此Raft限制只能通過判斷大多數的方式提交當前term的entry，進而對之前的entry間接提交，如過程e所示。

Raft never commits log entries from previous terms by counting replicas. Only log entries from the leader』s current term are committed by counting replicas; once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property.

那麼導致這種問題的根本原因是什麼？以及為什麼增加這個限制後就可以解決問題呢？Raft本質上是一種(multi-)Paxos，可以認為是對Paxos加了限制而得到的更簡單易懂的一致性演算法，因此本文嘗試從Paxos出發來回答上面的兩個問題。

Paxos

作為一致性協議，Paxos需要作出Liveness和Safty兩方面的保證，簡單的說：

Liveness：最終一定有value被chosen
Safty：只有一個value最終被chosen，且這個value一定是之前被propose過的

為了保證Liveness，Paxos要求每個acceptor必須接受收到的第一個value：

P1. An acceptor must accept the first proposal that it receives.

同時，單個Paxos實例允許不止一個propose最終被chosen，但要求所有被chosen的propose必須有相同的值，從而也保證了Safty。

P2. If a proposal with value v is chosen, then every higher-numbered pro- posal that is chosen has value v.

演算法細節上，Paxos要求每個propose需要通過第一階段的Propose及Promise過程在得到大多數節點對自己propose num認可的同時，也獲得可能存在的之前的最大propose num發起的value，並且用自己的更大的propose num對相同的value進行第二階段的重新提交。這一步非常關鍵，試想這樣一種場景，一個擁有三個acceptor的Paxos集群中，三個acceptor，a1、a2、a3可能會由於接收到消息的順序分別接受不同propose的不同value：

a1: (v1, pn=1)na2: (v2, pn=2)na3: (v3, pn=3) n

此時a3宕掉，新的proposer p4選取新的pn=4，嘗試讓集群達成一致，由於a3無法響應，p4從a1，a2獲得當前最大pn的值為(v2, pn=2)，假設p4沒有用自己的pn提交並最終Commit，則會出現：

a1: (v2, pn=2)na2: (v2, pn=2)na3: (v3, pn=3) down n

若此時a3恢復，便可能被新的proposer p5因讀取到集群最大pn的值為(v3, pn=3)而將之前p4的提交覆蓋，損害一致性。因此Paxos要求p4用自己的pn重新提交v2：

a1: (v2, pn=4)na2: (v2, pn=4)na3: (v3, pn=3) down n

Paxos to Multi-paxos

Paxos演算法分為兩個階段，第一個階段中節點通過Propose及Promise過程得到大多數節點對自己propose num的認可；之後在第二個階段中通過Accept請求廣播自己的提案值，並且在收到大多數的Ack後進行Commit。那麼當我們面對一連串提案而不是一個單獨的提案的Multi-Paxos時，很自然的優化就是選擇一個Coordinator，由這個Coordinator來發起所有提案的階段二，從而將Paxos階段一中的Propose及Promise過程省略。相當於每一次Propose及Promise的結果都是這個Coordinator獲勝。

由於所有的value都是由這個Coordinator發起的，是不是就不存在上面說到的不同propose提交同一個值了呢？不是的，只是這種情況被減少到了重新選擇Coordinator後的Recovery過程，可以看出每個階段的Coordinator都相當於上述Paxos的一個Proposer，因而新的Coordinator可能會發現之前的Coordinator發起的值，但其無法判斷這個值是不是已經被Commit，因為舊的Coordinator可能是在本地Commit並返回Client之後，通知其他節點Commit之前的空隙宕掉的。因此新的Coordinator安全的做法就是用自己的propose num重新發起並嘗試提交這個value。對於切主後需要Reovery的位置需要一個完整的Paxos階段一、階段二過程。這個過程中同樣要求Coordinator用自己的propose num對已有的value進行重新提交。

Multi-paxos to Raft

可以看出，Raft就是很典型的採取了這種有Coordinator模式的Multi-paxos。Coordinator在Raft中稱為Leader，propose num稱為term。自然地，Raft中新Leader也會發現舊Leader留下的log entry。因此正確的做法是新Leader用自己的term重新對這個entry進行提交，但由於Log的限制，新Leader沒有辦法修改這個entry中記錄的term，而任由這個entry存在而不修改卻將其提交也是不行的，因為entry中過時的term可能會導致未來被其實比當前新Leader小的term的值覆蓋，也就是文章開頭提到的錯誤。

Raft隱含Term提升

通過上面的追本溯源，我們知道造成這個問題的原因是，log entry中的term無法顯式地修改而使得後來的Leader無法得知可能已經被Commit的entry提交時所用的term，從而沒有辦法以此來作出後續的決策。Raft採用了一種很巧妙的辦法來隱含的標定這條entry的term，這就是在log的末尾追加一條記錄當前term的log entry，並嘗試提交這個entry。Raft選新主時需要比較日誌的新舊，最後一個entry的term大小優先於日誌長度：

Raft determines which of two logs is more up-to-date by comparing the index and term of the last entries in the logs. If the logs have last entries with different terms, then the log with the later term is more up-to-date. If the logs end with the same term, then whichever log is longer is more up-to-date.

這就相當於給了日誌中的所有entry一個隱含的term，這個term等於最後一條entry的term。從而完美的解決了文章開始提到的問題。

回顧總結

單個Paxos實例為了保證Safty，要求發現已有值時，需要用自己的propose num重新對這個值進行提交。
Multi-paxos重新選主後，新的Coordinator需要用自己的propose num對需要Recovery的位置進行重新提交。
Raft無法重置log entry中的term。
Raft通過增加新的記錄當前term的entry，來隱含地提升之前所有log的term，從而解決了文章開頭提出的問題。

參考

Paxos made simple

Paxos Made Live - An Engineering Perspective

In Search of an Understandable Consensus Algorithm

Zab: High-performance broadcast for primary-backup systems

談談paxos, multi-paxos, raft

Raft和它的三個子問題 | CatKang的博客