胡志剛，張欣欣，鄭美光，常成龍，李佳，楊柳

?

虛擬數(shù)據(jù)代理云模型構(gòu)建及數(shù)據(jù)布局

胡志剛，張欣欣，鄭美光，常成龍，李佳，楊柳

(中南大學(xué) 計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙，410083)

綜合考慮數(shù)據(jù)集間的依賴(lài)關(guān)系以及數(shù)據(jù)中心的存儲(chǔ)容量，引入一種名為“虛擬數(shù)據(jù)代理”的新實(shí)體，通過(guò)建立虛擬數(shù)據(jù)代理云模型，將數(shù)據(jù)布局問(wèn)題轉(zhuǎn)換為2個(gè)映射過(guò)程，即從數(shù)據(jù)集到虛擬數(shù)據(jù)代理的映射以及從虛擬數(shù)據(jù)代理到數(shù)據(jù)中心的映射，進(jìn)而提出一種基于虛擬數(shù)據(jù)代理的云模型數(shù)據(jù)布局策略(CDPVDA)。仿真實(shí)驗(yàn)結(jié)果表明：CDPVDA與典型的數(shù)據(jù)放置策略相比，可以將數(shù)據(jù)中心之間的數(shù)據(jù)傳輸開(kāi)銷(xiāo)降低5％~20％。

云模型；數(shù)據(jù)密集型應(yīng)用；虛擬數(shù)據(jù)代理；數(shù)據(jù)布局

