林偉偉 賀品嘉 劉波

(1.華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東 廣州 510006;2.華南師范大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510631)

數(shù)字信息的爆炸性增長(zhǎng)催生了海量數(shù)據(jù)存儲(chǔ)的需求，使得存儲(chǔ)系統(tǒng)成為以數(shù)據(jù)為中心的現(xiàn)代計(jì)算機(jī)系統(tǒng)的最重要組成部分之一.日益增大的數(shù)據(jù)存儲(chǔ)規(guī)模與以CPU 為代表的計(jì)算部件和以磁盤(pán)為代表的外存儲(chǔ)部件之間日趨擴(kuò)大的性能差異，使得存儲(chǔ)系統(tǒng)的性能提升和能耗降低成為整個(gè)計(jì)算機(jī)系統(tǒng)性能提升和能耗降低的關(guān)鍵.統(tǒng)計(jì)數(shù)據(jù)顯示，對(duì)于一個(gè)典型的數(shù)據(jù)中心來(lái)說(shuō)，存儲(chǔ)系統(tǒng)的能耗占數(shù)據(jù)中心總能耗的27%［1］，而每年以60%的速度遞增的數(shù)據(jù)存儲(chǔ)需求使得存儲(chǔ)系統(tǒng)能耗占整個(gè)計(jì)算機(jī)系統(tǒng)能耗的比例在未來(lái)數(shù)年內(nèi)持續(xù)增加.在當(dāng)今的信息系統(tǒng)能源消耗中，計(jì)算資源消耗與存儲(chǔ)資源消耗排在前兩位.而由于全球數(shù)據(jù)量的指數(shù)級(jí)增長(zhǎng)等原因，存儲(chǔ)資源消耗很有可能在未來(lái)超過(guò)計(jì)算資源消耗，成為消耗最多的信息系統(tǒng)能源.因此，研究如何節(jié)省分布式集群系統(tǒng)中的存儲(chǔ)能源消耗乃是重中之重的問(wèn)題.

在云對(duì)外提供的服務(wù)中，云存儲(chǔ)服務(wù)［2-4］正受到越來(lái)越多研究人員的關(guān)注.綠色計(jì)算已成為最受關(guān)注的研究熱點(diǎn)之一，尤其是隨著云計(jì)算［5］、物聯(lián)網(wǎng)和移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展以及數(shù)據(jù)中心的大量新建，能耗問(wèn)題越來(lái)越嚴(yán)重.云存儲(chǔ)子系統(tǒng)的能耗占據(jù)了計(jì)算機(jī)系統(tǒng)總能耗的較大部分.因此，有效降低云存儲(chǔ)系統(tǒng)的能耗是降低云數(shù)據(jù)中心總成本的主要手段之一.

利用冗余是一種節(jié)約能源的方法，如訪問(wèn)轉(zhuǎn)移(DIV)［6］的方法就使用了副本，這種方法提倡把所有數(shù)據(jù)項(xiàng)的第1 份拷貝存儲(chǔ)在一部分磁盤(pán)上，以達(dá)到節(jié)約能源的目的，但這種方法可能會(huì)降低系統(tǒng)在全功率模式下的性能.針對(duì)大規(guī)模閑置磁盤(pán)陣列(MAID)系統(tǒng)中的能源節(jié)約問(wèn)題，EERAID［7］、RIMAC［8］和PARAID［9］利用了冗余技術(shù)，但其解決方案僅適用于編碼有限的磁盤(pán)的情況，而不適用于冗余文件廣泛分布在系統(tǒng)中的情況.Greenan 等［10］在一些特殊的糾刪碼類中利用了冗余技術(shù).在低能耗模式中，通?？梢躁P(guān)閉部分存儲(chǔ)節(jié)點(diǎn).有許多方法可以讓磁盤(pán)更長(zhǎng)時(shí)間地處于閑置狀態(tài)，避免它們停止轉(zhuǎn)動(dòng).MAID［11］使用高速緩存磁盤(pán)來(lái)存儲(chǔ)最近被讀到的數(shù)據(jù).流熱點(diǎn)數(shù)據(jù)集中技術(shù)(PDC)［12］把經(jīng)常被讀取的數(shù)據(jù)集中在一起.Hibernator 能根據(jù)數(shù)據(jù)的活躍程度，把幾種速度不同的磁盤(pán)與數(shù)據(jù)不同的集合組合對(duì)應(yīng)起來(lái)，以節(jié)省能源［1］.

能耗已成為當(dāng)前云計(jì)算和云存儲(chǔ)研究最關(guān)注的問(wèn)題之一［13］.文獻(xiàn)［14］對(duì)現(xiàn)有云計(jì)算中的能耗進(jìn)行了綜合分析和討論，指出云計(jì)算中的數(shù)據(jù)傳輸與數(shù)據(jù)處理、數(shù)據(jù)存儲(chǔ)一樣，可能會(huì)消耗大量的能源;并指出用戶在個(gè)人計(jì)算機(jī)上執(zhí)行計(jì)算可能比在云上執(zhí)行計(jì)算消耗更多的能源.王意潔等［15］通過(guò)建立比例模型和兩段模型來(lái)改進(jìn)Hadoop 集群的能耗效率.雷成軍等［16］提出了集群自主管理的架構(gòu)，通過(guò)傳感器將數(shù)據(jù)整合到計(jì)算進(jìn)程，并通過(guò)這些數(shù)據(jù)對(duì)云計(jì)算集群的物理現(xiàn)象進(jìn)行建模，最終在權(quán)衡系統(tǒng)性能和工作負(fù)載的基礎(chǔ)上降低集群的整體能耗.

