海量小數據分布式聚類優化與負載均衡算法

汪明明,陳慶奎,b

(上海理工大學 a.光電信息與計算機工程學院; b.管理學院,上海 200093)

0 概述

隨著物聯網技術的發展,各種傳感器和嵌入式設備都在時刻產生數據,必然會遇到海量物聯網數據高效存儲的問題。由于物聯網數據是海量的和異構的[1],因此傳統的關系型數據庫并不適合海量物聯網數據的存儲場景。

隨著Hadoop生態圈的成熟和分布式文件系統的廣泛使用,現已有許多關于海量數據的解決方案[2-5]。然而文獻[2]方案并未對小數據進行優化,文獻[3]方案在小數據量大時存在索引過大問題,文獻[4-5]方案主要適用于單個文件較大的情況(一般Hadoop分布式文件系統(Hadoop Distributed File System,HDFS)的文件塊大小為64 MB),在單個文件較小時讀寫性能較差,但是大部分傳感器采集到的數據是小數據,如溫度、濕度、地理位置等。雖然Hadoop采用了Har File[6]和Hadoop順序文件[7]將多個小文件合并成大文件對小數據進行優化,然而性能較差。此外,文獻[8-11]提出了基于小數據文件特征的優化方法,但僅針對特殊文件格式和內容的數據,不具有通用性。

文獻[12]設計了SensorFS系統。該系統使用了把相似傳感器的數據合并成同一個大文件的方案,從而最優化讀寫吞吐量。同時,其在HDFS上層提出了DMFS來實現基于內存的分布式寫緩存和分布式文件合并,具有很好的讀寫性能。但SensorFS的傳感依賴圖(Sensing Dependency Graph,SDG)建立過程和基于SDG的傳感器聚類過程都在主節點(Master)進行操作,這使得Master節點在傳感器量很大的情況下會成為性能瓶頸。此外,該文獻給出基于內存和CPU使用率的粗粒度的負載均衡方案,并不能很好地實現集群內部的負載均衡。

針對SensorFS集中式傳感器聚類算法存在的問題,本文提出分布式算法,在海量傳感器的情況下提高聚類速度并且減輕Master節點內存負擔。此外,考慮到良好的負載均衡能有效提升系統整體性能和穩定性[13-15],本文針對各個傳感器不同的文件傳送速率,以傳感類為單位提出一種細粒度的負載均衡算法。

1 相關研究

文獻[12]中基于SDG的傳感器聚類算法可以有效地把相似的傳感器數據合并成同一HDFS文件塊,從而實現讀寫最優化。SDG的原理為通過計算傳感器兩兩之間的相似度和依賴關系來構造有向加權圖,而基于SDG的聚類算法則是根據構造出的有向加權圖對傳感器進行分類。圖1為SensorFS系統架構,從中可以看出,寫調度和傳感器聚類都在Master節點上執行,即表明Master節點不僅要緩存ChunkServer和傳感器映射的數據信息,還要負責根據傳感器和各自追蹤的對象集合來構建SDG圖和進行聚類,而這兩者都是非常消耗內存的操作,在數據量大的情況下,Master節點必然會成為瓶頸。此外,SensorFS的負載均衡機制是在每個ChunkServer子集群內部根據CPU和內存使用率來進行粗粒度的均衡,即在每個ChunkServer子集群之間是不做負載均衡的,子集群內部的負載均衡通過監控Master ChunkServer的內存和CPU,在其負載過大時選擇一個空閑的Slave ChunkServer轉換成Master ChunkServer來實現,這樣會出現子集群之間負載不均衡的情況。而在同一個子集群中,當同一子集群內部長時間負載過大時,會引起頻繁主從切換的問題,反而對集群性能產生反作用。

圖1 SensorFS系統架構

2 改進的SensorFS系統架構及核心技術

2.1 改進的SensorFS系統架構

