Bitmap、RoaringBitmap 原理分析

作者：京东科技 曹留界

在人群本地化实践中我们介绍了人群 ID 中所有的 pin 的偏移量可以通过 Bitmap 存储，而 Bitmap 所占用的空间大小只与偏移量的最大值有关系。假如现在要向 Bitmap 内存入两个 pin 对应的偏移量，一个偏移量为 1，另一个偏移量为 100w，那么 Bitmap 存储直接需要 100w bit 的空间吗？数据部将偏移量存入 Bitmap 时，又如何解决数据稀疏问题呢？本文将为大家解答这个问题。

一、BitMap

Bitmap 的基本思想就是用一个 bit 位来标记某个元素对应的 Value，而 Key 即是该元素。由于采用了 Bit 为单位来存储数据，因此可以大大节省存储空间。

如果想将数字 2 存入位图中，则只需要将位图数组中下标为 2 的数组值置为 1。

但是，如果现在要存储两个人群 ID 对应的偏移量，一个偏移量为 1，另一个偏移量为 100w，如果将这两个值直接放到位图数组中，那么位图数组所需要的空间就是 100wbit，会产生大量的空间浪费。那么有什么方法可以避免空间浪费吗？答案就是 RoaringBitMap！

二、RoaringBitMap

RoaringBitMap 是一种高效压缩位图，简称 RBM。RBM 的概念于 2016 年由 S. Chambi、D. Lemire、O. Kaser 等人在论文《Better bitmap performance with Roaring bitmaps》 《Consistently faster and smaller compressed bitmaps with Roaring》中提出。下面我们结合 java 中的实现对其进行介绍。

2.1 实现思路

RBM 主要将 32 位的整型（int）分为高 16 位和低 16 位（两个 short），其中高 16 位对应的数字使用 16 位整型有序数组存储，低 16 位根据不同的情况选择三种不同的 container 来存储，这三种 container 分别为：

•Array Container

底层数据结构为 short 类型的数组，直接将数字低 16 位的值存储到该数组中。short 类型的数组始终保持有序，方便使用二分查找，且不会存储重复数值。因为这种 Container 存储数据没有任何压缩，因此只适合存储少量数据。其内部数组容量是动态变化的，当容量不够时会进行扩容，最大容量为 4096。由于数组是有序的，存储和查询时都可以通过二分查找快速定位其在数组中的位置。

ArrayContainer 占用的空间大小与存储的数据量为线性关系，每个 short 为 2 字节，因此存储了 N 个数据的 ArrayContainer 占用空间大致为 2N 字节。存储一个数据占用 2 字节，存储 4096 个数据占用 8kb。

•Bitmap Container

底层实现为位图。这种 Container 使用 long[]存储位图数据。我们知道，每个 Container 处理 16 位整形的数据，也就是 0~65535，因此根据位图的原理，需要 65536 个比特来存储数据，每个比特位用 1 来表示有，0 来表示无。每个 long 有 64 位，因此需要 1024 个 long 来提供 65536 个比特。

因此，每个 BitmapContainer 在构建时就会初始化长度为 1024 的 long[]。这就意味着，不管一个 BitmapContainer 中只存储了 1 个数据还是存储了 65536 个数据，占用的空间都是同样的 8kb。

•Run Container

RunContainer 中的 Run 指的是行程长度压缩算法(Run Length Encoding)，对连续数据有比较好的压缩效果。

它的原理是，对于连续出现的数字，只记录初始数字和后续数量。即：

•对于数列11，它会压缩为11,0；

•对于数列11,12,13,14,15，它会压缩为11,4；

•对于数列11,12,13,14,15,21,22，它会压缩为11,4,21,1；

源码中的 short[] valueslength 中存储的就是压缩后的数据。

这种压缩算法的性能和数据的连续性（紧凑性）关系极为密切，对于连续的 100 个 short，它能从 200 字节压缩为 4 字节，但对于完全不连续的 100 个 short，编码完之后反而会从 200 字节变为 400 字节。

如果要分析 RunContainer 的容量，我们可以做下面两种极端的假设：

