分布式實(shí)時(shí)日志密度數(shù)據(jù)流聚類算法及其基于 Storm 的實(shí)現(xiàn)

張輝+王成龍+王偉

【摘要】 日志對(duì)于每個(gè)系統(tǒng)來(lái)說(shuō)，都是不可忽視的一部分。現(xiàn)階段構(gòu)建的日志分析平臺(tái)對(duì)數(shù)據(jù)的處理響應(yīng)時(shí)間差較大，實(shí)時(shí)性不能得到保證，因此 提出了基于Storm 框架的實(shí)時(shí)日志密度數(shù)據(jù)流聚類算法RL-DSCA（Real-time Log density stream clustering algorithm）。該算法綜合了經(jīng)典數(shù)據(jù)流聚類框架 Clustream和一種基于密度的聚類算法DBSCAN實(shí)現(xiàn)了多粒度的數(shù)據(jù)存儲(chǔ)。算法可以實(shí)現(xiàn)多線程并行的增量更新。設(shè)計(jì)RL-DSCA算法基于Storm 的實(shí)現(xiàn)方案，通過(guò)ELK進(jìn)行實(shí)時(shí)數(shù)據(jù)采集，選用Kafka作為中間件實(shí)現(xiàn)數(shù)據(jù)緩沖，Redis存儲(chǔ)中間結(jié)果，最后部署 Storm 的拓?fù)鋵?duì)RL-DSCA算法進(jìn)行實(shí)現(xiàn)。性能分析及實(shí)驗(yàn)結(jié)果表明： Bolt線程數(shù)量的增加不會(huì)影響到聚類的效果，RL-DSCA算法達(dá)到了較高的精度。

【關(guān)鍵字】 RL-DSCA ELK Storm Kafka Redis 增量更新

一、引言

日志信息可以作為特定指標(biāo)項(xiàng)的分析源來(lái)處理某些特定的信息，將日志數(shù)據(jù)作為原始數(shù)據(jù)，這樣有助于數(shù)據(jù)分析的準(zhǔn)確性。但是日志數(shù)量巨大，如何準(zhǔn)確、及時(shí)的篩選海量日志中的關(guān)鍵信息成為了亟待解決的問(wèn)題。

聚類分析是處理數(shù)據(jù)流的常用分析手段，本文RLDSCA算法使用兩層聚類框架處理數(shù)據(jù)同時(shí)兼顧實(shí)時(shí)和歷史離線數(shù)據(jù)，并加入了DBSCAN算法處理可能出現(xiàn)的噪聲數(shù)據(jù)和非球形數(shù)據(jù)，并將其應(yīng)用到Storm的計(jì)算架構(gòu)。對(duì)Storm計(jì)算架構(gòu)設(shè)計(jì)實(shí)驗(yàn)從聚類精度和計(jì)算效率方面對(duì)RL-DSCA算法的有效性進(jìn)行了驗(yàn)證。

二、Storm計(jì)算框架

BackType開(kāi)發(fā)了分布式計(jì)算系統(tǒng)Storm，并在2011年被Twitter開(kāi)源，該系統(tǒng)能夠很容易可靠地處理無(wú)界持續(xù)的流數(shù)據(jù)，進(jìn)行實(shí)時(shí)計(jì)算。

三、聚類算法分析

3.1 Clustream算法概述

數(shù)據(jù)流聚類框架Clustream在二十一世紀(jì)初被Aggarwal與Han 等人提出，該框架主要引入了兩個(gè)概念：簇和時(shí)間幀，將聚類過(guò)程分為了兩類：在線部分（微聚類）、離線部分（宏聚類）。在線部分實(shí)時(shí)處理新到達(dá)的數(shù)據(jù)，并周期性地存儲(chǔ)統(tǒng)計(jì)結(jié)果；離線部分就利用這些統(tǒng)計(jì)結(jié)果結(jié)合用戶輸入得到聚類結(jié)果。

微簇信息需要在特定時(shí)刻被維護(hù)，基本方法就是存儲(chǔ)中間結(jié)果以供離線階段查詢。實(shí)際的應(yīng)用中，往往近期數(shù)據(jù)對(duì)結(jié)果的影響比較大，而對(duì)于歷史數(shù)據(jù)僅僅是對(duì)結(jié)果起到補(bǔ)充的作用，時(shí)間幀結(jié)構(gòu)很好的解決了這個(gè)問(wèn)題，它用來(lái)劃分時(shí)間軸并根據(jù)粗細(xì)程度的不同來(lái)區(qū)分不同的時(shí)刻。不僅滿足了用戶需求也滿足了內(nèi)存的需求。

