布尔代数与海量报警过滤和关联分析的算法研究（转）

  现代的的编程语言已经做到很高级了，基本上不需要程序员去关注底层的实现了，已
经不是师爷那个纸带打口编程的年代了，二进制已经渐渐被人遗忘掉了。尤其是使用更高级
语言的程序员，例如Java，C#等。
学过离散数学的人都知道，有专门研究二进制运算的一门学科称之为布尔代数。布尔
代数简单得不能再简单了,运算的元素只有两个1和0 , 基本的运算也很简单。常用的有AND
、 OR 和NOT ,小学一年级的小朋友都能学会，据说这也个是叫布尔的小学的数学老师发明
的。
其实一个计算机系统再强大和先进也离不开最基础的二进制运算。这是计算机的基础，
也就是说我们的所有复杂的运算都最终到要转化成二进制的0或1 去交给计算机运算。
举几个布尔代数元素的简单例子
1 AND 1 = 1 1 AND 0 = 1 0 AND 0 = 0
1 OR 1 = 1 1 OR 0 = 0 0 OR 0 = 0
NOT 1= 0 NOT 0 = 1
很难想象计算机就是这么计算一切的，复杂的制图程序，互联网应用等。
由于做数据采集平台，经常面临的大量的数据要处理，每天几十万，百万，甚至千万
的数据要采集，性能是我必须考虑的一个因素。
前段时间，有一个小的功能点，过滤掉重复的报警信息。每台机器出现故障（或触发
事件）后都会上报报警（事件），故障恢复后也会发恢复类报警，故障的类型可能有上百
种，故障发生后，在恢复之前要报重复的发生报警要过滤掉。每个报警的 Key可以定义为
“机器ID_报警类型” 状态为“发生”或“恢复”。
这个问题任何程序员可能不用思考都会得出一个方案，就是new 个Map，来了一个报
警信息去Map中查，然后判断处理。这个方法通常是可行的，一点问题没有，并且简单方
便。但是在某些情况下可能不太适用。在全国，共约400个城市，每个城市都有几十个机器，
那么报警的Key可以定义为“区域编号_机器ID_报警类型“，这个Key可以用一个String
类型的变量来表示。最少也要10个左右的字符。区域ID三位，机器ID两位，报警类型三位，
如果数据模型设计的字段长度长些，这个Key可能会远大于10字符。
来计算一下，全国400个地市，每个地市 50台机器，报警（事件）类型定义为200
种。
极端的情况下，全部发生时候，Map中系统中要保存 400*50*200 = 400万条记录。
选择Java做开发语言的时候，每个char字符占用的空间为2B。
那么每个Key的大小为10*20 = 20B。
400万个Key大小为 400万*20B=8000万B=80,000,000=80,000KB = 80MB。由于哈希
表的存储效率一般只有 50%，占用的空间可能会更高。
这个好像也没有多大，现在哪个企业级应用不占用几个G的内存，但这个不是整个应
用，只是其中的一个小功能点，占用这么大的内存已经很可怕了。
记得当时开过多次会讨论对策，最终拿出的方案是利用嵌入式本地数据库来替代内存
存储。
使用嵌入式数据库的解决了内存占用的问题，但是也有两个缺点：
1. 每次查找数据的时候，有会有磁盘的IO（这个不会很多，根据B+树的高度有关）。
2. 需要维护一份本地的数据库。
分析上面提到的Key = “区域编号_机器ID_报警类型“，这个看起来和布尔代数没有
任何关系，重新思考一下，全国也就那么多个地方(400个左右)，每个地方的设备目前来说
也不超过100个，报警事情类型也定义200种。那么区域的ID可以认为是一个小于400的
整数，每个地方的机器可以编号为 0-99 的整数，报警事件的类型可以用一个小于200的整
数来表示，这样这个key可以优化为类似 400 99 200 字符串，可以转化为一个Java的int
型的整数了。Java 中Int占用的空间为4个字节的空间，如果占用这个方法，那么这些Key
的空间可以优化到原来的 4/10,很不错了,但是能不能再优化了?
到目前为止，仍然看不出和文章的标题布尔代数有任何的关系。
上面的Key已经优化到一个大小不超过400 99 200 大小的整数了，换句话说，任何的
一个key的取值范围 将在 001 00 001 – 400 99 200 这个数之间，而值是0或1。
值为0或1，正好是二进制的范围。这个值可以用内存中的每一位来表示（1B=8位）
那么怎么存放Key和值的关系呢？联想到Oracle中的位图索引的这个例子。
建立一个大小为400 99 200的数组，这个数组的每个元素是大小为1位，每个元素的
取值范围肯定是 0或1了。图中表示 40099197 这个key的报警发生了。
0 0 0 0 0 1 0 0 0
40099197
这个方法看似可笑，那么大的数组程序肯定崩溃。但是计算一下。
40099200位 约等于5 000 000B 约等于 5000KB 约等于 5M。那么“大“数组只需要
5M的空间。与原来的上百M的空间，是原来的20分之一以下。
并且运算也不需要经过复杂Map了，计算机的位运算是最快的运算。
另一个需求也是和报警处理相关的，报警（事件）定义为200个类型，例如，定义几
个事件，如果修改注册表（类型1），改写Windows 下系统目录（类型2），连接网络
（类型3），修改host文件（类型4）等事件，这些单独看起来没有什么问题，但是如果同
时发生，很可能就是一次入侵或病毒发作等黑客行为。
将上面的例子定位为一个规则，称之为有效报警，下文统称为有效报警。
下面描述的这个有效报警定义为A，（假设认为是一次黑客入侵，其实黑客入侵过程
不是这么样的，只是举例说明）
A类型的有效报警，由以下几个基础报警组成的。
报警（事件）描述类型
修改注册表1
改写Windows下系统文件2
修改host文件 4
那么A可以描述成 A（1，2，4）
另外同样的方式定义B（1，3，4）
在一台机器上，只有当类型为1，2，4的报警（事件）同时都发生，才可能触发一个
用户关注的有效报警A。
有效报警A，与其有关联的基础报警有1，2，4
我们的程序要进行有效报警与基础报警的关联性分析，最终结果要给出发生了的有效
报警。
转化为程序，可以设计一个客户关注的有效报警对象
Class A {
Map<Type，True和False>
}
里面的Type 为 与类型A关联的基础类型1，2，4
然后每来一条报警的时候 ，对这个Map迭代，判断是否所有的Value都等于True。
每个机器上定义很多种这个规则（假设40种吧），那么系统中在极端的情况下，也要
保存大量的A类型的对象。
400 * 50 * 40 * 50（假定对象A的大小为50B） 那么这个大小也为40 000 000B的大
小。约等于40M。（其实这个不算大）
分析一下，1，2，4同时满足，则发生。。。
这个好像和我们使用搜索引擎的方式有点相像。
比如搜索 大连 + 海鲜 + 饭店
搜索的结果 会把包含这几个关键字的 网页列出来。
借助曾经研究过的过关键字搜索引擎原理，我博客中曾经写
http://zhangdp.iteye.com/admin/blogs/562549
那么这个需求也可以抽象成多关键的搜索引擎。
同时输入1，2，4 类型的基础报警，产生A而不产生B。
按照多关键字搜索引擎的原理，创建一个二维的矩阵。
横坐标定义为 基础报警类型，1-200
纵坐标定义 地市下的机器ID 1-50
为每个地市创建一个矩阵，那么这个矩阵可以表示如下形式。
1 2 3 4 .。。。。198 199 200
1 1 1 1 1 0 0 0 0
2 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0
。0 0 0 0 0 0 0 0
48 0 0 0 0 0 0 0 0
49 0 0 0 0 0 0 0 0
50 0 0 0 0 0 0 0 0
针对其中的一台机器（编号1），发生了如下几个报警（事件），计算A类型的有效
报警是否发生的方式如下。
由于A（1，2，4），设第一列T1,二列T2，三列T3，四列T4。
与有效报警A有关的列为 T1，T2,T4.
那么计算A是否发生了，过程如下。
1.发生修改了Windows下系统目录（类型3）基础报警，修改 （1，2）位置的值为1
计算T1[1]&T2[1]&T3[1]的值 = 0
2.发生修改注册表（类型1）基础报警， 修改 （1，1）位置的值为1
计算T1[1]&T2[1]&T3[1]的值 = 0
3.发生连接网络（类型3）基础报警， 修改 （1，3）位置的值为1
计算T1[1]&T2[1]&T3[1]的值 = 0
4.发生修改了host文件（类型4） 修改 （1，4）位置的值为1
计算T1[1]&T2[1]&T3[1]的值 = 1
此时 A 类型的有效报警发生了。如果针对B类型的计算，此时也产生了B类型的有效
报警。
上面描述的这个矩阵，每个矩阵的元素只有0和1两种值，那么仍然可以用前面提到
的位数组来表示。每个矩阵的大小 为 200* 50 = 10000位 约等于 1250B = 1.25K。这个系统
共400个地市，那么大小也就400多K，对一个企业级应用来说一个功能点 用400K的内
存是基础上是可以接受的。
这样，一个复杂的问题，用计算机中最原始的计算方式就解决了。
另外，目前的有效报警定义都是针对一个机器定义的，如果将来，定义跨机器的有效
报警（例如，两台Oracle的RAC节点，同时发生几个类型基础报警，可以认为数据库挂掉
了），那么上面的算法稍微改变一些，也很能够解决这种类型的关联分析了，显示了位运
算的强大。
位运算在海量数据处理，图形图像编程，搜索引擎等领域有着广泛的应用，只是在企
业级开这被大家给忽略掉了。
下面代码为Java中的位操作的算法。

 

public final class BitVector {
private byte[] bits;
private int size;
public BitVector(int n) {
size = n;
bits = new byte[(size >> 3) + 1];
}
/**
* 将第bit位的值设置为1
* @param bit
*/
public final void set(int bit) {
bits[bit >> 3] |= 1 << (bit & 7);
}
/**
* 将第bit位的值设置为0
* @param bit
*/
public final void clear(int bit) {
bits[bit >> 3] &= ~(1 << (bit & 7));
}
/**
* 如果第i位的值为1返回True,否则返回False
* @param bit
* @return
*/
public final boolean get(int bit) {
return (bits[bit >> 3] & (1 << (bit & 7))) != 0;
}
public final int size() {
return size;
}
/**
* 按位&操作
* @param bv
* @return
*/
public final BitVector comp(BitVector bv){
for(int i=0;i<bv.bits.length;i++){
bits[i]=(byte) (bits[i]&bv.bits[i]);
}
return this;
}
}

 

评论

1 楼 investigater 2010-10-22  

好文！ 我能想到的只是一维数组解决，没想到用二维矩阵这么好的解决办法。