Paxos算法的研究與改進(jìn)

楊革+徐虹

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

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

1 概述

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

2 Paxos算法

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

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

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

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

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

3 TB-Paxos算法

3.1 優(yōu)化策略

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

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

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

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

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

3.2 TB-Paxos算法過(guò)程

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

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

3.3 性能分析

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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.

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