引言

今天我們聊聊 RoaringBitmap（咆哮位圖）。在海量數(shù)據(jù)背景下，我們通常需要快速對數(shù)據(jù)計算、中間存儲的需求。一系列專門為大數(shù)據(jù)準(zhǔn)備的數(shù)據(jù)結(jié)構(gòu)應(yīng)運而生，常見的有 HyperLogLog、BloomFilter等。

我們看一道老生常談的面試題：

給定含有40億個不重復(fù)的位于[0, 2^32 - 1]區(qū)間內(nèi)的整數(shù)的集合，如何快速判定某個數(shù)是否在該集合內(nèi)？

首先，40 億在存儲上我們需要消耗 40億 * 32 位 = 160 Byte，大致是 16000 MB 即 14.9 GB 的內(nèi)存，顯然這是我們不能接受的。如果你給出的是這個答案，那么你就已經(jīng)輸了！

我們可以用位圖來存儲，第 0 個 bit 表示數(shù)字 0，第 1 個 Bit 表示數(shù)字 1，以此類推。如果某個數(shù)位于原集合內(nèi)，就將它對應(yīng)的位圖內(nèi)的 bit 置為 1，否則保持為 0。這樣只占用了 512MB 的內(nèi)存，不到原來的 3.4%。

我們會發(fā)現(xiàn)當(dāng)數(shù)據(jù)稀疏的時候，也需要要開辟這么大的內(nèi)存空間，就發(fā)揮不出其存儲效率。為了解決位圖不適應(yīng)稀疏存儲的問題，RoaringBitmap（咆哮位圖）誕生了，因此本文重點探討它。下面簡稱 RBM。

1 什么是 RoaringBitmap

是一種基于位圖的數(shù)據(jù)結(jié)構(gòu)，可以高效地存儲大量的非負整數(shù)，并支持多種集合運算，如并集、交集、差集等。它可以高效地判斷一個元素是否在集合中，并且可以使用很少的空間來存儲集合。

2 數(shù)據(jù)結(jié)構(gòu)

源碼：

short[] keys;
Container[] values;
int size;

RoaringBitmap 當(dāng)前有兩個版本，分別用來存儲 32 位和 64 位整數(shù)。以 32 位為例，RBM 會將 32 位的整形（int）拆分成高 16 位和低 16位 兩部分來處理。其中

• 高 16位 會被作為 key 存儲到 short[] keys中
• 低 16 位則被看做 value，存儲到 Container[] values中的某個 Container 中

keys 和 values 通過下標(biāo)一一對應(yīng)。size 則標(biāo)示了當(dāng)前包含的 key-value pair的數(shù)量，即 keys 和 values 中有效數(shù)據(jù)的數(shù)量。

注意：keys 數(shù)組永遠保持有序，方便二分查找！

3 三種 Container

Container 是 RoaringBitmap的核心，我們結(jié)合上面的圖會發(fā)現(xiàn)每個 32 位整形（int）的高 16 位已經(jīng)作為key 存儲在 RoaringArray 中了，那么 Container 只需要處理低 16 位的數(shù)據(jù)即可。

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 位數(shù)據(jù) value 直接存儲在 short[] content中，因為是數(shù)組，始終保持順序存儲且不會重復(fù)，有利于二分查找。Container 存儲數(shù)據(jù)沒有任何壓縮，只適合存儲少量數(shù)據(jù)。

ArrayContainer 占用的空間大小與存儲的數(shù)據(jù)量為線性關(guān)系，每個 short 大小為 2 kb，所以存儲了 N 個數(shù)據(jù)的ArrayContainer 占用空間大致為 2N kb。存儲一個數(shù)據(jù)需要占用 2kb，存儲 4096 需要占用 8kb。

上面 DEFAULT_MAX_SIZE 值為 4096，可以知道，當(dāng)容量超過這個值的時候會將當(dāng)前 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[] 存儲位圖數(shù)據(jù)。RMB 每個 Container處理 16 位整形（int）數(shù)據(jù)，0~65535，需要 65536 個 bit 來存儲數(shù)據(jù)，每個 bit 位用 1 來表示有，0 來表示無。每個 long 有 64 位，所以需要 1024 個 long 來提供 65536 個 bit。

