云存儲多異構(gòu)文件聯(lián)合延遲尾概率凸優(yōu)化分析

許小媛，李海波，黃 黎，2

1.江蘇開放大學(xué) 信息工程學(xué)院，南京210017

2.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京211106

由于大數(shù)據(jù)分析和云計(jì)算[1]等新興應(yīng)用的出現(xiàn)，如今的分布式存儲系統(tǒng)通常存儲數(shù)PB[2]的數(shù)據(jù)。因此，這些系統(tǒng)正在從完全數(shù)據(jù)復(fù)制過渡到使用擦除代碼在多臺機(jī)器和機(jī)架上編碼和分發(fā)數(shù)據(jù)塊，以便在系統(tǒng)出現(xiàn)故障的情況下更有效地利用存儲空間，同時保持高可靠性。結(jié)果表明，由于存儲空間和數(shù)據(jù)中心占用空間較小，與重復(fù)編碼相比，使用擦除編碼[3]可以降低存儲成本50%以上。

對于擦除編碼存儲系統(tǒng)，文件被編碼成多個大小相等的數(shù)據(jù)塊，允許從任何子集進(jìn)行重建。因此，重建文件需要從不同的服務(wù)器獲取不同的塊，這導(dǎo)致尾部延遲顯著增加，因?yàn)樵谶@樣的系統(tǒng)中，服務(wù)延遲是由最熱的存儲節(jié)點(diǎn)以最高的擁塞和最慢的速度決定的，這實(shí)際上成了性能瓶頸[4]。文獻(xiàn)[5]指出盡管存在負(fù)載平衡和資源管理等機(jī)制，但對大型存儲系統(tǒng)的評估表明，延遲性能具有高度的隨機(jī)性。文獻(xiàn)[6]指出擦除編碼數(shù)據(jù)存儲系統(tǒng)的總體響應(yīng)時間由所需并行作業(yè)的長尾分布控制，每個作業(yè)可能有多個并行任務(wù)。文獻(xiàn)[7]指出盡管最近在提供平均服務(wù)延遲的界限方面取得了一些研究進(jìn)展，但對于擦除編碼存儲系統(tǒng)中的尾延遲知之甚少。文獻(xiàn)[8]中描述了具有獨(dú)立指數(shù)服務(wù)時間的相同服務(wù)器的基于復(fù)制的系統(tǒng)的平均服務(wù)延遲?；诓脸幋a的系統(tǒng)的問題仍然是一個開放的問題。為了提供同構(gòu)文件的平均服務(wù)延遲上限，文獻(xiàn)[9]提出Fork-join隊(duì)列分析通過將每個文件請求分叉到所有存儲節(jié)點(diǎn)來提供平均服務(wù)延遲的上限。文獻(xiàn)[10]提出基于排隊(duì)論分析的塊調(diào)度策略，它只允許緩沖區(qū)頭部的第一個請求向前移動。然而，由于狀態(tài)爆炸問題，這兩種方法都無法量化尾部延遲，因?yàn)橄鄳?yīng)隊(duì)列模型的狀態(tài)不僅必須封裝當(dāng)前系統(tǒng)的快照（包括塊放置和排隊(duì)請求），而且還必須封裝單個節(jié)點(diǎn)處理塊請求的過去歷史。隨后，利用順序統(tǒng)計(jì)分析和概率請求調(diào)度策略，在文獻(xiàn)[11]中給出了任意服務(wù)時間分布和異構(gòu)文件的平均延遲界限。文獻(xiàn)[12]基于復(fù)制系統(tǒng)的大量服務(wù)器限制，使用具有均勻概率和指數(shù)服務(wù)時間的概率調(diào)度來顯示與復(fù)制相比擦除編碼的延遲性能的改進(jìn)。文獻(xiàn)[13]分析了不同基于隊(duì)列的調(diào)度策略，假設(shè)在隨機(jī)塊放置的情況下，服務(wù)器之間的負(fù)載是對稱的。雖然降低平均延遲被發(fā)現(xiàn)對降低延遲包絡(luò)有積極影響，但量化和優(yōu)化擦除編碼存儲的尾部延遲仍然是開放問題。

