基于層次分析與主成分分析的云存儲(chǔ)資源調(diào)度策略

徐建鵬， 李 欣， 孫海春

(中國(guó)人民公安大學(xué)信息技術(shù)與網(wǎng)絡(luò)安全學(xué)院， 北京 100038)

0 引言

云存儲(chǔ)是云架構(gòu)中IaaS層的核心構(gòu)件，其效率直接影響著整個(gè)云平臺(tái)的性能[1]。目前常見的云存儲(chǔ)架構(gòu)包括Googel的Googel File System[2]、Apache的Hadoop Distributed File System[3]、Amazon的Dynamo[4]以及基于OpenStack[5]開源框架的Swift、Cinder和Ceph。以O(shè)penStack為例，面向用戶數(shù)據(jù)的動(dòng)態(tài)存取業(yè)務(wù)主要由Cinder塊存儲(chǔ)來承擔(dān)，其資源調(diào)度策略主要是通過比較存儲(chǔ)節(jié)點(diǎn)的剩余可用空間來實(shí)現(xiàn)，這雖然可以較好地提高資源利用率，但并未考慮該節(jié)點(diǎn)是否出現(xiàn)了網(wǎng)絡(luò)堵塞、內(nèi)存使用率過高等情況，因此存在一定的局限性。國(guó)內(nèi)外目前都有一些對(duì)此問題的研究，比如多維離線調(diào)度算法[6]、基于三角模糊數(shù)的調(diào)度算法[7]，以及通過網(wǎng)絡(luò)延遲、負(fù)載均衡等因素來對(duì)調(diào)度策略進(jìn)行優(yōu)化，這些方法都能較好地提高云存儲(chǔ)資源調(diào)度的效率，但調(diào)度的判定因素仍然不夠全面，應(yīng)用場(chǎng)景較為單一。

針對(duì)上述問題，本文提出了基于層次分析法與主成分分析法的云存儲(chǔ)資源調(diào)度策略，首先對(duì)調(diào)度所涉及的指標(biāo)進(jìn)行全方面的研究、歸納，然后利用層次分析法對(duì)指標(biāo)項(xiàng)進(jìn)行定性與定量的研究，再通過主成分分析法對(duì)調(diào)度策略所涉及的8個(gè)詳細(xì)指標(biāo)項(xiàng)進(jìn)行權(quán)重分析，減少層次分析法中主觀判斷的誤差，提高策略的魯棒性，最后與現(xiàn)有的Cinder資源調(diào)度策略進(jìn)行對(duì)比分析，驗(yàn)證本文策略的有效性和穩(wěn)定性。

1 層次分析法與主成分分析法[9-10]

1.1 層次分析法的概念

層次分析法(Analytic Hierarchy Process，AHP)是由美國(guó)運(yùn)籌學(xué)家薩蒂教授于20世紀(jì)70年代初提出的一種層次權(quán)重決策分析方法，該方法通過將整個(gè)決策過程分解為總目標(biāo)、準(zhǔn)則、方案3個(gè)層次，并以此為基礎(chǔ)進(jìn)行定性和定量的分析，最終得出決策的結(jié)果。AHP的主要過程包括：構(gòu)建層次結(jié)構(gòu)模型、判斷矩陣分析、計(jì)算與分析結(jié)果。

使用AHP對(duì)一個(gè)問題進(jìn)行分析時(shí)，首先要對(duì)該問題構(gòu)建層次結(jié)構(gòu)模型，根據(jù)問題所涉及的各因素之間的相互作用以及包含關(guān)系，將其分為總目標(biāo) 、各層子目標(biāo)、評(píng)價(jià)準(zhǔn)則以及備選方案，然后定性地判斷最底層(備選方案)相對(duì)于最高層(總目標(biāo))的重要性順序，再采用“1-9”標(biāo)度法將其轉(zhuǎn)換為定量的分析，生成判斷矩陣，最終計(jì)算出除最高層外各層相對(duì)于上一層的權(quán)重分布，并以此求出各備選方案相對(duì)于總目標(biāo)的權(quán)重，得到最終的決策結(jié)果。

1.2 主成分分析法的概念

主成分分析法是一種把多個(gè)變量轉(zhuǎn)化為少數(shù)主要變量(即主成分)的多元統(tǒng)計(jì)分析方法，即將原來眾多具有一定相關(guān)性的指標(biāo)，重新組合成一組新的互相無關(guān)的綜合指標(biāo)來代替原來的指標(biāo)。該方法通常用來尋找判斷某種事物的主成分，從而更好地揭示事物內(nèi)在的規(guī)律。

