基于網格服務的電力海量數據分布式恢復算法

常 濤 周愛華 朱韻攸 朱力鵬 饒 瑋 鄧 松

1(國網重慶市電力公司 重慶 400014)2(國網智能電網研究院 江蘇 南京 210003)3(國網重慶市電力公司信息通信分公司 重慶 401121)4(南京郵電大學先進技術研究院 江蘇 南京 210023)

?

基于網格服務的電力海量數據分布式恢復算法

常 濤1周愛華2*朱韻攸3朱力鵬2饒 瑋2鄧 松4

1(國網重慶市電力公司 重慶 400014)2(國網智能電網研究院 江蘇 南京 210003)3(國網重慶市電力公司信息通信分公司 重慶 401121)4(南京郵電大學先進技術研究院 江蘇 南京 210023)

傳統的基于糾錯碼的數據恢復算法既提高了數據存儲的可靠性，又增加了數據恢復的計算時間。為了解決這個問題，首先對整個樣本數據采用粗糙集進行約簡，然后基于網格服務思想，提出基于網格服務的電力海量數據分布式恢復算法DR-GSPMD(Distributed Recovery based on Grid Service for Power Mass Data)。仿真實驗表明針對所有測試數據集，隨著校驗碼個數的增加，整個系統的最大容錯率和數據恢復時間也隨著增加。同時針對約簡后的數據集隨著計算節點數的增加，算法降低了計算復雜度，加快了范德蒙矩陣運算的速度，減少了整個數據恢復的時間。

數據恢復 網格服務 屬性約簡

0 引 言

隨著云計算、物聯網等新型信息通信技術在智能電網中的不斷深入應用，智能電網發電、輸電、變電、配電、用電及調度等各個環節的業務系統數據呈幾何級數增長[1，2]。如何保證這些數據存儲的安全可靠性是需要解決的一個重要問題。為了解決這個問題，各類分布式存儲系統應運而生。這些基于分布式環境的存儲系統最終目標就是要使得用戶能連續且高可靠地訪問存儲數據，尤其是當存儲數據被外部攻擊或者損壞時，業務系統仍能正常運行，保證用戶的最大服務質量，這對智能電網業務系統運行，特別是與外部因特網環境直接連接的業務系統至關重要。

副本技術[3-6]就是一種通過創建數據的完整或者部分的備份，然后分布式存儲在各個網絡節點中的一種技術。這種技術具有提高數據訪問效率(可以就近訪問)、增強數據可用性、改善數據冗余性等優勢。左方等提出一種基于蟻群算法的云存儲副本動態選擇算法，實現了副本的有效分發和虛擬機集群的負載均衡[7]。針對服務質量比較敏感的用戶，文獻[8]提出一種基于QoS 偏好感知的副本選擇策略。李功麗等提出一種云計算數據副本動態管理策略[9]，通過基于用戶需求來確定副本數目以此確定副本的位置，降低平均響應時間。

但現有電力行業中的數據由于采集手段和采樣頻率的多樣化，各業務系統所包含的數據集大部分都是比較龐大的，維度較高，完全復制會帶來相當高的帶寬和存儲空間需求。在不考慮存儲經濟性的前提下，直接利用數據完全副本進行數據恢復的前提是該副本本身是完整可靠的，為了解決這個問題，很多研究者借鑒了信號處理領域的冗余容錯技術[10-12]，提出利用Erasure編碼來解決數據恢復問題，但是隨著數據量的呈幾何級數增加以及數據的高維特征，直接利用Erasure code進行編碼和解碼將耗費大量的計算時間，從而大大影響了整個數據恢復的時間，最終會影響到對實時性要求較高的電力業務系統運行。因此，本文針對電力海量數據安全存儲的實際需求，為了提高Erasure Code的編碼和解碼速度，結合屬性約簡和網格服務的思想，提出了基于網格服務的電力海量數據分布式恢復算法DR-GSPMD。

1 基于屬性約簡和Erasure Code的數據恢復算法

Erasure Code是一種典型的糾錯碼技術[10]，具有良好的容錯性和安全性。它的實現形式有很多類型，由于基于范德蒙矩陣的編碼簡單、易實現等特點，本文重點研究該RS編碼中基于范德蒙矩陣的數據恢復技術。首先給出相關的概念[10]。

定義1對于n塊子數據塊和m個校驗塊，構造如下的矩陣：

(1)

則稱式(1)為范德蒙矩陣，其中ai,i∈[1,n]可以為任意自然數。

