基于RDMA和NVM的大數據系統一致性協議研究

吳昊^1,2, 陳康^1,2, 武永衛^1,2, 鄭緯民^1,2

1 清華大學計算機科學與技術系，北京 100084

2 北京信息科學與技術國家研究中心，北京 100084

摘要：分布式的存儲系統以及計算系統是構造大數據處理系統的基礎。系統的高可用性是任何一個分布式系統的基石，高可用技術一般依賴于一致性協議。討論了經典的非拜占庭的分布式一致性協議以及新技術發展下的RDMA通信協議與NVM存儲介質，通過RDMA和NVM的結合獲得了更高性能的高可用系統。改進了一致性協議，使其能夠更好地利用RDMA與NVM的特性。實現的系統在保證系統數據一致和可用的同時，有效地提高了協議實現的性能。實驗表明，相比于現有的系統，實現的系統能夠得到40%的性能提高。

關鍵詞：大數據 ; 分布式系統 ; 一致性協議 ; 遠程內存直接訪問 ; 非易失存儲器

論文引用格式：

吳昊, 陳康, 武永衛, 鄭緯民. 基于RDMA和NVM的大數據系統一致性協議研究. 大數據[J], 2019, 5(4):89-99

WU H, CHEN K, WU Y W, ZHENG W M.Research on the consensus of big data systems based on RDMA and NVM. Big Data Research[J], 2019, 5(4):89-99

1 引言

隨著分布式系統規模的增大，服務器宕機和網絡服務中斷等各種故障使得分布式系統中斷服務的可能性越來越高。為了解決單點故障問題，維護系統的高可用性，分布式系統在實際應用中一般采用多副本的備份技術。這種方法不僅可以保證系統的高可靠性，還可以對請求進行相應的負載均衡，以提高服務的并發數量和擴展性。但是，這種多副本技術同樣會帶來系統一致性、可用性的問題。設計者通常使用分布式一致性協議來保證多副本系統中多臺機器上數據的強一致性。另外，隨著遠程內存直接訪問（remote direct memory access，RDMA）等新型網絡技術和非易失存儲器（non-volatile memory，NVM）等新型存儲介質的生產和普及，所有的系統服務在網絡通信和存儲過程中的性能都會得到巨大的提高，這為提高一致性系統的性能提供了機會。目前的一致性協議在新的網絡技術和存儲介質中的實現都不能完全地利用RDMA和NVM的特性。本文將展開這方面的研究，結合RDMA和NVM的特性，設計更加高效的分布式一致性協議。

2 概述

2.1 一致性協議概述

一致性問題是指集群節點在網絡狀態和服務器節點的運行狀態都不可以控制的情況下，仍然能夠對整個集群的某一問題或者集群的狀態達成一致的共識。一般來說，如果分布式系統中有2f+1個副本服務器在工作，一致性協議一般可以容忍f個副本服務器出現故障，即只要系統中存在f+1個副本服務器正常工作，那么分布式系統就可以正常地對外提供服務。圖1展示了分布式一致性協議的簡要發展過程和工業應用。其中，兩階段提交協議 通過投票階段和正式提交階段的兩輪消息交互，使得某項決定達成一致。而三階段提交協議是兩階段提交協議的阻塞問題的優化方案。Quorum 算法通過限定參與讀寫操作的副本的最小數目，實現讀寫操作的互斥，從而支持多副本的并發更新。在Lamport提出了Paxo s算法后，很多類Paxos算法陸續出現，以適應不同的應用環境。如Multi-P axos就是通過選舉出一個領導者，減少了Paxos協議的第一輪通信，避免了多個節點同時提交指令時的沖突問題。ZAB（ZooKeeper atomic broadca st）協議是Multi-Paxos的變種，是一種能夠支持崩潰恢復的原子廣播算法。Raft算法是研究者為了降低Paxos算法的復雜性而設計的一個管理日志的一致性協議。還有一些弱領導者協議（如Fas t Paxos、Generaliz ed Paxos、FGGC、EPaxos）也有不同方面的優化，但是協議相對復雜，實際應用很少。

圖1???分布式一致性協議的簡要發展過程與工業應用

2.2 RDMA概述

