楊春明 杜 炯

(西南科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院 四川綿陽 621010)

隨著企業(yè)應(yīng)用系統(tǒng)對計算能力需求的增長，傳統(tǒng)單節(jié)點處理的服務(wù)模式逐漸達到了一個瓶頸。為了緩解單點的網(wǎng)絡(luò)帶寬、存儲、計算等壓力以及解除單點故障(當服務(wù)中心出現(xiàn)軟硬件故障的時候整個服務(wù)不可用)等問題，越來越多的大型系統(tǒng)逐漸從單節(jié)點模式轉(zhuǎn)向分布式的云計算模式。

在分布式的計算環(huán)境中，解決計算節(jié)點之間的數(shù)據(jù)同步、分布式資源競爭以及單節(jié)點故障自主恢復(fù)等問題是系統(tǒng)正確性和可靠性的基本保證。其中最基本的是節(jié)點之間的數(shù)據(jù)一致性問題，即保證節(jié)點之間互通情況下從各個節(jié)點請求到的數(shù)據(jù)必須是一致的，同時外部請求對數(shù)據(jù)做出的修改在各個節(jié)點之間也必須同步。Paxos系列算法的出現(xiàn)解決了分布式設(shè)計中一致性的問題，可以應(yīng)用在數(shù)據(jù)復(fù)制、命名服務(wù)、配置管理、權(quán)限設(shè)置和號碼分配等場合［1－2］。然而很多時候系統(tǒng)在設(shè)計之初并沒有考慮到在分布式環(huán)境下的高可用和一致性的問題，當系統(tǒng)逐漸變大之后，系統(tǒng)的一致性和高可用性變得尤為重要。一些系統(tǒng)采用主從復(fù)制模式(Master/slave)來解決該問題［3］，但主從復(fù)制模式的一致性主要依賴主節(jié)點，主節(jié)點故障后導(dǎo)致各從節(jié)點之間的數(shù)據(jù)不能同步。

本文分析了Paxos算法的基本原理，設(shè)計了一個外部的鎖服務(wù)系統(tǒng)，可以使網(wǎng)絡(luò)節(jié)點間的同步能夠像進程間的同步一樣簡單、可靠。該分布式鎖服務(wù)除了具有鎖原語的基本操作(創(chuàng)建、鎖定、釋放)外，還提供了處理共享資源的簡單數(shù)據(jù)存儲以及實時的鎖事件通知(鎖的釋放、數(shù)據(jù)修改)等操作，可以簡化分布式應(yīng)用的設(shè)計。

1 Paxos算法

Paxos算法是用來解決在不可靠的網(wǎng)絡(luò)環(huán)境中多個網(wǎng)絡(luò)節(jié)點達成可靠一致性共識的算法。假設(shè)現(xiàn)在有一個可以提出提案的節(jié)點集合。一個一致性算法保證在這些提案中只有一個能被選中，如果沒有提案被提出則沒有提案被選中。如果一個提案被選中了，那么其他的節(jié)點應(yīng)該能夠知道這個被選中的提案。需要達成這個共識的安全需求有:

(1)只有某個提案被提出才能被選中;

(2)只能有一個提案被選中;

(3)一個節(jié)點永遠不會得知某個提案被選中除非它真的被選中了。

算法中將不同的節(jié)點用3個角色來表示:Proposers，Acceptors 和 Learners［4］，其 中，Proposer 向Acceptor提交提案(proposal)，提案中含有決議(value);Acceptor審批提案;Learner獲取并執(zhí)行已經(jīng)通過審批的提案中含有的決議。

一個節(jié)點可以扮演多個角色，不同的角色僅表示其在算法中的不同職能。不同的節(jié)點之間可以發(fā)送消息進行交流，發(fā)送的消息可能會丟失、延遲或重復(fù)，但是不能被破壞，即每次接收到的消息都是完整的、沒有被篡改。

