基于分片一致性哈希負(fù)載均衡策略與應(yīng)用

蘇躍明，李 晨，田麗華

(1.西安交通大學(xué) 軟件學(xué)院，陜西 西安 710000；2.百度(中國(guó))有限公司，北京 100000)

基于分片一致性哈希負(fù)載均衡策略與應(yīng)用

蘇躍明1,2，李 晨2，田麗華2

(1.西安交通大學(xué) 軟件學(xué)院，陜西 西安 710000；2.百度(中國(guó))有限公司，北京 100000)

采用一致性哈希進(jìn)行數(shù)據(jù)分區(qū)和負(fù)載均衡的分布式鍵值存儲(chǔ)系統(tǒng)具有高可擴(kuò)展性的特點(diǎn)，但一致性哈希中哈希函數(shù)靜態(tài)負(fù)載均衡的特性不能滿足日益多樣化的應(yīng)用場(chǎng)景需求。為了適應(yīng)以上需求，從一致性哈希策略出發(fā)，結(jié)合動(dòng)態(tài)負(fù)載均衡技術(shù)，設(shè)計(jì)了一種基于一致性哈希的動(dòng)態(tài)負(fù)載均衡策略。該策略使用與物理節(jié)點(diǎn)解耦的分片代替?zhèn)鹘y(tǒng)的虛擬節(jié)點(diǎn)，并利用針對(duì)分片的監(jiān)控信息，從分片級(jí)和節(jié)點(diǎn)級(jí)兩個(gè)層面對(duì)系統(tǒng)負(fù)載進(jìn)行均衡調(diào)度，通過更細(xì)的調(diào)度粒度優(yōu)化均衡效果。實(shí)驗(yàn)結(jié)果表明，該策略保留了一致性哈希策略在系統(tǒng)擴(kuò)展性上的優(yōu)勢(shì)，同時(shí)優(yōu)化了一致性哈希策略負(fù)載均衡的總體效果。利用基于分片的一致性哈希負(fù)載均衡策略，可以有效地均衡系統(tǒng)負(fù)載，提高存儲(chǔ)系統(tǒng)的效率。

一致性哈希；分片；動(dòng)態(tài)負(fù)載均衡；分布式鍵值存儲(chǔ)

1 概 述

為了滿足社交和移動(dòng)互聯(lián)網(wǎng)時(shí)代，海量讀寫請(qǐng)求和數(shù)據(jù)爆發(fā)式的增長(zhǎng)需求，分布式存儲(chǔ)系統(tǒng)被廣泛應(yīng)用。為了快速定位數(shù)據(jù)，同時(shí)提高集群的可擴(kuò)展性，分布式存儲(chǔ)系統(tǒng)多采取一致性哈希算法對(duì)數(shù)據(jù)進(jìn)行分區(qū)，但一致性哈希依賴哈希函數(shù)均衡系統(tǒng)負(fù)載，屬于靜態(tài)均衡策略[1]。

隨著鍵值存儲(chǔ)應(yīng)用領(lǐng)域發(fā)展的多樣化，采用靜態(tài)均衡的存儲(chǔ)系統(tǒng)給企業(yè)造成了極大的資源浪費(fèi)。如何結(jié)合分布式存儲(chǔ)系統(tǒng)的數(shù)據(jù)分區(qū)特點(diǎn)對(duì)其進(jìn)行動(dòng)態(tài)負(fù)載均衡成為迫切需要解決的問題。

負(fù)載均衡策略主要分為動(dòng)態(tài)負(fù)載均衡策略和靜態(tài)負(fù)載均衡策略。靜態(tài)負(fù)載均衡根據(jù)對(duì)系統(tǒng)負(fù)載狀態(tài)的先驗(yàn)分析[2]，預(yù)先制定系統(tǒng)負(fù)載策略，實(shí)現(xiàn)簡(jiǎn)單；而動(dòng)態(tài)負(fù)載均衡通過分析當(dāng)前的系統(tǒng)負(fù)載情況，動(dòng)態(tài)地分配和調(diào)度任務(wù)，適應(yīng)場(chǎng)景多，均衡效果好。一般分布式系統(tǒng)中，常用的負(fù)載均衡算法有隨機(jī)算法、輪詢、權(quán)重輪詢、最小連接數(shù)和動(dòng)態(tài)反饋[3-5]，在利用這些策略進(jìn)行負(fù)載均衡時(shí)，多要求分布式節(jié)點(diǎn)之間具有一定的可替代性，即一個(gè)任務(wù)可由分布式系統(tǒng)中任意的節(jié)點(diǎn)進(jìn)行處理[6]。然而，對(duì)于分布式存儲(chǔ)系統(tǒng)，單個(gè)節(jié)點(diǎn)并不能存儲(chǔ)全量的數(shù)據(jù)，數(shù)據(jù)需要進(jìn)行分區(qū)分塊存儲(chǔ)，導(dǎo)致存儲(chǔ)系統(tǒng)的讀寫任務(wù)只可以由特定節(jié)點(diǎn)處理。因此，分布式存儲(chǔ)系統(tǒng)的負(fù)載均衡與系統(tǒng)的數(shù)據(jù)分區(qū)方式緊密相關(guān)[7]。

