摘 要：在分布式存儲系統(tǒng)中，Raft（replicated and fault tolerant）算法的強(qiáng)領(lǐng)導(dǎo)特性在節(jié)點(diǎn)數(shù)量增多時(shí)會帶來巨大的日志分發(fā)開銷，限制了系統(tǒng)性能和水平擴(kuò)展能力。針對系統(tǒng)性能和擴(kuò)展性瓶頸，提出了兩種新的日志機(jī)制來優(yōu)化一致性哈希集群分布式存儲方案。第一種是基于動態(tài)優(yōu)先級的日志分發(fā)機(jī)制，日志分發(fā)順序由領(lǐng)導(dǎo)者與跟隨者節(jié)點(diǎn)日志的同步程度決定，加快了日志項(xiàng)的提交速度；第二種是基于窗口流水線的日志分發(fā)機(jī)制，領(lǐng)導(dǎo)者節(jié)點(diǎn)指派日志同步程度較高的跟隨者節(jié)點(diǎn)對同步程度較低的跟隨者節(jié)點(diǎn)進(jìn)行日志分發(fā)，縮短了系統(tǒng)中節(jié)點(diǎn)日志趨向一致的時(shí)間。相比于未優(yōu)化方法，吞吐量和日志同步時(shí)間在多節(jié)點(diǎn)集群上有顯著提升，證明了兩種日志機(jī)制在改進(jìn)系統(tǒng)性能上的有效性。

關(guān)鍵詞：分布式存儲；一致性哈希；日志分發(fā)；動態(tài)優(yōu)先級分配；窗口流水線

中圖分類號：TP311.13"" 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2024）12-031-3755-08

doi： 10.19734/j.issn.1001-3695.2024.05.0155

Optimization of log distribution mechanisms in Raft storage clusters

Xu Hui1， Gao Hui1， 2

（1.School of Computer Science amp; Engineering， University of Electronic Science amp; Technology of China， Chengdu 611731， China; 2. Kash Institute of Electronics amp; Information Industry， Kashgar Xinjiang 844000， China）

Abstract：In distributed storage systems， the Raft algorithm’s strong leadership characteristics introduce substantial log distribution overhead as the number of nodes increases， impacting performance and scalability. This paper proposed two innovative mechanisms to overcome these challenges. First algorithm was a dynamic priority based log distribution mechanism. It assigned log entries based on the synchronization levels between leader and follower nodes， thereby expediting log submission. Second algorithm was a window pipeline based log distribution delegation mechanism. Its leader node assigned more synchronized followers to disseminate logs to less synchronized ones， diminishing the time required to achieve system-wide log consistency. The experimental results demonstrate substantial enhancements in throughput and log synchronization time within multi-node clusters. This improvement shows the efficacy of these mechanisms in bolstering system perfor-mance.

Key words：distributed storage; consistent hashing; log replication; dynamic priority assignment; windowed pipelining

0 引言

根據(jù)國際調(diào)研機(jī)構(gòu)IDC發(fā)布的《Data Age 2025》[1]預(yù)測，全球數(shù)據(jù)總量從2016年的16.1 ZB增長至2025年的163 ZB。傳統(tǒng)的單機(jī)存儲或集中式存儲已經(jīng)觸及存儲性能和容量方面的瓶頸，無法滿足數(shù)據(jù)快速增長背景下對數(shù)據(jù)存儲的需求。

分布式存儲技術(shù)在這一背景下應(yīng)運(yùn)而生。相較于集中式存儲，分布式存儲可以通過水平擴(kuò)展的方式增加系統(tǒng)容量，滿足存儲海量數(shù)據(jù)的需求。同時(shí)，分布式存儲將用戶的讀寫請求分散到系統(tǒng)不同節(jié)點(diǎn)，提高整體性能，實(shí)現(xiàn)系統(tǒng)的負(fù)載均衡。此外，分布式存儲還可以通過將數(shù)據(jù)備份到不同節(jié)點(diǎn)實(shí)現(xiàn)異地容災(zāi)備份，提升數(shù)據(jù)安全性、系統(tǒng)可靠性和可用性。然而，盡管分布式存儲帶來了上述優(yōu)勢，但也存在一些缺陷，如數(shù)據(jù)一致性、數(shù)據(jù)分布不均衡等問題，這些都是需要解決的關(guān)鍵問題。

在分布式一致性算法中，Raft算法以其強(qiáng)領(lǐng)導(dǎo)特性、易理解性和良好的性能在業(yè)界受到廣泛關(guān)注。然而，隨著分布式存儲系統(tǒng)節(jié)點(diǎn)數(shù)量的增加，Raft算法中的領(lǐng)導(dǎo)者節(jié)點(diǎn)在日志分發(fā)過程中會面臨巨大的開銷，這不僅影響了日志項(xiàng)的提交速度，還限制了系統(tǒng)的水平擴(kuò)展能力。

在Raft算法中以領(lǐng)導(dǎo)者節(jié)點(diǎn)為中心進(jìn)行日志復(fù)制會產(chǎn)生以下三個(gè)問題：a）如果領(lǐng)導(dǎo)者節(jié)點(diǎn)為慢節(jié)點(diǎn)會產(chǎn)生長尾效應(yīng)導(dǎo)致性能瓶頸；b）日志的同步必須是有序提交的；c）切換領(lǐng)導(dǎo)者節(jié)點(diǎn)時(shí)有一段時(shí)間系統(tǒng)不可用。

當(dāng) Raft 存儲集群進(jìn)行節(jié)點(diǎn)變更時(shí)，新加入的節(jié)點(diǎn)可能會因?yàn)樾枰ㄙM(fèi)很長時(shí)間同步日志而降低集群的可用性，導(dǎo)致集群無法提交新的請求。在目前存儲數(shù)據(jù)的飛速增長的背景中，越大規(guī)模的分布式系統(tǒng)，日志復(fù)制越有可能會成為性能瓶頸。此外，隨著節(jié)點(diǎn)的增加，領(lǐng)導(dǎo)選舉和成員變更的開銷也會劇增。為了維護(hù)一個(gè)高可用、高擴(kuò)展性的分布式存儲系統(tǒng)，集群節(jié)點(diǎn)成員變更時(shí)的性能瓶頸亟待解決。

受到計(jì)算機(jī)網(wǎng)絡(luò)中的TCP滑動窗口和操作系統(tǒng)中的動態(tài)優(yōu)先級的進(jìn)程調(diào)度等相關(guān)算法的啟發(fā)，對Raft算法中的日志分發(fā)機(jī)制作出優(yōu)化改進(jìn)。研究主要解決Raft算法在分布式存儲系統(tǒng)中水平擴(kuò)展的限制，通過優(yōu)化日志分發(fā)機(jī)制來提高系統(tǒng)的性能和可靠性。

a）基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制中，領(lǐng)導(dǎo)者會根據(jù)系統(tǒng)中跟隨者節(jié)點(diǎn)中日志與自己日志的同步程度來決定日志分發(fā)到不同跟隨者節(jié)點(diǎn)的先后順序，從而更快地將日志項(xiàng)復(fù)制到集群一半以上節(jié)點(diǎn)中，加快日志項(xiàng)的提交速度并提高系統(tǒng)對寫請求的吞吐量。

b）基于窗口流水線的日志分發(fā)委托機(jī)制中，領(lǐng)導(dǎo)者節(jié)點(diǎn)為每個(gè)跟隨者節(jié)點(diǎn)維護(hù)了一個(gè)具有容量上限的委托復(fù)制窗口，窗口中存儲了領(lǐng)導(dǎo)者在之前心跳函數(shù)觸發(fā)時(shí)日志分發(fā)過程中產(chǎn)生的日志分發(fā)委托的記錄，窗口中的記錄會在一定時(shí)間內(nèi)得不到跟隨者的響應(yīng)而過期，在窗口內(nèi)記錄數(shù)量未滿或窗口內(nèi)有記錄過期的情況下，領(lǐng)導(dǎo)者節(jié)點(diǎn)在日志分發(fā)過程中為日志落后程度較高的節(jié)點(diǎn)指派跟隨者節(jié)點(diǎn)對其進(jìn)行指定區(qū)間的日志分發(fā)并在跟隨者的委托復(fù)制窗口中更新相關(guān)記錄信息，將領(lǐng)導(dǎo)者部分日志分發(fā)的壓力轉(zhuǎn)移到跟隨者中，縮短了系統(tǒng)中節(jié)點(diǎn)數(shù)據(jù)趨向一致的時(shí)間。

1 相關(guān)研究介紹

分布式系統(tǒng)中的一致性問題涉及同一集群中節(jié)點(diǎn)在初始狀態(tài)一致的情況下，執(zhí)行相同指令序列直至達(dá)到一致狀態(tài)的過程。Lamport提出的Paxos算法是基于消息傳遞的代表性一致性算法，將節(jié)點(diǎn)分為proposers、acceptors和learners。proposers提出指令，acceptors批準(zhǔn)或拒絕，最終由learners執(zhí)行。盡管Paxos理論描述詳盡，但在工程實(shí)踐中仍面臨挑戰(zhàn)。Google的Chubby[2]項(xiàng)目將Paxos引入工程實(shí)踐，解決了節(jié)點(diǎn)故障恢復(fù)等問題。

