摘 要：針對工業(yè)物聯(lián)網(wǎng)、大數(shù)據(jù)等領(lǐng)域?qū)Ψ植际綌?shù)據(jù)存儲基礎(chǔ)設(shè)施提出的高性能、高可用性和高可靠性需求，簡要回顧和分析了分布式共識協(xié)議的相關(guān)理論與關(guān)鍵技術(shù)，研究了具有高性能、高可用性和高可靠性的分布式鍵值對存儲系統(tǒng)，并設(shè)計(jì)開發(fā)了基于Raft共識協(xié)議和LevelDB的分布式鍵值對存儲系統(tǒng)。最后，測試了該系統(tǒng)的功能和性能指標(biāo)。實(shí)驗(yàn)結(jié)果表明，該系統(tǒng)具有高穩(wěn)定性、高可用性和良好的性能。

關(guān)鍵詞：分布式存儲系統(tǒng)；副本一致性；Raft共識協(xié)議；LevelDB數(shù)據(jù)庫；LSM-Tree；大數(shù)據(jù)

中圖分類號：TP392 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2024）11-00-04

0 引 言

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

1 相關(guān)工作

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

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

復(fù)制狀態(tài)機(jī)是分布式系統(tǒng)中解決容錯問題的一個經(jīng)典方案，Raft算法也采用了復(fù)制狀態(tài)機(jī)解決多節(jié)點(diǎn)如何就一系列值達(dá)成共識的問題。在復(fù)制狀態(tài)機(jī)中，每個節(jié)點(diǎn)都會保存收到的一系列請求為預(yù)寫日志。所有節(jié)點(diǎn)的預(yù)寫日志保持一致，在每個節(jié)點(diǎn)副本數(shù)據(jù)上執(zhí)行預(yù)寫日志的指令，從而保證所有節(jié)點(diǎn)副本數(shù)據(jù)一致。

LSM-Tree（Log Structured Merge Tree）是一種分層、有序、面向磁盤優(yōu)化的數(shù)據(jù)結(jié)構(gòu)。其核心設(shè)計(jì)理念是利用磁盤的順序?qū)懶阅苓h(yuǎn)高于隨機(jī)寫性能的優(yōu)勢，批量地將隨機(jī)寫轉(zhuǎn)化為一次性的順序?qū)懀蕴岣咝?。LSM-Tree在內(nèi)存中保存修改的數(shù)據(jù)，達(dá)到一定數(shù)量后，再將修改的數(shù)據(jù)批量寫入磁盤，在寫入磁盤的過程中將新數(shù)據(jù)與之前已經(jīng)存在的數(shù)據(jù)合并。LSM-Tree支持增、刪、讀、改及順序掃描等操作。LSM-Tree由2個或以上的存儲結(jié)構(gòu)組成，一個存儲結(jié)構(gòu)常駐于內(nèi)存中，稱為C0樹，可以是任何鍵值查找的數(shù)據(jù)結(jié)構(gòu)，例如紅黑樹；其余存儲結(jié)構(gòu)常駐于磁盤中，稱為C1樹、C2樹、……、CK樹，結(jié)構(gòu)類似于B樹。在LSM-Tree中，最低層級的C0樹位于內(nèi)存中，而更高層級的C1樹、C2樹、…、CK樹位于磁盤上。寫入新數(shù)據(jù)時，首先寫入C0樹，當(dāng)C0樹的規(guī)模達(dá)到一定閾值后，將C0樹的全部或部分?jǐn)?shù)據(jù)寫入磁盤上的C1樹。為防止數(shù)據(jù)丟失，在內(nèi)存數(shù)據(jù)寫入磁盤前，LSM-Tree會順序地在磁盤上寫入日志。內(nèi)存磁盤數(shù)據(jù)庫LevelDB使用LSM-Tree來存儲數(shù)據(jù)，其部分組成的具體介紹如下：

（1）MemTable是一個駐留在內(nèi)存中的跳躍表，用于緩存最近更新的數(shù)據(jù)。當(dāng)MemTable達(dá)到一定大小時，將其凍結(jié)為Immutable MemTable，并創(chuàng)建一個新的MemTable繼續(xù)寫入。凍結(jié)后的Immutable MemTable等待被轉(zhuǎn)換為SSTable并寫入磁盤。

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

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

2 系統(tǒng)設(shè)計(jì)

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

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

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

