Paxos算法的研究與改進

楊革+徐虹

摘 要：Paxos算法是分布式系統中解決一致性問題的最重要的算法，但該算法在活性和性能兩個方面存在不足。文章通過對Paxos算法及其現有優化算法的研究和對比，提出了一種基于超時機制的Paxos改進算法TB-Paxos（Timeout-based Paxos）。TB-Paxos通過對Proposer在重新發起prepare請求前加入隨機等待時間能有效地避免算法出現活鎖，以及在Proposer添加固定的等待時間、減少必要的Acceptor數量以及添加額外消息能有效地提升算法的執行效率。

關鍵詞：一致性算法；Paxos；超時機制；TB-Paxos

1 概述

一致性問題是分布式系統中最重要的問題之一，最典型的應用是容錯處理，比如在原子廣播和狀態機復制中都需要一個步驟讓所有節點讓一個值達成一致。一致性問題的難點在于異步網絡中的容錯處理，需要保證在部分節點出現故障時整個系統能繼續正確運行。一致性算法需要滿足安全性和活性兩個需求[1]，安全性指算法不會使系統進入不一致狀態，活性指算法在有限時間內進入下一個狀態。基于消息傳遞的Paxos算法是最重要的一致性算法之一，算法的安全性已經得到證明，即使在部分機器節點出錯的情況下也能保證算法的正確性，但是仍然算法本身存在活性和消息延遲等問題[2]。本文針對Paxos算法的不足，通過引入超時機制以及其它輔助策略對Paxos進行了改進，使Paxos可以在不引入Leader的情況下，保證算法的活性和提高算法的性能。

2 Paxos算法

Paxos算法通過復制日志解決一致性問題。日志內容是形如（id，v）組成的序列，其中id和v分別代表Paxos實例編號和客戶端請求，Paxos算法保證所有復制日志中id對應的v相同。Paxos算法中包括Proposer，Acceptor和Learner三種角色，每個角色對應節點上的一個進程，每個節點可同時擁有多個角色。單個Paxos實例的執行過程如下[1]：

（1）Prepare階段：Proposer選擇一個提案編號n，然后向所有Accepter發送編號為n的prepare請求。當Acceptor收到一個編號為n的prepare請求，且n大于它已經響應的所有prepare請求的編號。那么它保證不會再通過任何編號小于n的提案，同時將它已經通過的最大編號的提案（如果存在，不存在則為空）作為響應。

（2）Accept階段：如果Proposer收到來自半數以上的Acceptor對于它的prepare請求（編號為n）的響應，那么它就會發送一個針對編號為n，值為v的提案的accept請求給Acceptors的一個多數派，其中v是收到的響應中編號最大的提案的值，如果響應中不包含提案，那么它就是任意值。如果Acceptor收到一個針對編號n的提案的accept請求，只要它還未響應編號大于n的prepare請求，它就可以通過這個提案。

（3）Learn階段：在Proposer收到來自半數以上的accept請求的回復時，它將v記錄到日志里，然后發送Success消息給每個Acceptor。所有的Acceptor收到Success消息后，將v記錄到它的日志里。

從算法可知，Prepare階段中如果兩個Proposer持續地產生一系列的提案，最終不會有提案被選定，引起活鎖；另一方面，完成一個Paxos實例需要3次通信延遲，所以算法執行效率不高。針對Paxos算法的缺陷，現有的算法改進或實現主要是通過引入Leader機制[4]來解決活性問題，并且可以將3次通信延遲減少為2次，但會出現單點問題[5]。其余的改進多通過減少算法執行中通信節點的數量[2]和減少通信延遲次數[3]對算法進行優化，以及利用計算機工程技術提高算法的執行效率[6]。

3 TB-Paxos算法

3.1 優化策略

為了解決活性問題，為Paxos算法的必要過程設置一個計時器，利用超時機制來衡量這個過程是成功或者失敗，對某個流程選擇性地重復執行來保證這個流程正確執行。另外，可以利用隨機超時時間保證算法有效地避免出現活鎖。具體的優化策略如下：