隨著Paxos廣泛應(yīng)用于分布式系統(tǒng)，出現(xiàn)了多種優(yōu)化方案如Multi Paxos、Cheap Paxos、Fast Paxos、Ring Paxos、HT Paxos、Adv Paxos、Pig Paxos等[3～15]，以提升性能和容錯(cuò)性。Raft分布式一致性算法由斯坦福大學(xué)提出，相較Paxos更易理解且具備工程實(shí)踐基礎(chǔ)。其在區(qū)塊鏈共識算法中得到廣泛應(yīng)用，包括hhRaft、CRaft、KRaft等變體，優(yōu)化了在不同環(huán)境下的性能和容錯(cuò)能力。

1.1 Raft一致性算法

針對Paxos算法難以理解以及不易用于工程實(shí)踐等問題， Ongaro等人[16]發(fā)表了基于復(fù)制狀態(tài)機(jī)的Raft算法。復(fù)制狀態(tài)機(jī)通常是通過復(fù)制日志的方式來實(shí)現(xiàn)的。用戶向基于復(fù)制狀態(tài)機(jī)的分布式系統(tǒng)發(fā)起請求到收到響應(yīng)的流程一般分為以下幾個(gè)步驟：a）客戶端向集群中的某個(gè)服務(wù)節(jié)點(diǎn)發(fā)起修改狀態(tài)機(jī)中某些值的操作請求；b）該服務(wù)節(jié)點(diǎn)將該操作記錄在本地日志中，同時(shí)將該操作復(fù)制到系統(tǒng)中的其他服務(wù)器節(jié)點(diǎn)的日志中；c）操作在所有節(jié)點(diǎn)中都被記錄到日志后，狀態(tài)機(jī)執(zhí)行該操作，完成對某些值的修改；d）該服務(wù)節(jié)點(diǎn)返回對狀態(tài)機(jī)某些值修改的結(jié)果給客戶端。

Raft算法定義leader（領(lǐng)導(dǎo)者）、candidate（候選者）、follower（跟隨者） 三種節(jié)點(diǎn)狀態(tài)。通常僅一個(gè)領(lǐng)導(dǎo)者，其余為跟隨者。跟隨者不發(fā)起請求，僅響應(yīng)領(lǐng)導(dǎo)者和候選者。領(lǐng)導(dǎo)者處理客戶端請求，維持與跟隨者心跳，同步集群日志。候選者用于選舉領(lǐng)導(dǎo)者，自增任期、投票并請求其他節(jié)點(diǎn)投票。若獲多數(shù)票則成領(lǐng)導(dǎo)者，遇到現(xiàn)有領(lǐng)導(dǎo)者或任期更大者則回歸跟隨者。跟隨者初始化時(shí)均為此狀態(tài)，維護(hù)選舉超時(shí)計(jì)時(shí)器，超時(shí)則轉(zhuǎn)變?yōu)楹蜻x者并發(fā)起選舉。

Raft算法中，節(jié)點(diǎn)日志由序號標(biāo)記的條目構(gòu)成，含任期、索引及狀態(tài)機(jī)指令。日志條目復(fù)制到集群多數(shù)節(jié)點(diǎn)時(shí)可提交至狀態(tài)機(jī)執(zhí)行，確保節(jié)點(diǎn)間日志高一致性，簡化系統(tǒng)行為，保障安全性。Raft日志特性如下：

a）若兩個(gè)日志條目分別來自兩個(gè)節(jié)點(diǎn)的日志，且存儲了相同的索引值和任期，那么這兩個(gè)日志條目存儲了同樣的指令。

b）若兩個(gè)日志條目分別來自兩個(gè)節(jié)點(diǎn)的日志，且存儲了相同的索引值和任期，那么這兩個(gè)節(jié)點(diǎn)的日志在這兩個(gè)日志條目之前的所有日志條目都保持一致。

Raft日志特性確保同索引和任期的條目指令相同，且與之前條目一致。領(lǐng)導(dǎo)者每任期在指定索引位置最多創(chuàng)建一個(gè)條目，索引不變，保障一致性。附加日志RPC確保跟隨者拒絕不一致的條目。不一致時(shí)，領(lǐng)導(dǎo)者刪除跟隨者不一致條目后的所有日志，并重新發(fā)送，確保一致。隨系統(tǒng)運(yùn)行，日志增長占用空間，重置狀態(tài)機(jī)耗時(shí)。Raft采用快照系統(tǒng)壓縮日志，保存狀態(tài)機(jī)信息至持久化存儲，丟棄舊日志，解決可用性問題。

Raft算法問世以后被廣泛使用于區(qū)塊鏈共識算法中，這些Raft算法變體[17～19]提高了Raft算法在拜占庭環(huán)境下的容錯(cuò)能力。文獻(xiàn)[20]引人動態(tài)線性投票機(jī)制提高了Raft集群的可用性。hhRaft[21]通過引用監(jiān)控器的角色來優(yōu)化Raft達(dá)成共識的過程，適用于高實(shí)時(shí)性和高對抗性環(huán)境。文獻(xiàn)[22]針對Raft算法提出了一種準(zhǔn)確高效的用于跟隨者進(jìn)行日志修復(fù)的算法。CRaft[23]通過使用糾刪碼降低了Raft算法運(yùn)行的網(wǎng)絡(luò)成本和存儲成本。Kraft[24]通過在Kademlia協(xié)議中建立的K-Bucket節(jié)點(diǎn)關(guān)系，優(yōu)化了Raft算法中領(lǐng)導(dǎo)者選舉和共識過程，提高了集群中領(lǐng)導(dǎo)者的選舉速度。文獻(xiàn)[25]提出了一種基于節(jié)點(diǎn)活動和信用機(jī)制的Raft共識算法，降低了共識時(shí)延并具有更高的吞吐量。在最新Raft算法研究中，針對算法的日志機(jī)制，產(chǎn)生了許多改進(jìn)日志一致性、日志壓縮、日志復(fù)制等方面的優(yōu)化方法[26～28]，有效地解決了一致性和性能瓶頸。

1.2 帶虛擬節(jié)點(diǎn)的一致性哈希算法

當(dāng)使用一致性哈希算法構(gòu)建分布式系統(tǒng)，在服務(wù)節(jié)點(diǎn)比較少時(shí)，可能會面臨因節(jié)點(diǎn)在環(huán)上不均勻分布導(dǎo)致的數(shù)據(jù)傾斜問題，即在分布式系統(tǒng)中大量的數(shù)據(jù)集中存儲在環(huán)上的某個(gè)節(jié)點(diǎn)。為了解決數(shù)據(jù)傾斜的問題，帶虛擬節(jié)點(diǎn)的一致性哈希算法被提出。

帶虛擬節(jié)點(diǎn)的一致性哈希方法，核心思想是根據(jù)每個(gè)節(jié)點(diǎn)的性能，為每個(gè)節(jié)點(diǎn)劃分不同數(shù)量的虛擬節(jié)點(diǎn)，并將這些虛擬節(jié)點(diǎn)映射到哈希環(huán)中，然后再按照一致性哈希算法進(jìn)行數(shù)據(jù)映射和存儲。這樣在分布式系統(tǒng)中新增或刪除節(jié)點(diǎn)時(shí)系統(tǒng)的變動就由變動節(jié)點(diǎn)周圍的虛擬節(jié)點(diǎn)分擔(dān)，大大降低了發(fā)生數(shù)據(jù)傾斜的可能性，提高了分布式系統(tǒng)的穩(wěn)定性。帶虛擬節(jié)點(diǎn)的一致性哈希算法相對于普通的一致性哈希算法來說數(shù)據(jù)定位的算法保持不變，只是多了一步由虛擬節(jié)點(diǎn)到物理節(jié)點(diǎn)的映射，不僅適合硬件配置不同的節(jié)點(diǎn)的場景，而且適合節(jié)點(diǎn)規(guī)模會發(fā)生變動以及對系統(tǒng)穩(wěn)定性要求更高的場景。

2 一致性哈希存儲集群設(shè)計(jì)

該方案主要由基于Raft協(xié)議的一致性哈希集群以及基于Raft 協(xié)議的存儲集群構(gòu)成，其中一致性哈希集群充當(dāng)路由集群并負(fù)責(zé)維護(hù)存儲系統(tǒng)的路由信息，每個(gè)存儲集群有少量節(jié)點(diǎn)構(gòu)成，維護(hù)了屬于本集群所管理的數(shù)據(jù)元信息、文件并為存儲客戶端提供服務(wù)。本文方案避免了如圖1中直接在集群中增加節(jié)點(diǎn)的方式對系統(tǒng)進(jìn)行水平擴(kuò)展導(dǎo)致的集群性能下降等問題，而是通過在一致性哈希環(huán)中增加存儲集群并完成相關(guān)遷移數(shù)據(jù)的生成，然后上線新存儲集群中的節(jié)點(diǎn)并獲取遷移數(shù)據(jù)來實(shí)現(xiàn)系統(tǒng)的水平擴(kuò)展，在數(shù)據(jù)遷移過程中，只會對文件和目錄的元信息以及涉及到的鎖信息進(jìn)行遷移，文件數(shù)據(jù)繼續(xù)保留在原存儲集群中，降低了數(shù)據(jù)遷移的開銷。通過這種水平擴(kuò)展方式，每個(gè)存儲集群中節(jié)點(diǎn)的數(shù)量維持在較小規(guī)模，單個(gè)存儲集群的性能不會受到節(jié)點(diǎn)數(shù)量龐大所帶來的影響，存儲集群之間相互獨(dú)立，每個(gè)存儲集群中都實(shí)現(xiàn)了對自己所在集群文件元數(shù)據(jù)以及文件數(shù)據(jù)的備份，具備更高的可靠性。

