基于Raft共識協議的分布式鍵值對存儲系統研究與實現

摘 要：針對工業物聯網、大數據等領域對分布式數據存儲基礎設施提出的高性能、高可用性和高可靠性需求，簡要回顧和分析了分布式共識協議的相關理論與關鍵技術，研究了具有高性能、高可用性和高可靠性的分布式鍵值對存儲系統，并設計開發了基于Raft共識協議和LevelDB的分布式鍵值對存儲系統。最后，測試了該系統的功能和性能指標。實驗結果表明，該系統具有高穩定性、高可用性和良好的性能。

關鍵詞：分布式存儲系統；副本一致性；Raft共識協議；LevelDB數據庫；LSM-Tree；大數據

中圖分類號：TP392 文獻標識碼：A 文章編號：2095-1302（2024）11-00-04

0 引 言

快速發展的工業物聯網應用對數據存儲設施提出了高可用、高可靠和高性能方面的嚴格要求。傳統集中式數據存儲的硬件成本高，難以擴容，一旦發生宕機，系統就陷入不可用狀態。相比之下，分布式數據存儲具有硬件成本低、可伸縮性強和讀寫性能高等優點，能夠充分滿足工業物聯網應用對數據存儲服務的需求。分布式數據存儲系統部署組件于各計算節點，借助網絡協同工作，具有良好的可靠性、可用性和讀寫性能。其中，各節點通過投票就某數據值達成一致狀態的過程稱為共識。一致性是存儲器在一系列規則的約束下完成數據更新和讀寫操作，確保各存儲器的數據結果正確。通常，共識算法可實現副本數據一致性。Raft和Paxos是具有廣泛影響的共識算法[1-2]。本文深入研究了基于Raft共識算法的數據存儲一致性，采用LevelDB[3]作為底層存儲引擎，將鍵值對數據保存在LevelDB中，通過LevelDB實現數據的持久化存儲。當節點發生宕機并重啟后，系統通過執行Raft共識算法將副本數據恢復到當前的系統狀態。

1 相關工作

計算機領域的學者和技術人員經過多年努力，使得分布式共識協議發展日趨成熟，并廣泛應用于各種分布式計算系統，例如谷歌的Spanner[4]、亞馬遜科技的Amazon Aurora[5]、PingCAP的TiDB[6]等。PingCAP的分布式事務鍵值數據庫支持異地數據同步，并且具備良好的水平擴展能力。該數據庫采用Raft算法作為分布式共識協議，同時選用RocksDB[7]作為底層存儲引擎。Raft共識協議能夠保證副本數據一致性，其中協調者負責處理所有寫操作，并且僅在數據成功寫入多數副本后才返回寫入成功的消息。對于讀操作，系統會在數據足夠新的副本上進行處理，以保證讀取到的數據是最新的或滿足一致性要求的。

Raft和Paxos算法都可以保證日志被精確無誤地復制到多個節點上，從而實現狀態機的復制。相較于Paxos算法，Raft算法是將問題劃分為若干個子問題，使得其更易被理解和實現。在Raft算法中，首先選舉某節點為協調者，選舉由心跳機制實現。協調者定期向所有節點發送心跳信號，每個節點有定時器，當收到來自協調者的心跳信號，則重置其定時器。若定時器超時，沒有收到協調者的心跳，則節點轉變成候選者，發起選舉。為避免其他節點沒有收到協調者心跳而同時發起選舉，Raft使用心跳時間和隨機時間設置定時器，這樣協調者出現故障時，這些節點發起選舉的時間錯開，可快速執行選舉算法，選出新協調者。協調者負責處理客戶端請求，也是唯一有權發起日志復制的節點。Raft運行時允許成員變更，在進行成員變更時會添加一個稱為“共同一致”的過渡配置，它是新老配置的結合體，允許集群在配置轉換過程中依然響應客戶請求。