目前主流的分區(qū)方式有范圍分區(qū)、列表分區(qū)和哈希分區(qū)三種方式。分布式鍵值存儲(chǔ)系統(tǒng)只有一個(gè)列值，無法基于列表分區(qū)；范圍分區(qū)是按照鍵的范圍來進(jìn)行數(shù)據(jù)分區(qū)，典型的有MongoDB的Sharding分區(qū)方式。文獻(xiàn)[8]通過對(duì)MongoDB的負(fù)載均衡策略進(jìn)行改進(jìn)，優(yōu)化了MongoDB的應(yīng)用場(chǎng)景；而在分布式鍵值存儲(chǔ)系統(tǒng)中，應(yīng)用最廣泛的是哈希分區(qū)方式。相比于范圍分區(qū)，哈希分區(qū)具有天然的靜態(tài)負(fù)載均衡特性，通過選擇合適的哈希函數(shù)，就可以實(shí)現(xiàn)數(shù)據(jù)在哈?？臻g內(nèi)的均衡分布。

常用的哈希函數(shù)有MD5和SHA。文獻(xiàn)[9]給出的一致性哈希解決了哈希分區(qū)在集群擴(kuò)縮容時(shí)的數(shù)據(jù)重分布問題，在此基礎(chǔ)上，Amazon的Dynamo在實(shí)現(xiàn)一致性哈希策略時(shí)提出了虛擬節(jié)點(diǎn)的理論來解決集群內(nèi)節(jié)點(diǎn)之間異構(gòu)的問題[10]。

然而，這些方法都屬于靜態(tài)一致性哈希負(fù)載均衡策略，它們僅依賴于哈希函數(shù)進(jìn)行均衡負(fù)載，面對(duì)集群中部分?jǐn)?shù)據(jù)的熱點(diǎn)訪問帶來的負(fù)載不均，靜態(tài)負(fù)載均衡算法將無法調(diào)節(jié)[11]。

通過分析基于虛擬節(jié)點(diǎn)的一致性哈希策略，結(jié)合動(dòng)態(tài)反饋的負(fù)載均衡技術(shù)，提出了一種基于分片的一致性哈希動(dòng)態(tài)負(fù)載均衡策略。使用與物理節(jié)點(diǎn)解耦的分片代替?zhèn)鹘y(tǒng)的虛擬節(jié)點(diǎn)，并利用針對(duì)分片的監(jiān)控信息對(duì)負(fù)載進(jìn)行均衡調(diào)度。同時(shí)，調(diào)度策略分為分片級(jí)和節(jié)點(diǎn)級(jí)兩個(gè)層面，從而進(jìn)一步優(yōu)化負(fù)載均衡的效果。相比于傳統(tǒng)基于節(jié)點(diǎn)負(fù)載的動(dòng)態(tài)反饋均衡策略，該策略具有更細(xì)的監(jiān)控和調(diào)度粒度，從而實(shí)現(xiàn)了更高效的均衡調(diào)度。

2 一致性哈希策略

一致性哈希由MIT的Karger及其合作者提出，利用哈希函數(shù)將存儲(chǔ)的key和服務(wù)器哈希到同一個(gè)環(huán)形地址空間中，從而確定數(shù)據(jù)和服務(wù)器的映射關(guān)系。

