楊春明 杜 炯

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

隨著企業(yè)應(yīng)用系統(tǒng)對(duì)計(jì)算能力需求的增長(zhǎng)，傳統(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ù)不可用)等問(wèn)題，越來(lái)越多的大型系統(tǒng)逐漸從單節(jié)點(diǎn)模式轉(zhuǎn)向分布式的云計(jì)算模式。

在分布式的計(jì)算環(huán)境中，解決計(jì)算節(jié)點(diǎn)之間的數(shù)據(jù)同步、分布式資源競(jìng)爭(zhēng)以及單節(jié)點(diǎn)故障自主恢復(fù)等問(wèn)題是系統(tǒng)正確性和可靠性的基本保證。其中最基本的是節(jié)點(diǎn)之間的數(shù)據(jù)一致性問(wèn)題，即保證節(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ì)中一致性的問(wèn)題，可以應(yīng)用在數(shù)據(jù)復(fù)制、命名服務(wù)、配置管理、權(quán)限設(shè)置和號(hào)碼分配等場(chǎng)合［1－2］。然而很多時(shí)候系統(tǒng)在設(shè)計(jì)之初并沒(méi)有考慮到在分布式環(huán)境下的高可用和一致性的問(wèn)題，當(dāng)系統(tǒng)逐漸變大之后，系統(tǒng)的一致性和高可用性變得尤為重要。一些系統(tǒng)采用主從復(fù)制模式(Master/slave)來(lái)解決該問(wèn)題［3］，但主從復(fù)制模式的一致性主要依賴(lài)主節(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)程間的同步一樣簡(jiǎn)單、可靠。該分布式鎖服務(wù)除了具有鎖原語(yǔ)的基本操作(創(chuàng)建、鎖定、釋放)外，還提供了處理共享資源的簡(jiǎn)單數(shù)據(jù)存儲(chǔ)以及實(shí)時(shí)的鎖事件通知(鎖的釋放、數(shù)據(jù)修改)等操作，可以簡(jiǎn)化分布式應(yīng)用的設(shè)計(jì)。

1 Paxos算法

Paxos算法是用來(lái)解決在不可靠的網(wǎng)絡(luò)環(huán)境中多個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)達(dá)成可靠一致性共識(shí)的算法。假設(shè)現(xiàn)在有一個(gè)可以提出提案的節(jié)點(diǎn)集合。一個(gè)一致性算法保證在這些提案中只有一個(gè)能被選中，如果沒(méi)有提案被提出則沒(méi)有提案被選中。如果一個(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è)角色來(lái)表示:Proposers，Acceptors 和 Learners［4］，其 中，Proposer 向Acceptor提交提案(proposal)，提案中含有決議(value);Acceptor審批提案;Learner獲取并執(zhí)行已經(jīng)通過(guò)審批的提案中含有的決議。

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

算法的操作流程分為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)求而且它沒(méi)有回復(fù)一個(gè)比n大的Prepare請(qǐng)求，則接受這個(gè)Accept請(qǐng)求。通過(guò)這兩個(gè)階段的消息傳遞和實(shí)例執(zhí)行，可保證數(shù)據(jù)和操作的一致性。Paxos算法采用了投票選舉的形式，通過(guò)數(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í)間較長(zhǎng)、通信負(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)上，用戶(hù)或其他應(yīng)用的請(qǐng)求也會(huì)分流到不同的節(jié)點(diǎn)，為了提供不間斷的服務(wù)及保證各節(jié)點(diǎn)數(shù)據(jù)的一致性，需要一個(gè)分布式的鎖服務(wù)來(lái)提供上述功能。本文了采用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ù)將部署在該類(lèi)節(jié)點(diǎn)上，客戶(hù)端向服務(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ò)地位一致，從長(zhǎng)時(shí)間跨度來(lái)看，服務(wù)集群中沒(méi)有中心單點(diǎn)。鎖節(jié)點(diǎn)有如下3種角色:

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

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

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

