用zookeeper來構建的一種一致性副本協議

02-26

說明

我曾經在研究生期間負責開發過一個對可用性有要求的服務。為了保障該服務的可用性，我基於zookeeper設計了一個副本複製的解決方法，以確保當單個服務節點出現故障後，其他的備用服務節點能夠被選為主用服務節點，並對外提供服務，以保障整個系統不受單點故障的影響。與此同時，還能保障系統的數據一致性。本文介紹的內容就是這種解決方案的總結和抽象。

背景

在一個分散式系統中，多個有狀態的服務節點協同工作，完成某項系統功能。對於服務節點來說，保障其無故障運行，或者當其出現故障時，能夠快速恢復，是一件很有挑戰的事情。同時，帶有狀態的服務節點在快速恢復時，還需要恢復到故障出現前的服務狀態，更加地加大了系統設計的難度。

1. CAP定理

由Eric Brewer在2000年提出的CAP定理[1]，提出了在一個服務中，無法同時滿足數據一致性，服務可用性和分區容錯性。分區容錯性不僅僅包含網路分區，還應該包括宕機等異常情形。由於在分散式系統中，分區容錯性是必須被滿足的，因此分散式系統只能在數據一致性和服務可用性中做出選擇。

可用性指的是在足夠長的時間內，一個服務可用的時間。因此為了提高可用性，需要提高系統的可靠性，也就是系統連續無故障運行的時間，和需要減少系統在出現故障後的恢復時間。系統的可靠性與系統本身的實現與部署有關，不在本文討論的範圍。本文的設計，主要關注的是系統故障後的恢復時間。

對於數據一致性，保障的是後續操作對於先前操作的可見性。如果後續的讀取，無法讀到先前寫入的數據，會使得基於此系統的開發變得困難。

2. 多副本容災

為了能夠達成故障恢復的目標，傳統的做法是基於主用伺服器與備用伺服器之間做同步或者非同步數據複製，也就是primary-secondary協議[2]。當主用服務故障後，可以快速切換到備用服務。如果使用同步的數據複製，可以保障數據一致性，但是沒辦法保障系統可用性。因為無論主用服務還是備用服務出現了故障，都會導致服務不可用。因為必須將宕機服務重新啟動後才能恢復服務，從而導致系統故障恢復時間變長。如果使用非同步的數據複製，如果主用服務節點出現故障，可以很快切換到備用正常工作，從而縮短了故障恢復時間，因而提高了系統的可用性。但是有可能會出現數據不一致的情況，例如，用戶在之前寫入的數據，在後續的讀取中無法被讀到。

基於paxos[3]協議和raft[4]協議的系統是多副本容災中最常用的解決方案。因為paxos協議或者raft協議能夠保障數據一致性，並同時最大限度地保障系統可用性，只有當副本節點出現一半或以上的宕機情況時，才會影響可用性。否則，系統都能夠在短時間內恢復回來，並擁有一致性的數據副本。但是由於在系統中嵌入地正確實現無論是paxos協議，還是簡化的raft協議，都是相當有挑戰的事情。為了簡化上述系統的實現，我們可以藉助像zookeeper[5]等高可用的分散式協調服務，來幫助我們完成選主，和節點狀態監聽等工作。從而在此基礎上，完成日誌複製等工作，進而大大地簡化這個系統的實現。因此在這個系統設計中，我會使用zookeeper來完成選主和節點監聽等工作。

3. 設計考慮

無論是在paxos還是raft中，系統保障的是CAP中的數據一致性和分區容錯性，也就是CP。因為只要出現一半或者以上數量的副本節點宕機的情況，就會影響系統的可用性，因此paxos協議或者raft協議都不能保障完美可用性。本文設計的系統依然是保證了CAP中的數據一致性和分區容錯性，但是為了簡化實現，並沒有採用paxos或者raft的方案。而是借鑒了了primary-secondary協議的做法，在主用節點和備用節點之間做同步日誌複製。但同時引入了zookeeper來監聽節點的存活狀態，從而縮短了系統恢復可用的時間，提高了可用性。

