王志瑞 王幕天 劉正濤 黃慧

摘 要： 為了能在分布式環(huán)境下使用FibJs開發(fā)出持續(xù)高可用性的服務，并能保證分布式環(huán)境下的數據一致性，研究了分布式系統(tǒng)中的一致性問題。分析了分布式一致性算法Paxos，研究了該算法的工作原理，并對該算法進行了優(yōu)化。根據算法思想設計了一種適應于分布式環(huán)境下的數據一致性的方案，采用FibJs對該方案進行了實現，并在集群環(huán)境下對該方案進行了檢驗。驗證結果表明，該方案能夠很好的解決分布式環(huán)境下數據一致性問題。

關鍵詞： 一致性算法； Paxos； 分布式系統(tǒng)； 數據一致性； FibJs

中圖分類號：TP399 文獻標志碼：A 文章編號：1006-8228（2015）12-13-05

Research and application of distributed consensus algorithm

Wang Zhirui， Wang Mutian， Liu Zhengtao， Huang Hui

（Department of Computer and Information Engineering， Sanjiang University， Nanjing， Jiangsu 210012， China）

Abstract： In order to use FibJs to develop a continuous high availability service in distributed environment and to ensure the consensus of data in the environment， this paper studies the consensus problem in distributed systems. The distributed consensus algorithm Paxos is analyzed； the working principle of the algorithm is studied and then is optimized. According to the idea of the algorithm， a data consensus scheme adapted to the distributed environment is designed； the scheme is implemented by using FibJs and has been verified in a cluster environment. The verification results show that the proposed scheme can solve the consensus problem in distributed environment.

Key words： consensus algorithm； Paxos； distributed system； data consensus； FibJs

0 引言

當今，企業(yè)對計算機的依賴越來越強，為了保證企業(yè)的關鍵業(yè)務不出現故障，出現了雙機熱備，雙機雙工相關的技術來保證系統(tǒng)的穩(wěn)定性，但是這些方案的投資和部署難度都比較大，對于一些傳統(tǒng)的應用支持比較好，而對于一些新技術的支持不是特別的好。為了能在分布式環(huán)境下使用FibJs開發(fā)出持續(xù)高可用性的服務，并能保證分布式環(huán)境下的數據一致性。

本文研究了分布式系統(tǒng)中的一致性問題，研究了分布式一致性算法Paxos的原理，并對該算法進行了優(yōu)化?；赑axos算法的思想設計出了一種適用于分布式環(huán)境下的數據一致性的方案。采用FibJs對該方案進行了實現，并在集群環(huán)境下對該方案進行了檢驗。結果表明，該方案能夠很好地解決分布式環(huán)境下的數據一致性問題。

1 一致性算法Paxos

Paxos是由微軟的Leslie Lamport提出的一種基于消息傳遞的分布式一致性算法，其解決的問題是：一個分布式系統(tǒng)中如何就某個決議達成一致。Paxos可以應用在數據復制、命名服務、配置管理、權限設置和號碼分配等場合[1-2]，是解決分布式一致性問題最有效的算法之一?，F實中一些優(yōu)秀軟件的心臟，如Cassandra，Google的Spanner數據庫，分布式鎖服務Chubby都是利用Paxos算法設計的。

在分布式系統(tǒng)中節(jié)點崩潰、網絡故障時常會發(fā)生，Paxos算法側重解決的便是在一個可能發(fā)生上述異常的分布式系統(tǒng)中就某個值達成一致，保證不論發(fā)生何種異常，都不會破壞系統(tǒng)的一致性。

2 算法分析及優(yōu)化

2.1 算法分析

在Paxos算法中，有三種角色，Proposer，Acceptor，和Learner[3-4]，一個節(jié)點可以兼有多重角色。Proposer提出提案，提案是一個有序對構成，M是整數類型的提案編號，V是提案的值；Acceptor收到提案后可以接受提案，若提案獲得多數Acceptor的接受，則稱該提案被批準；Learner只能學習被批準的提案。Paxos算法的最終目標便是只有一個提案被選定，即確保在一次算法實例中只產生一個value。

