結(jié)合大數(shù)據(jù)流特征和改進(jìn)SOM聚類的資源動(dòng)態(tài)分配算法

項(xiàng)麗萍 楊紅菊

1(晉城職業(yè)技術(shù)學(xué)院信息工程系 山西 晉城 048000)2(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 山西 太原 030006)

0 引 言

現(xiàn)階段，物聯(lián)網(wǎng)和人們的生活越來越密切，物聯(lián)網(wǎng)設(shè)備可以隨機(jī)生成數(shù)據(jù)，這種隨機(jī)性會(huì)導(dǎo)致具有未知特性的大數(shù)據(jù)流的產(chǎn)生[1]。這些大數(shù)據(jù)通常由多樣性的圖像、視頻、音頻和文本等數(shù)據(jù)組成。大數(shù)據(jù)流的數(shù)據(jù)特性包括4V：體積(Volume)、速度(Velocity)、類型(Variety)和可變性(Variability)。

隨著大數(shù)據(jù)流的增加，如何實(shí)時(shí)分析大數(shù)據(jù)是一個(gè)難題。使用最多的是基于云計(jì)算的大數(shù)據(jù)分析法，通過選擇合適的云資源來分析數(shù)據(jù)特性已成為熱門研究問題[2-3]。文獻(xiàn)[4]強(qiáng)調(diào)了動(dòng)態(tài)資源配置是大數(shù)據(jù)應(yīng)用程序調(diào)度中的一個(gè)具有挑戰(zhàn)性的問題。文獻(xiàn)[5]提出了一個(gè)基于QoS的框架實(shí)現(xiàn)大數(shù)據(jù)中的最優(yōu)資源分配。該框架的功能和QoS要求由用戶提供。功能要求包括處理能力、GPU功率、RAM和輸入數(shù)據(jù)的大小等；QoS要求包括響應(yīng)時(shí)間、輸出數(shù)據(jù)質(zhì)量和結(jié)果可視化。根據(jù)功能和QoS要求，使用樸素貝葉斯算法確定所需云群。文獻(xiàn)[6]提出一種基于圖的大數(shù)據(jù)資源處理方法，可以在不影響響應(yīng)時(shí)間的情況下提高數(shù)據(jù)處理效率。文獻(xiàn)[7]提出了一種基于優(yōu)先級(jí)的多媒體數(shù)據(jù)處理方法，該方法是靜態(tài)混合算法。文獻(xiàn)[8]使用馬爾可夫鏈和分配的節(jié)點(diǎn)有效地預(yù)測(cè)了大數(shù)據(jù)的大小以進(jìn)行數(shù)據(jù)處理。但是該模型沒有考慮大數(shù)據(jù)資源分配的高速性、多樣性和可變性。文獻(xiàn)[9]強(qiáng)調(diào)云數(shù)據(jù)中心的可變性會(huì)影響云資源的分配。文獻(xiàn)[10]表明了預(yù)測(cè)大數(shù)據(jù)請(qǐng)求的速度對(duì)有效配置云資源至關(guān)重要。以上研究表明，流式大數(shù)據(jù)的4V特性是云資源分配的重要參數(shù)。

因此，本文提出了一種大數(shù)據(jù)環(huán)境下結(jié)合數(shù)據(jù)特征預(yù)測(cè)和智能聚類的資源管理算法。其主要?jiǎng)?chuàng)新點(diǎn)在于：(1) 根據(jù)現(xiàn)有數(shù)據(jù)的體積、速度的變化情況，對(duì)下一時(shí)刻數(shù)據(jù)的特征進(jìn)行估計(jì)。(2) 利用自組織映射SOM和粒子群優(yōu)化PSO相結(jié)合，構(gòu)建一種先進(jìn)的聚類算法，根據(jù)估計(jì)的數(shù)據(jù)特征對(duì)數(shù)據(jù)進(jìn)行聚類，用來分配合理資源。

1 算法流程