我們?cè)O(shè)原始指標(biāo)變量為x1,x2,…,xp，將其進(jìn)行線性組合構(gòu)成新的綜合指標(biāo)標(biāo)量，即主成分z1,z2,…,zq，具體如公式1、2所示：

(1)

且滿足：

(2)

其中zm與zn互不相關(guān)，z1的方差最大，其余z2,…,zq的方差依次減少,且原始數(shù)據(jù)的總方差等于p個(gè)互不相關(guān)的主成分的方差之和，即p個(gè)互不相關(guān)的主成分包含了原始數(shù)據(jù)中的全部信息，但主成分所包含的信息更為集中。

2 云存儲(chǔ)資源調(diào)度策略的實(shí)現(xiàn)

2.1 構(gòu)建層次結(jié)構(gòu)模型

云存儲(chǔ)資源調(diào)度策略主要解決的是存儲(chǔ)節(jié)點(diǎn)選擇的問題，而該選擇所依賴的判定依據(jù)主要包括節(jié)點(diǎn)靜態(tài)指標(biāo)、節(jié)點(diǎn)動(dòng)態(tài)指標(biāo)以及網(wǎng)絡(luò)指標(biāo)，其中節(jié)點(diǎn)靜態(tài)指標(biāo)細(xì)分為節(jié)點(diǎn)I/O頻率與節(jié)點(diǎn)故障率。節(jié)點(diǎn)動(dòng)態(tài)指標(biāo)包括節(jié)點(diǎn)剩余存儲(chǔ)空間、數(shù)據(jù)傳輸距離、節(jié)點(diǎn)CPU負(fù)載情況與節(jié)點(diǎn)內(nèi)存使用率。網(wǎng)絡(luò)指標(biāo)主要為節(jié)點(diǎn)網(wǎng)絡(luò)帶寬與節(jié)點(diǎn)網(wǎng)絡(luò)延遲。為便于分析，本文在備選方案中設(shè)計(jì)了3個(gè)可選節(jié)點(diǎn)。根據(jù)以上設(shè)計(jì)，即可構(gòu)建出相關(guān)的層次結(jié)構(gòu)模型，本文使用yaahp工具進(jìn)行實(shí)現(xiàn)，具體如圖1所示。

圖1 云存儲(chǔ)資源調(diào)度指標(biāo)的層次結(jié)構(gòu)模型

2.2 判斷矩陣分析

層次分析法中，定性分析轉(zhuǎn)換為定量分析的關(guān)鍵在于“1-9”標(biāo)度法的使用，具體如表1所示。

表1 “1-9”標(biāo)度法賦值及其具體含義

不同的云用戶，對(duì)于各類指標(biāo)會(huì)有不同的要求，例如與個(gè)人用戶相比，金融企業(yè)用戶會(huì)對(duì)網(wǎng)絡(luò)指標(biāo)具有極高的要求。因此，本文主要是基于廣泛的個(gè)人用戶的調(diào)研，來進(jìn)行云存儲(chǔ)資源調(diào)度策略的層次分析。

首先，我們分析“云存儲(chǔ)節(jié)點(diǎn)選擇”的判斷矩陣，如表2所示，其中每一個(gè)值，代表其橫向指標(biāo)相比于縱向指標(biāo)的標(biāo)度，即對(duì)于總目標(biāo)，橫向指標(biāo)與縱向指標(biāo)之間重要性的比較。

表2 節(jié)點(diǎn)靜態(tài)指標(biāo)、節(jié)點(diǎn)動(dòng)態(tài)指標(biāo)及網(wǎng)絡(luò)指標(biāo)相對(duì)于總目標(biāo)的重要性分析

由表2，即可得到相關(guān)的判斷矩陣A：

權(quán)重分布為WA=[0.209 8，0.549 9，0.240 2]T，且矩陣A的一致性指標(biāo)CR=0.017 6<0.1，滿足一致性檢驗(yàn)。

同理，我們可以得到節(jié)點(diǎn)靜態(tài)指標(biāo)、節(jié)點(diǎn)動(dòng)態(tài)指標(biāo)及網(wǎng)絡(luò)指標(biāo)這3個(gè)對(duì)象的判斷矩陣：

其權(quán)重分別為WB1=[0.166 7，0.833 3]T，WB2=[0.261 8，0.527 7，0.105 2，0.105 2]T，WB3=[0.166 7,0.833 3]T，且均通過一致性檢驗(yàn)。