相比于固定哈希系統(tǒng)擴(kuò)容時(shí)需要對(duì)所有節(jié)點(diǎn)上的數(shù)據(jù)進(jìn)行重新分布，當(dāng)采用一致性哈希的系統(tǒng)擴(kuò)容時(shí)，只需要遷移相鄰節(jié)點(diǎn)上的數(shù)據(jù)。為了合理分配集群內(nèi)異構(gòu)節(jié)點(diǎn)的負(fù)載，Amazon在Dynamo中引入虛擬節(jié)點(diǎn)(Virtual Node)概念，一個(gè)物理節(jié)點(diǎn)可配置成多個(gè)虛擬節(jié)點(diǎn)。

3 基于分片的一致性哈希動(dòng)態(tài)負(fù)載均衡策略

基于虛擬節(jié)點(diǎn)的一致性哈希仍然是通過哈希函數(shù)的平衡性，在概率上保證不同虛擬節(jié)點(diǎn)上分配到的數(shù)據(jù)量一致[12]。然而，存儲(chǔ)系統(tǒng)的負(fù)載不均還表現(xiàn)在系統(tǒng)訪問壓力的分布不均，面對(duì)動(dòng)態(tài)變化的訪問負(fù)載，數(shù)據(jù)的平均分布并不足以保證訪問壓力的均衡分布。面對(duì)復(fù)雜的負(fù)載場(chǎng)景，就需要對(duì)系統(tǒng)進(jìn)行動(dòng)態(tài)的負(fù)載均衡。改進(jìn)策略利用分片機(jī)制對(duì)一致性哈希策略進(jìn)行了相應(yīng)的改進(jìn)，主要包括兩點(diǎn)：

(1)將虛擬節(jié)點(diǎn)和物理節(jié)點(diǎn)徹底解耦，采用分片(Fragment)作為數(shù)據(jù)分區(qū)存儲(chǔ)的邏輯單元。

(2)基于分片負(fù)載監(jiān)控，對(duì)系統(tǒng)負(fù)載進(jìn)行動(dòng)態(tài)的均衡調(diào)度。

基于虛擬節(jié)點(diǎn)的一致性哈希策略多采用靜態(tài)配置文件維護(hù)虛擬節(jié)點(diǎn)與物理節(jié)點(diǎn)之間的映射關(guān)系[13]。改進(jìn)策略利用基于分片的一致性哈希，通過動(dòng)態(tài)的分片管理物理節(jié)點(diǎn)與數(shù)據(jù)之間的映射關(guān)系，分片可以進(jìn)行分裂、合并、遷移操作。

3.1數(shù)據(jù)模型

在改進(jìn)的一致性哈希策略中，數(shù)據(jù)與分片之間的位置關(guān)系使用哈希函數(shù)確定。一個(gè)分片處理哈希值在當(dāng)前分片ID與前驅(qū)分片ID之間的數(shù)據(jù)，數(shù)據(jù)與分片之間的映射關(guān)系為：

Ft=(Fi-1≤Hash(Key)

(1)

其中，F(xiàn)t為目標(biāo)分片ID；Fi-1為目標(biāo)分片的前驅(qū)分片ID；Hash為選用的哈希函數(shù)，如MD5、SHA-1等。

利用哈希分區(qū)的靜態(tài)負(fù)載均衡特性，使得數(shù)據(jù)在一致性哈希環(huán)地址空間內(nèi)均勻分布[14]。在獲得目標(biāo)分片ID后，需要查詢目標(biāo)分片所在的物理節(jié)點(diǎn)，分片與物理節(jié)點(diǎn)的映射關(guān)系在負(fù)載均衡過程中會(huì)變化，通過有序的Map表管理。在取得物理節(jié)點(diǎn)的地址后，客戶端與物理節(jié)點(diǎn)直接進(jìn)行數(shù)據(jù)操作。

物理節(jié)點(diǎn)上數(shù)據(jù)的讀寫操作都會(huì)被記錄，存儲(chǔ)系統(tǒng)的負(fù)載與單位時(shí)間內(nèi)數(shù)據(jù)的讀寫請(qǐng)求次數(shù)以及數(shù)據(jù)傳輸量和存儲(chǔ)容量消耗成正比。因此，存儲(chǔ)系統(tǒng)中服務(wù)器的負(fù)載狀況的主要影響因素有：?jiǎn)挝粫r(shí)間讀請(qǐng)求次數(shù)(記為QPS)、單位時(shí)間寫請(qǐng)求次數(shù)(記為UPS)、單位時(shí)間內(nèi)平均傳輸?shù)臄?shù)據(jù)大小(記為DPS)和服務(wù)器消耗的存儲(chǔ)空間(記為S)。而每臺(tái)服務(wù)器所能達(dá)到的最大負(fù)載閾值能夠通過硬件指標(biāo)進(jìn)行計(jì)算，或者通過性能壓力測(cè)試來計(jì)算，因此，服務(wù)器的負(fù)載可以通過式(2)計(jì)算：