算法的操作流程分為2個階段:(1)準備階段:Proposer選擇一個提案號n，并發(fā)送一個帶有n的Prepare請求給大部分的Acceptor。如果一個Acceptor收到的Request中的n大于任何一個它收到且回復(fù)的Prepare請求的n，則回復(fù)Proposer保證不會接受任何小于n的請求。(2)批準階段:如果Proposer收到了大部分Acceptor的回應(yīng)，則向這些Acceptor發(fā)送一個Accept請求，請求包含數(shù)字n和值v。如果一個Acceptor收到了一個包含n的Accept請求而且它沒有回復(fù)一個比n大的Prepare請求，則接受這個Accept請求。通過這兩個階段的消息傳遞和實例執(zhí)行，可保證數(shù)據(jù)和操作的一致性。Paxos算法采用了投票選舉的形式，通過數(shù)學(xué)歸納的思想進一步保障了majority機制，保證了2F+l的容錯能力，即具備2F+l個結(jié)點的系統(tǒng)最多允許F個結(jié)點同時出現(xiàn)故障［5］。但該算法也存在一些局限，如在兩個Proposer可能陷入活鎖、隨機等待時間較長、通信負載等，許子燦等人［6］對此進行了一系列的優(yōu)化。

2 基于Paxos算法的分布式鎖服務(wù)

2.1 分布式鎖服務(wù)的結(jié)構(gòu)

在分布式環(huán)境中，相同的應(yīng)用或數(shù)據(jù)會部署在不同的節(jié)點上，用戶或其他應(yīng)用的請求也會分流到不同的節(jié)點，為了提供不間斷的服務(wù)及保證各節(jié)點數(shù)據(jù)的一致性，需要一個分布式的鎖服務(wù)來提供上述功能。本文了采用Paxos算法構(gòu)建了一個分布式環(huán)境下的鎖服務(wù)，其系統(tǒng)結(jié)構(gòu)如圖1所示。

圖1 分布式鎖服務(wù)系統(tǒng)結(jié)構(gòu)Fig.1 The structure of distributed lock service system

圖中的圓形節(jié)點構(gòu)成了服務(wù)集群的鎖節(jié)點，應(yīng)用或數(shù)據(jù)將部署在該類節(jié)點上，客戶端向服務(wù)集群發(fā)出服務(wù)請求，服務(wù)集群將采用Paxos算法選擇響應(yīng)請求的節(jié)點，并將對數(shù)據(jù)的操作同步到其他各節(jié)點。圖中Leader和Follower的網(wǎng)絡(luò)地位一致，從長時間跨度來看，服務(wù)集群中沒有中心單點。鎖節(jié)點有如下3種角色:

(1)Leader:主要負責(zé)提出數(shù)據(jù)寫提案和數(shù)據(jù)寫操作請求;

(2)Follower:提供數(shù)據(jù)讀服務(wù)和向Leader提出數(shù)據(jù)寫申請;

(3)Learner:接受數(shù)據(jù)寫提案和向數(shù)據(jù)庫提交寫操作。

分布式的鎖服務(wù)中每個鎖節(jié)點對外提供一個帶鎖的Key/Value數(shù)據(jù)接口，主要的接口功能如表1所示。

表1 分布式鎖服務(wù)接口Table 1 The interface of distributed lock service

2.2 Leader選舉算法

在Paxos算法中每個成員都是Proposer，根據(jù)算法一個編號更大的提案會終止之前的提案過程，如果2個Proposer在這種情況下都轉(zhuǎn)而提出一個編號更大的提案，那么就可能陷入活鎖。這就難免會產(chǎn)生沖突，增加系統(tǒng)的時間延遲。

為了避免提案的沖突，在所有的Proposer中選舉一個Leader，所有的提案只能由Leader提出，其他Proposer就跟隨Leader，稱為 Follower。Leader通過 Fast－ Leader－ Election 算法［7－8］進行選舉，系統(tǒng)在以下幾種情況使用該算法進行Leader的選舉:

(1)系統(tǒng)啟動后，所有節(jié)點角色都是相同的;