兩階段聚類框架，能適應(yīng)數(shù)據(jù)流短時(shí)間涌入、有序無(wú)窮、單次掃描的特點(diǎn)，并挖掘數(shù)據(jù)流潛在的演化特征，但是對(duì)離群點(diǎn)的識(shí)別，非球形數(shù)據(jù)的聚類處理效果并不理想，有待改進(jìn)。

3.2 DBSCAN算法概述

DBSCAN 是一種基于密度的聚類算法[1]，它通過(guò)密度的高低劃分簇類，而且對(duì)簇類的識(shí)別不受噪聲數(shù)據(jù)的影響 [2]。DBSCAN 可以處理高維數(shù)據(jù)，有效的排除形狀大小不規(guī)則的簇和噪聲對(duì)象。

DBSCAN 對(duì)用戶定義的參數(shù)Eps和MinPts 很敏感，一般靠經(jīng)驗(yàn)確定[3]。.

四、RL-DSCA算法設(shè)計(jì)

4.1算法概述

本文設(shè)計(jì)的分布式實(shí)時(shí)日志數(shù)據(jù)流密度聚類算法RLDSCA將 CluStream 算法和DBSCAN算法相結(jié)合。既體現(xiàn)了CluStream框架對(duì)流數(shù)據(jù)處理的優(yōu)勢(shì)，又利用了DBSCAN算法克服了CluStream框架對(duì)非球形和噪聲數(shù)據(jù)聚類效果不佳的缺點(diǎn)。

微聚類部分分為兩大部分：微簇的實(shí)時(shí)日志增量更新（局部更新結(jié)果存放在Redis）和合并局部更新進(jìn)行全局微簇增量更新，算法的總體處理過(guò)程如圖1所示。

4.2實(shí)時(shí)局部微簇增量更新全局增量

微簇的在線更新任務(wù)有多個(gè)節(jié)點(diǎn)負(fù)責(zé)并執(zhí)行，節(jié)點(diǎn)流程圖如圖2所示。

聚類的過(guò)程一般分為兩個(gè)階段，首先對(duì)數(shù)據(jù)簇的形態(tài)進(jìn)行識(shí)別，隨后對(duì)初始化的數(shù)據(jù)進(jìn)行處理，其結(jié)果將被發(fā)送到BoltB中進(jìn)行匯總。對(duì)核心點(diǎn)進(jìn)行DBSCAN 聚類。按照DBSCAN 算法的思想，如果兩個(gè)簇的核心點(diǎn)是一類，那么這兩個(gè)核心點(diǎn)是互相直接密度可達(dá)的，它們代表的簇要?dú)w為一類。通過(guò)遍歷篩選后，最終不屬于任何類的點(diǎn)則為噪聲對(duì)象。

Storm 框架本身不負(fù)責(zé)計(jì)算結(jié)果的保存，在加入CluStream算法框架兩層模型和DBSCAN算法后，可以將中間局部增量結(jié)果存放在Redis中，以便合并為全局增量。

微簇的在線維護(hù)節(jié)點(diǎn)按照Strom滑動(dòng)窗口觸發(fā)機(jī)制單位時(shí)間向合并節(jié)點(diǎn)發(fā)送在該單位時(shí)間內(nèi)的增量。即發(fā)送在該單位時(shí)間內(nèi)生成新微簇與舊微簇增量并將實(shí)時(shí)結(jié)果保存在Redis中。

五、RL-DSCA算法在日志綜合管理平臺(tái)的實(shí)現(xiàn)方案

5.1開(kāi)發(fā)環(huán)境及采用的測(cè)試數(shù)據(jù)集

硬件環(huán)境包括Storm集群，Kakfa集群，Zookeeper集群，Storm包括1個(gè)Nimbus和4個(gè)Supervisor；Kafka集群包括5個(gè)節(jié)點(diǎn)；Zookeeper集群也包括5個(gè)節(jié)點(diǎn)，集體配置如表1所示。

軟件環(huán)境：jdk-1.7.0_79、logstash-2.3.4、elasticsearch-2.3.4、storm-0.9.5、kafka_2.9.1-0.8.2.0