本文提出的算法旨在基于數(shù)據(jù)特性(4V)為大數(shù)據(jù)流分配適當(dāng)?shù)馁Y源。為了實(shí)現(xiàn)該目標(biāo)，算法分為兩步，如圖1所示。

圖1 本文算法框架

1) 首先從輸入流中提取小塊數(shù)據(jù)，塊大小是底層存儲(chǔ)系統(tǒng)(例如HDFS的默認(rèn)塊大小為64 MB)的一個(gè)整數(shù)倍，這樣可減少讀取和分析數(shù)據(jù)的開銷。分析所選數(shù)據(jù)塊，根據(jù)現(xiàn)有數(shù)據(jù)特征來估計(jì)下一時(shí)刻數(shù)據(jù)流的體積和速度。在估計(jì)這些值時(shí)，會(huì)考慮數(shù)據(jù)的可變性。估計(jì)值用數(shù)據(jù)特征(CoD)向量表示。

2) 利用PSO優(yōu)化SOM算法的權(quán)值分布，構(gòu)建一種改進(jìn)型SOM算法，用于對(duì)CoD向量進(jìn)行聚類，動(dòng)態(tài)創(chuàng)建和分配空閑的云資源集群。

在r個(gè)時(shí)間單位之后，使用自適應(yīng)采樣技術(shù)[11]選擇另一個(gè)塊，其中，r取決于采樣率。這種機(jī)制允許算法在早期捕獲新到達(dá)數(shù)據(jù)流的變化性，從而分配適當(dāng)?shù)募?。接著，算法自?dòng)調(diào)整采樣率大小，這個(gè)過程中涉及到遷移開銷[12]。如果遷移開銷很高，r的值會(huì)增加，如果執(zhí)行時(shí)間很長(zhǎng)，則r的值會(huì)降低。對(duì)采樣的數(shù)據(jù)塊再次進(jìn)行分析，并使用上述步驟分配資源。

2 數(shù)據(jù)特性的估計(jì)

為了估計(jì)數(shù)據(jù)特征，通過四個(gè)階段進(jìn)行操作：第一階段，確定數(shù)據(jù)類型；第二階段，使用數(shù)據(jù)可變性估計(jì)數(shù)據(jù)的體積和速度；第三階段，計(jì)算相對(duì)體積和速度，即將這些估計(jì)值與其他到達(dá)云端的數(shù)據(jù)請(qǐng)求進(jìn)行比較，并計(jì)算相對(duì)的體積和速度；第四階段，相對(duì)值的有效表示。下面給出詳細(xì)的步驟。

2.1 數(shù)據(jù)類型確定

目前，數(shù)據(jù)分析主要有四種類型[13]，分別是文本分析、圖像分析、音頻分析和視頻分析。本文使用Bloom過濾器[14]來確定數(shù)據(jù)的類型。Bloom過濾器的組成包括：(1) 一個(gè)n位的序列，初始值均為0；(2)k個(gè)哈希函數(shù)的集合h1,h2,…,hk；(3)m個(gè)鍵值組成的集合S。每個(gè)哈希函數(shù)將鍵值映射到n個(gè)塊中，對(duì)應(yīng)于n個(gè)數(shù)組。Bloom過濾器的目的是允許S中的流元素通過，拒絕其他元素。

令p表示可接受的假陽性率，則n和k的值可由式(1)和式(2)計(jì)算得到：

(1)

(2)

Bloom過濾器的工作流程如算法1所示。

算法1Bloom過濾器的工作流程

輸入： 數(shù)組BF[n]，集合S，哈希函數(shù)h1,h2,…,hk

輸出： 特定類型的數(shù)據(jù)e

1. 初始化BF[1],…,BF[n]=0；2. 對(duì)于每個(gè)鍵值yi∈S

計(jì)算h1(yi),…,hk(yi)；

設(shè)置BF[hj(yi)]=1,1≤j≤k；

3. 對(duì)每個(gè)經(jīng)過過濾器的流元素e

計(jì)算h1(e),…,hk(e)；