其中，QPSmax、UPSmax為指定配置的服務(wù)器在系統(tǒng)要求的讀寫延遲指標(biāo)下，單位時(shí)間內(nèi)的最大讀寫次數(shù)；α,β,γ為權(quán)重因子。根據(jù)服務(wù)器壓測(cè)數(shù)據(jù)設(shè)定，以分片為單位統(tǒng)計(jì)UPS、QPS、DPS三項(xiàng)負(fù)載元數(shù)據(jù)。

基于上述數(shù)據(jù)模型可以實(shí)現(xiàn)對(duì)分布式存儲(chǔ)系統(tǒng)的動(dòng)態(tài)負(fù)載均衡，存儲(chǔ)系統(tǒng)的負(fù)載均衡涉及數(shù)據(jù)的跨節(jié)點(diǎn)遷移，均衡效果具有一定的滯后性?；诜制囊恢滦怨?dòng)態(tài)負(fù)載均衡策略采用時(shí)間窗口的方式，對(duì)一個(gè)時(shí)間窗內(nèi)的平均負(fù)載進(jìn)行分析，從而決定當(dāng)前節(jié)點(diǎn)或者分片是否過載。負(fù)載均衡的主要代價(jià)是數(shù)據(jù)跨節(jié)點(diǎn)遷移帶來的網(wǎng)絡(luò)資源占用，通過分片級(jí)和節(jié)點(diǎn)級(jí)兩個(gè)級(jí)別的負(fù)載均衡操作，降低負(fù)載均衡數(shù)據(jù)遷移的粒度，從而優(yōu)化負(fù)載均衡資源的消耗問題。

3.2分片級(jí)負(fù)載均衡

除了節(jié)點(diǎn)間的負(fù)載不均問題之外，分片間的負(fù)載不均問題也會(huì)導(dǎo)致系統(tǒng)資源的浪費(fèi)。同時(shí)，由于分片是跨節(jié)點(diǎn)數(shù)據(jù)遷移的最小單位，分片之間負(fù)載不均，提高了制定節(jié)點(diǎn)之間負(fù)載均衡策略的復(fù)雜度。而基于分片的一致性哈希動(dòng)態(tài)負(fù)載均衡，在負(fù)載統(tǒng)計(jì)的粒度上可以由傳統(tǒng)的節(jié)點(diǎn)級(jí)細(xì)化到分片級(jí)，利用分片的分裂、合并操作實(shí)現(xiàn)分片級(jí)負(fù)載均衡。

分片級(jí)負(fù)載均衡以同一節(jié)點(diǎn)上分片的平均負(fù)載為目標(biāo)，首先對(duì)時(shí)間窗內(nèi)整個(gè)節(jié)點(diǎn)上所有的分片計(jì)算出一個(gè)平均負(fù)載，記為loadavg。再以平均負(fù)載為基準(zhǔn)設(shè)定閾值，負(fù)載高出閾值的分片加入超載隊(duì)列，低于閾值的加入低載隊(duì)列。對(duì)超載隊(duì)列中的分片進(jìn)行分裂操作，分裂為M個(gè)均載分片，若記待分裂分片負(fù)載為loadcur，則分裂的分片個(gè)數(shù)與當(dāng)前負(fù)載的關(guān)系為：

(3)

記Fi為分裂的第i個(gè)分片的分片號(hào)，則該分片號(hào)可由式(4)給出：

(4)

其中，F(xiàn)0為待分裂分片的前驅(qū)分片號(hào)。

分片的分裂和合并操作可以實(shí)現(xiàn)負(fù)載在分片之間的重分配。由于存儲(chǔ)服務(wù)器同一個(gè)節(jié)點(diǎn)上磁盤內(nèi)和磁盤間的數(shù)據(jù)帶寬要遠(yuǎn)高于機(jī)器之間的網(wǎng)絡(luò)帶寬，因此，節(jié)點(diǎn)內(nèi)分片之間的數(shù)據(jù)遷移效率要遠(yuǎn)高于節(jié)點(diǎn)之間的數(shù)據(jù)遷移效率。針對(duì)分片的負(fù)載均衡策略的主要流程如圖1所示。對(duì)低于輕載閾值的分片，加入輕載分片隊(duì)列，對(duì)分片進(jìn)行合并操作，從而減少管理元信息的數(shù)量，降低系統(tǒng)管理開銷。

