理解分布式一致性:Paxos協議之Generalized Paxos & Byzantine Paxos

• Generalized Paxos
• Byzantine Paxos
• • Byzantine Multi-Paxos
  • Fast Byzantine Multi-Paxos

在前面一篇文章我們講到了理解分布式一致性:Paxos協議之Cheap Paxos & Fast Paxos，本篇文章我會講解Paxos協議的另外兩個變種：Generalized Paxos和Byzantine Paxos。

Generalized Paxos

我們大家都知道，分布式一致性的最大問題就是數據同步的問題，而產生問題的原因就是沖突，按照之前講到的各種Paxos協議方案，發生了沖突之后就必須解決沖突然后重新發送請求，這樣就會提高數據同步的成本和時間，那么有沒有更好的方式來解決這個問題呢？

答案肯定是有。在分布式系統中，沖突是不可避免的，遇到沖突的時候是不是每次都解決沖突然后重新發送請求呢？我們舉個例子：

如果Client1發送請求ReadA，Client2 發送請求ReadB，系統4個Acceptors，有2個接收ReadA，有2個接收ReadB，在共識層面來說，因為沒有達到最大的共識個數，達不成共識，需要重新發送。但是如果我們仔細觀察一下兩個請求，ReadA，ReadB這兩個命令是沒有任何聯系的，無論先執行哪一個都是同樣的效果。那么我們可以認為這種情況是沒有沖突的，我們在執行層面自行安排兩個請求的順序，而不用再次共識。 這就叫做Generalized Paxos。

這種共識的前提就是不同命令的先后順序無關。下面以序列圖的形式更加詳細的介紹：

Client1Client2LeaderAcceptor1Acceptor2Acceptor3LearnerAccept!(ReadA)Accept!(ReadA)Accept!(ReadA)Accept!(ReadA)Accept!(ReadB)Accept!(ReadB)Accept!(ReadB)Accept!(ReadB)Leader and Acceptor1Accepted(N,<ReadA,ReadB>), Acceptor2and Acceptor3Accepted(N,<ReadB,ReadA>),順序無關，不沖突，最終值Accepted(N,<ReadA,ReadB>)Accepted(N,<ReadA,ReadB>)Accepted(N,<ReadA,ReadB>)Accepted(N,<ReadA,ReadB>)Accepted(N,<ReadA,ReadB>)下面是沖突的情況，WriteA和ReadA同時發生，產生沖突時，Leader自行解決沖突，需要重發請求Accept!(ReadA)Accept!(ReadA)Accept!(ReadA)Accept!(ReadA)Accept!(WriteA)Accept!(WriteA)Accept!(WriteA)Accept!(WriteA)Accepted(N,<ReadA,WriteA>)Accepted(N,<ReadA,WriteA>)Accepted(N,<WriteA,ReadA>)Accepted(N,<WriteA,ReadA>)沖突產生，Leader根據協議自行決定執行順序，這里是<ReadA,WriteA>，N+1Accept!(N+1,<ReadA,WriteA>)Accept!(N+1,<ReadA,WriteA>)Accept!(N+1,<ReadA,WriteA>)Accepted(N+1,<ReadA,WriteA>)Accepted(N+1,<ReadA,WriteA>)Accepted(N+1,<ReadA,WriteA>)Client1Client2LeaderAcceptor1Acceptor2Acceptor3Learner

Byzantine Paxos

最后一個我們要講的Paxos協議是Byzantine Paxos。熟悉虛擬貨幣的人應該對拜占庭協議并不陌生，這里我們也不多講拜占庭協議，后面我會用單獨的文章來詳細介紹拜占庭協議。

上面我們講到的所有的Paxos協議，只講到了服務出錯的情況，并沒有考慮服務偽造篡改信息的情況，即并沒有考慮到惡意節點。而拜占庭協議就是為了解決這個問題而產生的。

Byzantine Paxos比正常的Paxos協議多了一個消息驗證的過程，這個驗證使用了拜占庭協議。

Byzantine Multi-Paxos

下面是個Byzantine Multi-Paxos的序列圖：

ClientProposerAcceptor1Acceptor2Acceptor3LearnerRequestAccept!(N,I,V)Accept!(N,I,V)Accept!(N,I,V)驗證消息Verify(N,I,V) - BROADCASTVerify(N,I,V) - BROADCASTVerify(N,I,V) - BROADCASTVerify(N,I,V) - BROADCASTAccepted(N,V)Accepted(N,V)Accepted(N,V)Accepted(N,V)Accepted(N,V)Accepted(N,V)Response(V)ClientProposerAcceptor1Acceptor2Acceptor3Learner

Fast Byzantine Multi-Paxos

同樣的也會有Fast Byzantine Multi-Paxos，為了更加Fast，本協議將Verify和Accepted進行融合，放在一步完成。

ClientAcceptor1Acceptor2Acceptor3LearnerAccept!(N,I,V)Accept!(N,I,V)Accept!(N,I,V)驗證消息，同時AcceptedAccepted(N,I,V) - BROADCASTAccepted(N,I,V) - BROADCASTAccepted(N,I,V) - BROADCASTAccepted(N,I,V) - BROADCASTAccepted(N,I,V) - BROADCASTAccepted(N,I,V) - BROADCASTAccepted(N,I,V) - BROADCASTResponse(V)ClientAcceptor1Acceptor2Acceptor3Learner

更多精彩內容且看：

• 區塊鏈從入門到放棄系列教程-涵蓋密碼學,超級賬本,以太坊,Libra,比特幣等持續更新
• Spring Boot 2.X系列教程:七天從無到有掌握Spring Boot-持續更新
• Spring 5.X系列教程:滿足你對Spring5的一切想象-持續更新
• java程序員從小工到專家成神之路（2020版）-持續更新中,附詳細文章教程

更多教程請參考flydean的博客

總結

以上是生活随笔為你收集整理的理解分布式一致性:Paxos协议之Generalized Paxos Byzantine Paxos的全部內容，希望文章能夠幫你解決所遇到的問題。

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