整個(gè)存儲系統(tǒng)由一致性哈希集群注冊中心、基于Raft協(xié)議的一致性哈希集群、基于Raft協(xié)議的存儲集群、客戶端四個(gè)部分構(gòu)成。

一致性哈希集群注冊中心主要負(fù)責(zé)維護(hù)當(dāng)前一致性哈希集群在線節(jié)點(diǎn)的狀態(tài)信息，當(dāng)一致性哈希集群有節(jié)點(diǎn)上線或離線時(shí)會在注冊中心登記相關(guān)信息。當(dāng)有新節(jié)點(diǎn)上線時(shí)也會返回注冊中心當(dāng)前在線節(jié)點(diǎn)的相關(guān)信息，同時(shí)注冊中心會將該節(jié)點(diǎn)的信息廣播到一致性哈希集群的所有節(jié)點(diǎn)，以便上線節(jié)點(diǎn)加人到集群中。注冊中心由兩個(gè)RPC服務(wù)（節(jié)點(diǎn)注冊、節(jié)點(diǎn)離線）、一致性哈希集群節(jié)點(diǎn)信息、心跳維護(hù)這三部分構(gòu)成。注冊中心會通過心跳始終保持跟一致性哈希集群中當(dāng)前處于在線狀態(tài)的節(jié)點(diǎn)的聯(lián)系，并將這種節(jié)點(diǎn)的在線狀態(tài)告知后續(xù)新加人到一致性哈希集群中的節(jié)點(diǎn)，然后新加人的節(jié)點(diǎn)也會根據(jù)在線節(jié)點(diǎn)的信息維持跟其他在線的節(jié)點(diǎn)之間的聯(lián)系。

基于Raft協(xié)議的一致性哈希集群由RPC服務(wù)、狀態(tài)機(jī)、集群節(jié)點(diǎn)維護(hù)和Raft一致性模塊構(gòu)成。一致性哈希集群負(fù)責(zé)接收面向用戶的存儲客戶端的路由請求，將集群內(nèi)部維護(hù)的存儲集群的服務(wù)區(qū)間等路由信息響應(yīng)給客戶端；接收面向系統(tǒng)管理者的一致性哈希集群客戶端的請求，對存儲集群的信息進(jìn)行管理；接收來自存儲集群的請求，保存存儲集群的相關(guān)服務(wù)的地址和端口信息；維持一致性哈希集群節(jié)點(diǎn)中的所維護(hù)的一致性哈希環(huán)在集群內(nèi)多個(gè)節(jié)點(diǎn)中一致，實(shí)現(xiàn)路由信息的冗余備份，保證系統(tǒng)的高可用性。

基于Raft協(xié)議的存儲集群由RPC服務(wù)、狀態(tài)機(jī)、存儲、集群節(jié)點(diǎn)維護(hù)、一致性哈希交互和Raft一致性模塊構(gòu)成。存儲集群接收面向用戶的存儲客戶端的請求，將集群內(nèi)部維護(hù)的目錄與文件元信息、文件數(shù)據(jù)以及客戶端對文件和目錄進(jìn)行并發(fā)訪問控制的結(jié)果響應(yīng)給客戶端；接收一致性哈希集群的請求，對自身所在存儲集群的服務(wù)區(qū)間信息進(jìn)行管理：維持存儲集群內(nèi)部節(jié)點(diǎn)之間目錄樹以及鎖目錄樹一致，實(shí)現(xiàn)文件和目錄元信息、鎖信息的冗余備份，保證集群的高可用性；將存儲集群中的文件分散存儲在集群中的節(jié)點(diǎn)并維護(hù)同一文件在存儲集群目錄樹中不同路徑下的映射信息，減少相同文件在不同路徑下重復(fù)上傳導(dǎo)致的存儲空間占用；響應(yīng)其他存儲集群節(jié)點(diǎn)的對數(shù)據(jù)遷移文件拉取的請求。

客戶端分為一致性哈希集群客戶端和存儲客戶端，其中存儲客戶端面向用戶使用，通過請求一致性哈希集群獲得路由信息并將其在本地進(jìn)行緩存，實(shí)現(xiàn)客戶端與存儲集群的交互以及結(jié)果的展示。一致性哈希集群客戶端面向系統(tǒng)管理員使用，通過管理員在終端鍵人的命令與一致性哈希集群進(jìn)行交互并實(shí)現(xiàn)對系統(tǒng)中的存儲集群進(jìn)行管理。

在本系統(tǒng)設(shè)計(jì)中，一致性哈希集群注冊中心能夠讓一致性哈希集群中的節(jié)點(diǎn)相互發(fā)現(xiàn)并構(gòu)成一個(gè)基于Raft協(xié)議的分布式一致性哈希系統(tǒng)，這個(gè)一致性哈希系統(tǒng)中維護(hù)了每個(gè)存儲集群對應(yīng)的虛擬節(jié)點(diǎn)的數(shù)量、虛擬節(jié)點(diǎn)在一致性哈希環(huán)上分布的位置信息以及每個(gè)存儲集群在一致性哈希環(huán)上負(fù)責(zé)響應(yīng)的客戶端請求的區(qū)間，由管理員通過一致性哈希集群客戶端進(jìn)行管理?；赗aft協(xié)議的存儲集群則負(fù)責(zé)真正處理來自客戶端的請求，將客戶端需要上傳的文件存儲到本集群中的節(jié)點(diǎn)中，同時(shí)在集群中記錄該集群負(fù)責(zé)的目錄樹和鎖目錄樹的相關(guān)信息以及文件信息。在這種設(shè)計(jì)下，客戶端對不同路徑文件的請求會被一致性哈希環(huán)上均勻分布的存儲集群所響應(yīng)，減少了單個(gè)存儲集群被客戶端頻繁請求的壓力，同時(shí)存儲集群中的文件也被分散存儲到集群中的各個(gè)節(jié)點(diǎn)中，減輕了單個(gè)存儲集群節(jié)點(diǎn)的文件存儲壓力。

3 Raft日志分發(fā)機(jī)制優(yōu)化

針對Raft算法在集群中節(jié)點(diǎn)數(shù)量變多時(shí)領(lǐng)導(dǎo)者節(jié)點(diǎn)需要更多的時(shí)間來將日志項(xiàng)復(fù)制到集群中的跟隨者節(jié)點(diǎn)時(shí)導(dǎo)致的集群對外界請求響應(yīng)能力降低帶來的性能下降的情形，本文在對Raft算法進(jìn)行優(yōu)化的過程中，主要在領(lǐng)導(dǎo)者將日志項(xiàng)復(fù)制給跟隨者這個(gè)過程考慮優(yōu)化的措施，設(shè)計(jì)了基于動態(tài)優(yōu)先級分配和雙心跳機(jī)制和基于窗口流水線的委托復(fù)制機(jī)制。

3.1 基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制

由于Raft協(xié)議是基于復(fù)制狀態(tài)機(jī)來實(shí)現(xiàn)集群內(nèi)部中節(jié)點(diǎn)的數(shù)據(jù)一致，每個(gè)節(jié)點(diǎn)都會有自己的日志和狀態(tài)機(jī)，日志中包含了多個(gè)日志項(xiàng)，這些日志項(xiàng)中存儲了請求發(fā)起方對系統(tǒng)進(jìn)行操作的指令，狀態(tài)機(jī)中則存儲了節(jié)點(diǎn)所維護(hù)的系統(tǒng)中副本數(shù)據(jù)在當(dāng)前節(jié)點(diǎn)的狀態(tài)。當(dāng)領(lǐng)導(dǎo)者將某個(gè)包含日志項(xiàng)分發(fā)給了系統(tǒng)中一半以上節(jié)點(diǎn)時(shí)，領(lǐng)導(dǎo)者就可以將該日志項(xiàng)包含的指令提交到狀態(tài)機(jī)中執(zhí)行并更新相關(guān)數(shù)據(jù)的狀態(tài)并響應(yīng)該指令的請求方，同時(shí)告訴系統(tǒng)中的其他節(jié)點(diǎn)當(dāng)前可以進(jìn)行提交的日志項(xiàng)的最大索引，系統(tǒng)中的其他節(jié)點(diǎn)就可以根據(jù)領(lǐng)導(dǎo)者告知的可以提交的日志項(xiàng)的最大索引往狀態(tài)機(jī)中提交相關(guān)日志項(xiàng)包含的指令，等待狀態(tài)機(jī)執(zhí)行并實(shí)現(xiàn)對相關(guān)數(shù)據(jù)狀態(tài)的更新。在Raft構(gòu)建的分布式系統(tǒng)正常運(yùn)行過程中，領(lǐng)導(dǎo)者在每一輪與跟隨者節(jié)點(diǎn)的心跳函數(shù)中不斷地將日志項(xiàng)分發(fā)到系統(tǒng)中的跟隨者節(jié)點(diǎn)。最終所有節(jié)點(diǎn)上的日志中包含的日志項(xiàng)都一樣，提交到各自狀態(tài)機(jī)中執(zhí)行的指令序列也一樣，所維護(hù)的副本數(shù)據(jù)狀態(tài)也就達(dá)成一致。但是在這個(gè)過程中會存在日志從領(lǐng)導(dǎo)者節(jié)點(diǎn)復(fù)制到系統(tǒng)中所有跟隨者節(jié)點(diǎn)中的這個(gè)開銷，領(lǐng)導(dǎo)者在每輪心跳中可以分發(fā)的日志項(xiàng)的數(shù)量并不是無限的。當(dāng)一個(gè)由Raft協(xié)議實(shí)現(xiàn)的分布式系統(tǒng)中節(jié)點(diǎn)數(shù)量越多時(shí)，這種由領(lǐng)導(dǎo)者將日志復(fù)制到跟隨者所帶來的時(shí)間開銷就越大，將日志項(xiàng)復(fù)制到集群一半以上節(jié)點(diǎn)才能對日志項(xiàng)進(jìn)行提交的時(shí)間開銷也就越大，這就會導(dǎo)致客戶端從發(fā)起一個(gè)更改集群狀態(tài)機(jī)數(shù)據(jù)的寫請求到得到集群響應(yīng)的時(shí)間就越長。為此，本文在分布式存儲系統(tǒng)實(shí)現(xiàn)中對Raft協(xié)議在領(lǐng)導(dǎo)者復(fù)制日志到跟隨者節(jié)點(diǎn)這個(gè)過程中采取了基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制來提高集群領(lǐng)導(dǎo)者對日志項(xiàng)的提交速度，從而提高系統(tǒng)對客戶端寫請求的寫請求的吞吐量。

