海量数据处理利器 Roaring BitMap 原理介绍

roaring,bitmap · 浏览次数 : 0

小编点评

本文主要探讨了BitMap及Roaring BitMap的原理及使用,特别是在大数据开发中的应用。文章首先介绍了布隆过滤器和Redis中的HyperLogLog在大数据判重和数量统计方面的应用,然后详细阐述了BitMap和Roaring BitMap的原理、存储方式、container类型以及Java中的相关API使用。 1. **引言**:文章开头指出,尽管布隆过滤器和Redis的HyperLogLog在高维数据判重和数量统计方面表现出色,但它们存在一定的误差。为追求100%准确性,作者推荐使用BitMap来存储数据。BitMap是一种广泛用于数据存储和搜索的数据结构,但在存储分散数据时会导致较大的内存占用。Roaring BitMap作为一种稀疏位图索引,能有效减少存储空间,提高计算性能。 2. **BitMap原理**:BitMap的基本思想是用bit位来标记某个元素对应的value,适用于快速排序、查找和去重等操作。然而,它无法存储重复数据,并且在存储稀疏数据时会造成较大的内存浪费。 3. **Roaring BitMap 原理**:Roaring BitMap是为解决BitMap在存储稀疏数据时的空间浪费问题而设计的。它将32位int型整数分为高16位和低16位处理,通过索引分片和数据桶来存储数据。Roaring BitMap采用不同类型的container来存储数据,包括ArrayContainer、BitMapContainer和RunContainer,以适应不同的数据存储需求。 4. **Roaring BitMap 相关源码介绍**:文章详细介绍了Roaring BitMap在Java中的实现,包括添加元素、ArrayContainer、BitMapContainer和RunContainer的源码实现,以及它们之间的转换关系。 5. **Roaring BitMap 使用**:文章还讨论了Roaring BitMap在Java中的相关API的使用,包括添加单个数字、添加范围数字、移除数字、遍历RBM、检测是否包含、获取基数、位与、位或、异或、取差集、取对称差集、序列化和反序列化等操作。 6. **业务实际场景应用**:最后,文章通过一个实际业务场景的应用示例,展示了Roaring BitMap在提高大数据标签处理效率方面的优势。 总结: 本文全面分析了BitMap和Roaring BitMap的原理及应用,特别是Roaring BitMap在大数据环境下的优势。通过Java API的使用和实际业务场景的演示,文章强调了Roaring BitMap在大数据处理中的高效性和实用性。

正文

作者:来自 vivo 互联网服务器团队- Zheng Rui

本文结合个人理解梳理了BitMap及Roaring BitMap的原理及使用,分别主要介绍了Roaring BitMap的存储方式及三种container类型及Java中Roaring BitMap相关API使用。

一、引言

在进行大数据开发时,我们可以使用布隆过滤器和Redis中的HyperLogLog来进行大数据的判重和数量统计,虽然这两种方法节省内存空间并且效率很高,但是也存在一些误差。如果需要100%准确的话,我们可以使用BitMap来存储数据。

BitMap 位图索引数据结构被广泛地应用于数据存储和数据搜索中,但是对于存储较为分散的数据时,BitMap会占用比较大的内存空间,因此我们更偏向于使用 Roaring BitMap稀疏位图索引进行存储。同时,Roaring BitMap广泛应用于数据库存储和大数据引擎中,例如Hive,Spark,Doris,Kylin等。

下文将分别介绍 BitMap 和 Roaring BitMap 的原理及其相关应用。

二、BitMap原理

BitMap的基本思想就是用bit位来标记某个元素对应的value,而key就是这个元素。

例如,在下图中,是一个字节代表的8位,下标为1,2,4,6的bit位的值为1,则该字节表示{1,2,4,6}这几个数。

图片

在Java中,1个int占用4个字节,如果用int来存储这四个数字的话,那么将需要4 * 4 = 16字节。

BitMap可以用于快速排序,查找,及去重等操作。优点是占用内存少(相较于数组)和运算效率高,但是缺点也非常明显,无法存储重复的数据,并且在存储较为稀疏的数据时,浪费存储空间较多。

三、Roaring BitMap 原理

3.1 存储方式

为了解决BitMap存储较为稀疏数据时,浪费存储空间较多的问题,我们引入了稀疏位图索引Roaring BitMap。Roaring BitMap 有较高的计算性能及压缩效率。下面简单介绍一下Roaring BitMap的基本原理。

