一種基于Paxos算法的高可用分布式鎖服務系統(tǒng)

楊春明 杜 炯

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

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

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

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

1 Paxos算法

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

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

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

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

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

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

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

2 基于Paxos算法的分布式鎖服務

2.1 分布式鎖服務的結構

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

圖1 分布式鎖服務系統(tǒng)結構Fig.1 The structure of distributed lock service system

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

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

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

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

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

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

2.2 Leader選舉算法

在Paxos算法中每個成員都是Proposer，根據算法一個編號更大的提案會終止之前的提案過程，如果2個Proposer在這種情況下都轉而提出一個編號更大的提案，那么就可能陷入活鎖。這就難免會產生沖突，增加系統(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)人工干預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)之間的轉換關系如圖2所示。

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

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

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

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

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

圖2 鎖節(jié)點之間的狀態(tài)轉移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)定投票(此時對應的鎖節(jié)點已結束選舉)，兩類投票分別用states和stable_votes集合記錄。

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

2.3 數據同步算法

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

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

同步流程如下:

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

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

圖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把收到的數據操作日志與本地的操作日志合并并將其應用于數據。

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

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

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

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

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

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

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

3 實驗及結果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結束語

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

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