本文提出一種分析框架來量化分布式存儲系統(tǒng)中使用擦除碼來存儲文件的尾部延遲。這個問題具有挑戰(zhàn)性：（1）最慢的存儲節(jié)點(diǎn)的性能會嚴(yán)重影響尾部延遲；（2）需要動態(tài)解決一個聯(lián)合塊調(diào)度問題，以決定為每個文件請求服務(wù)分配塊服務(wù)器；（3）由于塊訪問的依賴性和干擾，共享存儲服務(wù)器上不同文件的時間問題更加復(fù)雜。

1 系統(tǒng)模型

考慮由m個異構(gòu)服務(wù)器組成的數(shù)據(jù)中心[14]，表示為M=1,2,…,m，也稱為存儲節(jié)點(diǎn)。采取分布式存儲一組r文件，索引為i=1,2,…,r，將每個文件i劃分為ki個固定大小的數(shù)據(jù)塊，然后使用(ni,ki)MDS擦除代碼對其進(jìn)行編碼，以生成與文件i相同大小的ni個不同數(shù)據(jù)塊。編碼塊被分配并存儲在ni個不同的存儲節(jié)點(diǎn)上，由一組Si個存儲節(jié)點(diǎn)表示，滿足條件Si?M和ni=|Si|。使用(ni,ki)MDS擦除代碼可從ni數(shù)據(jù)塊中的ki任何子集重建文件，同時還引入了ni ki的冗余因子。因此，在每個文件請求到達(dá)時，調(diào)度程序選擇ki不同的塊并檢索其以重構(gòu)所需的文件。圖1給出一個有7個節(jié)點(diǎn)的分布式存儲系統(tǒng)。系統(tǒng)中分別使用（6，4）、（5，3）和（3，2）擦除碼存儲3個文件。到達(dá)系統(tǒng)的文件請求被聯(lián)合調(diào)度以訪問ni不同塊中的ki，以前的研究主要集中在平均延遲優(yōu)化上。

圖1 分布式存儲系統(tǒng)（7節(jié)點(diǎn)、3文件）

然而，這兩種方法都沒有量化尾部延遲，因?yàn)橄鄳?yīng)隊(duì)列模型的狀態(tài)不僅必須封裝當(dāng)前系統(tǒng)的快照，包括塊放置和排隊(duì)請求，而且還必須封裝單個節(jié)點(diǎn)處理塊請求歷史。這是因?yàn)樯傻年?duì)列的馬爾可夫鏈表示需要對每個狀態(tài)進(jìn)行封裝：（2）隊(duì)列中每個批的狀態(tài)；（1）將塊請求精確分配給存儲節(jié)點(diǎn)，因?yàn)楣?jié)點(diǎn)由多個異構(gòu)文件共享。這會導(dǎo)致狀態(tài)爆炸問題，因?yàn)閷?shí)際的存儲系統(tǒng)通常處理大量的文件和節(jié)點(diǎn)。截至目前，量化擦除編碼存儲系統(tǒng)的尾部延遲仍然是開放問題，因?yàn)樵诼?lián)合請求調(diào)度方面存在挑戰(zhàn)以及散亂片段對熱存儲節(jié)點(diǎn)的依賴性?？紤]存儲3個文件的擦除編碼存儲系統(tǒng)，如圖1所示。很容易看出，以相同的概率訪問可用塊的簡單調(diào)度策略會導(dǎo)致較高的尾部延遲，這是由性能最低的熱存儲節(jié)點(diǎn)（在本例中為節(jié)點(diǎn)1和5）決定的。然而，負(fù)載平衡每個服務(wù)器處理的請求數(shù)量的策略并不一定優(yōu)化所有文件的尾部延遲，這些文件使用不同的擦除代碼，從而對服務(wù)延遲產(chǎn)生不同的影響。假設(shè)來自所有存儲節(jié)點(diǎn)的塊傳輸時間具有相同分布，使用（6，4）代碼的文件1仍然可能比使用（3，2）代碼的文件3具有更高的尾部延遲，因?yàn)槊總€文件請求的服務(wù)時間由4個選定塊（而不是2個選定塊）中最慢的一個決定。

