面向電耗與網(wǎng)絡同步代價優(yōu)化的數(shù)據(jù)副本放置研究

樊玉琦,張 蓓,王倫飛

(合肥工業(yè)大學 計算機與信息學院,合肥 230601)

0 概述

為滿足數(shù)據(jù)密集型應用的需求,數(shù)據(jù)中心需要存儲大規(guī)模數(shù)據(jù)和來自數(shù)億終端用戶的大量數(shù)據(jù)訪問請求[1-2]。應用程序?qū)⒂脩舻脑L問請求指派到一組不同地理位置的數(shù)據(jù)中心以提供服務,這些數(shù)據(jù)中心通常由網(wǎng)絡連接。對于多數(shù)應用程序而言,延遲是一個重要的性能指標[3]。高用戶訪問延遲已被證明具有負面的經(jīng)濟效應,用戶和應用程序都需要較低的網(wǎng)絡延遲。與數(shù)據(jù)中心的排隊延遲或處理延遲相比,對于數(shù)據(jù)密集型應用程序,端到端的網(wǎng)絡延遲更加能夠反映用戶的感知延遲[4-5]。

為滿足用戶延遲需求并實現(xiàn)數(shù)據(jù)的可用性和可靠性,云服務提供商通常將一個數(shù)據(jù)的多個副本同時放置在多個數(shù)據(jù)中心。如果其中一個副本被修改或者更新,則需要通過數(shù)據(jù)中心間的網(wǎng)絡來同步放置在不同數(shù)據(jù)中心的多個數(shù)據(jù)副本。放置在數(shù)據(jù)中心的這些數(shù)據(jù)副本會消耗云資源,包括數(shù)據(jù)中心中存儲數(shù)據(jù)的服務器和不同數(shù)據(jù)中心之間的網(wǎng)絡帶寬[6-8]。因此,數(shù)據(jù)放置到數(shù)據(jù)中心會產(chǎn)生數(shù)據(jù)放置代價,包括數(shù)據(jù)中心服務器所需的電耗代價和數(shù)據(jù)中心之間數(shù)據(jù)傳輸?shù)木W(wǎng)絡通信代價。

用戶通常從距離自己最近的數(shù)據(jù)中心訪問數(shù)據(jù),因此,為使用戶得到更好的訪問延遲性能,應盡可能將數(shù)據(jù)放置到多個數(shù)據(jù)中心。然而,多數(shù)據(jù)副本增加了數(shù)據(jù)放置代價,因此,假設每個數(shù)據(jù)具有有限的副本數(shù),不同的數(shù)據(jù)副本存儲位置對數(shù)據(jù)中心的電耗、數(shù)據(jù)中心間的網(wǎng)絡傳輸和用戶訪問延遲具有不同的影響。云服務提供商需要選擇合適的數(shù)據(jù)中心來放置數(shù)據(jù)副本,以最小化放置代價。

本文假設每個數(shù)據(jù)具有相同的副本數(shù),在滿足用戶延遲需求的同時,以最小化電耗代價和網(wǎng)絡傳輸?shù)耐酱鷥r為目標,研究云數(shù)據(jù)中心多副本數(shù)據(jù)的放置問題,提出一種基于數(shù)據(jù)組劃分和數(shù)據(jù)中心劃分的數(shù)據(jù)放置算法DDDP。將數(shù)據(jù)進行分組,并按用戶訪問數(shù)據(jù)的延遲要求將數(shù)據(jù)中心劃分成數(shù)據(jù)中心子集,為每個數(shù)據(jù)選擇滿足延遲要求且能最小化放置代價的數(shù)據(jù)中心子集,以降低數(shù)據(jù)中心存儲數(shù)據(jù)所引起的電耗和網(wǎng)絡傳輸代價。

1 相關工作

近年來,有學者研究數(shù)據(jù)放置時的用戶訪問延遲、數(shù)據(jù)中心電耗、網(wǎng)絡傳輸代價以及同步代價問題。其中,一些研究關注數(shù)據(jù)放置對用戶訪問延遲的影響。文獻[9]研究了將數(shù)據(jù)對象分配給多個存儲設備的問題,其目的是最小化訪問所有對象的每個請求產(chǎn)生的總處理延遲。文獻[10]在滿足數(shù)據(jù)中心處理延遲要求的同時,最小化數(shù)據(jù)放置代價,并使用混合整數(shù)線性規(guī)劃(MILP)來確定數(shù)據(jù)放置結果。