數(shù)據(jù)密集型應(yīng)用是一種以數(shù)據(jù)為核心的應(yīng)用模式，其特點(diǎn)是在運(yùn)行過(guò)程中，需要不斷獲取、更新、存儲(chǔ)大量數(shù)據(jù)，并對(duì)這些數(shù)據(jù)進(jìn)行各種計(jì)算[1]。這些應(yīng)用通常需要處理分布在不同數(shù)據(jù)中心的數(shù)據(jù)集[2]，它們都通過(guò)對(duì)海量數(shù)據(jù)進(jìn)行復(fù)雜計(jì)算、分析挖掘與處理從而得出豐富的數(shù)據(jù)，服務(wù)于社會(huì)生活、生產(chǎn)以及科學(xué)研究領(lǐng)域。云計(jì)算是數(shù)據(jù)共享與服務(wù)共享計(jì)算模式的結(jié)合體[3]，為數(shù)據(jù)密集型應(yīng)用提供了一種全新的部署和執(zhí)行方式。在分布式計(jì)算領(lǐng)域，數(shù)據(jù)密集型工作流是科學(xué)研究和工程計(jì)算中最典型的一種任務(wù)類(lèi)型，在執(zhí)行過(guò)程中需要多數(shù)據(jù)中心協(xié)作[4]。當(dāng)前，許多地理上分布的私有云可以對(duì)外提供一部分計(jì)算和存儲(chǔ)資源，可將此類(lèi)私有云看作單獨(dú)的數(shù)據(jù)中心并通過(guò)互聯(lián)網(wǎng)形成更大的云平臺(tái)。該云計(jì)算平臺(tái)允許用戶(hù)執(zhí)行其應(yīng)用，并將所需的數(shù)據(jù)集上傳到平臺(tái)中。對(duì)于規(guī)模龐大的數(shù)據(jù)集，有一部分?jǐn)?shù)據(jù)集需要存放在某一特定的數(shù)據(jù)中心上，加之云平臺(tái)的節(jié)點(diǎn)之間存在帶寬限制，不可能將所有數(shù)據(jù)集上傳到某一個(gè)單獨(dú)的數(shù)據(jù)中心，或者在每個(gè)單獨(dú)數(shù)據(jù)中心存儲(chǔ)所有的數(shù)據(jù)集，而是需要將不同的數(shù)據(jù)集分別上傳到不同數(shù)據(jù)中心，使用戶(hù)數(shù)據(jù)密集型應(yīng)用的多個(gè)子任務(wù)并行執(zhí)行。由于任務(wù)之間存在較強(qiáng)的數(shù)據(jù)依賴(lài)關(guān)系，數(shù)據(jù)密集型在運(yùn)行時(shí)必然會(huì)產(chǎn)生跨多個(gè)數(shù)據(jù)中心的數(shù)據(jù)移動(dòng)任務(wù)，涉及大量的數(shù)據(jù)傳輸、數(shù)據(jù)同步等開(kāi)銷(xiāo)，不合理的數(shù)據(jù)設(shè)置將產(chǎn)生高額成本并嚴(yán)重影響工作流執(zhí)行效率，因此，為云環(huán)境下的數(shù)據(jù)密集型應(yīng)用設(shè)計(jì)合理的數(shù)據(jù)布局方法很有必要。云模型[5]是定性概念和定量論域的不確定性轉(zhuǎn)換工具，本文作者將云模型應(yīng)用于數(shù)據(jù)布局策略中，以解決數(shù)據(jù)布局過(guò)程中的不確定性和隨機(jī)性問(wèn)題。在數(shù)據(jù)布局過(guò)程中充分考慮數(shù)據(jù)密集型應(yīng)用所涉及數(shù)據(jù)集之間的依賴(lài)關(guān)系以及數(shù)據(jù)中心的存儲(chǔ)量，從而減小數(shù)據(jù)密集型應(yīng)用跨多個(gè)數(shù)據(jù)中心的數(shù)據(jù)移動(dòng)以及產(chǎn)生的時(shí)間消耗，提高應(yīng)用執(zhí)行效率和系統(tǒng)性能。本文中云計(jì)算和云模型都涉及“云”，為了將云計(jì)算和云模型區(qū)分開(kāi)來(lái)，云計(jì)算指分布式計(jì)算領(lǐng)域中的節(jié)點(diǎn)或者集群，它是一種計(jì)算范式，而云及云模型等均是不確定性人工智能范疇里云理論中的概念。針對(duì)云環(huán)境下數(shù)據(jù)密集型應(yīng)用的數(shù)據(jù)布局問(wèn)題，研究者進(jìn)行了大量的研究，如YUAN等[6]考慮到數(shù)據(jù)集之間的依賴(lài)關(guān)系，提出了一種結(jié)合K-means算法的數(shù)據(jù)布局方案，為所有數(shù)據(jù)集劃分不同的集合類(lèi)別并為不同的集合分配不同的位置，有效地減少了數(shù)據(jù)集移動(dòng)次數(shù)，但未考慮數(shù)據(jù)塊存放時(shí)，能否使節(jié)點(diǎn)負(fù)載維持在設(shè)定閾值內(nèi)。劉少偉等[7]在科學(xué)工作流建立階段，根據(jù)數(shù)據(jù)依賴(lài)關(guān)系圖將關(guān)系緊密型數(shù)據(jù)集盡可能放置到同一數(shù)據(jù)中心。研究結(jié)果表明，該策略能有效減少跨數(shù)據(jù)中心科學(xué)工作流執(zhí)行時(shí)的數(shù)據(jù)傳輸量。DENG等[8]在YUAN等[6]的基礎(chǔ)上，提出一種數(shù)據(jù)集和任務(wù)的協(xié)同調(diào)度策略。該策略考慮到數(shù)據(jù)集和應(yīng)用任務(wù)之間的依賴(lài)關(guān)系，有效地提高調(diào)度性能，但此方法主要考慮負(fù)載均衡，導(dǎo)致具有高依賴(lài)度的數(shù)據(jù)集可能在不同的數(shù)據(jù)中心上存儲(chǔ)，應(yīng)用任務(wù)在執(zhí)行過(guò)程中可能會(huì)產(chǎn)生大量數(shù)據(jù)集跨數(shù)據(jù)中心的時(shí)間開(kāi)銷(xiāo)。一些研究者考慮到數(shù)據(jù)依賴(lài)關(guān)系，用智能方法對(duì)數(shù)據(jù)布局問(wèn)題進(jìn)行研究，如：張?zhí)鹛鸬萚9]考慮數(shù)據(jù)依賴(lài)特性，設(shè)計(jì)一種融入釋放和重構(gòu)理論的數(shù)據(jù)布局策略，能夠用更少的時(shí)間確定出大規(guī)模范圍內(nèi)的最優(yōu)全局布局方法；PANDEY等[10]則將粒子群算法引入數(shù)據(jù)布局問(wèn)題中，該策略在數(shù)據(jù)中心的負(fù)載均衡、算法收斂方面有很好的效果。但上述方法的時(shí)間復(fù)雜度較高。綜合以上分析可知：人們將云環(huán)境下的數(shù)據(jù)密集型應(yīng)用于數(shù)據(jù)布局，并得到一些有效方法和策略，但有的為了使負(fù)載均衡，而未對(duì)跨數(shù)據(jù)中心數(shù)據(jù)傳輸所導(dǎo)致的時(shí)間開(kāi)銷(xiāo)進(jìn)行針對(duì)性?xún)?yōu)化；有的數(shù)據(jù)布局策略本身時(shí)間開(kāi)銷(xiāo)較大，導(dǎo)致數(shù)據(jù)布局策略靈活性不足；有的沒(méi)有考慮數(shù)據(jù)布局過(guò)程中存在的不確定性和隨機(jī)性。為此，本文作者考慮到云環(huán)境中數(shù)據(jù)中心的存儲(chǔ)容量以及數(shù)據(jù)集之間的數(shù)據(jù)依賴(lài)關(guān)系，提出一種基于云模型的數(shù)據(jù)布局策略，以減少跨數(shù)據(jù)中心傳輸所產(chǎn)生的時(shí)間開(kāi)銷(xiāo)和移動(dòng)次數(shù)。

1 問(wèn)題概念與定義

1.1 數(shù)據(jù)布局相關(guān)概念

1.2 虛擬數(shù)據(jù)代理