(2)Leader無法跟一半以上的Follower進行正常通信;

(3)Follower無法跟Leader進行正常通信;

(4)Leader的周期達到，進行計劃的 Leader選舉;

(5)人工干預(yù)Leader選舉。

此時鎖節(jié)點有以下3種狀態(tài):

(1)Looking:節(jié)點執(zhí)行 FastLeaderElection算法時，選舉Leader;

(2)Leading:Leader節(jié)點的狀態(tài);

(3)Following:Follower節(jié)點的狀態(tài)。

3種狀態(tài)之間的轉(zhuǎn)換關(guān)系如圖2所示。

為了保證選舉到的Leader擁有最新的鎖狀態(tài)，選舉時需要鎖節(jié)點包含以下屬性:

(1)myid:鎖節(jié)點ID號，需要人工在配置文件中指定;

(2)view:每次選舉后所有鎖節(jié)點的狀態(tài)稱為一個view，初始為0，每次選舉后view自增1;

(3)trans:提案事務(wù)序號，初始為0，每一次提案通過后trans自增1;

(4)clock:鎖服務(wù)的選舉計數(shù)，初始為0。

圖2 鎖節(jié)點之間的狀態(tài)轉(zhuǎn)移Fig.2 The state transition between locked nodes

選舉出的Leader必須保證trans和view是所有鎖節(jié)點中最大的，如果兩者都一樣就取myid最大的。因此，Leader的選舉流程如下:

鎖節(jié)點之間通過投票來選舉Leader，每次投票包含 leaderid，state，view，trans和 myid，其中 leaderid是本次投票Leader的ID號，state是投票者的狀態(tài)。

投票按投票者的狀態(tài)分為普通投票和穩(wěn)定投票，節(jié)點狀態(tài)為Looking的投票為普通投票，否則為穩(wěn)定投票(此時對應(yīng)的鎖節(jié)點已結(jié)束選舉)，兩類投票分別用states和stable_votes集合記錄。

在開始選舉時，首先將節(jié)點狀態(tài)設(shè)為Looking，推舉自己作為Leader，通知所有的鎖節(jié)點;然后只要當前服務(wù)器狀態(tài)為Looking且不為stop，進入循環(huán)，不斷地讀取其它鎖節(jié)點發(fā)來的投票、進行比較、更新自己的投票、發(fā)送自己的投票、統(tǒng)計投票結(jié)果，直到Leader選出或出錯退出。具體作法是接收一個投票，根據(jù)投票者的狀態(tài)進行相應(yīng)的處理，其選舉流程如圖3、圖4所示。

2.3 數(shù)據(jù)同步算法

鎖服務(wù)中數(shù)據(jù)同步主要有兩類:數(shù)據(jù)初始化同步、數(shù)據(jù)寫同步。鎖數(shù)據(jù)的所有操作都記錄在日志中，每個操作有一個事務(wù)ID來標識自己，記為trans。

在鎖節(jié)點選舉出Leader之后需要對鎖數(shù)據(jù)進行同步，確保所有鎖節(jié)點在開始工作之前的鎖數(shù)據(jù)是一致的。

同步流程如下:

(1)Follower向Leader發(fā)送同步請求，在請求中附上自己最后一次數(shù)據(jù)操作的trans;

(2)Leader把 Follower的 trans和自己的 trans比較，向Follower發(fā)送缺失的數(shù)據(jù)操作日志;

圖3 投票者為Looking狀態(tài)的選舉流程Fig.3 The election process of voters in“Looking”state

圖4 投票者為Leading或Following狀態(tài)的選舉流程Fig.4 The election process of voters in“Leading”or“Following”state

(3)Follower把收到的數(shù)據(jù)操作日志與本地的操作日志合并并將其應(yīng)用于數(shù)據(jù)。

數(shù)據(jù)寫操作包括新建鍵、修改鍵、刪除鍵以及鎖的相關(guān)操作，這里使用Paxos算法來同步數(shù)據(jù)，但是只允許Leader提出議案，具體流程如下:

(1)Leader或Follower向Leader提交一個寫操作請求;

(2)Leader檢查該寫操作是否合法(比如寫入數(shù)據(jù)請求時對應(yīng)的鍵值被鎖定);

(3)Leader向所有Follower發(fā)送寫操作的提案;

(4)Follower同意議案，告知Leader;

(5)Leader得到半數(shù)Follower的同意后向所有鎖節(jié)點發(fā)送寫操作提交請求;

(6)Leader或Follower收到寫操作提交請求記錄日志并向數(shù)據(jù)庫中提交數(shù)據(jù)。

3 實驗及結(jié)果分析

實驗主要在單臺機器下使用多個終端來模擬多個節(jié)點，驗證分布式鎖服務(wù)的有效性，同時進行性能分析。實驗環(huán)境為 PC機，Intel Core i5 CPU，2.5 GHz，6 GB 內(nèi)存，操作系統(tǒng)為 Linux Kernel 3.964位，使用 Python 2.7，gevent，leveldb 實現(xiàn)了分布式鎖服務(wù)。

分布式鎖服務(wù)主要解決分布式環(huán)境中高并發(fā)訪問時的容錯性和響應(yīng)速度，數(shù)據(jù)的容錯性主要由鎖服務(wù)的功能及節(jié)點故障后數(shù)據(jù)的一致性來體現(xiàn)，響應(yīng)速度則主要看多個客戶端在多次讀寫情況下不同數(shù)據(jù)量的時間消耗。

容錯性測試主要測試提供的鎖服務(wù)功能是否滿足要求，同時測試在節(jié)點故障(半數(shù)以上節(jié)點存活)時是否能提供不間斷服務(wù)，因此，實驗中在模擬5個客戶端下，做了鎖服務(wù)的有效性和可用性測試，結(jié)果如表2、表3所示。

表2 鎖服務(wù)有效性測試Table 2 The lock service effectiveness testing

表3 鎖服務(wù)可用性測試Table 3 The Lock service usability testing

表2和表3的測試結(jié)果表明，本文實現(xiàn)的分布式鎖服務(wù)具有容錯性，對于一個具有2F+1個節(jié)點的系統(tǒng)，能保證在故障節(jié)點小于F+1的情況下集群正常提供服務(wù)，且能保證各節(jié)點間數(shù)據(jù)讀寫的一致性。

鎖服務(wù)設(shè)計的目標是能處理高并發(fā)情況下的數(shù)據(jù)一致性問題，所以響應(yīng)速度也是反映鎖服務(wù)可用性的一個指標。鎖服務(wù)的響應(yīng)速度主要體現(xiàn)在不同客戶端并發(fā)情況下多次讀寫不同大小數(shù)據(jù)的時間消耗，因此，實驗時在客戶端調(diào)用鎖服務(wù)的接口進行以下4個方面的測試。

(1)不同并發(fā)下5000次讀取的時耗，反映等量讀取下，不同并發(fā)的時耗;(2)不同并發(fā)下單個客戶端讀取100次的時耗，反映并發(fā)增長時單客戶端讀取的時耗;(3)不同并發(fā)下寫入1000次的時耗，反映等量寫入時，不同并發(fā)下的時耗;(4)10個并發(fā)，每個客戶端在100次寫入不同數(shù)據(jù)大小下的時耗，反映等量并發(fā)和寫入下不同數(shù)據(jù)量的時耗。本文采用Paxos算法實現(xiàn)了一個分布式鎖服務(wù)系統(tǒng)，并對其中產(chǎn)生沖突時帶來的延時進行了改進。為了驗證改進的有效性，在上述(4)的測試中，對基本算法和本文算法的時間消耗進行了實驗對比。上述測試結(jié)果如圖5、圖6所示。

圖5 等量讀寫下不同并發(fā)的時耗Fig.5 The different concurrent time consumption under the same amount of read and write