部分學者通過綜合考慮數(shù)據(jù)中心的電耗和用戶訪問延遲來改善系統(tǒng)性能。文獻[5]利用不同時間和空間的碳足跡變化,綜合考慮電耗代價、服務水平協(xié)議(SLA)要求和碳排放減排預算。文獻[11]提出了一種包含電價和動態(tài)用戶請求率的自適應數(shù)據(jù)放置代價優(yōu)化框架,并設計了一種近似算法,以最大限度地增加用戶被接受的請求數(shù)量,該算法不僅考慮了請求均衡分配,而且滿足了用戶和云服務提供商之間的各種SLA,即響應用戶請求的最大延遲。文獻[12]提出了一種多數(shù)據(jù)中心系統(tǒng)電耗最小化的請求路由方案。針對多區(qū)域電力市場,文獻[13]對文獻[12]方案進行了改進,以更好地捕捉波動的電價,從而降低了電力代價。

另有一些學者關注數(shù)據(jù)放置的網(wǎng)絡傳輸代價以及同步代價優(yōu)化問題。文獻[14]提出了一種計算數(shù)據(jù)放置策略以最小化網(wǎng)絡通信成本,并將數(shù)據(jù)放置問題規(guī)約到經(jīng)典的圖劃分問題。文獻[6]提出了一種根據(jù)社交網(wǎng)絡用戶的社交關系劃分社區(qū)的方法,用于社交網(wǎng)絡用戶數(shù)據(jù)的放置,其綜合考慮數(shù)據(jù)中心的能耗和數(shù)據(jù)同步,目的是最小化數(shù)據(jù)中心的能耗代價和網(wǎng)絡同步代價。

從上述研究可以看出,用戶訪問延遲、數(shù)據(jù)中心電耗和網(wǎng)絡傳輸?shù)耐酱鷥r均對數(shù)據(jù)放置結果產(chǎn)生影響。但是,在將數(shù)據(jù)放置到不同地理位置分布的數(shù)據(jù)中心時,多數(shù)現(xiàn)有解決方案[1,6,9]沒有同時考慮用戶與數(shù)據(jù)中心之間的端到端延遲、電耗代價和網(wǎng)絡同步代價這3個因素。

2 問題描述

設一個分布式云數(shù)據(jù)中心由N個不同地域分布的數(shù)據(jù)中心組成,數(shù)據(jù)中心通過網(wǎng)絡進行互連。假設每個數(shù)據(jù)中心存儲容量有限,且數(shù)據(jù)中心中的服務器同構。將時間段劃分為多個時隙,令Q(t)為時隙t的用戶請求集合,每個請求由(ri,m(t),wi,m(t))表示,其中,ri,m(t)、wi,m(t)分別表示用戶i在時隙t訪問數(shù)據(jù)m的讀、寫率。為使放置的數(shù)據(jù)具有高可用性和可靠性,假設每個數(shù)據(jù)放置K個副本,且副本分布在不同的數(shù)據(jù)中心,數(shù)據(jù)放置的位置應該滿足用戶訪問數(shù)據(jù)的延遲需求。為不失一般性,如果用戶的寫請求更新其中一個數(shù)據(jù)副本,則該數(shù)據(jù)的其他副本也需更新。假設數(shù)據(jù)副本之間保持弱一致性,即副本之間不一定總是保持一致,但最終會實現(xiàn)一致。無論讀或?qū)?數(shù)據(jù)的放置都會引起服務器的電耗代價。此外,用戶的寫請求還會引發(fā)數(shù)據(jù)副本更新所需的數(shù)據(jù)中心間的網(wǎng)絡通信代價。

2.1 服務器電耗代價模型

