刚接触编程那会记得用 Bitmap 的 0 和 1 位来标识数据是否存在,主要用于排序;
后来发现只要判断一个对象在大对象集合存在性,都可以考虑使用 Bitmap;
再后来,我知道了布隆这个人使用 Hash 算法结合 Bitmap 实现了 BoomFilter,用于海量数据处理场景,我觉得布隆过滤器在做数据过滤这方面天下无敌;
后来的后来,有人问我,布隆过滤器虽然解决了数据过滤问题,但是它不支持数据修改和删除,另外如果数据稀疏,只有最低位是 1,其它都是 0,还是会造成资源浪费。又该怎么办呢?
布隆过滤器处理场景有限,然后谷歌上找到了这两遍论文《Better bitmap performance with Roaring bitmaps》
与《Consistently faster and smaller compressed bitmaps with Roaring》
主要用于处理这类问题,下面结合自己理解简单介绍下 RoaringBitmaps
。
RoaringBitmaps
简称 RBM,主要是将 32 位无符号整数按照高 16 位分桶,即最多可能有 2^16=65536 个桶,论文内称为 container。存储数据时,按照数据的高 16 位找到 container,如果找不到就会新建一个,再将低 16 位放入 container 中。也就是说,一个 RBM 就是很多 container 的集合。
RBM 的主要思想并不复杂,总结来说,有如下几点:
Array Container
和 Bitmap Container
、RunContainer
。Array Container 存放稀疏的数据,Bitmap Container 存放稠密的数据。即,若一个 Container 里面的 Integer 数量小于 4096,就用 Short 类型的有序数组来存储值。若大于 4096,就用 Bitmap 来存储值;RunContainer 则用于存储连续的数据。举个例子,连续的整数序列 11, 12, 13, 14, 15, 27, 28, 29 会被 RLE 压缩为两个二元组 11, 4, 27, 2,表示 11 后面紧跟着 4 个连续递增的值,27 后面跟着 2 个连续递增的值。如上图,就是官网给出的一个例子,三个容器分别代表了三个数据集:
上面这个例子只是说明了通过 RBM 可以对数据进行灵活分类,其它的表示形式,你不用较真。另外可能看着上面说的高 16 位存储在数组中,低 16 位存储在 Container 中,猛地一看比较迷瞪,我举个例子你就明白了。
看到这里,你可能仍然会有疑问 一个 Container 里面的 Integer 数量小于 4096,就用 Short 类型的有序数组来存储值。若大于 4096,就用 Bitmap 来存储值。这到底是什么用意呢?
这里之所以使用 4096 这个阈值,大概因为 int 的低 16 位是 2Bit, Arrary Container 中的话就是 2Byte * 4096 = 8KB;对于 Bitmap Container 来讲,2^16 个 bit 也相当于是 8KB。基本上就是相得益彰,相对的分割点。
用过 jdk1.8 HashMap 的都知道在为了对 HashMap 做进一步优化,引入了红黑树。而当链表长度太长(默认超过 8)时,链表就转换为红黑树。我们可以利用红黑树快速增删改查的特 点,提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候,又会将红黑树转化为链 表。因为在数据量较小的情况下,红黑树要维护平衡,比起链表来,性能上的优势并不明显。wcc 的,如果不纠结细节问题,RPM 的实现竟然跟 HashMap 设计思路这么相似?
在创建一个新container时,如果只插入一个元素,RBM默认会用ArrayContainer来存储。如果插入的是元素序列的话,则会先根据上面的方法计算ArrayContainer和RunContainer的空间占用大小,并选择较小的那一种进行存储。
在查找一个元素的时候,先二分算法查找高16位的ArrayContainer,如果存在且数据量低于4096,继续二分查找特定定数据,否则使用位运算。增删改查的时间复杂度方面,BitmapContainer只涉及到位运算,显然为O(1)。而ArrayContainer和RunContainer都需要用二分查找在有序数组中定位元素,故为O(logN)。
仔细阅读文章的话,你可能还有疑问,刚开始的时候只插入一个元素,那肯定是ArrayContainer,随着后面数据量增多了,怎么又有了后面的BitMapContainer?那是因为这个算法本身支持转换,具体请看下文解释。
当ArrayContainer的容量超过4096后,会自动转成BitmapContainer存储。4096是一个阈值,低于它时 ArrayContainer比较省空间,高于它时BitmapContainer也比较省空间。也就是说ArrayContainer存储稀疏数据,BitmapContainer存储稠密数据,可以最大限度地避免内存浪费。
RBM可以通过调用特定的API(名为optimize)比较ArrayContainer/BitmapContainer与等价的 RunContainer的内存占用情况,一旦RunContainer占用较小,就转换。也就是说,上图例子中的第二个ArrayContainer 可以转化为只有一个二元组0, 100的RunContainer,占用空间进一步下降到10200字节。
当然里面还涉及到多个Container之间的比较、合并等运算,例如:两个RBM做集合操作时,不同种类container之间位运算的处理方式,如ArrayContainer AND BitmapContainer,BitmapContainer OR RunContainer等;32位有时会不够用时需要对64位整数的支持;能够将RBM数据写到堆外,即内存映射;支持Kryo序列化等方式。这里面涉及到很多位移运算,复杂的一批,我也没搞明白。
java的实现:https://github.com/lemire/RoaringBitmap
redis的实现:https://github.com/aviggiano/redis-roaring
spark的实现:https://github.com/apache/spark/blob/master/core/src/main/scala/org/apache/spark/scheduler/MapStatus.scala