RDMA網絡技術是一種新型網絡技術，它可以繞過遠端CPU直接讀取遠端內存，同時還具有高吞吐量和低時延的特性，這些特性使其可以有效地降低集群中網絡通信的開銷。目前，RDMA 網絡在數據中心已經被逐漸普及。

RDMA的通信模式分為可靠連接（reliable connection，RC）、不可靠連接（unreliable connection，UC）和不可靠的數據報（unreliable datagram，UD）3種模式。RDMA支持的通信原語分別是RDMA Write、RDMA Read、Send、Receive以及原子操作（Atomic）。其中，Read和Write是單邊的操作。單邊的讀寫操作可以繞過遠端的CPU。Send和Receive是雙邊的操作，雙邊的操作要求通信雙方的CPU必須同時參與才能完成通信。原子操作包括Fetch and Add和Compare and Swap等。不同的連接模式支持不同的RDMA原語操作，因此本文采用RC模式以及單邊的讀寫操作。

2.3 NVM概述

NVM是新型存儲設備，它能夠在設備斷電之后仍然保存其中存儲的數據。新型非易失性存儲器（如PC M）具有可字節尋址、低時延、高密度等特點，其能耗比磁盤低90%以上，同時讀寫的時延也和DRAM相近。但是與DRAM不同的是，NVM的讀寫速度不對稱，其讀數據的速度快于寫數據的速度。而且類似于固態硬盤（solid state drive， SSD），其擦寫次數存在上限，因此其壽命有限，也需要考慮磨損均衡的問題。

表2比較了不同類型的存儲介質在能耗、讀寫時延以及最大擦寫次數等方面的性能。從表2可以明顯看出各種不同存儲介質的區別。NVM在很多方面和系統內存使用的動態隨機存取存儲器（dynamic random access memory，DRAM）相似，尤其是其讀寫速度快、容量大、可字節尋址的特性，使其有望代替主存。NVM還具有DRAM不具有的非易失性的特點，這使其可以應用到一致性系統中，作為日志存儲的存儲器，提高一致性系統的性能。

3 基于RDMA和NVM的一致性協議

3.1 RDMA、NVM與一致性協議的結合

在傳統的一致性協議中，協議除了要處理指令的共識問題，還要保證指令的持久化?？紤]到集群可能出現全部宕機的問題，因此要保證指令在系統重啟時可以從持久化的存儲中恢復出來。傳統的一致性協議使用磁盤或SSD作為持久化指令的存儲介質。隨之而來的問題是協議中的領導者在復制日志的時候，不知道日志是否已經被持久化。領導者必須等待其他副本進程回復日志已經被持久化的消息后，協議算法才能繼續。由于存儲介質的問題，即使在RDMA通信環境下，這個問題也同樣存在。如APUS 也只是在系統的網絡層設計中用RDMA網絡替換了傳統的以太網，副本進程通過RDMA網絡接收復制的指令消息，將其存入SSD后回復領導者。這種方式并沒有完全利用RDMA的特性，尤其是RDMA繞過遠端CPU的特性。

將NVM作為一致性系統中的存儲介質，可為解決上述問題提供幫助。首先， NVM可以替代內存與RDMA直接進行通信，即服務器可以使用RDMA對遠端的NVM直接進行讀寫；其次，NVM還具有持久性，使得使用RDMA通信后的消息同時也被持久化。這樣就使得通信和持久化兩個問題都通過RDMA的Write操作解決了。使用NVM后，領導者通過RDMA復制日志時，就不需要等待副本進程的回復，通過檢查自身的狀態就可以判斷日志是否被持久化到副本進程中，進而繼續判斷日志的共識過程是否成功。當領導者使用RDMA的Write操作成功之后，遠端的RDMA網卡會發送一個ACK到本地的網卡中，在本地網卡的完成隊列（completion queue，CQ）中生成一個發送消息完成的狀態。在RDMA的設計中，本地服務器首先調用RDMA Write操作向遠端服務器發送消息，遠端的服務器網卡收到該消息后會立即返回給本地服務器網卡一個ACK消息。因此Write操作的ACK消息不能確保數據被寫入NVM中，即數據不能確保是否被持久化。為了解決這個問題，筆者設計在每個Write操作之后，立刻發送一個RDMA中的Read操作。該Read操作讀取大小為0 byte的數據，讀取的遠端內存地址即Write操作中寫入遠端內存的地址，如Hyper Loo p中的設計。這個Read操作會保證對應位置的數據已經被成功寫入NVM中。本地程序只需要檢測本地網卡的CQ中對應Read操作的狀態，就可以判斷對應的數據是否被成功寫入NVM。