復制狀態機是分布式系統中解決容錯問題的一個經典方案，Raft算法也采用了復制狀態機解決多節點如何就一系列值達成共識的問題。在復制狀態機中，每個節點都會保存收到的一系列請求為預寫日志。所有節點的預寫日志保持一致，在每個節點副本數據上執行預寫日志的指令，從而保證所有節點副本數據一致。

LSM-Tree（Log Structured Merge Tree）是一種分層、有序、面向磁盤優化的數據結構。其核心設計理念是利用磁盤的順序寫性能遠高于隨機寫性能的優勢，批量地將隨機寫轉化為一次性的順序寫，以提高效率。LSM-Tree在內存中保存修改的數據，達到一定數量后，再將修改的數據批量寫入磁盤，在寫入磁盤的過程中將新數據與之前已經存在的數據合并。LSM-Tree支持增、刪、讀、改及順序掃描等操作。LSM-Tree由2個或以上的存儲結構組成，一個存儲結構常駐于內存中，稱為C0樹，可以是任何鍵值查找的數據結構，例如紅黑樹；其余存儲結構常駐于磁盤中，稱為C1樹、C2樹、……、CK樹，結構類似于B樹。在LSM-Tree中，最低層級的C0樹位于內存中，而更高層級的C1樹、C2樹、…、CK樹位于磁盤上。寫入新數據時，首先寫入C0樹，當C0樹的規模達到一定閾值后，將C0樹的全部或部分數據寫入磁盤上的C1樹。為防止數據丟失，在內存數據寫入磁盤前，LSM-Tree會順序地在磁盤上寫入日志。內存磁盤數據庫LevelDB使用LSM-Tree來存儲數據，其部分組成的具體介紹如下：

（1）MemTable是一個駐留在內存中的跳躍表，用于緩存最近更新的數據。當MemTable達到一定大小時，將其凍結為Immutable MemTable，并創建一個新的MemTable繼續寫入。凍結后的Immutable MemTable等待被轉換為SSTable并寫入磁盤。

（2）Immutable MemTable是只讀的內存表，禁止寫操作，這樣該表轉換為SSTable時數據不變。如果在轉換過程中插入新數據或修改舊數據，則會導致重復寫入或數據不一致。如果在轉換過程中鎖住整個表，則會影響寫性能。因此，在轉換期間使用Immutable MemTable來保存數據，并用新的MemTable來接收寫請求。

（3）SSTable是一個有序、不變、持久化的鍵值對文件，支持指定鍵值查找或遍歷指定鍵范圍內的所有鍵值對。每個SSTable由多個塊（默認大小為64 KB）組成，每個塊包含若干鍵值對。SSTable末尾有一個塊索引，用于快速定位塊所在位置。塊索引會加載到內存，查詢時從內存索引中查找目標塊，再從磁盤中讀取該塊。向LSM-Tree存儲結構寫數據，并不直接修改磁盤的數據，只是將變更寫入MemTable。因此，數據變更在預寫日志時只有一次順序I/O操作，再沒有其他隨機I/O操作。如圖1所示，查詢數據時，首先會查詢MemTable，若在MemTable中沒有查詢到目標數據，則查詢Immutable MemTable；若仍不存在，則查詢各級SSTable，直到在Cn的SSTable中查到數據。從以上讀寫操作可以看出，在LSM-Tree存儲結構中，一次查詢總時間包括若干次內存查詢時間和n次磁盤I/O時間，其中n是磁盤上SSTable的層數。而相比之下，LSM-Tree在處理一次數據變更時只需要一次內存插入操作。

2 系統設計

