數(shù)據(jù)網(wǎng)格的存儲(chǔ)資源預(yù)留方法

曲明成，吳翔虎，張 銀，廖明宏，楊孝宗，左德承

(1.哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱150001，qumingcheng@126.com;2.廈門大學(xué) 軟件學(xué)院，福建 廈門361005)

現(xiàn)有的針對(duì)存儲(chǔ)空間、計(jì)算能力和網(wǎng)絡(luò)帶寬的資源能力預(yù)留其主要解決方案為:通過在資源能力二維坐標(biāo)空間中將一段時(shí)間內(nèi)的資源能力預(yù)留抽象為矩形區(qū)域，最為有效的方法為基于時(shí)間槽的資源能力預(yù)留法［1-4］，本文中稱其為二元法(REC).數(shù)據(jù)網(wǎng)格資源能力預(yù)留可以表示成存儲(chǔ)空間與時(shí)間的二元組，即＜StorageSpace，Time ＞，該資源能力同樣為矩形區(qū)域，所以StorageSpace與Time 為確定的數(shù)值.如圖1 所示，網(wǎng)格的存儲(chǔ)資源量總數(shù)為M，有兩個(gè)資源預(yù)留分別為R1(h1，t1)，R2(h2，t2)，在圖1 中分別為兩個(gè)矩形區(qū)域，而資源能力的大小為矩形區(qū)域的面積.

圖1 REC 法資源能力預(yù)留

REC 法在數(shù)據(jù)網(wǎng)格的資源能力預(yù)留中性能較差.比如:歐洲原子能數(shù)據(jù)網(wǎng)格是為原子能實(shí)驗(yàn)特別設(shè)計(jì)的，其實(shí)驗(yàn)時(shí)以10 M/s 的速度產(chǎn)生數(shù)據(jù)，并對(duì)其存儲(chǔ)，而后以1 M/s 的速度處理數(shù)據(jù)［5］.而在其他很多時(shí)候也存在同樣的問題，比如目前將數(shù)據(jù)網(wǎng)格與計(jì)算網(wǎng)格相結(jié)合，在計(jì)算前從數(shù)據(jù)網(wǎng)格中預(yù)留一定的存儲(chǔ)數(shù)據(jù)，將數(shù)據(jù)以一定的速度存儲(chǔ)到預(yù)留的空間，待計(jì)算條件具備時(shí)以一定的速度進(jìn)行處理，并隨時(shí)刪除處理過的數(shù)據(jù)，釋放存儲(chǔ)空間［6］.為提升網(wǎng)絡(luò)的下載速度，很多副本部署方法也呈現(xiàn)同樣的特性［7-8］.

針對(duì)應(yīng)用場(chǎng)景和存在的問題，將資源能力的預(yù)留表示成四元組R=＜VP，VC，H，t ＞，其中，VP 為數(shù)據(jù)生產(chǎn)速度，VC 為數(shù)據(jù)消耗速度，H 為存儲(chǔ)空間總需求量，t 為起始時(shí)間.這樣資源能力的預(yù)留將可以表示成圖2(a)，稱這種預(yù)留方法為四元法(TR).從圖2(b)中可以看出，如果使用REC法，這兩個(gè)資源能力預(yù)留是無法被同時(shí)接納的.顯然TR 使用的資源能力較REC 小很多，如此必可以提升資源能力的使用率、資源能力預(yù)留請(qǐng)求的接納率，同時(shí)可以減少資源能力碎片，從而提升數(shù)據(jù)數(shù)據(jù)網(wǎng)格資源能力預(yù)留的整體性能.

圖2 TR 資源能力預(yù)留與REC 的比較

1 基本階梯法(BTR)

1.1 基本定義

定義1(資源能力空間) 在二維坐標(biāo)系中，以時(shí)間t 為橫坐標(biāo)，數(shù)據(jù)網(wǎng)格的可用存儲(chǔ)空間h 為縱坐標(biāo)，稱h=M(存儲(chǔ)空間總量)與h=0(橫坐標(biāo)軸)圍成的無限空間為資源能力空間.

