Paxos優化算法下的數據庫元數據一致性方法研究

摘 要： 通過對Paxos算法的研究與分析，從縮減階段過程、減少Learner通信量、使用快照機制進行節點崩潰恢復和使用批量提交方式節省通信量等方面改進了基本的Paxos算法，并搭建仿真實驗環境，測試驗證優化的Paxos算法的效果及性能，得出結論。

關鍵詞： 元數據一致性； Paxos； 閾值； Leader節點

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2013）13?0065?03

A consistent approach of NoSQL database metadata based on Paxos algorithm

ZHOU Yi?fan

（Navy Military Representative Office Stationed in Xingping District， Xingping 713107， China）

Abstract： Based on the research and analysis of Paxos algorithm， proceeding from shrinking the stage process， reducing the amount of Learner communication traffic， realizing the node crash recovery of snapshot mechanism and saving communication traffic by mass delivery mode， the basic Paxos algorithm was improved， and a simulation experiment environment was created. The effectiveness and performance of the optimized Paxos algorithm were tested and verified. The conclusion is given.

Keywords： metadata consistency； Paxos； threshold； Leader node

1 Paxos算法及其優化

Paxos是基于消息傳遞的算法，由于其較大的通信量，使得維護數據一致性的過程代價過大，會降低可靠性與可用性的提升的空間。所以，迄今為止Paxos也只是應用于分布式鎖環境中。對其進行優化的目的是減少算法的通信量從而得到性能的提升。

批量處理在通信系統是常見的優化手段，也可以把它用到Paxos中。與其來一次請求就進行一次Paxos實例過程，可以將多次請求累積然后只提交一次Paxos，這樣在很大程度上減少了通信量。一般而言，閾值設置的越大，通信量越少。但是這個閾值比較難定，很多因素影響閾值的設定：

（1）系統對數據包的大小的限制（例如，UDP包的大小最大是64 KB）；

（2）閾值越大，Leader需要花更多時間等待客戶請求，可能平均開銷比一次請求一次處理的更大；

（3）閾值越大，提交過程中出現故障（信息丟失或出現故障），則可能導致這些數據丟失，目前的業務場景可以接受這樣的以高性能換取數據可靠性（丟幾條或幾百條監測記錄不影響整個系統的使用）。

可以從策略上對批出處理流程進行優化，在請求數達到設定的閾值的情況下，提交進行Paxos實例過程；若未達到且未超過設定的接收請求時間，則繼續接收客戶端請求；若超時則立即提交。而對閾值和超時時間則可根據實際情況自行設定。閾值設定為1時，退化為提交一次執行一次的情況。

經上述處理，能節省Learner的通信量、使用快照機制加快了Learner節點的同步以及使用批量處理的方式一次性提交，這些優化措施均有效地減少了通信量，使性能得到提升。改進后的Paxos算法過程可以描述如下：

每次客戶端提交Key?value（KV），都進行下面流程（只說明Leader第一次請求之后的過程）：

（1）若請求數達到設定的閾值或設定的超時時間則將數據（KVs）提交給Leader；否則繼續接收客戶端請求。

（2）Leader給當前的KVs分配paxosID即instance id，并作為ACCEPT消息發送給Acceptors 中的一個多數派。

（3）若大多數派都響應了ACCEPT消息，Leader便把該KVs連同paxosID一起發送給所有的Learner。

（4）Learner在接收到Leader的消息后會檢查消息中的paxosID，看之前所有的paxosID是否已經學習過了。如果之前的均已學習過了，則把當前paxosID對應的KVs持久化到元數據表；否則Learner要請求Leader學習之前的paxosID對應的消息，若Learner落后的數據比較多，則先同步最近快照，然后再同步到最新狀態，以保證Learner與Leader一致。

2 容錯性分析

對Paxos算法經過以上優化后，分析其容錯性。在異步通信的環境中，可能出現的故障有：副本節點崩潰或失效后恢復；網絡分區；消息丟失、重發或延遲。以下分別討論這些故障出現后Paxos的處理機制。

（1）圖1是一次正常的Paxos實例過程（instance）

圖1 Paxos實例過程順序圖

（2）Acceptor，Learner失效情況

副本隨時可以失效。在[2N+1]個副本中，Paxos算法最多允許有[N]個副本失效。最常見的是Acceptor或Learner失效，但仍存在一個大多數節點存活。當以上情況發生時，一致性過程仍可繼續進行。當Proposer提交prepare請求后，有一個Acceptor失效，但仍有2個Acceptor存活，Proposer收到大多數派的回復，則一致性過程繼續進行。

（3）Proposer（Leader）失效情況

當Proposer失效后，會重新選出Leader，并再次發送新的prepare消息。如圖2所示。

（4）網絡分區

由于短暫的網絡故障，其他副本無法與Leader聯系，這時，其他副本可能會選出新的Leader。當網絡恢復后，舊的Leader并不知道有新Leader的存在，仍然認為自己是Leader，這樣就有兩個Leader同時存在。由于之前說過，每個Leader都會有一個生存期，舊Leader的lease過期后，就只會存在一個Leader，Paxos過程繼續正常進行。當然這期間兩個Leader會互相競爭。

（5）消息丟失、重發或延遲情況

副本之間的消息可以被復制，丟失或者發生任意時長的延遲。以下是消息丟失的情況，消息丟失后，Proposer會提高編號重新發送。

以下是消息延遲的情況，由于網絡的不穩定，Proposer發送prepare（N）消息后，等待超時，又發送了一個prepare（N+1）消息，Acceptor對N+1承諾后，又收到了prepare（N）消息，Acceptor發現已承諾編號大于N，于是拒絕該消息。如圖3所示。

