天天看點
傳回

從PhxPaxos中再看Paxos協定 一、預備操作 二、附帶phxelection選主例程解析

從PhxPaxos中再看Paxos協定

　　本文就是通過Phxpaxos中所附帶的簡單例子，摸索了解Phxpaxos中對Paxos算法的實作，算是驗證一下前面對Paxos算法的學習吧。當然之前也說過，Phxpaxos同Lamport老爺爺的原版Multi-Paxos相比已經修改了很多，畢竟老爺爺的文章比較的偏理論化，是以理論上不修改的Multi-Paxos是不可能滿足線上分布式系統的可用性和可靠性需求的，具體對于遇到的修改再行另表吧。

一、預備操作

　　預設情況下Phxpaxos的存儲子產品使用的是glog，但不知道怎麼回事，在我MacOS下VMware Fusion虛拟機Ubuntu-1604的環境下，嚴格按照《編譯安裝手冊》還是會報無法建立log檔案的錯誤，不知道是不是因為目錄使用NFS挂載的原因，此處也不詳究了。其實Phxpaxos的實作中，很多地方都有詳細的且分好等級的日志資訊，檢視代碼發現隻要設定了pLogFunc函數指針，就可以在所有log記錄之前執行這個hook函數，于是乎可以在sample中設定這個option，那麼整個系統的運作路徑和運作狀态也就一覽無餘了。

1
       
       
        2
       
       
        3
       
       
        4
       
       
        5
       
       
        6
       
       
        7
             
#include <stdarg.h>
       
       
        void custLog(const int iLogLevel, const char * pcFormat, va_list args) {
       
           
        char sBuf[
        1024] = {
        0};
       
       
            vsnprintf(sBuf, 
        sizeof(sBuf), pcFormat, args);
       
           
        std::
        cerr << sBuf << 
        std::
        endl;
       
       
        }
       
       
        oOptions.pLogFunc = custLog;

　　Phxpaxos的代碼雖然是多，但是當除掉存儲子產品、網絡子產品、CheckPoint子產品、Benchmark和單元測試等部分代碼後，核心代碼其實也是十分有限的，而且和Paxos算法相關的部分都單獨放在algorithm目錄中了，檢視這個檔案夾中的檔案名，赫然醒目的acceptor、proposer、learner、instance，就讓我們估計道知道他們是什麼角色履行的職責了。

二、附帶phxelection選主例程解析

　　Phxpaxos附帶的兩個sample詳細建構過程都在《README》中描述清楚了，本來是想phxelection和phxecho兩個例子都一起跟蹤的，但是後面看着看着發現，phxelection流程走完基本就定型了，phxecho和前者的差異主要就是傳遞了自定義的StateMachine，是以在Paxos算法Chosen Value之後，會額外的執行客戶提供的狀态機轉移函數Execute()，這其實和phxelection在原理上沒有本質的差異，因為後者算是對于選主的特殊情況，預先定義了MasterStateMachine狀态機而已。

2.1 Phxpaxos中的Master Node

　　在Phxpaxos的設計中弱化了Multi-Paxos中提到的Leader角色，而是使用了Master的概念，在後面PhxSQL項目的文檔中也強調了：Master是唯一具有外部寫權限的Node，是以可以保證這個Node的資料肯定是最新的副本，Client的所有寫請求和強一緻性的讀請求都需要直接或者由其他Node代理轉發到這個Master Node上面，而對資料一緻性要求不高的普通讀請求，其讀請求才可以在非Master Node上面執行。

