摘 要：在分布式存儲(chǔ)系統(tǒng)中，Raft（replicated and fault tolerant）算法的強(qiáng)領(lǐng)導(dǎo)特性在節(jié)點(diǎn)數(shù)量增多時(shí)會(huì)帶來(lái)巨大的日志分發(fā)開(kāi)銷，限制了系統(tǒng)性能和水平擴(kuò)展能力。針對(duì)系統(tǒng)性能和擴(kuò)展性瓶頸，提出了兩種新的日志機(jī)制來(lái)優(yōu)化一致性哈希集群分布式存儲(chǔ)方案。第一種是基于動(dòng)態(tài)優(yōu)先級(jí)的日志分發(fā)機(jī)制，日志分發(fā)順序由領(lǐng)導(dǎo)者與跟隨者節(jié)點(diǎn)日志的同步程度決定，加快了日志項(xiàng)的提交速度；第二種是基于窗口流水線的日志分發(fā)機(jī)制，領(lǐng)導(dǎo)者節(jié)點(diǎn)指派日志同步程度較高的跟隨者節(jié)點(diǎn)對(duì)同步程度較低的跟隨者節(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)鍵詞：分布式存儲(chǔ)；一致性哈希；日志分發(fā)；動(dòng)態(tài)優(yōu)先級(jí)分配；窗口流水線

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

文章編號(hào)：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ù)國(guó)際調(diào)研機(jī)構(gòu)IDC發(fā)布的《Data Age 2025》[1]預(yù)測(cè)，全球數(shù)據(jù)總量從2016年的16.1 ZB增長(zhǎng)至2025年的163 ZB。傳統(tǒng)的單機(jī)存儲(chǔ)或集中式存儲(chǔ)已經(jīng)觸及存儲(chǔ)性能和容量方面的瓶頸，無(wú)法滿足數(shù)據(jù)快速增長(zhǎng)背景下對(duì)數(shù)據(jù)存儲(chǔ)的需求。

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

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

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

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

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

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

b）基于窗口流水線的日志分發(fā)委托機(jī)制中，領(lǐng)導(dǎo)者節(jié)點(diǎn)為每個(gè)跟隨者節(jié)點(diǎn)維護(hù)了一個(gè)具有容量上限的委托復(fù)制窗口，窗口中存儲(chǔ)了領(lǐng)導(dǎo)者在之前心跳函數(shù)觸發(fā)時(shí)日志分發(fā)過(guò)程中產(chǎn)生的日志分發(fā)委托的記錄，窗口中的記錄會(huì)在一定時(shí)間內(nèi)得不到跟隨者的響應(yīng)而過(guò)期，在窗口內(nèi)記錄數(shù)量未滿或窗口內(nèi)有記錄過(guò)期的情況下，領(lǐng)導(dǎo)者節(jié)點(diǎn)在日志分發(fā)過(guò)程中為日志落后程度較高的節(jié)點(diǎn)指派跟隨者節(jié)點(diǎn)對(duì)其進(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)中的一致性問(wèn)題涉及同一集群中節(jié)點(diǎn)在初始狀態(tài)一致的情況下，執(zhí)行相同指令序列直至達(dá)到一致?tīng)顟B(tài)的過(guò)程。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ù)等問(wèn)題。

隨著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ū)塊鏈共識(shí)算法中得到廣泛應(yīng)用，包括hhRaft、CRaft、KRaft等變體，優(yōu)化了在不同環(huán)境下的性能和容錯(cuò)能力。

1.1 Raft一致性算法

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

Raft算法定義leader（領(lǐng)導(dǎo)者）、candidate（候選者）、follower（跟隨者） 三種節(jié)點(diǎn)狀態(tài)。通常僅一個(gè)領(lǐng)導(dǎo)者，其余為跟隨者。跟隨者不發(fā)起請(qǐng)求，僅響應(yīng)領(lǐng)導(dǎo)者和候選者。領(lǐng)導(dǎo)者處理客戶端請(qǐng)求，維持與跟隨者心跳，同步集群日志。候選者用于選舉領(lǐng)導(dǎo)者，自增任期、投票并請(qǐng)求其他節(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)日志由序號(hào)標(biāo)記的條目構(gòu)成，含任期、索引及狀態(tài)機(jī)指令。日志條目復(fù)制到集群多數(shù)節(jié)點(diǎn)時(shí)可提交至狀態(tài)機(jī)執(zhí)行，確保節(jié)點(diǎn)間日志高一致性，簡(jiǎn)化系統(tǒng)行為，保障安全性。Raft日志特性如下：

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

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

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