3.3節(jié)點(diǎn)級(jí)負(fù)載均衡

分片級(jí)的負(fù)載均衡提高了對(duì)分片的管理和操作效率，但并不能改善不同節(jié)點(diǎn)之間的負(fù)載不均問題，因此，還需要進(jìn)行物理節(jié)點(diǎn)級(jí)別的負(fù)載均衡。物理節(jié)點(diǎn)級(jí)別的負(fù)載均衡主要通過對(duì)分片進(jìn)行跨節(jié)點(diǎn)的遷移來完成。事實(shí)上，就是在改變分片與物理節(jié)點(diǎn)之間的映射關(guān)系，具體流程與分片級(jí)負(fù)載均衡相似。

圖1 分片級(jí)負(fù)載均衡流程

節(jié)點(diǎn)間的負(fù)載均衡由于涉及到數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸，觸發(fā)均衡的閾值一般設(shè)置的較高。負(fù)載均衡的流程與分片級(jí)均衡流程相似，同樣是確定重載節(jié)點(diǎn)后，選取合適的分片向低載節(jié)點(diǎn)遷移?？紤]到某些節(jié)點(diǎn)上分片平均負(fù)載較高，即便最小的分片遷移到其他節(jié)點(diǎn)也會(huì)導(dǎo)致其他節(jié)點(diǎn)成為重載節(jié)點(diǎn)，當(dāng)出現(xiàn)這種情況時(shí)，均衡策略會(huì)先對(duì)當(dāng)前節(jié)點(diǎn)中的部分分片進(jìn)行分裂操作，然后再選取合適的分片遷移。

4 實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證改進(jìn)的一致性哈希動(dòng)態(tài)負(fù)載均衡策略，通過一個(gè)負(fù)載均衡系統(tǒng)對(duì)其進(jìn)行測(cè)試實(shí)驗(yàn)。

測(cè)試環(huán)境中，核心路由連接了動(dòng)態(tài)負(fù)載均衡系統(tǒng)的管理集群、數(shù)據(jù)集群、監(jiān)控集群以及客戶端。管理集群是系統(tǒng)的中心節(jié)點(diǎn)；數(shù)據(jù)集群包含所有數(shù)據(jù)節(jié)點(diǎn)，部署了調(diào)度和監(jiān)控模塊；監(jiān)控集群負(fù)責(zé)收集系統(tǒng)監(jiān)控信息；客戶端是訪問負(fù)載均衡系統(tǒng)的入口。

系統(tǒng)采用接口化的設(shè)計(jì)，通過實(shí)現(xiàn)不同的元數(shù)據(jù)管理接口和均衡決策接口，就可以實(shí)現(xiàn)不同的數(shù)據(jù)分區(qū)策略和負(fù)載均衡策略。利用這個(gè)特性，分別實(shí)現(xiàn)了基于分片和基于虛擬節(jié)點(diǎn)的負(fù)載均衡系統(tǒng)，然后進(jìn)行實(shí)驗(yàn)測(cè)試。

實(shí)驗(yàn)中，采用相同的元數(shù)據(jù)規(guī)模(3個(gè)物理節(jié)點(diǎn)，12個(gè)虛擬節(jié)點(diǎn)或分片)和測(cè)試數(shù)據(jù)，均衡的目標(biāo)值設(shè)置為系統(tǒng)平均負(fù)載的20%以內(nèi)。初始狀態(tài)分片和虛擬節(jié)點(diǎn)的分布情況如表1所示。

通過施加一定規(guī)律的負(fù)載，對(duì)分片級(jí)別的負(fù)載均衡進(jìn)行實(shí)驗(yàn)，當(dāng)負(fù)載不均超過設(shè)定閾值時(shí)，負(fù)載均衡系統(tǒng)進(jìn)行負(fù)載均衡操作。從圖2可以看出，通過對(duì)重載分片(85、425、765)的分裂操作，降低了重載分片的負(fù)載；同時(shí)，通過對(duì)輕載分片(255、595、935)的合并操作，平衡了分片之間差異過大的負(fù)載。

表1 分片與虛擬節(jié)點(diǎn)分布表

圖2 分片級(jí)負(fù)載均衡效果

