海量数据处理利器RoaringBitMap原理介绍

航母

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.BitMapContainerBitMapContainer采用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.RunContainerRunContainer采用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 = 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.BitMapContainerpublic 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<