Raft算法問(wèn)世以后被廣泛使用于區(qū)塊鏈共識(shí)算法中，這些Raft算法變體[17～19]提高了Raft算法在拜占庭環(huán)境下的容錯(cuò)能力。文獻(xiàn)[20]引人動(dòng)態(tài)線性投票機(jī)制提高了Raft集群的可用性。hhRaft[21]通過(guò)引用監(jiān)控器的角色來(lái)優(yōu)化Raft達(dá)成共識(shí)的過(guò)程，適用于高實(shí)時(shí)性和高對(duì)抗性環(huán)境。文獻(xiàn)[22]針對(duì)Raft算法提出了一種準(zhǔn)確高效的用于跟隨者進(jìn)行日志修復(fù)的算法。CRaft[23]通過(guò)使用糾刪碼降低了Raft算法運(yùn)行的網(wǎng)絡(luò)成本和存儲(chǔ)成本。Kraft[24]通過(guò)在Kademlia協(xié)議中建立的K-Bucket節(jié)點(diǎn)關(guān)系，優(yōu)化了Raft算法中領(lǐng)導(dǎo)者選舉和共識(shí)過(guò)程，提高了集群中領(lǐng)導(dǎo)者的選舉速度。文獻(xiàn)[25]提出了一種基于節(jié)點(diǎn)活動(dòng)和信用機(jī)制的Raft共識(shí)算法，降低了共識(shí)時(shí)延并具有更高的吞吐量。在最新Raft算法研究中，針對(duì)算法的日志機(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í)，可能會(huì)面臨因節(jié)點(diǎn)在環(huán)上不均勻分布導(dǎo)致的數(shù)據(jù)傾斜問(wèn)題，即在分布式系統(tǒng)中大量的數(shù)據(jù)集中存儲(chǔ)在環(huán)上的某個(gè)節(jié)點(diǎn)。為了解決數(shù)據(jù)傾斜的問(wèn)題，帶虛擬節(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ù)映射和存儲(chǔ)。這樣在分布式系統(tǒng)中新增或刪除節(jié)點(diǎn)時(shí)系統(tǒng)的變動(dòng)就由變動(dòng)節(jié)點(diǎn)周圍的虛擬節(jié)點(diǎn)分擔(dān)，大大降低了發(fā)生數(shù)據(jù)傾斜的可能性，提高了分布式系統(tǒng)的穩(wěn)定性。帶虛擬節(jié)點(diǎn)的一致性哈希算法相對(duì)于普通的一致性哈希算法來(lái)說(shuō)數(shù)據(jù)定位的算法保持不變，只是多了一步由虛擬節(jié)點(diǎn)到物理節(jié)點(diǎn)的映射，不僅適合硬件配置不同的節(jié)點(diǎn)的場(chǎng)景，而且適合節(jié)點(diǎn)規(guī)模會(huì)發(fā)生變動(dòng)以及對(duì)系統(tǒng)穩(wěn)定性要求更高的場(chǎng)景。

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

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

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