但隨著云計算、物聯網在智能電網中的廣泛應用，越來越多的智能電網業務系統數據維度越來越高，數據量越來越大，使得在分布式存儲過程中直接基于Erasure Code進行數據恢復的時間復雜度過大，從而影響后臺業務系統所提供的服務質量。為了更快地基于Erasure Code進行數據恢復，首先需要對電力高維海量數據進行屬性降維，其方法主要包括主成份分析方法，奇異值分解法，以及粗糙集等。前兩種方法不可避免地會造成原始數據信息的部分丟失，而基于粗糙集的屬性約簡在降維的同時，并沒有改變約簡后數據的決策規則。因此本文提出基于粗糙集和Erasure Code的數據恢復算法DR-RSEC(Data Recovery algorithm based on Rough Set and Erasure Code)，首先利用粗糙集對待恢復的海量高維數據進行屬性約簡，降低其數據自身復雜度，然后再通過Erasure Code進行數據恢復計算，這樣在不改變數據本身決策能力的前提下，提高數據恢復的效率。

在介紹DR-RSEC算法之前，首先給出相關基于粗糙集的屬性約簡的定義[13]。

定義3樣本決策表SDT。設T=，其中U為樣本數據的研究對象集合，C∪D=R為樣本數據的屬性集合，C={c1,c2,…,cn}為樣本數據的條件屬性集合，D={d1,d2,…,dm}為樣本數據的決策屬性集合，V=∪vr,r∈R是樣本數據屬性值的集合，vr表示某一個屬性r∈R的屬性值范圍，f:U×R→V定義一個信息函數，它指定U中每一對象x的屬性值，即對于?r∈R,x∈U，有f(x,r)∈vr。稱滿足上述條件的T為樣本決策表。

定義4對于?P?R,且x，y∈U，當且僅當對于?r∈P，f(x,r)=f(y,r)時，x和y是不可分辨的，也即：IND(P)={(x,y)∈U|?r∈P,f(x,r)=f(y,r)}。

定義5設樣本決策表T=，對于相同的條件屬性值，其對應的決策屬性值也相同，則稱樣本決策表T是協調的。

整個基于粗糙集和Erasure Code的數據恢復算法DR-RSEC的形式化描述如算法1所示。

算法1DR-RSEC

Input: 原始數據集Odata，n個數據塊，校驗碼個數m；

Output: 恢復后的數據RData；

Begin

1. 針對原始數據集Odata，構造樣本決策表T=；

2. for (c∈C) {

3. if (rC-{c}(D)=1)C=C-{c}；}

4. 得到約簡后的T=；

5. 將約簡后的樣本數據集分割為n塊；

6. 根據分割塊數n和校驗碼個數m，分別構造范得蒙矩陣Fm×n以及分割后的數據矩陣Dn×1；

7. 校驗碼矩陣Cm×1=Fm×n×Dn×1；

