徐凱 李旭健

摘 要：Memcached是一個高性能分布式內(nèi)存對象緩存系統(tǒng)，目前受到各大規(guī)模數(shù)據(jù)中心青睞，但是其高能耗是一個亟待解決的問題。為達(dá)到較好的節(jié)能效果，同時滿足數(shù)據(jù)緩存的高效性，提出一種基于一致性哈希的數(shù)據(jù)緩存系統(tǒng)低能耗副本布局策略——LowPowerCHT，包括分層式副本布局策略和能耗調(diào)度器。LowPowerCHT 將副本分布在互不重合的多個服務(wù)器層中，在分層副本布局中，部分服務(wù)器層維持活動狀態(tài)，其它服務(wù)器層處于關(guān)閉狀態(tài)而不影響數(shù)據(jù)緩存，以此達(dá)到節(jié)能目的。能耗調(diào)度器能夠估算服務(wù)器的負(fù)載率，并根據(jù)負(fù)載的高低變化相應(yīng)開啟或關(guān)閉某些副本層。仿真實驗表明，LowPowerCHT能夠有效節(jié)省能耗，同時維持較好的數(shù)據(jù)緩存性能。

關(guān)鍵詞：Memcached分布式緩存系統(tǒng);一致性哈希表;LowPowerCHT;副本布局

DOI：10. 11907/rjdk. 182703

中圖分類號：TP301文獻(xiàn)標(biāo)識碼：A文章編號：1672-7800（2019）003-0039-04

0 引言

Memcached分布式緩存系統(tǒng)高能耗是一個重要關(guān)注點，高能耗帶來的是高額電費支出。此外，隨著緩存數(shù)據(jù)規(guī)模急劇擴(kuò)大，緩存系統(tǒng)的數(shù)據(jù)緩存量也愈發(fā)龐大。因此，解決服務(wù)器功耗問題已成為當(dāng)務(wù)之急。

有關(guān)數(shù)據(jù)中心能量管理的文獻(xiàn)表明，數(shù)據(jù)中心的大多數(shù)工作負(fù)載采用周期I/O負(fù)載模式，具有較大的峰谷比[1-2]。 普通分布式數(shù)據(jù)緩存系統(tǒng)中，在輕負(fù)載期間關(guān)閉存儲設(shè)備或服務(wù)器以降低功耗已有大量研究，說明該方式具有顯著的節(jié)能潛力[3]。另外一種方法是利用分布式存儲系統(tǒng)中副本的固有冗余[4]。該方法維護(hù)可用于訪問的主副本，并關(guān)閉承載冗余副本的服務(wù)器，以提供較高的節(jié)能水平[5]。然而，分布式緩存系統(tǒng)通常使用一致性哈希表將數(shù)據(jù)分發(fā)給緩存服務(wù)器，因為一致性哈希可以適應(yīng)變化中的服務(wù)器集群，并且具有最小中斷[6]。

以上關(guān)于服務(wù)器節(jié)能的方法均不能滿足分布式緩存系統(tǒng)的工作特點。因此，本文提出一種基于一致性哈希的數(shù)據(jù)緩存系統(tǒng)低能耗副本布局策略，在滿足數(shù)據(jù)緩存需求的同時實現(xiàn)功耗節(jié)省。使用多層放置副本，將副本分配給一致哈希環(huán)節(jié)中的非重疊層，通過維護(hù)部分服務(wù)器的層級，便可在不破壞數(shù)據(jù)緩存的情況下關(guān)閉剩余服務(wù)器層，而能耗調(diào)度器可以提供分布式緩存系統(tǒng)的功耗比例。因此，性能可以功耗成比例的方式放大。測試結(jié)果表明，LowPowerCHT在保持良好的數(shù)據(jù)緩存性能同時，可顯著節(jié)省服務(wù)器集群能耗。

1 LowPowerCHT概述

1.1 一致性哈希下傳統(tǒng)副本策略

目前鍵值存儲系統(tǒng)，如Dynamo[6]、Chord[7]、Cassandra[8]、Voldemort[9]和Sheepdog[10]經(jīng)常使用一致性哈希表將數(shù)據(jù)對象分配給節(jié)點，并將節(jié)點與它們的鍵值映射到哈希環(huán)上。然后，從隨機(jī)映射到環(huán)上某點的順時針出發(fā)，分配給其遇到的第一個節(jié)點。如圖1（a）所示，對象β被映射到順時針方向中遇到的第一個節(jié)點A。