對(duì)于所有j，如果BF[hj(e)]=1

允許e通過濾波器并輸出；

4. 退出

在本文所提出的算法中，使用四個(gè)Bloom過濾器。第一個(gè)過濾器僅允許圖像類數(shù)據(jù)通過，并阻擋其他類型的數(shù)據(jù)。類似地，第二、第三和第四過濾器分別允許音頻、視頻和文本數(shù)據(jù)通過。

這里，一個(gè)特定Bloom過濾器的集合S由所有可能的數(shù)據(jù)格式組成。例如，在第一個(gè)過濾器中設(shè)置S包含所有圖像格式，如jpeg、png等。第二個(gè)過濾器中的集合S由所有音頻格式組成，如mp3、wav、aiff等。用同樣的方式構(gòu)造另外兩個(gè)過濾器的S集合。因此，m的值等于S中n和k的總和。

在數(shù)據(jù)加入塊中時(shí)，計(jì)算塊中的數(shù)據(jù)的體積和速度的絕對(duì)值。設(shè)ρt(I)和ut(I)為t時(shí)刻圖像數(shù)據(jù)的絕對(duì)體積和速度，這些值開始時(shí)均為零。每次將圖像數(shù)據(jù)添加到其相應(yīng)的存儲(chǔ)塊中時(shí)，都會(huì)使用式(3)和式(4)更新數(shù)據(jù)體積和速度值。其中，δ表示在一個(gè)時(shí)間點(diǎn)通過過濾器的數(shù)據(jù)的體積量。

ρt(I)=ρt(I)+δ

(3)

ut(I)=ut(I)+1

(4)

類似地，音頻數(shù)據(jù)的體積為ρt(A)，音頻數(shù)據(jù)的速度為ut(A)，視頻數(shù)據(jù)的體積為ρt(V)，視頻數(shù)據(jù)的速度為ut(V)，文本數(shù)據(jù)的體積為ρt(T)，文本數(shù)據(jù)的速度為ut(T) 。這些值根據(jù)它們各自的塊進(jìn)行計(jì)算。在第二階段中，將使用這些值來估計(jì)第(t+1)時(shí)刻數(shù)據(jù)的體積和速度。

2.2 利用自回歸模型預(yù)測(cè)體積和速度

數(shù)據(jù)流可能不具有周期性峰值。比如，當(dāng)社交媒體上發(fā)生某些事情時(shí)，可能會(huì)導(dǎo)致在特定時(shí)間段內(nèi)大量高速生成數(shù)據(jù)。因此，在估計(jì)下一個(gè)時(shí)間間隔內(nèi)到達(dá)的數(shù)據(jù)體積和速度的過程中，可變性有著重要的影響。為了減小可變性的影響，本文采用自回歸模型[15]。自回歸模型使用預(yù)測(cè)變量的線性組合來預(yù)測(cè)變量的值。

(5)

(6)

其中：

(7)

(8)

式中:cov()和var()分別代表協(xié)方差和方差。同樣，使用自回歸模型計(jì)算音頻、視頻和文本數(shù)據(jù)的預(yù)測(cè)體積和速度。

2.3 計(jì)算相對(duì)體積和速度

本文并沒有對(duì)大數(shù)據(jù)作一個(gè)具體的定義，因此，第二階段的體積和速度的預(yù)測(cè)值需要與其他到達(dá)云數(shù)據(jù)中心的數(shù)據(jù)請(qǐng)求進(jìn)行比較。比較后得到的值稱為相對(duì)體積和速度。以下討論圖像數(shù)據(jù)的相對(duì)體積和速度的計(jì)算。音頻、視頻和文本數(shù)據(jù)的計(jì)算與圖像類型的計(jì)算方式類似。

(9)

(10)

