網(wǎng)格環(huán)境下基于文件訪問的負(fù)載平衡策略研究

網(wǎng)格環(huán)境下基于文件訪問的負(fù)載平衡策略研究

網(wǎng)絡(luò)包括計算網(wǎng)絡(luò)、數(shù)據(jù)網(wǎng)絡(luò)、網(wǎng)絡(luò)和知識網(wǎng)絡(luò)。要解決的共同問題是分布廣泛、數(shù)量大的資源共享和計算。數(shù)據(jù)存儲虛擬化是數(shù)據(jù)存儲計算的基礎(chǔ)，被稱為網(wǎng)格存儲。利用虛擬化技術(shù)和開放標(biāo)準(zhǔn)，分布、異構(gòu)存儲和數(shù)據(jù)集成可以為各種網(wǎng)格服務(wù)。網(wǎng)格存儲有三個優(yōu)點：更高的容錯誤和冗余，在負(fù)載波動中具有更好的性能和更低的成本。負(fù)載平衡是優(yōu)化網(wǎng)格存儲性能的關(guān)鍵,因為它可以提高系統(tǒng)整體的吞吐率和服務(wù)加速比.目前解決負(fù)載不均衡主要有兩種方法:靜態(tài)的數(shù)據(jù)分布優(yōu)化技術(shù)和動態(tài)的負(fù)載平衡技術(shù).靜態(tài)算法的固有缺點是數(shù)據(jù)分布預(yù)先確定,很難為動態(tài)數(shù)據(jù)訪問提供負(fù)載平衡.典型的動態(tài)負(fù)載平衡研究是文獻中提出的磁盤冷卻算法,隨著系統(tǒng)負(fù)載的變化,負(fù)載在重載與輕載的單元間遷移,從而達到系統(tǒng)的負(fù)載平衡.但該算法只是針對同構(gòu)存儲單元提出的,并且算法收斂時間長、負(fù)載調(diào)整的開銷大.針對以上不足,作者提出一種能實時反映存儲單元負(fù)載壓力的能量模型,并在此模型基礎(chǔ)上綜合考慮文件訪問特點和存儲單元性能差異,給出一種自適應(yīng)的負(fù)載平衡策略.實驗結(jié)果表明,提出的負(fù)載平衡策略適合網(wǎng)格存儲環(huán)境,提高了系統(tǒng)響應(yīng)性能和系統(tǒng)吞吐率,減少了系統(tǒng)開銷.1能量模型1.1訪問頻率及文件fi不同文件的訪問頻度差異造成存儲系統(tǒng)中各存儲單元的負(fù)載不均衡.采用能量這一概念來描述文件受訪問情況和由此給存儲系統(tǒng)帶來的負(fù)載壓力.文件能量受以下幾個因素影響:①與文件受訪問的次數(shù)相關(guān).受訪問次數(shù)越多,文件具有的能量越高.②與文件并發(fā)訪問數(shù)相關(guān).并發(fā)訪問數(shù)與當(dāng)時系統(tǒng)平均并發(fā)訪問數(shù)比值越高,文件具有的能量越高.③與文件大小成正比.文件越大,意味著文件受訪問時間越長,文件具有的能量越高.④文件能量隨訪問頻度呈指數(shù)衰減.類似于自然界中的放射性元素,有相應(yīng)的半衰期τc.若將用戶對存儲系統(tǒng)的每一次訪問都依次編號,ei(fi,t)為用戶第t次訪問存儲系統(tǒng)時文件fi所具有的能量,α=2-1/τc為能量的衰減基數(shù),則有:①如果在用戶第t次訪問前,文件fi從未被訪問過,則ei(fi,t)=0.②如果在用戶第t次訪問時,訪問文件fi,則ei(fi?t)=ei(fi,t-)+ρiˉρli.其中t-為用戶第t次訪問之前的時間點;ρi為用戶第t次訪問時文件fi的并發(fā)訪問數(shù);ˉρ為用戶第t次訪問時存儲系統(tǒng)的平均并發(fā)訪問數(shù);li為文件fi的長度.③如果在用戶第t1與t2次訪問期間,沒有發(fā)生對文件fi的訪問,則ei(fi,t2)=ei(fi,t1)αt2-t1.④如果在用戶第t2次訪問時,訪問文件fi,且上次對文件fi的訪問發(fā)生在第t1次,則ei(fi,t2)=ei(fi,t1)αt2-t1+ρiˉρli.(1)1.2相對能量.帶寬存儲單元的能量為其存儲的所有文件的能量和,根據(jù)存儲文件或文件分塊的不同,存儲單元擁有不同的能量.但能量高低并不能直接反映其上的負(fù)載情況,因為網(wǎng)格環(huán)境中存儲單元是異構(gòu)的,各存儲單元擁有不同的存儲空間和訪問帶寬.為了更加準(zhǔn)確地描述存儲單元當(dāng)前的負(fù)載,引入相對能量.相對能量主要受以下兩個因素影響:①在具有同等能量的情況下,存儲單元擁有的帶寬Sj越大,意味著單位帶寬分擔(dān)的文件能量越低,其相對能量也越低;②如果存儲單元當(dāng)前可用存儲空間Lj比系統(tǒng)當(dāng)前平均可用存儲空間ˉL大,則說明該存儲單元接納遷移文件的能力強,其相對能量越低.用E(nj,t)表示t時刻存儲單元nj所擁有的相對能量,則E(nj,t)=wjSjˉLLj,(2)式中wj為存儲單元nj上所有文件或者文件分塊擁有的能量和∑ei.2負(fù)載平衡策略2.1基于概率觸發(fā)函數(shù)當(dāng)存儲單元的負(fù)載超過一定數(shù)值時就會觸發(fā)文件遷移操作,傳統(tǒng)的觸發(fā)函數(shù)如圖1a所示,觸發(fā)條件被設(shè)定成一固定閾值.這種設(shè)置有一個缺點:存儲系統(tǒng)的訪問請求一般具有較大的傾斜性,在遷移觸發(fā)函數(shù)被觸發(fā)時,后續(xù)訪問請求可能迅速使存儲單元的負(fù)載情況惡化,進而導(dǎo)致存儲系統(tǒng)性能降低.作者提出的觸發(fā)函數(shù)是一種適應(yīng)異構(gòu)存儲系統(tǒng)、基于概率的觸發(fā)函數(shù)(randomearlymigration),式(3)為REM觸發(fā)函數(shù),函數(shù)形態(tài)如圖1b所示,圖中橫坐標(biāo)為一衡量存儲單元負(fù)載的變量,縱坐標(biāo)為文件遷移概率,用區(qū)間值表示.Ρj={0λ≤LminΡmaxλ-LminLmax-Lmin1λ≥Lmax,(λ∈{Lmin,Lmax})(3)λ=S′j/S,(4)S=minSjˉSˉSc?ˉS.(5)式中:Sj為存儲單元nj當(dāng)前的可用下行帶寬;S′j為存儲單元nj總下行帶寬;ˉS為存儲系統(tǒng)當(dāng)前平均可用下行帶寬;ˉSc為存儲系統(tǒng)擁有的平均下行帶寬.2.2基于文件的遷移為了便于描述,給出能量密度的定義:ρi=ei/li.(6)式中:ρi為文件fi的能量密度;li為文件fi的長度;ei為文件fi此時具有的能量.存儲系統(tǒng)的文件訪問請求一般具有較大的傾向性.一般地,如果一個文件被訪問,則在最近一段時間內(nèi)會經(jīng)常被訪問.因此,進行負(fù)載調(diào)整時必須同時考慮文件的訪問特點,遷移存儲單元上當(dāng)前正在被訪問且能量密度最高的文件,這樣可以使負(fù)載調(diào)整與用戶請求相重疊,從而減少負(fù)載平衡的I/O開銷,并且這種文件遷移策略有更好的收斂性.傳統(tǒng)的負(fù)載平衡策略,如磁盤冷卻算法,會根據(jù)負(fù)載情況選取負(fù)載最重的文件從很忙的設(shè)備讀出,寫入較空閑的設(shè)備,沒有考慮當(dāng)前文件訪問請求,負(fù)載調(diào)整時在一定程度上又加重了設(shè)備的負(fù)載.如果考慮當(dāng)前的文件訪問特點,選擇能量密度較高的文件遷移,在用戶訪問時將其讀出,可節(jié)省負(fù)載調(diào)整時的系統(tǒng)開銷.2.3負(fù)載調(diào)整及能量溢出在文件遷移過程中,往往會出現(xiàn)源存儲單元負(fù)載瓶頸消除的同時,目地存儲單元又成為新負(fù)載瓶頸的情況.頻繁的文件遷移會降低系統(tǒng)性能,要避免這種情況的發(fā)生,應(yīng)按照以下策略進行負(fù)載調(diào)整:①負(fù)載調(diào)整以數(shù)據(jù)塊為單位進行.文件以固定大小的數(shù)據(jù)塊為單位存儲,并以數(shù)據(jù)塊為單位進行遷移,由此可避免大文件遷移耗時長、消耗帶寬過多、易造成目地存儲單元性能瓶頸等不足.②選定的目地存儲單元nj應(yīng)具有較低的能量.設(shè)Ej為nj的能量,ˉE為系統(tǒng)當(dāng)前的平均能量,δ為一調(diào)整因子,滿足Ej≤δE,且nj在接受數(shù)據(jù)塊b后,其能量變化量ΔEj最小.③在任意時刻,目的存儲單元拒絕同時接受不同遷移任務(wù)的多個數(shù)據(jù)塊,避免因接受數(shù)據(jù)塊過多而導(dǎo)致能量溢出,同時避免多個遷移任務(wù)間的相互影響,延遲完成任務(wù).2.4文件能量密度無特定閾值提出的負(fù)載平衡策略是基于復(fù)制操作進行的,對于負(fù)載調(diào)整過程中產(chǎn)生的數(shù)據(jù)副本有:①對任意數(shù)據(jù)塊,在進行負(fù)載調(diào)整時都會產(chǎn)生且僅產(chǎn)生一個數(shù)據(jù)副本.②文件能量密度低于某個閾值ρ′時啟動回收操作.當(dāng)存在多個副本時,根據(jù)需要可刪除最閑的一個,也可刪除若干個,但刪除副本后的能量密度不應(yīng)高于其閾值ρnew,因為一旦某副本被刪除,存儲該文件副本的其它存儲單元的閑置程度會下降,甚至可能需要重新進行負(fù)載調(diào)整.ρ′=αρ,(7)ρnew=βρ.(8)式中:ˉρ表示存儲系統(tǒng)中當(dāng)前所有文件的平均能量密度;α,β為調(diào)節(jié)因子.2.5保護方式及其實現(xiàn)設(shè)存儲系統(tǒng)為D:{n1,n2,…,nM},nj=(Lj,Sj,Ej),Lj為存儲單元nj當(dāng)前的可用存儲空間;Sj為存儲單元nj當(dāng)前的可用下行帶寬;Ej為存儲單元nj當(dāng)前所具有的相對能量.設(shè)系統(tǒng)存儲的所有文件為F:{f1,f2,…,fn},fi=(li,ei);li為文件fi的長度;ei為文件fi當(dāng)前所具有的能量.算法具體描述如下:輸入:存儲系統(tǒng)的存儲單元數(shù)m及文件數(shù)n;輸出:負(fù)載平衡所需進行的動作ACTION.步驟1根據(jù)存儲單元nj的可用帶寬Sj,依據(jù)式(3)判斷是否需要觸發(fā)nj上的文件遷移操作.步驟2對所有觸發(fā)文件遷移操作的nj,依據(jù)式(6)選出各存儲單元上當(dāng)前正在訪問的能量密度最高的文件進行遷移.步驟3依據(jù)2.3節(jié)所述策略,選擇合適的目的存儲單元,安排數(shù)據(jù)復(fù)制操作.步驟4對擁有數(shù)據(jù)副本的所有數(shù)據(jù)塊d,結(jié)合式(7)(8)檢查是否有數(shù)據(jù)副本需要刪除,執(zhí)行數(shù)據(jù)副本刪除操作.3實驗結(jié)果優(yōu)化通過模擬實驗來驗證所提出的負(fù)載平衡策略對存儲系統(tǒng)I/O執(zhí)行時間的優(yōu)化效果.實驗的訪問請求采用合成負(fù)載方式.將負(fù)載平衡策略與存儲系統(tǒng)常用的磁盤冷卻算法進行比較.3.1系統(tǒng)帶寬生成存儲系統(tǒng)由10塊磁盤構(gòu)成,總計有可用存儲空間120GB,下行帶寬100MB,上行帶寬50MB.各磁盤取不同的性能值以模擬真實的網(wǎng)格環(huán)境.為了簡化,規(guī)定對構(gòu)成存儲系統(tǒng)的任意磁盤nj,初始空間Lj以100MB為單位生成,取值范圍表示為1GB≤Lj≤30GB」;初始下行帶寬以1MB為單位生成,取值范圍表示為5MB≤Sj≤25MB」;初始上行帶寬為5MB,為一常數(shù).對于系統(tǒng)中的任意存儲文件fi,其長度li以100MB為單位生成,取值范圍表示為[0.1GB≤li≤10.0GB].初始情況下,每一磁盤上存儲5個文件,總計消耗80%存儲空間;文件以100MB為單位劃分為獨立的數(shù)據(jù)塊.訪問請求采用FCFS方式,每一訪問請求需要的下行帶寬取固定值S=500kB.表1給出實驗中用到的參數(shù).3.2生成文件的概率實際的訪問蹤跡對模擬實驗非常重要,但人們收集的蹤跡往往很難反映出所有的訪問模式.因此實驗采用按一定方式合成負(fù)載的方法產(chǎn)生訪問請求序列.為了反映用戶請求的偏斜性,采用X/Y分布產(chǎn)生用戶請求,即X的用戶請求僅訪問占總量Y的少數(shù)文件.將文件編為1～50號,對于任意給定的參數(shù)X/Y,文獻168中給出了請求訪問的文件號i≤s時的概率:P(i≤s)=[S/N]lg(X/100)/lg(Y/100).(9)式中N為文件總數(shù).根據(jù)式(9)可求出訪問每個文件的概率,此概率反映文件的受訪問頻度,通過改變文件編號模擬文件受訪問頻度的動態(tài)變化.以1000次用戶訪問為一個周期,文件編號i為i=(i+T)%50,式中T為周期.3.3系統(tǒng)平均處理時間連續(xù)進行10組模擬實驗,每組按3.1節(jié)所述方法隨機生成存儲單元和文件,按3.2節(jié)所述方法生成訪問請求序列.為了驗證所提出的負(fù)載平衡策略的性能,與傳統(tǒng)的磁盤冷卻算法和無負(fù)載平衡策略進行比較,計算3種策略下按1,2,5,10s時間間隔計算1萬次訪問請求所需的平均處理時間和系統(tǒng)平均吞吐量.磁盤冷卻算法采用相對負(fù)載,該算法是根據(jù)文獻171中的算法改造而來.無負(fù)載平衡策略中每一存儲單元初始存有5個文件,無論存儲單元的負(fù)載怎樣變化都不進行負(fù)載平衡.請求平均處理時間為所有訪問請求的處理時間總和與請求總數(shù)的比值,反映了系統(tǒng)的服務(wù)速度;系統(tǒng)平均吞吐量為單位時間內(nèi)系統(tǒng)處理的請求數(shù),反映了系統(tǒng)的服務(wù)規(guī)模.表2為訪問請求按X/Y=90/10分布時不同策略下的性能對比.表中策略1為作者的負(fù)載平衡策略,策略2為磁盤冷卻算法.平均處理時間比率為本策略與無負(fù)載平衡策略下的請求平均處理時間之比,平均吞吐量比率