為了實現(xiàn)高可用性，鍵值存儲系統(tǒng)在不同節(jié)點上復(fù)制數(shù)據(jù)。如圖1（a）所示，對象β在環(huán)中的3個后繼節(jié)點A、B和C上被復(fù)制。并且，為了實現(xiàn)負(fù)載平衡，一致性哈希算法分配了多個虛擬節(jié)點到每個物理節(jié)點上。圖1（b）為每個物理節(jié)點的多個虛擬節(jié)點示意圖。通過跳過后續(xù)位置在不同節(jié)點上復(fù)制數(shù)據(jù)的方法，確保數(shù)據(jù)的每個副本存儲在不同物理節(jié)點上。因為虛擬節(jié)點由一致性哈希函數(shù)按偽隨機(jī)順序排列，所以每個數(shù)據(jù)的副本隨機(jī)分布在哈希環(huán)上。

1.2 一致性哈希下多層副本策略

1.2.1 分層策略

為了在分布式緩存系統(tǒng)的一致性哈希下實現(xiàn)能耗均衡目標(biāo)，多層副本策略首先將服務(wù)器分配給非重疊層，每層只包含每個數(shù)據(jù)的一個副本。因此，多層布局允許[（R-t）NR]臺服務(wù)器斷電，同時保持每個數(shù)據(jù)的[t]個副本可用，其中[N]是節(jié)點總數(shù)，[R]是副本級別參數(shù)。通過關(guān)閉不同數(shù)量的層，數(shù)據(jù)緩存系統(tǒng)可以切換到不同電源模式以維持不同工作負(fù)載水平。

圖2所示為3個功耗模式和3個副本級別為3的層。每個層包含服務(wù)器的子集，在每層中，副本是唯一的，表明每個數(shù)據(jù)的副本不存儲在同一層中。當(dāng)系統(tǒng)切換到功耗模式1時，前兩層（層0、層1）被斷電。在功耗模式1（最低功耗模式）中，當(dāng)仍有一層（層2）可用時其它兩層被斷電，顯然，最低功耗模式提供最高的能量節(jié)省。當(dāng)系統(tǒng)從功耗模式1切換到功耗模式2時，層1中的服務(wù)器被開啟。在這種情況下，功耗模式3是具有最高功耗的模式。

1.2.2 副本分配

每個數(shù)據(jù)的副本被分配給不同層中的第一個服務(wù)器，以確保每個層僅包含每個數(shù)據(jù)的1個副本。圖3所示為一致性哈希下多層副本，多層一致性哈希副本策略將每個數(shù)據(jù)的副本分配給其在環(huán)上不同層次的第一個虛擬節(jié)點。對象β的第一副本n1與虛擬節(jié)點A1相關(guān)聯(lián)，虛擬節(jié)點A1是其在層0中的第一個服務(wù)器，并映射到服務(wù)器A;第二副本n2與層1中的第一個虛擬節(jié)點B1相關(guān)聯(lián)，并映射到服務(wù)器B;此外，第三副本n3與層2中的第一個虛擬節(jié)點C1相關(guān)聯(lián)，并映射到服務(wù)器C。

在這種情況下，每個層只包含每個數(shù)據(jù)的1個副本。多層一致性哈希副本策略不僅在不影響數(shù)據(jù)緩存的前提下提供了功耗均衡性策略，而且由于它基于一致性哈希，所以還保持了負(fù)載平衡、容錯和可伸縮性等優(yōu)點。

表1顯示了數(shù)據(jù)β的副本在不同3層的分配情況。β有3個副本：n1、n2和n3。表中用“接收者”表示某層中的第一個接收者，n1被分配給第0層中的接收者1，n2、n3被分配給第1層和第2層中的接收者1。

1.3 功耗模式調(diào)度器

服務(wù)器需要幾秒鐘才能退出待機(jī)，而LowPowerCHT以小時為單位切換電源模式[11]。在管理器上運行的功耗模式調(diào)度器周期性地匯總來自本地服務(wù)器與所有其它遠(yuǎn)程服務(wù)器的負(fù)載測量值，并基于系統(tǒng)負(fù)載計算下一小時的電源模式。

1.3.1 功耗模式計算

為了選擇具有足夠活躍度的服務(wù)器維持給定負(fù)載的功耗模式，本文定義了3個度量標(biāo)準(zhǔn)：節(jié)點度量值、層次度量值和負(fù)載度量值。節(jié)點度量值和層次度量值是通過使用隨機(jī)訪問I/O流在Mb/s中測量的，負(fù)載度量值是通過使用對所有服務(wù)器進(jìn)行聚合讀寫定義的，寫入速率由R因子加權(quán)，因為寫入被復(fù)制R次，因此可以服務(wù)器為單位計算負(fù)載[11]。而本文方法的功耗模式調(diào)度器以層為單位進(jìn)行切換，所以選擇以層為單位而不是以服務(wù)器為單位計算負(fù)載。