式中：函數(shù)round(num，num_digit) 表示將數(shù)字num 四舍五入到具有num_digit位小數(shù)的數(shù)。本文中，將體積等于max(ρt(I))的大數(shù)據(jù)流的相對(duì)體積設(shè)置為1。這意味著相對(duì)體積的最大值是1。與之對(duì)應(yīng)的，相對(duì)體積的最小值是零。因此，式(9)的取值范圍為[0,1] 。此外，由于式(9)的結(jié)果四舍五入到小數(shù)點(diǎn)后一位，所以{0,0.1,0.2,…,0.9,1}是相對(duì)體積的可能值的集合。相對(duì)速度的計(jì)算與相對(duì)體積類似。

2.4 預(yù)測(cè)值的CoD表示

在云資源的分配中，有必要以一種特殊的形式表示預(yù)測(cè)的4V值。本文中將數(shù)據(jù)的相對(duì)體積和速度預(yù)測(cè)值進(jìn)行整合，形成數(shù)據(jù)強(qiáng)度度量。例如，圖像數(shù)據(jù)的強(qiáng)度φ(I)可以使用式(11)計(jì)算得到。

φ(I)=ρ″t+1(I)·u″t+1(I)

(11)

音頻、視頻和文本數(shù)據(jù)的強(qiáng)度也根據(jù)該等式進(jìn)行計(jì)算。由于ρ″t+1()和u″t+1()的范圍都在[0,1]之間，所以強(qiáng)度的取值范圍也是[0,1]。

在獲得圖像、音頻、視頻和文本數(shù)據(jù)的強(qiáng)度之后，用數(shù)據(jù)特征(CoD)矢量的形式來表示它們。CoD的定義為：CoD=(φ(I),φ(A),φ(V),φ(T))。

3 基于改進(jìn)SOM聚類的資源管理

3.1 PSO改進(jìn)SOM聚類

傳統(tǒng)的聚類算法如K_meas等，往往需要事先定義聚類數(shù)目。通?；诮?jīng)驗(yàn)知識(shí)來確定類別個(gè)數(shù)，而且一般需要多次嘗試，這種方法具有很大的盲目性。

在本文資源聚類應(yīng)用中，需要根據(jù)數(shù)據(jù)流特征來分配合適類型的資源，如果事先定義資源類型數(shù)量則不能適應(yīng)數(shù)據(jù)流的變化。為此，本文采用了SOM聚類算法，利用SOM的可視化功能來動(dòng)態(tài)確定聚類數(shù)目，避免傳統(tǒng)聚類算法確定聚類數(shù)目的盲目性。SOM是用于聚類分析的無監(jiān)督神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)技術(shù)之一[16]。初始時(shí)將每個(gè)資源都作為一個(gè)聚類，通過計(jì)算資源與數(shù)據(jù)流的距離來動(dòng)態(tài)聚類，以此為每個(gè)數(shù)據(jù)流分配最佳資源。SOM由輸入層和輸出層組成，其結(jié)構(gòu)如圖2所示。

圖2 SOM映射網(wǎng)絡(luò)

利用SOM進(jìn)行聚類分析可分為以下幾步：

初始化參數(shù)：輸入、輸出神經(jīng)元個(gè)數(shù)n、m，當(dāng)前迭代次數(shù)t，最大迭代次數(shù)T，初始權(quán)值Wij(1)，學(xué)習(xí)速率因子ψ(1)，鄰域半徑N(1)。

(1) 對(duì)SOM中神經(jīng)元的初始權(quán)值Wij(1)進(jìn)行歸一化，使權(quán)值的范圍處在(0,1)之間。

(2) 計(jì)算訓(xùn)練樣本和輸出層神經(jīng)元間的距離值，計(jì)算公式如下：

(12)

(3) 找出距離最小值對(duì)應(yīng)的輸出層神經(jīng)元，將它定義為獲勝神經(jīng)元j：

(13)

(4) 調(diào)整獲勝神經(jīng)元的權(quán)值：

Wij(t+1)=Wij(t)+ψ(t)(xi-Wij(t))

(14)

(5) 按照式(15)更新獲勝神經(jīng)元的鄰域以及SOM的學(xué)習(xí)速率。