提案在批準過程中需要滿足三個條件才能保證數據的一致性[1]：①提案只有被Proposer才可以批準；②每次只能批準一個提案；③只有提案被批準后Learner才可以獲取這個決議。為了保證提案的惟一性，只有Acceptor沒有收到編號大于M的請求時，才可以批準編號為M的提案。在這些約束的基礎上可以將提案的批準過程分為三階段[7-8]：Prepare階段，Accept階段，Notify階段。

Prepare階段（初次提出提案，查看是否能夠被接受）：Proposer設定一個新的提案編號M，并將prepare請求發(fā)送給Acceptors中的多數派；Acceptor收到請求之后，如果提案編號大于它之前己批準的任何提案編號，則Acceptor將自己上次批準回復給Proposer，并承諾不再批準小于M的提案；否則拒絕Proposer，Proposer收到拒絕后，會設定一個新的提案編號M+n，繼續(xù)向Acceptors中的多數派發(fā)送prepare請求。

Accept階段（再次確認提案是否被所有的Acceptors接受）：當Proposor收到了多數派Acceptors確認回復之后，便進入了Accept階段。它需要向所有回復prepare請求的Acceptors發(fā)送一個針對[M，V]的accept請求，V就是收到響應中編號最大的M提案的值，若響應中不包含任何值，那Proposor可以自由決定value。只要Acceptor沒有對編號大于M的提案響應，Acceptor就可以最終批準這個請求，如果在Prepare階段之后，Acceptor又對大于M的提案作了響應，則Acceptor就可以拒絕這個請求。

Notify階段（學習過程）：當Proposor收到多數派Acceptors的accept請求的確認回復后（反之則回到Prepare階段重新提交新的提案），該提案被選定，就向所有的Learner發(fā)送通知，Learner接受通知更新Value。

2.2 算法優(yōu)化

Paxos是基于消息傳遞的算法，當主機數量較多，Proposer角色和Acceptor角色較多時，在每個提案的批準過程中，會出現過多的通信量，使得數據一致性代價過高，因此在實現中需要對Paxos算法進行優(yōu)化。

Proposer數量過多時，當Proposer提案被拒絕后，Proposer會不斷的提高編號繼續(xù)提交，因此會出現過多的通信量，為了杜絕這種不斷競爭的現象，可從所有的Proposer中競選出一個或少量幾個主Proposer，只允許主Proposer提出提案，杜絕惡性競爭，減少提案批準過程中的通信量。但是也會出現單點故障問題，因此在系統(tǒng)運行過程中如果發(fā)現主Proposer出現故障，所有的從Proposer就通過Paxos算法競選出一個新的主Proposer，接替原主Proposer的工作。

3 數據一致性方案的設計與實現

Paxos算法已經有了一些實現方案，其中包括Google的分布式鎖服務chubby，Google的Spanner數據庫，開源分布式NoSQL數據庫系統(tǒng)Cassandra等[6]，這些都是當前比較優(yōu)秀的數據一致性產品。為了能夠在開源項目FibJs的開發(fā)過程中保證數據一致性，我們在FibJs環(huán)境下根據Paxos算法思想對數據一致性進行了設計與實現，并對該方法進行了實驗檢驗。

3.1 一致性方案的設計

Paxos算法設計的角色是三個：Proposer，Acceptor，Learner。本方案在設計過程中，根據Paxos算法思想設計了如下三個角色：Looking，Follower和Leader。要求集群機器數是奇數，最少三臺，并通過DNS服務器維護集群內主機的IP和域名信息。

Looking角色：當一個新的節(jié)點加入后，它的角色默認為Looking，Looking會向所有的節(jié)點發(fā)送選舉消息來確認Leader，可能是系統(tǒng)中已有的Leader，或者重新選舉出的Leader。當發(fā)現Leader宕機后，其他節(jié)點也會轉變?yōu)長ooking并執(zhí)行重新Leader選舉。