本文從分布式計算系統的可用性和可靠性這2個角度出發，設計開發高可用和伸縮性能良好的分布式鍵值對存儲系統。當一份數據被寫入該分布式鍵值對存儲系統中時，系統采用的一致性模型[8]可以決定各副本在何時可以看到這份寫入的數據，Raft算法能夠保證各節點的副本數據的一致性。通常，分布式計算系統還要具備容錯能力，若協調者節點發生宕機，不能正常工作，則從系統中的其他節點選舉一個新的協調者。系統部分節點宕機時，只要多數節點可用，那么系統繼續對外服務。系統數據分片采用了一致性哈希分片，哈希算法將數據映射到一個大小為65 535的哈希環，Raft Group（見圖2）也會被分配到哈希環的點上，當查找數據所在的團體時，通過相同的哈希算法獲得數據的鍵對應的哈希值，然后在哈希環上從數據對應的哈希值向后查找，當找到團體分配的點時，該團體就是數據所在的分區。當系統節點出現變化時，只需要遷移少量數據，就可以降低通信開銷和數據不一致的風險。另外，支持添加和刪除虛擬節點，使節點在哈希環上分布更均勻。

如圖2所示，客戶服務器架構中有kv Client、Shared-kv Server、kv Server和Raft Server四種角色。kv Client發送遠程過程調用（RPC）到Shared-kv Server，Shared-kv Server根據哈希算法找到請求中的鍵對應的Raft Group。Shared-kv Server和Raft Group之間的通信由kv Client負責，Shared-kv Server轉發請求到相應的Raft Group。一個Raft Group通常由2n+1（n≥1）個kv Server組成，每個kv Server包含一個Raft Server實例。Raft Server間通信采用RPC，請求會先被轉發到kv Server上，kv Server分析請求。若請求讀取，直接返回值；若請求寫入，則判斷kv Server狀態是否為協調者；若為協調者，則轉換請求為日志，并添加到Raft Server日志。將Raft Server日志提交后，通知客戶端寫入成功，否則返回錯誤；kv Client收到來自kv Server的錯誤回復后，向其他服務器發送請求。

Shared-kv Server是本系統的中心服務器，負責接收來自客戶端的讀寫請求，同時也可以設置管理員接口，例如動態添加、刪除Raft Group和插入虛擬節點等。Raft Server負責對分布式層進行抽象，Raft共識協議在各副本間同步日志，當日志被提交后，通知數據層，并施用日志到數據層。kv Server負責對數據層進行抽象，處理數據讀寫請求，將請求轉化成日志并傳遞給Raft Server完成日志復制，將日志提交后，施用日志到狀態機，將數據存儲在LevelDB。kv Client負責對通信連接層進行抽象，負責維護Shared-kv Server和Raft Group之間的連接，Shared-kv Server并不知道Raft Group中哪一個kv Server是協調者，因此與Raft Group中的每個kv Server維持一個RPC連接。

服務器程序設計采用基于事件驅動的Reactor模型，利用系統調用作為I/O多路復用函數，高效處理大量的并發連接。為進一步提高并發性能[9]，基于Linux的ucontext函數族設計并實現協程[10]模塊，該模塊在用戶態進行任務切換，從而提高系統CPU的使用率。結合Hook技術完成協程模塊開發，在I/O阻塞時執行協程切換主動讓出CPU，提高系統的吞吐量和響應速度。

3 測試結果

本文系統部署在華為云服務器上，配置如下：CPU采用Intel Cascade Lake架構，主頻為2.6 GHz，配置為1核，內存容量為1 GB，SSD磁盤容量為40 GB，網絡帶寬在0.1～0.8 Gb/s范圍內，操作系統為Ubuntu 20.04。

數據讀寫功能的測試過程如下：客戶端頁面發送請求至分布式存儲系統，系統處理請求后將響應結果返回給客戶端。向本文的分布式鍵值對存儲系統寫入從1到100的鍵值對，所有鍵值對均被成功存儲，如圖3所示。從分布式鍵值對存儲系統中讀取鍵值對并展示在前端頁面上，如圖4所示。

根據圖3和圖4所示的操作結果可以看出，本文所提出的分布式鍵值對存儲系統的讀寫操作功能運行正常。

為了測試系統各節點上副本數據的一致性，需要讓某個節點機器崩潰后重啟，再從系統中讀取數據，最后通過再寫入數據來完成測試。在機器崩潰重啟后，這些節點機器會從各自的日志中讀取同步日志，然后恢復數據。實驗結果如圖5所示，可以在重啟之后看到前端所讀取的數據。