服務提供商需要在數(shù)據(jù)中心中部署大量服務器以提供數(shù)據(jù)存儲服務,從而導致了數(shù)據(jù)中心的巨大電耗。數(shù)據(jù)中心中運行速率為μ的服務器的電耗可以由aμρ+b來估算[5],其中,a、b分別是與服務器巔峰負載狀態(tài)電耗和空閑狀態(tài)電耗有關的因子,ρ(ρ≥1)是由經(jīng)驗值確定的參數(shù)。數(shù)據(jù)中心j在時隙t開啟的服務器數(shù)量為:

(1)

這些服務器的實際服務率為:

(2)

(3)

2.2 網(wǎng)絡傳輸代價模型

當用戶i對數(shù)據(jù)進行寫或更新時,數(shù)據(jù)中心之間的數(shù)據(jù)同步將引起網(wǎng)絡通信代價。當其中一個數(shù)據(jù)副本被更新時,其他副本也需被更新,以保持多副本之間的數(shù)據(jù)一致性。更新數(shù)據(jù)傳播路徑采用組播樹進行數(shù)據(jù)同步,使更新的數(shù)據(jù)量在每個所需的網(wǎng)絡鏈路上只傳輸一次。所有數(shù)據(jù)的網(wǎng)絡通信代價為:

(4)

2.3 數(shù)據(jù)訪問延遲模型

用戶通常將請求發(fā)送到附近的數(shù)據(jù)中心,以獲得較低的訪問延遲。每個用戶對不同數(shù)據(jù)可能具有不同的SLA需求,對于相同的數(shù)據(jù),不同用戶也具有不同的SLA需求。假設Lq表示用戶對數(shù)據(jù)的訪問延遲需求等級,其中,L1

(5)

其中,di,j為用戶i到數(shù)據(jù)中心j之間的端到端延遲。

2.4 數(shù)據(jù)放置模型

在SLA延遲需求和數(shù)據(jù)中心存儲容量約束下,將每個數(shù)據(jù)的K個副本放置在不同的數(shù)據(jù)中心中,以最小化由數(shù)據(jù)中心服務器電耗和數(shù)據(jù)中心之間網(wǎng)絡通信代價構成的數(shù)據(jù)放置代價。對于時隙t,假設K≤N,數(shù)據(jù)放置問題可以表示為如下模型:

MinΨe(t)+Ψw(t)

(6)

s.t.

(7)

(8)

xi,m,j≤ym,j,?i,m,j

(9)

(10)

(11)

xi,m,j,ym,j∈{0,1},?i,m,j

(12)

式(7)表示存儲在數(shù)據(jù)中心中的數(shù)據(jù)總大小不能超過數(shù)據(jù)中心的存儲容量。式(8)確保用戶與數(shù)據(jù)中心之間的訪問延遲不能超過SLA需求。式(9)表明用戶訪問數(shù)據(jù)的數(shù)據(jù)中心時必須存儲該數(shù)據(jù)的一個副本。式(10)要求每個數(shù)據(jù)放置在不同的K個數(shù)據(jù)中心。式(11)確保每個用戶對每個數(shù)據(jù)的訪問請求分配給唯一的一個數(shù)據(jù)中心。式(12)表示用戶、數(shù)據(jù)和數(shù)據(jù)中心之間的映射關系由二進制變量表示。

3 基于分組與中心子集劃分的數(shù)據(jù)放置算法

針對大規(guī)模數(shù)據(jù)的放置問題,本文提出一種基于數(shù)據(jù)分組和數(shù)據(jù)中心子集劃分的數(shù)據(jù)放置算法DDDP,該算法同時考慮用戶訪問延遲、數(shù)據(jù)中心服務器電耗和網(wǎng)絡傳輸代價等因素。DDDP算法由3個階段組成:

1)根據(jù)數(shù)據(jù)讀寫率將數(shù)據(jù)集D劃分為多個數(shù)據(jù)分組,將具有相似讀寫率的數(shù)據(jù)放入同一組中。

2)讀寫率高的數(shù)據(jù)會導致高放置代價,因此,將多個數(shù)據(jù)分組按讀寫率的非升序進行排序,優(yōu)先放置讀寫率高的數(shù)據(jù)分組中的數(shù)據(jù)。