　　由此可見，在穩定的情況下Master Node起到了單點協調者的作用。但是當系統新啟動，或者在Master Node挂掉的時候，就需要有一個選主的操作。《Paxos理論介紹(3): Master選舉》已經将選主的原理詳細說明了。概而言之，就是在沒有Master的時候，大家都可以認為自己是Master并發出TryBeMaster請求，這就等于大家實作一個Basic-Paxos的流程，根據Paxos的算法原理可以保證，最後隻有唯一一個節點的提案被Chosen，這時候被Chosen提案的Proposer就被選為Master Node。在系統運作的過程中，各個節點會事先約定一個租賃周期，在這個周期到達之前Master Node可以提起續約的請求，其他節點當發現約定的檢查周期到達之後并且Master租賃有效期間之前還能夠請求到Master Node，就表示Master Node續約成功，此時就不再發起TryBeMaster的請求。這樣在穩定的情況下Master Node可以一直穩定的運作下去，而當Master Node異常或者普通Node和Master Node通信失常情況下的處理方式，會在後文中作進一步的解釋。

2.2 phxelection選主的實作流程

　　Phxpaxos中的兩個項目預設是使用的三個節點來實驗的，根據Paxos中Majority的需求，其節點數至少是三個，而且盡可能的是奇數數目。每一個運作的程序對外被抽象成Node節點，在内部使用帶序列号的Instance作為執行單元，且每個Instance内部都含有完整的Acceptor、Proposer、Leader的角色，而且同一個Instance中的三個角色是存在于同一個程序中的，互相之間的結果是立即可見的。

2.2.1 Node初始化操作

　　Phxelection曆程啟動很簡單，當代碼建立PhxElection對象oElection後，直接調用其成員函數PhxElection::RunPaxos()啟動。在這個成員函數中，可以設定相關參數oOptions(注意這個選項很大，而且後續會深入透傳到整個Phxpaxos内部)，這個sample中，最主要的是要打開選主開關bIsUseMaster，然後調用Node::RunNode()，也隻在這個函數中才進行PNode實體的建立和初始化工作，并将得到對象的位址儲存傳回給poNode指針，這樣使用者程式也可以操作Node(而非PNode)規定的其他可用接口來通路或操作底層對象了。

　　PNode對象的建立采用典型的兩段式構造，當然下面很多對象都是兩段式構造，主要工作在PNode::Init()中實作，這個初始化涉及的内容比較的多，幾乎貫穿了整個系統的啟動過程：

　　(1). InitLogStorage: 好像底層是基于啥LevelDB搞的吧，先不管它了；

　　(2). InitNetWork: 預設的網絡配置是根據指令行參數解析到的節點網絡資訊IP:Port，對于UDP協定建立接收套接字和一個發送套接字，對于TCP則是通常的bind-listen服務端初始化。TCP類型的初始化工作，還包括使用epoll_create建立異步事件偵聽，同時建立封裝了pipe匿名管道的Notify對象用于對接收到的消息進行傳遞，并設定管道NONBLOCK且将管道的讀端添加EPOLLIN事件偵聽；設定成員變量poNetWork；

　　(3). MasterList: 由于我們隻用到一個Group，是以隻建立一個MasterDamon對象，可見預設的Master Lease是10s，可以通過SetLeaseTime自由自定義設定這個租賃周期但是必須大于1s；同時還要建立一個MasterStateMachine對象，首先嘗試從之前儲存的資料加載曆史資訊，如果讀取失敗進行預設初始化，同時設定version的值為(uint64_t)-1；

　　(4). Group: 和上面一樣也隻有一個，主要把上面已經初始化的資訊儲存到這個容器裡面；這個裡面，讓我們最感興趣的是建立了一個Instance類型的m_oInstance對象，大概看了一下Instance類的聲明就讓人感到十分興奮，因為大部分的消息回調OnRecieveXXX都在這個類的聲明裡面，同時還包含了Acceptor、Proposer、Learner成員，表明我們離Paxos已經是很接近了；

　　(5). ProposeBatch: 批量送出，算是Phxpaxos相比Multi-Paxos的一個新操作，待到我後面研究到這個深度的時候再深入；

　　(6). InitStateMachine: 參數隻有一個——Options，一個超大巨形體參數，但是在這個sample中我們并沒有建立StateMachine，是以這裡的AddStateMachine啥也沒做，當然對于另外一個Phxecho需要使用使用者定義的StateMachine，此處就會進行添加；然後當我們開啟了選主的功能後，各個Node都會啟動運作RunMaster()，這個操作會建立一個線程運作MasterDamon::run()，這個線程就是Master Node選取和維護的主要實作部分，此處跳過，後面會單獨展開詳述；