(15)

(6) 如果滿足以下所列條件中的任意一個(gè)，則SOM算法結(jié)束，輸出聚類結(jié)果。①ψ(t)的值下降為0；②t=T。否則，t=t+1，返回到步驟(2)重復(fù)執(zhí)行。

雖然SOM算法的樣本學(xué)習(xí)更加精確，并且收斂速度能夠滿足多數(shù)情況下的要求，但SOM算法的收斂效果與權(quán)值的初始分布有著密切的關(guān)系。本文利用PSO算法優(yōu)化SOM算法的權(quán)值，以增強(qiáng)收斂效果。

在PSO算法中，候選解通常用粒子來表示。在一個(gè)D維空間中，令粒子的位置P、速度V表示如下：

(16)

在PSO算法的迭代過程中，粒子根據(jù)個(gè)體最優(yōu)值和全局最優(yōu)值更新自身的位置xi(t+1)和速度vi(t+1)：

(17)

式中：w表示慣性權(quán)重；c1和c2表示學(xué)習(xí)因子，它們的取值范圍是(1,2)；λ1和λ2是兩個(gè)在(0,1)之間的常數(shù)；pbsti和gbsti分別表示個(gè)體最優(yōu)粒子和全局最優(yōu)粒子。

基于PSO優(yōu)化SOM的具體步驟如下：

(1) 粒子位置編碼表示為：

P={w11,w12,…,w1m…wn1,…,wnm}

(18)

式中:m表示資源聚類數(shù)目，對(duì)應(yīng)于SOM算法中的輸出神經(jīng)元個(gè)數(shù)；n表示資源屬性數(shù)目，對(duì)應(yīng)于SOM算法中的輸入神經(jīng)元個(gè)數(shù)。

(2) 根據(jù)式(17)更新粒子的位置xi(t+1)和速度vi(t+1)。

(3) 計(jì)算粒子的適應(yīng)度值，找出個(gè)體最優(yōu)粒子pbsti和全局最優(yōu)粒子gbsti。適應(yīng)度值的計(jì)算式為：

(19)

式中：i表示樣本，j表示i相對(duì)應(yīng)的獲勝神經(jīng)元，Dij(t)表示i和j之間的距離。

(4) 當(dāng)?shù)玫降娜肿顑?yōu)粒子gbsti變化時(shí)，返回步驟(2)中重復(fù)執(zhí)行操作，直到gbsti不再發(fā)生變化。

3.2 動(dòng)態(tài)集群生成及資源分配

在本文提出的算法中，將特征預(yù)測(cè)步驟中得到的CoD向量作為輸入向量，輸入到改進(jìn)SOM中進(jìn)行聚類，如算法2所示。聚類過程從權(quán)重W和學(xué)習(xí)速率因子ψ的初始化開始，利用PSO初始化SOM的權(quán)值初始分布。SOM隨機(jī)選擇一個(gè)資源向量(Si)，并從每個(gè)CoD向量中計(jì)算與它的距離。具有最小距離的CoD向量(CJ)稱為獲勝向量，并將資源Si分配到CoD向量CJ對(duì)應(yīng)的數(shù)據(jù)流。每個(gè)資源都會(huì)重復(fù)該過程，所有獲勝向量為CJ的資源稱為一個(gè)集群。

算法2利用改進(jìn)SOM生成動(dòng)態(tài)集群

1. 利用PSO初始化SOM的權(quán)值初始分布；

2. 將學(xué)習(xí)速率因子ψ定義為略小于1的值；

3. 重復(fù)3-9，直至計(jì)算邊界不滿足條件；

4. 對(duì)于每個(gè)輸入資源向量Si，重復(fù)步驟6-8；5. 對(duì)于每個(gè)輸出神經(jīng)元j，根據(jù)下式計(jì)算S的歐氏距離的平方：

6. 選擇D(j)最小的j；

7. 設(shè)置聚類特征CoC(Si)=CoD(Cj) ；