使用RDMA網絡和NVM存儲為網絡中斷后的領導者選舉引入了新的問題。傳統協議的解決方法是每次發送指令時，指令都會附帶一個系統版本信息。這是一個整型數值，用來存儲系統版本。每次系統重新選舉領導者的時候，這個版本號就會增加1。當副本進程收到指令的時候，副本進程判斷指令附帶的版本信息，如果是舊的版本就忽略掉，從而避免舊的領導者對整個日志的破壞。但是由于筆者提出的方案繞過了副本機器的CPU，副本進程無法對消息進行判斷，因此還需要對選舉的流程進行修改，以保證協議的正確性。

本文針對RDMA網絡和NVM存儲介質的特性對Multi-Paxos協議進行了修改，并對修改后的協議進行了實現。本文修改了協議流程中對一致性成功的判定方式以及領導者選舉和日志恢復中的部分流程，利用RDMA Write操作的繞過目標服務器CPU的特性、NVM的持久性和可字節尋址的特性，使得修改后的協議具有低時延、高吞吐量和低CPU消耗等特點。下面將介紹修改后的具體流程。

3.2 日志復制

圖2為日志復制流程。在協議正常運行的情況下，日志的編號和復制都由領導者負責?？蛻舳送ㄟ^RDMA的Write操作將指令發送給領導者服務器。領導者服務器會不斷輪詢每一個客戶端對應的在本地注冊的內存，檢測是否有客戶端發送指令過來。當領導者服務器接收到從客戶端發送過來的指令后，領導者為該條指令分配一個序列號和這個指令在整個系統日志里的地址。然后，領導者服務器將該指令復制到其他的服務器上，領導者通過RDMA的Write操作直接將這條指令寫入對應副本機器中的NVM中，指令的地址即剛才分配的地址。當領導者將指令發送到副本機器后，領導者會繼續發送對應位置的一個Read操作，這個Read操作讀取的字節為0，用于保證數據被持久化到NVM中。同時這個Read操作可以在Write操作后直接使用，不需要等待Write操作的返回。領導者可以通過從RDMA的完成隊列中獲取相應Read操作對應的消息，判斷指令是否被成功寫入。領導者通過計算單個指令發送成功的次數判斷指令是否可以提交，當單個指令發送成功的次數為f+1次，即領導者已經成功地將該指令發送到f+1個副本機器中時，即可認為該指令已經完成了共識過程。領導者提交該指令，發送commit消息給所有的副本服務器，同時執行該指令，并將執行的結果返回給相應客戶端。如果指令的發送次數沒有超過f+1次，領導者將不斷發送該指令給未接收到的副本服務器，直到其接收到該指令為止。

圖2???日志復制流程

3.3 領導者選舉與日志恢復

由于協議是強領導者協議，因此當領導者出現故障時，整個系統就要重新選舉出一個新的領導者，才能繼續對外提供服務。每個領導者都對應著一個任期編號（term）。當副本進程檢測到與領導者的連接中斷時，該副本進程會進入選舉領導者的狀態。它會將term值增加1，并向其他的副本服務器發送選舉其為領導者的消息，在該消息中附帶自己的term值。然后等待其他副本進程為其投票。其他副本進程收到該消息后，根據自身情況回復相應消息：如果副本進程檢測到與領導者的連接暢通，那么回復不投票給發送該指令的副本進程，并將領導者的編號信息發送給該副本進程；如果其檢測到與領導者也斷開了連接，但是已經投票給了其他term值更高的副本進程，那么將回復不投票給發送該指令的副本進程；如果其檢測到與領導著也斷開了連接，并且沒有投票給任何其他的副本進程，那么回復投票給發送該指令的副本進程。當某一個副本進程收到大于f+1個為其投票的信息后，該副本進程的角色變為領導者，并進行日志恢復的過程，同時阻止其他副本進程進行新一輪的選舉。