數(shù)據(jù)布局為每個(gè)數(shù)據(jù)集在大量數(shù)據(jù)中心中選擇合適的位置，是一個(gè)復(fù)雜的多次擇優(yōu)過(guò)程，并具有不確定性和隨機(jī)性，同時(shí)產(chǎn)生時(shí)間及數(shù)據(jù)移動(dòng)等各類(lèi)開(kāi)銷(xiāo)。云模型[5, 11]是在概率理論和模糊集合理論基礎(chǔ)上重點(diǎn)考慮隨機(jī)性和模糊性的關(guān)聯(lián)性發(fā)展起來(lái)的，是定性知識(shí)描述和定性概念與其定量數(shù)值表示之間的不確定性轉(zhuǎn)換模型，已在智能控制、模糊評(píng)測(cè)、進(jìn)化計(jì)算等多個(gè)領(lǐng)域得到應(yīng)用[11?13]。本文為了解決過(guò)程中的隨機(jī)性和不確定性問(wèn)題，將云模型與數(shù)據(jù)布局策略相結(jié)合。為構(gòu)建融入云模型的數(shù)據(jù)布局策略，在云計(jì)算系統(tǒng)中引入虛擬數(shù)據(jù)代理。

引入虛擬數(shù)據(jù)代理的數(shù)據(jù)布局框架如圖1所示。

將數(shù)據(jù)密集型應(yīng)用中任務(wù)T1~T8分配到合適的虛擬機(jī)VM上，而每個(gè)任務(wù)涉及大量數(shù)據(jù)集，需進(jìn)行科學(xué)計(jì)算和處理，這些數(shù)據(jù)集就是可能來(lái)自不同數(shù)據(jù)中心的數(shù)據(jù)集。數(shù)據(jù)集映射到數(shù)據(jù)中心，需通過(guò)虛擬數(shù)據(jù)代理作為中間件來(lái)輔助完成，根據(jù)數(shù)據(jù)集之間的數(shù)據(jù)特性，虛擬數(shù)據(jù)代理將關(guān)系密切的數(shù)據(jù)集聚簇，1個(gè)虛擬數(shù)據(jù)代理則存儲(chǔ)在1個(gè)數(shù)據(jù)中心中。

圖1 引入虛擬數(shù)據(jù)代理的數(shù)據(jù)布局框架

定義2中的虛擬數(shù)據(jù)代理是1個(gè)存儲(chǔ)在數(shù)據(jù)中心的數(shù)據(jù)集集合，規(guī)定它先由一部分?jǐn)?shù)據(jù)集開(kāi)始，而后根據(jù)隸屬度的計(jì)算不斷加入新的數(shù)據(jù)集，直至全部數(shù)據(jù)集參與運(yùn)算為止。隸屬度是未布局的數(shù)據(jù)集隸屬于某虛擬數(shù)據(jù)代理的判定值，原則上，隸屬度越大，該數(shù)據(jù)集隸屬于虛擬數(shù)據(jù)代理的可能性越高。為找出確立虛擬數(shù)據(jù)代理的數(shù)據(jù)集以及描述高依賴(lài)度的數(shù)據(jù)布局策略，需要對(duì)依賴(lài)關(guān)系等進(jìn)行定義。

2 虛擬數(shù)據(jù)代理云模型及數(shù)據(jù)布局

這里構(gòu)建虛擬數(shù)據(jù)代理云模型，并提出數(shù)據(jù)布局策略。數(shù)據(jù)集布局到數(shù)據(jù)中心包含3個(gè)關(guān)鍵內(nèi)容：首先，利用逆向云發(fā)生器實(shí)現(xiàn)從定量數(shù)值到定性概念的轉(zhuǎn)換，確定虛擬數(shù)據(jù)代理云模型三元組；其次，確定數(shù)據(jù)集與虛擬數(shù)據(jù)代理間映射關(guān)系，利用正向云發(fā)生器，計(jì)算各數(shù)據(jù)集對(duì)各虛擬數(shù)據(jù)代理的隸屬度，實(shí)現(xiàn)數(shù)據(jù)集到虛擬數(shù)據(jù)代理的映射；最后，確定虛擬數(shù)據(jù)代理與數(shù)據(jù)中心的映射關(guān)系，考慮數(shù)據(jù)集與數(shù)據(jù)中心的數(shù)據(jù)請(qǐng)求關(guān)系，實(shí)現(xiàn)虛擬數(shù)據(jù)代理與數(shù)據(jù)中心的映射。

2.1 虛擬數(shù)據(jù)代理云模型計(jì)算

云模型由期望值x、熵n和超熵e這3個(gè)特征參數(shù)來(lái)表征1個(gè)定性概念。云的數(shù)字特征如圖2所示。x為所表征概念的中心值，它最能有效描述1個(gè)定性概念；n綜合反映概念的模糊性和概率，表達(dá)概念云模型的離散程度，在圖2中反映云的跨度；e為熵的熵，表達(dá)概念云模型的偏離程度，在圖2中反映云的厚度。圖2中，橫軸表示某一概念的不確定性度量范圍，縱軸表示隸屬度。隸屬度反映所屬程度，越接近于0，表明所屬程度越低。

圖2 云模型的數(shù)字特征