一致性哈希集群注冊(cè)中心主要負(fù)責(zé)維護(hù)當(dāng)前一致性哈希集群在線節(jié)點(diǎn)的狀態(tài)信息，當(dāng)一致性哈希集群有節(jié)點(diǎn)上線或離線時(shí)會(huì)在注冊(cè)中心登記相關(guān)信息。當(dāng)有新節(jié)點(diǎn)上線時(shí)也會(huì)返回注冊(cè)中心當(dāng)前在線節(jié)點(diǎn)的相關(guān)信息，同時(shí)注冊(cè)中心會(huì)將該節(jié)點(diǎn)的信息廣播到一致性哈希集群的所有節(jié)點(diǎn)，以便上線節(jié)點(diǎn)加人到集群中。注冊(cè)中心由兩個(gè)RPC服務(wù)（節(jié)點(diǎn)注冊(cè)、節(jié)點(diǎn)離線）、一致性哈希集群節(jié)點(diǎn)信息、心跳維護(hù)這三部分構(gòu)成。注冊(cè)中心會(huì)通過(guò)心跳始終保持跟一致性哈希集群中當(dāng)前處于在線狀態(tài)的節(jié)點(diǎn)的聯(lián)系，并將這種節(jié)點(diǎn)的在線狀態(tài)告知后續(xù)新加人到一致性哈希集群中的節(jié)點(diǎn)，然后新加人的節(jié)點(diǎn)也會(huì)根據(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é)接收面向用戶的存儲(chǔ)客戶端的路由請(qǐng)求，將集群內(nèi)部維護(hù)的存儲(chǔ)集群的服務(wù)區(qū)間等路由信息響應(yīng)給客戶端；接收面向系統(tǒng)管理者的一致性哈希集群客戶端的請(qǐng)求，對(duì)存儲(chǔ)集群的信息進(jìn)行管理；接收來(lái)自存儲(chǔ)集群的請(qǐng)求，保存存儲(chǔ)集群的相關(guān)服務(wù)的地址和端口信息；維持一致性哈希集群節(jié)點(diǎn)中的所維護(hù)的一致性哈希環(huán)在集群內(nèi)多個(gè)節(jié)點(diǎn)中一致，實(shí)現(xiàn)路由信息的冗余備份，保證系統(tǒng)的高可用性。

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

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

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

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

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

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

由于Raft協(xié)議是基于復(fù)制狀態(tài)機(jī)來(lái)實(shí)現(xiàn)集群內(nèi)部中節(jié)點(diǎn)的數(shù)據(jù)一致，每個(gè)節(jié)點(diǎn)都會(huì)有自己的日志和狀態(tài)機(jī)，日志中包含了多個(gè)日志項(xiàng)，這些日志項(xiàng)中存儲(chǔ)了請(qǐng)求發(fā)起方對(duì)系統(tǒng)進(jìn)行操作的指令，狀態(tài)機(jī)中則存儲(chǔ)了節(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)該指令的請(qǐ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)對(duì)相關(guān)數(shù)據(jù)狀態(tài)的更新。在Raft構(gòu)建的分布式系統(tǒng)正常運(yùn)行過(guò)程中，領(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è)過(guò)程中會(huì)存在日志從領(lǐng)導(dǎo)者節(jié)點(diǎn)復(fù)制到系統(tǒng)中所有跟隨者節(jié)點(diǎn)中的這個(gè)開(kāi)銷，領(lǐng)導(dǎo)者在每輪心跳中可以分發(fā)的日志項(xiàng)的數(shù)量并不是無(wú)限的。當(dāng)一個(gè)由Raft協(xié)議實(shí)現(xiàn)的分布式系統(tǒng)中節(jié)點(diǎn)數(shù)量越多時(shí)，這種由領(lǐng)導(dǎo)者將日志復(fù)制到跟隨者所帶來(lái)的時(shí)間開(kāi)銷就越大，將日志項(xiàng)復(fù)制到集群一半以上節(jié)點(diǎn)才能對(duì)日志項(xiàng)進(jìn)行提交的時(shí)間開(kāi)銷也就越大，這就會(huì)導(dǎo)致客戶端從發(fā)起一個(gè)更改集群狀態(tài)機(jī)數(shù)據(jù)的寫請(qǐng)求到得到集群響應(yīng)的時(shí)間就越長(zhǎng)。為此，本文在分布式存儲(chǔ)系統(tǒng)實(shí)現(xiàn)中對(duì)Raft協(xié)議在領(lǐng)導(dǎo)者復(fù)制日志到跟隨者節(jié)點(diǎn)這個(gè)過(guò)程中采取了基于動(dòng)態(tài)優(yōu)先級(jí)分配的日志分發(fā)機(jī)制來(lái)提高集群領(lǐng)導(dǎo)者對(duì)日志項(xiàng)的提交速度，從而提高系統(tǒng)對(duì)客戶端寫請(qǐng)求的寫請(qǐng)求的吞吐量。

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

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

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

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