在分片級(jí)均衡的基礎(chǔ)上，對(duì)節(jié)點(diǎn)級(jí)負(fù)載均衡進(jìn)行實(shí)驗(yàn)，分別對(duì)基于虛擬節(jié)點(diǎn)和基于分片的負(fù)載均衡系統(tǒng)施加負(fù)載壓力。圖3和圖4分別是兩個(gè)系統(tǒng)在負(fù)載均衡前的負(fù)載分布圖。

圖3 均衡前基于虛擬節(jié)點(diǎn)的系統(tǒng)負(fù)載分布圖

圖4 均衡前基于分片的系統(tǒng)負(fù)載分布圖

從圖3可看出，基于虛擬節(jié)點(diǎn)的系統(tǒng)不僅出現(xiàn)了物理節(jié)點(diǎn)之間的負(fù)載不均衡，同時(shí)在虛擬節(jié)點(diǎn)之間也出現(xiàn)了負(fù)載不均。從圖4可看出，基于分片的系統(tǒng)，雖然出現(xiàn)了節(jié)點(diǎn)之間的負(fù)載不均，但得益于節(jié)點(diǎn)內(nèi)部分片間的負(fù)載均衡策略，分片之間負(fù)載分布較為均衡。

經(jīng)過一段時(shí)間的負(fù)載均衡調(diào)度，兩個(gè)系統(tǒng)中各個(gè)物理節(jié)點(diǎn)的負(fù)載狀況如圖5所示。

圖5 均衡后節(jié)點(diǎn)負(fù)載分布圖

從負(fù)載均衡的效果來看，基于虛擬節(jié)點(diǎn)的系統(tǒng)和基于分片的系統(tǒng)都能夠通過一系列的調(diào)度操作對(duì)負(fù)載不均衡的節(jié)點(diǎn)進(jìn)行有效的負(fù)載均衡，達(dá)到將節(jié)點(diǎn)之間的負(fù)載控制在平均負(fù)載的20%以內(nèi)的目標(biāo)。但基于分片的系統(tǒng)在數(shù)據(jù)遷移量和均衡效果上要略優(yōu)于基于虛擬節(jié)點(diǎn)的系統(tǒng)，遷移量上降低了約30%左右，且節(jié)點(diǎn)之間的負(fù)載也更加均衡。

對(duì)以上實(shí)驗(yàn)結(jié)果進(jìn)行分析，基于分片的系統(tǒng)，在負(fù)載均衡過程中采用了兩級(jí)均衡策略，其中分片級(jí)的負(fù)載均衡利用機(jī)器空閑資源在物理節(jié)點(diǎn)內(nèi)部進(jìn)行負(fù)載調(diào)度，使負(fù)載分布均衡。相比之下，基于虛擬節(jié)點(diǎn)的系統(tǒng)，在采用相同的元數(shù)據(jù)復(fù)雜度(虛擬節(jié)點(diǎn)數(shù)與分片數(shù)相同)的情況下，虛擬節(jié)點(diǎn)之間負(fù)載不均，導(dǎo)致在均衡決策時(shí)，遷移負(fù)載的粒度較大，在多數(shù)場(chǎng)景下遷移的數(shù)據(jù)量要高于基于分片的系統(tǒng)。

5 結(jié)束語

從一致性哈希出發(fā)，結(jié)合動(dòng)態(tài)負(fù)載均衡技術(shù)，設(shè)計(jì)了一個(gè)基于分片的一致性哈希動(dòng)態(tài)負(fù)載均衡策略。利用分片進(jìn)一步解耦數(shù)據(jù)和節(jié)點(diǎn)的映射關(guān)系，并在對(duì)分片的監(jiān)控?cái)?shù)據(jù)進(jìn)行動(dòng)態(tài)收集、分析的基礎(chǔ)上，對(duì)分片間和節(jié)點(diǎn)間的負(fù)載進(jìn)行均衡調(diào)度。實(shí)驗(yàn)結(jié)果表明，該策略保留了一致性哈希在系統(tǒng)擴(kuò)展性上的優(yōu)勢(shì)，同時(shí)優(yōu)化了一致性哈希策略負(fù)載均衡的總體效果。借助基于分片的一致性哈希負(fù)載均衡策略，可以有效均衡系統(tǒng)負(fù)載，提高存儲(chǔ)系統(tǒng)的效率。