針對SensorFS的不足,本文設計優化后的Mater和ChunkServer節點的功能架構,如圖2所示。其中,Master節點只負責初始寫調度,即只有在Sensor首次發出寫請求時會經過Master節點,如圖3所示。當Senser獲取到對應的ChunkServer信息后就會把該信息緩存下來,再次發出寫請求時直接和對應ChunkServer交互,不經過Master節點,如圖4所示,從而大幅降低Master節點的請求壓力。傳感器聚類由原來的Master節點的集中式傳感器聚類改變為在各個ChunkServer內部先對各自節點上的傳感器進行基于SDG的聚類,然后由Master節點對這些類進行聚類。此外,各個子節點會計算各個傳感器的數據是否達到負載,并根據負載均衡算法進行均衡。

圖2 Master與ChunkServer的功能架構

圖3 Sensor首次請求響應過程

圖4 Sensor非首次請求響應過程

改進系統的協同交互過程如圖5所示。假設Sensor對應本地緩存的ChunkServer為ChunkServer1,一開始Sensor會把數據傳送向ChunkServer1,在經過圖3中步驟2)～步驟4)后,Master節點返回負載均衡調度信息通知源節點ChunkServer1和目的節點ChunkServer2,系統則根據返回的信息進行數據傳輸和傳感器調度。

圖5 改進的SensorFS系統交互過程

2.2 分布式傳感器聚類

分布式傳感器聚類的總體過程如圖6所示,其中,三角形代表各個傳感器si,圓形表示聚類后產生的類cj。

圖6 分布式傳感器聚類過程

本文用ok表示傳感器感知到的對象,用O表示對象ok的集合,每個傳感器si都對應其檢測到的對象的集合Oi,用S表示傳感器si的集合,用C表示聚類后類的集合,用CSi表示第i個ChunkServer子節點,用SDG_SK表示基于SDG的聚類過程。

式(1)表示對CSi節點上的n個傳感器S及對應對象的集合通過SDG_SK進行聚類,最終得到CSi節點上m個類及每個類所共有的對象的集合(Oc1,Oc2,…,Ocn),記作CCSi,m,整個過程對應圖6上方的ChunkServer部分。

CCSi,m=SDG_SK(O1,O2,…,On)

(1)

式(2)表示Master節點收集k個CS節點上已經通過式(1)聚類完成后的所有類的集合及每個類對應的所共有的對象的集合(CCS1,m,CCS2,m,…,CCSk,m),然后對傳感類通過SDG_SK進行聚類,得到p個聚類后類的集合Cp,整個過程對應圖6中間的Master部分,不同的地方在于Master節點上大圈內部是小圈(傳感器類)而不是三角形(傳感器)。

Cp=SDG_SK(CCS1,m,CCS2,m,…,CCSk,m)

(2)

本文提出的將集中式傳感器聚類操作轉化為分布式傳感器的方案,首先由各個ChunckServer子節點對各自內部的傳感器進行聚類操作,這樣可以把內部傳感器聚為m個類并且提取出各個傳感器類的共有特征,然后再由Master節點對這些已經預先聚類過的類及類特征進行聚類,從而降低Master節點的內存和計算壓力,同時提高聚類算法的并行度,減少在對海量傳感器數據執行聚類算法時的時間消耗。假設T1集中式傳感器聚類的耗時,T2為分布式傳感器聚類的耗時,N為集群節點數量,Tcom為ChunkerServer把聚類后的類信息傳送給Master節點的通信時間,Tmaster為Master節點對類進行聚類的時間。Tcom和Tmaster隨著設定的聚類后類的數量M的增大而增大,但M一定遠小于傳感器的數量Nsensor,因此,在Nsensor極大時可將(Tcom+Tmaster)近似看為0,此時分布式傳感器聚類的耗時T2僅為T1的1/N,隨著節點N數量越大,聚類耗時就越少。

(3)

分布式傳感器聚類算法具體描述如下:

算法1分布式傳感器聚類算法

Slave節點(CSi):

設置聚類后的目標類的數量m;

獲取CSi節點上的n個傳感器S及對應對象的集合(O1,O2,…,On);