圖6 等量并發(fā)及寫時不同數(shù)據(jù)大小的時耗Fig.6 The different time consumption of data under the same amount of concurrent and write

圖5表明，實現(xiàn)的鎖服務(wù)在高并發(fā)等量讀取下，低并發(fā)和高并發(fā)的耗時比較接近。因為低并發(fā)時建立Session的時間比較少，而讀取不需要整個集群交互;高并發(fā)下單個客戶端讀取的次數(shù)較少，大量的客戶端可以并發(fā)讀取，因此消耗的總時間比較少。隨著并發(fā)客戶端的增加，讀取的時間消耗是近似成正比增加的。在等量寫入下，隨著并發(fā)的增加消耗的時間也隨之增加，這個結(jié)果與讀取結(jié)果不同的原因在于數(shù)據(jù)的寫入必須保證原子性，無法發(fā)揮并發(fā)的優(yōu)勢，消耗時間隨著并發(fā)增高是因為Session的建立會更多，結(jié)果中消耗時間的差異主要是Session數(shù)量的差異。

圖6反映了在不同鎖數(shù)據(jù)容量下寫入的性能，可以看出1000次寫入的時間差距十分小，但是有緩慢上升的總趨勢。同時也可以看出，本文改進后的算法，可以將寫數(shù)據(jù)時的一致性時間消耗提高4%～7%，其原因是本文改進的算法中，避免了沖突產(chǎn)生時的延遲。

上述的實驗結(jié)果表明，本文實現(xiàn)的分布式鎖服務(wù)具有較高容錯性，在服務(wù)集群硬件有限的情況下，能為高并發(fā)下分布式環(huán)境中的應(yīng)用提供高可用的數(shù)據(jù)一致性服務(wù)。

4 結(jié)束語

文章深入分析了Paox算法的特點，針對分布式環(huán)境下的應(yīng)用程序保證數(shù)據(jù)一致性的場景，設(shè)計了一個分布式鎖服務(wù)，為分布式應(yīng)用對共享資源的訪問提供了一種同步方式，使得節(jié)點間的同步和進程間的同步一樣簡單、可靠。該分布式鎖服務(wù)除了具有鎖原語的基本操作(創(chuàng)建、鎖定、釋放)外，還提供了方便分布式應(yīng)用處理共享資源的簡單數(shù)據(jù)存儲以及實時的鎖事件通知(鎖的釋放、數(shù)據(jù)修改等操作)，簡化了分布式應(yīng)用的設(shè)計。

［1］LAMPORT L.Fast paxos［J］.Distributed Computing，2006，2(19):79－103.

［2］RAO J，SHEKITA E J，TATA S.Using Paxos to build a scalable，consistent，and highly available datastore［J］.Proc.VLDB Endow.，2011，4(4):243－254.

［3］BUENO A M，RIGON A G，F(xiàn)ERREIRA A A，et al.Design constraints for third－order PLL nodes in masterslave clock distribution networks［J］.Communications in Nonlinear Science and Numerical Simulation，2010，15(9):2565－2574.

［4］MARZULLO K，MELING H，MEI A.Brief Announcement:When You Don’t Trust Clients:Byzantine Proposer Fast Paxos［C］.The 25th International Symposium，DISC 2011，Rome，Italy，2011.143－144.

［5］SANTOS N，SCHIPER A.Tuning Paxos for high －throughput with batching and pipelining［C］.The 13th International Conference，ICDCN 2012，Hong Kong，China，2012.153－167.

［6］許子燦，吳榮泉.基于消息傳遞的Paxos算法研究［J］.計算機工程，2011，37(21):287－290.

［7］MEDEIROS A.Zoo Keeper’s Atomic Broadcast Protocol:Theory and Practice［R］.2012.1 －19.

［8］MARANDI P J，MARCO PRIMI N S，PEDONE F.Ring Paxos:A High－throughput Atomic Broadcast Protocol［A］.In Dependable Systems and Networks(DSN)［C］.2010 IEEE/IFIP International Conference， 2010.527－536.