Follower角色：當選舉結束后，一個節(jié)點會變成Leader，其他節(jié)點發(fā)現Leader選舉出來后則會成為Follower。Follower角色可以當做Paxos算法中的Acceptor和Learner，用來批準Leader的提案和執(zhí)行Leader的決議。

Leader角色：選舉完成后，某個節(jié)點會轉變成Leader。它負責處理客戶端發(fā)送的所有請求。對于寫請求，Leader會采用一致性協議將請求廣播給所有Follower，得到過半的Follower批準后再通知Follower執(zhí)行；對于讀請求，可由Leader直接執(zhí)行。它也管理著Follower節(jié)點，檢測節(jié)點是否正常通信，并提供告警功能。

集群中每個服務節(jié)點都是平等的，都可以被選舉為Leader和Follower角色，因而在架構上也是相同的。每個節(jié)點都包含三個基本功能模塊。

⑴ 網絡通信模塊：主要用來實現節(jié)點之間的通信，并在通信的基礎上實現心跳連接（檢測節(jié)點間的連接狀態(tài)）。

⑵ Paxos算法模塊：主要用來實現角色轉換和Leader選舉，是系統(tǒng)中比較重要的模塊。

⑶ 數據管理模塊：用于執(zhí)行數據的讀/寫操作和節(jié)點間的數據同步，當有新節(jié)點或者故障恢復后的節(jié)點時，通過數據同步來保證與其他節(jié)點的數據一致。

3.2 一致性方案的實現

3.2.1 網絡通信模塊

該模塊主要包括節(jié)點間的網絡通信和心跳連接兩個主要部分，其中節(jié)點通信主要采用RPC（Remote Procedure Call Protocol）框架實現，FibJs中內置有RPC框架的功能，直接使用即可。心跳連接主要用來檢測Follower與Leader之間的通信狀態(tài)，并告知Follower當前的數據日志編號M，當Follower發(fā)現和Leader不一致時通知數據管理模塊進行數據同步。

具體算法流程：首先由Follower發(fā)起keepAlive請求，然后等待一段時間后接收響應。當Leader收到Follower的keepAlive請求時，會將Follower的sid寫入阻塞隊列，再阻塞一段時間后響應給Follower，同時將該sid移除阻塞隊列，等待下次keepAlive請求再寫入。而Follower接收到響應后會立刻再次發(fā)起keepAlive請求。這樣Leader上總會有keepAlive請求阻塞，Leader也從而得知它與Follower之間的通信是否正常。阻塞時間的設定可根據服務器的壓力進行調節(jié)，以確保運行高效。

當某個Follower等待了兩倍于阻塞時間后仍未接收到Leader的響應，則它會認為Leader已不存在或已崩潰，然后它會轉變成Looking狀態(tài)，并開始發(fā)起選舉。同樣的，Leader也會定期檢查是否存在Follower節(jié)點通信異常（通過檢測阻塞隊列內節(jié)點的個數），若大多數節(jié)點都無法與其通信，那么Leader會自己轉變成Looking狀態(tài)并開始選舉。

3.2.2 Paxos算法模塊

該模塊主要包括角色轉換和Leader選舉。Leader選舉借助Paxos算法思想，利于多數派的投票來確定，選舉模塊包括了選舉啟動，消息傳輸，選舉算法實現這幾個步驟。

首先確定投票所用到相關參數。

sid：用來惟一標識每個節(jié)點的整數值，值越大則權重越大。在這里表示為選舉的Leader，開始時Looking都會選舉自己為Leader。

clock：用來區(qū)分不同的選舉輪次，初值為0，每進行一輪值加1。

leader：當Leader和Follower接收到投票時會返回當前系統(tǒng)中的leader。

voteSet：Looking接受到投票時，會返回voteSet，即自己的投票集合。