系統在復制指令的時候使用了RDMA的Write操作將指令寫入副本進程的NVM中，領導者直接繞過了副本進程的CPU和操作系統。這樣的好處是減少了副本進程的CPU消耗，同時降低了時延；壞處是副本進程不會判斷寫入的指令是否是由新的領導者寫入的。為了解決這個問題，系統在選舉領導者的時候，當副本進程收到某個副本進程選舉領導者成功消息的時候，該副本進程就會斷開與舊的領導者的RDMA連接。這樣使得舊的領導者無法寫入任何新系統中存活的副本進程的NVM中，就不會破壞整個日志。圖3為領導者選舉流程。

圖3???領導者選舉流程

進入選舉過程后，收到選舉消息的副本機器會把與之前的領導者之間的連接切斷，銷毀相應的資源。斷開連接的副本服務器若想重新加入系統集群中，要向領導者發送join指令，該指令表明有新的副本服務器要加入系統。領導者收到該指令后，同樣為該指令分配其在日志中的位置，并將其復制到其他副本服務器中。當領導者成功將其發送到了f+1個副本服務器上時，表明該指令已經成功提交到日志中，該副本服務器可以加入系統中。同時，系統中副本機器的多數派的數量也要發生相應的改變，領導者在復制日志的時候也要將日志復制到該副本機器中。

4 相關工作

近年來，使用硬件和一致性協議結合的方法對一致性協議進行優化的工作也有很多。NetPa xos利用網絡交換機中消息的順序實現Paxos算法，同時該工作還能夠兼容Open Flow的應用程序編程接口（application programming interface， API），具有很高的應用價值。NO Paxos則首先設計了一個特殊的網絡，以支持有序不可靠廣播（ordered unreliable multicast， OUM），并在該網絡下實現一致性協議。由于該網絡是有序的網絡，因此要比Paxos等簡單很多。同樣還有將Paxos協議實現在可編程路由器中，如使用P4語言實現Paxos協議的Switchc y-Paxos。也有學者使用現場可編程門陣列（field programmable gate arr ay，FPGA）在網絡層實現ZAB協議，性能也非常優秀。

目前使用RDMA網絡實現一致性 協議的工作有DARE系統和APUS。其中， DARE可以看作將Raft協議在RDMA環境下的實現，其利用RDMA的原語對Raft進行了修改。APUS則是Multi-Paxos算法在RDMA中的實現，同時使用SSD存儲日志。與本文的實現比較，二者各有不同的缺陷。DARE由于協議的設計，需要兩輪通信才可以提交指令，時延比本文的工作要高很多，同時DARE只能運行在內存中，并沒有做日志的持久化工作。APUS則存在之前提到的問題，雖然它是一輪通信的協議，但是其領導者必須等待副本的回復才可以判斷日志是否可以提交，時延也比本文的工作高。在吞吐量方面，三者相差不大。由于APUS沒有提供直接測試的客戶端程序，因此第5節中將本文工作和DARE進行了對比。

除了一致性協議的工作，使用RDMA進行數據復制的 工作還有Tailwind。Tailwind的復制過程中使用RDMA的Write操作進行數據復制，與本文的工作有一定程度的重疊。不過Tailwind和本文的工作也有3點區別。一是Tailwind使用的是Primary-Backup的模式，使用f+1個副本容忍f個副本發生錯誤，而本文使用的是傳統的一致性協議設計，使用2f+1個副本容忍f個副本發生錯誤，提供了更高的可用性。在f個副本發生錯誤后，仍然能夠繼續對外提供服務。二是Tailwind的工作中提供了關于數據恢復的方法，但是沒有關于選舉領導者的工作。三是在數據持久化的工作中，本文使用NVM硬件和RDMA中的Read操作確保數據的持久性。但是Tailwind在保證數據持久性方面沒有任何的工作，只是假設服務器存在備用的電源設備，并且服務器能夠在斷電后利用備用的電源設備將PCIe控制器和RDMA網卡緩存中的數據寫入SSD中。因此Tailwind并不具有任何應用價值。同時Tailwind沒有提供其實現的代碼，因此本文工作也無法和其進行測試對比。

