RoaringBitmap的原理与应用

RoaringBitmap

介绍

RoaringBitmap是高效压缩位图，简称RBM

官网介绍：Roaring bitmaps are compressed bitmaps. They can be hundreds of times faster

实现思路

将 32bit int（无符号的）类型数据 划分为 2^16 个桶，即最多可能有216=65536个桶，论文内称为container。用container来存放一个数值的低16位

在存储和查询数值时，将数值 k 划分为高 16 位和低 16 位，取高 16 位值找到对应的桶，然后在将低 16 位值存放在相应的 Container 中（存储时如果找不到就会新建一个）

比如要将31这个数放进roarigbitmap中，它的16进制为：0000001F,前16位为0000，后16为001F。

所以先需要根据前16位的值：0，找到它对应的通的编号为0，然后根据后16位的值：31，确定这个值应该放到桶中的哪一个位置，如下图所示。

container（小桶）的类型

在roaringbitmap中共有4种小桶：

• arraycontainer(数组容器)，
• bitmapcontainer(位图容器)，
• runcontainer(行程步长容器)，
• 类图如下：

RoaringBitmap的应用

RoaringBitmap在很多产品中都有使用，如lucene, redis, spark等，参见 https://github.com/RoaringBitmap/RoaringBitmap

import org.roaringbitmap.IntConsumer;
import org.roaringbitmap.RoaringBitmap;

public class Basic {

    public static void main(String[] args) {
        RoaringBitmap rr = RoaringBitmap.bitmapOf(1, 2, 3, 1000);
        RoaringBitmap rr2 = new RoaringBitmap();
        rr2.add(4000L, 4255L);
        rr.select(3); // 返回RBM中的第4个值,索引从0开始
        rr.rank(2); // 返回<=x的元素个数
        rr.contains(1000); // RBM是否包含1000,返回true
        rr.contains(7); // 返回false

        RoaringBitmap rror = RoaringBitmap.or(rr, rr2);// new bitmap
        rr.or(rr2); //两个RBM合并
        boolean equals = rror.equals(rr);// true
        if (!equals) throw new RuntimeException("bug");
        // 打印元素的个数
        long cardinality = rr.getLongCardinality();
        System.out.println(cardinality);
        rr.forEach(new IntConsumer() {
            @Override
            public void accept(int value) {
                System.out.println(value);
            }
        });
    }
}

针对long整数的使用

在代码中打印出进程ID, 然后在任务管理器中可以查看占用内存情况，可以看到使用的内存比较小

import org.roaringbitmap.longlong.*;

import java.lang.management.ManagementFactory;
import java.lang.management.RuntimeMXBean;

public class Roaring64BitmapTest {

    public static void main(String[] args) {
        // Roaring64NavigableMap使用示例
        LongBitmapDataProvider r = Roaring64NavigableMap.bitmapOf(1, 2, 100, 1000);
        r.addLong(1234);
        System.out.println(r.contains(1)); // true
        System.out.println(r.contains(3)); // false
        LongIterator li = r.getLongIterator();
        getProcessID();
        while (li.hasNext()) {
            System.out.println(li.next());
        }

        // Roaring64Bitmap使用示例
        Roaring64Bitmap bitmap1 = new Roaring64Bitmap();
        Roaring64Bitmap bitmap2 = new Roaring64Bitmap();
        int k = 1 << 16;
        for (int i = 0; i < 10000; ++i) {
            bitmap1.add(i * k);
            bitmap2.add(i * k + 1);
        }
        bitmap1.or(bitmap2);
        getProcessID();
        System.out.println(bitmap1.getLongCardinality());
        bitmap1.forEachInRange(0, 10 * k, new LongConsumer() {
            @Override
            public void accept(long value) {
                System.out.println(value);
            }
        });
    }

    public static final int getProcessID() {
        RuntimeMXBean runtimeMXBean = ManagementFactory.getRuntimeMXBean();
        System.out.println(runtimeMXBean.getName());
        return Integer.valueOf(runtimeMXBean.getName().split("@")[0]).intValue();
    }
}

arraycontainer