本文中使用“概率調(diào)度”策略[15]：（1）以預(yù)定概率P(Ai)將每批數(shù)據(jù)塊請求（對應(yīng)于同一文件請求）發(fā)送到適當(dāng)節(jié)點(diǎn)集（由文件i的服務(wù)器集Ai表示）；（2）每個節(jié)點(diǎn)在本地隊(duì)列中緩沖請求并按順序處理?？尚懈怕蕿?/p>

的概率調(diào)度策略存在于且僅當(dāng)存在條件概率πi,j∈[0,1],?i,j滿足：

如果j?Si，則πi,j=0。πi,j是從節(jié)點(diǎn)j檢索文件i塊的概率。因?yàn)槊總€集合Ai都包含ki節(jié)點(diǎn)，可得ki,?i?？紤]圖1所示的示例。在概率調(diào)度下，當(dāng)文件1請求到達(dá)時，隨機(jī)選擇具有已知概率{π1,j,?j}的可用文件塊的k1=4節(jié)點(diǎn)，并將一個塊請求分派給每個選定的存儲節(jié)點(diǎn)。然后，每個存儲節(jié)點(diǎn)獨(dú)立管理其本地隊(duì)列，并按順序繼續(xù)處理請求。如果文件請求的所有塊請求都由單個節(jié)點(diǎn)處理，則該文件請求將完成。

本文所用到的變量參數(shù)聲明如下：r是系統(tǒng)中的文件數(shù)，i=1,2,…,r；m是存儲節(jié)點(diǎn)數(shù)是文件i的擦除代碼參數(shù)；λi是文件i的到達(dá)率；πij是從節(jié)點(diǎn)j檢索文件i塊的概率；Li是檢索文件i的延遲；x是參數(shù)索引延遲尾概率；Qj是節(jié)點(diǎn)j的逗留時間；Xj是節(jié)點(diǎn)j的塊服務(wù)時間；Mj(t)是節(jié)點(diǎn)j服務(wù)時間的矩生成函數(shù)；μj是節(jié)點(diǎn)j的平均服務(wù)時間；Λj是節(jié)點(diǎn)j到達(dá)率；ρj是節(jié)點(diǎn)j的請求強(qiáng)度；Si是來自文件i的塊的存儲節(jié)點(diǎn)集；Ai是用于從文件i提供文件塊的節(jié)點(diǎn)集是節(jié)點(diǎn)j的移動指數(shù)分布服務(wù)時間參數(shù)；ωi是文件i的權(quán)重。

2 尾部延遲界限

2.1 任意服務(wù)時間分布情形

首先量化具有任意服務(wù)時間分布（即任意已知的Xj分布）的擦除編碼存儲系統(tǒng)的尾延遲。設(shè)Qj為塊請求在節(jié)點(diǎn)j中花費(fèi)的（隨機(jī)）時間（逗留時間）。在概率調(diào)度下，文件i請求的響應(yīng)時間（用Li表示）由隨機(jī)選擇的存儲節(jié)點(diǎn)集Ai處的最大塊響應(yīng)時間確定。

在概率調(diào)度下，塊請求在節(jié)點(diǎn)j處的到達(dá)形成速率為的Poisson過程。設(shè)為在服務(wù)器j處處理單個塊的服務(wù)時間的矩生成函數(shù)。然后，可給出了Qj的Laplace-Stieltjes變換：

式中，ρj=ΛjE[]Xj是節(jié)點(diǎn)j的請求強(qiáng)度。此外，使用概率調(diào)度將文件i的延遲表示為Li。文件i的延遲尾概率定義為給定x的Li大于或等于x的概率。對于給定的文件i的權(quán)重ωi，希望最小化目標(biāo)由于在一般服務(wù)時間分布中很難找到閉式的Pr(Li≥x)，因此在此基礎(chǔ)上進(jìn)一步使用一個上界來代替目標(biāo)中的Pr(Li≥x)。下面的定理給出了文件延遲尾概率的上界。

