暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / 用BitMap结构实现快速取差集

用BitMap结构实现快速取差集

IT那活儿 2024-01-29
510
点击上方“IT那活儿”公众号--专注于企业全栈运维技术分享，不管IT什么活儿，干就完了！！！  



前 言



在流式计算对比基线无数据告警场景中，利用基线数据对比来源数据，如果发现该时间窗口内的数据不在基线数据中则产生告警，因此基线数据和来源数据需要进行对比计算，基线数据去掉来源数据中已有的数据，余下的数据作为产生的告警数据。在数据量较小时直接进行集合运算取差集即可，但是但基线数据和来源数据量达百万甚至千万时则计算缓慢，出现延时，因此需要找到其它方式方法。

基线数据的定义：
基线数据是一组带时分的时序数据，时分是根据配置对24小时进行分割得到，比如配置1分钟内没数据则告警，则24小时按1分钟进行分割，则分割成00:01, 00:02…的时序数据,总共1440条记录，1440条表示每个1分钟窗口内有一条数据。配置5分钟内没数据则告警，则按5分钟进行分割，则分割成00:05, 00:10…的时序数据,每个时间窗口内有且仅有一条数据。每个任务对应一组基线数据。



测试对比



假设基线数据量为一百万条，窗口内来源数据为九十九万九千条，基线数据中移除来源数据即取差集后则只有一千条。

2.1 集合的取差集方法

1）List.removeAll(sublist)方法取差集

private static void testRemoveAll() { 
    List<String> listA = new ArrayList<>(); 
    for(int i=0;i<OneMillion;i++){ //随机创建百万条基线数据
        String key1="ip(192.168.199.10"+i+")#port("+i+")#service_name(orcl)#time(23:30:00)"+i;
        listA.add(key1); 
    } 
    //从百万条基线数据中随机获取九十九万九千条作为来源数据
    List<String> listB = createRandomList(listA,999000); 
    Date date = new Date(); 
    listA.removeAll(listB); 
    Date date1 = new Date(); 
    System.out.println("testRemoveAll:"+(date1.getTime()-date.getTime())/1000+"秒"); 
    System.out.println(listA.size());
}
测试结果：
30分钟未计算出结果，手动kill程序。

2）List.removeAll(new HashSet(sublist))方法取差集

分析removeAll方法的源码，发现removeAll方法中有subList.contain(value)的方法，如果subList为list集合，则调用indexOf()方法，一个一个地遍历查找。最坏时间复杂度为O(总数据量)。如果先将subList转为HashSet，在调用contain方法时，则时间复杂度为O(1)，加快对比计算速度。
private static void testRemoveAll() { 
   List<String> listA = new ArrayList<>(); 
   for(int i=0;i<OneMillion;i++){ //随机创建百万条基线数据
       String key1="ip(192.168.xxx.10"+i+")#port("+i+")#service_name(orcl)#time(23:30:00)"+i;
       listA.add(key1); 
   } 
   //从百万条基线数据中随机获取九十九万九千条作为来源数据
   List<String> listB = createRandomList(listA,999000);
   Date date = new Date(); 
   //listA.removeAll(listB);
   listA.removeAll(new HashSet(listB));
   Date date1 = new Date(); 
   System.out.println("testRemoveAll:"+(date1.getTime()-date.getTime())/1000+"秒");
   System.out.println(listA.size());
}
//0.3秒
测试结果：
计算耗时仅0.3s，这个结果相比上一步有巨大提升。

2.2 BitMap的取差集方法

BitMap，直译为位图，是一种数据结构，代表了有限域中的稠集（Dense Set），每一个元素至少出现一次，没有其他的数据和元素相关联。在索引，数据压缩等方面有广泛应用。
计算机中1 byte = 8 bit，一个比特（bit，称为比特或者位）可以表示1或者0两种值，通过一个比特去标记某个元素的值，而KEY或者INDEX就是该元素，构成一张映射关系图。因为采用了Bit作为底层存储数据的单位，所以可以极大地节省存储空间。同时还支持去重，交集，差集等各种运算Bitmap的实现有很多，例如Java原生的BitSet，第三方的RoaingBitmap等。