　　(7). Group Init: 将啟動時候添加的所有Node清單資訊添加到SystemVSM中，同時添加GetSystemVSM()、GetMasterSM()兩個StateMachine。其實看到這裡，讓人感覺到StateMachine實際等價于某個帶狀态的函數，當所謂的StateMachine發生轉移的時候，實際就是其對應的函數被執行。然後執行Instance::Init()，由于Instance的初始化有較多操作，且是跟Paxos密切相關的，下面單獨展開介紹。

2.2.2 Instance初始化操作

　　在Instance初始化的過程中，主要是對Paxos中的幾個角色的初始化，其角色大多都是繼承自Thread類，是以意味着各自以線程的方式獨立運作。我們主要關心的角色有：

　　(1). Learner

　　最終映射成LearnerSender::run()線程，做的事情就是：等待條件變量m_bIsComfirmed被設定，然後調用SendLearnedValue(m_llBeginInstanceID, m_iSendToNodeID);從llBeginInstanceID開始一直發送到目前的m_llInstanceID。對在每一個instance發送的過程中，都需要從log中查取這個instance的相關資訊(比如提案節點、提案号、Chosen Value等)後打包發送，具體的資訊請參看Learner::SendLearnValue()中的打包過程，然後可以選擇之前在Node初始化中網絡部分的TCP還是UDP方式發送，具體任務交由網絡子產品負責了。

　　Learner會等待記錄ACK資訊，目前被确認的ID儲存在m_llAckInstanceID變量中，确認逾時後錯誤傳回，錯誤時候記錄目前已經發送的llSendInstanceID變量不被更新。

　　(2). Acceptor

　　初始化較為的簡單，因為我們沒有曆史記錄，是以加載資料發現為空，就将m_llInstanceID設定為0就可以了；

　　(3). CheckpointMgr

　　這個暫時也不展開說了。作為一個狀态機如果要重新加載狀态，最直覺的就是從最開始零狀态一直進行曆史記錄回放，但是這種方式效率低，而且随着狀态機的運作記錄所有的曆史資訊也是不現實的，是以為了增加效能實作的CheckPoint功能就是将曆史記錄某個時間點的狀态做完整快照，加載狀态可以從那個CheckPoint開始重放到目前日志記錄的狀态(這個過程叫做CatchUp)，具體的資訊可以檢視《狀态機Checkpoint詳解》。

　　本sample都是從頭開始的，這些東西基本都是0狀态的。

　　(4). IOLoop

　　這也是開辟一個線程，主要是在一個消息隊列m_oMessageQueue中不斷的完成取出消息和處理消息(主要就是通過一個帶互斥鎖、條件變量封裝的std::deque，騰訊說好的無鎖隊列呢？)的工作，正常情況下會取出消息，然後發配到OnReceive(*psMessage)處理，而OnReceive的處理流程會對資料包拆包檢查，然後根據消息類型分别發配給Learner、Acceptor、Proposer對應角色去處理，消息的類型定義在了comm\commdef.h的enum PaxosMsgType中，看上去Proposer和Acceptor比較明确，而Learner處理的消息比較多啊。

　　通過把這個OnReceive的處理大概逛了一下，基本就是标準的Paxos協定的内容了，比如Proposer接收到Acceptor的表決資訊後，會先調用m_oMsgCounter.AddReceive()，然後檢查m_oMsgCounter.IsPassedOnThisRound()看看是不是已經滿足超過半數決議了，如果是就進行接下來的例程Accept()或者向Learner廣播消息ProposerSendSuccess()，而如果投票失敗(否決票過多或者逾時)則等待幾十毫秒後重新發起Prepare請求。