最好情况，即只存在一个数据或只存在一串连续数字，那么只会存储 2 个 short，占用 4 字节

最坏情况，0~65535 的范围内填充所有的奇数位（或所有偶数位），需要存储 65536 个 short，128kb

也就 RBM 在存入一个 32 位的整形数字时，会先按照该数字的高 16 位进行分桶，以确定该数字要存入到哪个桶中。确定好分桶位置后，再将该数字对应的低 16 位放入到当前桶所对应的 container 中。

举个栗子

以十进制数字 131122 为例，现在我们要将该数字放入到 RBM 中。第一步，先将该数字转换为 16 进制，131122 对应的十六进制为 0x00020032；其中，高十六位对应 0x0002，首先我们找到 0x0002 所在的桶，再将 131122 的低 16 位存入到对应的 container 中，131122 的低 16 位转换为 10 进制就是 50，没有超过 ArrayContainer 的容量 4096，所以将低 16 位直接放入到对应的 ArrayContainer 中。

如果要插入的数字低 16 位超过了 4096，RBM 会将 ArrayContainer 转换为 BitMapContainer。反之，如果数据在删除之后，数组中的最大数据小于 4096，RBM 会将 BitMapContainer 转换回 ArrayContainer。

RBM 处理的是 32 位的数字，如果我们想处理 Long 类型的数字怎么办呢？这个时候可以使用 Roaring64NavigableMap。Roaring64NavigableMap 也是使用拆分模式，将一个 long 类型数据，拆分为高 32 位与低 32 位，高 32 位代表索引，低 32 位存储到对应 RoaringBitmap 中，其内部是一个 TreeMap 类型的结构，会按照 signed 或者 unsigned 进行排序，key 代表高 32 位，value 代表对应的 RoaringBitmap。

三、空间占用对比

1、连续数据

分别向位图中插入 1w、10w、100w、1000w 条连续数据，并且对比 BitMap 和 RoaringBitMap 占用空间的大小。比较结果如下表所示：

@Test    public void testSizeOfBitMap() {
        //对比占用空间大小 - 10w元素        RoaringBitmap roaringBitmap3 = new RoaringBitmap();        byte[] bits2 = new byte[100000];        for (int i = 0; i < 100000; i++) {                roaringBitmap3.add(i);                bits2[i] = (byte) i;        }        System.out.println("10w数据 roaringbitmap byte size:"+ roaringBitmap3.getSizeInBytes());        System.out.println("10w数据 位图数组 byte size:"+bits2.length);
        RoaringBitmap roaringBitmap4 = new RoaringBitmap();        byte[] bits3 = new byte[1000000];        for (int i = 0; i < 1000000; i++) {            roaringBitmap4.add(i);            bits3[i] = (byte) i;        }        System.out.println("100w数据 roaringbitmap byte size:"+ roaringBitmap4.getSizeInBytes());        System.out.println("100w数据 位图数组 byte size:"+bits3.length);
        RoaringBitmap roaringBitmap5 = new RoaringBitmap();        byte[] bits4 = new byte[10000000];        for (int i = 0; i < 10000000; i++) {            roaringBitmap5.add(i);            bits4[i] = (byte) i;        }        System.out.println("1000w数据 roaringbitmap byte size:"+ roaringBitmap5.getSizeInBytes());        System.out.println("1000w数据 位图数组 byte size:"+bits4.length);    }

运行截图：

2、稀疏数据

我们知道，位图所占用空间大小只和位图中索引的最大值有关系，现在我们向位图中插入 1 和 999w 两个偏移量位的元素，再次对比 BitMap 和 RoaringBitMap 所占用空间大小。

@Test    public void testSize() {        RoaringBitmap roaringBitmap5 = new RoaringBitmap();        byte[] bits4 = new byte[10000000];        for (int i = 0; i < 10000000; i++) {            if (i == 1 || i == 9999999) {                roaringBitmap5.add(i);                bits4[i] = (byte) i;            }        }        System.out.println("两个稀疏数据 roaringbitmap byte size:"+ roaringBitmap5.getSizeInBytes());        System.out.println("两个稀疏数据 位图数组 byte size:"+bits4.length);    }

运行截图：