對上一步獲取到的數據進行聚類SDG_SK(O1,O2,…,On)得到CCSi,m;

把本節點上的CCSi,m傳輸到Master節點

Master節點:

接收所有子節點上的數據CCSi,m;

得到CSi節點上m個類及每個類所共有的對象的集合(CCS1,m,CCS2,m,…,CCSk,m);

對傳感器類進行聚類SDG_SK(CCS1,m,CCS2,m,…,CCSk,m)得到Cp

2.3 細粒度負載均衡

Δt=t2-t1

(4)

(5)

(6)

(7)

(8)

(9)

集群負載均衡的過程在Master節點上通過總傳感器類負載均衡算法完成,如算法2所示。

算法2細粒度負載均衡調度算法

對于主節點上的傳感器集合Cp中的每一個傳感器類C:

計算該類的負載L

把C拆分為2類:C1 和 C2

把拆分出的2類加入待調度類的列表

Else

從可用節點列表獲取一個可用節點

If 該節點的當前總負載大于L:

把集合C中的傳感器遷移到該節點

Else

把該節點中的傳感器遷移到集合C所在節點

遷移目標節點的總負載+=L

把該節點從可用節點列表移除

整個基于傳感器的負載均衡算法基于3個目標:

2)在滿足目標1)的情況下最小化R的值,將整個負載均衡問題轉化為一個最優化問題。

3)在需要把類A和類B遷移到同一個節點上時,若LA

3 實驗與結果分析

3.1 實驗準備

本文基于仿真環境產生測試數據,所提供的可調整參數如表1所示,通過調整其中參數的值,可以對分布式聚類性能和負載均衡性能進行評估:調整SENSOR_NUM的值可以測試出分布式聚類在不同傳感器數量的情況下的性能;調整CLUSTER_NUM的值可以影響聚類復雜度和傳輸數據的量;CLUSTER_SAME_OBJECT_NUM為每個傳感器類共有的對象數量,調整該值可以影響單傳感器類傳輸到主節點的數據量。

表1 測試程序可調參數

3.2 分布式聚類性能實驗

圖7和圖8分別為在目標傳感器類個數為10和100的情況下,不同數量的傳感器聚類時間隨著節點數量增大時的變化趨勢。節點數量為1時的聚類時間即集中式傳感器聚類所消耗的時間,可以看出分布式傳感器聚類時間小于集中式傳感器聚類時間,并且聚類時間隨著節點數量的增加而變短。此外還可以看出,在傳感器數量較少時,分布式傳感聚類相對于集中式傳感器聚類時間優勢不明顯,這是因為分布式傳感器聚類多了數據傳輸時間,而在傳感器數量較少時,計算時間也較為短,相對而言數據傳輸時間的所占比重也會變大。但是,隨著數據量的增大,傳輸時間所占的比重也就越小,考慮到物聯網數據的海量性特點,分布式傳感器聚類算法的優勢也就越明顯。

圖7 目標傳感器類個數為10時的聚類時間

圖8 目標傳感器類個數為100時的聚類時間

圖9和圖10分別為在傳感器個數為100 000和1 000 000的情況下,目標傳感器類個數分別為10和100時的聚類時間比較。

圖9 傳感器個數為100 000時的聚類時間

圖10 傳感器個數為1 000 000時的聚類時間

從2幅圖中折線的下降趨勢和斜率可以看出,目標類數量越大,折線下降得越快,即表明分布式傳感器聚類算法的效果越好。這是因為目標傳感器類數量越多,聚類所花費的時間也就越長,此時提高聚類的并行度的效果也就越好。

3.3 負載均衡性能實驗

本文的負載均衡的最小單位為一個傳感器類,圖11展示了在不同目標傳感器類個數情況下的負載均衡性,集群均衡度R越趨近0則負載越均衡。從圖11可以看出,目標傳感器類越多,負載越均衡,這是因為傳感器類越多,每個傳感器類的所包含的傳感器數量就越少,即粒度越小。

圖11 不同目標傳感器類個數情況下的負載均衡性