在每個服務(wù)器上以1s間隔測量負(fù)載進(jìn)行追蹤，并針對每小時進(jìn)行聚合。首先，調(diào)度器使用現(xiàn)有ARMAX模型的預(yù)測器估算下一小時的負(fù)載[Lpredict][12]。然后，通過確定下一小時的預(yù)測負(fù)載是否超過p層負(fù)載，計算下一小時的功耗模式P。最后，關(guān)閉其它層，選擇包含P層的功耗模式P以維持當(dāng)前負(fù)載。功耗模式P：

其中，[Ltier]表示層次度量，它是一層服務(wù)器的性能;[P]表示選擇的功耗模式，它與系統(tǒng)負(fù)載成比例。在這種情況下，功耗模式調(diào)度器與多層副本策略協(xié)作提供功耗比例，能夠有效選擇適當(dāng)?shù)墓哪Ｊ?，從而達(dá)到節(jié)省能耗的目的。

2 仿真實驗

通過使用追蹤驅(qū)動預(yù)測以評估LowPowerCHT和12個企業(yè)數(shù)據(jù)中心的工作負(fù)載[13]。評估中使用的12條追蹤數(shù)據(jù)是在塊級別上獲取的，并且是從Microsoft Cambridge服務(wù)器收集的[14]。12個工作負(fù)載中的每一個均由7d數(shù)據(jù)組成。表2所示為追蹤參數(shù)。

2.1 實驗裝置

實驗運行在配置有15個服務(wù)器的基于LINUX的緩存集群上，每個服務(wù)器都配備了2.13GHz的Intel Xeon CPU （E5506）和16GB存儲器。所有服務(wù)器都安裝了FEDORA 14、Linux 2.635.64-55.FC14x86-內(nèi)核、Ext4文件系統(tǒng)。每個服務(wù)器配備一個磁盤（西部數(shù)據(jù)RE4 ITB），每個磁盤提供1 TB存儲空間。此外，所使用的哈希函數(shù)是FNV-1散列函數(shù)，Voldemort和Sheepdog都使用該函數(shù)[15]。初始情況下，Sheepdog存儲集群被格式化為使用默認(rèn)的復(fù)制因子3。

仿真實驗測試了負(fù)載預(yù)測準(zhǔn)確性、能耗模式調(diào)度器可靠性以及LowPowerCHT與Sheepdog的節(jié)電效果。

2.2 負(fù)載預(yù)測準(zhǔn)確性

應(yīng)用ARAMX模型預(yù)測工作量[16]。圖4所示為12個工作負(fù)載中使用的負(fù)載預(yù)測器準(zhǔn)確性。

在大約90%的時間內(nèi)，預(yù)測誤差小于1，而在70%的時間內(nèi)，預(yù)測誤差小于0.3。最大預(yù)測精度為prxy，90%的prxy誤差小于0.15。最小預(yù)測精度為wdev，70%的wdev誤差小于0.3。圖5所示為功率模式調(diào)度，可以觀察到，在90%的時間內(nèi)，功率模式與工作負(fù)載相匹配。因此，預(yù)測大部分時間是正確的。

2.3 能耗模式調(diào)度器

圖5顯示了每小時負(fù)載度量以及能耗模式調(diào)度器為每小時緩存usr數(shù)據(jù)所選擇的電源模式，使用的負(fù)載度量為每小時工作負(fù)載所需服務(wù)器數(shù)量，電源模式為每小時工作負(fù)載的層級數(shù)。

由實驗結(jié)果可知：第一，在90%的時間內(nèi)，功率模式是正確的，選擇的活動層數(shù)與每小時工作量相匹配;第二，15臺服務(wù)器足以滿足性能要求，只有幾個小時的負(fù)載在峰值附近[17]。例如，60-64小時期間的工作量即使在所有層都被供電時也無法維持。

2.4 LowPowerCHT與Sheepdog節(jié)電效果對比

實驗中使用的服務(wù)器是均勻的，并且緩存集群總功耗與活動服務(wù)器數(shù)量幾乎成正比[18]。因此，基于活躍狀態(tài)服務(wù)器的數(shù)目計算功耗：

圖6顯示了LowPowerCHT與Sheepdog的功耗。如圖所示，LowPowerCHT比Sheepdog消耗的功率低很多。對于不同工作負(fù)載，Sheepdog功耗相同，并且打開的活動服務(wù)器平均數(shù)量是15，這是因為Sheepdog不使用電源管理策略[19]。

3 結(jié)語

