简介

首先我们要简述一下为什么要做文本的泛化和聚类，以及为什么要做增量式聚类。

为什么我们要做文本泛化聚类

我们在日志系统中会接受到很多的报警信息，这些报警信息可能是因为系统的某个点故障了造成的，例如下面几条文本：

Server CDH-NAME-1 disconnected caused by timeout.
Server CDH-NAME-2 disconnected caused by timeout.
Server CDH-NAME-5 disconnected caused by timeout.

很明显，这些报警可以使用以下的形式来泛化：

Server CDH-NAME-* disconnected caused by timeout.

或者详细一点：

Server CDH-NAME-{1,2,5} disconnected caused by timeout.

我们知道是CDH集群的NAME节点掉线了几个，这个时候我们要检查所有的NameNode是否有配置不当或者其他问题。

这样的信息会有很多很多，肉眼根本来不及看，如果泛化做得好，可以大大减少看日志的时间。

为什么我们要做增量式文本泛化聚类

如果这个时候又追加了两条信息，这个时候我们的泛化信息就需要变化了：

Server CDH-ADMIN-0 disconnected caused by timeout.
Server CDH-DATA-10 disconnected caused by timeout.

这个时候我们发现各个服务器陆续掉线，可能并不是NameNode的问题，而是一些基础的网络设施的故障，那么我们可以考虑从网络排查。

这个时候的泛化信息记作：

Server CDH-* disconnected caused by timeout.

或者详细一点：

Server CDH-{NAME-1,NAME-2,NAME-5,ADMIN-0,DATA-10} disconnected caused by timeout.

当然如果我们做二层的泛化，甚至是三层，我们可以得到更加通俗的结果（当然对前端展示带来一定挑战）：

Server CDH-{NAME-{1,2,5},ADMIN-0,DATA-10} disconnected caused by timeout.

除了泛化的信息可能随着日志的到来变化，在聚类的时候如何做到常数级别时间也是重要的问题。 例如我们现在聚类完成了，目前有k类，每一类有Ni(i \in [1,k], i \in Z)条日志。

这个时候来了一条新的日志，我们需要做2件事情：

1. 快速筛选，决定和哪几类做计算，最后挑出一个
2. 将这条日志和之前的日志进行合并，更新这一类

随着日志的过来，如果不能保证每条日志的常数时间处理，那么结局会很悲惨。

日志泛化聚类算法

核心其实很简单，就是最大公共字符串求取算法。无非就是在N串字符串中不断“压榨”出新的公共字符串。

如果不能理解，那么可以看看下面的例子：

Server CDH-NAME-1 disconnected caused by timeout on 5001ms.
Server CDH-NAME-2 disconnected caused by timeout on 5002ms.
Server CDH-NAME-5 disconnected caused by timeout on 5010ms.

首先我我们找出公共部分， disconnected caused by timeout.，随后泛化成了：

{Server CDH-NAME-1,Server CDH-NAME-2,Server CDH-NAME-5} disconnected caused by timeout on {5001ms,5002ms,5010ms}.

这个时候分别对{Server CDH-NAME-1,Server CDH-NAME-2,Server CDH-NAME-5}和{5001ms,5002ms,5010ms}继续进行泛化。

Server CDH-NAME-{1,2,5} disconnected caused by timeout on 50{01,02,10}ms.

连续文本的小优化

这个时候，我们注意到时间被泛化成了：50{01,02,10}ms.，这个其实不是最友好的方式，我们可以提出更友好的方式：{5001,5002,5010}ms。

但是如何实现这一点呢？其实也不复杂，将字母+数字归为一类，其它所有的字符（中文字符们，对不起了）归为另一类，然后以这个为依据切断。

切断的方式也很简单，用正则就行了：

[^0-9a-zA-Z]+|[0-9a-zA-Z]+

下面是我们在实际日志上的一个实战：

可以看到，{12461700, 12461702, 12461698}的类里面没有将公共的12461提取出来。

can't connect to mysql server ,errmsg:Unknown database 'cvnavidb' MySQLConnection [id={12461700, 12461702, 12461698}, lastTime=1551971922856, user=cvnavidb, schema=cvnavidb, old shema=cvnavidb, borrowed=false, fromSlaveDB=true, threadId={298807, 298805, 298809}, charset=utf8, txIsolation=3, autocommit=true, attachment=null, respHandler=null, host=IP不能告诉你, port=端口也是, statusSync=null, writeQueue=0, modifiedSQLExecuted=false]

增量式泛化聚类算法

想要做到增量式算法，那么有一点一定要做到，就是不能依赖以前的日志，而是要依赖一个中间状态量，这个状态量再复杂，毕竟也只有一个。

我们决定将这个状态量叫pattern，也就是这个日志的模式。 这个pattern是一个String数组（或者用List也行），代表着日志中必需出现的字符。

例如：

pattern = [ "a=1 b=", " c=", " d=" ]

这个pattern就可以容纳a=1 b=2 c=3 d=4这样的日志，但是不能容纳Server CDH-NAME-1 disconnected caused by timeout on 5001ms.这样的日志。

那么问题来了，如果遇到了：a=2 b=6 c=3 d=4这样的日志怎么办？

这个时候我们就需要对原有的Pattern进行更新，更新操作的原理也很简单，首先找到后面一个模式的匹配位置，也就是" c="的位置，找到以后取出前面的部分：a=1 b=6 ，将这个字符串和a=1 b=进行互操作，原理和上面的聚类算法一样，我们得到更新后的pattern。

pattern = [ "a=", " b=", " c=", " d=" ]

这里还有一个容易引起BUG的地方，就是在匹配之前必需先运行LCS（这里的S是Sequence了）算法，判断大致的相似度，否则pattern很容易提取出几个空格来。

这里的相似度我们使用类似Jaccard相似度的定义：sim=\frac{common(s_1,s_2)}{max(len(s_1),len(s_2))}

其他泛化聚类算法

并不是所有的泛化聚类都和消息体的聚类一样难缠，我们还有其他的聚类算法：

通用泛化

也就是我们之前说的算法，将相同的部分聚合到一起，例如：

flink/a/jiading/1
flink/b/jiading/2
flink/b/jiading/1

泛化为：flink/{a,b}/jiading/{1,2}

前缀泛化（后缀泛化同理）

一般用在有层级结构的地方

flink/a/jiading/1
flink/b/jiading/2
flink/b/jiading/1

泛化为：`flink/{a/jiading/1,b/jiading/2,b/jiading/1}

树形结构泛化

一般用在类似文件夹表达的地方：

flink/a/jiading/1
flink/b/jiading/2
flink/b/jiading/1

泛化为：

flink/{
    a/jiading/{
        1,
        2
    },
    b/jiading/1
}

可以展现为树形结构。

以上两种都非常容易实现增量式算法，因为太简单，这里就不赘述了，还有其他算法的话欢迎补充。