Roaring BitMap处理int型整数,将32位的int型整数分为高16位和低16位分别进行处理,高16位作为索引分片,而低16位用于存储实际数据。其中每个索引对应一个数据桶(bucket),那么一共可以包含2^16 = 65536个数据块。每个数据桶使用container容器来存储低16位的部分,每个数据桶最多存储2^16 = 65536个数据。

图片

如上图所示,高16位作为索引查找具体的数据块,当前索引值为0,低16位作为value进行存储。

Roaring BitMap在进行数据存储时,会先根据高16位找到对应的索引key(二分查找),低16位作为key对应的value,先通过key检查对应的container容器,如果发现container不存在的话,就先创建一个key和对应的container,否则直接将低16位存储到对应的container中。

Roaring BitMap的精妙之处在于使用不同类型的container,接下来将对其进行介绍。

3.2 container类型

1.ArrayContainer

顾名思义,ArrayContainer直接采用数组来存储低16位数据,没有采用任何数据压缩算法,适合存储比较稀疏的数据,在Java中,使用short数组来存储,并且占用的内存空间大小和数据量成线性关系。由于short为2字节,因此n个数据为2n字节。ArrayContainer采用二分查找定位有序数组中的元素,因此时间复杂度为O(logN)。ArrayContainer的最大数据量为4096, 4096 * 2b = 8kb。

2.BitMapContainer

BitMapContainer采用BitMap的原理,就是一个没有经过压缩处理的普通BitMap,适合存储比较稠密的数据,在Java中使用Long数组存储低16位数据,每一个bit位表示一个数字。由于每个container需要存储2^16 = 65536个数据,如果通过BitMap进行存储的话,需要使用2^16个bit进行存储,即8kb的数据空间。

可以从下图中看出ArrayContainer和BitMapContainer的内存空间使用关系,当数据量小于4096时,使用ArrayContainer比较合适,当数据量大于等于4096时,使用BitMapContainer更佳。

图片

因为BitMap直接使用位运算,所以BitMapContainer的时间复杂度为O(1)。

3.RunContainer

RunContainer采用Run-Length Encoding 行程长度编码进行压缩,适合存储大量连续数据。Java中使用short数组进行存储。连续bit位程度越高的话越节省存储空间,最佳场景下(65536个数据全为1)只需要存储4字节。最差场景为所有数据都不连续,所有存储数据位置为奇数或者偶数,这种场景需要存储128kb。由于采用二分查找算法定位元素,因此时间复杂度为O(logN)。

行程长度编码即的原理是对连续出现的数字进行压缩,只记录初始数字和后续连续数量。

例如:[1,2,3,4,5,8,9,10]使用编码后的数据为[1,4,8,2]。

Java 里可以使用runOptinize()方法来对比RunContainer和其他两个Container存储空间大小,如果使用RunContainer存储空间更佳则会进行转化。

根据上面三个Container类型我们可以得知如何进行选择:

  1. Container默认使用ArrayContainer,当元素数量超过4096时,会由ArrayContainer转换BitMapContainer。

  2. 当元素数量小于等于4096时,BitMapContainer会逆向转换回ArrayContainer。

  3.  正常增删元素不会使Container直接变成RunContainer,而需要用户进行优化方法调用才会转换为最节省空间的Container。

3.3 Roaring BitMap 相关源码

介绍完Roaring BitMap的三种container类型以后,让我们了解一下,Roaring BitMap的相关源码。这里介绍一下Java中增加元素的源码实现。

public void add(final int x) {
    final short hb = Util.highbits(x);
    final int i = highLowContainer.getIndex(hb);
    if (i >= 0) {
      highLowContainer.setContainerAtIndex(i,
          highLowContainer.getContainerAtIndex(i).add(Util.lowbits(x)));
    } else {
      final ArrayContainer newac = new ArrayContainer();
      highLowContainer.insertNewKeyValueAt(-i - 1, hb, newac.add(Util.lowbits(x)));
    }
  }

Roaring BitMap首先获取添加元素的高16位,然后再调用getIndex获取高16位对应的索引,如果索引大于0,表示已经创建该索引对应的container,故直接添加相应的元素低16位即可;否则的话,说明该索引对应的container还没有被创建,先创建对应的ArrayContainer,再进行元素添加。值得一提的是,在getIndex方法中,使用了二分查找来获取索引值,所以时间复杂度为O(logn)。

// 包含一个二分查找
protected int getIndex(short x) {
  // 在二分查找之前,我们先对常见情况优化。
  if ((size == 0) || (keys[size - 1] == x)) {
    return size - 1;
  }
  // 没有碰到常见情况,我们只能遍历这个列表。
  return this.binarySearch(0, size, x);
}

