RoaringBitmap 的原理及在 Go 中如何使用

今天我们聊聊 `RoaringBitmap`（咆哮位图）。在海量数据背景下，我们通常需要快速对数据计算、中间存储的需求。一系列专门为大数据准备的数据结构应运而生，常见的有 `HyperLogLog`、`BloomFilter`等。 我们看一道老生常谈的面试题： > 给定含有40亿个不重复的位于[0, 2^32 - 1]区间内的整数的集合，如何快速判定某个数是否在该集合内？ 首先，40 亿在存储上我们需要消耗 40亿 * 32 位 = 160 亿 Byte，大致是 16000 MB 即 14.9 GB 的内存，显然这是我们不能接受的。如果你给出的是这个答案，那么你就已经输了！ 我们可以用位图来存储，第 0 个 bit 表示数字 0，第 1 个 Bit 表示数字 1，以此类推。如果某个数位于原集合内，就将它对应的位图内的 bit 置为 1，否则保持为 0。这样只占用了 512MB 的内存，不到原来的 3.4%。 我们会发现当数据稀疏的时候，也需要要开辟这么大的内存空间，就发挥不出其存储效率。为了解决位图不适应稀疏存储的问题，`RoaringBitmap`（咆哮位图）诞生了，因此本文重点探讨它。下面简称 RBM。 ## 1 什么是 RoaringBitmap 是一种基于位图的数据结构，可以高效地存储大量的非负整数，并支持多种集合运算，如并集、交集、差集等。它可以高效地判断一个元素是否在集合中，并且可以使用很少的空间来存储集合。 ## 2 数据结构 源码： ``` short[] keys; Container[] values; int size; ``` `RoaringBitmap` 当前有两个版本，分别用来存储 32 位和 64 位整数。以 32 位为例，RBM 会将 32 位的整形（int）拆分成高 16 位和低 16位 两部分来处理。其中 - 高 16位 会被作为 key 存储到 `short[] keys`中 - 低 16 位则被看做 value，存储到 `Container[] values`中的某个 Container 中 keys 和 values 通过下标一一对应。size 则标示了当前包含的 key-value pair的数量，即 keys 和 values 中有效数据的数量。  **注意：keys 数组永远保持有序，方便二分查找！** **** ## 3 三种 Container Container 是 `RoaringBitmap`的核心，我们结合上面的图会发现每个 32 位整形（int）的高 16 位已经作为key 存储在 RoaringArray 中了，那么 Container 只需要处理低 16 位的数据即可。 ### 3.1 ArrayContainer 源码： ``` private static final int DEFAULT_INIT_SIZE = 4; private static final int ARRAY_LAZY_LOWERBOUND = 1024; static final int DEFAULT_MAX_SIZE = 4096; private static final long serialVersionUID = 1L; protected int cardinality; short[] content; ``` 从源码可以可以看出 16 位数据 value 直接存储在 `short[] content`中，因为是数组，始终保持顺序存储且不会重复，有利于二分查找。Container 存储数据没有任何压缩，只适合存储少量数据。 ArrayContainer 占用的空间大小与存储的数据量为线性关系，每个 short 大小为 2 kb，所以存储了 N 个数据的ArrayContainer 占用空间大致为 2N kb。存储一个数据需要占用 2kb，存储 4096 需要占用 8kb。 上面 DEFAULT_MAX_SIZE 值为 4096，可以知道，当容量超过这个值的时候会将当前 Container 替换为BitmapContainer。 ### 3.2 BitmapContainer 源码： ``` private static final int DEFAULT_INIT_SIZE = 4; private static final int ARRAY_LAZY_LOWERBOUND = 1024; static final int DEFAULT_MAX_SIZE = 4096; private static final long serialVersionUID = 1L; protected int cardinality; short[] content; ``` BitmapContainer 底层用了 `long[]` 存储位图数据。RMB 每个 `Container`处理 16 位整形（int）数据，0~65535，需要 65536 个 bit 来存储数据，每个 bit 位用 1 来表示有，0 来表示无。每个 long 有 64 位，所以需要 1024 个 long 来提供 65536 个 bit。 BitmapContainer 中无论存储了 1 个还是存储了 65536 个数据，其占用的空间都是同样的 8 kb **（4096）。** ### 3.3 RunContainer 源码： ``` private short[] valueslength; int nbrruns; ``` RunContainer 又称行程长度压缩算法(Run Length Encoding)，在连续数据上压缩效果显著。 RunContainer 原理在连续出现的数字，只会记录其初始数字和后续数量，举个例子： - 数列 22，它会压缩为 22,0； - 数列 22,23,24 它会压缩为 22,3； - 数列 22,23,24,32,33，它会压缩为 22,3,32,1； 其中，`short[] valueslength`中存储的就是压缩后的数据。 可以看出，这种压缩算法在性能和数据的连续性（紧凑性）关系极为密切， - 在连续的 100 个 short，可以将 200 字节压缩成 4 个 kb。 - 对于不连续的 100 个 short，编码完之后会从 200 字节变为 400 kb。 如果要分析RunContainer的容量，我们可以做下面两种极端的假设： - 最优情况，只存在一个数据或者一串连续数字，存储 2 个 short 会占用 4 kb。 <!----> - 最差情况，0~65535 的范围内填充所有的不连续数字，(全部奇数位或全部偶数位)，需要存储 65536 个short 占用 128 kb。 小结一下：  ## 4 Go 使用 RoaringBitmap Go 语言支持了 RoaringBitmap，安装 roaring 库： ``` go get -u github.com/RoaringBitmap/roaring // go get -u github.com/RoaringBitmap/roaring/roaring64 ``` RoaringBitmap 支持多种集合运算，包括并集、交集、差集、异或等，这些运算都可以在高效地处理大规模数据集的同时，避免内存溢出和性能问题。 下面介绍一些 RoaringBitmap 集合运算的示例： ### 4.1 并集运算 ``` // 创建两个 RoaringBitmap rb1 := roaring.NewBitmap() rb2 := roaring.NewBitmap() // 添加元素 rb1.Add(1) rb1.Add(2) rb1.Add(3) rb2.Add(3) rb2.Add(4) rb2.Add(5) // 计算并集 rb3 := roaring.Or(rb1, rb2) // 输出结果 fmt.Println(rb3.ToArray()) // Output: [1 2 3 4 5] ``` ### 4.2 交集运算 ``` // 创建两个 RoaringBitmap rb1 := roaring.NewBitmap() rb2 := roaring.NewBitmap() // 添加元素 rb1.Add(1) rb1.Add(2) rb1.Add(3) rb2.Add(3) rb2.Add(4) rb2.Add(5) // 计算交集 rb3 := roaring.And(rb1, rb2) // 输出结果 fmt.Println(rb3.ToArray()) // Output: [3] ``` ### 4.3 差集运算 ``` // 创建两个 RoaringBitmap rb1 := roaring.NewBitmap() rb2 := roaring.NewBitmap() // 添加元素 rb1.Add(1) rb1.Add(2) rb1.Add(3) rb2.Add(3) rb2.Add(4) rb2.Add(5) // 计算差集 rb3 := roaring.AndNot(rb1, rb2) // 输出结果 fmt.Println(rb3.ToArray()) // Output: [1 2] ``` ### 4.4 异或运算 ``` // 创建两个 RoaringBitmap rb1 := roaring.NewBitmap() rb2 := roaring.NewBitmap() // 添加元素 rb1.Add(1) rb1.Add(2) rb1.Add(3) rb2.Add(3) rb2.Add(4) rb2.Add(5) // 计算异或 rb3 := roaring.Xor(rb1, rb2) // 输出结果 fmt.Println(rb3.ToArray()) // Output: [1 2 4 5] ``` 小结一下，RoaringBitmap 可以很方便地进行集合运算，这些运算都可以在高效地处理大规模数据集的同时，避免内存溢出和性能问题。同时，RoaringBitmap 还提供了丰富的 API 接口，支持更多高级的操作和应用场景。 ## 5 总结 本文阐述了 `RoaringBitmap`的基础原理、数据结构和 Container 源码，也列举了 Go 语言常用的位运算。因为最近在业务场景里使用到了 `RoaringBitmap`，所以想和 xdm 介绍一下。在大数据的应用场景使用 `RoaringBitmap` 确实能够达到降本增效的作用。 大数据方面还有很多方向可以做，比如通过 `RoaringBitmap` 优化 Redis 中自带的 bitmap，通过 `RoaringBitmap` 也可以提高、优化 Flink 存储和计算去重状态的性能等等。 最后希望本文为大家提供解决类似问题的一种新思路，欢迎关注、或者在评论区一起交流探讨。