選舉算法的工作機制如下，算法中AB階段的流程圖見圖1。ACD階段流程圖見圖2。

[節(jié)點狀態(tài)][A][Looking] [B][sid，clock] [Looking] [比較clock] [比較sid][相等] [＼&忽略＼&＼&][小][＼&更新clock

清空投票

sid加入投票集合＼&＼&] [大][A] [＼&更新clock＼&＼&] [大][＼&sid加入投票集合＼&＼&][A] [接受返回值] [Voteset，clock] [Voteset，clock] [比較clock] [大][Follower] [Leader] [Voteset，clock][leader，clock]

圖1 AB階段流程圖

A：發(fā)送投票：當節(jié)點狀態(tài)為Looking時，會向集群內所有節(jié)點發(fā)送投票，投票中包含投票集合中最大的sid和clock，初次發(fā)送時會用自己的sid。

B：接受投票：不同狀態(tài)的節(jié)點接受到投票后處理方式不同。

B.1：Looking節(jié)點，會根據投票中clock的值進行處理。

B.1.1：接收到的clock比自己當前的clock大，更新clock，并清空自己的投票集合，將sid加入自己的投票集合，并返回voteSet和clock，然后從A開始繼續(xù)投票。

B.1.2：接收到的clock比自己當前的小，則忽略該投票，并將voteSet和clock返回給對方。

B.1.3：接收到的clock與自己當前的一致，若接收到的sid比自己大，則更新投票sid，并將該sid加入自己的投票集合，然后從A開始繼續(xù)投票；若接收到的sid比自己的小，并返回voteSet和clock。

[C] [比較clock] [包含參數] [相等][＼&更新clock＼&＼&] [大] [leader] [判斷sid][＼&忽略＼&＼&][D] [大][＼&更新投票＼&＼&] [voteSet] [包含參數] [leader] [voteSet][＼&更新投

票集合＼&＼&][A] [小] [voteSet，clock

leader，clock]

圖2 ACD階段流程圖

每個Looking都會維護一個投票集合，當接收到投票時便要根據clock進行更新，然后判斷集合中是否存在節(jié)點獲得的投票已經過半，如果存在，等待一段時候后再觀察是否有變話，若有變化則繼續(xù)執(zhí)行選舉，若無變化則跳至D。

B.2：Follower節(jié)點或者Leader節(jié)點：會直接返回當前的Leader和clock，并判斷clock是否比自己大，如果大就更新。

C：接受返回值：Looking節(jié)點會根據返回值的clock值進行處理。

C.1：若clock比自己當前的大，就更新自己的clock。若返回值中包含Leader參數，則跳至D；若包含voteSet參數，則更新投票集合，并從A開始繼續(xù)投票。

C.2：當clock和自己當前的相同時，若包含Leader參數，則跳至D；若包含voteSet參數，判斷sid，若大則更新投票，并從A開始繼續(xù)投票。

C.3：一般不會有clock比自己當前的小，若出現則通常為網絡故障?？芍苯雍雎栽摲祷刂怠?/p>

D：確定Leader：Looking會根據Leader的sid是否是自己來轉變自己的角色，若為Follower，則與Leader進行心跳連接，當一段時間都未得到Leader的響應，則放棄，并轉變?yōu)長ooking開始新一輪選舉；若為Leader，就等待Follower與自己連接，當一段時間沒有過半Follower連接，則轉變?yōu)長ooking開始新一輪選舉。

3.2.3 數據管理模塊

數據同步模塊用來實現數據的讀寫操作，并保證節(jié)點之間的數據同步。在數據寫入過程中為了能夠記錄每一次的寫操作，并保證節(jié)點間的數據一致性，引入了編號M，每寫入一次數據則加1；為了保證Follower批準的提案和執(zhí)行的提案是同一個提案，引入了惟一編號uuid，具體的算法工作機制如下。算法的流程圖見圖3。