云模型理論有2種云產(chǎn)生算法即2種云發(fā)生 器[14?15]：正向云發(fā)生器和逆向云發(fā)生器。正向云發(fā)生器是用語(yǔ)言值描述的某個(gè)基本概念與其數(shù)值表示之間的不確定性轉(zhuǎn)換模型，是從定性到定量的映射；逆向云發(fā)生器是某個(gè)基本概念的數(shù)值表示和其語(yǔ)言值描述之間的不確定性轉(zhuǎn)換模型，是從定量到定性的映射。

由數(shù)據(jù)集間不同的依賴(lài)關(guān)系可能得到不同的數(shù)據(jù)布局，而在本文中也會(huì)確立不同特征值的VDA，這反映了數(shù)據(jù)布局的隨機(jī)性。數(shù)據(jù)集隸屬于某個(gè)數(shù)據(jù)中心的可靠程度不同，而本文中數(shù)據(jù)集隸屬于某個(gè)VDA的可靠程度也不同，這種可靠程度反映了數(shù)據(jù)布局的不確定性。

建立虛擬數(shù)據(jù)代理云模型，采用逆向云發(fā)生器生成VDA的3個(gè)特征值，即給出VDA的定性描述。定性概念表達(dá)其所在區(qū)域的整體特征，為了盡可能準(zhǔn)確地表達(dá)1個(gè)定性概念，需要一定數(shù)量的數(shù)值特征，即提取一定數(shù)量的“云滴”構(gòu)成“云滴組”。為獲得1個(gè)高質(zhì)量的VDA，利用數(shù)據(jù)密集型應(yīng)用中數(shù)據(jù)集間的依賴(lài)性，找出作為“云滴組”的數(shù)據(jù)集來(lái)共同表達(dá)定性概念VDA。云滴組形成的云即表達(dá)1個(gè)虛擬數(shù)據(jù)代理。

利用逆向云發(fā)生器來(lái)確立虛擬數(shù)據(jù)代理云模型三元組，原則為優(yōu)先選取具有高依賴(lài)度的數(shù)據(jù)集組成“云滴組”。為獲得1個(gè)高質(zhì)量的VDA，利用數(shù)據(jù)密集型應(yīng)用中數(shù)據(jù)集間的依賴(lài)性，找出作為“云滴組”的數(shù)據(jù)集來(lái)共同表達(dá)定性概念VDA，云滴組形成的云即表達(dá)1個(gè)虛擬數(shù)據(jù)代理。本文隨機(jī)選出個(gè)沒(méi)有依賴(lài)關(guān)系或依賴(lài)關(guān)系非常小的數(shù)據(jù)集作為個(gè)“云滴組”的初始數(shù)據(jù)集，并利用定義5的依賴(lài)度閾值分別為每個(gè)初始數(shù)據(jù)集找到一定數(shù)量的相關(guān)數(shù)據(jù)集增至各個(gè)云滴組中，構(gòu)造出組“云滴組”。

為每個(gè)初始數(shù)據(jù)集找到的相關(guān)數(shù)據(jù)集個(gè)數(shù)可能不同，在特征值計(jì)算公式(式(2))中將每個(gè)云滴組的數(shù)據(jù)集數(shù)量統(tǒng)稱(chēng)為。利用逆向云發(fā)生器實(shí)現(xiàn)從依照數(shù)據(jù)特性選定的數(shù)據(jù)集到定性概念的轉(zhuǎn)換，確立出個(gè)虛擬數(shù)據(jù)代理，“云滴組”數(shù)據(jù)集則存儲(chǔ)在相應(yīng)的虛擬數(shù)據(jù)代理中。對(duì)于每個(gè)虛擬數(shù)據(jù)代理，按下式計(jì)算期望值x、熵n和超熵e：

以20個(gè)數(shù)據(jù)集和3個(gè)數(shù)據(jù)中心(即=3)為例，對(duì)上述過(guò)程進(jìn)行解釋。數(shù)據(jù)集的初始隨機(jī)位置P和數(shù)據(jù)集之間的依賴(lài)關(guān)系如表1所示。將隨機(jī)抽取出的3個(gè)數(shù)據(jù)集3，6和11分別作為3個(gè)云滴組的初始數(shù)據(jù)集，依賴(lài)度閾值設(shè)為3。對(duì)于初始數(shù)據(jù)集a，表1中與其滿(mǎn)足高依賴(lài)度的數(shù)據(jù)集為4，將3和4這2個(gè)數(shù)據(jù)集視為一組“云滴組”，由式(2)得出期望值x=2.250，熵n=0.453，超熵e=0.237，即生成3所對(duì)應(yīng)的虛擬數(shù)據(jù)代理的3個(gè)特征值= (2.25,0.453,0.237)。同理，得出6所對(duì)應(yīng)的虛擬數(shù)據(jù)代理的特征值= (1.45,0.168,0.052)，11所對(duì)應(yīng)的虛擬數(shù)據(jù)代理的特征值=(2.69,0.422,0.276)。

表1 數(shù)據(jù)集初始位置及依賴(lài)關(guān)系

2.2 數(shù)據(jù)集到虛擬數(shù)據(jù)代理的映射