分布式的鎖服務(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ì)終止之前的提案過(guò)程，如果2個(gè)Proposer在這種情況下都轉(zhuǎn)而提出一個(gè)編號(hào)更大的提案，那么就可能陷入活鎖。這就難免會(huì)產(chǎn)生沖突，增加系統(tǒng)的時(shí)間延遲。

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

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

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

(3)Follower無(wú)法跟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)稱(chēng)為一個(gè)view，初始為0，每次選舉后view自增1;

(3)trans:提案事務(wù)序號(hào)，初始為0，每一次提案通過(guò)后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)之間通過(guò)投票來(lái)選舉Leader，每次投票包含 leaderid，state，view，trans和 myid，其中 leaderid是本次投票Leader的ID號(hào)，state是投票者的狀態(tài)。

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

在開(kāi)始選舉時(shí)，首先將節(jié)點(diǎn)狀態(tài)設(shè)為L(zhǎng)ooking，推舉自己作為L(zhǎng)eader，通知所有的鎖節(jié)點(diǎn);然后只要當(dāng)前服務(wù)器狀態(tài)為L(zhǎng)ooking且不為stop，進(jìn)入循環(huán)，不斷地讀取其它鎖節(jié)點(diǎn)發(fā)來(lái)的投票、進(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ù)同步主要有兩類(lèi):數(shù)據(jù)初始化同步、數(shù)據(jù)寫(xiě)同步。鎖數(shù)據(jù)的所有操作都記錄在日志中，每個(gè)操作有一個(gè)事務(wù)ID來(lái)標(biāo)識(shí)自己，記為trans。

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

同步流程如下:

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

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

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

圖4 投票者為L(zhǎng)eading或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ù)寫(xiě)操作包括新建鍵、修改鍵、刪除鍵以及鎖的相關(guān)操作，這里使用Paxos算法來(lái)同步數(shù)據(jù)，但是只允許Leader提出議案，具體流程如下:

(1)Leader或Follower向Leader提交一個(gè)寫(xiě)操作請(qǐng)求;

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

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

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

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

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

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

實(shí)驗(yàn)主要在單臺(tái)機(jī)器下使用多個(gè)終端來(lái)模擬多個(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ā)訪(fǎng)問(wèn)時(shí)的容錯(cuò)性和響應(yīng)速度，數(shù)據(jù)的容錯(cuò)性主要由鎖服務(wù)的功能及節(jié)點(diǎn)故障后數(shù)據(jù)的一致性來(lái)體現(xiàn)，響應(yīng)速度則主要看多個(gè)客戶(hù)端在多次讀寫(xiě)情況下不同數(shù)據(jù)量的時(shí)間消耗。

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

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

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

表2和表3的測(cè)試結(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ù)讀寫(xiě)的一致性。

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

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

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

圖6 等量并發(fā)及寫(xiě)時(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è)客戶(hù)端讀取的次數(shù)較少，大量的客戶(hù)端可以并發(fā)讀取，因此消耗的總時(shí)間比較少。隨著并發(fā)客戶(hù)端的增加，讀取的時(shí)間消耗是近似成正比增加的。在等量寫(xiě)入下，隨著并發(fā)的增加消耗的時(shí)間也隨之增加，這個(gè)結(jié)果與讀取結(jié)果不同的原因在于數(shù)據(jù)的寫(xiě)入必須保證原子性，無(wú)法發(fā)揮并發(fā)的優(yōu)勢(shì)，消耗時(shí)間隨著并發(fā)增高是因?yàn)镾ession的建立會(huì)更多，結(jié)果中消耗時(shí)間的差異主要是Session數(shù)量的差異。

圖6反映了在不同鎖數(shù)據(jù)容量下寫(xiě)入的性能，可以看出1000次寫(xiě)入的時(shí)間差距十分小，但是有緩慢上升的總趨勢(shì)。同時(shí)也可以看出，本文改進(jìn)后的算法，可以將寫(xiě)數(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é)束語(yǔ)

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