3)根據(jù)用戶訪問某數(shù)據(jù)的延遲要求將數(shù)據(jù)劃分成由K個數(shù)據(jù)中心組成的數(shù)據(jù)中心子集,以滿足訪問該數(shù)據(jù)的所有用戶的SLA延遲需求。

DDDP算法以迭代的方式進行運行,在每次迭代中,放置某數(shù)據(jù)組中的一個數(shù)據(jù)到一個數(shù)據(jù)中心子集中,數(shù)據(jù)的放置應能最小化數(shù)據(jù)放置代價,上述迭代過程一直持續(xù)到所有數(shù)據(jù)被放置結束。

3.1 數(shù)據(jù)組劃分

本文根據(jù)數(shù)據(jù)讀寫率的相似度來進行數(shù)據(jù)分組。讀請求會產(chǎn)生數(shù)據(jù)中心的電耗代價,而寫請求不僅產(chǎn)生電耗代價,還產(chǎn)生用于數(shù)據(jù)副本同步的網(wǎng)絡通信代價。具有相似讀寫率的數(shù)據(jù)會產(chǎn)生相似的放置代價,從而使數(shù)據(jù)放置結果相同。因此,本文將數(shù)據(jù)集劃分為多個數(shù)據(jù)分組,使得每組數(shù)據(jù)的訪問率相似。在確定數(shù)據(jù)分組時,可以通過比較待分組的數(shù)據(jù)的讀寫率與數(shù)據(jù)分組中的平均讀寫率是否相似,以判斷待分組數(shù)據(jù)是否放入到該數(shù)據(jù)分組中。

假設數(shù)據(jù)A、B的讀寫率分別為dA=(r1,w1)、dB=(r2、w2),計算2個數(shù)據(jù)項的曼哈頓距離DdistM(A,B)來定義數(shù)據(jù)A和B之間的相似性,即DdistM(A,B)=|r1-r2|+|w1-w2|。曼哈頓距離越小,數(shù)據(jù)之間的相似性就越高。值得注意的是,如果讀和寫的請求量相同,寫請求對放置代價的影響要大于讀請求。因此,為讀請求和寫請求分別分配權重α和β,其中,0<α<β。用加權曼哈頓距離來表示數(shù)據(jù)之間的相似性,即數(shù)據(jù)m和組g的相似度L(m,g)為:

(13)

假設相似性閾值Δ>0,從數(shù)據(jù)集D中隨機選取一個數(shù)據(jù)作為初始數(shù)據(jù)組g,對于每一個剩余數(shù)據(jù)m,計算該數(shù)據(jù)與數(shù)據(jù)組g之間的相似度L(m,g),并從所有數(shù)據(jù)組中找出使L(m,g)最小的一個數(shù)據(jù)分組,記為g*。如果L(m,g)<Δ,則將數(shù)據(jù)m添加到組g*中;否則,數(shù)據(jù)m不屬于任何已有數(shù)據(jù)分組,而是單獨生成一個數(shù)據(jù)分組。

3.2 數(shù)據(jù)中心子集劃分

每個數(shù)據(jù)都需要放置到K個數(shù)據(jù)中心,這K個數(shù)據(jù)中心構成一個數(shù)據(jù)中心子集。對于一個數(shù)據(jù)中心子集,如果數(shù)據(jù)m放置在該子集的數(shù)據(jù)中心中導致部分用戶的訪問延遲需求SLA不能被滿足,則數(shù)據(jù)m不能放置在該數(shù)據(jù)中心子集中,即該數(shù)據(jù)中心子集不能作為數(shù)據(jù)m放置的候選位置。反之,如果數(shù)據(jù)m放置在該子集的數(shù)據(jù)中心中時,所有訪問數(shù)據(jù)m的用戶訪問延遲需求都能被滿足,則該數(shù)據(jù)中心子集中的數(shù)據(jù)中心是數(shù)據(jù)m的一個候選位置。

(14)