輸出：nextIndexSortVec。

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

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

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

/*優(yōu)先級(jí)由同步程度排在最中間的節(jié)點(diǎn)到同步程度最高的節(jié)點(diǎn)遞減，然后再?gòu)耐匠潭扰旁谧钪虚g的節(jié)點(diǎn)左邊開(kāi)始的節(jié)點(diǎn)到同步程度最小的節(jié)點(diǎn)之間遞減*/

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

//為優(yōu)先級(jí)中的節(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開(kāi)始的（logIndex-node.idx+1）個(gè)日志項(xiàng)的附加日志請(qǐng)求;

else if loadgt;0 then

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

load = 0;

end if

break;

end if

end for

圖2給出了一個(gè)Raft集群運(yùn)行在某個(gè)時(shí)刻下各個(gè)節(jié)點(diǎn)中的日志示例圖，用以對(duì)優(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í)后，其首先會(huì)向集群中的所有跟隨者發(fā)送僅用于維持與跟隨者節(jié)點(diǎn)之間心跳的附加日志請(qǐng)求用以重置跟隨者中的electionOutTimerId定時(shí)器。然后根據(jù)nextIndexMap中數(shù)據(jù)對(duì)集群中跟隨者節(jié)點(diǎn)按日志同步程度由低到高進(jìn)行排序后，得到排序結(jié)果（C，E，D，B），領(lǐng)導(dǎo)者進(jìn)行日志復(fù)制的優(yōu)先級(jí)按從高到低的順序就是（D，B，E，C）。于是領(lǐng)導(dǎo)者節(jié)點(diǎn)從跟隨者節(jié)點(diǎn)D開(kāi)始為跟隨者節(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)于這次附加日志請(qǐng)求的響應(yīng)來(lái)更新集群中的CommittedIndex，在狀態(tài)機(jī)執(zhí)行到該日志項(xiàng)時(shí)完成對(duì)產(chǎn)生相應(yīng)日志項(xiàng)的請(qǐng)求的響應(yīng)。

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

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

在上述基于動(dòng)態(tài)優(yōu)先級(jí)分配的日志分發(fā)機(jī)制的Raft算法優(yōu)化中，Raft集群中的領(lǐng)導(dǎo)者在心跳周期函數(shù)觸發(fā)時(shí)按照一定的優(yōu)先級(jí)排序方式優(yōu)先將日志項(xiàng)復(fù)制給集群中日志與自己同步程度較高的節(jié)點(diǎn)。以期望于領(lǐng)導(dǎo)者中的未能提交的日志項(xiàng)能夠更快地被復(fù)制到集群中的一半以上節(jié)點(diǎn)中，從而能使領(lǐng)導(dǎo)者能夠更快地對(duì)集群中的日志項(xiàng)進(jìn)行提交，提高系統(tǒng)整體對(duì)寫請(qǐ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)寫請(qǐng)求大量不停到來(lái)的極端情況時(shí)，與領(lǐng)導(dǎo)者節(jié)點(diǎn)日志同步程度較低的節(jié)點(diǎn)就會(huì)出現(xiàn)“饑餓”的情況，日志同步程度遲遲跟不上領(lǐng)導(dǎo)者節(jié)點(diǎn)，基于窗口流水線的日志分發(fā)委托機(jī)制就是在上述背景中被構(gòu)思而來(lái)。