Raft對象中在內(nèi)部維護(hù)了兩個(gè)定時(shí)器，分別是用以重置選舉超時(shí)的定時(shí)器electionOutTimerId和用以發(fā)送攜帶心跳信息的附加日志請求的定時(shí)器heartBeat-TimerId。當(dāng)節(jié)點(diǎn)身為領(lǐng)導(dǎo)者時(shí)，electionOutTimerId定時(shí)器被取消，heartBeatTimerId定時(shí)器被激活。每當(dāng)heartBeatTimerId 定時(shí)器超時(shí)，領(lǐng)導(dǎo)者節(jié)點(diǎn)首先會在heart-BeatTimerId定時(shí)器超時(shí)回調(diào)函數(shù)（心跳）中對集群中的其他跟隨者節(jié)點(diǎn)的發(fā)起的附加日志請求中僅僅附加心跳信息來重置集群中跟隨者節(jié)點(diǎn)的選舉定時(shí)器electionOutTimerId，這樣領(lǐng)導(dǎo)者會獲得更加充足的時(shí)間來準(zhǔn)備對日志項(xiàng)進(jìn)行分發(fā)。領(lǐng)導(dǎo)者節(jié)點(diǎn)接著會根據(jù)Raft對象中存儲的集群中其他跟隨者節(jié)點(diǎn)在領(lǐng)導(dǎo)者節(jié)點(diǎn)下一次日志復(fù)制時(shí)的需要分發(fā)的日志項(xiàng)的起始索引記錄nextIndexMap，計(jì)算跟隨者節(jié)點(diǎn)與領(lǐng)導(dǎo)者節(jié)點(diǎn)日志同步程度并由低到高排序。排序在最中間的節(jié)點(diǎn)（跟隨者數(shù)量為N，則從排序在N/2的節(jié)點(diǎn)開始，舍棄掉N/2中計(jì)算結(jié)果的小數(shù)部分）的優(yōu)先級最高。然后從中間節(jié)點(diǎn)開始到同步程度最高的節(jié)點(diǎn)之間優(yōu)先級依次遞減，再從同步程度排序在最中間節(jié)點(diǎn)前面的節(jié)點(diǎn)到同步程度最低的節(jié)點(diǎn)之間依次遞減。由于日志項(xiàng)只需要被復(fù)制到集群中的一半以上節(jié)點(diǎn)時(shí)領(lǐng)導(dǎo)者就可以對該日志項(xiàng)進(jìn)行提交，領(lǐng)導(dǎo)者通過這種動態(tài)優(yōu)先級將每一輪心跳中有限的日志項(xiàng)分發(fā)數(shù)量優(yōu)先分配給影響領(lǐng)導(dǎo)者對未提交日志項(xiàng)進(jìn)行提交的跟隨者節(jié)點(diǎn)。將本輪心跳分發(fā)的日志項(xiàng)通過對優(yōu)先級較高節(jié)點(diǎn)的第二次日志附加請求中發(fā)送，就能更快地對新增的日志項(xiàng)進(jìn)行提交，從而更快地對請求的發(fā)起方進(jìn)行響應(yīng)。

領(lǐng)導(dǎo)者在每一輪heartBeatTimerId定時(shí)器超時(shí)回調(diào)函數(shù)觸發(fā)時(shí)都會根據(jù)當(dāng)前跟隨者節(jié)點(diǎn)日志與自身日志的同步程度重新計(jì)算每個(gè)節(jié)點(diǎn)的日志分發(fā)優(yōu)先級，然后按照優(yōu)先級對每個(gè)節(jié)點(diǎn)分發(fā)日志項(xiàng)，跟隨者節(jié)點(diǎn)的日志分發(fā)優(yōu)先級不是固定的，所以稱該機(jī)制為基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制?；趧討B(tài)優(yōu)先級分配的日志分發(fā)機(jī)制的算法流程如算法1所示。

算法1 基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制

輸入：跟隨者數(shù)量n;日志在一輪心跳中的分發(fā)數(shù)量load;領(lǐng)導(dǎo)者當(dāng)前日志最大索引logIndex;跟隨者到下一次日志分發(fā)起始索引l的映射nextIndexMap。

輸出：nextIndexSortVec。

對每一個(gè)跟隨者發(fā)送不包含任何日志項(xiàng)的心跳附加日志請求，重置跟隨者中的選舉超時(shí)器，獲得更加充足的日志項(xiàng)分發(fā)準(zhǔn)備時(shí)間;

根據(jù)nextIndexMap計(jì)算得到存放 [索引，對應(yīng)節(jié)點(diǎn)] 的nextIndexSortVec;//同步程度由低到高排序

nextIndexSortVec=［［idx1，N1］，［idx2，N2］，…，［idxn，Nn］］，（idx1lt;idx2lt;…lt;idxn）;

/*優(yōu)先級由同步程度排在最中間的節(jié)點(diǎn)到同步程度最高的節(jié)點(diǎn)遞減，然后再從同步程度排在最中間的節(jié)點(diǎn)左邊開始的節(jié)點(diǎn)到同步程度最小的節(jié)點(diǎn)之間遞減*/

根據(jù)nextlndexSortVec得到節(jié)點(diǎn)的優(yōu)先級，PrioritySequence=［［idxn2+1，Nn2+1］，［idxn2+2，Nn2+2］，…，［idxn，Nn］，［idxn2，Nn2］，［idxn2－1，Nn2－1］，…，［idx1，N1］］;

//為優(yōu)先級中的節(jié)點(diǎn)依次分配本輪心跳周期中的日志復(fù)制數(shù)

for i=1; ilt;=n; i++ do

node = PrioritySequence[i];

if loadgt;=（logIndex-node.idx+1） then

load = load - （logIndex-node.idx+1）;

向跟隨者節(jié)點(diǎn)node.N發(fā)送攜帶從node.idx開始的（logIndex-node.idx+1）個(gè)日志項(xiàng)的附加日志請求;

else if loadgt;0 then

向跟隨者節(jié)點(diǎn)node.N發(fā)送攜帶從node.idx開始的load個(gè)日志項(xiàng)的附加日志請求;

load = 0;

end if

break;

end if

end for

圖2給出了一個(gè)Raft集群運(yùn)行在某個(gè)時(shí)刻下各個(gè)節(jié)點(diǎn)中的日志示例圖，用以對優(yōu)化算法進(jìn)行講解。

在圖2中，假定領(lǐng)導(dǎo)者節(jié)點(diǎn)在一輪heartBeatTimerId定時(shí)器超時(shí)的日志分發(fā)數(shù)量為5，即在一次心跳超時(shí)中只能向集群中的所有跟隨者節(jié)點(diǎn)發(fā)送5個(gè)日志項(xiàng)。當(dāng)領(lǐng)導(dǎo)者節(jié)點(diǎn)heart-BeatTimerId定時(shí)器超時(shí)后，其首先會向集群中的所有跟隨者發(fā)送僅用于維持與跟隨者節(jié)點(diǎn)之間心跳的附加日志請求用以重置跟隨者中的electionOutTimerId定時(shí)器。然后根據(jù)nextIndexMap中數(shù)據(jù)對集群中跟隨者節(jié)點(diǎn)按日志同步程度由低到高進(jìn)行排序后，得到排序結(jié)果（C，E，D，B），領(lǐng)導(dǎo)者進(jìn)行日志復(fù)制的優(yōu)先級按從高到低的順序就是（D，B，E，C）。于是領(lǐng)導(dǎo)者節(jié)點(diǎn)從跟隨者節(jié)點(diǎn)D開始為跟隨者節(jié)點(diǎn)分配在本輪心跳周期的日志復(fù)制數(shù)量，將索引為5、6、7的三個(gè)日志項(xiàng)復(fù)制到發(fā)送給跟隨者節(jié)點(diǎn)D。然后再將索引為6、7的兩個(gè)日志項(xiàng)復(fù)制到發(fā)送給跟隨者節(jié)點(diǎn)B，領(lǐng)導(dǎo)者節(jié)點(diǎn)在該次心跳超時(shí)中的日志分發(fā)數(shù)量使用完畢，領(lǐng)導(dǎo)者節(jié)點(diǎn)等待跟隨者節(jié)點(diǎn)B、D關(guān)于這次附加日志請求的響應(yīng)來更新集群中的CommittedIndex，在狀態(tài)機(jī)執(zhí)行到該日志項(xiàng)時(shí)完成對產(chǎn)生相應(yīng)日志項(xiàng)的請求的響應(yīng)。