当ArrayContainer（其中每一个元素的类型为 short int 占两个字节,且里面的元素都是按从大到小的顺序排列的）的容量超过4096（即8k）后，会自动转成BitmapContainer(这个所占空间始终都是8k)存储。

4096这个阈值很聪明，低于它时ArrayContainer比较省空间，高于它时BitmapContainer比较省空间。也就是说ArrayContainer存储稀疏数据，BitmapContainer存储稠密数据，可以最大限度地避免内存浪费。

bitmapcontainer

这个容器就是位图，只不过这里位图的位数为2¹⁶（65536）个，也就是2^¹⁶个bit, 所占内存就是8kb。然后每一位用0，1表示这个数不存在或者存在，如下图：

runcontainer

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；

不过这种容器不常用，所以在使用的时候需要自行调用相关的转换函数来判断是不是需要将arraycontiner，或bitmapcontainer转换为runcontainer。

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

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

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

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

1.4 读取性能

增删改查的时间复杂度方面，BitmapContainer只涉及到位运算且可以根据下标直接寻址，显然为O(1)。而ArrayContainer和RunContainer都需要用二分查找在有序数组中定位元素，故为O(logN)。

ArrayContainer一直线性增长，在达到4096后就完全比不上BitmapContainer了

BitmapContainer是一条横线，始终占用8kb

RunContainer比较奇葩，因为和数据的连续性关系太大，因此只能画出一个上下限范围。不管数据量多少，下限始终是4字节；上限在最极端的情况下可以达到128kb。

空间占用（即序列化时写出的字节流长度）方面，BitmapContainer是恒定为8KB的。ArrayContainer的空间占用与基数（c）有关，为(2 + 2c)B；RunContainer的则与它存储的连续序列数（r）有关，为(2 + 4r)B。

1.5 与bitmap的性能对比

roaringbitmap除了比bitmap占用内存少之外，其并集和交集操作的速度也要比bitmap的快，原因如下：

- 计算上的优化

对于roaringbitmap本质上是将大块的bitmap分成各个小块，其中每个小块在需要存储数据的时候才会存在。所以当进行交集或并集运算的时候，roaringbitmap只需要去计算存在的一些块而不需要像bitmap那样对整个大的块进行计算。如果块内非常稀疏，那么只需要对这些小整数列表进行集合的 AND、OR 运算，这样的话计算量还能继续减轻。这里既不是用空间换时间，也没有用时间换空间，而是用逻辑的复杂度同时换取了空间和时间。

同时在roaringbitmap中32位长的数据，被分割成高 16 位和低 16 位，高 16 位表示块偏移，低16位表示块内位置，单个块可以表达 64k 的位长，也就是 8K 字节。这样可以保证单个块都可以全部放入 L1 Cache，可以显著提升性能

- 程序逻辑上的优化

- roaringbitmap维护了排好序的一级索引以及有序的arraycontainer，当进行交集操作的时候，只需要根据一级索引中对应的值来获取需要合并的容器，而不需要合并的容器则不需要对其进行操作直接过滤掉。

- 当进行合并的arraycontainer中数据个数相差过大的时候采用基于二分查找的方法对arraycontainer求交集,避免不必要的线性合并花费的时间开销。

- roaingbitmap在做并集的时候同样根据一级索引只对相同的索引的容器进行合并操作，而索引不同的直接添加到新的roaringbitmap上即可，不需要遍历容器。

- roaringbitmap在合并容器的时候会先预测结果，生成对应的容器，避免不必要的容器转换操作。

1.6 针对long整数的扩展【64-bit integers (long)】

虽然RoaringBitmap是为32位的情况设计的，但对64位整数进行了扩展。为此提供了两个类:Roaring64NavigableMap和Roaring64Bitmap。

Roaring64NavigableMap依赖于传统的红黑树。键是32位整数，代表元素中最重要的32位，而树的值是32位RoaringBitmap。32位RoaringBitmap表示一组元素的最低有效位。

较新的Roaring64Bitmap方法依赖ART数据结构来保存键/值对。键由元素的最重要的48位组成，而值是16位的Roaring容器。它的灵感来自 The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases by Leis et al. (ICDE '13)。