　　上面提及的隻是消費消息，消息的生産者在哪裡呢？之前說道PNode在初始化網絡層的時候有過TCP和UDP兩種通信方式，TCP通過使用event異步事件，而UDP在一個線程中不斷的接收消息，這些管道接收到的資訊，最後都會放到這個隊列中去的。

　　此外Instance還保留了一個m_oRetryQueue重試隊列，用于處理Paxos相關消息，具體什麼原理暫時不詳。

　　上面的這些線程的循環，都在m_bIsEnd=true的時候會退出來，在IOLoop::Stop()會設定這個變量，檢索後在Instance對象被析構的時候會調用之。

2.2.3 MasterDamon主線程工作

　　根據上面說到的選主原理，這個線程的工作内容也十分簡單，實質的工作内容就是TryBeMaster()：首先在Master Node穩定正常的情況下自身會自動續約，那麼在m_llAbsExpireTime之前就會傳回m_iMasterNodeID和版本号，否則傳回nullnode；當Node發現傳回nullnode的時候，無論是Master Node的原因還是自己和其通信的原因，都會發起一個包含llMasterVersion資訊的Proposer請求，那麼：

　　(1). 系統剛開始的時候，所有的Node都認為自己是Master Node，然後發起Propose()請求，經過Basic-Paxos的正常流程，會最終有一個Node被Chosen，由于大家都在同一個Instance中，被Chosen Value所對應同一程序中的Learner已經知道Chosen Value了(多線程共享變量)，然後就會發送ProposerSendSuccess()廣播給所有的Learner，大家接收到之後通過OnProposerSendSuccess()進行學習，并設定m_bIsLearned=true狀态；Learner的後續執行流程檢查到這個狀态後，就會執行狀态機MasterStateMachine狀态轉移Execute()即LearnMaster()，設定所有節點的m_iMasterNodeID為被Chosen Value的節點。系統啟動Master Node新選取成功時候，m_llAbsExpireTime的值為0，而後面續約的時候更新為提起Propose時刻+Master租賃時長-100ms長度，自此選主成功。

　　(2). 所有節點都會在Lease Timer之前發起(但不一定會實質執行)TryBeMaster()，為了減少異常情況下通過Basic-Paxos新選取Master時候可能的“活鎖”沖突，大家發起Prepare的時間點會有個微小的elf差異，當發現Master Node在逾時時間之前仍然有效的時候，非Master節點都直接傳回而不執行BeMaster()，Master節點會發起一個續約的正常Propose請求，最終狀态機轉移的時候更新時間等資訊，然後所有節點學習重新調整即可；

　　(3). 當Master Node本身挂掉的時候，大家都會發起Propose請求，那麼此時就退化成初始狀态多個Node采用Basic-Paxos的方法選主的情況了；

　　(4). 當某個非Master Node因為通信或者其他的原因，錯誤的發起了BeMaster()的時候，wiki也說了這裡是個“樂觀鎖”的解決方案：這個節點将自己觀測到的最大version打包到Propose參數裡面去，後續通過正常的Paxos流程會被Chosen，待到最後執行狀态轉移LearnMaster()的時候，會解包對參數進行校驗，發現請求的version版本和目前最新版本不符，那麼放棄這次狀态機的實質切換操作而直接傳回了。我們樂觀的預估，此時改節點和系統的通信正常了，在真正的MasterNode下次續約的時候，改節點将會正确學習到Master Node的資訊并正常工作。

轉載于:  https://taozj.org/2016/11/%E5%88%86%E5%B8%83%E5%BC%8F%E7%B3%BB%E7%BB%9F%E5%85%A5%E9%97%A8%E7%AC%94%E8%AE%B0%EF%BC%88%E4%B8%89%EF%BC%89%EF%BC%9A%E4%BB%8EPhxPaxos%E4%B8%AD%E5%86%8D%E7%9C%8BPaxos%E5%8D%8F%E8%AE%AE/

分布式一緻性
上一篇: TiKV架構解析
下一篇: PBFT（拜占庭容錯)

繼續閱讀