公共計算環(huán)境分布式數(shù)據(jù)存儲優(yōu)化策略研究*

石釗銘

（武漢市江夏區(qū)藏龍大道709號 武漢 430205）

1 引言

公共計算環(huán)境為全艦業(yè)務(wù)系統(tǒng)提供計算、存儲、顯控、信息接入與傳輸交互等集成保障服務(wù)，在對各基礎(chǔ)設(shè)備監(jiān)測過程中，會產(chǎn)生大量的歷史數(shù)據(jù)，Hadoop 技術(shù)棧能夠?yàn)楣灿嬎悱h(huán)境基礎(chǔ)服務(wù)平臺提供分布式數(shù)據(jù)存儲功能支撐。

Hadoop 分布式存儲通過自身負(fù)載均衡程序完成均衡［1］。但該負(fù)載均衡算法并沒有優(yōu)先處理負(fù)載超重的計算單元，在多節(jié)點(diǎn)的計算單元集群中負(fù)載均衡的效率有待提高。

2 Hadoop負(fù)載均衡算法

針對負(fù)載不均的情形，Hadoop 提供一套針對方案，該方案中設(shè)計了一種算法，算法定義了一個閾值參數(shù)。通過該參數(shù)來對比Hadoop 平臺各計算單元的實(shí)際數(shù)據(jù)占用率。如果占用率高于該定義值，則說明該處理對象承載的數(shù)據(jù)量過大，需要被均衡處理；如果占用率低于該自定義值，則說明該處理對象單元已經(jīng)達(dá)到均衡狀態(tài)。

定義四個鏈表用于存放計算單元對象，依次分別存放承載數(shù)據(jù)量過大計算單元、超過平均值且不是承載數(shù)據(jù)量過大的計算單元、低于平均值且不是非常低的計算單元和非常低的計算單元，通過Hadoop 負(fù)責(zé)均衡設(shè)計思路和實(shí)現(xiàn)方法可以逐個將各對象單元的負(fù)載達(dá)到一個平衡狀態(tài)［2］。各對象單元負(fù)載實(shí)現(xiàn)均衡狀態(tài)后，能夠顯著提高整個計算單元集群承載能力，在數(shù)量相同的情況下，可以承擔(dān)更多業(yè)務(wù)的處理能力和數(shù)據(jù)的存儲存儲能力。

設(shè)計方法如下：

假設(shè)把兩個數(shù)據(jù)單元作為處理對象，分別標(biāo)號為S、T，把S 中的數(shù)據(jù)b 遷移到T 中，滿足以下條件即可：

1）數(shù)據(jù)塊b未遷移；

2）數(shù)據(jù)塊b沒有副本；

3）數(shù)據(jù)塊副本所在的計算單元數(shù)據(jù)保持不變。

具體策略如下：

1）假設(shè)S 與T 屬于同一計算單元，則可以遷移b。理由是數(shù)據(jù)塊b的位置沒有跨計算單元：

2）遍歷b 的副本，假設(shè)副本的位置與T 在同一計算單元，則繼續(xù)判斷步驟3），否則可以遷移數(shù)據(jù)塊b；

3）遍歷數(shù)據(jù)塊b 的副本，假設(shè)有副本與S 在同一計算單元內(nèi)，并且通過分析得出此副本不在S上，則可以遷移數(shù)據(jù)塊b。

通過分析上述負(fù)責(zé)均衡設(shè)計的思路和實(shí)現(xiàn)策略，可以得出Hadoop 負(fù)載均衡方法流程是直接先行處理計算單元內(nèi)的均衡，再進(jìn)行計算單元間的均衡［3～5］，沒有優(yōu)先處理負(fù)載超重的計算單元。

設(shè)想在一個計算單元M中，包含大多數(shù)負(fù)載重的數(shù)據(jù)單元（up 單元），只有很少的空閑數(shù)據(jù)單元（off 或down 單元），該計算單元的承載數(shù)據(jù)明顯超過均值，在此計算單元中只將up 單元上的負(fù)載遷移到off 和down 單元，理論上無法實(shí)現(xiàn)較好的均衡效果，必須通過負(fù)載遷移來解決該計算單元負(fù)載承重過高的情形，針對該種情景，Hadoop 處理的應(yīng)對方案是第一步在計算單元內(nèi)部實(shí)行均衡算法，循序遍歷的去處理每一個待處理的承載過高的對象單元，逐個將這些對象單元實(shí)現(xiàn)承載數(shù)據(jù)平衡，統(tǒng)計分析可以得出，該過程會顯著延長計算單元全部實(shí)現(xiàn)均衡的時間［6～8］。