对于元素添加,三种Container提供了不同的实现方式,下面将分别介绍。

1. ArrayContainer

if (cardinality == 0 || (cardinality > 0
          && toIntUnsigned(x) > toIntUnsigned(content[cardinality - 1]))) {
    if (cardinality >= DEFAULT_MAX_SIZE) {
      return toBitMapContainer().add(x);
    }
    if (cardinality >= this.content.length) {
      increaseCapacity();
    }
    content[cardinality++] = x;
  } else {
    int loc = Util.unsignedBinarySearch(content, 0, cardinality, x);
    if (loc < 0) {
      // 当标签中元素数量等于默认最大值时,把ArrayContainer转换为BitMapContainer
      if (cardinality >= DEFAULT_MAX_SIZE) {
        return toBitMapContainer().add(x);
      }
      if (cardinality >= this.content.length) {
        increaseCapacity();
      }
      System.arraycopy(content, -loc - 1, content, -loc, cardinality + loc + 1);
      content[-loc - 1] = x;
      ++cardinality;
    }
  }
  return this;
}

ArrayContainer把添加元素分成两种场景,一种走二分查找,另外一种不走二分查找。

第一种场景:不走二分查找。

当基数为0或者值大于container中的最大值,可以直接添加,因为content数组是有序的,最后一个是最大值。

当基数大于等于默认最大值4096时,ArrayContainer将转换为BitMapContainer。如果基数大于content的数组长度的话,需要将content进行扩容。最后进行赋值即可。

第二种场景:走二分查找。

先通过二分查找找到对应的插入位置,如果返回loc大于等于0,说明存在,直接返回即可,如果小于0才进行后续插入。后续操作同上,当基数大于等于默认最大值4096时,ArrayContainer将转换为BitMapContainer。如果基数大于content的数组长度的话,需要将content进行扩容。最后通过拷贝数组将元素插入到content数组中。

2. BitMapContainer

public Container add(final short i) {
  final int x = Util.toIntUnsigned(i);
  final long previous = BitMap[x / 64];
  long newval = previous | (1L << x);   BitMap[x / 64] = newval;
  if (USE_BRANCHLESS) {
    cardinality += (previous ^ newval) >>> x;
  } else if (previous != newval) {
    ++cardinality;
  }
  return this;
}

BitMap数组为BitMapContainer的存储容器存放数据的内容,数据类型为long,在这里我们只需要找到x在BitMap中的位置,并且把相应的bit位置1即可。x/64就是找到对应long的旧值,1L<<x 就是把对应的bit位置为1,再跟旧值进行或操作,就可以得到新值,再将这个新值存回到bitmap数组即可。<="" span="">

3. RunContainer

public Container add(short k) {
   
  int index = unsignedInterleavedBinarySearch(valueslength, 0, nbrruns, k);
  if (index >= 0) {
    return this;// already there
  }
  index = -index - 2;
  if (index >= 0) {
    int offset = toIntUnsigned(k) - toIntUnsigned(getValue(index));
    int le = toIntUnsigned(getLength(index));
    if (offset <= le) {
      return this;
    }
    if (offset == le + 1) {
      // we may need to fuse
      if (index + 1 < nbrruns) {
        if (toIntUnsigned(getValue(index + 1)) == toIntUnsigned(k) + 1) {
          // indeed fusion is needed
          setLength(index,
              (short) (getValue(index + 1) + getLength(index + 1) - getValue(index)));
          recoverRoomAtIndex(index + 1);
          return this;
        }
      }
      incrementLength(index);
      return this;
    }
    if (index + 1 < nbrruns) {
      // we may need to fuse
      if (toIntUnsigned(getValue(index + 1)) == toIntUnsigned(k) + 1) {
        // indeed fusion is needed
        setValue(index + 1, k);
        setLength(index + 1, (short) (getLength(index + 1) + 1));
        return this;
      }
    }
  }
  if (index == -1) {
    // we may need to extend the first run
    if (0 < nbrruns) {
      if (getValue(0) == k + 1) {
        incrementLength(0);
        decrementValue(0);
        return this;
      }
    }
  }
  makeRoomAtIndex(index + 1);
  setValue(index + 1, k);
  setLength(index + 1, (short) 0);
  return this;
}

RunContainer中的两个数据结构,nbrruns表示有多少段行程,数据类型为int,valueslength数组表示所有的行程,数据类型为short。

  1. 首先,使用二分查找+顺序查找在valueslength数组中查找元素k的插入位置index。如果查找到的index结果大于等于0那就说明k是某个行程起始值,已经存在,直接返回。

  2. -index-2是为了指向前一个行程起始值的索引。

  3. 接下来是一些偏移量和索引值的判断,主要是为了确认k是否落在上一个行程里,或者外面,如果落在上一个行程里,则直接返回,否则需要新建一个行程或者就近与一个行程混合并且将行程长度加1。