通過領(lǐng)導(dǎo)者在每輪心跳中優(yōu)先將日志分發(fā)數(shù)量分配在系統(tǒng)中與自身日志同步程度最高的一半跟隨者節(jié)點(diǎn)的方式，在同等節(jié)點(diǎn)規(guī)模中的分布式存儲系統(tǒng)中，應(yīng)用了基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制的Raft算法構(gòu)建的分布式系統(tǒng)比應(yīng)用原始Raft算法構(gòu)建的分布式系統(tǒng)能夠更快地對新日志項(xiàng)進(jìn)行提交，客戶端也能更快地收到響應(yīng)，提高了系統(tǒng)寫請求的吞吐量。

3.2 基于窗口流水線的日志分發(fā)委托機(jī)制

在上述基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制的Raft算法優(yōu)化中，Raft集群中的領(lǐng)導(dǎo)者在心跳周期函數(shù)觸發(fā)時(shí)按照一定的優(yōu)先級排序方式優(yōu)先將日志項(xiàng)復(fù)制給集群中日志與自己同步程度較高的節(jié)點(diǎn)。以期望于領(lǐng)導(dǎo)者中的未能提交的日志項(xiàng)能夠更快地被復(fù)制到集群中的一半以上節(jié)點(diǎn)中，從而能使領(lǐng)導(dǎo)者能夠更快地對集群中的日志項(xiàng)進(jìn)行提交，提高系統(tǒng)整體對寫請求的吞吐量。

由于領(lǐng)導(dǎo)者總是優(yōu)先考慮將日志項(xiàng)復(fù)制給與自己同步程度較高的節(jié)點(diǎn)，在每輪心跳周期函數(shù)中領(lǐng)導(dǎo)者可以進(jìn)行分配的日志項(xiàng)數(shù)量有限的情況下，當(dāng)系統(tǒng)出現(xiàn)寫請求大量不停到來的極端情況時(shí)，與領(lǐng)導(dǎo)者節(jié)點(diǎn)日志同步程度較低的節(jié)點(diǎn)就會出現(xiàn)“饑餓”的情況，日志同步程度遲遲跟不上領(lǐng)導(dǎo)者節(jié)點(diǎn)，基于窗口流水線的日志分發(fā)委托機(jī)制就是在上述背景中被構(gòu)思而來。

在基于窗口流水線的日志分發(fā)委托機(jī)制中，基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制中領(lǐng)導(dǎo)者節(jié)點(diǎn)在每一輪心跳周期中都會計(jì)算集群中的跟隨者與自己日志的同步程度并以此作為優(yōu)先級將該輪心跳周期中的日志項(xiàng)的復(fù)制數(shù)量進(jìn)行分配。然后該同步程度排序結(jié)果會被基于窗口流水線的日志分發(fā)委托機(jī)制所使用，領(lǐng)導(dǎo)者會為每個(gè)跟隨者節(jié)點(diǎn)設(shè)定委托復(fù)制窗口，每個(gè)跟隨者的委托復(fù)制窗口中保存了領(lǐng)導(dǎo)者在之前的心跳周期中向其他跟隨者委托復(fù)制日志項(xiàng)給該跟隨者節(jié)點(diǎn)的記錄，記錄的定義如表1所示。

在領(lǐng)導(dǎo)者進(jìn)行日志復(fù)制的心跳周期中，領(lǐng)導(dǎo)者根據(jù)跟隨者中日志與自身日志同步程度由低到高進(jìn)行排序，然后在進(jìn)行日志分發(fā)委托時(shí)根據(jù)跟隨者節(jié)點(diǎn)數(shù)量將跟隨者節(jié)點(diǎn)分為兩組。當(dāng)跟隨者數(shù)量是偶數(shù)時(shí)，將排序在前一半的節(jié)點(diǎn)和后一半的節(jié)點(diǎn)各分到一組中；當(dāng)跟隨者數(shù)量是奇數(shù)時(shí)，舍棄掉排序在最中間的節(jié)點(diǎn)，然后將排序在最中間節(jié)點(diǎn)前面的節(jié)點(diǎn)以及后面的節(jié)點(diǎn)各分到一組中。日志同步程度較高的那組分組被稱為委托者分組，日志同步程度較低的那組分組被稱為接收者分組，經(jīng)過這樣的分組后，兩組中節(jié)點(diǎn)的數(shù)量相同。然后領(lǐng)導(dǎo)者節(jié)點(diǎn)會根據(jù)兩組中節(jié)點(diǎn)在其分組中同一位置進(jìn)行日志項(xiàng)復(fù)制委托，如由委托者分組的同步程度最高的節(jié)點(diǎn)負(fù)責(zé)對接收者分組的同步程度最高節(jié)點(diǎn)進(jìn)行委托復(fù)制，委托者分組的中同步程度最低的節(jié)點(diǎn)負(fù)責(zé)對接收者分組中同步程度最低的節(jié)點(diǎn)進(jìn)行委托復(fù)制。

在領(lǐng)導(dǎo)者對跟隨者進(jìn)行日志分發(fā)委托過程中會根據(jù)每個(gè)接收者委托復(fù)制窗口中的記錄、委托者和接收者節(jié)點(diǎn)的日志狀態(tài)計(jì)算委托者需要發(fā)送的日志項(xiàng)的起始索引以及結(jié)束索引，并將其他相關(guān)信息一起登記在該接收者的委托復(fù)制窗口中，然后向攜帶相關(guān)參數(shù)向委托者發(fā)起請求。

委托者節(jié)點(diǎn)在接收到來自領(lǐng)導(dǎo)者的委托復(fù)制請求后，會攜帶本次領(lǐng)導(dǎo)者委托的相應(yīng)日志項(xiàng)以及其他參數(shù)向接收者發(fā)起請求并將日志項(xiàng)復(fù)制到接收者中。接收者在收到來自委托者的日志復(fù)制請求時(shí)的處理邏輯與Raft算法中跟隨者收到領(lǐng)導(dǎo)者的日志復(fù)制請求時(shí)保持一致，然后向領(lǐng)導(dǎo)者發(fā)起請求告知接收者此時(shí)日志的相關(guān)狀態(tài)，由領(lǐng)導(dǎo)者完成對接收者委托復(fù)制窗口中記錄的更新以及日志狀態(tài)的更新。領(lǐng)導(dǎo)者進(jìn)行委托復(fù)制的算法流程如算法2所示。

算法2 基于窗口流水線的日志分發(fā)委托機(jī)制

輸入：跟隨者數(shù)量n;動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制計(jì)算得到的nextlndexSortVec。

if n%2==0 then

/*跟隨者數(shù)量為偶數(shù)，則取同步程度最高的一半跟隨者節(jié)點(diǎn)成為委托者節(jié)點(diǎn)*/

senderVec=［［idxn2+1，Nn2+1］，［idxn2+2，Nn2+2］，…，［idxn，Nn］］，（idxn2+1lt;idxn2+2lt;…lt;idxn）;

else

/*跟隨者數(shù)量為奇數(shù)，舍棄同步程度排在最中間的節(jié)點(diǎn)，取剩余的同步程度最高的一半跟隨者節(jié)點(diǎn)成為委托者節(jié)點(diǎn)*/

senderVec=［［idxn2+2，Nn2+2］，［idxn2+3，Nn2+3］，…， ［idxn，Nn］］，（idxn2+2lt;idxn2+3lt;…lt;idxn）;

end if

//接收者節(jié)點(diǎn)則取同步程度較低的另一組節(jié)點(diǎn)

receiverVec=［［idx1，N1］，［idx2，N2］，…，［idxn2，Nn2］］，（idx1lt;idx2lt;…lt;idxn2）;

receiverNum=n2

for i=1; ilt;=receiverNum; i++ do

/*針對每一個(gè)接收者分配一個(gè)委托者對其進(jìn)行日志分發(fā)，分配原則是委托者中同步程度最低的節(jié)點(diǎn)對接收者中同步程度最低的節(jié)點(diǎn)進(jìn)行日志分發(fā)，委托者中同步程度最高的節(jié)點(diǎn)對接收者中同步程度最高的節(jié)點(diǎn)進(jìn)行日志分發(fā)*/

sender = senderVec[i];

receiver = receiverVec[i];

if sender.idxgt;receiver.idx then

if receiver.N委托復(fù)制窗口未滿or有過期記錄then

領(lǐng)導(dǎo)者根據(jù)receiver.N節(jié)點(diǎn)的委托復(fù)制窗口中的記錄計(jì)算sender.N節(jié)點(diǎn)本次委托中需要向receiver.N節(jié)點(diǎn)發(fā)起復(fù)制的日志的起始索引和結(jié)束索引以及其他相關(guān)信息;