因為本文設計的系統保障了數據一致性，犧牲了系統的部分性能和可用性。但是這種選擇是值得的，保障了數據一致性的系統，可以屏蔽數據不一致給業務層帶來的煩惱，從而降低業務開發的工作難度。

1. 複製狀態機

在本文介紹的系統中，需要把服務節點抽象成一個狀態機[6]。每個節點包含一組狀態，一個轉換函數和一個輸出函數。客戶發往服務節點的請求都可以抽象為一個操作日誌，作為轉換函數和輸出函數的輸入。多個相同初始狀態的狀態機，輸入相同的操作日誌序列，最終能夠得到相同的狀態，並且輸出相同的結果。因此，系統只需要在多個副本節點中同步複製操作日誌流，即可實現系統的狀態複製。

2. 選主實現

在多個複製狀態機，也即服務節點中，需要選舉出一個主用服務節點，來對外提供讀寫服務。為了簡化實現，本系統使用了zookeeper中的分散式鎖服務來實現選主功能。多個服務節點在啟動後都會向zookeeper中的同一目錄下，去請求創建同一個臨時鎖文件。只有第一個服務節點能夠創建成功，接著成為主用服務節點。其他服務節點成為備用服務節點，並去監聽臨時鎖文件的狀態。當主用服務節點發生故障，導致主用服務節點與zookeeper的租約到期，臨時鎖文件會被zookeeper刪除，然後會通知其他的備用服務節點。備用服務節點接著可以再次請求創建臨時鎖文件，進而成為新的主用服務節點。

3. 節點存活狀態監聽

每一個節點都會在zookeeper上創建一個臨時文件，並協商最大租約時間。當節點出現故障，租約到期後，臨時文件會被刪除，並向所有節點廣播該節點的故障信息。當一個故障的節點恢復後，會重新到zookeeper上去創建臨時文件，zookeeper會向其他節點廣播該節點重新上線的消息。以上機制可以確保每一個節點都擁有了當前所有節點的存活狀態。

4. 日誌複製

主用服務節點在接受客戶的操作日誌流時，需要把日誌流複製到備用服務節點上。每條日誌都帶有唯一自增序號。

對於每一條操作日誌，主用服務節點會將操作日誌順序寫入磁碟，確保操作日誌的持久化，同時將操作日誌發往所有的備用服務節點。所有的備用服務節點在接受到操作日誌後，同樣要把操作日誌順序寫入磁碟，然後向主用服務節點返回確認。主用服務節點只要等到當前操作日誌已經被寫入本機磁碟，以及已經接收到除自己之外，所有的存活的備用節點的確認消息，就可以認為當前操作日誌同步完成，可以去處理下一條操作日誌。

在處理返回客戶端當前操作日誌處理完成，並去處理下一條日誌之前，需要在zookeeper上記錄當前最新確認成功提交的日誌序號。在zookeeper上記錄最新commit的日誌序號，zookeeper會將最新commit的序號廣播給所有節點，節點上就可以提交給狀態機了，主用節點上還要返回客戶端。最新commit日誌序號，記錄在zookeeper上，還可以用於以供後續節點宕機恢復以及新節點加入時使用。新恢復或啟動的節點，只需到zookeeper上查詢最新commit的日誌序號，就可以向其他節點請求自己所缺失的日誌了。

5. 故障恢復

當節點出現故障時，主要分這兩種類型。

首先是主用節點出現故障。此時，新的主用節點會被選出來。由於主用節點和備用節點之間採用了同步的日誌複製方式，所以備用節點可以快速地成為主用，而不用去其他節點上拉取未同步的日誌。

接著，如果是備用節點出現故障。此時，主用節點的日誌流同步複製操作會出現阻塞。當備用節點與zookeeper的租約到期後，備用節點故障的消息會被zookeeper廣播到主用節點上。此時，主用節點的日誌流同步工作可以繼續下去。

當一個節點從故障中恢復回來，或者加入一個新節點。此時，該節點狀態會落後於其他節點，該節點會向zookeeper獲取最新確認成功提交的日誌序號，然後向其他節點拉取缺失的操作日誌。在該節點完成日誌同步之前，無法應答其他節點和客戶端的任何請求。