圖2 Leader失效順序圖

圖3 消息延遲順序圖

這樣可以處理以下故障：

（1）非Leader節點失效不影響系統的正常運行。

（2）當Leader節點失效時，PaxosLease算法會選取一個新的節點作為Leader節點。新Leader節點可以繼續處理剩余工作。

（3）失效節點恢復是容易的。由于之前運行狀態都進行了持久化記錄，故節點從崩潰中恢復時可根據記錄追蹤到最新的狀態。

（4）節點從網絡分區故障恢復后，節點之間的數據仍保持一致。

（5）節點之間的消息可以丟失、重發或者發生任意時長的延遲。

3 優化的Paxos算法仿真測試

研究采用了5臺PC機i5?2450M 2.5 GHz，2 GB內存，操作系統位64位CentOS 6，每個節點均充當了Paxos算法中的三個角色。采用了基于不可靠的UDP協議下的Socket編程實現了基本Paxos算法和改進的Paxos算法。重點分析了算法運行正確性以及性能和容錯性。

就使用兩階段提交協議（two?phase commit），使用基本Paxos算法（basic paxos）和使用改進的Paxos算法（improved paxos）主要測試以下幾個方面的內容：分別模擬3臺機器和5臺機器正常運行的情況；模擬3臺機器中1臺機器宕機、剩余2臺機器正常運行的情況；分別模擬5臺機器中1臺機器宕機、剩余4臺機器正常運行的情況以及模擬其中2臺機器宕機、剩余3臺機器正常運行的情況。模擬3臺機器測試批量提交優化的運行性能。

以下每個過程執行了100次數據提交，每次提交的間隔過程為1 s。圖4和圖5是3臺機器時運行時間的仿真結果，圖6是5臺機器時運行時間的仿真結果，圖7是3臺機器進行批量提交的仿真結果。其中，使用3臺機器時，第4次后有1臺機器宕機（分非Leader節點宕機和Leader節點宕機兩種情況）；使用5臺機器時，第4次后有1臺機器宕機，第7次后有2臺機器宕機。

圖4 三臺機器時運行時間比較（非Leader宕機）

如圖4所示，前三次正常運行時，improved paxos比basic paxos提交速度快。在第四次提交開始，斷掉1臺非Leader機器，basic paxos和improved paxos正常運行，由于少了1臺機器，通信時間減少；而兩階段提交協議出現了大量的提交失敗。

圖5 三臺機器時運行時間比較（Leader宕機）

如圖5所示，在第四次提交時斷掉了1臺Leader機器，此時會重新選舉新的Leader節點，而導致短暫的性能降低。兩階段提交協議仍是出現了大量的提交失敗。

如圖6所示，在第4次提交時斷掉了1臺機器，basic paxos和improved paxos正常運行，由于少了1臺機器，通信時間減少，在第7次斷掉第2臺機器時，通信時間進一步減少。而兩階段提交協議一直是出現大量提交失敗。

圖6 三臺機器時運行時間比較

接下來模擬3臺機器測試批量提交優化的運行性能，這里設置每100條提交一次，提交超時時間為5 s，每次測試運行60 s。如圖7所示，使用批量提交的improved paxos比basic paxos平均每秒提交數略高，通信負載明顯降低。

圖7 三臺機器批量提交運行比較

4 結 論

從以上實驗可以得出以下結論：

（1）本實現的系統具有容錯性，對于一個有2N+1個節點的系統，能夠保證在節點宕機數小于N+1的情況下系統正常運行；basic paxos算法和improved paxos算法都能夠實現各運行節點數據間的一致性。并且系統中節點數越少，達成協議的速度越快。

（2）在正常運行情況下，improved paxos算法比basic paxos算法達成協議的速度要快，節省了運行時間；消息個數減少，通信負載明顯降低；由于通信負載的降低，改進后的算法平均每秒提交數略有提高。兩階段提交協議雖然保證了較快的性能，但是一旦節點出現故障，將會導致大量的數據不一致，所以兩提交協議的可用性較差。

（3）Paxos算法在Acceptor或者Proposer出現故障時，最終會使Learner獲得一致的提交結果，需要多余的執行過程來彌補不確定的批準結果，這里會有一定的通信代價，然而節點的損毀畢竟是小概率事件，這并不會在實際應用中產生較大的計算資源的影響，重要的是提高了可用性。

（4）使用批量提交優化在一定程度上加快了Paxos算法達成協議的速度，節省了運行時間，改進后的算法平均每秒提交數略有提高。

參考文獻

[1] SANTOS N， SCHIPER A. Tuning Paxos for high?throughput with batching and pipelining [C]// Proceedings of The 13th International Conference on Distributed Computing and Networking. [S.l.]： ICDCN， 2012： 153?167.

[2] RAO Jun， SHEKITA E J. TATA S， et al. Using Paxos to build a scalable， consistent， and highly available datastore [J]. Proceedings of the VLDB Endowment， 2011， 4（4）： 243?254.

[3] Anon. The apache cassandra project [EB/OL]. [2012?10?04]. http：//www.cassandra.apache.org.

[4] KRISTINA C， MICHAEL D， MONGO D B. The definitive guide [M]. Sebastopol： O′Reilly， 2010.

[5] Anon. MongoDB sharding and failover [EB/OL]. [2012?11?25]. http：//www.mongodb.org/display/DOCS/Sharding+and+Failover.

[6] 葉國權，寧洪.元倉庫與源數據庫的元數據同步策略的研究與設計[J].現代電子技術，2010，33（17）：146?149.