定義2(資源能力三角形，資源三角形) 令V0，V1分別為一次資源能力預(yù)留中數(shù)據(jù)的生產(chǎn)速度和消耗速度，總存儲(chǔ)空間需求為M(總數(shù)據(jù)量)，已知t0，V0，V1，M.則資源能力預(yù)留的幾何圖形可以表示為圖3(a)，其中V0，V1分別為三角形兩條邊的斜率，稱這樣的三角形為資源能力三角形.其中，t0為預(yù)留起始時(shí)刻，t1為達(dá)到預(yù)留量時(shí)刻，t2為空間使用完畢時(shí)刻.兩個(gè)不與t 坐標(biāo)軸平行的邊的函數(shù)分別為h1=V0(t-t0)，h2=-V1(t-t2).

定義3(資源能力階梯三角形，階梯三角形) 如圖3(b)所示，將資源三角形以t1為界分割成兩個(gè)三角形，將區(qū)間(t0，t1)與(t1，t2)以時(shí)間單位r 進(jìn)行分割，其分割的份數(shù)分別為n1和n2.對(duì)于左側(cè)三角形每個(gè)小區(qū)間的面積Sir =rV0(t1+ir-t0)，而令，右側(cè)三角形每個(gè)小區(qū)間的面積-rV0(t1+jr-t2)=rV0(t2-jr-t1)，令，令，稱由和構(gòu)成的區(qū)域?yàn)橘Y源能力階梯三角形.

圖3 資源能力三角形與階梯三角形

定義4(資源能力使用率) 定義一段時(shí)間內(nèi)所接納的資源能力預(yù)留的總和與該段時(shí)間時(shí)間內(nèi)資源能力空間大小的比值為資源能力使用率(U).令某個(gè)階梯三角形的大小為，REC 法資源能力大小為.其對(duì)應(yīng)的為某段時(shí)間內(nèi)的資源能力空間大小.

1.2 公式推導(dǎo)

為了能夠有效地計(jì)算某個(gè)資源能力預(yù)留請(qǐng)求是否可以被接納，理想的情況下是資源能力空間在資源能力預(yù)留時(shí)刻處有足夠的空間可以容納下資源能力三角形(REC 法為矩形).給出ST，SR，UT，UR的求解過程，求解時(shí)參考圖3 進(jìn)行幾何推導(dǎo).

令時(shí)間單位長(zhǎng)度為r，將t1-t0分成n1=份，則，并假設(shè)區(qū)間(t0，t1)，(t1，t2)之間有整數(shù)個(gè)單位時(shí)間間隔.t1，t2的求解為

由式(1)可以得出SR為

為了求解ST，需先求出S1′，S1″，由式(1)推出:，由此可以推出:

由定義4 和式(2)，式(4)得出

2 閾值階梯法(VTR)

由于網(wǎng)絡(luò)速度的動(dòng)態(tài)變化，基本階梯法的資源能力預(yù)留存在一定的局限性(要求網(wǎng)絡(luò)速度平穩(wěn))，因此應(yīng)為生產(chǎn)與消耗速度引入一定的速度變化區(qū)間.

定義5(可靠閾值ε) 生產(chǎn)與消耗速度實(shí)際中會(huì)存在偏差，在基本階梯法中引入速度偏差，即生產(chǎn)與消耗速度分別位于區(qū)間(V0-ε，V0+ε)與(V1-ε，V1+ε)中，稱ε 為可靠閾值.

定義6(閾值梯形) 在基本階梯法中引入可靠閾值后，即相當(dāng)于在圖3(a)的幾何圖形上將非平行t 軸的兩條三角形邊的斜率分別±ε，而后形成的圖形為一個(gè)梯形，如圖4 中的由t0，t2，A，B 4 個(gè)點(diǎn)構(gòu)成的圖形，稱其為閾值梯形.