zookeeper-3.3.5、python-2.7.12。

操作系統(tǒng)：Linux version 3.10.0-327.el7.x86_64

數(shù)據(jù)集：用戶話單日志信息（約2 billon/day）。

5.2平臺(tái)架構(gòu)及處理流程

日志綜合處理平臺(tái)主要由三層組成，包括：數(shù)據(jù)采集層、數(shù)據(jù)分析及存儲(chǔ)層以及數(shù)據(jù)展示層?？梢詫?shí)現(xiàn)對(duì)日志從采集到分析處理的全過(guò)程并在頁(yè)面監(jiān)控平臺(tái)顯示。RL-DSCA算法在Storm平臺(tái)的Topology關(guān)系如圖3所示。

SpoutA接收待初始化的數(shù)據(jù)，并將其發(fā)K-means&DBSCANBolt 通過(guò)數(shù)據(jù)簇形態(tài)識(shí)別以初始化微簇；SpoutB從Kafka中接收初始化后待處理的流數(shù)據(jù)，將其發(fā)送至LocalBolt進(jìn)行局部微聚類；SpoutC用作處理時(shí)間戳，每單位時(shí)間向LocalBolt發(fā)送一次信息，當(dāng)接收到時(shí)間戳消息，將局部微聚類更新結(jié)果存放到Redis做實(shí)時(shí)局部微聚類更新結(jié)果的保存，并合并原有的增量信息發(fā)送到GlobalBolt；SpoutD通過(guò)消息中間件 Kafka接收用戶發(fā)送的查詢參數(shù)。

六、實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)主要針對(duì)RL-DSCA算法應(yīng)用在Storm平臺(tái)上對(duì)Storm集群數(shù)據(jù)處理、RL-DSCA算法精確度、RL-DSCA算法實(shí)現(xiàn)效果三方面進(jìn)行試驗(yàn)分析。

6.1 Storm集群數(shù)據(jù)處理能力分析

本實(shí)驗(yàn)比較不使用RL-DSCA算法的Storm集群和使用RL-DSCA算法的Storm集群對(duì)同樣的數(shù)據(jù)量處理能力比較。為了方便比較將不使用RL-DSCA算法的Storm集群稱為Storm-A集群，使用RL-DSCA算法的Storm集群稱為Storm-B集群。首先對(duì)Strom-A集群進(jìn)行數(shù)據(jù)分析。吞吐量和數(shù)據(jù)延遲分別如圖4和圖5所示。

由圖4和圖5大概分析可得集群A平均吞吐量在25000條/秒，數(shù)據(jù)延遲時(shí)間與時(shí)間正比增加，分析主要原因在于Bolt之間處理的速度隨著數(shù)據(jù)的大量涌入而變慢，數(shù)據(jù)量堆積，所以延遲增加。而改進(jìn)后的Strom-B集群反而吞吐量下降到了23000條/秒，這是因?yàn)樾滤惴ǖ囊M(jìn)改變了集群的處理負(fù)載，使其更加均衡的分布在各個(gè)節(jié)點(diǎn)，這點(diǎn)從數(shù)據(jù)延遲就可以看出，大部分的處理延遲較小基本可以忽略，偶爾的延遲較大，分析其原因是由于多個(gè)任務(wù)由一個(gè)調(diào)度器來(lái)調(diào)度，數(shù)據(jù)流注入Spout并不規(guī)則，可能在某個(gè)時(shí)間發(fā)送Spout獲得大量數(shù)據(jù)并同時(shí)發(fā)送。但是數(shù)據(jù)延遲并沒(méi)有持續(xù)增加，并且在延時(shí)增加的一段時(shí)間內(nèi)迅速恢復(fù)正常說(shuō)明了短時(shí)間內(nèi)大量涌入的數(shù)據(jù)能被集群及時(shí)的“消化”，從而側(cè)面證明了該算法提升了Strom集群處理性能。

6.2 算法精確程度分析