3 超負(fù)載處理算法

3.1 算法描述

針對計算單元集群內(nèi)部承載數(shù)據(jù)量過大的計算單元，首先需要進(jìn)行資源占用均衡分析，通過分析采用對應(yīng)的處理方案，實(shí)施方法如下。

定義計算單元i的磁盤使用率Pi：Pi=Ui/Ti。其中Ui 是計算單元i 的已使用空間，Ti 是計算單元i的總空間大小。

m 表示每個計算單元的平均空間占有率。定義變量m，計算方法為m=Aui/Ati。該計算公式中，變量Aui表示所有計算單元的總空間中已經(jīng)使用的占有量，Ati表示全部所有計算單元的用量總空間。

定義閾值變量K：針對每個計算單元負(fù)載運(yùn)行情況，用戶可以自定義設(shè)定此閾值的值，并優(yōu)先處理承載高于該閾值的對象單元。

定義on 計算單元：假設(shè)計算單元i 滿足公式m＜Pi≤m+ts，則這個計算單元為on 計算單元。該計算公式中，ts為自定義閾值。

up 計算單元：假設(shè)計算單元i 滿足公式Pi＞m+ts，則這個計算單元可設(shè)定為up計算單元。

off 計算單元：假設(shè)計算單元i 滿足公式m-ts ≤Pi＜m，則這個計算單元可設(shè)定為off計算單元。

down 計算單元：假設(shè)計算單元i 滿足公式m-ts＞Pi，則這個計算單元可設(shè)定為down 計算單元。

定義變量Ei，Ei 表示第i 個計算單元在承載過大情形下的數(shù)據(jù)存儲總量值。

依次順序排列第j 個計算單元，假設(shè)該對象單元承載過大情形下的均衡值為SSj：SSj=L/Gj。

若SSj ≤1，則可以在計算單元內(nèi)能夠?qū)崿F(xiàn)均衡；若SSj＞1，則無法通過在計算單元內(nèi)自行實(shí)現(xiàn)數(shù)據(jù)承載平衡：若SSj＞K，則表明此計算單元數(shù)據(jù)承載量超過均衡閾值，在一定程度上影響了計算單元集群的數(shù)據(jù)處理性能，待處理的優(yōu)先級較高，急需作為處理對象進(jìn)行承載數(shù)據(jù)均衡。

定義變量Osj，該變量表示第j個計算單元在承載數(shù)據(jù)量過大情形下的均衡能力。OSj=Ej/Gj。

創(chuàng)建三個隊(duì)列，分別按照如下對應(yīng)關(guān)系命名：PriorBalanceList（P 隊(duì)列），F(xiàn)orBalanceList（F 隊(duì)列），NextForBalanceList（N隊(duì)列）。

把SSi＜1 的計算單元存放在隊(duì)列F 中；把SSi＞1且OSi＜1 的計算單元存放在隊(duì)列N 中；把SSi＞K 的計算單元存放在隊(duì)列P中。

所有分部在P 這個隊(duì)列中的計算單元，根據(jù)上述定義分析，都?xì)w結(jié)為承載數(shù)據(jù)量過大計算單元，根據(jù)計算得出這些計算單元的內(nèi)部承載數(shù)據(jù)量偏大，按照設(shè)計思路該對象單元應(yīng)該需要設(shè)定為優(yōu)先處理的單元進(jìn)行均衡，均衡方法中按照公式計算SSi，并且按照SSi的降序排列［9～11］。

3.2 策略設(shè)計

設(shè)定一閾值K，該值可以按照用戶需要自定義設(shè)定，用于分析并確定給出的計算單元的運(yùn)行情況，判定是否為承載過大計算單元。

針對每一個計算單元，定義變量SSi。該變量表示計算單元在內(nèi)部機(jī)制下的平衡能力，計算公式為SSi=Li/Gi。

為使計算單元i在均衡進(jìn)程中達(dá)到一定的時間要求，設(shè)定被均衡的對象單元遷移的數(shù)據(jù)總量為Li，Gi是對象計算單元i能承載的的總數(shù)據(jù)量［12～14］。

若SSi ≤1，表示在均衡過程中，被均衡的計算單元內(nèi)部需要遷移出的數(shù)據(jù)總量小于它所能承載的量。即說明此計算單元能夠自行完成自適應(yīng)承載平衡。