8. 根據(jù)下式更新j的所有拓?fù)溧従拥臋?quán)值：

Wjk(t+1)=(1-ψ)Wjk(t)+ψ(t)Sk；

9.ψ單調(diào)遞減；

10. 基于各自的CoC輸出虛擬聚類；

集群形成后，使用具有CoC=CoD屬性的集群來為數(shù)據(jù)流分配資源。如果選擇的集群有足夠的資源來處理數(shù)據(jù)流，則分配該集群。否則，搜索并分配具有足夠資源，且最近的拓?fù)溆行蚣?，這么做可以減小數(shù)據(jù)流的等待時(shí)間。

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

實(shí)驗(yàn)中分為兩個(gè)步驟，即數(shù)據(jù)流的特征估計(jì)和資源分配。其中，在PC機(jī)上通過Java編程實(shí)現(xiàn)自回歸模型，對(duì)下一時(shí)間間隔到達(dá)的數(shù)據(jù)的特征進(jìn)行估計(jì)。在第二個(gè)步驟中，使用AWS SDK for Java工具，在Amazon Web Services云平臺(tái)上開發(fā)和部署Java應(yīng)用程序，連接Amazon彈性計(jì)算云 EC2中的計(jì)算資源，實(shí)現(xiàn)資源分配。實(shí)驗(yàn)分為兩個(gè)部分，即預(yù)測(cè)分析和算法對(duì)比分析。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

生成四個(gè)容量較大的數(shù)據(jù)集。第一個(gè)數(shù)據(jù)集是由86 280個(gè)圖像組成的圖像數(shù)據(jù)集，第二個(gè)數(shù)據(jù)集是一個(gè)音頻集合，包含1 568首音樂曲目，第三個(gè)數(shù)據(jù)集是一個(gè)包含32小時(shí)視頻的監(jiān)控視頻數(shù)據(jù)集。第四個(gè)數(shù)據(jù)集是一個(gè)由1 000萬個(gè)單詞組成的文本數(shù)據(jù)集。使用這四個(gè)數(shù)據(jù)集創(chuàng)建一個(gè)數(shù)據(jù)庫(kù)，該數(shù)據(jù)庫(kù)滿足以下特征：

(1) 它由12%的圖像數(shù)據(jù)，21%的音頻數(shù)據(jù)，24%的視頻數(shù)據(jù)和43%的文本數(shù)據(jù)組成。

(2) 圖像數(shù)據(jù)在數(shù)據(jù)集前部時(shí)的體積較小，當(dāng)它越靠近數(shù)據(jù)集尾部時(shí)，體積逐漸增大。

(3) 音頻數(shù)據(jù)在數(shù)據(jù)集前部中的體積很大，而在數(shù)據(jù)集的末端有所下降。

(4) 視頻數(shù)據(jù)的體積先下降然后增加。

(5) 文本數(shù)據(jù)的體積在整個(gè)數(shù)據(jù)集中保持均勻，幾乎不變。

將數(shù)據(jù)庫(kù)中的數(shù)據(jù)以流的形式輸入到算法中，時(shí)間為1小時(shí)。其中圖像、音頻、視頻和文本數(shù)據(jù)的速度遵循以下模式：

(1) 圖像數(shù)據(jù)的速度先下降然后隨時(shí)間增加，使其形成流的整體速度的19%。

(2) 音頻數(shù)據(jù)的速度隨時(shí)間減小，使其形成流的整體速度的23%。

(3) 視頻數(shù)據(jù)的速度隨時(shí)間增加，使其形成流的整體速度的22%。

(4) 文本數(shù)據(jù)的速度幾乎保持不變，使其形成流的整體速度的36%。

4.2 數(shù)據(jù)流體積和速度的預(yù)測(cè)

將數(shù)據(jù)流的實(shí)際值與本文算法的預(yù)測(cè)值進(jìn)行比較，結(jié)果如表1和表2所示。本次實(shí)驗(yàn)中，以0.5個(gè)樣本/min的恒定采樣頻率進(jìn)行采樣。