為減少云存儲(chǔ)系統(tǒng)的能耗，文中考慮在云存儲(chǔ)系統(tǒng)利用率較低時(shí)(例如晚上或周末)關(guān)閉部分存儲(chǔ)節(jié)點(diǎn).然而，關(guān)閉部分節(jié)點(diǎn)的前提是保證集群中的所有數(shù)據(jù)項(xiàng)可用.在云存儲(chǔ)系統(tǒng)(如Hadoop 的分布式文件系統(tǒng)HDFS)中，每個(gè)數(shù)據(jù)項(xiàng)均有r 個(gè)副本，因此，在云存儲(chǔ)系統(tǒng)使用率較低時(shí)，可以通過(guò)關(guān)閉部分存儲(chǔ)節(jié)點(diǎn)來(lái)減少系統(tǒng)能耗，但要求這個(gè)關(guān)閉節(jié)點(diǎn)集合中不能包含某個(gè)數(shù)據(jù)項(xiàng)的所有副本，否則會(huì)導(dǎo)致這個(gè)數(shù)據(jù)項(xiàng)失效.為此，針對(duì)如何選擇云存儲(chǔ)系統(tǒng)中可以關(guān)閉的節(jié)點(diǎn)集合問(wèn)題，文中設(shè)計(jì)實(shí)現(xiàn)了基于輔助節(jié)點(diǎn)的貪心算法，并針對(duì)異構(gòu)云存儲(chǔ)系統(tǒng)的能耗優(yōu)化問(wèn)題，提出了改進(jìn)的貪心算法，以降低云存儲(chǔ)系統(tǒng)的能耗.

1 云存儲(chǔ)系統(tǒng)的能耗優(yōu)化數(shù)據(jù)管理問(wèn)題描述

云存儲(chǔ)系統(tǒng)通過(guò)分布式存儲(chǔ)來(lái)實(shí)現(xiàn)其可擴(kuò)展性，通過(guò)冗余存儲(chǔ)來(lái)確保數(shù)據(jù)的可靠性.為方便描述，設(shè)r 為云存儲(chǔ)系統(tǒng)的重復(fù)因子(即云存儲(chǔ)系統(tǒng)中每個(gè)數(shù)據(jù)項(xiàng)冗余存儲(chǔ)的份數(shù)或副本的個(gè)數(shù))，M 為云存儲(chǔ)系統(tǒng)中的存儲(chǔ)節(jié)點(diǎn)數(shù)，N 為系統(tǒng)中數(shù)據(jù)項(xiàng)的個(gè)數(shù)，p 為關(guān)閉節(jié)點(diǎn)集合中的節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比例.文中按照使用率高低將云存儲(chǔ)系統(tǒng)分為全能耗模式(如白天)和低能耗模式(如夜晚)兩種.為節(jié)約能源，文中考慮在系統(tǒng)的使用率降低時(shí)關(guān)閉一部分存儲(chǔ)節(jié)點(diǎn).設(shè)E 為能源節(jié)約率，即低能耗模式下節(jié)省的能耗占全能耗模式下能耗的百分比，該值越大表示算法的節(jié)能效果越好.

由于通過(guò)關(guān)閉部分云存儲(chǔ)節(jié)點(diǎn)實(shí)現(xiàn)能耗優(yōu)化的方法要保證整個(gè)系統(tǒng)的可用性(每個(gè)文件或數(shù)據(jù)可訪問(wèn)性)，故要保證每個(gè)數(shù)據(jù)項(xiàng)至少有一個(gè)副本依然可用，即每個(gè)數(shù)據(jù)項(xiàng)至少有一個(gè)副本所在的存儲(chǔ)節(jié)點(diǎn)未被關(guān)閉.一種簡(jiǎn)單的方法是修改數(shù)據(jù)分配函數(shù)，以達(dá)到最佳的節(jié)能效果，如把所有數(shù)據(jù)項(xiàng)的第一個(gè)副本存放在選定的存儲(chǔ)節(jié)點(diǎn)集合中，其余副本隨機(jī)分配在剩余的節(jié)點(diǎn)上;在低能耗模式下，僅開(kāi)啟存有所有數(shù)據(jù)項(xiàng)第1 個(gè)副本的存儲(chǔ)節(jié)點(diǎn)集合.但系統(tǒng)在全能耗模式下(白天)時(shí)，此方法很可能會(huì)降低數(shù)據(jù)的訪問(wèn)性能.因此，在不改動(dòng)分配函數(shù)的前提下，應(yīng)選出一個(gè)關(guān)閉節(jié)點(diǎn)集合.

在云存儲(chǔ)系統(tǒng)中尋找可關(guān)閉節(jié)點(diǎn)的問(wèn)題可抽象為一個(gè)圖的覆蓋問(wèn)題，其評(píng)判的標(biāo)準(zhǔn)是剩余的節(jié)點(diǎn)要覆蓋盡可能多的數(shù)據(jù)項(xiàng)(至少保存該數(shù)據(jù)項(xiàng)的一個(gè)拷貝).此覆蓋問(wèn)題的輸入是一個(gè)二部圖［17］，圖中左邊有M 個(gè)節(jié)點(diǎn)(代表系統(tǒng)中的存儲(chǔ)節(jié)點(diǎn))，右邊有N 個(gè)節(jié)點(diǎn)(代表系統(tǒng)中的數(shù)據(jù)項(xiàng))，右邊的每個(gè)數(shù)據(jù)項(xiàng)(節(jié)點(diǎn))與左邊的存儲(chǔ)節(jié)點(diǎn)有r 條相鄰的邊(代表該數(shù)據(jù)項(xiàng)在存儲(chǔ)節(jié)點(diǎn)上有r 個(gè)拷貝).對(duì)一個(gè)給定的比例p(0 ＜p ＜100%)，尋找一個(gè)節(jié)點(diǎn)數(shù)為Mp的節(jié)點(diǎn)子集，使剩余節(jié)點(diǎn)覆蓋的數(shù)據(jù)項(xiàng)數(shù)最大化.若一個(gè)數(shù)據(jù)項(xiàng)節(jié)點(diǎn)與存儲(chǔ)節(jié)點(diǎn)有相連邊，則稱此數(shù)據(jù)項(xiàng)被覆蓋了.文中的優(yōu)化目標(biāo)是在給定一個(gè)圖和最大化關(guān)閉存儲(chǔ)節(jié)點(diǎn)比例p 的情況下，最小化未被覆蓋到數(shù)據(jù)項(xiàng)的節(jié)點(diǎn)數(shù).

