关于go: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 存储和计算去重状态的性能等等。

最初心愿本文为大家提供解决相似问题的一种新思路，欢送关注、或者在评论区一起交换探讨。