BitmapContainer 中無論存儲了 1 個還是存儲了 65536 個數(shù)據(jù)，其占用的空間都是同樣的 8 kb （4096）。

3.3 RunContainer

源碼：

private short[] valueslength;
int nbrruns;

RunContainer 又稱行程長度壓縮算法(Run Length Encoding)，在連續(xù)數(shù)據(jù)上壓縮效果顯著。

RunContainer 原理在連續(xù)出現(xiàn)的數(shù)字，只會記錄其初始數(shù)字和后續(xù)數(shù)量，舉個例子：

• 數(shù)列 22，它會壓縮為 22,0；
• 數(shù)列 22,23,24 它會壓縮為 22,3；
• 數(shù)列 22,23,24,32,33，它會壓縮為 22,3,32,1；

其中，short[] valueslength中存儲的就是壓縮后的數(shù)據(jù)。

可以看出，這種壓縮算法在性能和數(shù)據(jù)的連續(xù)性（緊湊性）關(guān)系極為密切，

• 在連續(xù)的 100 個 short，可以將 200 字節(jié)壓縮成 4 個 kb。
• 對于不連續(xù)的 100 個 short，編碼完之后會從 200 字節(jié)變?yōu)?400 kb。

如果要分析RunContainer的容量，我們可以做下面兩種極端的假設(shè)：

• 最優(yōu)情況，只存在一個數(shù)據(jù)或者一串連續(xù)數(shù)字，存儲 2 個 short 會占用 4 kb。

• 最差情況，0~65535 的范圍內(nèi)填充所有的不連續(xù)數(shù)字，(全部奇數(shù)位或全部偶數(shù)位)，需要存儲 65536 個short 占用 128 kb。

小結(jié)一下：

4 Go 使用 RoaringBitmap

Go 語言支持了 RoaringBitmap，安裝 roaring 庫：

go get -u github.com/RoaringBitmap/roaring
// go get -u github.com/RoaringBitmap/roaring/roaring64

RoaringBitmap 支持多種集合運算，包括并集、交集、差集、異或等，這些運算都可以在高效地處理大規(guī)模數(shù)據(jù)集的同時，避免內(nèi)存溢出和性能問題。

下面介紹一些 RoaringBitmap 集合運算的示例：

4.1 并集運算

// 創(chuàng)建兩個 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)
// 輸出結(jié)果
fmt.Println(rb3.ToArray())
// Output: [1 2 3 4 5]

4.2 交集運算

// 創(chuàng)建兩個 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)
// 輸出結(jié)果
fmt.Println(rb3.ToArray())
// Output: [3]

4.3 差集運算

// 創(chuàng)建兩個 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)
// 輸出結(jié)果
fmt.Println(rb3.ToArray())
// Output: [1 2]

4.4 異或運算

// 創(chuàng)建兩個 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)
// 輸出結(jié)果
fmt.Println(rb3.ToArray())
// Output: [1 2 4 5]

小結(jié)一下，RoaringBitmap 可以很方便地進行集合運算，這些運算都可以在高效地處理大規(guī)模數(shù)據(jù)集的同時，避免內(nèi)存溢出和性能問題。同時，RoaringBitmap 還提供了豐富的 API 接口，支持更多高級的操作和應(yīng)用場景。

5 總結(jié)

本文闡述了 RoaringBitmap的基礎(chǔ)原理、數(shù)據(jù)結(jié)構(gòu)和 Container 源碼，也列舉了 Go 語言常用的位運算。因為最近在業(yè)務(wù)場景里使用到了 RoaringBitmap，所以想和 xdm 介紹一下。在大數(shù)據(jù)的應(yīng)用場景使用 RoaringBitmap 確實能夠達到降本增效的作用。

大數(shù)據(jù)方面還有很多方向可以做，比如通過 RoaringBitmap 優(yōu)化 Redis 中自帶的 bitmap，通過 RoaringBitmap 也可以提高、優(yōu)化 Flink 存儲和計算去重狀態(tài)的性能等等。

以上就是RoaringBitmap原理及在Go中的使用詳解的詳細內(nèi)容，更多關(guān)于Go RoaringBitmap原理的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論