关于bitmap:BitmapRoaringBitmap原理分析

作者：京东科技 曹留界

在人群本地化实际中咱们介绍了人群 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);
    }

运行截图：