背景

眾所周知, Multi-Paxos演算法可以在Proposer沒有被其他節點拒絕的情況下, 省略後續Paxos實例的prepare消息, 以此來提高系統的效率. 但是Multi-Paxos演算法本身沒有限制系統中只有一個Proposer可以發起提議. 所以, 如果系統中所有Proposer都可以隨意發起提議, 那麼Multi-Paxos演算法就會退化, 無法提高系統的效率.

所以我們需要選擇一個Proposer, 將所有的都交給它進行處理, 防止系統中有多個Proposer同時提議的情況發生. 這個特殊的節點我們稱之為Master[1].

另外, 我們系統中除了寫請求之外還有, 對於一些對一致性要求嚴格的應用, 它可能要求讀到最新的數據, 也即是需要能讀取到之前所有的更新數據. 如果我們保證所有都在Master上處理的話, 那麼從Master上讀取的數據應該也是最新的.

所以總結一下Paxos集群中Master的作用, 主要是兩點作用:

提高系統的效率

實現讀的一致性

但是如何正確的實現Master選舉機制呢, 這裡可以分解為兩個關鍵點:

多數派節點對當前誰擔任Master可以達成共識

集群中任意時刻至多只有一個Master節點

對於第1點, 可以基於Paxos演算法達成達成共識. 某個節點想成為Master需要發起一次Master選舉, 也即是運行一次Paxos, 提議內容可以簡單認為是"我要當Master", 當多數派節點接受這個提議後, 該節點就可以認為自己是Master了.

對於第2點, 可以通過常用的手段來保證系統中不會同時有兩個Master. 指得是Master的任期時間, 當Master還在任期內時, 其他節點不能再發起Master選舉.

那麼我們看看PhxPaxos是如何實現選舉和租約的.

PhxPaxos的Master實現

PhxPaxos基於Paxos演算法, 在狀態機層面實現了Master選舉的功能, 並且具有租約的特性. 應用開發者可以使用PhxPaxos很方便的實現多個節點間Master的選舉功能, 不再依賴額外的ZooKeeper集群.

選舉線程

PhxPaxos中有單獨的線程負責Master選舉的邏輯. 代碼如下所示:

選舉線程所做的事情很簡單, 在循環中不斷調用TryBeMaster()嘗試發起選舉/續約, 然後sleep一段時間. 如此反覆.

TryBeMaster()

TryBeMaster()方法負責發起Paxos提議.

但是在發起提議之前, 需要判斷當前節點能否發起提議, 如果當前系統中已經存在Master但是自己又不是Master角色, 那麼就不能發起提議.

如果確認當前沒有Master角色, 那麼可以調用Propose()方法[2]發起提議, 提議內容包含:

NodeID: 當前節點的NodeID.

MasterVersion: 當前節點保存的Master版本, 取值來自於上次集群選主成功時的InstanceID.

LeaseTime: 當前集群配置的租約時長.

其中MasterVersion的作用是用於樂觀鎖檢查.

想像這樣一種場景, 某個節點X和Master發生了網路分區, 所以該節點在Master租約到期後認為集群中還未有Master角色, 所以發起了Master選舉, 如果X提議失敗了還好, 萬一提議成功那麼節點X將會違背演算法的保證: 在Master的任期內不能有其他節點發起選舉(成功).

什麼情況下X的提議會失敗呢?

X和多數派節點的網路處於分區中.

或者是X進行propose的時候, 它的InstanceID還沒有追上集群最新的InstanceID, 導致提議失敗.

PhxPaxos對集群中的Paxos實例運行做了串列限制, 所以Proposer要想propose成功它必須已經追上集群最新的Paxos實例. 因為PhxPaxos的作者認為並發運行Paxos實例的並沒有太大的性能優勢, 而且並發運行還帶來了實現的複雜度(並發運行Paxos實例能否發揮性能優勢還是取決於狀態機能否並發apply). 其實通過batch優化後性能也不比並發差, 所以乾脆就拋棄了並發的特性.

什麼情況下X的提議會成功呢?

X進行propose的那一刻, 它的learner已經學習了集群中所有Paxos實例的提議結果.

注意Master選舉和learner學習是不同的線程, 所以Master選舉線程調用propose的時候, learner可能已經學習了集群所有的提議結果, 也可能沒有.

如果X提議成功了, 有什麼方法可以補救嗎? 答案就是讓狀態機檢查提議結果中的MasterVersion, 檢查通過才學習提議結果: 所有節點的狀態機檢查提議結果中的MasterVersion, 判斷是否和當前自身保存的MasterVersion一致, 如果發現不一致那麼直接忽略本次的提議結果.

注意是所有節點的狀態機, 包括節點X的. 像這種情況, X也會發現提議中的MasterVersion和learner學習完之後的MasterVersion不一致了.

LearnMaster()

我們接下來看看狀態機的處理邏輯. Paxos提議結束後, Master選舉狀態機的Execute()方法會被調用. Execute()方法的主要邏輯在於LearnMaster(), 後者的代碼如下所示:

當提議結束之後, LearnMaster()會被調用, 首先會進行上述的樂觀鎖的檢查.

檢查之後, 判斷是否自身成為Master, 是的話使用TryBeMaster()中計算的時刻作為租約失效時刻(記為T1).

如果是別人成為Master, 使用當前時刻+租約時長作為租約失效時刻(記為T2).

其中T1

如果非Master節點先認為租約失效, 那麼就無法保證在Master的任期內不能有其他節點發起選舉. 這是租約機制設計中的一個常識.

對提議結果學習之後, TryBeMaster()中便可以通過判斷Master的租約是否失效來判斷當前有沒有Master存在, 如果沒有才發起新的選舉提議.

總結

PhxPaxos的Master選舉模塊實現了以下兩點關鍵特性, 為應用開發者提供了很大的便利:

多數派節點對當前誰擔任Master可以達成共識

哪怕發生網路分區, 集群中任意時刻至多只有一個Master節點

而且PhxPaxos的Master選舉模塊是通過狀態機實現, 一定程度上讓Master選舉邏輯和Paxos演算法的解耦, 在設計和編碼實現上達到了比較優雅的效果.

參考

[1] Paxos made live

[2] PhxPaxos源碼分析之Paxos實現

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！