利用貪婪策略選擇一個θj值最大的數(shù)據(jù)中心j,然后從U中移除其服務的用戶,并在選定數(shù)據(jù)中心j的基礎上,考慮網(wǎng)絡傳輸代價,計算余下數(shù)據(jù)中心的權重,隨后選擇下一個數(shù)據(jù)中心直至找到K個數(shù)據(jù)中心。用圖1示例表示上述過程,其中,黑點表示用戶,圓角框表示5個數(shù)據(jù)中心的用戶集合U′j。假設用戶數(shù)為14,每個數(shù)據(jù)中心的權重分別為1、2、2、2、1。對于所有的數(shù)據(jù)中心,用向量V表示每一個數(shù)據(jù)中心的用戶集合在每個階段包含的單位權重未被服務的用戶數(shù)θj,如果數(shù)據(jù)中心子集大小為3,則最佳解為數(shù)據(jù)中心1、2、5,總代價為4。數(shù)據(jù)中心子集劃分過程如下:選擇數(shù)據(jù)中心1,原因是數(shù)據(jù)中心1的θ在V={7/1,7/2,8/2,4/2,2/1}時最大;選擇數(shù)據(jù)中心2,原因是數(shù)據(jù)中心2的θ在V={·,7/2,4/2,2/2,1/1}時最大;最后,選擇數(shù)據(jù)中心5,原因是數(shù)據(jù)中心1、2可以服務所有用戶,在選擇第3個數(shù)據(jù)中心時,只需要在V={·,·,0/2,0/2,0/1}中選擇θ分母最小的數(shù)據(jù)中心。

圖1 數(shù)據(jù)中心子集劃分過程

3.3 數(shù)據(jù)放置算法DDDP

DDDP算法的偽代碼描述如算法1所示。

算法1多副本數(shù)據(jù)放置算法DDDP

輸入數(shù)據(jù)集D,數(shù)據(jù)中心集合DC,用戶集U

輸出數(shù)據(jù)放置方案ym,j

1.將數(shù)據(jù)集D劃分為數(shù)據(jù)分組;

2.根據(jù)數(shù)據(jù)組的平均讀寫率進行數(shù)據(jù)組排序;

3.對每一個數(shù)據(jù)分組g

4.將數(shù)據(jù)組中的數(shù)據(jù)按s(m)大小進行非降序排列;

5.對每一個數(shù)據(jù)m∈g

7.更新子集中每個數(shù)據(jù)中心的存儲容量;

8.ym,j=TRUE;

9.返回ym,j;

為了在延遲和容量約束下將不同數(shù)據(jù)組的數(shù)據(jù)放置到數(shù)據(jù)中心,本文提出了一種數(shù)據(jù)組排序方法,該方法綜合考慮讀寫請求對放置代價的影響。每個數(shù)據(jù)組g有一個排序值Ω(g),由如下公式確定:

(15)

DDDP算法將數(shù)據(jù)組按Ω(g)值進行非升序排序,原因是寫率高的數(shù)據(jù)產(chǎn)生的放置代價大,因此將高Ω(g)的數(shù)據(jù)組中的數(shù)據(jù)優(yōu)先放置。在放置數(shù)據(jù)組g中的數(shù)據(jù)到數(shù)據(jù)中心時,考慮最小化數(shù)據(jù)中心的單位存儲容量放置代價,則對于數(shù)據(jù)組g中的數(shù)據(jù)m,按照數(shù)據(jù)大小s(m)的非降順序依次放置到能夠最小化放置代價的數(shù)據(jù)中心子集,并同時滿足所有訪問數(shù)據(jù)m的用戶的延遲需求以及數(shù)據(jù)中心的存儲容量約束。

3.4 算法時間復雜度分析

4 性能評估

4.1 模擬配置

