海量数据处理利器 Roaring BitMap 原理介绍-低调大师

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

2024-06-19 312

作者：来自 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类型我们可以得知如何进行选择：

Container默认使用ArrayContainer，当元素数量超过4096时，会由ArrayContainer转换BitMapContainer。
当元素数量小于等于4096时，BitMapContainer会逆向转换回ArrayContainer。
正常增删元素不会使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。

首先，使用二分查找+顺序查找在valueslength数组中查找元素k的插入位置index。如果查找到的index结果大于等于0那就说明k是某个行程起始值，已经存在，直接返回。
-index-2是为了指向前一个行程起始值的索引。
接下来是一些偏移量和索引值的判断，主要是为了确认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使用，如有不足和优化建议，也欢迎大家批评指正。

参考资料：

Chambi S , Lemire D , Kaser O , et al.

Better BitMap performance with Roaring

BitMaps[J]. Software—practice & Experience, 2016, 46(5):709-719.
https://RoaringBitMap.org/
https://github.com/RoaringBitMap/RoaringFormatSpec

END

探索新升级！在 ART-Pi Smart 体验 RT-Thread Smart v5.1.0

1.引言 RT-Thread Smart v5.1.0 已经正式发布。这一版本在内核和功能上做了大量的改进与增强。我们可以在ART-Pi Smart开发板尽情探索这一新版更完善更强大的RT-Thread Smart操作系统。ART-Pi Smart开发板搭载了米尔科技的i.MX6ULL核心板，硬件设计和制作由韦东山团队完成，整体的BSP板级支持包由社区完成。这是首个运行 RT-Thread Smart 的 ARM Cortex-A7 开发板，具有强大的硬件性能和丰富的外设接口，非常适合学习，开发和调试RT-Thread Smart系统。硬件规格情况 🔗开发板购买链接：https://m.tb.cn/h.gUlY2J1?tk=7ah8Wy7fME1 在ART-Pi Smart的板卡上包括了百兆以太网，TF卡插槽，USB device，USB host接口，以及RW007 WiFi模块，Type-C的USB UART，RGB888 FPC座，Camera FPC座等资源。核心板上板载i.MX6ULL 800MHz ARM Cortex-A7单核32位处理器，512MB DDR3内存，4...

2024-06-13

373

DataOps真能“降本增效”？

在各行各业中，越来越多的公司开始重视收集数据，并寻找创新方法来获得真实可行的商业成果，并且愿意投入大量时间和金钱来实现这一目标。据IDC称，数据和分析软件及云服务市场规模在 2021 年达到了 900 亿美元，随着企业继续对人工智能和机器学习 (AI/ML) 和现代数据计划进行投资，预计到 2026 年将增长一倍以上。然而，尽管投入了大量资金，数据项目往往收效甚微。麦肯锡最近对高级主要分析项目进行的一项调查发现，公司 80% 的时间都花在准备数据等重复性任务上，而这些任务产生的增值作用有限。此外，他们还发现，只有 10% 的公司认为他们已经控制住了这个问题。项目为何失败？尽管增加了投资和关注，数据项目的失败率为什么仍然如此之高？许多变量都会影响项目的成功，经常被提及的因素包括项目复杂性和对应的开发人才技术水平。企业也意识到，许多数据项目都失败了，是因为他们难以在生产中大规模实施数据计划。这导致了 DataOps 的出现，成为克服大数据项目中常见挑战的新框架。DataOps 是敏捷工程和 DevOps 最佳实践在数据管理领域的应用，能帮助企业快速将新见解转化为完全可操作的生产...

2024-06-20

300

发表评论

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。