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

原创
06/19 20:59
阅读数 1.2K

作者:来自 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)
//遍历RBMpublic 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 IOExceptionpublic void serialize(ByteBuffer buffer)
//反序列化public void deserialize(DataInput in) throws IOExceptionpublic 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使用,如有不足和优化建议,也欢迎大家批评指正。


参考资料:


END

猜你喜欢

本文分享自微信公众号 - vivo互联网技术(vivoVMIC)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部