在本文實驗中,分布式云由10個位于不同地理位置的數(shù)據(jù)中心組成,通過網(wǎng)絡鏈路E相互連接[6],這些數(shù)據(jù)中心分布在8個地區(qū)[10]:美國東部(弗吉尼亞州),美國東部(俄亥俄州)(2個數(shù)據(jù)中心),美國西部(北加州),美國西部(俄勒岡州)(2個數(shù)據(jù)中心),加州中部,歐洲西(愛爾蘭),亞洲東南(新加坡),亞洲東北(東京)。使用GT-ITM工具[15]生成30個具有不同拓撲結構的云,其中,任意2個數(shù)據(jù)中心之間有一條概率為0.4的邊。假設對于每個數(shù)據(jù)中心,傳輸1 GB數(shù)據(jù)的代價是[$0.05,$0.12]范圍內(nèi)的隨機值[6]。每個時隙t的持續(xù)時間為10 min[16],延遲需求分為5個級別(q=5),分別為15 ms～19 ms[17]。用戶和數(shù)據(jù)中心的端到端網(wǎng)絡延遲由它們之間的地理距離表示[17]。根據(jù)文獻[6,18],所有用戶對所有數(shù)據(jù)總的讀/寫率的比例約為0.92/0.08。每個用戶的讀寫率在[10,20]范圍內(nèi),每次數(shù)據(jù)寫更新產(chǎn)生256 MB的數(shù)據(jù)量[6]。采用層次分析法(AHP)確定權重α、β,以衡量讀寫請求對放置代價的重要度。根據(jù)文獻[19],最終得到α=0.17,β=0.83。

表1列出每個數(shù)據(jù)中心的重要參數(shù)[4-5]。數(shù)據(jù)中心的能耗使用效率(PUE)在[1.3,1.7]范圍內(nèi)隨機生成,服務器的最大服務率表示每秒處理的平均請求數(shù),其范圍為[20.0,32.5]。式(3)中參數(shù)ρ設置為2,參數(shù)a、b分別在[0.18,0.30]、[100,125]中取值。數(shù)據(jù)中心1 MWh的平均電費p在$10～$30之間,數(shù)據(jù)中心的存儲容量范圍為[50 TB,200 TB]。表2所示為不同大小的數(shù)據(jù)所占的比例。

表1 數(shù)據(jù)中心的重要參數(shù)

表2 不同大小的數(shù)據(jù)所占的比例

式(6)中的目標函數(shù)為非線性,式(7)～式(12)中的約束為線性,xi,m,j、ym,j是二值變量,因此,數(shù)據(jù)放置問題是典型的0-1非線性規(guī)劃問題。為評估DDDP算法的性能,本文采用了一個廣泛應用的基準算法,將整數(shù)變量松弛到連續(xù)約束[9,20],在仿真中稱為NPR,該基準算法由3個階段組成:1)通過將變量值xi,m,j、ym,j松弛到[0,1]范圍內(nèi),將0-1規(guī)劃問題轉化為連續(xù)優(yōu)化模型;2)求解連續(xù)優(yōu)化模型,然后迭代修正最接近1的變量固定為1,用固定變量代入原方程,重復模型求解和變量固定過程,直到解中的所有變量固定為0或1;3)連續(xù)優(yōu)化模型產(chǎn)生的數(shù)據(jù)副本數(shù)可能不是K,則添加或刪除數(shù)據(jù)副本以保證其數(shù)目為K。

4.2 性能評估結果

本節(jié)從數(shù)據(jù)放置總代價、電耗代價和網(wǎng)絡傳輸代價(分別表示為性能1、性能2和性能3)3個方面對算法進行評估和研究。

4.2.1 數(shù)據(jù)量對代價的影響