若SSi＞1，表示在均衡過程中，被均衡的計算單元內(nèi)部需要遷移出的數(shù)據(jù)量大于它可承載的量，即說明該對象單元內(nèi)不能夠自行實(shí)現(xiàn)并完成均衡進(jìn)程，必須把部分?jǐn)?shù)據(jù)遷移到其它對象計算單元中去。

若SSi＞K，表示均衡過程中被均衡的對象計算單元內(nèi)能夠承載的量大幅低于需要處理的數(shù)據(jù)總量，即說明該對象計算單元承載數(shù)據(jù)量偏大，需要設(shè)定處理優(yōu)先級來完成承載量均衡，按照均衡方法立即處理。

定義變量Osi，該變量表示計算單元i的負(fù)載自平衡能力。計算公式為OSi=Ei/Gi。

假設(shè)此值低于1，表示此計算單元中承載的數(shù)據(jù)總量少于能夠承載的容量，能夠提供使得該計算單元中的up 計算單元達(dá)到均衡的空余條件，可以作為均衡時承載數(shù)據(jù)的對象單元。

P 中存放需要首先均衡的承載量過大計算單元（SSi＞K的計算單元）。

F 中存放自身能夠完成承載平衡并且還能承載其他數(shù)據(jù)的對象計算單元（SSi＜1）。

N 中存放承載過大并且能在該對象計算單元內(nèi)完成均衡的計算單元（OSi＜1）。

處理邏輯是P 隊(duì)列降序排列，將該隊(duì)列中負(fù)載最大的計算單元第一時間做均衡處理。

計算單元i 選自P 隊(duì)列，在F 隊(duì)列中選取一個計算單元設(shè)為j，把i均衡后還需遷移的數(shù)據(jù)遷移到j(luò)。并分別在遷移策略算法中計算Ei及SSj的值。

通過上述計算方法，如果得出Ei 等于0，就表明已完成對計算單元i的處理，同時觸發(fā)任務(wù)，停止i與j之間的均衡進(jìn)程。

假設(shè)計算得出SSj 的值≥1，就表明該計算單元j不能再承載其他均衡數(shù)據(jù)，該進(jìn)程需要干預(yù)，否則計算單元j 便會出現(xiàn)數(shù)據(jù)承載過大的情況，應(yīng)當(dāng)選擇其它計算單元繼續(xù)承載遷移數(shù)據(jù)。

假設(shè)P 中沒有待處理的對象元素，則表明均衡進(jìn)程已經(jīng)完成。其余計算單元均衡按照原算法的實(shí)現(xiàn)思路完成均衡流程即可。

假設(shè)F 中沒有待處理的對象元素，則表明進(jìn)程繼續(xù)從N中處理其他計算單元來承載均衡數(shù)據(jù)。

基于Hadoop 的設(shè)計算法，本文的設(shè)計算法著重于首先處理數(shù)據(jù)量承載過大的計算單元，升級了Hadoop 算法的策略，把隨機(jī)選取的模式改為優(yōu)先選擇承載過大計算單元作為被均衡的對象單元來進(jìn)行處理［15］。

3.3 算法流程

算法輸入：各個計算單元的磁盤使用率

算法輸出：無

算法偽語言描述：

1）按照上述設(shè)計的計算公式和分析策略，分別得出計算單元i的Li、Gi、SSi、Ei及Osi的值。

2）把滿足SSi＞K 的計算單元加入到隊(duì)列P，將優(yōu)先需要處理的對象元素存放在該隊(duì)列中。

3）把滿足SSi＜1 的計算單元加入到隊(duì)列F，該隊(duì)列一方面能夠完成計算單元內(nèi)部的自適應(yīng)均衡，另一方面還能夠?qū)⒊休d遷移數(shù)據(jù)的計算單元按升序在隊(duì)列中排序。

4）分別從P 隊(duì)列和F 隊(duì)列各取一個計算單元，假設(shè)為j和k。對于計算單元j，首先分析該計算單元內(nèi)部的均衡情況，完成內(nèi)部的自適應(yīng)均衡，然后分析計算單元j 和k 間的總數(shù)據(jù)量承載情況，完成單元間的承載平衡，循環(huán)執(zhí)行進(jìn)程，直到進(jìn)程結(jié)果計算得出Ej=0或著計算得出SSk ≥1。

5）分別按照上述方法計算自定義變量Ej、自定義變量SSk和OSk的值，

（1）若Ej=0，在P中刪除計算單元j；

（2）若SSk ≥l，在F 中刪除計算單元k，若OSk＜l，把k 加入到N隊(duì)列中，升序排列此隊(duì)列；

