基于Paxos的分布式一致性算法應(yīng)用研究

劉克禮，張文盛

(安徽開放大學(xué)，合肥 230022)

一、引言

Paxos是解決分布式一致性的核心算法[1]。Tushar Chandra在Paxosmadelive[2]中提出Paxos從理論到實現(xiàn)之間有較大的鴻溝，實現(xiàn)一個Paxos往往需要對Paxos的經(jīng)典理論做一些擴展[3]。目前針對Paxos的研究，除了降低理解難度，使用形式化的方法證明外[4]，更多的研究是進(jìn)行優(yōu)化，以提高性能和便于實踐中應(yīng)用。這方面已經(jīng)有很多應(yīng)用的實例，如Google的Chubby[5]，Tencent的PhxPaxos[6]，Alibaba的X-Paxos等。作為應(yīng)用研究成果的MultiPaxos，引入了實例和選主[7]。Raft也是一個分布一致性算法，其優(yōu)點是易實現(xiàn)，對Paxos的應(yīng)用有借鑒意義[8]。Lampson[9]分析了Paxos算法在工程領(lǐng)域?qū)嵺`中遇到的問題和經(jīng)驗教訓(xùn)。Tecent[10]詳細(xì)地研究了實現(xiàn)PhxPaxos中存在的問題，并給出解決方法?，F(xiàn)有的Paxos應(yīng)用研究中存在選主和成員變更較復(fù)雜，難以實現(xiàn)的問題，本文對此進(jìn)行梳理，并提出兩條優(yōu)化措施。

二、Paxos的實現(xiàn)要點及優(yōu)化

(一)選主和配置變更

1.Paxos中節(jié)點間的通信

Paxos應(yīng)用的一個重要設(shè)計是將Proposer、Acceptor、Learner、SM(State Machine，狀態(tài)機)融合在一個節(jié)點中，通常是同一個進(jìn)程，其中Proposer、Acceptor和Learner使用線程實現(xiàn)。這樣做的好處是所有節(jié)點都是對等和對稱的，可以降低復(fù)雜度。此外Proposer、Acceptor和Learner之間可以共享數(shù)據(jù)，能夠執(zhí)行一些優(yōu)化措施，提高系統(tǒng)性能。為了保證提案編號唯一，所有節(jié)點都要按順序進(jìn)行編號，確保編號唯一。

Paxos是針對異步通信環(huán)境而設(shè)計的，在算法實現(xiàn)過程中存在通信協(xié)議的選擇。UDP協(xié)議屬于典型的異步通信，支持多播和廣播，可以減少發(fā)送的消息數(shù)量，適合Paxos應(yīng)用。TCP協(xié)議能夠消除異步消息的各種問題，如通過超時重傳解決丟失和延遲，通過序號解決亂序和重復(fù)的問題。使用TCP協(xié)議降低了編程難度，例如ZooKeeper[11]就是使用了TCP協(xié)議。

2.Paxos中的實例

Paxos算法只能確定一個值，但在實際應(yīng)用中，需要確定多個值，并且這些值是有序的，形成值序列。各個節(jié)點都維持一個狀態(tài)機，狀態(tài)機的初始狀態(tài)一致。各個節(jié)點將相同值序列輸入本地狀態(tài)機，最終得到的狀態(tài)機仍然一致，從而實現(xiàn)一致性和高可用性。多次執(zhí)行Paxos算法，就可以確定多個值。

相同節(jié)點的集合，可以先執(zhí)行一次Paxos算法，直到值V1確定，保存該值和相關(guān)狀態(tài)，然后再初始化Paxos算法，重新執(zhí)行，直到值V2確定，依次進(jìn)行下去。每個Paxos算法的執(zhí)行被稱為一個實例(Instance)，并被編號，這種方法稱為MultiPaxos。由于后面的選主和配置變更也要用到Paxos，為了方便區(qū)分，記確定應(yīng)用相關(guān)值的Paxos為MP(V)，實例i確定的值記為MP(V,i)，執(zhí)行MP(V)時產(chǎn)生的消息稱為應(yīng)用消息。實例和值按實例號順序組織，一般稱為日志。

各個實例之間的執(zhí)行關(guān)系有兩種：順序和亂序?，F(xiàn)有實例號i和j，順序是指當(dāng)i

3.Paxos中的選主過程

Paxos算法因為Proposer競爭導(dǎo)致確定值可能要很長時間，甚至存在活鎖問題，一般通過選主(Leader)來解決。在所有Proposer中選出一個Leader，其他Proposer的請求都發(fā)給Leader，由Leader發(fā)起提案。Leader消除了鎖競爭，可以迅速確定值，其缺點就是可能存在單點故障。

Leader也是一種共識，為了達(dá)成共識，選主也使用Paxos算法。當(dāng)Leader因為某種原因失效后，需要重新選主。記用于選主的MultiPaxos為MP(L)，執(zhí)行MP(L)產(chǎn)生的消息稱為選主消息。選主狀態(tài)機很簡單，只有一個變量，就是當(dāng)前主(curLeader)。MP(L)在第二階段選擇提案值的時候，如果沒有值可選，可將自己作為提案中的值。一開始所有的節(jié)點都無主，所有的節(jié)點都開始執(zhí)行選主過程(假設(shè)實例號為1)，若最終節(jié)點a勝出，那么實例1的值就是a，記為MP(L,1)=a，并設(shè)置到各個節(jié)點curLeader，此后其他節(jié)點將請求轉(zhuǎn)發(fā)給節(jié)點a。產(chǎn)生主的實例號一般稱為代或任期(term)，當(dāng)主失效后，任期增加。MP(L)形成的日志稱為選主日志。假設(shè)當(dāng)前任期是l，有主的MP(V,i)擴展記為MP(V,i,l)。在應(yīng)用消息中攜帶任期，節(jié)點可檢測主是否切換，如果切換，那么先要執(zhí)行選主日志同步操作。

選主過程如圖1所示。

圖1 選主過程

為了維持a不失效，a需要定期向其他節(jié)點發(fā)送存活消息，其他節(jié)點也可以向節(jié)點a定期發(fā)送探測消息，此外其他節(jié)點向a轉(zhuǎn)發(fā)請求時也可以看成附帶的探測。當(dāng)超過一定時間沒有收到存活消息，或發(fā)送幾次探測消息沒有響應(yīng)，或轉(zhuǎn)發(fā)幾次相同的請求都沒有響應(yīng)時，在這三種情況下都可以認(rèn)定a失效，并設(shè)置變量validCurLeader為NULL。

認(rèn)定a失效的節(jié)點b開始執(zhí)行定時探測，向其他節(jié)點發(fā)送消息，詢問其當(dāng)前的validCurLeader，其他節(jié)點返回當(dāng)前實例號和validCurLeader。如果當(dāng)前實例號相同，且過半節(jié)點(包括b)的validCurLeader為NULL，則b開始執(zhí)行MP(L,2)。等待過半節(jié)點的validCurLeader為NULL實質(zhì)是一個同步的過程，是觸發(fā)選主的必要條件。

如果a真的宕機了，那么其他節(jié)點將幾乎同時認(rèn)定a失效，并幾乎同時啟動MP(L,2)的執(zhí)行。發(fā)現(xiàn)選主成功的節(jié)點(例如c)會通知其他節(jié)點當(dāng)前主是誰(例如d)，d在確認(rèn)自己當(dāng)選主之后，開始發(fā)送存活消息，而其他節(jié)點在同步選主日志后將curLeader和validCurLeader都設(shè)置為d。

認(rèn)定a失效并不等于a真的失效，例如分區(qū)導(dǎo)致節(jié)點b在一個少數(shù)分區(qū)C中，而該分區(qū)不包括a。當(dāng)C重新加入主分區(qū)，b經(jīng)過幾輪探測發(fā)現(xiàn)，當(dāng)前任期相同，且過半節(jié)點的validCurLeader仍然是a，則重新設(shè)置本地validCurLeader=a。如果任期不同，那么要先執(zhí)行同步操作。

當(dāng)節(jié)點b認(rèn)定主a失效后(validCurLeader=NULL)，將不再轉(zhuǎn)發(fā)應(yīng)用消息給a，也不再處理a的任何應(yīng)用消息，直到新的主產(chǎn)生。

4.成員和配置變更

運行Paxos算法需要知道系統(tǒng)的配置，至少包括各個節(jié)點的信息(IP和端口)，記為集合CC。各個節(jié)點上的配置必須一致，且默認(rèn)情況下配置固定不變。但在實際應(yīng)用中，為了應(yīng)對多變的環(huán)境和需求，要求系統(tǒng)是可配置的和可伸縮的。

配置的變更需要所有節(jié)點參與。如果只有部分節(jié)點參與，將會導(dǎo)致配置不一致，從而各個節(jié)點看到的節(jié)點數(shù)n是不一致的，這樣會影響Quorum的計算，從而使得Paxos算法執(zhí)行產(chǎn)生混亂。配置也是一種共識，因此配置的變更也適用Paxos算法，記為MP(C,i)，配置的狀態(tài)機就是集合CC。為了解決執(zhí)行MP(C,i)后可能有部分節(jié)點不知配置已變更的問題，在節(jié)點向Leader發(fā)送消息時，攜帶本地當(dāng)前配置的實例號(也稱為版本)。如果Leader的當(dāng)前配置版本大于收到消息中的配置版本，立即返回錯誤，指示節(jié)點先同步配置。配置變更一般都是管理員手動進(jìn)行，管理員在確認(rèn)所有節(jié)點都正常運行后，才會執(zhí)行變更，因此MP(C,i)都能執(zhí)行成功。

配置的變更有很多種組合：增加一個節(jié)點，刪除一個節(jié)點，增加多個節(jié)點，刪除多個節(jié)點，同時增加和刪除多個節(jié)點。只考慮刪除一個節(jié)點(DeleteNode)和增加一個節(jié)點(Add Node)兩種基本操作，其他組合都可以分解成這兩種基本操作。

MP(C,i)執(zhí)行完成并應(yīng)用到狀態(tài)機CC后，如果是DeleteNode，則判斷節(jié)點值是否是自己，如果是的話，則退出；如果節(jié)點值是主節(jié)點，則各個節(jié)點將validCurLeader設(shè)置為NULL，并立即啟動選主過程，不必等待超時；如果是AddNode，Leader會主動通知新節(jié)點成功加入，此后新節(jié)點可以參與后續(xù)的各種消息處理。

5.三個MultiPaxos的關(guān)系

上述三個一致性協(xié)議的執(zhí)行對比如表1所示。

表1 三個MultiPaxos比較

選主和配置變更，都會影響業(yè)務(wù)處理。配置變更可能會觸發(fā)選主，而選主不會影響配置。只有選主是通過競爭確定值，執(zhí)行過程不確定；而配置變更和業(yè)務(wù)處理都是在有主的情況下進(jìn)行的，可以迅速確定值。當(dāng)無主時，配置和業(yè)務(wù)處理暫停執(zhí)行，直到新主選出，因此三個MultiPaxos只能交替運行。

(二)日志和數(shù)據(jù)同步

1.Paxos中的日志和快照

在執(zhí)行Paxos協(xié)議過程中，Acceptor在accept階段要持久化[mp,ap,av]，記為plog，其中mp是收到的最大提案號，ap是接受提案的編號，av是接受提案的值。在MultiPaxos中的Leader在值確定后，要將實例號和值寫入本地日志，記為mlog。然后Leader將值輸入狀態(tài)機，并把日志確定標(biāo)志發(fā)給其他節(jié)點，其他節(jié)點也執(zhí)行同樣的動作，即寫日志和輸入狀態(tài)機。由于每個節(jié)點都具有相同的結(jié)構(gòu),因此可以將plog和mlog合并，組成(i,s,mp,ap,av)，記為mplog，其中i是實例號，s是值的狀態(tài)。

節(jié)點重啟后，從頭執(zhí)行mplog可恢復(fù)狀態(tài)機。在日志量很少的情況下，該方法有效。但在日志量很大的情況下，一方面日志要占用大量磁盤空間，另一方面恢復(fù)狀態(tài)機也需要更長的時間，在恢復(fù)期間節(jié)點不可用，這降低了系統(tǒng)可用性。為了減少日志量和加速狀態(tài)機的重建，引入快照技術(shù)，定期導(dǎo)出狀態(tài)機的當(dāng)前狀態(tài)，并刪除之前的日志。節(jié)點重啟后，直接從最新快照恢復(fù)狀態(tài)機，然后執(zhí)行增量日志，可以快速恢復(fù)服務(wù)。

導(dǎo)出快照時狀態(tài)機不能執(zhí)行任何改動，在數(shù)據(jù)量很大的情況下，可能需要較長時間。節(jié)點對外服務(wù)是基于狀態(tài)機的，狀態(tài)機的凍結(jié)降低了節(jié)點的可用性。一種稱為COW(Copy On Write，寫時復(fù)制)的技術(shù)解決了該問題。在準(zhǔn)備生成快照時，父進(jìn)程節(jié)點先克隆一個子進(jìn)程，該子進(jìn)程共享父進(jìn)程的內(nèi)存，父進(jìn)程可以讀寫狀態(tài)機，而子進(jìn)程對狀態(tài)機只讀不寫。父進(jìn)程寫狀態(tài)機時操作系統(tǒng)會自動COW新的內(nèi)存頁，保證了父進(jìn)程正常運行。子進(jìn)程的狀態(tài)機始終是克隆時的狀態(tài)，可以從容導(dǎo)出快照，并在完成后退出。

2.節(jié)點間數(shù)據(jù)同步

新節(jié)點加入集群時，狀態(tài)機為空，需要從其他節(jié)點同步狀態(tài)，這與節(jié)點重啟時遇到的問題類似。一種同步方法是從其他節(jié)點學(xué)習(xí)所有日志，從頭執(zhí)行，在日志很少的情況下這種方法是有效的。在日志數(shù)據(jù)多的情況下，一方面?zhèn)鬏斎罩疽加么罅繋捄蜁r間，另一方面執(zhí)行日志也會需要較長的時間，此時若業(yè)務(wù)請求頻繁，就可能會出現(xiàn)故障。另一種同步方法是從其他節(jié)點導(dǎo)入最新快照，再同步增量日志。

在極端情況下，同步耗時較長且新日志增長迅速，此時采用并行操作能夠讓新節(jié)點迅速加入集群并提供服務(wù)。新節(jié)點加入集群的操作如下：一方面參與一致性協(xié)議的執(zhí)行并記錄新日志(開始日志編號記為y)，但不輸入狀態(tài)機，另一方面通過舊日志或快照同步狀態(tài)(截止日志編號記為x)。當(dāng)狀態(tài)機還原到x時，由于x≤y，新節(jié)點需要學(xué)習(xí)其他節(jié)點(x,y)間的日志，然后將x之后的日志輸入狀態(tài)機，直至最新日志執(zhí)行完畢，此時新節(jié)點才算成功加入集群。為了降低Leader的壓力，選擇同步日志節(jié)點時將Leader排在最后。

3.讀數(shù)據(jù)和讀寫保序

集群中的寫操作需要通過一致性協(xié)議完成，讀操作只要讀取狀態(tài)機中的數(shù)據(jù)。讀有兩種方式，一種是通過本地節(jié)點的狀態(tài)機提供，稱為本地讀，另一種是讀取Leader的狀態(tài)機，稱為全局讀。本地讀的優(yōu)點是速度快，其缺點是不能保證讀到最新數(shù)據(jù)。全局讀的優(yōu)點是可以讀到最新的數(shù)據(jù)，其缺點是比較費時，增加了Leader的壓力，且在集群發(fā)生分區(qū)時無法完成。

如果兩個操作之間有因果關(guān)系，為了保證結(jié)果的正確性，需要對操作進(jìn)行串化，或者是保序。如果兩個操作之間沒有因果關(guān)系，則可以亂序執(zhí)行。操作通常只有兩種方式：讀和寫。其中寫操作是純粹寫，不包含自增類的寫。兩個操作共有三種組合：讀讀，讀寫，寫寫。兩個操作的目標(biāo)之間有三種關(guān)系：不相交，部分相交，相同。如果兩個操作不相交，則可以亂序執(zhí)行。通常很難判斷操作是否相交，這種情況下，讀寫和寫寫都要保序，讀讀不需要保序。

當(dāng)某個節(jié)點收到讀操作后，為了保證因果關(guān)系，確保能讀到最新的數(shù)據(jù)，需要將該節(jié)點之前的寫操作全部提交到日志中，寫操作寫入狀態(tài)機后，才允許執(zhí)行讀操作。

同一個節(jié)點上的寫操作按接收的順序保序提交，普通節(jié)點再保序提交到Leader，Leader保序執(zhí)行一致性協(xié)議，日志按順序執(zhí)行。

(三)性能優(yōu)化措施

Leader可以讓提案迅速通過，最少需要2RTT(Round Trip Time)。通過分析Paxos的兩階段(Prepare和Accept)，可以發(fā)現(xiàn)Prepare的目的是搶占鎖和選擇值，Accept的目的是驗證鎖并提交值。因為Leader的存在，鎖競爭已經(jīng)成為小概率事件，所以Prepare可以省略，直接跳轉(zhuǎn)至Accept階段。省略Prepare后，MP(V)只需要1RTT就可完成，系統(tǒng)性能可以提高1倍。

省略Prepare需要滿足條件，即不能違反Paxos值不變性約束。分析如下：在Leader發(fā)出promise消息時，此時值還未確定,假設(shè)該promise的提案編號P是1，而每個實例的初始P是0，在(0,1)之間沒有其他提案，則promise安全。在新舊Leader交替時，存在如下情況，即舊Leader發(fā)送提案[1,V1]被某個節(jié)點接收后，因某種原因舊Leader宕機，假設(shè)此時新Leader生成[2,V2]提案，如果V1不等于V2，那么在新Leader完成Accept后，不變性約束就被破壞。為了限制上一個Leader造成的影響，將任期信息附加到P上，新的提案編號為(term,P)。如果promise消息中的任期小于當(dāng)前任期，提案將被拒絕。

通常情況下MP(V)一次可確定一個值，也可以同時確定多個值，即同時確定編號分別是i,i+1,i+2,...,i+n的實例，這樣的批量確定可以使系統(tǒng)性能得到提升。當(dāng)然也不能無限增加同時確定的實例個數(shù)，受網(wǎng)絡(luò)傳輸數(shù)據(jù)包大小限制，當(dāng)數(shù)據(jù)包超過最大傳輸單元時就會發(fā)生分片和重組，由此導(dǎo)致的開銷和不確定性會抵消性能的優(yōu)化。批量確定只能串行操作，在前一個批量確定完成后，才能執(zhí)行下一個批量的確定，這樣就不會產(chǎn)生大量日志空洞。

三、實驗結(jié)果與分析

在所有的一致性實現(xiàn)當(dāng)中，一致性KV(Key Value,鍵值對)數(shù)據(jù)庫是最簡單的。根據(jù)上述分析，使用Python實現(xiàn)一致性KV數(shù)據(jù)庫，并進(jìn)行測試。實驗環(huán)境采用3個節(jié)點的虛擬機，配置為4CPU AMD Opteron(tm)Processor 6376，4G內(nèi)存，50G硬盤，1G網(wǎng)卡。測試項目包括2RTT吞吐量，1RTT吞吐量，批量確定吞吐量。結(jié)果如表2所示，單位為RPS(Request Per Second)。

表2 一致性KV數(shù)據(jù)庫吞吐量測試 Request Per Second

表2中K=10指Key的長度是10字節(jié)，V=10指值的長度是10字節(jié)，余類推。A指代2RTT列數(shù)據(jù)，B指代1RTT列數(shù)據(jù)，C指代批量確定列數(shù)據(jù)。B/A指B列除以A列的值，顯示將2RTT優(yōu)化為1RTT后系統(tǒng)吞吐量提升效果。C/B指C列除以B列的值，顯示將1RTT優(yōu)化為批量確定后系統(tǒng)吞吐量提升效果。根據(jù)表2可知，2RRT比1RTT吞吐量大將近1倍，而批量確定的吞吐量比1RTT又大若干倍，優(yōu)化效果明顯。

四、小結(jié)

詳細(xì)分析Paxos應(yīng)用過程中可能遇到的問題，討論了常規(guī)的通信、實例、日志、同步等，就選主和成員變更提出了輕量級的算法，將選主、配置和應(yīng)用三個一致性協(xié)議進(jìn)行有機組合，互相配合，確保系統(tǒng)穩(wěn)定、可靠和易用。為了保證結(jié)果的正確性，研究分析了讀寫保序問題，并給出一般準(zhǔn)則。最后討論了性能優(yōu)化措施，將2RTT縮減到1RTT，再到批量確定。結(jié)果表明，該設(shè)計能夠滿足進(jìn)一步研究和應(yīng)用的需求。