最后，我們需要分析3個(gè)存儲(chǔ)結(jié)點(diǎn)的各指標(biāo)表現(xiàn)情況，具體如表3所示，其中C1～C8代表“I/O頻率”至“網(wǎng)絡(luò)延遲”8個(gè)指標(biāo)，此時(shí)表中的標(biāo)度值可以理解為兩節(jié)點(diǎn)在某一指標(biāo)下的優(yōu)劣程度。綜合以上數(shù)據(jù)，可得表4。

在最后階段，我們需要計(jì)算8個(gè)指標(biāo)項(xiàng)相對(duì)于總目標(biāo)的權(quán)重分布，再結(jié)合表4中的標(biāo)度值，求出3個(gè)節(jié)點(diǎn)最終相對(duì)于總目標(biāo)的權(quán)重(得分)，并由此做出決策判斷。為減少層次分析法中主觀判斷的誤差影響，提高策略的魯棒性，我們采用主成分分析法來確定8個(gè)指標(biāo)項(xiàng)相對(duì)于總目標(biāo)的權(quán)重分布。

2.3 主成分分析法的實(shí)現(xiàn)

我們使用SPSS(Statistical Product and Service Solutions)軟件對(duì)表4內(nèi)的數(shù)據(jù)進(jìn)行主成分分析，首先將原始數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，根據(jù)公式3，將其轉(zhuǎn)化為均值為0，方差為1的無量綱數(shù)據(jù)，其結(jié)果如表5所示。

表3 C1～C8各指標(biāo)表現(xiàn)情況

(3)

式中k為樣本數(shù)，i為指標(biāo)數(shù)，且：

表4 3個(gè)存儲(chǔ)結(jié)點(diǎn)的 C1～C8指標(biāo)表現(xiàn)情況

表5 原始數(shù)據(jù)的標(biāo)準(zhǔn)化處理結(jié)果

由表5，可根據(jù)公式(4)求得其相關(guān)系數(shù)矩陣X：

式中：

(4)

令|X-λI|=0，即可解出X的p個(gè)非負(fù)特征根λi(i=1,2,…,p)，且滿足λ1≥λ2≥…≥λp≥0，每個(gè)特征根都表示對(duì)應(yīng)主成分的方差，計(jì)算結(jié)果如表6所示。

表6 主成分分析結(jié)果

表7 第一與第二主成分的成分矩陣

由表6中數(shù)據(jù)可知，第一主成分與第二主成分的方差總占比達(dá)到了100%≥85%，由此我們即可使用第一與第二主成分這兩個(gè)綜合指標(biāo)來代替原來的8個(gè)指標(biāo)。最后，綜合表7數(shù)據(jù)，即可得到主成分的表達(dá)式：

F1=0.415 8C1-0.394 2C2+0.410 5C3

-0.135 7C4-0.378 0C5+0.415 8C6

+0.332 1C7-0.242 2C8

F2=0.072 1C1-0.251 5C2+0.140 9C3

+0.719 7C4+0.323 9C5+0.072 1C6

+0.461 7C7+0.620 1C8

最后，我們將3個(gè)存儲(chǔ)節(jié)點(diǎn)的各指標(biāo)數(shù)值代入F1、F2，且令F=F1+F2，最終可得到3個(gè)存儲(chǔ)節(jié)點(diǎn)的評(píng)分，如圖2所示。可知在所設(shè)計(jì)的3個(gè)存儲(chǔ)節(jié)點(diǎn)中，節(jié)點(diǎn)2得分最高，最適合作為數(shù)據(jù)的存儲(chǔ)節(jié)點(diǎn)。

圖2 3個(gè)節(jié)點(diǎn)的最終得分比較

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

本實(shí)驗(yàn)對(duì)文中提出的云存儲(chǔ)資源調(diào)度策略的有效性進(jìn)行了分析，實(shí)現(xiàn)了策略的代碼設(shè)計(jì)，完成實(shí)驗(yàn)測(cè)試。

實(shí)驗(yàn)硬件環(huán)境：Intel Core i7- 6700HQ四核處理器，8 GB內(nèi)存，Linux Ubuntu 14.04 LTS操作系統(tǒng)。

軟件環(huán)境：Kdevelop編譯器，C++語言。

實(shí)驗(yàn)數(shù)據(jù)集：程序中設(shè)計(jì)CloudStrogeNode類與CloudMessage類來分別實(shí)現(xiàn)數(shù)據(jù)中心的存儲(chǔ)節(jié)點(diǎn)以

及存儲(chǔ)的數(shù)據(jù)。

