基于分布式同步時鐘的paxos算法改進

王麗穎 王紅 劉春漲

【摘要】 本文分析了出現數據一致方面的問題，對解決數據一致性的paxos算法中存在的主要問題進行了闡述，重點對一個accept與accepted過程只能通過一個議案問題和通過議案的時間受議案的長度影響問題進行了研究。在paxos算法的基礎上，利用proposor提交多個議案編號，結合議案被服務器集群過半存儲的前提，對算法進行了改進。測試結果表明了算法的正確性和合理性。

【關鍵詞】 paxos算法 一次提交多個議案 過半存儲

一、引言

數據一致性問題是分布式領域的經典問題，同時也是難點問題[1]。以服務器為中心的服務模型下，單點故障會導致服務器無法對外提供服務，因此需要引入多臺服務器。這樣將會帶來數據一致性問題，因此必須有一個副本控制協議來實現數據的一致性。[2]本文的分布式存儲系統由成百上千個設備組成，若一次只能提交一條議案，引入邏輯時鐘同步是一個巨大的開銷。本文提出的一次提交多個議案編號的方案可以降低該開銷。一次提交多個議案編號的設計中假若議案編號的議案缺失，會使得系統卡在此編號上，使得服務器無法運行下一條議案。因此得設計一個方法保證議案在被批準前時刻存在。

服務器的服務能力受其自身網絡的硬件條件的制約。單臺服務器所能對外提供的服務能力是有限路數的，很多是受帶寬、網卡處理能力的影響，這是典型的單點問題。當單臺服務器達到服務能力的上限時，則采用用多臺服務器來對外提供更強的服務能力。此時需要解決數據的一致性問題。

單點問題的解決方案大多是采用備份以及多服務器，多服務器意味著多中心的出現，多個中心如何保證數據一致性，以及對外提供更快速的服務是需首要解決的問題。尤其是互聯網時代中的各種交易平臺（如果多中心沒有一致會使得業務收到影響），達成一致性所用的時間將會影響用戶體驗和平臺的性能。因而，設計合理的響應時間的一致性算法對實際的應用來說是有意義的。

本文提出了基于全局邏輯時鐘同步分布式系統一致全局狀態的一種方法。本文設計了一個一致性算法并進行了系統仿真。

二、相關工作

2.1全局時鐘

分布式系統中，全局時鐘需要能對發生在系統中的事件進行排序。一個時鐘要能用于刻畫事件發生先后順序，且對于因果序其要滿足的條件：對于任意事件a，b：如果a->b，那么Cfunction（a） < Cfunction （b）。Cfunction定義為一個函數——為進程中的任意事件a分配編號Cfunction （a）。即：

IR1.每個進程Pi在任意連續的兩個事件之間會增加Ci的值。

IR2.（a）如果事件a代表了進程Pi發送消息m的事件，那么消息m包含的時間戳Tm=Ci（a）.

（b）在收到消息m后，進程Pj會設置Cj的值使得它大于等于它的當前值并大于Tm。[3]

2.2 Paxos算法

Paxos算法分為兩步驟：通過一個決議的過程分為兩個階段[4，5，6]（若是fastpaxos則首先，是leader選舉；其次是通過一個決議[7]）：1.準備階段（prepear，promise），2.批準階段（accept，accepted）。隨著運行paxos算法的機器數的增多算法達到一致性的時間會延長。還可得知機器數少，達到一致性的時間更短。Paxos算法通過一條議案的轉態轉移如下圖所示：

2.3改進的算法

改進的算法轉態轉移圖如下：

我們約定：

1.一個客戶端要執行與全局相關的事件e的時，需要向時鐘系統申請一個編號，之后才能執行。來保證e的操作能被其他客戶端收到。

2.定義事件系統為；存儲、記錄以及執行全局相關的所有事件的執行順序的系統。事件系統是按照時鐘進行事件推演的。即，將事件系統的推演定義為：整個系統執行操作的順序是按照給定的邏輯時鐘編號進行執行的，即各個節點先執行C（event1）為1的event1，在執行C（event2）為2的event2

3. 進程內，進程pi只有執行完一條指令，才能提出下一條指令的時鐘申請。

基于paxos算法的分布式時鐘能夠用來為系統運行提供一個時序。各個節點向該時鐘系統申請執行議案，且嚴格的按照paxos時鐘的時序來執行。

單個的授時中心是不可靠的，因此需要多個授時中心，但是多個授時中心的時鐘又是難以保證時時刻刻一致只能在一定的精度范圍內的保持一致。故為了完成在多節點的情況下能授給任何節點相同的時鐘，可以在這些分布式授時中心上運行一致性算法paxos來為事件系統的執行提供時鐘協作信號。從而使得事務系統中發生在各個節點中進程的事件都可以被注冊唯一的編號，即C（event）是唯一的，只要其是經過我們的時鐘系統提出了申請。

如何標記議案使得其在全局中是唯一。是一個較易做到的。例如使用自身的IP和PORT可以區別出本機和本機的其他進程，給議案一個標記step使其在本進程內同其他的議案相區別開，同時使帶step的議案單調遞增的被本進程執行。

本文對這種標記議案使其在全局中唯一的標記定義為ID。

2.4一次提交多個議案的算法的正確性說明

上述算法設計進程內：任意連續的兩個事件之間會增加Ci的值。.進程間：（a）如果事件a代表了進程Pi發送消息m的事件，那么消息m包含的時間戳Tm=Ci（a）.（b）在收到消息m后，時鐘系統會設置Cj的值使得它大于等于它的當前值并大于Tm。

在時鐘系統中的learner中會使得編號單調遞增。

2.5仿真實驗設計與實現

實驗環境

操作系統：ubuntu 15.04

處理器：Xeon E5-2620 ，

主頻：2.00GHz，

內存：32GB的服務器 虛擬12臺機器（每臺1G）。

編程技術和工具：Linux C、C++。

時鐘系統源碼：libpaxos（開源的），（也可以用SB_ paxos）。

三、結束語

經實驗驗證，采用本文所述策略使得在有大量請求時效率會高于原paxos算法。關于paxos算法，若通過設置不同的paxos組可實現不同范圍內的同步?？梢酝ㄟ^修改配置文件來構建更大范圍的應用。所以，下一階段工作是進行利用改進后的paxos算法構建應用軟件的研究。

參 考 文 獻

[1]周婧，王意潔，阮煒，等. 面向海量數據的數據一致性研究[J].計算機科學，2006，33（4）：137-140.

[2]談華芳，孫麗麗，侯紫峰.一種多副本一致性控制方法[J].計算機工程.2006（11）

[3]LAMPORT L.Time，clocks and the ordering of events in a distributed system[J]Commun ACM （CACM）， 1978， 21（7）：558-565

[4]許子燦，吳榮泉.基于消息傳遞的Paxos算法研究[J].計算機工程，2011，37（21）：287-290.

[5] Lamport L. Paxos made simple. ACM SIGACT News 32，4 （Dec.2001），18-25.

[6] LAMPORT L.The partime Pariment[M]. ACM Transaction on Computer Systems，1998，16（2）：133-169.

[7]LAMPORT L. Fast paxos[J].Distributed Computing，2006，2（19）：79-103.