公共計算環境分布式數據存儲優化策略研究*

石釗銘

（武漢市江夏區藏龍大道709號 武漢 430205）

1 引言

公共計算環境為全艦業務系統提供計算、存儲、顯控、信息接入與傳輸交互等集成保障服務，在對各基礎設備監測過程中，會產生大量的歷史數據，Hadoop 技術棧能夠為公共計算環境基礎服務平臺提供分布式數據存儲功能支撐。

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

2 Hadoop負載均衡算法

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

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

設計方法如下：

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

1）數據塊b未遷移；

2）數據塊b沒有副本；

3）數據塊副本所在的計算單元數據保持不變。

具體策略如下：

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

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

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

通過分析上述負責均衡設計的思路和實現策略，可以得出Hadoop 負載均衡方法流程是直接先行處理計算單元內的均衡，再進行計算單元間的均衡［3～5］，沒有優先處理負載超重的計算單元。

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

3 超負載處理算法

3.1 算法描述

針對計算單元集群內部承載數據量過大的計算單元，首先需要進行資源占用均衡分析，通過分析采用對應的處理方案，實施方法如下。

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

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

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

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

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

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

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

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

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

若SSj ≤1，則可以在計算單元內能夠實現均衡；若SSj＞1，則無法通過在計算單元內自行實現數據承載平衡：若SSj＞K，則表明此計算單元數據承載量超過均衡閾值，在一定程度上影響了計算單元集群的數據處理性能，待處理的優先級較高，急需作為處理對象進行承載數據均衡。

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

創建三個隊列，分別按照如下對應關系命名：PriorBalanceList（P 隊列），ForBalanceList（F 隊列），NextForBalanceList（N隊列）。

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

所有分部在P 這個隊列中的計算單元，根據上述定義分析，都歸結為承載數據量過大計算單元，根據計算得出這些計算單元的內部承載數據量偏大，按照設計思路該對象單元應該需要設定為優先處理的單元進行均衡，均衡方法中按照公式計算SSi，并且按照SSi的降序排列［9～11］。

3.2 策略設計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

假設計算得出SSj 的值≥1，就表明該計算單元j不能再承載其他均衡數據，該進程需要干預，否則計算單元j 便會出現數據承載過大的情況，應當選擇其它計算單元繼續承載遷移數據。

假設P 中沒有待處理的對象元素，則表明均衡進程已經完成。其余計算單元均衡按照原算法的實現思路完成均衡流程即可。

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

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

3.3 算法流程

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

算法輸出：無

算法偽語言描述：

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

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

3）把滿足SSi＜1 的計算單元加入到隊列F，該隊列一方面能夠完成計算單元內部的自適應均衡，另一方面還能夠將承載遷移數據的計算單元按升序在隊列中排序。

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

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

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

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

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

（4）若F 不含對象元素，執行第6）步；如果含有對象元素則跳轉到第4）步。

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

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

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

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

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

（4）若F 中不含對象元素，則跳轉到執行第8）步；否則執行第6）步。

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

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

圖1 算法流程圖

4 實驗分析

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

圖2 優先處理超負載計算單元實驗拓撲圖

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

通過實驗結果可以看出本文兩種算法進行比較。具體比較參數包括：總空間及使用率和已占用大小。

整個處理對象單元的承載均衡進程實驗分析以及處理結果如圖3、圖4所示。圖中所示的橫坐標即代表對象編號，縱坐標代表使用率。K值均為5。

表1 計算單元的初始數據存儲率

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

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

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

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

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

5 結語

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