首先，redis的bitmap占用空间是很恐怖的，512M，就算用的很少也是512M

但是使用概率型数据结构，比如hyperloglog，省空间，但是有误差，且只能增不能删

又想要大量标记，又不想有误差，又不想占用大空间，解决方案 roaring bitmap

对稀疏位图进行压缩，减少内存占用并提高效率。比较有代表性的有WAH、EWAH、Concise，以及RoaringBitmap。前三种算法都是基于行程长度编码（Run-length encoding, RLE）做压缩的，而RoaringBitmap算是它们的改进

  1. 支持动态修改位图（静态的位图有其它压缩方式）
  2. 利用SIMD加速位图操作

image-20201214204833017

32位无符号整数按照高16位分桶，即最多可能有216=65536个桶，论文内称为container。存储数据时，按照数据的高16位找到container（找不到就会新建一个），再将低16位放入container中。也就是说，一个RBM就是很多container的集合

  • 第一层称之为Chunk，每个Chunk表示该区间取值范围的base(n2^16, 0<= n < 2^16)，如果该取值范围内没有数据则Chunk不会创建
  • 第二层称之为Container，会依据数据分布进行创建（Container内的值实际是区间内的offset）

ArrayContainer

当桶内数据的基数不大于4096时，会采用它来存储，其本质上是一个unsigned short类型的有序数组。数组初始长度为4，随着数据的增多会自动扩容（但最大长度就是4096）。另外还维护有一个计数器，用来实时记录基数。

  • 当区间内数量少于4096时，数组占用更紧凑；多于4096，则使用位图更经济

BitmapContainer

当桶内数据的基数大于4096时，会采用它来存储，其本质就是上一节讲过的普通位图，用长度固定为1024的unsigned long型数组表示，亦即位图的大小固定为216位（8KB）。它同样有一个计数器。

上图中的第三个container基数远远大于4096，所以要用BitmapContainer存储。

RunContainer

RunContainer在图中并未示出，初始的RBM实现中也没有它，而是在本节开头的第二篇论文中新加入的。它使用可变长度的unsigned short数组存储用行程长度编码（RLE）压缩后的数据。

AAAAAAbbbXXXXXt
6A3b5X1t

由此可见，RunContainer的压缩效果可好可坏。考虑极端情况：如果所有数据都是连续的，那么最终只需要4字节；如果所有数据都不连续（比如全是奇数或全是偶数），那么不仅不会压缩，还会膨胀成原来的两倍大。所以，RBM引入RunContainer是作为其他两种container的折衷方案。

O(logn)的查找性能：

  • 首先二分查找key值的高16位是否在分片（chunk）中
  • 如果分片存在，则查找分片对应的Container是否存
    • 如果Bitmap Container，查找性能是O(1)
    • 其它两种Container，需要进行二分查找

参考链接

  • 论文地址 https://arxiv.org/pdf/1603.06549.pdf
  • 官网 http://roaringbitmap.org/，有各种实现 c实现 https://github.com/RoaringBitmap/CRoaring
  • redis的bitmap不是这个方案，社区实现了一个module https://github.com/aviggiano/redis-roaring，直接搬croaring
  • 图来自 https://blog.bcmeng.com/post/doris-bitmap.html 这篇介绍，doris了解一下，doris和clickhouse啥区别？
    • https://github.com/apache/incubator-doris
    • 他这篇hbase rowkey设计也不错，基本覆盖了书里介绍的内容 https://blog.bcmeng.com/post/hbase-rowkey.html
  • 本文内容整理自 https://zhuanlan.zhihu.com/p/39828878和https://www.jianshu.com/p/818ac4e90daf
  • sigmod2021有一个新的设计 Tree-Encoded Bitmaps http://db.in.tum.de/~lang/papers/tebs.pdf 值得研究一下，这里留个坑 TODO