5 系統性能測試

5.1 測試環境

本文使用C++語言對修改后的MultiPaxos協議進行了實現，同時使用 基于InfiniBand網絡設施的服務器集群對實現的一致性系統進行測試。集群由10臺服務器構成，每臺服務器的配置見表3。其中，筆者使用5臺服務器作為一致性系統的服務端，另外5臺服務器作為客戶端，負責和服務端進行通信并發送請求。由于目前市面上沒有可用的NVM硬件，因此使用內存模擬測試，同時由于NVM的寫時延比內存高，因此在測試時，筆者修改了CentOS內核，使得系統內存的寫時延增加150 ns，從而匹配NVM性能。

?

5.2 性能測試

在性能測試中，本文主要從時延和吞吐量兩個方面對一致性系統進行測試。在測試系統時延的過程中，筆者分別對數據大小為8 byte、32 byte、128 byte、512 byte和2 048 byte的指令提交時延進行了測試。每次測試都將指令分別提交，即當客戶端收到一個指令提交成功的回復后，再提交下一個指令。每次測試提交10 000條指令，然后對所得的結果取平均值。在測試吞吐量時，筆者隨機生成測試數據，數據量大小為32 byte，通過不同數量的客戶端同時進行提交，并測試性能。

測試結果如圖4所示。由于本文工作是單輪通信協議，而DARE是兩輪通信協議，因此本文工作的時延比DARE低。在時延測試中，當數據大小為8 byte時，單次提交指令的時延最低可達到6 μs，相比DARE的9 μs時延來說約減少了33%。由于RDMA操作的時延隨著數據大小的增加而增加，因此二者的時延也隨著數據大小的增加而增加。

圖4???時延和吞吐量測試結果

在吞吐量測試中，二者的吞吐量都隨著客戶端連接數量的增加而增大。DARE協議在第二輪通信中要比本文工作多發送一輪日志的尾指針，發送數據量比本文多一些，因此本文工作的吞吐量要大一些。本文的協議中請求可以并行處理，而DARE只可以等待前面的請求處理結束后才開始處理之后的請求。為了提高性能，DARE在設計中使用了批量處理操作，將相同操作類型的請求打包到一起。隨著連接的客戶端數量增加，領導者服務器接收到的請求也隨之增多，DARE每一次批量處理后的數據大小也隨著增大。RDMA的帶寬利用率是隨著傳輸數據大小增加而增加的，因此本文工作和DARE的吞吐量差距也隨著客戶端連接數的增加而減小。

6 結束語

本文調研了分布式一致性協議的研究現狀以及新的網絡技術RDMA和新的存儲介質NVM的特性。針對RDMA和NVM的特性，設計了適應RDMA和NVM的新協議。該協議能夠充分地利用新技術以及新硬件的特性，使得分布式一致性系統的性能得到了巨大的提升。

作者簡介

吳昊（1992- ），男，清華大學計算機科學與技術系碩士生，主要研究方向為分布式系統。

陳康（1976- ），男，清華大學計算機科學與技術系副教授，中國計算機學會（CCF）會員，主要研究方向為分布式系統、存儲系統等。

武永衛（1974- ），男，清華大學計算機科學與技術系教授，CCF高級會員，主要研究方向為并行和分布 式處理、云計算和存儲等。

鄭緯民（1946- ），男，清華大學計算機科學與技術系教授、博士生導師，CCF會士，主要研究方向為計 算機架構、操作系統、存儲和分布式計算等。

《大數據》期刊

《大數據（Big Data Research，BDR）》雙月刊是由中華人民共和國工業和信息化部主管，人民郵電出版社主辦，中國計算機學會大數據專家委員會學術指導，北京信通傳媒有限責任公司出版的中文科技核心期刊。

關注《大數據》期刊微信公眾號，獲取更多內容

---

往期文章回顧

基于圖查詢系統的圖計算引擎

大數據環境下的存儲系統構建：挑戰、方法和趨勢

一種軟硬件結合的大數據訪存蹤跡收集分析工具集

開源芯片、RISC-V與敏捷開發

基因大數據的集成分析

---

總結

以上是生活随笔為你收集整理的基于RDMA和NVM的大数据系统一致性协议研究的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。