領(lǐng)導(dǎo)者更新receiver.N節(jié)點(diǎn)的委托復(fù)制窗口中的相關(guān)記錄;

領(lǐng)導(dǎo)者攜帶相關(guān)委托的參數(shù)向sender.N節(jié)點(diǎn)發(fā)起日志分發(fā)委托的請求;

end if

end if

end for

同樣用圖2對基于窗口流水線的日志分發(fā)委托機(jī)制進(jìn)行講解，假設(shè)領(lǐng)導(dǎo)者當(dāng)前的心跳節(jié)拍為10（心跳節(jié)拍隨著每輪心跳函數(shù)觸發(fā)增加），任期為1，每個(gè)節(jié)點(diǎn)委托復(fù)制窗口的容量為3，窗口中的記錄在其記錄中的ticks參數(shù)3個(gè)心跳節(jié)拍以后過期，在一次分發(fā)委托中包含的日志數(shù)量限制為5。根據(jù)算法對跟隨者節(jié)點(diǎn)按照日志同步程度由低到高進(jìn)行排序后，排序結(jié)果為CEDB，跟隨者節(jié)點(diǎn)D、B被分組到委托者分組，跟隨者節(jié)點(diǎn)C、E被分組到接收者分組，然后領(lǐng)導(dǎo)者節(jié)點(diǎn)委托節(jié)點(diǎn)B對節(jié)點(diǎn)E進(jìn)行索引I范圍為4到5的日志復(fù)制，委托節(jié)點(diǎn)D對節(jié)點(diǎn)C進(jìn)行索引范圍為3到4的日志復(fù)制。

在原始Raft算法中，領(lǐng)導(dǎo)者對跟隨者進(jìn)行日志分發(fā)這個(gè)過程中所有跟隨者節(jié)點(diǎn)中日志項(xiàng)都來自于領(lǐng)導(dǎo)者，跟隨者之間并不會相互發(fā)送日志項(xiàng)，這就會導(dǎo)致當(dāng)系統(tǒng)節(jié)點(diǎn)數(shù)量增多時(shí)領(lǐng)導(dǎo)者節(jié)點(diǎn)會面臨非常大的日志分發(fā)的壓力。基于窗口流水線的日志分發(fā)委托機(jī)制通過在領(lǐng)導(dǎo)者進(jìn)行每一次心跳函數(shù)進(jìn)行日志分發(fā)這個(gè)過程中為日志同步程度較低的節(jié)點(diǎn)分配日志同步較高的節(jié)點(diǎn)進(jìn)行一次指定區(qū)間日志的分發(fā)委托，窗口中具備多個(gè)存放記錄的容量是為了提高這種分發(fā)委托機(jī)制的效率。在跟隨者的委托復(fù)制窗口中記錄未滿時(shí)，領(lǐng)導(dǎo)者不用等待跟隨者在接收來自委托者的日志復(fù)制請求后的響應(yīng)就可以在下一次心跳函數(shù)中根據(jù)窗口中記錄信息給相應(yīng)跟隨者繼續(xù)安排委托者對其進(jìn)行指定區(qū)間日志的分發(fā)。通過這種日志分發(fā)委托機(jī)制，領(lǐng)導(dǎo)者節(jié)點(diǎn)能夠加速集群中所有節(jié)點(diǎn)日志趨于一致的時(shí)間，每個(gè)節(jié)點(diǎn)都能更快實(shí)現(xiàn)在本節(jié)點(diǎn)狀態(tài)機(jī)中所維護(hù)的數(shù)據(jù)一致。

4 Raft算法優(yōu)化性能對比測試

4.1 測試環(huán)境

系統(tǒng)測試環(huán)境的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為總線型，由千兆網(wǎng)絡(luò)連接服務(wù)器A、B、C，服務(wù)器A和B是通過VirtualBox虛擬機(jī)軟件分別在兩臺物理設(shè)備上虛擬化構(gòu)建而成， 然后將它們通過虛擬網(wǎng)卡接入到千兆交換機(jī)中。三臺服務(wù)器的系統(tǒng)均為 Ubuntu 20.04 LTS 64 bit，文件系統(tǒng)為EXT4，網(wǎng)卡速度100 Mbps，具體差異配置如表2所示。

4.2 基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制

為了減少系統(tǒng)中其他因素對基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制性能測試的影響，在測試時(shí)，限制了存儲集群中每個(gè)節(jié)點(diǎn)成為領(lǐng)導(dǎo)者時(shí)在一次心跳周期（200 ms）中只能向集群中的所有跟隨者節(jié)點(diǎn)傳輸1 000個(gè)日志項(xiàng)。這樣就能在一定程度上減少日志項(xiàng)由領(lǐng)導(dǎo)者節(jié)點(diǎn)傳輸給跟隨者節(jié)點(diǎn)時(shí)其他因素成為瓶頸帶來的影響，同時(shí)分別在集群中節(jié)點(diǎn)的數(shù)量為3個(gè)和5個(gè)的部署方式下進(jìn)行測試。

在系統(tǒng)中分別采用未經(jīng)優(yōu)化的Raft算法和基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制優(yōu)化下的Raft算法對存儲集群1、2、3進(jìn)行寫請求的吞吐量測試，每次測試通過腳本提交數(shù)量為20 000的寫請求，多次測試并統(tǒng)計(jì)系統(tǒng)的平均吞吐量，測試結(jié)果如圖3所示。

根據(jù)圖3的結(jié)果可以計(jì)算得到，基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制優(yōu)化的Raft算法在三個(gè)和五個(gè)節(jié)點(diǎn)分別構(gòu)成的集群中單位時(shí)間內(nèi)吞吐量對比未經(jīng)優(yōu)化的Raft算法提升了97.9百分點(diǎn)和98.3百分點(diǎn)。在三節(jié)點(diǎn)構(gòu)建的集群和五節(jié)點(diǎn)構(gòu)建的集群中，跟隨者數(shù)量分別為兩個(gè)和四個(gè)。在基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制中，與原始Raft算法構(gòu)建的集群中領(lǐng)導(dǎo)者在心跳函數(shù)中將日志分發(fā)給所有跟隨者節(jié)點(diǎn)相比，三節(jié)點(diǎn)集群領(lǐng)導(dǎo)者在每輪心跳函數(shù)中優(yōu)先將1 000個(gè)日志項(xiàng)分配數(shù)量分發(fā)給其中一個(gè)跟隨者，五節(jié)點(diǎn)集群領(lǐng)導(dǎo)者在每輪心跳函數(shù)中優(yōu)先將1 000個(gè)日志項(xiàng)分配數(shù)量分發(fā)給其中兩個(gè)跟隨者。由于領(lǐng)導(dǎo)者只需要將日志項(xiàng)復(fù)制到集群一半以上節(jié)點(diǎn)時(shí)就可以對其進(jìn)行提交并響應(yīng)，理論上在偶數(shù)個(gè)跟隨者的集群中領(lǐng)導(dǎo)者對寫請求的吞吐量能提升一倍，通過上述實(shí)驗(yàn)可以看到寫請求的吞吐量的提升都在95個(gè)百分點(diǎn)以上。由此可見，基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制優(yōu)化的Raft算法對比原始Raft算法在單位時(shí)間內(nèi)能對更多的日志項(xiàng)進(jìn)行提交，提高集群對寫請求在單位時(shí)間內(nèi)的吞吐量。

4.3 基于窗口流水線的日志分發(fā)委托機(jī)制

在測試時(shí)，在三個(gè)節(jié)點(diǎn)構(gòu)成的集群中限制了每個(gè)節(jié)點(diǎn)成為領(lǐng)導(dǎo)者時(shí)在一次心跳周期（200 ms）中只能向集群中的所有跟隨者節(jié)點(diǎn)傳輸500個(gè)日志項(xiàng)，這樣就能在一定程度上減少日志項(xiàng)由領(lǐng)導(dǎo)者節(jié)點(diǎn)傳輸給跟隨者節(jié)點(diǎn)時(shí)其他因素成為瓶頸的帶來的影響，同時(shí)允許領(lǐng)導(dǎo)者節(jié)點(diǎn)在對其他節(jié)點(diǎn)進(jìn)行一次日志分發(fā)委托時(shí)允許復(fù)制的日志項(xiàng)數(shù)最多為500個(gè)。在五個(gè)節(jié)點(diǎn)構(gòu)成的集群中限制了節(jié)點(diǎn)成為領(lǐng)導(dǎo)者時(shí)在一次心跳周期（200 ms）中只能向集群中的所有跟隨者節(jié)點(diǎn)傳輸1 000個(gè)日志項(xiàng)，同時(shí)允許領(lǐng)導(dǎo)者節(jié)點(diǎn)在對其他節(jié)點(diǎn)進(jìn)行一次日志分發(fā)委托時(shí)允許復(fù)制的日志項(xiàng)數(shù)最多為1 000個(gè)。同樣分別在集群中節(jié)點(diǎn)的數(shù)量為3個(gè)和5個(gè)的部署方式下進(jìn)行測試。