1）Java原生的BitSet

private static void testBitSet() { 
   List<String> listA = new ArrayList<>(); 
   BitSet bitmap = new BitSet(); 
   for(int i=0;i<OneMillion;i++){ 
       String key1="ip(192.168.XXX.10"+i+")#port("+i+")#service_name(orcl)#time(23:30:00)"+i; 
       bitmap.set(Math.abs(key1.hashCode())); 
       listA.add(key1); 
   } 
   BitSet bitmap1 = new BitSet(); 
   List<String> listB = createRandomList(listA,999000); 
   for(String s:listB){ 
       bitmap1.set(Math.abs(s.hashCode())); 
   } 
   Date date = new Date(); 
   bitmap.andNot(bitmap1); 
   Date date1 = new Date(); 
   System.out.println("testBitSet:"+(double)(date1.getTime()-date.getTime())/1000+"秒"); 
}
//testBitSet:0.02秒
测试结果：
计算耗时仅0.02s，这个结果相比上一步时间缩短一个数量级。

2）RoaingBitmap

Bitmap的主要缺陷是占用大量的内存空间。Bitmap是一种使用位图来表示数据集合的数据结构，每个位代表一个元素的存在与否。当数据集合很大时，Bitmap需要使用大量的位来表示，导致内存占用较高。
RoaringBitmap是一种改进的Bitmap数据结构，它能够解决Bitmap的内存占用问题。RoaringBitmap使用了一种压缩算法，能够有效地压缩位图数据，减少内存占用。具体来说，RoaringBitmap将位图分成多个块，每个块使用不同的压缩算法进行压缩。这样，当数据集合中存在大量连续的元素时，RoaringBitmap能够更好地压缩数据，减少内存占用。另外，RoaringBitmap还支持快速的位图操作，如并集、交集和差集等，使得对数据集合的操作更加高效。RoaringBitmap还支持动态增长，可以动态地添加和删除元素，而不需要重新分配内存。
总的来说，RoaringBitmap通过压缩算法和优化的位图操作，能够有效地解决Bitmap的内存占用问题，提高了位图数据结构的性能和可扩展性。
private static void testRoaringBitmap() { 
   List<String> listA = new ArrayList<>(); 
   RoaringBitmap bitmap = new RoaringBitmap(); 
   for(int i=0;i<OneMillion;i++){ 
       String key1="ip(192.168.xxx.10"+i+")#port("+i+")#service_name(orcl)#time(23:30:00)"+i; 
       bitmap.add(Math.abs(key1.hashCode())); 
       listA.add(key1); 
   } 
   RoaringBitmap bitmap1 = new RoaringBitmap(); 
   List<String> listB = createRandomList(listA,999000); 
   for(String s:listB){ 
       bitmap1.add(Math.abs(s.hashCode())); 
   } 
   Date date = new Date(); 
   bitmap.andNot(bitmap1); 
   Date date1 = new Date(); 
   System.out.println("testRoaringBitmap:"+(double)(date1.getTime()-date.getTime())/1000+"秒"); 
}
//testRoaringBitmap:0.022秒
测试结果：
计算耗时仅0.022s，这个结果和Java原生的BitSet时间基本相同。

总 结：

通过上述测试对比，相比其它方式采用BitMap和升级的RoaingBitmap在时间上能缩小一个数量级，效果十分明显，但是使用BitMap和RoaingBitmap存在的问题是BitMap结构只支持数字，如果是字符串需要先将字符串转成数字，字符串转数字时有一定的概率出现hash碰撞（不同的字符串转成相同的数字），因此如果能允许一定的误差，用Bitmap和RoaingBitmap是最快的。
参考文档：
https://zhuanlan.zhihu.com/p/616558669
https://www.cnblogs.com/throwable/p/15759956.html
https://segmentfault.com/a/1190000042188742
附:hash算法: http://www.partow.net/programming/hashfunctions/index.html

END


本文作者：长研架构小组(上海新炬中北团队）

本文来源：“IT那活儿”公众号

bitmap位图基线string
文章转载自IT那活儿，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

评论