定理1對于任意且滿足Mj(tj)＜∞和情況下，使用概率調(diào)度的文件i，的延遲尾概率上界為：

證明使用概率調(diào)度來考慮延遲尾概率的上界，如下所示：

其中，（a）表示從概率調(diào)度開始，檢索文件的時間是從Ai檢索所有塊的最大時間。利用馬爾可夫引理，可得到使用Pollaczek-Khinchine公式對公式（2）中的Qj進(jìn)行Laplace變換，并設(shè)定S=-tj。然而，只有當(dāng)時，表達(dá)式才是有限的。這證明了定理陳述中的結(jié)果。

在某些情況下，力矩生成函數(shù)可能不存在，這意味著對于任何tj＞0，都不滿足條件在這種情況下，將直接使用Laplace變換在下一個定理中給出另一個上界。

定理2對于任意sj＞0，且文件i，Pr(Li≥x)延遲尾概率上界為：

證明這個結(jié)果是定理1的一個變種，其中馬爾可夫引理是使用排隊(duì)等待時間的Laplace變換而不是矩生成函數(shù)。

2.2 移動指數(shù)時間分布情形

考慮當(dāng)服務(wù)時間分布是移動指數(shù)分布時的情況。假設(shè)來自服務(wù)器j的服務(wù)時間分布具有概率密度函數(shù)fXj(x)，如下所示：

指數(shù)分布是βj=0的特例。力矩生成函數(shù)如下：

其中，t＜αj。由此可得以下結(jié)果。

推論1對于任，當(dāng)服務(wù)器的服務(wù)時間分布為轉(zhuǎn)移指數(shù)分布時，文件i的延遲尾概率Pr(Li≥x)上界為：

由于指數(shù)分布是移位指數(shù)分布的一個特例，可得如下推論。

推論2對于任意當(dāng)服務(wù)器的服務(wù)時間分布為指數(shù)分布時，文件i的延遲尾概率Pr(Li≥x)上界為：

進(jìn)一步量化了任意擦除編碼存儲系統(tǒng)文件大小和指數(shù)服務(wù)時間下的服務(wù)延遲尾指數(shù)。證明了基于概率調(diào)度的算法獲得了α-1的最優(yōu)尾指數(shù)，其中α＞2是Pareto分布塊大小的形狀參數(shù)。

2.3 加權(quán)延遲尾概率優(yōu)化模型

本節(jié)提出一個包含多個異構(gòu)文件的聯(lián)合延遲尾概率優(yōu)化模型。由于的延遲尾概率由給出，因此考慮一個最小化所有文件的加權(quán)延遲尾概率的優(yōu)化，定義為：

式中，ωi是分配給文件i的正向權(quán)重。設(shè)定從而使到達(dá)率較大的文件加權(quán)更高，文件i服務(wù)時間的延遲尾概率為所提出的延遲尾概率界的目標(biāo)函數(shù)為：

上述約束中，約束①給出在給定調(diào)度概率πi,j和到達(dá)率λi下每個節(jié)點(diǎn)的總到達(dá)率Λj；約束②定義了關(guān)于參數(shù)tj的矩生成函數(shù)；約束③定義了服務(wù)器的流量強(qiáng)度；約束④～⑥保證調(diào)度概率是可行的；根據(jù)約束⑨中的技術(shù)約束，表面力矩生成函數(shù)存在。如果滿足約束⑨，則ρj＜1也成立，從而確保存儲系統(tǒng)的穩(wěn)定性（即，在給定到達(dá)率和調(diào)度概率下，隊(duì)列長度不會膨脹到無窮大）。注意到tj＞0可以等價(jià)地轉(zhuǎn)換為tj≥0（約束⑧），因?yàn)閠j=0不滿足，并且已經(jīng)被考慮在內(nèi)。對于π的優(yōu)化有助于降低加權(quán)尾延遲概率，并在選擇訪問文件的最低隊(duì)列服務(wù)器時提供了顯著的靈活性。