本文提出了基于一致性哈希的數(shù)據(jù)緩存系統(tǒng)低能耗副本布局策略LowPowerCHT。在分層副本布局中，部分服務(wù)器層維持活動狀態(tài)，其它服務(wù)器層處于關(guān)閉狀態(tài)而不影響數(shù)據(jù)緩存，以此達(dá)到節(jié)能目的。能耗調(diào)度器能夠估算服務(wù)器的負(fù)載率，并根據(jù)負(fù)載的高低變化相應(yīng)開啟或關(guān)閉某些副本層。與廣泛使用的傳統(tǒng)方案相比，本文策略在保持整個系統(tǒng)可靠性的同時，能夠顯著地節(jié)省功耗[20]。

參考文獻(xiàn)：

[1] LE H H， HIKIDA S， YOKOTA H. An efficient gear-shifting power-proportional distributed file system[C]. International Conference on Database & Expert Systems Applications， 2015：153-161.

[2] WESTERMEYER J，YOON G，THURAS P，et al. Pharmacotherapy in methadone maintenance：clinical utility of peak-trough blood levels[J]. Addictive Disorders & Their Treatment， 2016， 15（4）：157-164.

[3] 宋馳. 基于異構(gòu)存儲服務(wù)器的節(jié)能調(diào)度機(jī)制的研究[D]. 武漢：華中科技大學(xué)，2015.

[4] JABER G，KACIMI R，MAMMERI Z. Exploiting redundancy for energy-efficiency in wireless sensor networks[C]. Wireless and Mobile NETWORKING Conference，2016：180-186.

[5] MEMON A J， SHAIKH M M. Confidence bounds for energy conservation in electric motors： an economical solution using statistical techniques[J]. Energy，2016， 109：592-601.

[6] 蘇躍明，李晨，田麗華. 基于分片一致性哈希負(fù)載均衡策略與應(yīng)用[J]. 計算機(jī)技術(shù)與發(fā)展，2017（11）：62-65.

[7] KORZENIOWSKI F，WIDMER G. Automatic chord recognition with higher-order harmonic language modelling[C]. European Signal Processing Conference，2018：1-5.

[8] 呂顯赫. 基于混合緩存架構(gòu)的Cassandra讀性能優(yōu)化[D]. 濟(jì)南：山東大學(xué)，2015.

[9] NEVES R，BERNARDINO J. Performance and scalability of voldemort NoSQL[C]. Information Systems and Technologies， 2015：1-6.

[10] STORTEIG H S，STEINHEIM G，F(xiàn)JERDINGBY O H， et al. Genetic analyses of herding traits in the Border Collie using sheepdog trial data[J]. Journal of Animal Breeding and Genetics，2016，134（2）：1-8.

[11] 王芳. 分布式系統(tǒng)中節(jié)能的數(shù)據(jù)擺放和任務(wù)調(diào)度算法的研究[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，2014.

[12] DU G W，ZHOU L H，F(xiàn)ANG Y，et al. Time series clustering via NMF in networks[C]. 2018 IEEE 16th International Conference on Software Engineering Research，Management and Applications（SERA）， 2018：87-92.

[13] 崔黎黎，王曉薇，吳鵬，等. 不確定非線性系統(tǒng)的事件驅(qū)動魯棒跟蹤控制[J]. 沈陽師范大學(xué)學(xué)報：自然科學(xué)版，2018，36（3）：237-249.

[14] JEONG G M， TRUONG P H， LEE T Y， et al. Course design for internet of things using lab of things of Microsoft research[C]. Frontiers in Education Conference， 2016：1-6.

[15] SAMUELSON P. Cisco systems， INC. v. Arista Networks， INC. brief amicus curiae of copyright law professor Pamela Samuelson[J]. Social Science Electronic Publishing， 2018，16（2）：658-680.

[16] 秦天龍. 方程誤差模型基于最新估計的加權(quán)新息最小二乘辨識[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，2015.

[17] 李楊. 一種大負(fù)載峰值電流模DC-DC變換器的設(shè)計[J]. 電子科技，2016，29（7）：128-131.

[18] WANG Y， CHEN S， GOUDARZI H， et al. Resource allocation and consolidation in a multi-core server cluster using a Markov decision process model[C]. International Symposium on Quality Electronic Design， 2013：635-642.

[19] 盧翠榮，鄒靜昭.基于云計算平臺的動態(tài)電源管理策略研究[J].電源技術(shù)，2016， 40（10）：2077-2078.

[20] ALESSIO D， RENFRO W B. The Voldemort of imperial history： rethinking empire and US history[J]. International Studies Perspectives， 2014，17（3）：250-266.

（責(zé)任編輯：何 麗）