表1 數(shù)據(jù)流體積的實(shí)際值與本文算法的預(yù)測(cè)值比較 GB

表2 數(shù)據(jù)流速度的實(shí)際值與本文算法的預(yù)測(cè)值比較 數(shù)據(jù)流量數(shù)量/min

從表1和表2可以看出，四種數(shù)據(jù)集的實(shí)際值與預(yù)測(cè)值之間的差異很小。圖3為四種數(shù)據(jù)類型的數(shù)據(jù)流體積和速度預(yù)測(cè)的平均絕對(duì)預(yù)測(cè)誤差(MAPE)。

圖3 平均絕對(duì)預(yù)測(cè)誤差

從圖3可以看出，MAPE隨著數(shù)據(jù)占比的增加而減少。如上文所述，數(shù)據(jù)流由12%的圖像數(shù)據(jù)，21%的音頻數(shù)據(jù)，24%的視頻數(shù)據(jù)和43%的文本數(shù)據(jù)組成，而預(yù)測(cè)圖像、音頻、視頻和文本數(shù)據(jù)體積的MAPE分別為0.247、0.216、0.172和0.123。圖像數(shù)據(jù)占比是最小的，但它的MAPE是最高的；文本數(shù)據(jù)的占比是最大的，而它的MAPE是最低的。因此，對(duì)于占比更高的數(shù)據(jù)類型，其MAPE會(huì)更低，并且這一數(shù)值隨著數(shù)據(jù)占比的減少而增加。從數(shù)據(jù)速度的角度上可以觀察到類似的現(xiàn)象，這符合大數(shù)定律，也就是說，誤差隨著數(shù)據(jù)大小的增加而減小。

從以上結(jié)果可知，本文算法能有效地預(yù)測(cè)圖像、音頻、視頻和文本數(shù)據(jù)的體積和速度。

4.3 算法對(duì)比

將本文提出的算法與文獻(xiàn)[5]提出的基于QoS的資源管理算法、文獻(xiàn)[8]提出的基于馬爾可夫鏈的資源分配算法進(jìn)行實(shí)驗(yàn)比較。本次實(shí)驗(yàn)中生成具有不同體積和速度占比的5個(gè)大數(shù)據(jù)流集，流生成的過程與第4.1節(jié)相同。表3為5個(gè)數(shù)據(jù)流集中各種數(shù)據(jù)的體積和速度的占比，每隔十分鐘將一個(gè)流送入算法中。

表3 生成的流中不同數(shù)據(jù)的體積和速度的百分比

分別使用上述三種算法，從Amazon彈性計(jì)算云 Elastic Compute Cloud(EC2)中選擇虛擬機(jī)(VM)作為資源，分配給適當(dāng)?shù)臄?shù)據(jù)流。本文中選擇10個(gè)VM實(shí)例來進(jìn)行資源管理，每個(gè)實(shí)例都來自于EC2中針對(duì)計(jì)算密集型工作負(fù)載優(yōu)化的c4.large實(shí)例，配備2.9 GHz Intel Xeon E5-2666 v3 處理器。虛擬機(jī)處理生成的流，并在每個(gè)流上運(yùn)行Alon-Matias-Szegedy(AMS)算法。AMS用于確定流中不同元素的頻率。整個(gè)實(shí)驗(yàn)的執(zhí)行時(shí)間為一個(gè)小時(shí)。