備注1由于約束⑨在(π,t)中是非凸的，因此所提出的WLTP優(yōu)化是非凸的。此外，內(nèi)容放置S具有整數(shù)約束。

2.4 優(yōu)化問題凸性分析

為得到算法解，證明當(dāng)其他變量固定時，對于優(yōu)化變量t和π，問題是單調(diào)凸的，這樣可以簡化優(yōu)化算法設(shè)計(jì)，由此可以提出一個交替優(yōu)化算法來解決這個問題。

定理3對于滿足約束①～⑨，在區(qū)域t=(t1,t2,…,tm)內(nèi)，目標(biāo)函數(shù)是凸性的。

證明在求和過程中，該項(xiàng)只依賴于tj值，這表明相對于tj值是凸的。因?yàn)檫@里只有一個索引j，所以這個證明的其余部分可忽略這個子卷積。

因此，F(xiàn)(t)可表示為的

乘積，其中由于滿足

約束①～⑨，h(t)＞0。此外，h(t)的所有正導(dǎo)數(shù)都是非正的。設(shè)w(t)=-h′(t)，則w(t)≥0，w′(t)≥0。由此可得：

進(jìn)而可得F″(t)計(jì)算形式為：

結(jié)合h(t)≥0和w′(t)≥0可得在區(qū)間t=(t1,t2,…,tm)內(nèi)，目標(biāo)函數(shù)是凸的。

然后，對定理3進(jìn)行擴(kuò)展，驗(yàn)證在區(qū)間π=(πij,?i=1,2,…,r,j=1,2,…,m)上目標(biāo)函數(shù)也是凸的。

定理4對于區(qū)間目標(biāo)函數(shù)是凸的。

首先證明Hj在Λj中是單調(diào)遞增凸函數(shù)，Hj可以寫成：

因此，Hj是Λj的單調(diào)遞增凸函數(shù)。同時因?yàn)棣玧是Λj的單調(diào)遞增凸函數(shù)。兩項(xiàng)乘積也為凸函數(shù)，結(jié)論得證。

2.5 優(yōu)化算法設(shè)計(jì)

因?yàn)槟繕?biāo)模型相對于π和t是凸函數(shù)，嚴(yán)格的＜約束可以修改為≤足夠小約束。約束條件在每個變量中也分別是凸的。現(xiàn)在將開發(fā)一個交替最小化算法來解決這個問題。

（1）算法結(jié)構(gòu)。為了描述算法，首先定義三個子問題：

子問題1t優(yōu)化問題，輸入π,S。

約束條件：①～③，⑧～⑨。

子問題2π優(yōu)化問題，輸入t,S。

約束條件：①～⑥，⑨。

子問題3S優(yōu)化問題，輸入t,π。

約束條件：①～⑦。

對于布局子問題（S-優(yōu)化），考慮對每個文件請求分別使用固定π和t進(jìn)行S上的優(yōu)化。首先重寫文件i的延遲尾概率，如下所示：

通過將現(xiàn)有πiu分配給具有現(xiàn)有負(fù)載的服務(wù)器來量化對總延遲尾概率的貢獻(xiàn)。Gr上的最小權(quán)匹配可找到一個最小化的最優(yōu)β：

算法1給出了一種求解延遲尾概率問題的算法，其中隨機(jī)選擇文件的放置順序。其決定被更改的文件的順序會有所不同。在所提出的算法中，由于存在一個交替最小化的外循環(huán)，只需對文件進(jìn)行一次遍歷。由于目標(biāo)是非負(fù)的，并且目標(biāo)在每次迭代中都是非遞增的，所以算法收斂。

算法1延遲尾概率問題的改進(jìn)算法

3 實(shí)驗(yàn)分析