服務(wù)器程序設(shè)計(jì)采用基于事件驅(qū)動的Reactor模型，利用系統(tǒng)調(diào)用作為I/O多路復(fù)用函數(shù)，高效處理大量的并發(fā)連接。為進(jìn)一步提高并發(fā)性能[9]，基于Linux的ucontext函數(shù)族設(shè)計(jì)并實(shí)現(xiàn)協(xié)程[10]模塊，該模塊在用戶態(tài)進(jìn)行任務(wù)切換，從而提高系統(tǒng)CPU的使用率。結(jié)合Hook技術(shù)完成協(xié)程模塊開發(fā)，在I/O阻塞時執(zhí)行協(xié)程切換主動讓出CPU，提高系統(tǒng)的吞吐量和響應(yīng)速度。

3 測試結(jié)果

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

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

根據(jù)圖3和圖4所示的操作結(jié)果可以看出，本文所提出的分布式鍵值對存儲系統(tǒng)的讀寫操作功能運(yùn)行正常。

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

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

刷新圖6的頁面之后，可以看到鍵為1時所對應(yīng)的值已經(jīng)被設(shè)置為10，其結(jié)果如圖7所示。通過以上的測試結(jié)果可以看出，基于Raft協(xié)議的分布式鍵值對存儲系統(tǒng)能夠保證各節(jié)點(diǎn)副本數(shù)據(jù)的一致性。

為了測試系統(tǒng)的容錯性，可以“殺死”協(xié)調(diào)者服務(wù)，然后查看團(tuán)體中各副本機(jī)器的狀態(tài)。圖8所示為一個團(tuán)體的初始狀態(tài)。

“殺死”序號為2的協(xié)調(diào)者節(jié)點(diǎn)后，再次查看系統(tǒng)的狀態(tài)，結(jié)果如圖9所示。

由此可知，系統(tǒng)可以在原有協(xié)調(diào)者節(jié)點(diǎn)宕機(jī)后，通過節(jié)點(diǎn)備份的選舉算法選出新的協(xié)調(diào)者，使系統(tǒng)具有一定的容錯性。

通過增加分區(qū)和刪除分區(qū)可以完成系統(tǒng)的可伸縮性測試。圖10所示為系統(tǒng)中一個新團(tuán)體的情況。

點(diǎn)擊圖10中的“新增分區(qū)”按鍵，添加一個新的數(shù)據(jù)分區(qū)，哈希點(diǎn)（hash）為1，集群變化情況如圖11所示。

點(diǎn)擊圖11中的“刪除分區(qū)”按鍵，會刪除該團(tuán)體所負(fù)責(zé)的哈希點(diǎn)位為1的數(shù)據(jù)分區(qū)，集群的情況也會發(fā)生變化，如圖12所示，可以看出系統(tǒng)具有良好的可伸縮性。

隨機(jī)或順序向分布式鍵值對存儲系統(tǒng)中寫入100個鍵值對，并比較分析寫入所需時間。本系統(tǒng)寫入性能測試結(jié)果如下：隨機(jī)寫用時3 780 ms，順序?qū)懹脮r3 639 ms。測試結(jié)果表明，系統(tǒng)對于順序?qū)懞碗S機(jī)寫都展現(xiàn)了良好的性能。

4 結(jié) 語

本文提出了基于Raft共識協(xié)議的分布式鍵值對存儲系統(tǒng)，并成功測試了協(xié)調(diào)者選舉、基于日志的數(shù)據(jù)同步功能，以保證各副本數(shù)據(jù)的一致性，以及系統(tǒng)的可伸縮性和系統(tǒng)容錯能力。此外，還測試了系統(tǒng)的隨機(jī)寫和順序?qū)懶阅?。?shí)驗(yàn)結(jié)果表明，該分布式存儲系統(tǒng)具有高穩(wěn)定性、高可用性、良好的可伸縮性和出色的響應(yīng)性能。

參考文獻(xiàn)

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

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

[3]趙江.基于LevelDB的分布式數(shù)據(jù)庫的研究與實(shí)現(xiàn)[D].成都：電子科技大學(xué)，2019.

[4]俞騰秋.分布式事務(wù)處理模型研究與實(shí)現(xiàn)[D].成都：電子科技大學(xué)，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多線程服務(wù)端編程：使用muduo C++網(wǎng)絡(luò)庫[M].北京：機(jī)械工業(yè)出版社，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

基金項(xiàng)目：西安郵電大學(xué)—華為智能基座并行計(jì)算課程項(xiàng)目