9. if (n塊數據子塊中有p塊受損) {

10. if (p<=m) {

12. RData==Merger(Dn×1)；}

13. else {print (“不可恢復！”)}

14. Return RData.

算法1的時間復雜度為O(n(m+n)+|U||C|)，主要集中在屬性約簡和矩陣運算中。隨著數據量和數據維度的增大，以及分割塊數和校驗碼個數的增加，整個算法的時間復雜度將會急劇增加，這勢必將影響到數據恢復的時間。

2 基于網格服務的電力海量數據分布式恢復算法

2.1 算法思想

為了解決傳統的Erasure code的海量計算的問題，本文在算法1的基礎上，結合網格服務的思想，提出了基于網格服務的電力海量數據分布式恢復算法DR-GSPMD。通過網格服務，來構造并行分布式計算平臺，大大減少了計算的時間，提高了數據恢復的效率。

DR-GSPMD算法的主要思想就是首先利用粗糙集對原始數據集進行屬性約簡；然后根據分割塊數和校驗碼個數來分別構造范得蒙矩陣、分割后的數據矩陣以及計算恢復所需的其他矩陣，接著把按照行對每一個矩陣進行分解，然后把分解后的各個子矩陣分別傳輸到各個網格節點中；其次編寫相關矩陣的乘運算以及求逆運算的網格服務，并把該網格服務部署到相應的服務端；然戶分別把相應矩陣運算網格服務所需的參數通過數據傳輸服務傳輸到指定的服務端；最后客戶端通過門戶并行地調用和執行各網格服務，并把處理后的最終結果返回給客戶端。

2.2 算法描述

基于網格服務的分布式數據恢復算法主要就是把數據恢復中的有關矩陣運算進行分解，然后利用網格服務來并行化處理這些計算，從而提高計算的效率。整個算法的描述如下所示：

算法2基于網格服務的電力海量數據分布式恢復算法DR-GSPMD

Input: 原始數據集Odata，n個數據塊，校驗碼個數m；

Output: 恢復后的數據RData；

Begin {

1. 客戶端首先根據原始數據集，基于粗糙集進行屬性約簡，求解得到約簡后的待分割數據集；

2. 基于約簡后的待分割數據集，根據分割塊數和校驗碼個數，分別構造范得蒙矩陣Fm×n以及分割后的數據矩陣Dn×1；

3. 根據部署矩陣乘算法網格服務的節點個數，分解Fm×n和Dn×1，然后把分解后的各個子矩陣分別傳送到各個算法服務的節點上；

4. 對于每一個網格服務節點，并行進行矩陣相乘，最后傳輸到客戶端進行合并成校驗碼矩陣Cm×1；

6. if (n塊數據子塊中有p塊受損) {

7. if (p<=m) {

8. 將p個數據子塊對應的矩陣A(n+m)×n和E(n+m)×1中的行刪除掉，得到新的矩陣A(n+m-p)×n和E(n+m-p)×1；

11. 對于每一個網格服務節點，并行進行矩陣相乘，最后傳輸到客戶端進行合并成數據矩陣Dn×1；

12. RData=Merger (Dn×1)；}

13. Return RData；

算法2的通信開銷主要集中在各個網格節點之間傳輸數據子矩陣、各個矩陣相乘的耗時，同時由于對各個矩陣分解后利用網格服務進行并行運算，故整個算法的時間復雜度大大減少。整個恢復過程是利用矩陣乘算法服務以及矩陣求逆算法服務協同工作，大大提高了矩陣求解的效率，節約了數據恢復的時間。

3 實驗與分析

為了證明DR-GSPMD算法的有效性，本文在實驗室環境下做了仿真實驗分析。整個實驗平臺為P4 1.8 GHz+512 MB+Java+Windows XP+WS-Core 4.0.2，所有的程序由Java語言實現。其中包括5臺計算節點，每個節點配置為2×E5-2620v2 CPU,128 GB內存以及2×4 TB硬盤。為了說明算法的有效性，本文的數據源主要包括隨機產生大小分別為100 MB、500 MB、1 GB和50G的三個數據集和來自國家電網公司某業務系統2006年-2012年的網絡安全日志數據約1.5 GB。整個實驗數據的屬性如表1所示。

表1 實驗數據集

實驗1針對表1中所示的實驗數據集，表2給出了屬性約簡后的各個數據集的屬性個數。圖1給出了當數據分割塊數固定時，隨著產生校驗碼個數的增加，數據集最大容錯率的變化情況。圖2則給出了當數據塊數為5，隨著校驗碼個數的增加，上述5個數據集約簡前的恢復算法的計算耗時的變化情況。圖3給出了當數據分割塊數為5，校驗碼個數為3時，約簡前后的數據恢復算法的計算耗時比較。

表2 基于粗糙集的數據集屬性約簡前后條件屬性個數變化

圖1 不同數據塊條件下最大容錯率隨著校驗碼數變化的情況

圖2 不同校驗碼個數條件下五個數據集的數據恢復算法耗時

圖3 約簡前后的數據恢復算法的計算耗時比較

從表2中可以看出針對表1中的5個測試數據集而言，約簡后的條件屬性個數分別下降了62.5%、54.55%、75%、84.09%、72.73%。從圖1中可以看出，隨著校驗碼個數的增加，整個系統的最大容錯率也隨著增加，而最大容錯率的增加表明了整個恢復系統的可靠性增加，允許有更多的數據子塊的丟失。而圖2則表明當數據塊數為5時，隨著校驗碼個數的增加，表1中五個數據集的數據恢復算法平均計算耗時分別增加了27.42、51.07、21.93、21.17、21.81倍。這是因為隨著校驗碼個數和數據集大小的增加，構造的范得蒙矩陣、數據矩陣以及校驗碼矩陣的復雜度也隨之增加，從而使得整個算法花費大量的時間在矩陣的運算中。圖3則顯示當數據分割塊數為5，校驗碼個數為3時，通過對表1中所示的五個數據集進行屬性約簡，大大降低了表1中五個數據集恢復算法的計算耗時。

實驗2由實驗1可以看出，較多的校驗碼個數可以保證數據存儲的高可靠性，但同時也增加了數據恢復的計算耗時。為了很好地解決這個問題，實驗2利用網格服務設計并行數據恢復算法DR-GSPMD，在保證數據存儲高可靠性的同時，也極大地降低了數據恢復的時間。圖4表明了當分割塊數n=5，校驗碼個數m=4時，隨著節點數目的增加，數據恢復的計算耗時變化情況。

圖4 不同計算節點個數條件下5個數據集恢復的平均耗時

從圖4中可以看出，在分割塊數為5，校驗碼個數為4的條件下，隨著計算節點的增加，五個隨機數據集的平均恢復時間分別最大降低56.88%、43.19%、26.08%、62.28%、46.58%。這主要是因為在分割塊數和校驗碼個數確定的情況下，恢復所有的計算都集中在矩陣的乘法和求逆運算，而DR-GSPMD算法利用網格服務使得矩陣的乘法和求逆計算并行化，加快了整個矩陣的運算，最終導致整個恢復時間的下降。

4 結 語

本文在傳統基于Erasure code的數據恢復算法基礎上，結合網格服務和屬性約簡的思想，提出了基于網格服務的電力海量數據分布式恢復算法DR-GSPMD。首先利用屬性約簡降低原始數據維度從而減少數據恢復算法的計算耗時；同時對于數據恢復算法中的大量的矩陣乘法和求逆運算，DR-GSPMD設計了相應的網格服務，使得數據恢復中的各種矩陣運算并行化。仿真實驗表明，隨著節點的增加，DR-GSPMD算法加快了矩陣計算的速度，減少了整個數據恢復的時間。

[1] 秦立軍, 馬其燕. 智能配電網及其關鍵技術[M].北京：中國電力出版社, 2010.

[2] Nouredine Hadjsaid.有源智能配電網[M].陶順, 肖湘寧, 彭騁,譯.北京：中國電力出版社, 2013.

[3] Ranganathan K, Foster I. Identifying Dynamic Replication Strategies for a High Performance Data Grid[C]//Proceeding of the Second International workshop on Grid Computing, Denver, November, 2001:75-86.

[4] 楊濤.數據網絡中復制管理研究[D].北京：中國科學技術大學，2007.

[5] Rahman R M, Alhajj R, Barker K. Replica selection strategies in data grid[J].Journal of Parallel and Distributed Computing, 2008,68(12):1561-1574.

[6] Al Mistarihi H H E, Yong C H. On fairness, optimizing replica selection in data grids[J].IEEE Transactions on Parallel and Distributed Systems, 2009,20(8):1102-1111.

[7] 左方, 何欣. 一種基于蟻群算法的云存儲副本動態選擇機制研究[J].計算機應用研究,2015,32(11):3368-3370,3374.

[8] 熊潤群, 羅軍舟, 宋愛波,等.云計算環境下QoS偏好感知的副本選擇策略[J]. 通信學報, 2011,32(7):93-102.

[9] 李功麗, 趙曉焱, 劉慧.一種云計算數據副本動態管理策略[J].河南師范大學學報：自然科學版,2015, 43(4):138-143.

[10] 羅象宏, 舒繼武.存儲系統中的糾刪碼研究綜述[J].計算機研究與發展, 2012,49(1):1-11.

[11] 毛波, 葉閣焰, 藍琰佳,等.一種基于重復數據刪除技術的云中云存儲系統[J].計算機研究與發展,2015,52(6):1278-1287.

[12] 潘利偉,谷建華,朱靖飛,等.基于Erasure Code 的分布式文件存儲系統[J].計算機工程,2010,36(17):45-47.

[13] Pawlak Z. Rough sets[J].International Journal of Computer and Information Sciences,1982,11(5):341-356.

DISTRIBUTED RECOVERY ALGORITHM FOR MASSIVE POWER DATA BASED ON GRID SERVICE

Chang Tao1Zhou Aihua2*Zhu Yunyou3Zhu Lipeng2Rao Wei2Deng Song4

1(State Grid Chongqing Electric Power Company, Chongqing 400014, China)2(State Grid Smart Grid Research Institute, Nanjing 210003,Jiangsu, China)3(State Grid Chongqing Information and Telecommunication Company, Chongqing 401121, China)4(Nanjing University of Posts and Telecommunications, Nanjing 210023,Jiangsu, China)

Traditional error-correcting code-based data recovery algorithm improves the reliability of data storage but increases the computational time of data recovery as well. To solve this problem, we first employed the rough set to carry out reduction on entire sample data, and then proposed the grid service-based distributed recovery algorithm for massive power data (DR-GSPMD), which is based on the idea of grid services. Simulation experiments showed that for all test datasets, the maximum error rate and data recovery time of whole system increases along with the augment in numbers of check node. Meanwhile, aiming at the problem that the reduced datasets increases along with the augment in numbers of computational nodes, DR-GSPMD reduces the computing complexity, speeds up the calculation of Vandermonde matrix and decreases the time of entire data recovery.

Data recovery Grid service Attribution reduction

2015-09-24。國家自然科學基金項目(51507084)。常濤，高工，主研領域：電力信息化。周愛華，工程師。朱韻攸，工程師。朱力鵬，工程師。饒瑋，工程師。鄧松，高工。

TP3

A

10.3969/j.issn.1000-386x.2016.11.047