在系統(tǒng)中分別采用未經(jīng)優(yōu)化的Raft算法和在基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制上實(shí)現(xiàn)的基于窗口流水線的日志分發(fā)委托機(jī)制優(yōu)化的Raft算法對存儲集群1、2、3進(jìn)行集群所有節(jié)點(diǎn)日志最終同步到一致時(shí)所需時(shí)間的測試。基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制會使得集群中跟隨者節(jié)點(diǎn)之間日志同步程度分為較高和較低兩個(gè)群體，跟隨者這兩個(gè)群體的日志同步程度差異也是基于窗口流水線的日志分發(fā)委托機(jī)制發(fā)揮作用的基礎(chǔ)。然后在三節(jié)點(diǎn)集群中通過腳本提交數(shù)量為20 000的寫請求并統(tǒng)計(jì)所有節(jié)點(diǎn)中日志同步的時(shí)間，在五節(jié)點(diǎn)集群中通過腳本提交數(shù)量為10 000的寫請求并統(tǒng)計(jì)所有節(jié)點(diǎn)中日志同步的時(shí)間，多次運(yùn)行上述腳本求得同步時(shí)間平均值，測試結(jié)果如圖4所示。

根據(jù)圖4的結(jié)果可以計(jì)算得到，基于窗口流水線的日志分發(fā)委托機(jī)制優(yōu)化下的Raft算法在三個(gè)和五個(gè)節(jié)點(diǎn)構(gòu)成的集群上的日志同步時(shí)間分別為未經(jīng)優(yōu)化的Raft算法同步時(shí)間的54.3%、53.5%。

在三節(jié)點(diǎn)和五節(jié)點(diǎn)構(gòu)建的集群中，跟隨者數(shù)量分別為兩個(gè)和四個(gè)。在基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制中，領(lǐng)導(dǎo)者節(jié)點(diǎn)將每輪心跳函數(shù)中的日志項(xiàng)分配數(shù)量優(yōu)先分發(fā)給系統(tǒng)中一半的跟隨者節(jié)點(diǎn)，造成系統(tǒng)中在所有節(jié)點(diǎn)日志在完全同步前有一半跟隨者節(jié)點(diǎn)中日志的同步程度始終比另一半跟隨者節(jié)點(diǎn)高。然后在基于窗口流水線的日志分發(fā)委托機(jī)制中，領(lǐng)導(dǎo)者節(jié)點(diǎn)為日志同步程度落后的節(jié)點(diǎn)分配日志同步程度較高的節(jié)點(diǎn)進(jìn)行日志復(fù)制，將部分領(lǐng)導(dǎo)者對跟隨者進(jìn)行日志復(fù)制的壓力轉(zhuǎn)移到同步程度較高的跟隨者節(jié)點(diǎn)中。

通過實(shí)驗(yàn)可以得到基于窗口流水線的日志分發(fā)委托機(jī)制對比原始Raft算法能夠更快地使得Raft集群中節(jié)點(diǎn)的日志趨向一致。

4.4 吞吐量測試

清空之前功能測試建立的所有存儲集群以及一致性哈希集群中的信息，在服務(wù)器A中啟動注冊中心和一致性哈希集群節(jié)點(diǎn)1、2、3，分別新增存儲集群1，在服務(wù)器A中啟動存儲集群1中的節(jié)點(diǎn)1、2、3；新增存儲集群2，在服務(wù)器B中啟動存儲集群2中的節(jié)點(diǎn)4、5、6；新增存儲集群3，在服務(wù)器C中啟動存儲集群3中的節(jié)點(diǎn)7、8、9；然后分別進(jìn)行由同個(gè)服務(wù)器三個(gè)節(jié)點(diǎn)構(gòu)成的單存儲集群進(jìn)行寫請求和讀請求的吞吐量的性能測試。

對上述測試步驟重復(fù)多次并統(tǒng)計(jì)不同數(shù)量線程下所有請求完成的平均時(shí)間，吞吐量性能測試結(jié)果如圖5所示。

在吞吐量性能測試中，根據(jù)圖5可以發(fā)現(xiàn)不同存儲集群對寫請求的吞吐量隨著構(gòu)成存儲集群的虛擬機(jī)的配置不同而產(chǎn)生差異。

原因在于寫請求需要由存儲集群中的領(lǐng)導(dǎo)者寫到日志中并在心跳周期函數(shù)中被復(fù)制到集群中一半以上節(jié)點(diǎn)后領(lǐng)導(dǎo)者才可以將其提交到狀態(tài)機(jī)中執(zhí)行并對其進(jìn)行響應(yīng)，同時(shí)還要將日志項(xiàng)存儲到本地文件中保存，這些操作對時(shí)間的需求較大，所以寫請求吞吐量的性能測試結(jié)果對比起讀請求吞吐量性能測試結(jié)果來說較低。

讀和寫請求的吞吐量在剛開始都會隨著并發(fā)線程的數(shù)量增加而提升，在并發(fā)線程數(shù)量增加到5個(gè)線程的時(shí)候吞吐量達(dá)到系統(tǒng)峰值，吞吐量在達(dá)到峰值后會隨著并發(fā)線程數(shù)量的增加而降低，系統(tǒng)寫請求吞吐量的瓶頸主要在對包含寫請求的日志項(xiàng)進(jìn)行本地存儲并在集群中達(dá)成一致這個(gè)過程。

吞吐量隨著并發(fā)數(shù)先增加再降低的現(xiàn)象可以通過系統(tǒng)資源利用與并發(fā)數(shù)的關(guān)系來解釋。在低并發(fā)數(shù)時(shí)，系統(tǒng)資源充足，能夠快速處理請求，響應(yīng)時(shí)間短，因此吞吐量隨著并發(fā)數(shù)的增加而增加。然而，隨著并發(fā)數(shù)的繼續(xù)增加，系統(tǒng)資源逐漸被占滿，處理每個(gè)請求所需的資源變多，導(dǎo)致響應(yīng)時(shí)間增長。當(dāng)并發(fā)數(shù)達(dá)到某個(gè)臨界點(diǎn)時(shí)，系統(tǒng)資源接近或達(dá)到上限，處理請求的效率降低，響應(yīng)時(shí)間大幅增加，根據(jù)吞吐量的計(jì)算公式，響應(yīng)時(shí)間增長導(dǎo)致吞吐量下降。

4.5 可擴(kuò)展性測試

清空之前測試建立的所有存儲集群以及一致性哈希集群中的信息，在服務(wù)器A中啟動注冊中心和一致性哈希集群節(jié)點(diǎn)1、2、3，然后分別啟動存儲集群1和2、存儲集群1、2和3，進(jìn)行兩個(gè)、三個(gè)存儲集群下的吞吐量的性能測試，查看系統(tǒng)在集群規(guī)模增大情況下的吞吐量的性能變化情況，驗(yàn)證系統(tǒng)是否具備較高的可擴(kuò)展性。

運(yùn)行腳本啟動不同數(shù)量的線程對隨機(jī)生成數(shù)量為50 000的目錄路徑調(diào)用mkdirs向當(dāng)前啟動的存儲集群發(fā)起創(chuàng)建目錄請求進(jìn)行寫請求吞吐量的性能測試，然后以同樣的方式啟動不同數(shù)量的線程對隨機(jī)生成的50 000數(shù)量的目錄路徑并調(diào)用lsdir對當(dāng)前啟動的存儲集群發(fā)起查看目錄請求進(jìn)行讀請求吞吐量的性能測試。

對上述測試步驟進(jìn)行多次并統(tǒng)計(jì)不同數(shù)量線程下所有請求完成的平均時(shí)間，不同集群數(shù)量規(guī)模下的吞吐量性能測試結(jié)果如圖6所示。

在多集群吞吐量性能測試中，根據(jù)圖6測試結(jié)果，系統(tǒng)在啟動集群1和2的時(shí)候隨著并發(fā)線程數(shù)量的增加，系統(tǒng)的讀寫請求的吞吐量也在增加，在并發(fā)線程數(shù)量達(dá)到15時(shí)吞吐量達(dá)到峰值，隨后隨著并發(fā)線程數(shù)量的增加，吞吐量開始降低。系統(tǒng)在啟動集群1、2和3時(shí)在并發(fā)線程數(shù)量達(dá)到25時(shí)吞吐量達(dá)到峰值，隨后同樣隨著并發(fā)線程數(shù)量的增加，吞吐量開始降低。根據(jù)系統(tǒng)在啟動多個(gè)集群下吞吐量的變化情況可以得到隨著系統(tǒng)集群數(shù)量的增加，在并發(fā)線程未達(dá)到系統(tǒng)性能峰值時(shí)系統(tǒng)的整體吞吐量會提升，能夠隨著并發(fā)線程數(shù)量的增加在單位時(shí)間內(nèi)處理更多的讀寫請求，同時(shí)隨著系統(tǒng)中集群數(shù)量的增加系統(tǒng)在達(dá)到吞吐量峰值時(shí)的并發(fā)線程數(shù)量也在增加。

在系統(tǒng)吞吐量未到達(dá)峰值時(shí)，提升并發(fā)線程數(shù)量能夠更加充分地利用系統(tǒng)中集群的資源從而提高吞吐量，但是在系統(tǒng)吞吐量達(dá)到峰值后再增加并發(fā)線程時(shí)，由于線程之間的競爭導(dǎo)致系統(tǒng)吞吐量下降。由上述測試可知，增加系統(tǒng)中的集群數(shù)量可以提高系統(tǒng)吞吐量，系統(tǒng)具備一定的可擴(kuò)展性。