假設用戶數(shù)為1 000,通過改變數(shù)據(jù)量來對DDDP和NPR算法的性能進行評估。從圖2可以看出,數(shù)據(jù)放置總代價、電耗代價和網(wǎng)絡傳輸代價均隨著數(shù)據(jù)量的增加而增加,原因是隨著數(shù)據(jù)量的增大,需要更多的服務器來容納數(shù)據(jù)訪問請求以及更多的網(wǎng)絡傳輸來進行數(shù)據(jù)同步。在3個性能指標上,DDDP算法的數(shù)據(jù)放置代價(性能1)優(yōu)于NPR算法9.8%～14.9%,DDDP算法的電耗代價(性能2)、網(wǎng)絡傳輸代價(性能3)分別約為NPR算法的8%～23%、7.5%～29%。DDDP算法的代價均優(yōu)于NPR算法,前者將數(shù)據(jù)劃分為多個數(shù)據(jù)組,并對所有數(shù)據(jù)組進行排序,讀寫率高的數(shù)據(jù)優(yōu)先級高,首先放置較高優(yōu)先級的數(shù)據(jù)組的數(shù)據(jù),并依次為數(shù)據(jù)選擇最小化放置代價的數(shù)據(jù)中心子集,這些數(shù)據(jù)中心電耗低,并且數(shù)據(jù)中心之間通過最短路徑傳輸更新數(shù)據(jù),降低了數(shù)據(jù)傳輸?shù)木W(wǎng)絡代價和放置代價。NPR算法松弛了整數(shù)變量約束,并通過變量固定最小化代價,然而,松弛連續(xù)優(yōu)化問題的最優(yōu)解通常差于整數(shù)規(guī)劃問題的最優(yōu)解,而且變量固定過程會導致數(shù)據(jù)副本數(shù)目不為K,因此,為了滿足數(shù)據(jù)副本數(shù)量約束,其需要增加或刪除數(shù)據(jù)中心,這將導致代價增加。

圖2 數(shù)據(jù)量對放置代價的影響

4.2.2 用戶數(shù)對代價的影響

假設數(shù)據(jù)量設置為3 000,研究用戶數(shù)對不同算法性能的影響。從圖3可以看出,當用戶數(shù)從1 000增加到5 000時,算法的數(shù)據(jù)放置總代價、電耗代價和網(wǎng)絡傳輸代價都增加,原因是來自用戶的大量請求需要更多的服務器以及會產(chǎn)生更多的數(shù)據(jù)同步傳輸,從而增加了電耗和網(wǎng)絡通信代價。DDDP算法的性能1、性能2和性能3均優(yōu)于NPR算法。與NPR算法相比,DDDP算法將數(shù)據(jù)按數(shù)據(jù)組的非升序排列,訪問率較高的數(shù)據(jù)優(yōu)先放置。此外,隨著用戶數(shù)的增加,與NPR算法相比,DDDP算法的網(wǎng)絡通信代價(性能3)減少程度要大于電耗代價(性能2),網(wǎng)絡通信代價和電耗代價的減少程度分別如圖4所示。數(shù)據(jù)的訪問率隨著用戶數(shù)的增加而增加,高訪問率的數(shù)據(jù)的訪問率會更高,因此,用戶數(shù)對數(shù)據(jù)分組排序的影響較小。DDDP算法中計算用戶讀寫請求對放置代價的影響權重,當寫請求的數(shù)量隨著用戶數(shù)的增加而增加時,由于寫請求的權重大于讀請求,寫率高的數(shù)據(jù)將放置到較近的數(shù)據(jù)中心,使路由路徑變短,但數(shù)據(jù)中心的電耗可能變高。

圖3 用戶數(shù)對放置代價的影響

圖4 不同用戶數(shù)下DDDP算法的電耗和網(wǎng)絡代價減少量

4.2.3 數(shù)據(jù)副本數(shù)量對代價的影響

本節(jié)研究數(shù)據(jù)副本數(shù)量K對算法放置代價的影響。圖5所示為在不同數(shù)據(jù)量和用戶數(shù)條件下,當K從2增長到5時數(shù)據(jù)副本數(shù)量K對算法性能的影響結果。其中,數(shù)據(jù)量分別為2 000、6 000和10 000,用戶數(shù)分別為1 000、3 000和5 000。

圖5 數(shù)據(jù)副本數(shù)量對放置代價的影響