[1] 黃秋蘭，程耀東，陳 剛.分布式存儲(chǔ)系統(tǒng)的哈希算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(1)：1-4.

[2] 凌 云,周華鋒.面向異構(gòu)集群系統(tǒng)的動(dòng)態(tài)負(fù)載均衡技術(shù)研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(12)：3068-3070.

[3] Rai I,Alanyali M. Uniform weighted round robin scheduling algorithms for input queued switches[C]//IEEE international conference on communications.Helsinki,Finland:IEEE,2001:2028-2032.

[4] Kim J S,Lee D C.Weighted round robin packet scheduler using relative service share[C]//IEEE military communications conference.[s.l.]:IEEE,2001:988-992.

[5] 陳 偉，張玉芳，熊忠陽.動(dòng)態(tài)反饋的異構(gòu)集群負(fù)載均衡算法的實(shí)現(xiàn)[J].重慶大學(xué)學(xué)報(bào):自然科學(xué)版,2010,33(2):73-78.

[6] 朱虹宇，李 挺，閆健恩，等.基于動(dòng)態(tài)負(fù)載均衡的分布式任務(wù)調(diào)度算法研究[J].高技術(shù)通訊，2014,24(12):1261-1269.

[7] 尹向東,楊 杰,屈長(zhǎng)青.云計(jì)算環(huán)境下分布式文件系統(tǒng)的負(fù)載平衡研究[J].計(jì)算機(jī)科學(xué)，2014，41(3):141-144.

[8] 鄧志飛，應(yīng)良佳，王軍威.基于IODA算法MongoDB負(fù)載均衡的改進(jìn)[J].現(xiàn)代電信科技，2013(7):9-13.

[9] Karger D R,Lehman E,Leighton F T,et al.Consistent hashing and random trees:distributed caching protocols for relieving hot spots on the world wide web[C]//ACM symposium on theory of computing.[s.l.]:ACM,1997:654-663.

[10] Sivasubramanian S.Amazon dynamoDB:a seamlessly scalable non-relational database service[C]//ACM SIGMOD international conference on management of data.[s.l.]:[s.n.],2012:729-730.

[11] 張聰萍,尹建偉.分布式文件系統(tǒng)的動(dòng)態(tài)負(fù)載均衡算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2011,32(7):1424-1426.

[12] 趙 見.高性能高可用鍵值存儲(chǔ)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].成都：電子科技大學(xué)，2010.

[13] Schintke F,Reinefeld A,Haridi S,et al.Enhanced paxos commit for transactions on DHTs[C]//IEEE/ACM international conference on cluster,cloud and grid computing.[s.l.]:IEEE,2010:448-454.

[14] 田浪軍，陳衛(wèi)衛(wèi)，陳衛(wèi)東,等.云存儲(chǔ)系統(tǒng)中動(dòng)態(tài)負(fù)載均衡算法研究[J].計(jì)算機(jī)工程,2013,39(10):19-23.

AConsistentHashingLoadBalancingStrategyBasedonFragmentationandItsApplication

SU Yue-ming1,2，LI Chen2，TIAN Li-hua2

(1.School of Software Engineering，Xi’an Jiaotong University，Xi’an 710000，China；2.Baidu Corporation，Beijing 100000，China)

The distributed key-value storage system,which uses consistent hashing for data partitioning and load balancing,has high expansibility.However,the static load balancing strategy in consistent hashing cannot meet the increasingly diverse needs of application.In order to adapt to above needs,a dynamic load balancing strategy is designed based on the consistent hashing and combined with dynamic load balancing.It adopts the fragment decoupled physical nodes instead of traditional virtual nodes and uses the monitoring information of fragments to make decisions for load balancing scheduling from two aspects of fragment level and node level.Experimental results show that it has retained the advantage of consistent hashing strategy in system scalability,while optimizing the overall performance of consistent hashing load balancing.The system load can be effectively balanced and the utilization of the system can be improved.

consistent hashing;fragment;dynamic load balancing;distributed key-value storage

2016-06-14

2016-10-12 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-08-01

國(guó)家自然科學(xué)基金資助項(xiàng)目(61403302)；西安交通大學(xué)科研業(yè)務(wù)基金(XJJ2016029)

蘇躍明(1989-)，男，碩士，研究方向?yàn)榉植际酱鎯?chǔ)系統(tǒng)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1549.006.html

TP39

A

1673-629X(2017)11-0062-04

10.3969/j.issn.1673-629X.2017.11.013