基于分布式同步時(shí)鐘的paxos算法改進(jìn)

王麗穎 王紅 劉春漲

【摘要】 本文分析了出現(xiàn)數(shù)據(jù)一致方面的問題，對(duì)解決數(shù)據(jù)一致性的paxos算法中存在的主要問題進(jìn)行了闡述，重點(diǎn)對(duì)一個(gè)accept與accepted過程只能通過一個(gè)議案問題和通過議案的時(shí)間受議案的長度影響問題進(jìn)行了研究。在paxos算法的基礎(chǔ)上，利用proposor提交多個(gè)議案編號(hào)，結(jié)合議案被服務(wù)器集群過半存儲(chǔ)的前提，對(duì)算法進(jìn)行了改進(jìn)。測(cè)試結(jié)果表明了算法的正確性和合理性。

【關(guān)鍵詞】 paxos算法 一次提交多個(gè)議案 過半存儲(chǔ)

一、引言

數(shù)據(jù)一致性問題是分布式領(lǐng)域的經(jīng)典問題，同時(shí)也是難點(diǎn)問題[1]。以服務(wù)器為中心的服務(wù)模型下，單點(diǎn)故障會(huì)導(dǎo)致服務(wù)器無法對(duì)外提供服務(wù)，因此需要引入多臺(tái)服務(wù)器。這樣將會(huì)帶來數(shù)據(jù)一致性問題，因此必須有一個(gè)副本控制協(xié)議來實(shí)現(xiàn)數(shù)據(jù)的一致性。[2]本文的分布式存儲(chǔ)系統(tǒng)由成百上千個(gè)設(shè)備組成，若一次只能提交一條議案，引入邏輯時(shí)鐘同步是一個(gè)巨大的開銷。本文提出的一次提交多個(gè)議案編號(hào)的方案可以降低該開銷。一次提交多個(gè)議案編號(hào)的設(shè)計(jì)中假若議案編號(hào)的議案缺失，會(huì)使得系統(tǒng)卡在此編號(hào)上，使得服務(wù)器無法運(yùn)行下一條議案。因此得設(shè)計(jì)一個(gè)方法保證議案在被批準(zhǔn)前時(shí)刻存在。

服務(wù)器的服務(wù)能力受其自身網(wǎng)絡(luò)的硬件條件的制約。單臺(tái)服務(wù)器所能對(duì)外提供的服務(wù)能力是有限路數(shù)的，很多是受帶寬、網(wǎng)卡處理能力的影響，這是典型的單點(diǎn)問題。當(dāng)單臺(tái)服務(wù)器達(dá)到服務(wù)能力的上限時(shí)，則采用用多臺(tái)服務(wù)器來對(duì)外提供更強(qiáng)的服務(wù)能力。此時(shí)需要解決數(shù)據(jù)的一致性問題。

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

本文提出了基于全局邏輯時(shí)鐘同步分布式系統(tǒng)一致全局狀態(tài)的一種方法。本文設(shè)計(jì)了一個(gè)一致性算法并進(jìn)行了系統(tǒng)仿真。

二、相關(guān)工作

2.1全局時(shí)鐘

分布式系統(tǒng)中，全局時(shí)鐘需要能對(duì)發(fā)生在系統(tǒng)中的事件進(jìn)行排序。一個(gè)時(shí)鐘要能用于刻畫事件發(fā)生先后順序，且對(duì)于因果序其要滿足的條件：對(duì)于任意事件a，b：如果a->b，那么Cfunction（a） < Cfunction （b）。Cfunction定義為一個(gè)函數(shù)——為進(jìn)程中的任意事件a分配編號(hào)Cfunction （a）。即：

IR1.每個(gè)進(jìn)程Pi在任意連續(xù)的兩個(gè)事件之間會(huì)增加Ci的值。

IR2.（a）如果事件a代表了進(jìn)程Pi發(fā)送消息m的事件，那么消息m包含的時(shí)間戳Tm=Ci（a）.

（b）在收到消息m后，進(jìn)程Pj會(huì)設(shè)置Cj的值使得它大于等于它的當(dāng)前值并大于Tm。[3]

2.2 Paxos算法

Paxos算法分為兩步驟：通過一個(gè)決議的過程分為兩個(gè)階段[4，5，6]（若是fastpaxos則首先，是leader選舉；其次是通過一個(gè)決議[7]）：1.準(zhǔn)備階段（prepear，promise），2.批準(zhǔn)階段（accept，accepted）。隨著運(yùn)行paxos算法的機(jī)器數(shù)的增多算法達(dá)到一致性的時(shí)間會(huì)延長。還可得知機(jī)器數(shù)少，達(dá)到一致性的時(shí)間更短。Paxos算法通過一條議案的轉(zhuǎn)態(tài)轉(zhuǎn)移如下圖所示：

2.3改進(jìn)的算法

改進(jìn)的算法轉(zhuǎn)態(tài)轉(zhuǎn)移圖如下：