因此，該系統中，出現機器宕機和機器恢復時，都會導致系統短暫的不可用，無法處理操作日誌，從而無法應答客戶端的寫入請求。但是，仍然能夠應答客戶端的讀取請求。

6. 日誌提交

日誌在複製到所有的存活節點上後，最後需要確認提交狀態。在很多一致性複製演算法中，會將日誌複製和提交的流程分離開。首先主用節點發起日誌複製，複製成功後，再發起日誌提交流程。當收到提交請求後，狀態機就可以執行日誌了。在本文設計的系統中，當完成日誌複製後，主用節點會將提交日誌id更新到zookeeper，通過zookeeper來廣播其他節點操作日誌的提交消息。通過zookeeper來分發和記錄最新提交日誌的id，雖然在系統性能上會有部分損耗，但是卻能極大的簡化系統的實現。

當一個新的節點加入複製組，或者一個之前故障的節點恢復後，提交日誌都需要恢復到和zookeeper上的commit日誌序號一樣的位置，才能正常對外提供服務。因此，在新加入節點，或者節點恢復時，會導致系統暫時不可用，不可用的時間長短與節點日誌恢復的時間有關。

當日誌完成提交後，狀態機就可以執行操作日誌了，這裡的狀態機與具體的應用有關，不屬於本文要討論的範圍。

系統設計

1. 總體架構設計

該系統的總體架構中，需要有zookeeper集群，作為分散式協調服務，還有多個節點。其中有一個主節點，與多個備用節點。主用節點向備用節點同步日誌。

架構圖如下：

2. 系統介面

系統向用戶暴露日誌提交介面，並提供同步或者非同步的提交確認。

通過向用戶暴露日誌提交介面，用戶可以通過客戶端，向系統提交操作日誌，系統在完成日誌在多節點的複製後，會提交給狀態機來執行。

3. 與Zookeeper交互的模塊設計

Zookeeper在本文設計的系統中主要負責三個功能，選主，節點存活狀態監聽和記錄最新一次成功提交的日誌序號。

因此在zookeeper上的目錄結構如下所示：

節點存活狀態監聽

在每個節點啟動後，都會去zookeeper的/nodes目錄下面，創建一個臨時文件，文件名稱為本節點的地址，並在zookeeper上註冊監聽/nodes目錄下面子節點的變化。

當有節點出現故障後，與zookeeper的心跳中斷，租約到期。之後zookeeper會刪除該故障節點創建的臨時文件，並通知其他複製組節點，關於/nodes目錄下的子節點變化。其他節點就可以實時知道當前所有節點的存活情況。

選主

在節點註冊完自身狀態後，還需要去創建/lock的臨時文件，如果創建成功，則成為主用節點。如果文件已存在，說明已經存在其他主用，則只需要監聽/lock文件狀態，並成為備用節點。當主用出現故障後，與zookeeper的租約也會到期，文件也會被刪除，並通知備用節點。備用節點接收到/lock文件被刪除的通知後，可以再次去創建/lock文件。

記錄提交日誌序號

在完成每一條日誌的複製後，主節點會去zookeeper上更新最新的成功提交日誌序號。Zookeeper會把日誌序號變化的事件，廣播給所有節點。

4. RPC設計

整個系統的實現，需要每一個節點上都實現以下功能的RPC。

處理主節點發送的日誌

主節點會將客戶端發送過來的操作日誌，發往其他的備用節點。備用節點在接收到操作日誌後，會將日誌寫入磁碟，並返回確認消息。

處理日誌拉取請求

在新節點，或者先前出現故障的節點恢復後，需要向其他節點拉取日誌，同步到與其他節點一致的日誌狀態，然後才能正常對外服務。所以，這裡同樣提供了一個日誌拉取的RPC調用。

功能實現

1. 節點上線

當節點上線後，首先在zookeeper的/nodes目錄中創建一個臨時文件。然後嘗試在zookeeper上創建/lock臨時文件，如果創建成功，則成為主用節點，否則，成為備用節點。

