楊革+徐虹

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

關(guān)鍵詞：一致性算法；Paxos；超時機制；TB-Paxos

1 概述

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

2 Paxos算法

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

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

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

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

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

3 TB-Paxos算法

3.1 優(yōu)化策略

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

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

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

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

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

3.2 TB-Paxos算法過程

優(yōu)化算法過程和Paxos算法相似，只需在相應(yīng)的階段和角色中添加優(yōu)化策略。Paxos算法的執(zhí)行過程，以下給出優(yōu)化算法的流程圖（如圖1），其中l(wèi)astTried為上次請求編號，nextBal為上次同意投票的編號、preVote為上次投票的值。

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

3.3 性能分析

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

4 結(jié)束語

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

參考文獻

[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-），男，四川達州，碩士研究生，主要研究方向：嵌入式工程。