初始虛擬數(shù)據(jù)代理云模型確立后，使用正向云發(fā)生器，計(jì)算數(shù)據(jù)集對(duì)虛擬數(shù)據(jù)代理的隸屬度，從而實(shí)現(xiàn)數(shù)據(jù)集到虛擬數(shù)據(jù)代理的映射。需要說(shuō)明的是：構(gòu)成“云滴組”的數(shù)據(jù)集默認(rèn)存儲(chǔ)在當(dāng)前虛擬數(shù)據(jù)代理中，不再參與隸屬度計(jì)算。正向云發(fā)生器輸入云的數(shù)字特征(期望值x、熵n和超熵e)以及需要生成的云滴數(shù)，輸出每個(gè)云滴對(duì)虛擬數(shù)據(jù)代理的隸屬度。

為避免云模型生成過(guò)程中虛擬數(shù)據(jù)代理的數(shù)據(jù)集數(shù)差異過(guò)大，使各VDA云模型負(fù)載均衡，并考慮到數(shù)據(jù)中心的剩余存儲(chǔ)問(wèn)題，采取如下策略：當(dāng)1個(gè)數(shù)據(jù)集相對(duì)幾個(gè)不同的虛擬數(shù)據(jù)代理具有相同的隸屬度時(shí)，將該數(shù)據(jù)集分配到剩余存儲(chǔ)量最大的虛擬數(shù)據(jù)中 代理。

將2.1節(jié)中20個(gè)數(shù)據(jù)集布局到3個(gè)虛擬數(shù)據(jù)代理中，結(jié)果如表2所示。

2.3 虛擬數(shù)據(jù)代理到數(shù)據(jù)中心的映射

表2 數(shù)據(jù)集到虛擬數(shù)據(jù)代理的映射

每個(gè)虛擬數(shù)據(jù)代理最終與1個(gè)數(shù)據(jù)中心一一映射。本文依據(jù)數(shù)據(jù)集和數(shù)據(jù)中心的數(shù)據(jù)請(qǐng)求關(guān)系來(lái)實(shí)現(xiàn)VDA與數(shù)據(jù)中心之間的映射。數(shù)據(jù)中心會(huì)發(fā)出數(shù)據(jù)請(qǐng)求，數(shù)據(jù)請(qǐng)求取決于當(dāng)前任務(wù)的數(shù)據(jù)集需求，使得數(shù)據(jù)集具有一定的先后順序參與數(shù)據(jù)密集型應(yīng)用的運(yùn)算。1個(gè)數(shù)據(jù)請(qǐng)求可能需要多個(gè)數(shù)據(jù)集，同一數(shù)據(jù)集也可能被多個(gè)請(qǐng)求處理。在數(shù)據(jù)請(qǐng)求中，對(duì)單一數(shù)據(jù)集的1次請(qǐng)求記為1，數(shù)據(jù)中心與個(gè)數(shù)據(jù)集的請(qǐng)求關(guān)系可采用×的矩陣表述如下：

參數(shù)c1c1c2cm d1Y11Y21Y31Ym1 d2Y12Y22Y32Ym2 d3Y13Y23Y33Ym3 dnY1nY2nY3nYmn

其中：行向量對(duì)應(yīng)數(shù)據(jù)中心，列向量對(duì)應(yīng)數(shù)據(jù)集。依據(jù)隸屬度計(jì)算，2.2節(jié)已完成數(shù)據(jù)集到VDA的映射，各VDA中都包含一組數(shù)據(jù)集子集。對(duì)每個(gè)VDA，計(jì)算各數(shù)據(jù)中心對(duì)其中所有數(shù)據(jù)集的總請(qǐng)求次數(shù)?？傉?qǐng)求次數(shù)最大值對(duì)應(yīng)的數(shù)據(jù)中心即為虛擬數(shù)據(jù)代理將存放的數(shù)據(jù)中心?？傉?qǐng)求次數(shù)計(jì)算如下：

同樣采用2.1節(jié)中的實(shí)例。對(duì)于虛擬數(shù)據(jù)代理=(1.45,0.168,0.052)，其被2請(qǐng)求次數(shù)最多，因此，將被存儲(chǔ)在數(shù)據(jù)中心2上。為記錄方便，設(shè)VDA的編號(hào)與其所屬的數(shù)據(jù)中心編號(hào)一致。同理，得到3個(gè)虛擬數(shù)據(jù)代理與數(shù)據(jù)中心1，2和3，根據(jù)總請(qǐng)求次數(shù)所得映射結(jié)果如表3所示。

表3 映射結(jié)果

2.4 基于虛擬數(shù)據(jù)代理的云模型數(shù)據(jù)布局策略

基于虛擬數(shù)據(jù)代理的云模型數(shù)據(jù)布局策略(CDPVDA)如下。

輸入：個(gè)隨機(jī)數(shù)據(jù)集

輸出：數(shù)據(jù)布局結(jié)果

Begin

步驟1：FOR(=0;＜;++) DO

找出與輸入數(shù)據(jù)集之間有高依賴(lài)關(guān)系的數(shù)據(jù)集；

步驟2：FOR (=0;＜;++) DO

