Go 每日一庫(kù)之 roaring
簡(jiǎn)介
集合是軟件中的基本抽象。實(shí)現(xiàn)集合的方法有很多，例如 hash set、tree等。要實(shí)現(xiàn)一個(gè)整數(shù)集合，位圖（bitmap，也稱(chēng)為 bitset 位集合，bitvector 位向量）是個(gè)不錯(cuò)的方法。使用 n 個(gè)位（bit），我們可以表示整數(shù)范圍[0, n)。如果整數(shù) i 在集合中，第 i 位設(shè)置為 1。這樣集合的交集（intersection）、并集（unions）和差集（difference）可以利用整數(shù)的按位與、按位或和按位與非來(lái)實(shí)現(xiàn)。而計(jì)算機(jī)執(zhí)行位運(yùn)算是非常迅速的。
bitset 在某些場(chǎng)景中會(huì)消耗大量的內(nèi)存。例如，設(shè)置第 1,000,000 位，需要占用超過(guò) 100kb 的內(nèi)存。為此 bitset 庫(kù)的作者又開(kāi)發(fā)了壓縮位圖庫(kù)：roaring。
本文首先介紹了 roaring 的使用。最后分析 roaring 的文件存儲(chǔ)格式。
安裝
本文代碼使用 Go Modules。
創(chuàng)建目錄并初始化：
$ mkdir -p roaring && cd roaring
$ go mod init github.com/darjun/go-daily-lib/roaring安裝roaring庫(kù)：
$ go get -u github.com/RoaringBitmap/roaring使用
基本操作
func main() {
bm1 := roaring.BitmapOf(1, 2, 3, 4, 5, 100, 1000)
fmt.Println(bm1.String()) // {1,2,3,4,5,100,1000}
fmt.Println(bm1.GetCardinality()) // 7
fmt.Println(bm1.Contains(3)) // true
bm2 := roaring.BitmapOf(1, 100, 500)
fmt.Println(bm2.String()) // {1,100,500}
fmt.Println(bm2.GetCardinality()) // 3
fmt.Println(bm2.Contains(300)) // false
bm3 := roaring.New()
bm3.Add(1)
bm3.Add(11)
bm3.Add(111)
fmt.Println(bm3.String()) // {1,11,111}
fmt.Println(bm3.GetCardinality()) // 3
fmt.Println(bm3.Contains(11)) // true
bm1.Or(bm2) // 執(zhí)行并集
fmt.Println(bm1.String()) // {1,2,3,4,5,100,500,1000}
fmt.Println(bm1.GetCardinality()) // 8
fmt.Println(bm1.Contains(500)) // true
bm2.And(bm3) // 執(zhí)行交集
fmt.Println(bm2.String()) // {1}
fmt.Println(bm2.GetCardinality()) // 1
fmt.Println(bm2.Contains(1)) // true
}
上面演示了兩種創(chuàng)建 roaring bitmap 的方式：
roaring.BitmapOf()：傳入集合元素，創(chuàng)建位圖并添加這些元素roaring.New()：創(chuàng)建一個(gè)空位圖
首先，我們創(chuàng)建了一個(gè)位圖 bm1:{1,2,3,4,5,100,1000}。輸出它的字符串表示，集合大小，檢查 3 是否在集合中。
然后又創(chuàng)建了一個(gè)位圖 bm2:{1,100,500}。輸出檢查三連。
接著創(chuàng)建了一個(gè)空位圖 bm3，依次添加元素 1，11，111。輸出檢查三連。
然后我們對(duì) bm1 和 bm2 執(zhí)行并集，結(jié)果直接存放在 bm1 中。由于集合中的元素各不相同，此時(shí) bm1 中的元素為{1,2,3,4,5,100,500,1000}，大小為 8。
再然后我們對(duì) bm2 和 bm3 執(zhí)行交集，結(jié)果直接存放在 bm2 中。此時(shí) bm2 中的元素為{1}，大小為 1。
可以看出 roaring 提供的基本操作與 bitset 大體相同。只是命名完全不一樣，在使用時(shí)需要特別注意。
bm.String()：返回 bitmap 的字符串表示bm.Add(n)：添加元素 nbm.GetCardinality()：返回集合的基數(shù)（Cardinality），即元素個(gè)數(shù)bm1.And(bm2)：執(zhí)行集合交集，會(huì)修改 bm1bm1.Or(bm2)：執(zhí)行集合并集，會(huì)修改 bm1
迭代
roaring 位圖支持迭代。
func main() {
bm := roaring.BitmapOf(1, 2, 3, 4, 5, 100, 1000)
i := bm.Iterator()
for i.HasNext() {
fmt.Println(i.Next())
}
}
與很多編程語(yǔ)言支持的迭代器一樣，先調(diào)用對(duì)象的Iterator()返回一個(gè)迭代器，然后循環(huán)調(diào)用HasNext()檢查是否有下一個(gè)元素，調(diào)用i.Next()返回下一個(gè)元素。
上面代碼依次輸出 1，2，3，4，5，100，1000。
并行操作
roaring 支持位圖集合運(yùn)算的并行執(zhí)行。可以指定使用多少個(gè) goroutine 對(duì)集合執(zhí)行交集、并集等。同時(shí)可以傳入可變數(shù)量的位圖集合：
func main() {
bm1 := roaring.BitmapOf(1, 2, 3, 4, 5, 100, 1000)
bm2 := roaring.BitmapOf(1, 100, 500)
bm3 := roaring.BitmapOf(1, 10, 1000)
bmAnd := roaring.ParAnd(4, bm1, bm2, bm3)
fmt.Println(bmAnd.String()) // {1}
fmt.Println(bmAnd.GetCardinality()) // 1
fmt.Println(bmAnd.Contains(1)) // true
fmt.Println(bmAnd.Contains(100)) // false
bmOr := roaring.ParOr(4, bm1, bm2, bm3)
fmt.Println(bmOr.String()) // {1,2,3,4,5,10,100,500,1000}
fmt.Println(bmOr.GetCardinality()) // 9
fmt.Println(bmOr.Contains(10)) // true
}
并行操作使用相應(yīng)接口的Par*版本，第一個(gè)參數(shù)指定 worker 數(shù)量，接著傳入任意多個(gè) bitmap。
寫(xiě)入與讀取
roaring 可以將壓縮的位圖寫(xiě)入到文件中，并且格式與其他語(yǔ)言的實(shí)現(xiàn)保持兼容。也就是說(shuō)，我們可以用 Go 將 roaring 位圖寫(xiě)入文件，然后通過(guò)網(wǎng)絡(luò)發(fā)送給另一臺(tái)機(jī)器，在這臺(tái)機(jī)器上使用 C++ 或 Java 的實(shí)現(xiàn)讀取這個(gè)文件。
func main() {
bm := roaring.BitmapOf(1, 3, 5, 7, 100, 300, 500, 700)
buf := &bytes.Buffer{}
bm.WriteTo(buf)
newBm := roaring.New()
newBm.ReadFrom(buf)
if bm.Equals(newBm) {
fmt.Println("write and read back ok.")
}
}
WriteTo(w io.Writer)：寫(xiě)入一個(gè) io.Writer，可以是內(nèi)存（byte.Buffer），可以是文件（os.File），甚至可以是網(wǎng)絡(luò)（net.Conn)ReadFrom(r io.Reader)：從一個(gè) io.Reader 中讀取，來(lái)源同樣可以是內(nèi)存、文件或網(wǎng)絡(luò)等
注意WriteTo的返回值為size和err，使用時(shí)需要處理錯(cuò)誤情況。ReadFrom也是返回size和err，同樣需要處理處理。
64 位版本
默認(rèn)情況下，roaring 位圖只能用來(lái)存儲(chǔ) 32 位整數(shù)。所以 roaring 位圖最多能包含 4294967296（2^32） 個(gè)整數(shù)。
roaring 也提供了存儲(chǔ) 64 位整數(shù)的擴(kuò)展，即github.com/RoaringBitmap/roaring/roaring64。提供的接口基本相同。然而，64 位版本不保證與 Java/C++ 等格式兼容。
存儲(chǔ)格式
roaring 可以寫(xiě)入文件中，也可以從文件中讀取。并且提供多種語(yǔ)言兼容的格式。下面我們一起來(lái)看看存儲(chǔ)的格式。
roaring 位圖默認(rèn)只能存儲(chǔ) 32 位的整數(shù)。在序列化時(shí)，將這些整數(shù)分容器（container）存儲(chǔ)。每個(gè)容器有一個(gè) 16 位表示的基數(shù)（Cardinality，即元素個(gè)數(shù)，范圍[1,2^16]）和一個(gè)鍵（key）。鍵取元素的最高有效 16 位（most significant），所以鍵的范圍為[0, 65536)。這樣如果兩個(gè)整數(shù)的最高 16 位有效位相同，那么它們將被保存在同一個(gè)容器中。這樣做還有一個(gè)好處：可以減少占用的空間。
所有整數(shù)均采用小端存儲(chǔ)。
概覽
roaring 采用的存儲(chǔ)格式布局如下：
從上到下依次介紹。
開(kāi)始部分是一個(gè) Cookie Header。它用來(lái)識(shí)別一個(gè)二進(jìn)制流是不是一個(gè) roaring 位圖，并且存儲(chǔ)一些少量信息。
cookie 這個(gè)詞有點(diǎn)意思，本意是餅干。我的理解是指小物件，所以 http 中的 cookie 只是用來(lái)存儲(chǔ)少量信息。這里的 Cookie Header 也是如此。
接下來(lái)是 Descriptive Header。見(jiàn)名知義，它用來(lái)描述容器的信息。后面會(huì)詳細(xì)介紹容器。
接下來(lái)有一個(gè)可選的 Offset Header。它記錄了每個(gè)容器相對(duì)于首位的偏移，這讓我們可以隨機(jī)訪問(wèn)任意容器。
最后一部分是存儲(chǔ)實(shí)際數(shù)據(jù)的容器。roaring 中一共有 3 種類(lèi)型的容器：
array（數(shù)組型）：16bit 整數(shù)數(shù)組 bitset（位集型）：使用上一篇文章介紹的 bitset 存儲(chǔ)數(shù)據(jù) run：這個(gè)有點(diǎn)不好翻譯。有些人可能聽(tīng)說(shuō)過(guò) run-length 編碼，有翻譯成游程編碼的。即使用長(zhǎng)度+數(shù)據(jù)來(lái)編碼，比如"0000000000"可以編碼成"10,0"，表示有 10 個(gè) 0。run 容器也是類(lèi)似的，后文詳述
設(shè)計(jì)這種的布局，是為了不用將存儲(chǔ)的位圖全部載入內(nèi)存就可以隨機(jī)讀取它的數(shù)據(jù)。并且每個(gè)容器的范圍相互獨(dú)立，這使得并行計(jì)算變得容易。
Cookie Header
Cookier Header 有兩種類(lèi)型，分別占用 32bit 和 64bit 的空間。
第一種類(lèi)型，前 32bit 的值為 12346，此時(shí)緊接著的 32bit 表示容器數(shù)量（記為 n）。同時(shí)這意味著，后面沒(méi)有 run 類(lèi)型的容器。12346 這魔術(shù)數(shù)字被定義為常量SERIAL_COOKIE_NO_RUNCONTAINER，含義不言自明。
第二種類(lèi)型，前 32bit 的最低有效 16 位的值為 12347。此時(shí)，最高有效 16 位存儲(chǔ)的值等于容器數(shù)量-1。將 cookie 右移 16 位再加 1 即可得到容器數(shù)量。由于這種類(lèi)型的容器數(shù)量不會(huì)為 0，采用這種編碼我們能記錄的容器數(shù)量會(huì)多上 1 個(gè)。這種方法在很多地方都有應(yīng)用，例如 redis。后面緊接著會(huì)使用 (n+7)/8 字節(jié)（作為一個(gè) bitset）表示后面的容器是否 run 容器。每位對(duì)應(yīng)一個(gè)容器，1 表示對(duì)應(yīng)的容器是 run 容器，0 表示不是 run 容器。
由于是小端存儲(chǔ)，所以流的前 16bit 一定是 12346 或 12347。如果讀取到了其它的值，說(shuō)明文件損壞，直接退出程序即可。
Descriptive Header
Cookie Header 之后就是 Descriptive Header。它使用一對(duì) 16bit 數(shù)據(jù)描述每個(gè)容器。一個(gè) 16bit 存儲(chǔ)鍵（即整數(shù)的最高有效 16bit），另一個(gè) 16bit 存儲(chǔ)對(duì)應(yīng)容器的基數(shù)（Cardinality）-1（又見(jiàn)到了），即容器存儲(chǔ)的整數(shù)數(shù)量）。如果有 n 個(gè)容器，則 Descriptive Header 需要 32n 位 或 4n 字節(jié)。
掃描 Descriptive Header 之后，我們就能知道每個(gè)容器的類(lèi)型。如果 cookie 值為 12347，cookie 后有一個(gè) bitset 表示每個(gè)容器是否是 run 類(lèi)型。對(duì)于非 run 類(lèi)型的容器，如果容器的基數(shù)（Cardinality）小于等于 4096，它是一個(gè) array 容器。反之，這是一個(gè) bitset 容器
Offset Header
滿足以下任一條件，Offset Header 就會(huì)存在：
cookie 的值為 SERIAL_COOKIE_NO_RUNCONTAINER（即 12346） cookie 的值為 SERIAL_COOKIE（即 12347），并且至少有 4 個(gè)容器。也有一個(gè)常量 NO_OFFSET_THRESHOLD = 4
Offset Header 為每個(gè)容器使用 32bit 值存儲(chǔ)對(duì)應(yīng)容器距離流開(kāi)始處的偏移，單位字節(jié)。
Container
接下來(lái)就是實(shí)際存儲(chǔ)數(shù)據(jù)的容器了。前面簡(jiǎn)單提到過(guò)，容器有三種類(lèi)型。
array
存儲(chǔ)有序的 16bit 無(wú)符號(hào)整數(shù)值，有序便于使用二分查找提高效率。16bit 值只是數(shù)據(jù)的最低有效 16bit，還記得 Descriptive Header 中每個(gè)容器都有一個(gè) 16bit 的 key 吧。將它們拼接起來(lái)才是實(shí)際的數(shù)據(jù)。
如果容器有 x 個(gè)值，占用空間 2x 字節(jié)。
bitmap/bitset
bitset 容器固定使用 8KB 的空間，以 64bit 為單位（稱(chēng)為字，word）序列化。因此，如果值 j 存在，則第 j/64 個(gè)字（從 0 開(kāi)始）的 j%64 位會(huì)被設(shè)置為 1（從 0 開(kāi)始）。
run
以一個(gè)表示 run 數(shù)量的 16bit 整數(shù)開(kāi)始。后續(xù)每個(gè) run 用一對(duì) 16bit 整數(shù)表示，前一個(gè) 16bit 表示開(kāi)始的值，后一個(gè) 16bit 表示長(zhǎng)度-1（又雙見(jiàn)到了）。例如，11,4 表示數(shù)據(jù) 11,12,13,14,15。
手?jǐn)]解析代碼
驗(yàn)證我們是否真的理解了 roaring 布局最有效的方法就是手?jǐn)]一個(gè)解析。使用標(biāo)準(zhǔn)庫(kù)encoding/binary可以很容易地處理大小端問(wèn)題。
定義常量:
const (
SERIAL_COOKIE_NO_RUNCONTAINER = 12346
SERIAL_COOKIE = 12347
NO_OFFSET_THRESHOLD = 4
)
讀取 Cookie Header:
func readCookieHeader(r io.Reader) (cookie uint16, containerNum uint32, runFlagBitset []byte) {
binary.Read(r, binary.LittleEndian, &cookie)
switch cookie {
case SERIAL_COOKIE_NO_RUNCONTAINER:
var dummy uint16
binary.Read(r, binary.LittleEndian, &dummy)
binary.Read(r, binary.LittleEndian, &containerNum)
case SERIAL_COOKIE:
var u16 uint16
binary.Read(r, binary.LittleEndian, &u16)
containerNum = uint32(u16)
buf := make([]uint8, (containerNum+7)/8)
r.Read(buf)
runFlagBitset = buf[:]
default:
log.Fatal("unknown cookie")
}
fmt.Println(cookie, containerNum, runFlagBitset)
return
}
讀取 Descriptive Header:
func readDescriptiveHeader(r io.Reader, containerNum uint32) []KeyCard {
var keycards []KeyCard
var key uint16
var card uint16
for i := 0; i < int(containerNum); i++ {
binary.Read(r, binary.LittleEndian, &key)
binary.Read(r, binary.LittleEndian, &card)
card += 1
fmt.Println("container", i, "key", key, "card", card)
keycards = append(keycards, KeyCard{key, card})
}
return keycards
}
讀取 Offset Header:
func readOffsetHeader(r io.Reader, cookie uint16, containerNum uint32) {
if cookie == SERIAL_COOKIE_NO_RUNCONTAINER ||
(cookie == SERIAL_COOKIE && containerNum >= NO_OFFSET_THRESHOLD) {
// have offset header
var offset uint32
for i := 0; i < int(containerNum); i++ {
binary.Read(r, binary.LittleEndian, &offset)
fmt.Println("offset", i, offset)
}
}
}
讀取容器，根據(jù)類(lèi)型調(diào)用不同的函數(shù):
// array
func readArrayContainer(r io.Reader, key, card uint16, bm *roaring.Bitmap) {
var value uint16
for i := 0; i < int(card); i++ {
binary.Read(r, binary.LittleEndian, &value)
bm.Add(uint32(key)<<16 | uint32(value))
}
}
// bitmap
func readBitmapContainer(r io.Reader, key, card uint16, bm *roaring.Bitmap) {
var u64s [1024]uint64
for i := 0; i < 1024; i++ {
binary.Read(r, binary.LittleEndian, &u64s[i])
}
bs := bitset.From(u64s[:])
for i := uint32(0); i < 8192; i++ {
if bs.Test(uint(i)) {
bm.Add(uint32(key)<<16 | i)
}
}
}
// run
func readRunContainer(r io.Reader, key uint16, bm *roaring.Bitmap) {
var runNum uint16
binary.Read(r, binary.LittleEndian, &runNum)
var startNum uint16
var length uint16
for i := 0; i < int(runNum); i++ {
binary.Read(r, binary.LittleEndian, &startNum)
binary.Read(r, binary.LittleEndian, &length)
length += 1
for j := uint16(0); j < length; j++ {
bm.Add(uint32(key)<<16 | uint32(startNum+j))
}
}
}
整合:
func main() {
data, err := ioutil.ReadFile("../roaring.bin")
if err != nil {
log.Fatal(err)
}
r := bytes.NewReader(data)
cookie, containerNum, runFlagBitset := readCookieHeader(r)
keycards := readDescriptiveHeader(r, containerNum)
readOffsetHeader(r, cookie, containerNum)
bm := roaring.New()
for i := uint32(0); i < uint32(containerNum); i++ {
if runFlagBitset != nil && runFlagBitset[i/8]&(1<<(i%8)) != 0 {
// run
readRunContainer(r, keycards[i].key, bm)
} else if keycards[i].card <= 4096 {
// array
readArrayContainer(r, keycards[i].key, keycards[i].card, bm)
} else {
// bitmap
readBitmapContainer(r, keycards[i].key, keycards[i].card, bm)
}
}
fmt.Println(bm.String())
}
我將寫(xiě)入讀取那個(gè)示例中的 byte.Buffer 保存到文件roaring.bin中。上面的程序就可以解析這個(gè)文件:
12346 1 []
container 0 key 0 card 8
offset 0 16
{1,3,5,7,100,300,500,700}
成功還原了位圖??
總結(jié)
本文我們首先介紹了 roaring 壓縮位圖的使用。如果不考慮內(nèi)部實(shí)現(xiàn)，壓縮位圖和普通的位圖在使用上并沒(méi)有多少區(qū)別。
然后我通過(guò) 8 張?jiān)韴D詳細(xì)分析了存儲(chǔ)的格式。
最后通過(guò)手?jǐn)]一個(gè)解析來(lái)加深對(duì)原理的理解。
大家如果發(fā)現(xiàn)好玩、好用的 Go 語(yǔ)言庫(kù)，歡迎到 Go 每日一庫(kù) GitHub 上提交 issue??
參考
roaring GitHub：github.com/RoaringBitmap/roaring roaring 文件格式：https://github.com/RoaringBitmap/RoaringFormatSpec Go 每日一庫(kù) GitHub：https://github.com/darjun/go-daily-lib
推薦閱讀