從圖5可以看出,隨著數(shù)據(jù)副本數(shù)量的增加,DDDP算法和NPR算法的數(shù)據(jù)放置代價都會增加,原因是數(shù)據(jù)副本的增加相當于數(shù)據(jù)量的增加,因此,需要更多的服務器來容納數(shù)據(jù)副本以及更多的網(wǎng)絡傳輸來保持數(shù)據(jù)副本更新的一致性。相比NPR算法,DDDP算法的放置代價較小,當K=3時,DDDP算法的放置代價比NPR算法分別降低約29%和26%。然而,隨著數(shù)據(jù)副本數(shù)量的增加,DDDP算法數(shù)的性能沒有K=3情況下的性能好。原因是,當K較小時,排序值高的數(shù)據(jù)分組中的數(shù)據(jù)副本首先被放置,可以被具有較低電費且網(wǎng)絡傳輸路徑較短的數(shù)據(jù)中心所容納,當K很大時,由于數(shù)據(jù)中心存儲容量約束,隨著數(shù)據(jù)副本數(shù)量的增加,高訪問率的數(shù)據(jù)將被放置到放置代價小的數(shù)據(jù)中心子集,其他數(shù)據(jù)可能被放置到具有較低電價但距離較遠的數(shù)據(jù)中心。

4.2.4 數(shù)據(jù)副本放置對用戶訪問性能的影響

圖6、圖7分別說明在不同數(shù)據(jù)量和用戶數(shù)條件下,當K從2增長到5時數(shù)據(jù)副本數(shù)量K對用戶訪問性能的影響。從圖6可以看出,在用戶數(shù)為1 000,數(shù)據(jù)量分別為2 000、6 000和10 000情況下,訪問延遲需求滿足的百分比基本持平,穩(wěn)定在100%,即DDDP算法產(chǎn)生的數(shù)據(jù)放置策略可以滿足100%的用戶訪問數(shù)據(jù)延遲需求。DDDP算法在為每個數(shù)據(jù)采用貪心策略選擇數(shù)據(jù)中心時,以滿足延遲需求為限制條件,使得選擇的數(shù)據(jù)中心的放置代價最小化,同時滿足所有用戶的延遲需求,從而保證了用戶訪問性能。此外,在用戶數(shù)不變的情況下,隨著數(shù)據(jù)副本的增加,數(shù)據(jù)會被放置到離用戶較近的數(shù)據(jù)中心,從而減小了用戶訪問延遲并滿足用戶的延遲需求。從圖7可以看出,在數(shù)據(jù)量為3 000,用戶數(shù)分別為1 000、3 000和5 000情況下,隨著數(shù)據(jù)副本數(shù)量和用戶數(shù)的增加,訪問延遲需求滿足的百分比保持在100%。隨著數(shù)據(jù)副本的增加,數(shù)據(jù)會被放置到離用戶較近的數(shù)據(jù)中心,用戶通常訪問最近的數(shù)據(jù)中心,從而滿足了其延遲需求。同時,數(shù)據(jù)放置到多個數(shù)據(jù)中心,擴大了用戶的服務范圍,即使用戶數(shù)量增加,數(shù)據(jù)中心也可以在很大程度上滿足其延遲需求。

圖6 不同數(shù)據(jù)量下數(shù)據(jù)副本數(shù)量對用戶訪問性能的影響

圖7 不同用戶數(shù)下數(shù)據(jù)副本數(shù)量對用戶訪問性能的影響

5 結束語

大規(guī)模的數(shù)據(jù)密集型應用程序通過將服務請求指派到位于不同地理位置的數(shù)據(jù)中心，以為終端用戶提供服務。在數(shù)據(jù)中心存儲應用所需的海量數(shù)據(jù)時，常為每個數(shù)據(jù)維護多個副本，從而產(chǎn)生高額的電費和數(shù)據(jù)中心之間的網(wǎng)絡傳輸費用。本文假設每個數(shù)據(jù)都有K個副本，以最小化多副本數(shù)據(jù)放置代價為目標，建立數(shù)據(jù)放置問題模型，并提出一種基于數(shù)據(jù)組和數(shù)據(jù)中心劃分的DDDP算法。仿真結果表明，相對NPR算法，DDDP算法能有效降低數(shù)據(jù)放置代價。在實際應用中,用戶訪問數(shù)據(jù)的讀寫率是動態(tài)變化的,即數(shù)據(jù)放置的最佳位置會發(fā)生變化。因此,下一步將考慮每個時間段的讀寫率變化對數(shù)據(jù)放置的影響,根據(jù)需要來動態(tài)調(diào)整部分數(shù)據(jù)的放置位置,以降低數(shù)據(jù)訪問引起的能耗和網(wǎng)絡傳輸代價。