接下來，執行狀態恢復的流程。讀取zookeeper上/logid文件內的最新提交的日誌序號，並讀取本節點的最新提交的日誌序號。比較兩個日誌序號，如果本節點已提交日誌落後於其他節點，則調用PullLog的RPC，完成日誌拉取並恢復。在日誌恢復完成之前，無法響應客戶端和其他節點的RPC請求。

完成日誌恢復後，可以正常響應客戶端和其他節點的RPC請求。

處理流程如下：

2. 主節點處理操作日誌

當主節點接受到客戶端的操作日誌，首先寫入磁碟，然後將日誌通過HandleOpLog的RPC，發往備用節點，等待備用節點RPC都返回確認後，則認為該日誌複製成功，修改zookeeper上/logid文件內容為該日誌序號。如果發往某個備用節點的HandleOpLog的RPC調用失敗，則不斷重試，直到成功，或者該備用節點被zookeeper檢測到出現故障。

處理流程如下：

3. 備用節點處理操作日誌

當備用節點通過PRC HandleOpLog接收到主節點發送過來的操作日誌後，首先需要寫入磁碟，等待日誌持久化成功後，再返回成功確認。

4. 狀態機執行

當主用節點更新/logid 中的最新提交日誌序號後，zookeeper會將日誌序號廣播給所有的節點，然後節點就可以推進狀態機的執行日誌。

5. 選主實現

在本系統中，選主是依賴於zookeeper來實現的，通過多個節點搶佔創建zookeeper上的/lock文件。當主節點出現故障後，/lock文件會被zookeeper刪除，然後廣播通知其他備用節點。接收到通知的節點，可以再次搶佔創建/lock文件。

優化

1. 日誌批量操作

在主節點接受到客戶端的操作日誌的時候，先不急著寫入磁碟和發往備用節點。可以緩存一段時間的操作日誌，然後再一起寫入磁碟和發往備用節點，這樣可以提高系統的吞吐量。但是主節點由於需要緩存日誌，所以系統的響應延遲會增長。所以系統要根據業務場景來選擇緩存時間。

2. 日誌流水線操作

主節點不需要等到之前的操作日誌都成功寫入磁碟和複製到備用節點上後，才能發起新操作日誌的複製操作。而是可以並行發起多條日誌的寫入磁碟和複製到備用節點的操作，從而某條日誌的複製阻塞，不會影響到後面日誌的複製操作。不過，主用節點在zookeeper上更新已提交日誌序號的操作，日誌序號必須是增長的。而且，狀態機執行操作日誌也是順序執行。

3. 日誌拉取

如果剛加入的節點，日誌落後其他節點太多，可以通過生成snapshot文件，新節點拉取snapshot，來加快日誌和狀態的恢復。

4. 數據讀取

由於在這個系統中，各個節點的狀態是強一致的，所以數據讀取可以在系統的任意一個節點上執行，從而降低主節點的系統負荷。所以本文介紹的是一個單寫多讀的系統，通過增長節點個數，可以優化數據讀取性能，不過會導致寫入變慢，因為日誌同步的代價會加大。

如果業務中對讀取到的數據不要求強一致，允許一定的延時，可以考慮加入非同步複製的弱一致節點。弱一致節點不參與主節點的選舉和同步的日誌複製，只會非同步的向普通節點拉取日誌，並對外提供弱一致性讀的功能。

討論

1. 與客戶端交互

客戶端在向主節點提交操作日誌後，主節點需要向客戶端返回確認。返回確認的時間應該是在將日誌序號更新到zookeeper的/logid中後，因為此時就可以確認日誌已提交。

如果系統由於異常，比如網路中斷，機器宕機等，導致客戶端超時未得到日誌提交結果。此時，進入未知狀態，客戶端需要先向系統讀取日誌提交情況，根據情況來決定是否重新執行日誌提交。

2. 與paxos和raft的比較

在本系統中，只要有一台機器出現故障，就會導致系統的不可用，不可用的時間與zookeeper的租約時長有關。但是在paxos中，單台機器的故障不會導致系統的不可用。如果是帶有leader的paxos實現，如果leader所在的機器出現故障，新選出的leader需要執行兩階段流程恢復日誌狀態，恢復時間與新leader恢復日誌的時間有關。所以paxos上如果leader所在節點出現故障，才會導致系統不可用，不可用時間與選主和日誌恢復時間有關。在raft中，leader會由日誌最長的機器擔任，所以raft不存在日誌恢複流程。所以raft系統同樣只受leader故障的影響，不可用時間與選主時間有關。