5 結(jié)束語

Raft算法的強(qiáng)領(lǐng)導(dǎo)特性在節(jié)點(diǎn)數(shù)量增多時(shí)會帶來巨大的日志分發(fā)開銷，限制了系統(tǒng)性能和水平擴(kuò)展能力。本文在Raft的基礎(chǔ)上，提出了一種新的支持高并發(fā)、海量存儲、高可靠的分布式存儲方案。在 Raft 算法領(lǐng)導(dǎo)者進(jìn)行日志分發(fā)過程中，本文提出了一種基于動態(tài)優(yōu)先級分配的日志分發(fā)機(jī)制，該機(jī)制讓領(lǐng)導(dǎo)者根據(jù)系統(tǒng)中跟隨者節(jié)點(diǎn)日志與自己日志的同步程度來決定日志分發(fā)到不同跟隨者節(jié)點(diǎn)的先后順序，從而更快地將日志項(xiàng)復(fù)制到集群一半以上節(jié)點(diǎn)中，加快日志項(xiàng)的提交速度并提高系統(tǒng)寫請求的吞吐量。在 Raft 算法領(lǐng)導(dǎo)者進(jìn)行日志分發(fā)過程中，本文提出了一種基于窗口流水線的日志分發(fā)委托機(jī)制，該機(jī)制讓領(lǐng)導(dǎo)者節(jié)點(diǎn)指派日志同步程度較高的跟隨者節(jié)點(diǎn)對日志同步程度較低的跟隨者節(jié)點(diǎn)進(jìn)行日志分發(fā)，將領(lǐng)導(dǎo)者部分日志分發(fā)的壓力轉(zhuǎn)移到跟隨者，縮短了系統(tǒng)中節(jié)點(diǎn)日志趨向一致的時(shí)間。

在未來的研究過程中，可以通過改進(jìn)一致性模型和引入更高效的共識算法，增強(qiáng)分布式系統(tǒng)的可靠性；利用新型硬件降低延遲并通過智能數(shù)據(jù)分片提升吞吐量；采用強(qiáng)加密技術(shù)和隱私保護(hù)計(jì)算，加強(qiáng)安全與隱私保護(hù)；集成云原生與邊緣計(jì)算，提升系統(tǒng)靈活性和響應(yīng)速度。

參考文獻(xiàn)：

[1]Reinsel D， Gantz J，Rydning J. Data age 2025： the evolution of data to life-critical [EB/OL]. （2017） [2024-04-12] . https：//www. seagate.com/files/www-content/our-story/trends/files/data-age-2025-white-paper-simplified-chinese.pdf.

[2]Burrows M. The chubby lock service for loosely-coupled distributed systems [C]// Proc of the 7th Symposium on Operating Systems Design and Implementation.Berkeley，CA： USENIX Association， 2006： 335-350.

[3]Calder B， Wang J，Ogus A， et al. Windows azure storage： a highly available cloud storage service with strong consistency [C]// Proc of the 23rd ACM Symposium on Operating Systems Principles. New York： ACM Press， 2011： 143-157.

[4]Chandra T D， Griesemer R， Redstone J. Paxos made live： an engineering perspective [C]// Proc of the 26th Annual ACM Symposium on Principles of Distributed Computing. New York： ACM Press， 2007： 398-407.

[5]Lamport L.Byzantizing Paxos by refinement [C]//Proc of International Symposium on Distributed Computing. Berlin： Springer， 2011： 211-224.

[6]Marandi P J， Primi M，Schiper N， et al. Ring Paxos： a high-throughput atomic broadcast protocol [C]// Proc of IEEE/IFIP International Conference on Dependable Systems and Networks. Piscata-way， NJ： IEEE Press， 2010： 527-536.

[7]Marandi P J， Primi M， Pedone F. Multi-RingPaxos [C]//Proc of IEEE/IFIP International Conference on Dependable Systems and Networks. Piscataway， NJ： IEEE Press， 2012： 1-12.

[8]Kumar V， Agarwal A. HT-Paxos： high throughput state-machine replication protocol for large clustered data centers [J]. The Scientific World Journal， 2015， 2015 （1）： 1-13.

[9]Biely M， Milosevic Z， Santos N，et al. S-Paxos： offloading the leader for high throughput state machine replication [C]//Proc of the 31st" IEEE Symposium on Reliable Distributed Systems. Piscataway， NJ： IEEE Press， 2012： 111-120.

[10]Dang H T， Sciascia D， Canini M， et al. NetPaxos： consensus at network speed [C]// Proc of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research. New York： ACM Press， 2015： 1-7.

[11]Hunt P， Konar M， Junqueira F P，et al. ZooKeeper： wait-free coordination for Internet-scale systems [C]//Proc of USENIX Annual Technical Conference. Berkeley，CA： USENIX Association， 2010： 145-158.

[12]Moraru I， Andersen D G， Kaminsky M. There is more consensus in egalitarian parliaments [C]// Proc of the 24th ACM Symposium on Operating Systems Principles. New York： ACM Press， 2013： 358-372.

[13]LiuFagui， Yang Yingyi. D-Paxos： building hierarchical replicated state machine for cloud environments [J]. IEICE Trans on Information and Systems， 2016， 99 （6）： 1485-1501.

[14]Li Bin， Jiang Jianguo， Yuan Kaiguo. Adv Paxos： making classical Paxos more efficient [J]. The Journal of China Universities of Posts and Telecommunications， 2019， 26 （5）： 33-40，59.

[15]Charapko A， Ailijiang A， Demirbas M. PigPaxos： devouring the communication bottlenecks in distributed consensus [C]// Proc of International Conference on Management of Data. New York： ACM Press， 2021： 235-247.

[16]Ongaro D， Ousterhout J. In search of an understandable consensus algorithm [C]//Proc of USENIX Annual Technical Conference. Berkeley，CA： USENIX Association， 2014： 305-319.

[17]Tian Sihan， Liu Yun， Zhang Yansong， et al. A Byzantine fault-tolerant raft algorithm combined with schnorr signature [C]//Proc of the 15th International Conference on Ubiquitous Information Management and Communication. Piscataway， NJ： IEEE Press， 2021： 1-5.

[18]Zhou Shumeng， Ying Bidi. VG-Raft： an improved Byzantine fault tolerant algorithm based on Raft algorithm [C]//Proc of the 21st International Conference on Communication Technology. Piscataway， NJ： IEEE Press， 2021： 882-886.

[19]王謹(jǐn)東，李強(qiáng)." 基于Raft算法改進(jìn)的實(shí)用評占庭容錯(cuò)共識算法[J].計(jì)算機(jī)應(yīng)用2023， 43（1）： 122-129. （Wang Jindong， Li Qiang. Improved practical Byzantine fault tolerance consensus algorithm based on Raft algorithm [J]. Journal of Computer Applications， 2023， 43（1）： 122-129.）

[20]Paris J F， Long D D E. Pirogue， a lighter dynamic version of the Raft distributed consensus algorithm [C]//Proc of the 34th IEEE International Performance Computing and Communications Conference. Piscataway， NJ： IEEE Press， 2015： 1-8.

[21]Wang Yuchen， Li Shuang， Xu Lei， et al. Improved Raft consensus algorithm in high real-time and highly adversarial environment [C]// Proc of the 18th International Conference on Web Information Systems and Applications. Cham： Springer， 2021： 718-726.

[22]Guo Jinwei， Cai Peng， Qian Weining， et al. Accurate and efficient follower log repair for Raft-replicated database systems [J]. Frontiers of Computer Science， 2021， 15： 1-13.

[23]Wang Zizhong， Li Tongliang， Wang Haixia， et al. Craft： an erasure-coding-supported version of raft for reducing storage cost and network cost [C]// Proc of the 18th USENIX Conference on File and Storage Technologies. Berkeley，CA： USENIX Association， 2020： 297-308.

[24]Wang Rihong， Zhang Lifeng， Xu Quanqing， et al. K-bucket based Raft-like consensus algorithm for permissioned blockchain [C]// Proc of the 25th IEEE International Conference on Parallel and Distributed Systems. Piscataway， NJ： IEEE Press， 2019： 996-999.

[25]Wu Yusen， Wu Yuansai， Liu Yiran， et al. The research of the optimized solutions to Raft consensus algorithm based on a weighted Page-Rank algorithm [C]// Proc of Asia Conference on Algorithms， Computing and Machine Learning. Piscataway， NJ： IEEE Press， 2022： 784-789.

[26]Dautov R， Husom E J. Raft protocol for fault tolerance and self-recovery in federated learning [C]// Proc of the 19th International Symposium on Software Engineering for Adaptive and Self-Managing Systems. New York： ACM Press， 2024： 110-121.

[27]Liu Xiao， Huang Zhao， Wang Quan. An optimized snapshot Raft algorithm for log compression [C]//Proc of the 2nd International Conference on Artificial Intelligence and Blockchain Technology. Piscata-way， NJ： IEEE Press， 2023： 6-10.

[28]Tong Shihua， Zhou Xiang， Fu Wei， et al. Improved Raft algorithm based on communication bottleneck and log inconsistency [C]// Proc of China Automation Congress. Piscataway， NJ： IEEE Press， 2023： 4833-4838.