圖4 閾值梯形圖

閾值梯形的面積為資源能力預(yù)留的數(shù)量，令其為ST′，其面積可以分解為3 部分，如圖5(a)，即三角形Δt0T1A(Sa)，矩形T1T1′AB(Sb)，三角形ΔT1′T2B(Sc).將3 個(gè)區(qū)域重新組合成圖5(b)，并對(duì)新的大三角形按照基本階梯法進(jìn)行處理，同時(shí)根據(jù)圖4 進(jìn)行推導(dǎo):

根據(jù)式(4)和圖5(b)可以得出ST′=(Sa+Sc)+Sb，由此推出:

圖5 閾值梯形分解圖

定理1 由于為在基本解題法中引入可靠閾值后致使資源能力預(yù)留時(shí)間增加了Δt2=T2-t2，當(dāng)V0-V1+ε ＞0 時(shí)，如果對(duì)REC 法進(jìn)行t2可靠閾值擴(kuò)展，其資源能力SR′增加量SR＞ST=ST′-ST.

證明:

因?yàn)閂0-V1+ε ＞0，所以ΔST-ΔSR＞0，證畢.

定理1 說明，在時(shí)間增加相同的情況下針對(duì)REC 法進(jìn)行可靠擴(kuò)展的代價(jià)要大于閾值階梯法.

由式(2)，式(5)推出:

由式(7)，式(8)推出:

3 仿真實(shí)驗(yàn)

令資源能力空間具有2 500 個(gè)時(shí)間單位，資源最大數(shù)量為4 000，在一次測(cè)試中，針對(duì)該段資源能力空間隨機(jī)的產(chǎn)生不同數(shù)量的資源能力預(yù)留請(qǐng)求.判斷某請(qǐng)求是否可以被接納的條件為:該請(qǐng)求的任意一個(gè)hi都能被其所對(duì)應(yīng)的時(shí)間單位內(nèi)的資源能力空間所接納.實(shí)驗(yàn)中將測(cè)試REC 法與BRTVTR 法的資源能力預(yù)留請(qǐng)求的接納率、資源的使用率，并對(duì)其進(jìn)行對(duì)比分析.同時(shí)模擬速度動(dòng)態(tài)變化，以檢測(cè)不同的ε 對(duì)已預(yù)留的資源能力使用失效的影響.

3.1 基本階梯法性能測(cè)試

在一定的資源能力空間中，對(duì)REC 法與BTR法接納率與資源能力使用率進(jìn)行比較.從圖6 可以看出隨著請(qǐng)求數(shù)的增加兩種方法的接納率都成下降趨勢(shì)，但是BTR 法接納率明顯較REC 法的高.而從圖7 中可以看出，在接納率相同時(shí)BTR法的資源能力使用率明顯高于BTR 法.

圖6 不同資源能力請(qǐng)求REC 與BTR 接納率比較

3.2 閾值階梯法性能測(cè)試

在一定的資源能力空間中，當(dāng)ε =0 時(shí)，對(duì)REC 法與VTR 法接納率與資源能力使用率進(jìn)行比較.從圖8 可以看出隨著資源能力預(yù)留請(qǐng)求數(shù)的增加兩種方法的接納率都成下降趨勢(shì)，但是VTR 法接納率明顯較REC 法的高.而從圖9 中可以看出，在接納率相同時(shí)VTR 法的資源能力使用率明顯高于BTR 法.

圖7 相同接納率REC 與BTR 資源能力使用率比較

圖8 不同資源能力請(qǐng)求REC 與VTR 接納率比較

圖9 相同接納率REC 與VTR 資源能力使用率比較

3.3 綜合比較與預(yù)留失效檢測(cè)