計(jì)算式(2) AND

生成3個(gè)數(shù)字特征(x，n，e)，記錄生成云滴的個(gè)數(shù)；

計(jì)算公式(3) AND

個(gè)云滴及其確定度()；

步驟4：FOR (=0;＜;++) DO

d放置于對(duì)應(yīng)max(())的虛擬數(shù)據(jù)代理；

步驟5：FOR (=0;＜;++) DO

找出每個(gè)數(shù)據(jù)中心總請(qǐng)求次數(shù)最高的虛擬數(shù)據(jù)代理 AND虛擬數(shù)據(jù)代理映射到數(shù)據(jù)中心；

End

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

3.1 實(shí)驗(yàn)環(huán)境

為驗(yàn)證CDPVDA算法的性能，選用墨爾本大學(xué)網(wǎng)格實(shí)驗(yàn)室的CloudSim云計(jì)算仿真平臺(tái)[16]進(jìn)行實(shí)驗(yàn)。數(shù)據(jù)密集型工作流應(yīng)用分別通過(guò)模擬設(shè)置和實(shí)際工作流應(yīng)用這2種方式產(chǎn)生。

本文開(kāi)發(fā)了數(shù)據(jù)密集型應(yīng)用(data-intensive application, DIA)集成測(cè)試平臺(tái)，自動(dòng)化定制生成數(shù)據(jù)密集型應(yīng)用，驗(yàn)證數(shù)據(jù)密集型應(yīng)用是否滿(mǎn)足數(shù)據(jù)密集型特征，以及在驗(yàn)證數(shù)據(jù)密集型應(yīng)用滿(mǎn)足數(shù)據(jù)密集型特征后，存儲(chǔ)所生成的數(shù)據(jù)密集型應(yīng)用。平臺(tái)基于IOZone[17]中3個(gè)核心原子操作(R, W, RW)自動(dòng)定制生成一種典型數(shù)據(jù)密集型應(yīng)用IOZones，用戶(hù)可輸入IOZones的主要參數(shù)(最大節(jié)點(diǎn)數(shù)、最小節(jié)點(diǎn)數(shù)、DAG圖的層數(shù)、最大寬度以及RW任務(wù)的個(gè)數(shù))對(duì)IOZones應(yīng)用進(jìn)行定制，并且將數(shù)據(jù)密集型應(yīng)用以DAG圖的形式保存在本地。在生成DIA時(shí)會(huì)產(chǎn)生2個(gè)文件，分別是保存DIA各個(gè)節(jié)點(diǎn)之間依賴(lài)關(guān)系的DAG圖信息文件iozones_dag.txt以及保存每個(gè)節(jié)點(diǎn)中的命令信息iozones_command.txt.iozone。任務(wù)是文件系統(tǒng)測(cè)試基準(zhǔn)工具IOZone中的任務(wù)，是典型的數(shù)據(jù)密集型任務(wù)，每一個(gè)iozone操作都是獨(dú)立的測(cè)試任務(wù)，具有原子性。

綜合以上問(wèn)題參數(shù)，通過(guò)分別改變工作流應(yīng)用的數(shù)據(jù)集(文件數(shù)據(jù))個(gè)數(shù)以及數(shù)據(jù)中心個(gè)數(shù)這2種參數(shù)，共生成(3×30+3)×5×4=1 860組測(cè)試實(shí)例。將COPVDA與隨機(jī)Random算法和最具代表性的K-means聚類(lèi)算法[6]進(jìn)行對(duì)比試驗(yàn)，3種數(shù)據(jù)布局策略從應(yīng)用執(zhí)行過(guò)程中的數(shù)據(jù)移動(dòng)次數(shù)以及傳輸時(shí)間情況這2方面進(jìn)行對(duì)比和分析。實(shí)驗(yàn)結(jié)果取所有實(shí)驗(yàn)組數(shù)的平均值。

實(shí)驗(yàn)的硬件環(huán)境為Intel(R) Core(TM) i5 CPU 1.60GHz，RAM 4.00GB；軟件環(huán)境為Ubuntu 16.04.2LTS，gcc version 5.4.0，qt version 5.6.2。

3.2 數(shù)據(jù)移動(dòng)次數(shù)對(duì)比

數(shù)據(jù)移動(dòng)次數(shù)為科學(xué)工作流執(zhí)行過(guò)程中數(shù)據(jù)集在不同數(shù)據(jù)中心的傳遞次數(shù)。數(shù)據(jù)集個(gè)數(shù)對(duì)移動(dòng)次數(shù)的影響見(jiàn)圖3(其中，橫坐標(biāo)表示數(shù)據(jù)集的數(shù)量，數(shù)據(jù)集數(shù)量由20增到100；縱坐標(biāo)表示跨數(shù)據(jù)中心的數(shù)據(jù)移動(dòng)次數(shù))。從圖3可見(jiàn)：隨著數(shù)據(jù)量增多，3種策略的數(shù)據(jù)移動(dòng)次數(shù)明顯呈上升趨勢(shì)，但本文策略對(duì)應(yīng)的傳輸次數(shù)最少。