圖4為三種算法的資源利用率的變化。在文獻(xiàn)[5]提出的基于QoS的算法中，算法的處理能力、GPU功率、RAM和輸入數(shù)據(jù)的大小由用戶提供。這些用戶需求用于為輸入請(qǐng)求分配資源。用戶需求取決于數(shù)據(jù)特征，在大數(shù)據(jù)流的情況下，用戶通常不知道數(shù)據(jù)特征。因此，在基于QoS的方法中，用戶可能無法為大數(shù)據(jù)流確定合適的資源，并且數(shù)據(jù)流在整個(gè)時(shí)間段內(nèi)運(yùn)行在相同的資源上。文獻(xiàn)[8]提出的算法能有效地預(yù)測(cè)數(shù)據(jù)流的大小，以選擇合適資源來處理數(shù)據(jù)，但是算法沒有考慮大數(shù)據(jù)資源分配的高速性、多樣性和可變性等因素。本文提出的算法能夠預(yù)測(cè)流的4V，并且能夠隨流中數(shù)據(jù)的特征變化恰當(dāng)?shù)姆峙滟Y源。因此，在圖4中，與文獻(xiàn)[5]、文獻(xiàn)[8]提出的算法相比，本文提出的算法資源利用率更高。

圖4 資源利用率

圖5為三種算法的整體執(zhí)行延遲的比較。在文獻(xiàn)[5]算法中，整個(gè)執(zhí)行期間執(zhí)行延遲幾乎相同，只是在實(shí)驗(yàn)結(jié)束時(shí)執(zhí)行延遲略有增加。這是因?yàn)殡S著更多流添加到算法中，算法所需集群的不可用的概率逐漸增加(所請(qǐng)求的資源可能已被其他流所占用)，因此，算法需要更多的時(shí)間尋找可用且最近的拓?fù)溆行蚣骸Ｔ谖墨I(xiàn)[8]算法中，執(zhí)行延遲隨著執(zhí)行時(shí)間的增加慢慢增大。在本文提出的算法中，實(shí)驗(yàn)開始時(shí)，執(zhí)行延遲較高，這是因?yàn)楸疚乃惴ㄔ诜峙溥m當(dāng)集群之前就預(yù)測(cè)了流的CoD，這就減少了執(zhí)行延遲，并且使合適資源可以更快地處理數(shù)據(jù)流。此外，從圖5可以看出，自從10 min后在系統(tǒng)中添加新流時(shí)，每隔10 min執(zhí)行延遲會(huì)出現(xiàn)周期性峰值。這是因?yàn)?，新流添加后需要重新?jì)算所有流的CoD，這就導(dǎo)致執(zhí)行延遲的周期性增加。盡管如此，本文提出算法的整體執(zhí)行延遲小于其余兩種算法。

圖5 執(zhí)行延遲

圖6為三種算法的的響應(yīng)時(shí)間比較。本文提出的算法的響應(yīng)時(shí)間在整個(gè)實(shí)驗(yàn)中幾乎保持相同。這是因?yàn)闊o論數(shù)據(jù)流中的數(shù)據(jù)特征發(fā)生何種變化，在本文提出的算法中始終能找到更合適的資源集群來處理該數(shù)據(jù)流，這帶來了穩(wěn)定的響應(yīng)時(shí)間。對(duì)于文獻(xiàn)[5]算法，在整個(gè)執(zhí)行時(shí)間段內(nèi)，無論數(shù)據(jù)特性如何變化，流始終在相同的資源上運(yùn)行，響應(yīng)時(shí)間就會(huì)隨著執(zhí)行時(shí)間而增加。文獻(xiàn)[8]算法僅僅根據(jù)數(shù)據(jù)流的大小來調(diào)整資源，沒有考慮資源速度的可變性，所分配的資源不一定最合適。

圖6 響應(yīng)時(shí)間

5 結(jié) 語

本文提出了一種高效的大數(shù)據(jù)流資源管理算法。所提出的算法基于數(shù)據(jù)特性的預(yù)測(cè)來分配合適資源，從而高效的處理數(shù)據(jù)流。這種分配方式可以隨著數(shù)據(jù)特性改變做出調(diào)整，使對(duì)數(shù)據(jù)流的響應(yīng)時(shí)間保持穩(wěn)定。此外，由改進(jìn)型SOM形成的簇的拓?fù)渑判蚩梢詼p少了流的等待時(shí)間。實(shí)驗(yàn)結(jié)果表明，和常用的分配算法相比，本文提出的算法能有效提高云資源的利用率。