我們約定：

1.一個(gè)客戶端要執(zhí)行與全局相關(guān)的事件e的時(shí)，需要向時(shí)鐘系統(tǒng)申請(qǐng)一個(gè)編號(hào)，之后才能執(zhí)行。來保證e的操作能被其他客戶端收到。

2.定義事件系統(tǒng)為；存儲(chǔ)、記錄以及執(zhí)行全局相關(guān)的所有事件的執(zhí)行順序的系統(tǒng)。事件系統(tǒng)是按照時(shí)鐘進(jìn)行事件推演的。即，將事件系統(tǒng)的推演定義為：整個(gè)系統(tǒng)執(zhí)行操作的順序是按照給定的邏輯時(shí)鐘編號(hào)進(jìn)行執(zhí)行的，即各個(gè)節(jié)點(diǎn)先執(zhí)行C（event1）為1的event1，在執(zhí)行C（event2）為2的event2

3. 進(jìn)程內(nèi)，進(jìn)程pi只有執(zhí)行完一條指令，才能提出下一條指令的時(shí)鐘申請(qǐng)。

基于paxos算法的分布式時(shí)鐘能夠用來為系統(tǒng)運(yùn)行提供一個(gè)時(shí)序。各個(gè)節(jié)點(diǎn)向該時(shí)鐘系統(tǒng)申請(qǐng)執(zhí)行議案，且嚴(yán)格的按照paxos時(shí)鐘的時(shí)序來執(zhí)行。

單個(gè)的授時(shí)中心是不可靠的，因此需要多個(gè)授時(shí)中心，但是多個(gè)授時(shí)中心的時(shí)鐘又是難以保證時(shí)時(shí)刻刻一致只能在一定的精度范圍內(nèi)的保持一致。故為了完成在多節(jié)點(diǎn)的情況下能授給任何節(jié)點(diǎn)相同的時(shí)鐘，可以在這些分布式授時(shí)中心上運(yùn)行一致性算法paxos來為事件系統(tǒng)的執(zhí)行提供時(shí)鐘協(xié)作信號(hào)。從而使得事務(wù)系統(tǒng)中發(fā)生在各個(gè)節(jié)點(diǎn)中進(jìn)程的事件都可以被注冊(cè)唯一的編號(hào)，即C（event）是唯一的，只要其是經(jīng)過我們的時(shí)鐘系統(tǒng)提出了申請(qǐng)。

如何標(biāo)記議案使得其在全局中是唯一。是一個(gè)較易做到的。例如使用自身的IP和PORT可以區(qū)別出本機(jī)和本機(jī)的其他進(jìn)程，給議案一個(gè)標(biāo)記step使其在本進(jìn)程內(nèi)同其他的議案相區(qū)別開，同時(shí)使帶step的議案單調(diào)遞增的被本進(jìn)程執(zhí)行。

本文對(duì)這種標(biāo)記議案使其在全局中唯一的標(biāo)記定義為ID。

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

上述算法設(shè)計(jì)進(jìn)程內(nèi)：任意連續(xù)的兩個(gè)事件之間會(huì)增加Ci的值。.進(jìn)程間：（a）如果事件a代表了進(jìn)程Pi發(fā)送消息m的事件，那么消息m包含的時(shí)間戳Tm=Ci（a）.（b）在收到消息m后，時(shí)鐘系統(tǒng)會(huì)設(shè)置Cj的值使得它大于等于它的當(dāng)前值并大于Tm。

在時(shí)鐘系統(tǒng)中的learner中會(huì)使得編號(hào)單調(diào)遞增。

2.5仿真實(shí)驗(yàn)設(shè)計(jì)與實(shí)現(xiàn)

實(shí)驗(yàn)環(huán)境

操作系統(tǒng)：ubuntu 15.04

處理器：Xeon E5-2620 ，

主頻：2.00GHz，

內(nèi)存：32GB的服務(wù)器 虛擬12臺(tái)機(jī)器（每臺(tái)1G）。

編程技術(shù)和工具：Linux C、C++。

時(shí)鐘系統(tǒng)源碼：libpaxos（開源的），（也可以用SB_ paxos）。

三、結(jié)束語

經(jīng)實(shí)驗(yàn)驗(yàn)證，采用本文所述策略使得在有大量請(qǐng)求時(shí)效率會(huì)高于原paxos算法。關(guān)于paxos算法，若通過設(shè)置不同的paxos組可實(shí)現(xiàn)不同范圍內(nèi)的同步?？梢酝ㄟ^修改配置文件來構(gòu)建更大范圍的應(yīng)用。所以，下一階段工作是進(jìn)行利用改進(jìn)后的paxos算法構(gòu)建應(yīng)用軟件的研究。

參 考 文 獻(xiàn)

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

[2]談華芳，孫麗麗，侯紫峰.一種多副本一致性控制方法[J].計(jì)算機(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].計(jì)算機(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.