若一個(gè)數(shù)據(jù)放置方案覆蓋了所有的數(shù)據(jù)項(xiàng)，則稱此方案實(shí)現(xiàn)了對(duì)數(shù)據(jù)的全覆蓋.文中主要討論尋找圖的最佳覆蓋(即超圖中的點(diǎn)覆蓋)問(wèn)題，這是一個(gè)計(jì)算復(fù)雜而且困難的問(wèn)題.為此，考慮一個(gè)有M頂點(diǎn)(每個(gè)頂點(diǎn)代表系統(tǒng)中的一個(gè)節(jié)點(diǎn))的超圖，共有N 條超邊，每條超邊連接d 個(gè)頂點(diǎn)(超邊代表數(shù)據(jù)項(xiàng)，超邊連接著所有存放該數(shù)據(jù)項(xiàng)的節(jié)點(diǎn)).解決此覆蓋問(wèn)題等價(jià)于尋找一個(gè)節(jié)點(diǎn)的子集，使該超圖在其子集中節(jié)點(diǎn)數(shù)盡量小的情況下相連的邊盡可能多.當(dāng)重復(fù)度為2 時(shí)，此覆蓋問(wèn)題可轉(zhuǎn)化為經(jīng)典的點(diǎn)覆蓋問(wèn)題(Karp［18］的21 個(gè)原始非確定性的多項(xiàng)式問(wèn)題(NP)之一).因?yàn)樵诜植际酱鎯?chǔ)系統(tǒng)中，數(shù)據(jù)項(xiàng)經(jīng)常發(fā)生改變，在全能耗模式下使用時(shí)，經(jīng)常有數(shù)據(jù)項(xiàng)的增加與刪除操作，所以針對(duì)某個(gè)特定數(shù)據(jù)項(xiàng)集的分布情況求出的最優(yōu)解，并不會(huì)一直適用.而當(dāng)數(shù)據(jù)項(xiàng)的分布情況發(fā)生改變時(shí)，原先的最優(yōu)解往往也會(huì)變成一個(gè)較優(yōu)解，故求最優(yōu)解沒(méi)有實(shí)際意義.加上求出最優(yōu)解需要較長(zhǎng)的計(jì)算時(shí)間，較優(yōu)解足以達(dá)到節(jié)約能耗的目的，故文中采用啟發(fā)式算法來(lái)尋求一些比較好的覆蓋.

2 算法設(shè)計(jì)

2.1 一般貪心算法

一般貪心算法(算法1)的核心思想是在每次迭代過(guò)程中取局部最優(yōu)解，以使最后結(jié)果為全局較優(yōu)解.能耗優(yōu)化的目標(biāo)是使節(jié)約的能源最大化，即在低能耗模式下關(guān)閉節(jié)點(diǎn)的集合達(dá)到最大值.在集群數(shù)據(jù)項(xiàng)總數(shù)一定的情況下，關(guān)閉節(jié)點(diǎn)上的數(shù)據(jù)項(xiàng)越少，則關(guān)閉節(jié)點(diǎn)的集合越大.因此，可以先根據(jù)節(jié)點(diǎn)上的數(shù)據(jù)項(xiàng)數(shù)對(duì)節(jié)點(diǎn)進(jìn)行排序(從小到大)，再對(duì)排好序的vector(節(jié)點(diǎn)的抽象數(shù)據(jù)結(jié)構(gòu))進(jìn)行迭代.

一般貪心算法的輸入為存儲(chǔ)節(jié)點(diǎn)集合、數(shù)據(jù)項(xiàng)節(jié)點(diǎn)集合、數(shù)據(jù)項(xiàng)的重復(fù)因子和每個(gè)存儲(chǔ)節(jié)點(diǎn)的能耗，輸出為關(guān)閉節(jié)點(diǎn)集合中的存儲(chǔ)節(jié)點(diǎn)數(shù)與使用該算法所節(jié)約的能源量，具體的算法步驟如下:①對(duì)兩個(gè)vector(這兩個(gè)vector 分別抽象存儲(chǔ)節(jié)點(diǎn)集合與數(shù)據(jù)項(xiàng)集合)進(jìn)行初始化;②將每個(gè)數(shù)據(jù)項(xiàng)隨機(jī)分配到該整數(shù)對(duì)應(yīng)的存儲(chǔ)節(jié)點(diǎn)上;③調(diào)用C ++標(biāo)準(zhǔn)模板庫(kù)STL 的sort 函數(shù)，根據(jù)存儲(chǔ)節(jié)點(diǎn)上的數(shù)據(jù)項(xiàng)數(shù)對(duì)存儲(chǔ)節(jié)點(diǎn)進(jìn)行排序(從小到大);④從所存放數(shù)據(jù)項(xiàng)最少的存儲(chǔ)節(jié)點(diǎn)開(kāi)始遍歷，將節(jié)點(diǎn)放入關(guān)閉節(jié)點(diǎn)集合中，直到有一個(gè)數(shù)據(jù)項(xiàng)沒(méi)有一個(gè)副本存放在未關(guān)閉的存儲(chǔ)節(jié)點(diǎn)上為止;⑤輸出關(guān)閉節(jié)點(diǎn)集合，并據(jù)此計(jì)算出系統(tǒng)節(jié)約的能源量.該算法的偽代碼描述如下:

分析最壞情況下貪心算法的復(fù)雜度.對(duì)有N 個(gè)數(shù)據(jù)項(xiàng)(每個(gè)數(shù)據(jù)項(xiàng)有r 個(gè)副本)與M 個(gè)存儲(chǔ)節(jié)點(diǎn)的系統(tǒng)，預(yù)先設(shè)定關(guān)閉節(jié)點(diǎn)集的節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比例為c(以下實(shí)驗(yàn)皆同)，則算法初始化所有存儲(chǔ)節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(M)，初始化所有數(shù)據(jù)項(xiàng)的時(shí)間復(fù)雜度為O(N)，使用隨機(jī)分配函數(shù)對(duì)數(shù)據(jù)項(xiàng)(共有rN 個(gè)數(shù)據(jù)副本)進(jìn)行分配的時(shí)間復(fù)雜度為O(rN)，根據(jù)存儲(chǔ)節(jié)點(diǎn)上的數(shù)據(jù)項(xiàng)數(shù)對(duì)存儲(chǔ)節(jié)點(diǎn)進(jìn)行排序的時(shí)間復(fù)雜度為O(Mlog2M)，最壞情況下遍歷完所有節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(MN).一般來(lái)說(shuō)M＞N，故貪心算法的時(shí)間復(fù)雜度為O(M + N + M +rN + M + Mlog2M + cMN)≈O(M2).

由此算法可獲得可關(guān)閉節(jié)點(diǎn)的集合，但當(dāng)數(shù)據(jù)項(xiàng)不是特別小(如數(shù)據(jù)項(xiàng)數(shù)與節(jié)點(diǎn)數(shù)的比值為10)時(shí)，由此算法求出的可關(guān)閉節(jié)點(diǎn)集合十分小;當(dāng)數(shù)據(jù)項(xiàng)數(shù)與節(jié)點(diǎn)數(shù)的比值較大時(shí)，某數(shù)據(jù)項(xiàng)的所有副本均在被選出的即將關(guān)閉的節(jié)點(diǎn)集合中.因此，單純采用貪心算法求出低能耗模式下可關(guān)閉節(jié)點(diǎn)的集合將十分小.當(dāng)然這與數(shù)據(jù)的重復(fù)度(即每個(gè)數(shù)據(jù)項(xiàng)的副本數(shù)量)有關(guān).為此，文中提出了一種基于輔助節(jié)點(diǎn)的貪心算法.

2.2 基于輔助節(jié)點(diǎn)的貪心算法

在貪心算法的迭代過(guò)程中，若有任一數(shù)據(jù)項(xiàng)的所有副本存放在所選關(guān)閉節(jié)點(diǎn)集合中，則停止迭代，這會(huì)導(dǎo)致迭代過(guò)程較早地停止，因?yàn)橄到y(tǒng)中的數(shù)據(jù)項(xiàng)一般為(或近似為)隨機(jī)分配.為此，文中向系統(tǒng)中添加一定的輔助存儲(chǔ)節(jié)點(diǎn)，即新增專門(mén)用來(lái)存儲(chǔ)在低能耗模式下失效的數(shù)據(jù)項(xiàng)的節(jié)點(diǎn)，以改進(jìn)算法的節(jié)能效果.在物理構(gòu)造與存儲(chǔ)能力上，輔助節(jié)點(diǎn)與系統(tǒng)中其他節(jié)點(diǎn)一樣，區(qū)別在于其在整個(gè)分布式存儲(chǔ)系統(tǒng)中扮演的角色不同.

基于輔助節(jié)點(diǎn)的貪心算法(算法2)的輸入為存儲(chǔ)節(jié)點(diǎn)集合、數(shù)據(jù)項(xiàng)節(jié)點(diǎn)集合、數(shù)據(jù)項(xiàng)的重復(fù)因子、預(yù)先設(shè)定的關(guān)閉節(jié)點(diǎn)集合中的節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比例和每個(gè)存儲(chǔ)節(jié)點(diǎn)所消耗的能源，輸出為所需要的輔助節(jié)點(diǎn)數(shù)與使用該算法所節(jié)約的能源量.該算法的大部分步驟與2.1 節(jié)中的貪心算法類似.在初始化并分配好數(shù)據(jù)項(xiàng)后，采用與2.1 節(jié)相同的方法進(jìn)行排序;然后，從存儲(chǔ)節(jié)點(diǎn)vector 中的第一個(gè)存儲(chǔ)節(jié)點(diǎn)開(kāi)始遍歷，將節(jié)點(diǎn)歸入關(guān)閉節(jié)點(diǎn)集合中，直到關(guān)閉節(jié)點(diǎn)集合中的節(jié)點(diǎn)數(shù)與總節(jié)點(diǎn)數(shù)的比例與預(yù)先設(shè)定值p 相等為止;最后，輸出關(guān)閉節(jié)點(diǎn)集合、所需要的輔助節(jié)點(diǎn)數(shù)與系統(tǒng)所節(jié)約的能源量.該算法的偽代碼描述如下:

{輸入:nodevector，datavector，r，p，energy

輸出:Number of auxiliary storage nodes and save_energy

分析最壞情況下基于輔助節(jié)點(diǎn)的貪心算法的復(fù)雜度.此算法與2.1 中的貪心算法類似.排序后，需要遍歷cM 個(gè)存儲(chǔ)節(jié)點(diǎn)上的所有數(shù)據(jù)項(xiàng)，故時(shí)間復(fù)雜度為O(cMN).一般來(lái)說(shuō)，M＞N，故此算法的時(shí)間復(fù)雜度為O(n2).

2.3 面向異構(gòu)系統(tǒng)能耗優(yōu)化的改進(jìn)貪心算法

前面提出的貪心算法和基于輔助節(jié)點(diǎn)的貪心算法主要適用于同構(gòu)系統(tǒng)(即由同一種節(jié)點(diǎn)構(gòu)成，其存儲(chǔ)容量、計(jì)算能力、能耗等均相同).但現(xiàn)實(shí)中常有異構(gòu)的分布式存儲(chǔ)系統(tǒng).為優(yōu)化異構(gòu)云存儲(chǔ)系統(tǒng)的能耗，文中提出了面向異構(gòu)云存儲(chǔ)系統(tǒng)能耗優(yōu)化的改進(jìn)貪心算法(算法3)，用于計(jì)算關(guān)閉節(jié)點(diǎn)集合和節(jié)省的能耗.為簡(jiǎn)化問(wèn)題，文中只討論各節(jié)點(diǎn)能耗不同的情況，即假設(shè)集群中的節(jié)點(diǎn)有幾種不同的能耗.這樣，在考慮云存儲(chǔ)數(shù)據(jù)管理的能耗優(yōu)化問(wèn)題時(shí)，就不能僅僅考慮存儲(chǔ)節(jié)點(diǎn)上的數(shù)據(jù)項(xiàng)數(shù)，還應(yīng)考慮該節(jié)點(diǎn)的能耗.若只考慮存儲(chǔ)節(jié)點(diǎn)上的數(shù)據(jù)項(xiàng)數(shù)，則可能出現(xiàn)關(guān)閉節(jié)點(diǎn)上的數(shù)據(jù)項(xiàng)數(shù)雖少但其耗能是低的情況，從而造成節(jié)省的能耗并不高的結(jié)果.

在同構(gòu)系統(tǒng)中，能耗的計(jì)算僅需考慮使用貪心算法存儲(chǔ)數(shù)據(jù)項(xiàng)所需要的存儲(chǔ)節(jié)點(diǎn)數(shù).而在異構(gòu)系統(tǒng)中，還需要考慮不同存儲(chǔ)節(jié)點(diǎn)的能耗.為此，文中引入計(jì)算能耗因子的函數(shù)f(x，y)=ax－ by，其中x為節(jié)點(diǎn)上的數(shù)據(jù)項(xiàng)數(shù)，y 為節(jié)點(diǎn)的能耗(初始化時(shí)賦予).通過(guò)調(diào)整a 和b 值可使系統(tǒng)的能耗趨向最少.通過(guò)反復(fù)實(shí)驗(yàn)最終確定a 和b 的取值分別為1.0 和30.0.

面向異構(gòu)云存儲(chǔ)系統(tǒng)能耗優(yōu)化的改進(jìn)貪心算法的輸入為存儲(chǔ)節(jié)點(diǎn)集合、數(shù)據(jù)項(xiàng)節(jié)點(diǎn)集合、數(shù)據(jù)項(xiàng)的重復(fù)因子、預(yù)先設(shè)定的關(guān)閉節(jié)點(diǎn)集合中的節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比例和兩個(gè)用于計(jì)算rank 值的參數(shù)，輸出為所需要的輔助節(jié)點(diǎn)數(shù)與使用該算法所節(jié)約的能源量.該算法的具體步驟如下:①初始化兩個(gè)vector(用于抽象存儲(chǔ)節(jié)點(diǎn)集合與數(shù)據(jù)項(xiàng)集合);②遍歷每個(gè)數(shù)據(jù)項(xiàng)節(jié)點(diǎn)，并將該數(shù)據(jù)項(xiàng)分配到隨機(jī)的某個(gè)存儲(chǔ)節(jié)點(diǎn)上;③調(diào)用C ++標(biāo)準(zhǔn)模板庫(kù)STL 的sort 函數(shù)，根據(jù)存儲(chǔ)節(jié)點(diǎn)的rank 值(由存儲(chǔ)節(jié)點(diǎn)的能耗與存儲(chǔ)節(jié)點(diǎn)上的數(shù)據(jù)項(xiàng)數(shù)共同決定)對(duì)存儲(chǔ)節(jié)點(diǎn)進(jìn)行排序;④從rank 值最小的存儲(chǔ)節(jié)點(diǎn)開(kāi)始遍歷，將節(jié)點(diǎn)歸入關(guān)閉節(jié)點(diǎn)集合中，直至關(guān)閉節(jié)點(diǎn)集合中的節(jié)點(diǎn)數(shù)與總節(jié)點(diǎn)數(shù)的比例與預(yù)先設(shè)定值相等為止;⑤輸出關(guān)閉節(jié)點(diǎn)集合、所需要的輔助節(jié)點(diǎn)數(shù)與系統(tǒng)所節(jié)約的能源量.算法的偽代碼描述如下:

分析最壞情況下算法的復(fù)雜度.本算法與基于輔助節(jié)點(diǎn)的貪心算法類似，不同之處在于:①要初始化所有存儲(chǔ)節(jié)點(diǎn)的能耗參數(shù)，其時(shí)間復(fù)雜度為O(M);②數(shù)據(jù)分配完成后，需要計(jì)算出每個(gè)節(jié)點(diǎn)的評(píng)價(jià)值，其時(shí)間復(fù)雜度為O(M).故整個(gè)算法的時(shí)間復(fù)雜度為O(M2).

3 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證文中算法的有效性，在CPU 為3.0 GHz、內(nèi)存為2 GB、硬盤(pán)為120 GB 的個(gè)人計(jì)算機(jī)上進(jìn)行模擬實(shí)驗(yàn).在Visual Studio 2010 環(huán)境下采用C ++開(kāi)發(fā)算法程序，存儲(chǔ)節(jié)點(diǎn)和數(shù)據(jù)項(xiàng)分別采用nodeitem類和dataitem 類來(lái)模擬，nodeitem 類的數(shù)據(jù)成員包含一個(gè)vector 與幾個(gè)保存存儲(chǔ)節(jié)點(diǎn)狀態(tài)的變量.數(shù)據(jù)項(xiàng)與存儲(chǔ)節(jié)點(diǎn)類似，包含一個(gè)定長(zhǎng)的數(shù)組與一些保存數(shù)據(jù)節(jié)點(diǎn)狀態(tài)的變量，其中定長(zhǎng)數(shù)組的長(zhǎng)度由一個(gè)宏變量確定，以方便修改.存儲(chǔ)節(jié)點(diǎn)集合與數(shù)據(jù)項(xiàng)集合皆用數(shù)組來(lái)模擬，實(shí)驗(yàn)中可根據(jù)需要改變集合的大小，以研究算法在不同數(shù)據(jù)項(xiàng)數(shù)下的能耗優(yōu)化效果.實(shí)驗(yàn)中對(duì)每個(gè)數(shù)據(jù)項(xiàng)的每一副本，生成一個(gè)一定范圍內(nèi)(由存儲(chǔ)節(jié)點(diǎn)數(shù)確定)的隨機(jī)數(shù)，并根據(jù)該隨機(jī)數(shù)來(lái)分配數(shù)據(jù)項(xiàng)的副本，將分配信息同時(shí)保存在數(shù)據(jù)項(xiàng)與存儲(chǔ)節(jié)點(diǎn)所對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)中.