通過客戶端的單個鍵值對“添加”按鈕提供的操作功能，可以對分布式鍵值對儲存系統的鍵值對進行修改，其操作過程如圖6所示。

刷新圖6的頁面之后，可以看到鍵為1時所對應的值已經被設置為10，其結果如圖7所示。通過以上的測試結果可以看出，基于Raft協議的分布式鍵值對存儲系統能夠保證各節點副本數據的一致性。

為了測試系統的容錯性，可以“殺死”協調者服務，然后查看團體中各副本機器的狀態。圖8所示為一個團體的初始狀態。

“殺死”序號為2的協調者節點后，再次查看系統的狀態，結果如圖9所示。

由此可知，系統可以在原有協調者節點宕機后，通過節點備份的選舉算法選出新的協調者，使系統具有一定的容錯性。

通過增加分區和刪除分區可以完成系統的可伸縮性測試。圖10所示為系統中一個新團體的情況。

點擊圖10中的“新增分區”按鍵，添加一個新的數據分區，哈希點（hash）為1，集群變化情況如圖11所示。

點擊圖11中的“刪除分區”按鍵，會刪除該團體所負責的哈希點位為1的數據分區，集群的情況也會發生變化，如圖12所示，可以看出系統具有良好的可伸縮性。

隨機或順序向分布式鍵值對存儲系統中寫入100個鍵值對，并比較分析寫入所需時間。本系統寫入性能測試結果如下：隨機寫用時3 780 ms，順序寫用時3 639 ms。測試結果表明，系統對于順序寫和隨機寫都展現了良好的性能。

4 結 語

本文提出了基于Raft共識協議的分布式鍵值對存儲系統，并成功測試了協調者選舉、基于日志的數據同步功能，以保證各副本數據的一致性，以及系統的可伸縮性和系統容錯能力。此外，還測試了系統的隨機寫和順序寫性能。實驗結果表明，該分布式存儲系統具有高穩定性、高可用性、良好的可伸縮性和出色的響應性能。

參考文獻

[1]沈佳杰，盧修文，向望，等.分布式存儲系統讀寫一致性算法性能優化研究綜述[J].計算機工程與科學，2022，44（4）：571-583.

[2]劉克禮，張文盛.基于Paxos的分布式一致性算法應用研究[J].安徽開放大學學報，2022（1）：91-96.

[3]趙江.基于LevelDB的分布式數據庫的研究與實現[D].成都：電子科技大學，2019.

[4]俞騰秋.分布式事務處理模型研究與實現[D].成都：電子科技大學，2021.

[5] VERBITSKI A， GUPTA A， SAHA D， et al. Amazon aurora： design considerations for high throughput cloud-native relational databases [C]// Proceedings of the 2017 ACM International Conference on Management of Data. Chicago： ACM， 2017： 1041-1052.

[6] HUANG D X ， LIU Q， CUI Q， et al. TiDB： a Raft-based HTAP database [J]. Proceedings of the VLDB endowment， 2020， 13（12）： 3072

[7] DONG S， KRYCZKA A， JIN Y， et al. RocksDB：" evolution of development priorities in a key-value store serving large-scale applications [J]. ACM transactions on storage， 2021（4）： 17.

[8] ALDIN H N S， DELDARI H， MOATTAR M H， et al. Consistency models in distributed systems： a survey on definitions， disciplines， challenges and applications [J]. VLDB journal， 2019， 28（6）： 841-872.

[9]陳碩. Linux多線程服務端編程：使用muduo C++網絡庫[M].北京：機械工業出版社，2013：59-74.

[10] SMITH R， VANDEVOORDE D， ROMER G， et al. Coroutines： language and implementation impact [EB/OL]. https： //www.open-std.org/.

收稿日期：2023-10-18 修回日期：2023-11-20

基金項目：西安郵電大學—華為智能基座并行計算課程項目