CloudStrogeNode類：為重點(diǎn)體現(xiàn)調(diào)度策略的影響，本文將所有的存儲(chǔ)節(jié)點(diǎn)的固有屬性(I/O速率以及節(jié)點(diǎn)故障率)設(shè)置為相同的定值，其他指標(biāo)均由隨機(jī)函數(shù)生成。

CloudMessage類：主要包括距離以及數(shù)據(jù)大小兩個(gè)指標(biāo)，均由隨機(jī)函數(shù)生成。

第一數(shù)據(jù)集：實(shí)驗(yàn)中共實(shí)例化生成100個(gè)不同的CloudStrogeNode類實(shí)例以及1 000個(gè)不同的CloudMessage類實(shí)例，即需要將1 000個(gè)數(shù)據(jù)包存儲(chǔ)到100個(gè)存儲(chǔ)節(jié)點(diǎn)之中。

第二數(shù)據(jù)集：實(shí)驗(yàn)中共實(shí)例化生成500個(gè)不同的CloudStrogeNode類實(shí)例以及3000個(gè)不同的CloudMessage類實(shí)例，即需要將3 000個(gè)數(shù)據(jù)包存儲(chǔ)到500個(gè)存儲(chǔ)節(jié)點(diǎn)之中。

每次實(shí)驗(yàn)測(cè)試的結(jié)果為數(shù)據(jù)存儲(chǔ)完成時(shí)的耗時(shí)t，并非程序的運(yùn)行時(shí)間，t主要由CloudStrogeNode以及CloudMessage的相關(guān)指標(biāo)計(jì)算得到，且Cinder策略與本文策略采用相同的計(jì)算方式。

為模擬云環(huán)境，所有的存儲(chǔ)節(jié)點(diǎn)都會(huì)隨著數(shù)據(jù)的存儲(chǔ)而更新相關(guān)的指標(biāo)，如剩余存儲(chǔ)空間、內(nèi)存使用率、CPU使用率等等，且整個(gè)進(jìn)程采取并行的方式運(yùn)行。本實(shí)驗(yàn)使用不同的隨機(jī)種子，使用兩組數(shù)據(jù)集分別進(jìn)行了10組實(shí)驗(yàn)，每組實(shí)驗(yàn)中進(jìn)行了20次測(cè)試，取耗時(shí)的平均值進(jìn)行分析。

3.2 實(shí)驗(yàn)結(jié)果分析

首先，我們使用第一數(shù)據(jù)集進(jìn)行10組實(shí)驗(yàn)，測(cè)試結(jié)果如圖3所示：

圖3 使用第一數(shù)據(jù)集測(cè)試Cinder策略與本文策略的耗時(shí)

數(shù)據(jù)顯示，本文策略可有效提高存儲(chǔ)效率，其耗時(shí)平均要比Cinder策略低79%。接下來我們使用第二數(shù)據(jù)集同樣進(jìn)行10組實(shí)驗(yàn)，測(cè)試結(jié)果如圖4所示。

圖4 使用第二數(shù)據(jù)集測(cè)試Cinder策略與本文策略的耗時(shí)

由以上結(jié)果可知，Cinder策略由于只考慮節(jié)點(diǎn)的剩余存儲(chǔ)空間，未考慮到節(jié)點(diǎn)的其他各項(xiàng)指標(biāo)影響，容易出現(xiàn)耗時(shí)不穩(wěn)定的情況，而本文策略綜合考慮各項(xiàng)性能指標(biāo)，選取最優(yōu)節(jié)點(diǎn)進(jìn)行存儲(chǔ)，確保了結(jié)果的穩(wěn)定性。

4 結(jié)束語

本文在理論及實(shí)踐的基礎(chǔ)上提出了基于層次分析與主成分分析的云存儲(chǔ)資源調(diào)度策略，該策略充分考慮云存儲(chǔ)環(huán)境中的各項(xiàng)性能指標(biāo)，通過層次分析法與主成分分析法進(jìn)行定性及定量的研究，且對(duì)其進(jìn)行了代碼實(shí)現(xiàn)。經(jīng)實(shí)驗(yàn)驗(yàn)證，該策略具有有效性與良好的穩(wěn)定性，為云存儲(chǔ)源調(diào)度提供了一種全新的思路。但另一方面，該策略的缺陷在于層析分析階段，各指標(biāo)項(xiàng)的重要性分析仍具有一定的主觀性，因此，下一步的研究重點(diǎn)是建立一個(gè)客觀、科學(xué)的云存儲(chǔ)性能指標(biāo)評(píng)價(jià)標(biāo)準(zhǔn)，實(shí)現(xiàn)更加高效、可靠的云存儲(chǔ)資源調(diào)度。