3.4 BitMap 和 Roaring BitMap 存储情况对比

public static void count(Integer inputSize) {         RoaringBitMap BitMap = new RoaringBitMap();         BitMap.add(0L, inputSize);
 
        //获取BitMap个数
        int cardinality = BitMap.getCardinality();
 
        //获取BitMap压缩大小
        int compressSizeIntBytes = BitMap.getSizeInBytes();
 
        //删除压缩(移除行程编码,将container退化为BitMapContainer 或 ArrayContainer)         BitMap.removeRunCompression();
 
        //获取BitMap不压缩大小
        int uncompressSizeIntBytes = BitMap.getSizeInBytes();
 
        System.out.println("Roaring BitMap个数:" + cardinality);
        System.out.println("最好情况,BitMap压缩大小:" + compressSizeIntBytes / 1024 + "KB");
        System.out.println("最坏情况,BitMap不压缩大小:" + uncompressSizeIntBytes / 1024 / 1024 + "MB");
 
        BitSet bitSet = new BitSet();
        for (int i = 0; i < inputSize; i++) {
            bitSet.set(i);
        }
        //获取BitMap大小
        int size = bitSet.size();
 
        System.out.println("BitMap个数:" + bitSet.length());
        System.out.println("BitMap大小:" + size / 8 / 1024 / 1024 + "MB");
    }

上述代码使用了Java内置的BitMap(BitSet) 和 Roaring BitMap进行存储大小对比,输出结果如下所示。

  • Roaring BitMap个数:1000000000

  • 最好情况,BitMap压缩大小:149KB

  • 最坏情况,BitMap不压缩大小:119MB

  • Roaring BitMap个数:1000000000

  • BitMap大小:128MB

可以发现,Roaring BitMap的压缩性能效果非常好,同等情况下,是BitMap占用内存的近一千分之一。在退化成BitMapContainer/arrayContainer之后也仍然比使用基本的BitMap存储效果好一些。

四、Roaring BitMap 使用

4.1 Java 中相关 API 使用

在Java中,Roaring BitMap提供了交并补差集等操作,如下代码所示,列举了Java中roaing BitMap的相关API使用方式。

//添加单个数字
public void add(final int x)

//添加范围数字
public void add(final long rangeStart, final long rangeEnd)

//移除数字
public void remove(final int x)

//遍历RBM
public void forEach(IntConsumer ic)

//检测是否包含
public boolean contains(final int x)

//获取基数
public int getCardinality()

//位与,取两个RBM的交集,当前RBM会被修改
public void and(final RoaringBitMap x2)

//同上,但是会返回一个新的RBM,不会修改原始的RBM,线程安全
public static RoaringBitMap and(final RoaringBitMap x1, final RoaringBitMap x2)

//位或,取两个RBM的并集,当前RBM会被修改
public void or(final RoaringBitMap x2)

//同上,但是会返回一个新的RBM,不会修改原始的RBM,线程安全
public static RoaringBitMap or(final RoaringBitMap x1, final RoaringBitMap x2)

//异或,取两个RBM的对称差,当前RBM会被修改
public void xor(final RoaringBitMap x2)

//同上,但是会返回一个新的RBM,不会修改原始的RBM,线程安全
public static RoaringBitMap xor(final RoaringBitMap x1, final RoaringBitMap x2)

//取原始值和x2的差集,当前RBM会被修改
public void andNot(final RoaringBitMap x2)

//同上,但是会返回一个新的RBM,不会修改原始的RBM,线程安全
public static RoaringBitMap andNot(final RoaringBitMap x1, final RoaringBitMap x2)

//序列化
public void serialize(DataOutput out) throws IOException
public void serialize(ByteBuffer buffer)

//反序列化
public void deserialize(DataInput in) throws IOException
public void deserialize(ByteBuffer bbf) throws IOException

对于序列化来说,Roaring BitMap官方定义了一套序列化规则,用来保证不同语言实现的兼容性。

图片

Java中可以使用serialize方法进行序列化,deserialize方法进行反序列化。

4.2 业务实际场景应用

Roaring BitMap可以用来构建大数据标签,针对类型特征来创建对应的标签。