[uuid是否相同][＼&將M+1和

寫操作寫

入日志＼&＼&][Follower][Leader][＼&同步數據

寫數據，寫日志

M+1＼&＼&] [M+1，uuid，寫操作][客戶端] [發(fā)送數據操作] [操作類型] [寫操作][＼&取最大編號M

生成uuid＼&＼&] [Follower][sid，M+1，uuid][＼&記錄uuid＼&＼&] [M+1>N

Leader==sid] [是] [Leader] [accept] [否

neject] [Accept

占多數] [是] [否] [讀操作]

圖3 數據讀寫流程圖

A：客戶端將數據操作請求發(fā)送給Leader節(jié)點。

B：Leader判斷請求類別，如果讀操作直接返回讀取結果；如果寫操作，取出當前保存的最大編號M，生成一個uuid，并將編號M+1同Leader的sid一起發(fā)送給Follower，并保存最大編號為M+1。

C：Follower接收到Leader的寫請求時會先判斷編號M+1是否比本地保存的最大編號N大，并且它的Leader是否為sid，然后記錄uuid，并返回accept，否則返回reject。

D：當Leader收到多數Follower的accept反饋后，就將編號M+1和寫操作內容同uuid發(fā)送給所有Follower，并將操作寫入日志，然后反饋給客戶端寫入完成。若收到多數reject，則應該是發(fā)生了Leader更換，先檢查與自己連接的Follower是否為大多數，若還是大多數，則跳至B進行重試。

E：Follower接受到執(zhí)行請求時，判斷uuid是否相同，然后從Leader的日志中讀取編號N到編號M的寫操作，執(zhí)行并寫入本地日志，再執(zhí)行請求的寫操作并寫入日志，并更新N為M+1。

4 實驗檢驗

為了方便測試，我們組建了由三臺服務器構成的集群，每臺服務器上使用FibJs作為服務運行框架，并放置了兩個SQLite文件，分別用來存儲數據和日志。

服務啟動后，首先進行的是Leader選舉，選舉成功后開始檢測心跳，當接受到客戶端的寫請求后進行數據寫入，如果執(zhí)行成功則將對應的數據操作腳本輸出。具體運行結果見圖4。

圖4 Leader選舉與執(zhí)行數據寫操作

5 結束語

本文給出的方案能夠將FibJs開發(fā)的服務部署到集群中，并對外提供持續(xù)的可用性，后期考慮對該方案繼續(xù)研究和優(yōu)化，以期將該方案設計成FibJs的一個組件，能夠集成到FibJs中，讓更多的人員參與該方案的優(yōu)化和使用。希望該方案可為其他系統(tǒng)的設計提供參考。

參考文獻（References）：

[1] 許子燦，吳榮泉.基于消息傳遞的Paxos算法研究[J].計算機

工程，2011.37（21）：287-290

[2] 高石玉，艾中良，劉忠麟.應用Paxos算法構建自組織網絡[J].

計算機工程與應用，2014.6：88-91，204

[3] Lamport L. Paxos Made Simple[J].ACM SIGACT News，

2001.32（4）：18-25

[4] Jim G，Lamport L. Consensus on Transaction Commit[J].

ACM Transactions on Database Systems，2006.1：133-160

[5] 楊春明，杜炯.一種基于Paxos算法的高可用分布式鎖服務系

統(tǒng)[J].西南科技大學學報，2014.2：60-65

[6] 趙瑞芬.云存儲中基于PAXOS算法的數據一致性研究[J].科

技視界，2013.34：64，121

[7] 趙黎斌.面向云存儲的分布式文件系統(tǒng)關鍵技術研究[D].西

安電子科技大學，2011.

[8] 陳鴻欽.基于Paxos的Leader選舉與分布式日志復制系統(tǒng)[D].

東南大學，2012.

[9] 倪超.從Paxos到ZooKeeper分布式一致性原理與實踐[M].

電子工業(yè)出版社，2015.