由于文中研究的算法是離線的，而且提出的算法主要是計(jì)算低能耗(低功率)模式下的關(guān)閉節(jié)點(diǎn)集合，而低功率模式下系統(tǒng)訪問(wèn)數(shù)據(jù)比較少，基本上不會(huì)影響云存儲(chǔ)系統(tǒng)的性能.因此，文中模擬實(shí)驗(yàn)主要分析算法對(duì)系統(tǒng)能耗的改進(jìn).

實(shí)驗(yàn)1 采用貪心算法進(jìn)行實(shí)驗(yàn)，存儲(chǔ)節(jié)點(diǎn)數(shù)固定為1000，重復(fù)因子r=3，通過(guò)改變數(shù)據(jù)項(xiàng)數(shù)來(lái)考察數(shù)據(jù)項(xiàng)數(shù)與存儲(chǔ)節(jié)點(diǎn)數(shù)的比值k 對(duì)關(guān)閉節(jié)點(diǎn)集合選取(即關(guān)閉節(jié)點(diǎn)數(shù)C)的影響，取10 次實(shí)驗(yàn)結(jié)果的平均值作為最終實(shí)驗(yàn)結(jié)果(以下實(shí)驗(yàn)皆同)，如圖1 所示.

圖1 貪心算法的關(guān)閉節(jié)點(diǎn)數(shù)與數(shù)據(jù)項(xiàng)數(shù)的關(guān)系Fig.1 Relationship between number of close nodes and data items in the greedy algorithm

由圖1 可見(jiàn):在數(shù)據(jù)項(xiàng)數(shù)比較小時(shí)，貪心算法的能耗優(yōu)化效果較好;隨著數(shù)據(jù)項(xiàng)數(shù)的增大，貪心算法的能耗優(yōu)化效果變得越差;在數(shù)據(jù)項(xiàng)數(shù)與存儲(chǔ)節(jié)點(diǎn)數(shù)的比值較大時(shí)，算法求出的可關(guān)閉節(jié)點(diǎn)集合較小.例如，在數(shù)據(jù)項(xiàng)數(shù)與存儲(chǔ)節(jié)點(diǎn)數(shù)的比值為10 時(shí)，所求出的可關(guān)閉節(jié)點(diǎn)集合中只有70 多個(gè)節(jié)點(diǎn)，即只能節(jié)約7%的能源量.

綜合以上討論知道，在使用隨機(jī)分配函數(shù)或一致性哈希函數(shù)的分布式存儲(chǔ)系統(tǒng)中，單純使用貪心算法來(lái)求解可關(guān)閉的節(jié)點(diǎn)集合時(shí)，算法的能耗優(yōu)化效果較差.只有在數(shù)據(jù)項(xiàng)分布十分稀疏(如數(shù)據(jù)項(xiàng)數(shù)與存儲(chǔ)節(jié)點(diǎn)數(shù)的比值為10－1)時(shí)，低能耗模式下節(jié)約的能源量才比較可觀(為78.17%);若數(shù)據(jù)項(xiàng)數(shù)與存儲(chǔ)節(jié)點(diǎn)數(shù)的比值比較大(如為100)，則低能耗模式下節(jié)約的能源量可能不及10%.

貪心算法的能耗優(yōu)化效果較差，其原因在于數(shù)據(jù)項(xiàng)在存儲(chǔ)節(jié)點(diǎn)中是近乎于隨機(jī)分配的，故在選取可關(guān)閉節(jié)點(diǎn)集合時(shí)，很容易把一個(gè)數(shù)據(jù)項(xiàng)的所有副本均包含進(jìn)去，此時(shí)算法會(huì)停止迭代，從而導(dǎo)致算法求出的可關(guān)閉節(jié)點(diǎn)集合很小.

實(shí)驗(yàn)2 假設(shè)每個(gè)輔助節(jié)點(diǎn)可存儲(chǔ)3 000 個(gè)數(shù)據(jù)項(xiàng)，存儲(chǔ)節(jié)點(diǎn)數(shù)固定為1 000，關(guān)閉節(jié)點(diǎn)集合中的節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比例p=60%，重復(fù)因子r=3，通過(guò)改變數(shù)據(jù)項(xiàng)數(shù)來(lái)考察數(shù)據(jù)項(xiàng)數(shù)與存儲(chǔ)節(jié)點(diǎn)數(shù)的比值對(duì)能耗優(yōu)化效果的影響，結(jié)果如表1 所示.

