引言

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

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

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

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

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

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

1 什么是 RoaringBitmap

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

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

源碼：

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

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

• 高 16位 會(huì)被作為 key 存儲(chǔ)到 short[] keys中
• 低 16 位則被看做 value，存儲(chǔ)到 Container[] values中的某個(gè) Container 中

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

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

3 三種 Container

Container 是 RoaringBitmap的核心，我們結(jié)合上面的圖會(huì)發(fā)現(xiàn)每個(gè) 32 位整形（int）的高 16 位已經(jīng)作為key 存儲(chǔ)在 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 直接存儲(chǔ)在 short[] content中，因?yàn)槭菙?shù)組，始終保持順序存儲(chǔ)且不會(huì)重復(fù)，有利于二分查找。Container 存儲(chǔ)數(shù)據(jù)沒(méi)有任何壓縮，只適合存儲(chǔ)少量數(shù)據(jù)。

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

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

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

3.3 RunContainer

源碼：

private short[] valueslength;
int nbrruns;

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

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

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

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

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

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

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

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

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

小結(jié)一下：

4 Go 使用 RoaringBitmap

Go 語(yǔ)言支持了 RoaringBitmap，安裝 roaring 庫(kù)：

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

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

下面介紹一些 RoaringBitmap 集合運(yùn)算的示例：

4.1 并集運(yùn)算

// 創(chuàng)建兩個(gè) 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)
// 計(jì)算并集
rb3 := roaring.Or(rb1, rb2)
// 輸出結(jié)果
fmt.Println(rb3.ToArray())
// Output: [1 2 3 4 5]

4.2 交集運(yùn)算

// 創(chuàng)建兩個(gè) 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)
// 計(jì)算交集
rb3 := roaring.And(rb1, rb2)
// 輸出結(jié)果
fmt.Println(rb3.ToArray())
// Output: [3]

4.3 差集運(yùn)算

// 創(chuàng)建兩個(gè) 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)
// 計(jì)算差集
rb3 := roaring.AndNot(rb1, rb2)
// 輸出結(jié)果
fmt.Println(rb3.ToArray())
// Output: [1 2]

4.4 異或運(yùn)算

// 創(chuàng)建兩個(gè) 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)
// 計(jì)算異或
rb3 := roaring.Xor(rb1, rb2)
// 輸出結(jié)果
fmt.Println(rb3.ToArray())
// Output: [1 2 4 5]

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

5 總結(jié)

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

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

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