在有節點加入的時候，本系統同樣會出現不可用的情況，不可用時間與日誌恢復的時間有關。但在paxos和raft的系統中不會有這種問題。

在paxos和raft中，只要出現一半或者一半以上的節點故障，系統將沒辦法自動恢復，需要人工介入。但是在本系統中只有所有節點出現故障，才會導致系統沒法自動恢復。人工介入系統恢復會導致不可用時間延長，但是由於一半或者一半以上的節點出現故障的概率極低。而且在通常情況下，出現一台機器宕機後就應該在不影響服務的前提下，加入新的副本，從而防止出現過半節點故障的情形發生。從這個角度來說，本文介紹的系統可用性要差於paxos和raft。

3. 適用場景

本文介紹的系統由於日誌需要同步複製到所有的節點，因此不適用於部署在網路故障率高，網路延遲高的廣域網場景，僅僅適用於數據中心內的區域網部署。

測試

1. 測試環境

測試環境由6台共有雲上的主機組成，這幾台主機處於同一個數據中心。其中，有三台用於部署zookeeper集群，有三台伺服器用於部署本文設計的高可用系統集群。

2. 測試說明

本測試主要集中於當系統中出現節點宕機後，系統可用恢復所要的時間。而對於系統的整體讀寫性能，以及當新節點加入後的系統可用恢復，都與系統具體實現有關，不在本測試討論的範圍。

集群中有三台伺服器，其中有一台主用節點，和兩台備用節點。當備用節點故障後，主用節點無法向其複製日誌，因此日誌提交無法推進，此時系統處於不可用狀態。接著當故障的備用節點與zookeeper的租約到期，然後zookeeper通知主用節點，此時主用節點更新存活節點列表，不會向該故障節點複製日誌。此時系統故障恢復，進入可用狀態。

當主用節點出現故障時，系統同樣進入不可用狀態。故障的主用節點與zookeeper的租約到期後，zookeeper會通知其他備用節點，主用失效的消息。備用節點首先要搶佔創建zookeeper上的/lock文件，接著更新存活節點列表，最後系統的故障才可以恢復，進入可用狀態。

主用節點調用HandleOpLog向備用節點複製日誌的RPC超時時間設置為1s。

下述測試結果，與具體的程序實現有很大的關係，我根據研究生期間基於此設計開發的程序的測試結果，得出了下面的結果。

3. 測試結果

備用節點宕機恢複測試結果如下：

主用節點宕機恢複測試結果如下：

這裡測試的不可用時間，根據的是主用節點和備用節點的日誌數據估算而來，可能存在些誤差，待後續再設計合理的測試場景來驗證。

最後

本文是通過在高可用實踐中的一點思考，從而設計出來的一種在保障數據一致性的條件下，解決系統高可用的設計思路。相比於paxos和raft協議，由於本設計需要依賴於分散式協調服務，因此在性能等方面不佔優勢。但是本設計依然有其自身的優點，比如實現簡單，易於理解，從而能更容易地證明其實現的正確性。

本文提到的一致性副本協議，正在解耦出來，準備成為一個通用的多節點副本拷貝庫，目前還在開發中。。。

參考文獻

[1] Brewer, Eric A. "Towards robust distributed systems." PODC. Vol. 7. 2000.

[2] 劉傑. 分散式系統原理介紹

[3] Lamport L. The part-time parliament. ACM Transactions on Computer Systems (TOCS). 1998

[4] Ongaro D, Ousterhout JK. In search of an understandable consensus algorithm. InUSENIX Annual Technical Conference 2014

[5] Hunt P, Konar M, Junqueira FP, Reed B. ZooKeeper: Wait-free Coordination for Internet-scale Systems. InUSENIX annual technical conference 2010

[6] Schneider FB. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys (CSUR). 1990