表1 兩種貪心算法的能耗優(yōu)化效果對(duì)比Table 1 Comparison of energy saving results of two greedy algorithms

從表1 可知，在添加了輔助節(jié)點(diǎn)后，系統(tǒng)在低能耗模式下可節(jié)約的能源量大大增加.當(dāng)然，這里尚未考慮添加輔助節(jié)點(diǎn)本身所帶來(lái)的成本.不過(guò)從節(jié)能的角度考慮，適當(dāng)增加少量服務(wù)器應(yīng)該是可以接受的，例如輔助節(jié)點(diǎn)數(shù)為原節(jié)點(diǎn)數(shù)的10%以下時(shí)是可以接受的.在實(shí)驗(yàn)中，當(dāng)重復(fù)因子為3、數(shù)據(jù)項(xiàng)數(shù)為106時(shí)，僅需要添加69 個(gè)輔助節(jié)點(diǎn)(6.9%)便可以使系統(tǒng)在低能耗模式下節(jié)約近60%的能源量，這個(gè)數(shù)值是十分可觀的.

接著，在存儲(chǔ)節(jié)點(diǎn)數(shù)固定為1 000、重復(fù)因子為3、數(shù)據(jù)項(xiàng)數(shù)為106的情況下，通過(guò)設(shè)定不同的p(分別為20%、40%、60%和80%)來(lái)計(jì)算使用基于輔助節(jié)點(diǎn)的貪心算法所需添加的輔助節(jié)點(diǎn)數(shù).實(shí)驗(yàn)結(jié)果顯示:所設(shè)定的關(guān)閉節(jié)點(diǎn)集合越大，所需增加的輔助節(jié)點(diǎn)越多;在p 增大到某一值時(shí)，增加輔助節(jié)點(diǎn)所帶來(lái)的能耗優(yōu)化效果大大減少.在p=80%時(shí)，估計(jì)可節(jié)約的能源量為80%，但由于增加的輔助節(jié)點(diǎn)較多，故實(shí)際節(jié)約的能源量?jī)H為68.55%，且系統(tǒng)關(guān)閉80%的節(jié)點(diǎn)時(shí)需要添加16.7%的輔助節(jié)點(diǎn)，成本太高.因此，若采取添加輔助節(jié)點(diǎn)的方法，則所設(shè)定的關(guān)閉節(jié)點(diǎn)集合的比例不能太大，p=60%時(shí)能取得較好的能耗優(yōu)化效果.

實(shí)驗(yàn)3 設(shè)置存儲(chǔ)節(jié)點(diǎn)數(shù)為90，數(shù)據(jù)項(xiàng)數(shù)為9 ×104，重復(fù)因子為3，將存儲(chǔ)節(jié)點(diǎn)等分為3 份(其節(jié)點(diǎn)集合的能耗參數(shù)分別為2、4 和6，輔助節(jié)點(diǎn)的能耗參數(shù)為4)，每份中的30 個(gè)節(jié)點(diǎn)具有相同的能耗參數(shù)，使用隨機(jī)分配函數(shù)把數(shù)據(jù)分配到90 個(gè)節(jié)點(diǎn)上，通過(guò)設(shè)定不同的p(分別為20%、40%、60% 和80%)并采用面向異構(gòu)系統(tǒng)能耗優(yōu)化的改進(jìn)貪心算法和基于輔助節(jié)點(diǎn)的貪心算法進(jìn)行實(shí)驗(yàn)，所需能耗和添加的輔助節(jié)點(diǎn)數(shù)如表2 所示.其中能耗值是低能耗模式下運(yùn)行節(jié)點(diǎn)的能耗加上輔助節(jié)點(diǎn)的能耗，該能耗值越小，表明算法的能耗優(yōu)化效果越好.

表2 兩種貪心算法所需能耗和添加的輔助節(jié)點(diǎn)數(shù)對(duì)比Table 2 Comparison of required energy and auxiliary nodes of two greedy algorithms

由表2 可知:與使用基于輔助節(jié)點(diǎn)的貪心算法相比，使用面向異構(gòu)系統(tǒng)能耗優(yōu)化的改進(jìn)貪心算法的分布式存儲(chǔ)系統(tǒng)在低能耗模式下所需的能源有所降低，能耗減少最多達(dá)24.69%;兩種算法所需添加的輔助節(jié)點(diǎn)數(shù)十分接近，這說(shuō)明使用這兩種算法時(shí)，為系統(tǒng)添加輔助節(jié)點(diǎn)的成本是相同的.綜合上述實(shí)驗(yàn)結(jié)果可知，面向異構(gòu)系統(tǒng)能耗優(yōu)化的改進(jìn)貪心算法的性能優(yōu)于不考慮異構(gòu)情況的貪心算法.在管理由異構(gòu)節(jié)點(diǎn)組成的分布式存儲(chǔ)系統(tǒng)時(shí)，不但要考慮存儲(chǔ)在節(jié)點(diǎn)上的數(shù)據(jù)項(xiàng)數(shù)，還要考慮節(jié)點(diǎn)本身的能耗.若某節(jié)點(diǎn)的能耗特別大，則優(yōu)先考慮關(guān)閉該節(jié)點(diǎn).

4 結(jié)語(yǔ)