在設定目標傳感器類為50時,圖12表明在集群初始均衡度從0.9到0.1變化時進行負載均衡后集群的均衡度。從圖中可以看出,均衡后的R值基本在0.1處上下浮動。因此,細粒度負載均衡調度算法能提高集群負載的均衡性。

圖12 目標傳感器類個數為50時的負載均衡性

4 結束語

本文設計了分布式傳感器聚類算法和基于傳感器的細粒度的負載均衡算法。通過理論分析與實驗表明,分布式傳感器聚類算法能有效地提升海量傳感器時的聚類速度,減輕Master節點的內存和CPU壓力,并且把傳感器傳送文件的速率考慮在內。而負載均衡算法則能有效提升系統的均衡性和穩定性。考慮到霧計算能利用物端的計算能力來提升物聯網的性能,因此,下一步是將其引入系統架構中,使部分計算任務在物端完成,從而在降低集群計算壓力的同時,減少網絡傳輸數據量并降低延遲,提升物聯網文件計算與存儲性能。

[1] 田 野,袁 博,李廷力.物聯網海量異構數據存儲與共享策略研究[J].電子學報,2016,44(2):247-257.

[2] 李 敏,倪少權,邱小平,等.物聯網環境下基于上下文的Hadoop大數據處理系統模型[J].計算機應用,2015,35(5):1267-1272.

[3] 馬友忠,孟小峰.云數據管理索引技術研究[J].軟件學報,2015,26(1):145-166.

[4] GARCIA H,LUDU A.The Google File System[J].ACM SIGOPS Operating Systems Review,2003,37(5):29-43.

[5] SHVACHKO K,KUANG H,RADIA S,et al.The Hadoop Distributed File System[C]//Proceedings of the 26th IEEE Symposium on Mass Storage Systems and Technologies.Washington D.C.,USA:IEEE Press,2010:1-10.

[6] Hadoop Archives(2016)[EB/OL].[2016-11-10].http://hadoop.apache.org/docs/stable1/hadoop_archives.html.

[7] Hadoop Sequence File (2016) [EB/OL].[2016-11-10].http://hadoop.apache.org/common/docs/current/api/org/ap ache/hadoop/io/SequenceFile.html.

[8] LIU Xuhui,HAN Jizhong,ZHONG Yunqin,et al.Implementing WebGIS on Hadoop:A Case Study of Improving Small File I/O Performance on HDFS[C]//Proceedings of 2009 IEEE International Conference on Cluster Computing and Workshops.Washington D.C.,USA:IEEE Press,2009:1-8.

[9] CHEN Jilian,WANG Dan,FU Lihua,et al.An Improved Small File Processing Method for HDFS[J].Inter-national Journal of Digital Content Technology and Its Applications,2012,6(20):296-304.

[10] XUE Shengjun,PAN Wubin,FANG Wei.A Novel Approach in Improving I/O Performance of Small Meteorological Files on HDFS[J].Applied Mechanics and Materials,2011,117-119:1759-1765.

[11] ZHANG Yin,HAN Weili,WANG Wei,et al.Optimizing the Storage of Massive Electronic Pedigrees in HDFS[C]//Proceedings of the 3rd International Conference on Internet of Things.Washington D.C.,USA:IEEE Press,2012:68-75.

[12] HAO Xingjun,JIN Peiquan,YUE Lihua.Efficient Storage of Multi-sensor Object-tracking Data[J].IEEE Transactions on Parallel and Distributed Systems,2015,27(10):2881-2894.

[13] JIANG Yichuan.A Survey of Task Allocation and Load Balancing in Distributed Systems[J].IEEE Transactions on Parallel and Distributed Systems,2016,27(2):585-599.

[14] 陳 濤,肖 儂,劉 芳.對象存儲系統中自適應的元數據負載均衡機制[J].軟件學報,2013,24(2):331-342.

[15] 孫 耀,劉 杰,葉 丹,等.分布式文件系統元數據服務的負載均衡框架[J].軟件學報,2016,27(12):3192-3207.