海量小數(shù)據(jù)分布式聚類優(yōu)化與負(fù)載均衡算法

汪明明,陳慶奎,b

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

0 概述

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展,各種傳感器和嵌入式設(shè)備都在時(shí)刻產(chǎn)生數(shù)據(jù),必然會(huì)遇到海量物聯(lián)網(wǎng)數(shù)據(jù)高效存儲(chǔ)的問題。由于物聯(lián)網(wǎng)數(shù)據(jù)是海量的和異構(gòu)的[1],因此傳統(tǒng)的關(guān)系型數(shù)據(jù)庫并不適合海量物聯(lián)網(wǎng)數(shù)據(jù)的存儲(chǔ)場(chǎng)景。

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

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

針對(duì)SensorFS集中式傳感器聚類算法存在的問題,本文提出分布式算法,在海量傳感器的情況下提高聚類速度并且減輕Master節(jié)點(diǎn)內(nèi)存負(fù)擔(dān)。此外,考慮到良好的負(fù)載均衡能有效提升系統(tǒng)整體性能和穩(wěn)定性[13-15],本文針對(duì)各個(gè)傳感器不同的文件傳送速率,以傳感類為單位提出一種細(xì)粒度的負(fù)載均衡算法。

1 相關(guān)研究

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

圖1 SensorFS系統(tǒng)架構(gòu)

2 改進(jìn)的SensorFS系統(tǒng)架構(gòu)及核心技術(shù)

2.1 改進(jìn)的SensorFS系統(tǒng)架構(gòu)

針對(duì)SensorFS的不足,本文設(shè)計(jì)優(yōu)化后的Mater和ChunkServer節(jié)點(diǎn)的功能架構(gòu),如圖2所示。其中,Master節(jié)點(diǎn)只負(fù)責(zé)初始寫調(diào)度,即只有在Sensor首次發(fā)出寫請(qǐng)求時(shí)會(huì)經(jīng)過Master節(jié)點(diǎn),如圖3所示。當(dāng)Senser獲取到對(duì)應(yīng)的ChunkServer信息后就會(huì)把該信息緩存下來,再次發(fā)出寫請(qǐng)求時(shí)直接和對(duì)應(yīng)ChunkServer交互,不經(jīng)過Master節(jié)點(diǎn),如圖4所示,從而大幅降低Master節(jié)點(diǎn)的請(qǐng)求壓力。傳感器聚類由原來的Master節(jié)點(diǎn)的集中式傳感器聚類改變?yōu)樵诟鱾€(gè)ChunkServer內(nèi)部先對(duì)各自節(jié)點(diǎn)上的傳感器進(jìn)行基于SDG的聚類,然后由Master節(jié)點(diǎn)對(duì)這些類進(jìn)行聚類。此外,各個(gè)子節(jié)點(diǎn)會(huì)計(jì)算各個(gè)傳感器的數(shù)據(jù)是否達(dá)到負(fù)載,并根據(jù)負(fù)載均衡算法進(jìn)行均衡。

圖2 Master與ChunkServer的功能架構(gòu)

圖3 Sensor首次請(qǐng)求響應(yīng)過程

圖4 Sensor非首次請(qǐng)求響應(yīng)過程

改進(jìn)系統(tǒng)的協(xié)同交互過程如圖5所示。假設(shè)Sensor對(duì)應(yīng)本地緩存的ChunkServer為ChunkServer1,一開始Sensor會(huì)把數(shù)據(jù)傳送向ChunkServer1,在經(jīng)過圖3中步驟2)～步驟4)后,Master節(jié)點(diǎn)返回負(fù)載均衡調(diào)度信息通知源節(jié)點(diǎn)ChunkServer1和目的節(jié)點(diǎn)ChunkServer2,系統(tǒng)則根據(jù)返回的信息進(jìn)行數(shù)據(jù)傳輸和傳感器調(diào)度。

圖5 改進(jìn)的SensorFS系統(tǒng)交互過程

2.2 分布式傳感器聚類

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

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

本文用ok表示傳感器感知到的對(duì)象,用O表示對(duì)象ok的集合,每個(gè)傳感器si都對(duì)應(yīng)其檢測(cè)到的對(duì)象的集合Oi,用S表示傳感器si的集合,用C表示聚類后類的集合,用CSi表示第i個(gè)ChunkServer子節(jié)點(diǎn),用SDG_SK表示基于SDG的聚類過程。

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

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

(1)

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

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

(2)

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

(3)

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

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

Slave節(jié)點(diǎn)(CSi):