對比算法：（1）預(yù)計(jì)平等訪問概率（PEAP），對于每個文件請求，聯(lián)合請求調(diào)度器以相同的概率選擇可用節(jié)點(diǎn)。（2）隨機(jī)預(yù)計(jì)平等訪問概率（PEAP-RP），與PEAP策略相比，塊被均勻地隨機(jī)放置。（3）預(yù)計(jì)服務(wù)費(fèi)率比例分配（PSPP），聯(lián)合請求調(diào)度器選擇訪問概率與存儲節(jié)點(diǎn)的服務(wù)速率成比例。此策略根據(jù)服務(wù)器的服務(wù)速率按比例分配服務(wù)器。（4）隨機(jī)預(yù)計(jì)服務(wù)費(fèi)率比例分配（PSPP-RP），與PSPP策略相比，塊被均勻地隨機(jī)放置。在輔助變量選擇上，對加權(quán)延遲尾概率進(jìn)行了優(yōu)化。

實(shí)驗(yàn)參數(shù)：云存儲文件數(shù)量r=1 000，所有文件大小是200 MB，使用由m=12個分布式節(jié)點(diǎn)組成的分布式存儲系統(tǒng)中的擦除碼（7，4）?？紤]塊服務(wù)時間隨速率αj和位移βj服從一個位移指數(shù)分布，本文采用12個不同服務(wù)速率αj和移位βj的異構(gòu)存儲節(jié)點(diǎn)，見表1所示。前250個文件每秒的基本到達(dá)率為2/150，后250個文件每秒的基本到達(dá)率為4/150，接下來的250個文件是6/150，最后的250個文件是3/150。本文還考慮了文件的權(quán)重與到達(dá)率成正比。為了初始化算法，對于所有tj=0.01在放置服務(wù)器上選擇πij=k/n。然而，由于這些π和t的選擇可能不可行，將初始化π修改為與上述選擇最接近的范數(shù)可行解。

表1 異構(gòu)存儲節(jié)點(diǎn)參數(shù)設(shè)定

實(shí)驗(yàn)1（加權(quán)延遲尾概率）圖2中給出本文算法以及對比算法的加權(quán)延遲尾概率實(shí)驗(yàn)?zāi)M結(jié)果。本文算法策略通過提出的在π、t和S上的替代優(yōu)化算法來求解最優(yōu)加權(quán)延遲尾概率。通過優(yōu)化t和布局，策略PEAP使用相同的服務(wù)器訪問概率，向可行區(qū)域投射，而策略PSPP根據(jù)服務(wù)速率在不同服務(wù)器上分配塊請求。然后，對上述給定的πi,j的值最優(yōu)地求出t的值。

圖2 加權(quán)延遲尾概率

根據(jù)圖2所示實(shí)驗(yàn)結(jié)果，本文提出的聯(lián)合優(yōu)化π、t和S的算法比選取的簡單的對比啟發(fā)式算法可提供顯著的性能改進(jìn)，實(shí)驗(yàn)結(jié)果顯示本文算法的加權(quán)延遲尾概率降低了幾個數(shù)量級。例如，所提算法策略將99%的加權(quán)延遲從對比策略中的160 s以上減少到大約20 s。

實(shí)驗(yàn)2（到達(dá)率影響）接下來將模擬不同的請求到達(dá)率對加權(quán)延遲尾概率的影響，選擇x=50 s。對于λ作為基本到達(dá)率，將所有文件的到達(dá)率從0.2λ增加到1.4λ，并在圖3中繪制加權(quán)延遲尾概率。

圖3 不同文件到達(dá)率的加權(quán)延遲尾概率

根據(jù)圖3結(jié)果可知，當(dāng)延遲尾概率隨著到達(dá)率的增加而增加時，所提算法為不同的文件分配不同的延遲以保持低加權(quán)延遲尾概率。實(shí)驗(yàn)結(jié)果顯示，所提出的算法優(yōu)于選取的對比實(shí)驗(yàn)策略。由于在高到達(dá)率下加權(quán)延遲尾概率更為顯著，因此觀察到在圖3中PEAP和本文算法策略之間，在最高到達(dá)率下延遲尾概率顯著提高了約9倍（約0.025到約0.22）。所提策略總是得到最小的延遲。因此，有效地降低高到達(dá)率文件的延遲可以降低總加權(quán)延遲尾概率。

