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

楊春明 杜 炯

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

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

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

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

1 Paxos算法

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

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

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

(3)一個(gè)節(jié)點(diǎn)永遠(yuǎn)不會(huì)得知某個(gè)提案被選中除非它真的被選中了。

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

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

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

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

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

在分布式環(huán)境中，相同的應(yīng)用或數(shù)據(jù)會(huì)部署在不同的節(jié)點(diǎn)上，用戶或其他應(yīng)用的請(qǐng)求也會(huì)分流到不同的節(jié)點(diǎn)，為了提供不間斷的服務(wù)及保證各節(jié)點(diǎn)數(shù)據(jù)的一致性，需要一個(gè)分布式的鎖服務(wù)來提供上述功能。本文了采用Paxos算法構(gòu)建了一個(gè)分布式環(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é)點(diǎn)構(gòu)成了服務(wù)集群的鎖節(jié)點(diǎn)，應(yīng)用或數(shù)據(jù)將部署在該類節(jié)點(diǎn)上，客戶端向服務(wù)集群發(fā)出服務(wù)請(qǐng)求，服務(wù)集群將采用Paxos算法選擇響應(yīng)請(qǐng)求的節(jié)點(diǎn)，并將對(duì)數(shù)據(jù)的操作同步到其他各節(jié)點(diǎn)。圖中Leader和Follower的網(wǎng)絡(luò)地位一致，從長時(shí)間跨度來看，服務(wù)集群中沒有中心單點(diǎn)。鎖節(jié)點(diǎn)有如下3種角色:

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

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

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

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

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

2.2 Leader選舉算法

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

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

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

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

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

(4)Leader的周期達(dá)到，進(jìn)行計(jì)劃的 Leader選舉;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

同步流程如下:

(1)Follower向Leader發(fā)送同步請(qǐng)求，在請(qǐng)求中附上自己最后一次數(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提交一個(gè)寫操作請(qǐng)求;

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

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

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

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

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

3 實(shí)驗(yàn)及結(jié)果分析

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

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

容錯(cuò)性測試主要測試提供的鎖服務(wù)功能是否滿足要求，同時(shí)測試在節(jié)點(diǎn)故障(半數(shù)以上節(jié)點(diǎn)存活)時(shí)是否能提供不間斷服務(wù)，因此，實(shí)驗(yàn)中在模擬5個(gè)客戶端下，做了鎖服務(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é)果表明，本文實(shí)現(xiàn)的分布式鎖服務(wù)具有容錯(cuò)性，對(duì)于一個(gè)具有2F+1個(gè)節(jié)點(diǎn)的系統(tǒng)，能保證在故障節(jié)點(diǎn)小于F+1的情況下集群正常提供服務(wù)，且能保證各節(jié)點(diǎn)間數(shù)據(jù)讀寫的一致性。

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

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

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

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

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

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

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

4 結(jié)束語

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

［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］.計(jì)算機(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.