設(shè)置聚類后的目標(biāo)類的數(shù)量m;

獲取CSi節(jié)點(diǎn)上的n個(gè)傳感器S及對(duì)應(yīng)對(duì)象的集合(O1,O2,…,On);

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

把本節(jié)點(diǎn)上的CCSi,m傳輸?shù)組aster節(jié)點(diǎn)

Master節(jié)點(diǎn):

接收所有子節(jié)點(diǎn)上的數(shù)據(jù)CCSi,m;

得到CSi節(jié)點(diǎn)上m個(gè)類及每個(gè)類所共有的對(duì)象的集合(CCS1,m,CCS2,m,…,CCSk,m);

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

2.3 細(xì)粒度負(fù)載均衡

Δt=t2-t1

(4)

(5)

(6)

(7)

(8)

(9)

集群負(fù)載均衡的過程在Master節(jié)點(diǎn)上通過總傳感器類負(fù)載均衡算法完成,如算法2所示。

算法2細(xì)粒度負(fù)載均衡調(diào)度算法

對(duì)于主節(jié)點(diǎn)上的傳感器集合Cp中的每一個(gè)傳感器類C:

計(jì)算該類的負(fù)載L

把C拆分為2類:C1 和 C2

把拆分出的2類加入待調(diào)度類的列表

Else

從可用節(jié)點(diǎn)列表獲取一個(gè)可用節(jié)點(diǎn)

If 該節(jié)點(diǎn)的當(dāng)前總負(fù)載大于L:

把集合C中的傳感器遷移到該節(jié)點(diǎn)

Else

把該節(jié)點(diǎn)中的傳感器遷移到集合C所在節(jié)點(diǎn)

遷移目標(biāo)節(jié)點(diǎn)的總負(fù)載+=L

把該節(jié)點(diǎn)從可用節(jié)點(diǎn)列表移除

整個(gè)基于傳感器的負(fù)載均衡算法基于3個(gè)目標(biāo):

2)在滿足目標(biāo)1)的情況下最小化R的值,將整個(gè)負(fù)載均衡問題轉(zhuǎn)化為一個(gè)最優(yōu)化問題。

3)在需要把類A和類B遷移到同一個(gè)節(jié)點(diǎn)上時(shí),若LA

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

3.1 實(shí)驗(yàn)準(zhǔn)備

本文基于仿真環(huán)境產(chǎn)生測(cè)試數(shù)據(jù),所提供的可調(diào)整參數(shù)如表1所示,通過調(diào)整其中參數(shù)的值,可以對(duì)分布式聚類性能和負(fù)載均衡性能進(jìn)行評(píng)估:調(diào)整SENSOR_NUM的值可以測(cè)試出分布式聚類在不同傳感器數(shù)量的情況下的性能;調(diào)整CLUSTER_NUM的值可以影響聚類復(fù)雜度和傳輸數(shù)據(jù)的量;CLUSTER_SAME_OBJECT_NUM為每個(gè)傳感器類共有的對(duì)象數(shù)量,調(diào)整該值可以影響單傳感器類傳輸?shù)街鞴?jié)點(diǎn)的數(shù)據(jù)量。

表1 測(cè)試程序可調(diào)參數(shù)

3.2 分布式聚類性能實(shí)驗(yàn)

圖7和圖8分別為在目標(biāo)傳感器類個(gè)數(shù)為10和100的情況下,不同數(shù)量的傳感器聚類時(shí)間隨著節(jié)點(diǎn)數(shù)量增大時(shí)的變化趨勢(shì)。節(jié)點(diǎn)數(shù)量為1時(shí)的聚類時(shí)間即集中式傳感器聚類所消耗的時(shí)間,可以看出分布式傳感器聚類時(shí)間小于集中式傳感器聚類時(shí)間,并且聚類時(shí)間隨著節(jié)點(diǎn)數(shù)量的增加而變短。此外還可以看出,在傳感器數(shù)量較少時(shí),分布式傳感聚類相對(duì)于集中式傳感器聚類時(shí)間優(yōu)勢(shì)不明顯,這是因?yàn)榉植际絺鞲衅骶垲惗嗔藬?shù)據(jù)傳輸時(shí)間,而在傳感器數(shù)量較少時(shí),計(jì)算時(shí)間也較為短,相對(duì)而言數(shù)據(jù)傳輸時(shí)間的所占比重也會(huì)變大。但是,隨著數(shù)據(jù)量的增大,傳輸時(shí)間所占的比重也就越小,考慮到物聯(lián)網(wǎng)數(shù)據(jù)的海量性特點(diǎn),分布式傳感器聚類算法的優(yōu)勢(shì)也就越明顯。