在基于窗口流水線的日志分發(fā)委托機(jī)制中，基于動(dòng)態(tài)優(yōu)先級(jí)分配的日志分發(fā)機(jī)制中領(lǐng)導(dǎo)者節(jié)點(diǎn)在每一輪心跳周期中都會(huì)計(jì)算集群中的跟隨者與自己日志的同步程度并以此作為優(yōu)先級(jí)將該輪心跳周期中的日志項(xiàng)的復(fù)制數(shù)量進(jìn)行分配。然后該同步程度排序結(jié)果會(huì)被基于窗口流水線的日志分發(fā)委托機(jī)制所使用，領(lǐng)導(dǎo)者會(huì)為每個(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)過(guò)這樣的分組后，兩組中節(jié)點(diǎn)的數(shù)量相同。然后領(lǐng)導(dǎo)者節(jié)點(diǎn)會(huì)根據(jù)兩組中節(jié)點(diǎn)在其分組中同一位置進(jìn)行日志項(xiàng)復(fù)制委托，如由委托者分組的同步程度最高的節(jié)點(diǎn)負(fù)責(zé)對(duì)接收者分組的同步程度最高節(jié)點(diǎn)進(jìn)行委托復(fù)制，委托者分組的中同步程度最低的節(jié)點(diǎn)負(fù)責(zé)對(duì)接收者分組中同步程度最低的節(jié)點(diǎn)進(jìn)行委托復(fù)制。

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

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

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

輸入：跟隨者數(shù)量n;動(dòng)態(tài)優(yōu)先級(jí)分配的日志分發(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

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

sender = senderVec[i];

receiver = receiverVec[i];

if sender.idxgt;receiver.idx then

if receiver.N委托復(fù)制窗口未滿or有過(guò)期記錄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ā)委托的請(qǐng)求;

end if

end if

end for