在我们的业务场景中,有很多需要基于人群标签进行交并补集运算的场景,下面以一个场景为例,我们需要计算每天某个设备接口 在设备标签A上的查询成功率,因为设备标签A中的设备不是所有都活跃在网的,所以我们需要将设备标签A与每日日活人群标签取交集,得到的交集大小才能用作成功率计算的分母,另外拿查询成功的标签人群做分子来进行计算即可,查询时长耗时为1s。

假如没有使用标签保存集合之前,我们需要在hive表中查询出同时满足当天在网的活跃用户和设备A的用户数量,查询时长耗时在几分钟以上。两种方式相比之下,使用Roaring BitMap查询的效率更高。

图片

五、总结

本文结合个人理解梳理了BitMap及Roaring BitMap的原理及使用,分别主要介绍了Roaring BitMap的存储方式及三种container类型及Java中Roaring BitMap相关API使用,如有不足和优化建议,也欢迎大家批评指正。

参考资料:

与海量数据处理利器 Roaring BitMap 原理介绍相似的内容:

海量数据处理利器 Roaring BitMap 原理介绍

本文结合个人理解梳理了BitMap及Roaring BitMap的原理及使用,分别主要介绍了Roaring BitMap的存储方式及三种container类型及Java中Roaring BitMap相关API使用。

一文带你全面了解openGemini

处理海量遥测数据的利器—openGemini时序数据库。

前后端结合解决Excel海量公式计算的性能问题

背景 在数据密集的业务领域,尤其是金融,保险,税务等行业中,经常需要利用Excel模型,来对业务进行分析和处理。例如: 1.金融投资: 根据模型进行估值计算,并对投资风险进行评估,通过测算出投资的内部收益率(IRR),净现值(NPV)来做投资收益分析,反应项目的获利能力。 2.保险精算: 运用数学,

海量监控数据处理如何做,看华为云SRE案例分享

摘要:openGemini的设计和优化都是根据时序数据特点而来,在面对海量运维监控数据处理需求时,openGemini显然更加有针对性。 IT运维诞生于最早的信息化时代。在信息化时代,企业的信息化系统,主要为了满足企业内部管理的需求。通常是集中、可控和固化的烟囱式架构。传统IT运维,以人力运维为主,

Hive 和 Spark 分区策略剖析

随着技术的不断的发展,大数据领域对于海量数据的存储和处理的技术框架越来越多。在离线数据处理生态系统最具代表性的分布式处理引擎当属Hive和Spark,它们在分区策略方面有着一些相似之处,但也存在一些不同之处。

对接HiveMetaStore,拥抱开源大数据

本文分享自华为云社区《对接HiveMetaStore,拥抱开源大数据》,作者:睡觉是大事。 1. 前言 适用版本:9.1.0及以上 在大数据融合分析时代,面对海量的数据以及各种复杂的查询,性能是我们使用一款数据处理引擎最重要的考量。而GaussDB(DWS)服务有着强大的计算引擎,其计算性能优于MR

海量数据运维要给力,GaussDB(for Cassandra)来助力

摘要:应用运维管理平台(AOM)和Cassandra是两个不可分割的组成部分,它们共同构成了一个高效的解决方案,可以帮助企业在应用运维业务上取得巨大的优势。在这篇文章中,我们将介绍AOM和Cassandra的优势和特点,揭晓它们如何为企业保持市场竞争力的秘密。 本文分享自华为云社区《海量数据运维要给

ECharts海量数据渲染解决卡顿的4种方式

场景 周五进行需求评审的时候; 出现了一个图表,本身一个图表本没有什么稀奇的; 可是产品经理在图表的上的备注,让我觉得这个事情并不简单; 那个图表的时间跨度可以是月,年,而且时间间隔很短; 这让我意识到事情并不是想的那样简单; 然后经过简单的询问:如果选择的范围是年;数据可能会上万; 我们都知道;出

前端说你的API接口太慢了,怎么办?

当有千万条海量数据时,前端调取接口发现接口响应的太慢,前端这时让你优化一下接口,你说有几千万条数据,觉得自己尽力了,前端觉得你好菜,别急,读完这篇文章,让前端喊你一声:大佬,厉害!!! 常用的方法总结 通过合理的分页加载、索引优化、数据缓存、异步处理、压缩数据等手段,可以有效地优化接口性能,提升系统

Redis系列10:HyperLogLog实现海量数据基数统计

Redis系列1:深刻理解高性能Redis的本质 Redis系列2:数据持久化提高可用性 Redis系列3:高可用之主从架构 Redis系列4:高可用之Sentinel(哨兵模式) Redis系列5:深入分析Cluster 集群模式 追求性能极致:Redis6.0的多线程模型 追求性能极致:客户端缓