數(shù)據(jù)中心個(gè)數(shù)對(duì)移動(dòng)次數(shù)的影響見(jiàn)圖4(其中，橫坐標(biāo)表示數(shù)據(jù)中心的數(shù)量，縱坐標(biāo)表示跨數(shù)據(jù)中心的數(shù)據(jù)移動(dòng)次數(shù))。從圖4可見(jiàn)：當(dāng)數(shù)據(jù)中心數(shù)量由3增到10時(shí)，3種數(shù)據(jù)布局策略所對(duì)應(yīng)的跨數(shù)據(jù)中心數(shù)據(jù)移動(dòng)次數(shù)都相應(yīng)增加；雖然當(dāng)數(shù)據(jù)中心數(shù)量較少時(shí)，本文策略與聚類(lèi)策略相差很小，但綜合來(lái)看，隨著數(shù)據(jù)中心數(shù)量增多，本文策略的跨數(shù)據(jù)中心數(shù)據(jù)移動(dòng)次數(shù)最少。

數(shù)據(jù)布局策略：1—Random；2—K-means；3—CDPVDA。

數(shù)據(jù)布局策略：1—Random；2—K-means；3—CDPVDA。

3.3 數(shù)據(jù)傳輸時(shí)間對(duì)比

數(shù)據(jù)傳輸時(shí)間為科學(xué)工作流通過(guò)HEFT任務(wù)調(diào)度算法來(lái)仿真模擬運(yùn)行任務(wù)的整體時(shí)間。數(shù)據(jù)集變化和數(shù)據(jù)中心變化對(duì)傳輸時(shí)間的影響分別如圖5和圖6所示。從圖5和圖6可見(jiàn)：數(shù)據(jù)集以及數(shù)據(jù)中心的數(shù)量越大，3種數(shù)據(jù)布局策略所對(duì)應(yīng)的跨數(shù)據(jù)中心數(shù)據(jù)傳輸時(shí)間越多，而本文策略所對(duì)應(yīng)的數(shù)據(jù)傳輸時(shí)間開(kāi)銷(xiāo)一直最少。

上述實(shí)驗(yàn)結(jié)果表明：在云環(huán)境中實(shí)現(xiàn)數(shù)據(jù)密集型應(yīng)用，隨著數(shù)據(jù)量增多和數(shù)據(jù)中心增多，應(yīng)用在執(zhí)行過(guò)程中涉及的跨數(shù)據(jù)中心數(shù)據(jù)移動(dòng)次數(shù)和時(shí)間開(kāi)銷(xiāo)都不斷增大，而本文策略與基于隨機(jī)算法以及聚類(lèi)算法的數(shù)據(jù)布局策略相比時(shí)間開(kāi)銷(xiāo)減少，所獲得的結(jié)果 較優(yōu)。

數(shù)據(jù)布局策略：1—Random；2—K-means；3—CDPVDA。

數(shù)據(jù)布局策略：1—Random；2—K-means；3—CDPVDA。

4 結(jié)論

1) 針對(duì)數(shù)據(jù)布局問(wèn)題中現(xiàn)有技術(shù)和方法存在的不足，構(gòu)建虛擬數(shù)據(jù)代理云模型，設(shè)計(jì)出一種面向數(shù)據(jù)密集型應(yīng)用的基于虛擬數(shù)據(jù)代理的云模型數(shù)據(jù)布局策略。與其他數(shù)據(jù)布局策略相比，本文的數(shù)據(jù)布局策略具有較好的性能，跨數(shù)據(jù)中心的數(shù)據(jù)移動(dòng)次數(shù)降低，時(shí)間開(kāi)銷(xiāo)較少。

2) 數(shù)據(jù)布局過(guò)程中的核心即確立虛擬數(shù)據(jù)代理，其結(jié)果對(duì)第1個(gè)數(shù)據(jù)集很敏感，而本文采取的是隨機(jī)抽取方法對(duì)數(shù)據(jù)布局策略有一定影響。下一步將進(jìn)一步研究能夠反映真實(shí)情況的云模型數(shù)據(jù)布局算法，并將該方法應(yīng)用于具體的數(shù)據(jù)密集型領(lǐng)域。