同樣用圖2對(duì)基于窗口流水線的日志分發(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é)拍以后過(guò)期，在一次分發(fā)委托中包含的日志數(shù)量限制為5。根據(jù)算法對(duì)跟隨者節(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對(duì)節(jié)點(diǎn)E進(jìn)行索引I范圍為4到5的日志復(fù)制，委托節(jié)點(diǎn)D對(duì)節(jié)點(diǎn)C進(jìn)行索引范圍為3到4的日志復(fù)制。

在原始Raft算法中，領(lǐng)導(dǎo)者對(duì)跟隨者進(jìn)行日志分發(fā)這個(gè)過(guò)程中所有跟隨者節(jié)點(diǎn)中日志項(xiàng)都來(lái)自于領(lǐng)導(dǎo)者，跟隨者之間并不會(huì)相互發(fā)送日志項(xiàng)，這就會(huì)導(dǎo)致當(dāng)系統(tǒng)節(jié)點(diǎn)數(shù)量增多時(shí)領(lǐng)導(dǎo)者節(jié)點(diǎn)會(huì)面臨非常大的日志分發(fā)的壓力?；诖翱诹魉€的日志分發(fā)委托機(jī)制通過(guò)在領(lǐng)導(dǎo)者進(jìn)行每一次心跳函數(shù)進(jìn)行日志分發(fā)這個(gè)過(guò)程中為日志同步程度較低的節(jié)點(diǎn)分配日志同步較高的節(jié)點(diǎn)進(jìn)行一次指定區(qū)間日志的分發(fā)委托，窗口中具備多個(gè)存放記錄的容量是為了提高這種分發(fā)委托機(jī)制的效率。在跟隨者的委托復(fù)制窗口中記錄未滿時(shí)，領(lǐng)導(dǎo)者不用等待跟隨者在接收來(lái)自委托者的日志復(fù)制請(qǐng)求后的響應(yīng)就可以在下一次心跳函數(shù)中根據(jù)窗口中記錄信息給相應(yīng)跟隨者繼續(xù)安排委托者對(duì)其進(jìn)行指定區(qū)間日志的分發(fā)。通過(guò)這種日志分發(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)化性能對(duì)比測(cè)試

4.1 測(cè)試環(huán)境

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

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

為了減少系統(tǒng)中其他因素對(duì)基于動(dòng)態(tài)優(yōu)先級(jí)分配的日志分發(fā)機(jī)制性能測(cè)試的影響，在測(cè)試時(shí)，限制了存儲(chǔ)集群中每個(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í)其他因素成為瓶頸帶來(lái)的影響，同時(shí)分別在集群中節(jié)點(diǎn)的數(shù)量為3個(gè)和5個(gè)的部署方式下進(jìn)行測(cè)試。

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

根據(jù)圖3的結(jié)果可以計(jì)算得到，基于動(dòng)態(tài)優(yōu)先級(jí)分配的日志分發(fā)機(jī)制優(yōu)化的Raft算法在三個(gè)和五個(gè)節(jié)點(diǎn)分別構(gòu)成的集群中單位時(shí)間內(nèi)吞吐量對(duì)比未經(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è)。在基于動(dòng)態(tài)優(yōu)先級(jí)分配的日志分發(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í)就可以對(duì)其進(jìn)行提交并響應(yīng)，理論上在偶數(shù)個(gè)跟隨者的集群中領(lǐng)導(dǎo)者對(duì)寫請(qǐng)求的吞吐量能提升一倍，通過(guò)上述實(shí)驗(yàn)可以看到寫請(qǐng)求的吞吐量的提升都在95個(gè)百分點(diǎn)以上。由此可見(jiàn)，基于動(dòng)態(tài)優(yōu)先級(jí)分配的日志分發(fā)機(jī)制優(yōu)化的Raft算法對(duì)比原始Raft算法在單位時(shí)間內(nèi)能對(duì)更多的日志項(xiàng)進(jìn)行提交，提高集群對(duì)寫請(qǐng)求在單位時(shí)間內(nèi)的吞吐量。

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

在測(cè)試時(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í)其他因素成為瓶頸的帶來(lái)的影響，同時(shí)允許領(lǐng)導(dǎo)者節(jié)點(diǎn)在對(duì)其他節(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)在對(duì)其他節(jié)點(diǎn)進(jìn)行一次日志分發(fā)委托時(shí)允許復(fù)制的日志項(xiàng)數(shù)最多為1 000個(gè)。同樣分別在集群中節(jié)點(diǎn)的數(shù)量為3個(gè)和5個(gè)的部署方式下進(jìn)行測(cè)試。

在系統(tǒng)中分別采用未經(jīng)優(yōu)化的Raft算法和在基于動(dòng)態(tài)優(yōu)先級(jí)分配的日志分發(fā)機(jī)制上實(shí)現(xiàn)的基于窗口流水線的日志分發(fā)委托機(jī)制優(yōu)化的Raft算法對(duì)存儲(chǔ)集群1、2、3進(jìn)行集群所有節(jié)點(diǎn)日志最終同步到一致時(shí)所需時(shí)間的測(cè)試?；趧?dòng)態(tài)優(yōu)先級(jí)分配的日志分發(fā)機(jī)制會(huì)使得集群中跟隨者節(jié)點(diǎn)之間日志同步程度分為較高和較低兩個(gè)群體，跟隨者這兩個(gè)群體的日志同步程度差異也是基于窗口流水線的日志分發(fā)委托機(jī)制發(fā)揮作用的基礎(chǔ)。然后在三節(jié)點(diǎn)集群中通過(guò)腳本提交數(shù)量為20 000的寫請(qǐng)求并統(tǒng)計(jì)所有節(jié)點(diǎn)中日志同步的時(shí)間，在五節(jié)點(diǎn)集群中通過(guò)腳本提交數(shù)量為10 000的寫請(qǐng)求并統(tǒng)計(jì)所有節(jié)點(diǎn)中日志同步的時(shí)間，多次運(yùn)行上述腳本求得同步時(shí)間平均值，測(cè)試結(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è)。在基于動(dòng)態(tài)優(yōu)先級(jí)分配的日志分發(fā)機(jī)制中，領(lǐng)導(dǎo)者節(jié)點(diǎn)將每輪心跳函數(shù)中的日志項(xiàng)分配數(shù)量?jī)?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)者對(duì)跟隨者進(jìn)行日志復(fù)制的壓力轉(zhuǎn)移到同步程度較高的跟隨者節(jié)點(diǎn)中。

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

4.4 吞吐量測(cè)試

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

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

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

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

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

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

4.5 可擴(kuò)展性測(cè)試

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

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

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

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

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

5 結(jié)束語(yǔ)

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

在未來(lái)的研究過(guò)程中，可以通過(guò)改進(jìn)一致性模型和引入更高效的共識(shí)算法，增強(qiáng)分布式系統(tǒng)的可靠性；利用新型硬件降低延遲并通過(guò)智能數(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í)用評(píng)占庭容錯(cuò)共識(shí)算法[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.