實(shí)驗(yàn)3（文件數(shù)量影響）圖4給出將文件數(shù)量從200變?yōu)? 200對加權(quán)延遲尾概率的影響。加權(quán)延遲尾概率隨著文件數(shù)量的增加而增加，這會帶來更多的工作負(fù)載（即更高的到達(dá)率）。所提優(yōu)化算法對新文件和現(xiàn)有文件進(jìn)行優(yōu)化，以將總的加權(quán)延遲尾概率保持在一個較低的水平?？梢娝岢龅膬?yōu)化策略有效地降低了尾部概率，并且優(yōu)于所選取的對比算法策略。因此，對所有三個變量π、t和S進(jìn)行聯(lián)合優(yōu)化有助于顯著降低尾部概率。

圖4 不同文件數(shù)的加權(quán)延遲尾概率

實(shí)驗(yàn)4（文件大小影響）實(shí)驗(yàn)?zāi)M中，將文件大小從200 MB更改為700 MB，并在圖5中用不同的文件大小繪制最佳加權(quán)延遲尾概率。為了獲得與默認(rèn)大小200 MB相比文件大小增加的影響，將參數(shù)α和β的值與移動指數(shù)服務(wù)時間分布中的塊大小成比例地增加。隨著文件大小的增加，文件的加權(quán)尾延遲概率增加，所提算法與對比策略進(jìn)行了比較，驗(yàn)證了所提優(yōu)化算法可以顯著降低尾延遲。

圖5 不同文件大小的加權(quán)延遲尾概率

實(shí)驗(yàn)5（浪潮云Inspur實(shí)驗(yàn)）選取浪潮云Inspur實(shí)驗(yàn)平臺進(jìn)行算法性能測試，選取的實(shí)驗(yàn)指標(biāo)為算法云存儲冗余度，對比算法仍然選取上述算法，實(shí)驗(yàn)參數(shù)設(shè)置同上。出冗余度（RSR）是考慮異構(gòu)存儲系統(tǒng)冗余節(jié)省，在保證數(shù)據(jù)可用性d?的RSR指標(biāo)定義為：

式中，rhomo和rheter分別為同質(zhì)系統(tǒng)和異構(gòu)系統(tǒng)，實(shí)驗(yàn)對比結(jié)果見表2所示。

表2 浪潮云Inspur實(shí)驗(yàn)結(jié)果對比

根據(jù)表2實(shí)驗(yàn)結(jié)果，在設(shè)定相同的數(shù)據(jù)可用性指標(biāo)下，所提算法具有的數(shù)據(jù)冗余度指標(biāo)實(shí)驗(yàn)結(jié)果最低，表明所提算法具有更高的計(jì)算效率。同時，隨著數(shù)據(jù)可用性d?的增加，浪潮云Inspur實(shí)驗(yàn)結(jié)果的RSR指標(biāo)逐漸增大，這表明數(shù)據(jù)可用性對于冗余度指標(biāo)，具有直接的影響。

4 結(jié)束語

本文的主要貢獻(xiàn)概括如下：（1）提出一個分析框架，用于量化和馴服云存儲（TTLoC）上的尾延遲、任意擦除編碼存儲系統(tǒng)和服務(wù)時間分布。（2）當(dāng)數(shù)據(jù)塊傳輸時間服從移動指數(shù)分布時，提出一種加權(quán)延遲尾概率優(yōu)化方法，通過在數(shù)據(jù)塊放置、輔助變量和調(diào)度策略三個維度上對系統(tǒng)進(jìn)行優(yōu)化，同時最小化所有文件的尾延遲。（3）提出了一個分析框架來量化任意擦除編碼存儲系統(tǒng)的服務(wù)延遲尾指數(shù)。（4）提出了一種交替優(yōu)化算法，它收斂于尾延遲優(yōu)化的最優(yōu)解。下一步，計(jì)劃在真實(shí)云環(huán)境中開發(fā)數(shù)據(jù)云存儲系統(tǒng)平臺，驗(yàn)證所提方法相對于所考慮的基線的優(yōu)越性。