（3）若P不含對象元素，執(zhí)行第9）步；

（4）若F 不含對象元素，執(zhí)行第6）步；如果含有對象元素則跳轉(zhuǎn)到第4）步。

6）分別從P 和N 中取一個計算單元，假設(shè)為j 和k。對于計算單元j，第一步分析計算單元內(nèi)部的均衡情況，完成單元內(nèi)部的均衡，第二步在計算單元j 和k 之間進(jìn)行承載平衡，循環(huán)執(zhí)行進(jìn)程直到計算得出Ej=0 或著計算得出OSk ≥10。

7）計算新的定義值Ej和Osk。

（1）若Ej=0，從P中刪除對象計算單元j；

（2）若OSk ≥1，從F中刪除對象計算單元k；

（3）若P中不含對象元素，執(zhí)行第9）步：

（4）若F 中不含對象元素，則跳轉(zhuǎn)到執(zhí)行第8）步；否則執(zhí)行第6）步。

8）通過計算得出承載數(shù)據(jù)量過大的計算單元數(shù)目過多，則自定義設(shè)置閾值K。

9）完成上述分析和實(shí)現(xiàn)過程后，剩下的均衡情形和處理對象，其均衡過程基于Hadoop 的實(shí)現(xiàn)流程處理便可完成。

圖1 算法流程圖

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

測試環(huán)境如圖2所示，包括計算單元A、計算單元B、計算單元C三個計算單元：計算單元A中配置三個數(shù)據(jù)單元A1、A2、A3，計算單元B 配置B1、B2、B3三個數(shù)據(jù)單元，計算單元C配置C1、C2兩個數(shù)據(jù)單元。

圖2 優(yōu)先處理超負(fù)載計算單元實(shí)驗(yàn)拓?fù)鋱D

自定義每個HDFS 數(shù)據(jù)件塊在單元內(nèi)部存儲系統(tǒng)中的大小為10M。實(shí)驗(yàn)中各計算單元的本地配置如：操作系統(tǒng)、cpu 和內(nèi)存均保持一致，保證實(shí)驗(yàn)過程中非影響元素的統(tǒng)一性。

通過實(shí)驗(yàn)結(jié)果可以看出本文兩種算法進(jìn)行比較。具體比較參數(shù)包括：總空間及使用率和已占用大小。

整個處理對象單元的承載均衡進(jìn)程實(shí)驗(yàn)分析以及處理結(jié)果如圖3、圖4所示。圖中所示的橫坐標(biāo)即代表對象編號，縱坐標(biāo)代表使用率。K值均為5。

表1 計算單元的初始數(shù)據(jù)存儲率

圖3 threshold為10%的空間使用率

圖4 threshold為15%的空間使用率

計算單元A 中包含三個承載過大數(shù)據(jù)單元，分別定義為A1、A2、A3。計算單元B 中的數(shù)據(jù)單元B3以及計算單元C的全部數(shù)據(jù)單元均為低負(fù)載對象。

圖3 中本文算法數(shù)據(jù)分布更均衡。用時6.89min。Hadoop算法整個數(shù)據(jù)量承載均衡進(jìn)程執(zhí)行完成，計算出用時大約為7.46min。在A1 對象計算單元完成數(shù)據(jù)量承載均衡時，本文算法耗時大約為2.43min。

圖4 中，Hadoop 算法在5.89min 完成數(shù)據(jù)量承載平衡，本文算法用時略多，但能夠更快地實(shí)現(xiàn)計算單元A1 中各數(shù)據(jù)單元之間的均衡，提高各數(shù)據(jù)單元的數(shù)據(jù)量承載均衡效率。

5 結(jié)語

計算單元存儲負(fù)載均衡是公共計算領(lǐng)域的一個重要研究課題。Hadoop 平臺能夠在較多計算單元集群的應(yīng)用場景中，高效地處理和存儲海量數(shù)據(jù)。該平臺自身負(fù)載均衡算法在面對有承載過大計算單元的情形時，實(shí)現(xiàn)跨計算單元的快速均衡的效率有待提升，針對該情形，本文設(shè)計并提出了一種改進(jìn)的數(shù)據(jù)量承載平衡思路，該設(shè)計以Hadoop本身平衡策略為基礎(chǔ)，加以改進(jìn)和優(yōu)化。驗(yàn)證了該優(yōu)化策略能夠更快地處理數(shù)據(jù)量承載過大的計算單元，縮短了承載過大計算單元負(fù)載均衡時間，提高了全系統(tǒng)負(fù)載均衡效率。