[1] 宮學(xué)慶, 金澈清, 王曉玲, 等. 數(shù)據(jù)密集型科學(xué)與工程: 需求和挑戰(zhàn)[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(8): 1563?1578. GONG Xueqing, JIN Cheqing, WANG Xiaoling, et al. Data-intensive science and engineering: requirements and challenges[J]. Chinese Journal of Computers, 2012, 35(8): 1563?1578.

[2] BRIAN V E, HENRY H, SASHA A, et al. DI-MMAP—a scalable memory-map runtime for out-of-core data-intensive applications[J]. Cluster Computing, 2015, 18: 15?28.

[3] SENYO P K, EFFAH J, ADDAE E. Preliminary insight into cloud computing adoption in a developing country[J]. Journal of Enterprise Information Management, 2016, 29(4): 400?422.

[4] SHANGPengju, WANG Jun. A novel power management for CMP systems in data-intensive environment[C]//IEEE International Symposium on Parallel and Distributed Processing. Anchorage, Alaska, USA, 2011: 92?103.

[5] WANG Shangguang, SUN Qibo, ZHANG Guangwei, et al. Uncertain Qos-aware skyline service selection based on cloud model[J]. Journal of Software, 2012, 23(6): 1397?1412.

[6] YUAN Dong, YANG Yun, LIU Xiao. A data placement strategy in scientific cloud workflows[J]. Future Generation Computer Systems, 2010, 26(8): 1200?1214.

[7] 劉少偉, 孔令梅, 任開(kāi)軍, 等. 云環(huán)境下優(yōu)化科學(xué)工作流執(zhí)行性能的兩階段數(shù)據(jù)放置與任務(wù)調(diào)度策略[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(11): 2121?2130. LIU Shaowei, KONG Lingmei, REN Kaijun, et al. A two-step data placement and task scheduling strategy for optimizing scientific workflow performance on cloud computing platform[J]. Chinese Journal of Computers,2011,34(11): 2121?2130.

[8] DENG Kefeng, REN Kaijun, SONG Junqiang, et al. A clustering based co-scheduling strategy for efficient scientific workflow execution in cloud computing[J]. Concurrency and Computation: Practice & Experience, 2013, 25(18): 2523?2539.

[9] 張?zhí)鹛? 崔立真. 基于釋放和重構(gòu)的科學(xué)工作流數(shù)據(jù)布局策略[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(S2): 71?76. ZHANG Tiantian, CUI Lizhen. A data placement strategy based on relaxation and reconstruction for scientific workflow applications[J]. Journal of Computer Research and Development, 2013, 50(S2): 71?76.

[10] PANDEY S, WU Linlin, GURU S M, et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[C]// IEEE International Conference on Advanced Information NETWORKING and Applications. Aina, Perth, Australia, 2010: 400?407.

[11] XU Changlin, WANG Guoyin, ZHANG Qinghua. A new multi-step backward cloud transformation algorithm based on normal cloud model[J]. Fundamental Informaticae, 2014, 133(1): 55?85.

[12] CHEN Jinpeng, LIU Yu, LI Deyi. Enhancing recommender diversity using gaussian cloud transformation[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2015, 23(4): 521?544.

[13] MA Hua, HU Zhigang, LI Keqin. Toward trustworthy cloud service selection: a time-aware approach using interval neutrosophic set[J]. Journal of Parallel & Distributed Computing, 2016, 96(C): 75?94.

[14] ZHANG Xinxin, HU Zhigang, ZHENG Meiguang, et al. A novel cloud model based data placement strategy for data-intensive application in clouds[EB/OL]. [2018?08?21]. https://doi.org/ 10.1016/j.compeleceng.2018.07.007.

[15] WANG Guoyin, XU Changlin, LI Deyi. Generic normal cloud model[J]. Information Science, 2014, 280: 1?15.

[16] AUFFHAMMER M, HSIANG S M, SCHLENKER W, et al. Using Weather Data and Climate Model Output in Economic Analyses of Climate Change[J]. Review of Environmental Economics & Policy, 2013, 7(2): 181?198.

[17] BAUN C. Mobile clusters of single board computers: an option for providing resources to student projects and researchers[J]. Springer Plus, 2016, 5(1): 360.

[18] DALEY C S, GHOSHAL D, LOCKWOOD G K, et al. Performance characterization of scientific workflows for the optimal use of burst buffers[J]. Future Generation Computer Systems, 2017, 53: 69?73.

[19] HU Zhigang, LI Jia, ZHENG Meiguang, et al. Hypergraph-based data reduced scheduling policy for data-intensive workflow in clouds[C]// ICPCSEE 2017. Third International Conference of Pioneering Computer Scientists, Engineers and Educators. Changsha, China, 2017: 335?349.

Cloud model construction of virtual data agent and data placement

HU Zhigang, ZHANG Xinxin, ZHENG Meiguang, CHANG Chenglong, LI Jia, YANG Liu

(School of Computer Science, Central South University, Changsha 410083, China)

Considering the dependence between data sets and the storage capacity of data centers, a new type of entity called virtual data agent was introduced. The data placement problem was converted into two mapping processes namely mapping from the data set to the virtual data agent and mapping from the virtual data agent to the data center. Cloud model based data placement algorithm with virtual data agent(CDPVDA) was proposed. The results of simulation experiment show that compared with two typical data placement strategies, CDPVDA can reduce data transmission overhead between data centers by 5% to 20%.

cloud model; data-intensive application; virtual data agent; data placement

TP391

A

1672?7207(2019)03?0587?09

10.11817/j.issn.1672-7207.2019.03.012

2018?04?10；

2018?06?05

國(guó)家自然科學(xué)基金資助項(xiàng)目(61602525，61572525) (Projects(61602525, 61572525) supported by the National Natural Science Foundation of China)

鄭美光，博士，副教授，碩士生導(dǎo)師，從事云計(jì)算、大數(shù)據(jù)等研究；E-mail: zhengmeiguang@csu.edu.cn

(編輯 陳燦華)