（1）為Proposer等待prepare請求和accept請求回復的過程增加一個時鐘，超過設置的時鐘Proposer就認為該請求失敗。當時鐘設置為無窮大時，即為原生Paxos算法。具體時鐘的大小可以根據具體的網絡環境和服務器處理能力進行設置，初始時可以設置一個略大的值，然后根據算法具體執行流程所花費的時間，來設置一個合理大小的時鐘。

（2）當提案被拒絕時，Proposer需要重新提交prepare請求，如果頻繁的提交可能會引起活鎖，但是可以等待一個范圍內的隨機時間再提交prepare請求就可以有效地減小出現活鎖的概率。

（3）在Acceptor接收到一個新的prepare請求時，可以給最近收到的prepare請求回復一條Nack消息，通知該編號的協議不會被通過。如果某個Proposer收到超過半數的Acceptor的Nack消息，則可以斷定該提案一定會失敗，可以提前結束這個流程。

（4）使用缺少失敗恢復機制的Cheap Paxos的策略[2]，可以減少Proposer發送prepare請求和accept消息的數量。由于系統環境的不確定性，可以根據具體環境決定接收Acceptor集合的大小，并且每個階段Acceptor的數量可以不一致。

3.2 TB-Paxos算法過程

優化算法過程和Paxos算法相似，只需在相應的階段和角色中添加優化策略。Paxos算法的執行過程，以下給出優化算法的流程圖（如圖1），其中lastTried為上次請求編號，nextBal為上次同意投票的編號、preVote為上次投票的值。

在Proposer重新發起請求之前，可以根據是否收到alert消息判斷是否需要設置一個隨機等待時間避免活鎖。如果需要則等待隨機時間后才發起請求；否則直接發起請求。圖中的虛線框的內容表示可以根據需要選擇是否添加到算法中，收到Nack消息可以按照算法改進策略（3）進行處理；Acceptor如果收到一個編號比其它prepare請求編號小，可發送reject消息（內容為請求編號）告知Proposer需要提交更大編號的請求才能被通過，以減少該Proposer請求失敗的次數。流程圖中未涉及相應階段Acceptor集合的選擇，具體參考算法改進策略（4）。

3.3 性能分析

本文提出的前三條優化策略可以有效地解決Paxos算法的活性問題，可以提高算法的可靠性，保證算法快速完成；第四條優化策略從消息數量方面對Paxos算法進行了優化，在穩定的系統環境中，可以有效的提升算法的執行效率。假設Paxos集群擁有2F+1個節點，如果在Prepare階段和Accept階段分別選用M，N（M，N>F+1）個Acceptor，則可以減少2（2F+1-M-N）個消息傳輸和處理。然而在網絡不穩定的系統環境中減少消息傳輸可能不會帶來明顯的效果，反而導致算法不斷重新執行。

4 結束語

數據一致性是分布式系統中的難點問題，Paxos算法是一致性問題的主要解決方案。本文提出的TB-Paxos算法在不破壞系統節點對稱性的前提下，能有效地解決Paxos算法的活性問題，并且通過減少消息通信數量的方式可以提高算法性能。Paxos算法除了本文提及的活性問題，還有很多問題需要解決（如日志復制、讀寫請求的區分等），未來的工作主要包括如何優化Paxos算法流程以及結合計算機相關技術方面來提高算法的可靠性和性能。

參考文獻

[1]L Lamport. Paxos Made Simple [J]. ACM Sigact News， 32（4）： 18-25， 2001.

[2]L Lamport， Massa Mike. Cheap Paxos [J]. Proceedings of the International Conference， 2004.

[3]L Lamport. Fast Paxos [J]. Distributed Computing， 19（2）， 2005.

[4]D Ongaro. In Search of an Understandable Consensus Algorithm [J]. Stanford University. 2013.

[5]I Moraru. There Is More Consensus in Egalitarian Parliaments [J]. In Proc. of SOSP， 2013.

[6]J Li. Just Say NO to Paxos Overhead： Replacing Consensus with Network Ordering [J]. In 11th USENIX Symposium on OSDI.，2016.

作者簡介：楊革（1992-），男，四川達州，碩士研究生，主要研究方向：嵌入式工程。