分布式实时日志密度数据流聚类算法及其基于 Storm 的实现

【摘要】 日志τ诿扛鱿低忱此担都是不可忽视的一部分。现阶段构建的日志分析平台对数据的处理响应时间差较大，实时性不能得到保证，因此 提出了基于Storm 框架的实时日志密度数据流聚类算法RL-DSCA（Real-time Log density stream clustering algorithm）。该算法综合了经典数据流聚类框架 Clustream和一种基于密度的聚类算法DBSCAN实现了多粒度的数据存储。算法可以实现多线程并行的增量更新。设计RL-DSCA算法基于Storm 的实现方案，通过ELK进行实时数据采集，选用Kafka作为中间件实现数据缓冲，Redis存储中间结果，最后部署 Storm 的拓扑对RL-DSCA算法进行实现。性能分析及实验结果表明： Bolt线程数量的增加不会影响到聚类的效果，RL-DSCA算法达到了较高的精度。

【关键字】 RL-DSCA ELK Storm Kafka Redis 增量更新

一、引言

日志信息可以作为特定指标项的分析源来处理某些特定的信息，将日志数据作为原始数据，这样有助于数据分析的准确性。但是日志数量巨大，如何准确、及时的筛选海量日志中的关键信息成为了亟待解决的问题。

聚类分析是处理数据流的常用分析手段，本文RLDSCA算法使用两层聚类框架处理数据同时兼顾实时和历史离线数据，并加入了DBSCAN算法处理可能出现的噪声数据和非球形数据，并将其应用到Storm的计算架构。对Storm计算架构设计实验从聚类精度和计算效率方面对RL-DSCA算法的有效性进行了验证。

二、Storm计算框架

BackType开发了分布式计算系统Storm，并在2011年被Twitter开源，该系统能够很容易可靠地处理无界持续的流数据，进行实时计算。

三、聚类算法分析

3.1 Clustream算法概述

数据流聚类框架Clustream在二十一世纪初被Aggarwal与Han 等人提出，该框架主要引入了两个概念：簇和时间帧，将聚类过程分为了两类：在线部分（微聚类）、离线部分（宏聚类）。在线部分实时处理新到达的数据，并周期性地存储统计结果；离线部分就利用这些统计结果结合用户输入得到聚类结果。

微簇信息需要在特定时刻被维护，基本方法就是存储中间结果以供离线阶段查询。实际的应用中，往往近期数据对结果的影响比较大，而对于历史数据仅仅是对结果起到补充的作用，时间帧结构很好的解决了这个问题，它用来划分时间轴并根据粗细程度的不同来区分不同的时刻。不仅满足了用户需求也满足了内存的需求。

两阶段聚类框架，能适应数据流短时间涌入、有序无穷、单次扫描的特点，并挖掘数据流潜在的演化特征，但是对离群点的识别，非球形数据的聚类处理效果并不理想，有待改进。

3.2 DBSCAN算法概述

DBSCAN 是一种基于密度的聚类算法[1]，它通过密度的高低划分簇类，而且对簇类的识别不受噪声数据的影响 [2]。DBSCAN 可以处理高维数据，有效的排除形状大小不规则的簇和噪声对象。

DBSCAN 对用户定义的参数Eps和MinPts 很敏感，一般靠经验确定[3]。.

四、RL-DSCA算法设计

4.1算法概述

本文设计的分布式实时日志数据流密度聚类算法RLDSCA将 CluStream 算法和DBSCAN算法相结合。既体现了CluStream框架对流数据处理的优势，又利用了DBSCAN算法克服了CluStream框架对非球形和噪声数据聚类效果不佳的缺点。

微聚类部分分为两大部分：微簇的实时日志增量更新（局部更新结果存放在Redis）和合并局部更新进行全局微簇增量更新，算法的总体处理过程如图1所示。

4.2实时局部微簇增量更新全局增量

微簇的在线更新任务有多个节点负责并执行，节点流程图如图2所示。

聚类的过程一般分为两个阶段，首先对数据簇的形态进行识别，随后对初始化的数据进行处理，其结果将被发送到BoltB中进行汇总。对核心点进行DBSCAN 聚类。按照DBSCAN 算法的思想，如果两个簇的核心点是一类，那么这两个核心点是互相直接密度可达的，它们代表的簇要归为一类。通过遍历筛选后，最终不属于任何类的点则为噪声对象。

Storm 框架本身不负责计算结果的保存，在加入CluStream算法框架两层模型和DBSCAN算法后，可以将中间局部增量结果存放在Redis中，以便合并为全局增量。

微簇的在线维护节点按照Strom滑动窗口触发机制单位时间向合并节点发送在该单位时间内的增量。即发送在该单位时间内生成新微簇与旧微簇增量并将实时结果保存在Redis中。

五、RL-DSCA算法在日志综合管理平台的实现方案

5.1开发环境及采用的测试数据集

硬件环境包括Storm集群，Kakfa集群，Zookeeper集群，Storm包括1个Nimbus和4个Supervisor；Kafka集群包括5个节点；Zookeeper集群也包括5个节点，集体配置如表1所示。

软件环境：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。

操作系统：Linux version 3.10.0-327.el7.x86_64

数据集：用户话单日志信息（约2 billon/day）。