為節(jié)省云存儲(chǔ)系統(tǒng)的能耗，文中研究了云存儲(chǔ)系統(tǒng)的節(jié)點(diǎn)管理方法，即考慮在系統(tǒng)的低能耗模式(如夜晚)下關(guān)閉部分節(jié)點(diǎn)以達(dá)到節(jié)約能源的目的.但在關(guān)閉部分節(jié)點(diǎn)時(shí)，必須保證所有的數(shù)據(jù)項(xiàng)依然可用，這就要求從存儲(chǔ)節(jié)點(diǎn)集合中選出一個(gè)關(guān)閉節(jié)點(diǎn)集合，使某數(shù)據(jù)項(xiàng)的所有副本盡可能少地出現(xiàn)在該集合中.為此，文中設(shè)計(jì)了不同的算法并進(jìn)行實(shí)驗(yàn).結(jié)果表明，與基于輔助節(jié)點(diǎn)的貪心算法相比，面向異構(gòu)系統(tǒng)能耗優(yōu)化的改進(jìn)貪心算法的能耗優(yōu)化效果更好，在所需輔助節(jié)點(diǎn)數(shù)幾乎一樣的情況下，系統(tǒng)所節(jié)約的能源超過(guò)10%.

今后將在開(kāi)源Hadoop 平臺(tái)上實(shí)現(xiàn)文中提出的算法，并在實(shí)際應(yīng)用中驗(yàn)證和改進(jìn)提出的能耗優(yōu)化算法.

［1］Zhu Q，Chen Z，Tan L，et al.Hibernator:helping disk arrays sleep through the winter［C］∥Proceedings of the 20th ACM Symposium on Operating Systems Principles.Brighton:ACM，2005:177-190.

［2］Bowers K D，Juels A，Oprea A.HAIL:a high-availability and integrity layer for cloud storage［C］∥Proceedings of the 16th ACM Conference on Computer and Communications Security.New York:ACM，2009:187-198.

［3］林偉偉，劉波.基于動(dòng)態(tài)帶寬分配的Hadoop 數(shù)據(jù)負(fù)載均衡方法［J］.華南理工大學(xué)學(xué)報(bào):自然科學(xué)版，2012，40(9):42-47.Lin Wei-wei，Liu Bo.Hadoop data load balancing method based on dynamic bandwidth allocation ［J］.Journal of South China University of Technology:Natural Science Edition，2012，40(9):42-47.

［4］吳吉義，傅建慶，平玲娣，等.一種對(duì)等結(jié)構(gòu)的云存儲(chǔ)系統(tǒng)研究［J］.電子學(xué)報(bào)，2011，38(5):1100-1107.Wu Ji-yi，F(xiàn)u Jian-qing，Ping Ling-di，et al.Study on the P2P cloud storage system［J］.Acta Electronica Sinica，2011，38(5):1100-1107.

［5］Buyya R，Yeo C S，Venugopal S.Market oriented cloud computing:vision，hype，and reality for delivering IT services as computing utilities［C］∥Proceedings of the 9th IEEE/ACM International Symposium on Cluster Computing and the Grid.Washington D C:IEEE，2008:5-13.

［6］Pinheiro E，Bianchini R，Dubnicki C.Exploiting redundancy to conserve energy in storage systems［C］∥Proceedings of SIGMETRICS'06.New York:ACM，2006:15-26.

［7］Li Dong，Wang Jun.EERAID:energy efficient redundant and inexpensive disk array［C］∥Proceedings of the 11th Workshop on ACM SIGOPS European Workshop.New York:ACM，2004:29/1-6.

［8］Yao X，Wang J.Rimac:a novel redundancy-based hierarchical cache architecture for energy efficient，high performance storage［C］∥Proceedings of EuroSys'06.New York:ACM，2006:249-262.

［9］Weddle C，Oldham M，Qian J，et al.Paraid:a gear-shifting power-aware raid ［J］.ACM Transactions on Storage，2007，3(3):13/1-33.

［10］Greenan K，Long D，Miller E，et al.A spin-up saved is energy earned:achieving power-efficient，erasure-coded storage［C］∥Proceedings of the Fourth Conference on Hot Topics in System Dependability.Berkeley:USENIX Association，2008:4-9.

［11］Colarelli D，Grunwald D.Massive arrays of idle disks for storage archives ［C］∥Proceedings of Supercomputing 2002.Los Alamitos:IEEE，2002:1-11.

［12］Pinheiro E，Bianchini R.Conservation technique for disk array-based servers［C］∥Proceedings of ICS'04.New York:ACM，2004:68-78.

［13］林偉偉，齊德昱.云計(jì)算資源調(diào)度研究綜述［J］.計(jì)算機(jī)科學(xué)，2012，39(10):1-6.Lin Wei-wei，Qi De-yu.Survey of resource scheduling in cloud computing［J］.Computer Science，2012，39(10):1-6.

［14］Baliga J，Ayre R W A，Hinton K，et al.Green cloud computing:balancing energy in processing，storage，and transport［J］.Proceedings of the IEEE，2011，99(1):149-167.

［15］王意潔，孫偉東，周松，等.云計(jì)算環(huán)境下的分布存儲(chǔ)關(guān)鍵技術(shù)［J］.軟件學(xué)報(bào)，2012，23(4):962-986.Wang Yi-jie，Sun Wei-dong，Zhou Song，et al.Key technologies of distributed storage for cloud computing［J］.Journal of Software，2012，23(4):962-986.

［16］雷成軍，羅亮，吳文峻.基于云計(jì)算的集群能耗監(jiān)控與節(jié)能方法研究［J］.計(jì)算機(jī)應(yīng)用與軟件，2011，28(11):242-244.Lei Cheng-jun，Luo Liang，Wu Wen-jun.Cloud computing based cluster energy monitoring and energy saving method study［J］.Computer Applications and Software，2011，28(11):242-244.

［17］Zha H，He X，Ding C，et al.Bipartite graph partitioning and data clustering［C］∥Proceedings of the Tenth International Conference on Information and Knowledge Management.New York:ACM，2001:25-32.

［18］Karp R M.Reducibility among combinatorial problems［C］∥Proceedings of a Symposium on the Complexity of Computer Computations.Yorktown Heights:Plenum Press，1972:85-103.