圖7 目標(biāo)傳感器類個(gè)數(shù)為10時(shí)的聚類時(shí)間

圖8 目標(biāo)傳感器類個(gè)數(shù)為100時(shí)的聚類時(shí)間

圖9和圖10分別為在傳感器個(gè)數(shù)為100 000和1 000 000的情況下,目標(biāo)傳感器類個(gè)數(shù)分別為10和100時(shí)的聚類時(shí)間比較。

圖9 傳感器個(gè)數(shù)為100 000時(shí)的聚類時(shí)間

圖10 傳感器個(gè)數(shù)為1 000 000時(shí)的聚類時(shí)間

從2幅圖中折線的下降趨勢(shì)和斜率可以看出,目標(biāo)類數(shù)量越大,折線下降得越快,即表明分布式傳感器聚類算法的效果越好。這是因?yàn)槟繕?biāo)傳感器類數(shù)量越多,聚類所花費(fèi)的時(shí)間也就越長(zhǎng),此時(shí)提高聚類的并行度的效果也就越好。

3.3 負(fù)載均衡性能實(shí)驗(yàn)

本文的負(fù)載均衡的最小單位為一個(gè)傳感器類,圖11展示了在不同目標(biāo)傳感器類個(gè)數(shù)情況下的負(fù)載均衡性,集群均衡度R越趨近0則負(fù)載越均衡。從圖11可以看出,目標(biāo)傳感器類越多,負(fù)載越均衡,這是因?yàn)閭鞲衅黝愒蕉?每個(gè)傳感器類的所包含的傳感器數(shù)量就越少,即粒度越小。

圖11 不同目標(biāo)傳感器類個(gè)數(shù)情況下的負(fù)載均衡性

在設(shè)定目標(biāo)傳感器類為50時(shí),圖12表明在集群初始均衡度從0.9到0.1變化時(shí)進(jìn)行負(fù)載均衡后集群的均衡度。從圖中可以看出,均衡后的R值基本在0.1處上下浮動(dòng)。因此,細(xì)粒度負(fù)載均衡調(diào)度算法能提高集群負(fù)載的均衡性。

圖12 目標(biāo)傳感器類個(gè)數(shù)為50時(shí)的負(fù)載均衡性

4 結(jié)束語

本文設(shè)計(jì)了分布式傳感器聚類算法和基于傳感器的細(xì)粒度的負(fù)載均衡算法。通過理論分析與實(shí)驗(yàn)表明,分布式傳感器聚類算法能有效地提升海量傳感器時(shí)的聚類速度,減輕Master節(jié)點(diǎn)的內(nèi)存和CPU壓力,并且把傳感器傳送文件的速率考慮在內(nèi)。而負(fù)載均衡算法則能有效提升系統(tǒng)的均衡性和穩(wěn)定性。考慮到霧計(jì)算能利用物端的計(jì)算能力來提升物聯(lián)網(wǎng)的性能,因此,下一步是將其引入系統(tǒng)架構(gòu)中,使部分計(jì)算任務(wù)在物端完成,從而在降低集群計(jì)算壓力的同時(shí),減少網(wǎng)絡(luò)傳輸數(shù)據(jù)量并降低延遲,提升物聯(lián)網(wǎng)文件計(jì)算與存儲(chǔ)性能。

[1] 田 野,袁 博,李廷力.物聯(lián)網(wǎng)海量異構(gòu)數(shù)據(jù)存儲(chǔ)與共享策略研究[J].電子學(xué)報(bào),2016,44(2):247-257.

[2] 李 敏,倪少權(quán),邱小平,等.物聯(lián)網(wǎng)環(huán)境下基于上下文的Hadoop大數(shù)據(jù)處理系統(tǒng)模型[J].計(jì)算機(jī)應(yīng)用,2015,35(5):1267-1272.

[3] 馬友忠,孟小峰.云數(shù)據(jù)管理索引技術(shù)研究[J].軟件學(xué)報(bào),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] 陳 濤,肖 儂,劉 芳.對(duì)象存儲(chǔ)系統(tǒng)中自適應(yīng)的元數(shù)據(jù)負(fù)載均衡機(jī)制[J].軟件學(xué)報(bào),2013,24(2):331-342.

[15] 孫 耀,劉 杰,葉 丹,等.分布式文件系統(tǒng)元數(shù)據(jù)服務(wù)的負(fù)載均衡框架[J].軟件學(xué)報(bào),2016,27(12):3192-3207.