5.2平台架构及处理流程

日志综合处理平台主要由三层组成，包括：数据采集层、数据分析及存储层以及数据展示层。可以实现对日志从采集到分析处理的全过程并在页面监控平台显示。RL-DSCA算法在Storm平台的Topology关系如图3所示。

SpoutA接收待初始化的数据，并将其发K-means&DBSCANBolt 通过数据簇形态识别以初始化微簇；SpoutB从Kafka中接收初始化后待处理的流数据，将其发送至LocalBolt进行局部微聚类；SpoutC用作处理时间戳，每单位时间向LocalBolt发送一次信息，当接收到时间戳消息，将局部微聚类更新结果存放到Redis做实时局部微聚类更新结果的保存，并合并原有的增量信息发送到GlobalBolt；SpoutD通过消息中间件 Kafka接收用户发送的查询参数。

六、实验结果分析

实验主要针对RL-DSCA算法应用在Storm平台上对Storm集群数据处理、RL-DSCA算法精确度、RL-DSCA算法实现效果三方面进行试验分析。

6.1 Storm集群数据处理能力分析

本实验比较不使用RL-DSCA算法的Storm集群和使用RL-DSCA算法的Storm集群对同样的数据量处理能力比较。为了方便比较将不使用RL-DSCA算法的Storm集群称为Storm-A集群，使用RL-DSCA算法的Storm集群称为Storm-B集群。首先Strom-A集群进行数据分析。吞吐量和数据延迟分别如图4和图5所示。

由图4和图5大概分析可得集群A平均吞吐量在25000条/秒，数据延迟时间与时间正比增加，分析主要原因在于Bolt之间处理的速度随着数据的大量涌入而变慢，数据量堆积，所以延迟增加。而改进后的Strom-B集群反而吞吐量下降到了23000条/秒，这是因为新算法的引进改变了集群的处理负载，使其更加均衡的分布在各个节点，这点从数据延迟就可以看出，大部分的处理延迟较小基本可以忽略，偶尔的延迟较大，分析其原因是由于多个任务由一个调度器来调度，数据流注入Spout并不规则，可能在某个时间发送Spout获得大量数据并同时发送。但是数据延迟并没有持续增加，并且在延时增加的一段时间内迅速恢复正常说明了短时间内大量涌入的数据能被集群及时的“消化”，从而侧面证明了该算法提升了Strom集群处理性能。

6.2 算法精确程度分析

本节设计了对比实验测试RL-DSCA算法的精度。首先对话单日志数据进行簇形态识别，球根据形态的不同而分别处理，为了稳定性本测试使用单机测试，单机运行K-means和DBSCAN算法，单机运行RL-DSCA算法，以及在 Storm平台上分布式多节点（ LocalBolt 线程数分别为1与4，同时Worker 数设为1与4） 运行RL-DSCA算法进行聚类，聚类簇数为30。测试多次取其平均值，数轴表示簇内各个数据点到中心点的平均距离。测试结果如图6所示。

上述实验结果表明，线程数的增加并没有对算法的精确性产生大的影响，基本可以认定该算法的精确性与K-means算法以及DBSCAN算法一致。

6.3 算法实现效果分析

由于设计的RL-DSCA算法按照单位时间进行分布式聚类，并且按照单位时间合并中间结果，算法的处理速度与到达数据的流速有关。改变分布式 RL-DSCA算法的并行线程数，通过 UI界面观测各线程的线程处理压力（ capacity）。

由测试结果可以看出，单个 LocalBolt 线程的处理压力随着线程数的增加呈倒数减小趋势；而 GlobalBolt 线程的线程压力随着 LocalBolt 线程的增加呈近线性增加趋势。该测试结果与理论一致。本文所实现RL-DSCA算法的簇内各点与簇中心平均距离相比K-means算法以及DBSCAN算法有稍微的差距， 但是差距微乎其微，考虑到RL-DSCA算法是一种动态算法，其性能远高于静态算法，切单点处理条数稳定，所以本文所实现的RL-DSCA算法有着明显的优势。

七、结束语

本文设计了一种分布式实时日志密度流数据聚类算法RL-DSCA，该算法综合运用了流聚类算法CluStream和DBSCAN算法处理各类形态数据簇，并有效的屏蔽了噪声数据，将RL-DSCA应用到流数据计算平台 Storm 的计算架构中，引入了微簇的时间属性参数和中间结果Redis缓存机制。对话单日志数据集的聚类实验结果及性能分析表明了RL-DSCA算法在聚类精度和计算效率方面的优势，也说明了RL-DSCA算法基于 Storm 的实现方案的可行性。

但是对数据簇形态的识别会出现误差影响实验结果的准确性，今后应在数据簇形态的识别中加强理论研究并应用到实际开发中。

参 考 文 献

[1] 叶大田，张锐，钱翔.基于密度提取的细胞荧光图像标识算法[J].清华大学学报：自然科学版，2013（1）：129-132.

[2] 侯荣涛，朱斌，冯民学.基于 DBSCAN聚类算法的闪电临近预报模型[J].计算机应用，2012，32（3）：847-851.

[3] 潘渊洋，李光辉，徐勇军.基于DBSCAN的环境传感器网络异常数据检测方法[J].计算机应用与软件，2012，29（ 11）：69-72.