令ε=0、5、10，觀測(cè)請(qǐng)求量與接納率的變化曲線，從圖10 中可以看出較小的ε 產(chǎn)生較高的接納率.令生產(chǎn)與消耗速度分別在(0.8 V，1.2 V)之間隨機(jī)的變化.在整個(gè)資源能力空間中，如果某個(gè)時(shí)間單位的實(shí)際資源能力需求量超出網(wǎng)格的資源總量那么算作一次失效，搜索請(qǐng)求量為600 時(shí)的失效時(shí)間單位數(shù)，并將總數(shù)與總的資源能力空間時(shí)間單位數(shù)進(jìn)行比值，得出失效單位數(shù)f.針對(duì)不同ε 取值分別進(jìn)行10 次實(shí)驗(yàn)，取平均值，繪出柱形圖如圖11 所示，從圖11 中可以看到，當(dāng)ε=4 時(shí)，f 已經(jīng)為0，效果較好.

圖10 ε 對(duì)VTR 接納率的影響

圖11 ε 對(duì)VTR 預(yù)留失效的影響

3.4 實(shí)驗(yàn)小結(jié)

①采用BTR 與VTR 方法進(jìn)行資源能力預(yù)留較傳統(tǒng)的REC 法有更好的性能;②隨著ε 的增加VTR 的性能逐漸降低;③在ε 達(dá)到合理的數(shù)值時(shí)預(yù)留失效可以降低為0;④采用合理的ε 值，可以大幅的提升資源能力預(yù)留請(qǐng)求的接納率和資源能力的使用率，并可以降低或消除預(yù)留失效.

4 結(jié) 論

1)提出了基本階梯法和閾值階梯法很好的實(shí)現(xiàn)了四元法預(yù)留策略，而閾值階梯法更能適應(yīng)傳輸速度動(dòng)態(tài)變化的網(wǎng)絡(luò)特性.

2)從實(shí)驗(yàn)可以看出:與二元法相比四元法能夠有效降低資源能力碎片，提升存儲(chǔ)空間的使用率，進(jìn)而提高資源能力預(yù)留的接納率和網(wǎng)格系統(tǒng)的整體吞吐量.

［1］BURCHARD L O.On the performance of computer networks with advance reservation mechanisms［C］//Proceedings of the 11thIEEE Intl.Conference on Networks(ICON’03).Washington:IEEE Computer Society，2003:449-454.

［2］HU Chunming，HUAI Jinpeng，WO Tianyu.Flexible resource reservation using slack time for service grid［C］//Proceedings of the 12th International Conference on Parallel and Distributed Systems (ICPADS′06).Washington:IEEE Computer Society，2006:327-334.

［3］胡春明，懷進(jìn)鵬，沃天宇.一種基于松弛時(shí)間的服務(wù)網(wǎng)格資源能力預(yù)留機(jī)制［J］.計(jì)算機(jī)研究與發(fā)展，2007，44(1):20-28.

［4］XIAO Peng，HU Zhigang，LI Xi，et al.A novel statistic-based relaxed grid resource reservation strategy［C］//Proceedings of the 9th International Conference for Young Computer Scientists.Washington:IEEE Computer Society，2008:703-707.

［5］Large Scale System Configuration Workshop.CERN and the DataGrid Project［EB/OL］.http://homepages.inf.ed.ac.uk/group/lssconf/files2001/datagrid-edinburgh.pdf.

［6］MCCLATCHEY R，ANJUM A，STOCKINGER H，et al.Data intensive and network aware (diana)grid scheduling［J］.Journal of Grid Computing，2007，5(1):43-64.

［7］SHI Ke.A replication and cache based distributed metadata management system for data grid［C］//Eighth ACIS International Conference on Software Engineering，Artificial Intelligence，Networking，and Parallel/Distributed Computing.Washington:IEEE Computer Society，2007:20-25.

［8］YUAN Yulai，WU Yongwei，YANG Guangwen，et al.Dynamic data replication based on local optimization principle in data grid［C］//The 6th International Conference on Grid and Cooperative Computing(GCC 2007).Washington:IEEE Computer Society，2007:815-822.