本節(jié)設(shè)計(jì)了對(duì)比實(shí)驗(yàn)測(cè)試RL-DSCA算法的精度。首先對(duì)話單日志數(shù)據(jù)進(jìn)行簇形態(tài)識(shí)別，球根據(jù)形態(tài)的不同而分別處理，為了穩(wěn)定性本測(cè)試使用單機(jī)測(cè)試，單機(jī)運(yùn)行K-means和DBSCAN算法，單機(jī)運(yùn)行RL-DSCA算法，以及在 Storm平臺(tái)上分布式多節(jié)點(diǎn)（ LocalBolt 線程數(shù)分別為1與4，同時(shí)Worker 數(shù)設(shè)為1與4） 運(yùn)行RL-DSCA算法進(jìn)行聚類，聚類簇?cái)?shù)為30。測(cè)試多次取其平均值，數(shù)軸表示簇內(nèi)各個(gè)數(shù)據(jù)點(diǎn)到中心點(diǎn)的平均距離。測(cè)試結(jié)果如圖6所示。

上述實(shí)驗(yàn)結(jié)果表明，線程數(shù)的增加并沒(méi)有對(duì)算法的精確性產(chǎn)生大的影響，基本可以認(rèn)定該算法的精確性與K-means算法以及DBSCAN算法一致。

6.3 算法實(shí)現(xiàn)效果分析

由于設(shè)計(jì)的RL-DSCA算法按照單位時(shí)間進(jìn)行分布式聚類，并且按照單位時(shí)間合并中間結(jié)果，算法的處理速度與到達(dá)數(shù)據(jù)的流速有關(guān)。改變分布式 RL-DSCA算法的并行線程數(shù)，通過(guò) UI界面觀測(cè)各線程的線程處理壓力（ capacity）。

由測(cè)試結(jié)果可以看出，單個(gè) LocalBolt 線程的處理壓力隨著線程數(shù)的增加呈倒數(shù)減小趨勢(shì)；而 GlobalBolt 線程的線程壓力隨著 LocalBolt 線程的增加呈近線性增加趨勢(shì)。該測(cè)試結(jié)果與理論一致。本文所實(shí)現(xiàn)RL-DSCA算法的簇內(nèi)各點(diǎn)與簇中心平均距離相比K-means算法以及DBSCAN算法有稍微的差距， 但是差距微乎其微，考慮到RL-DSCA算法是一種動(dòng)態(tài)算法，其性能遠(yuǎn)高于靜態(tài)算法，切單點(diǎn)處理?xiàng)l數(shù)穩(wěn)定，所以本文所實(shí)現(xiàn)的RL-DSCA算法有著明顯的優(yōu)勢(shì)。

七、結(jié)束語(yǔ)

本文設(shè)計(jì)了一種分布式實(shí)時(shí)日志密度流數(shù)據(jù)聚類算法RL-DSCA，該算法綜合運(yùn)用了流聚類算法CluStream和DBSCAN算法處理各類形態(tài)數(shù)據(jù)簇，并有效的屏蔽了噪聲數(shù)據(jù)，將RL-DSCA應(yīng)用到流數(shù)據(jù)計(jì)算平臺(tái) Storm 的計(jì)算架構(gòu)中，引入了微簇的時(shí)間屬性參數(shù)和中間結(jié)果Redis緩存機(jī)制。對(duì)話單日志數(shù)據(jù)集的聚類實(shí)驗(yàn)結(jié)果及性能分析表明了RL-DSCA算法在聚類精度和計(jì)算效率方面的優(yōu)勢(shì)，也說(shuō)明了RL-DSCA算法基于 Storm 的實(shí)現(xiàn)方案的可行性。

但是對(duì)數(shù)據(jù)簇形態(tài)的識(shí)別會(huì)出現(xiàn)誤差影響實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，今后應(yīng)在數(shù)據(jù)簇形態(tài)的識(shí)別中加強(qiáng)理論研究并應(yīng)用到實(shí)際開(kāi)發(fā)中。

參 考 文 獻(xiàn)

[1] 葉大田，張銳，錢翔.基于密度提取的細(xì)胞熒光圖像標(biāo)識(shí)算法[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2013（1）：129-132.

[2] 侯榮濤，朱斌，馮民學(xué).基于 DBSCAN聚類算法的閃電臨近預(yù)報(bào)模型[J].計(jì)算機(jī)應(yīng)用，2012，32（3）：847-851.

[3] 潘淵洋，李光輝，徐勇軍.基于DBSCAN的環(huán)境傳感器網(wǎng)絡(luò)異常數(shù)據(jù)檢測(cè)方法[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（ 11）：69-72.