Go 每日一庫之 roaring
簡介
集合是軟件中的基本抽象。實現集合的方法有很多,例如 hash set、tree 等。要實現一個整數集合,位圖(bitmap,也稱爲 bitset 位集合,bitvector 位向量)是個不錯的方法。使用 n 個位(bit),我們可以表示整數範圍[0, n)
。如果整數 i 在集合中,第 i 位設置爲 1。這樣集合的交集(intersection)、並集(unions)和差集(difference)可以利用整數的按位與、按位或和按位與非來實現。而計算機執行位運算是非常迅速的。
bitset 在某些場景中會消耗大量的內存。例如,設置第 1,000,000 位,需要佔用超過 100kb 的內存。爲此 bitset 庫的作者又開發了壓縮位圖庫:roaring
。
本文首先介紹了 roaring 的使用。最後分析 roaring 的文件存儲格式。
安裝
本文代碼使用 Go Modules。
創建目錄並初始化:
$ mkdir -p roaring && cd roaring
$ go mod init github.com/darjun/go-daily-lib/roaring
安裝roaring
庫:
$ 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) // 執行並集
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) // 執行交集
fmt.Println(bm2.String()) // {1}
fmt.Println(bm2.GetCardinality()) // 1
fmt.Println(bm2.Contains(1)) // true
}
上面演示了兩種創建 roaring bitmap 的方式:
-
roaring.BitmapOf()
:傳入集合元素,創建位圖並添加這些元素 -
roaring.New()
:創建一個空位圖
首先,我們創建了一個位圖 bm1:{1,2,3,4,5,100,1000}。輸出它的字符串表示,集合大小,檢查 3 是否在集合中。
然後又創建了一個位圖 bm2:{1,100,500}。輸出檢查三連。
接着創建了一個空位圖 bm3,依次添加元素 1,11,111。輸出檢查三連。
然後我們對 bm1 和 bm2 執行並集,結果直接存放在 bm1 中。由於集合中的元素各不相同,此時 bm1 中的元素爲 {1,2,3,4,5,100,500,1000},大小爲 8。
再然後我們對 bm2 和 bm3 執行交集,結果直接存放在 bm2 中。此時 bm2 中的元素爲 {1},大小爲 1。
可以看出 roaring 提供的基本操作與 bitset 大體相同。只是命名完全不一樣,在使用時需要特別注意。
-
bm.String()
:返回 bitmap 的字符串表示 -
bm.Add(n)
:添加元素 n -
bm.GetCardinality()
:返回集合的基數(Cardinality),即元素個數 -
bm1.And(bm2)
:執行集合交集,會修改 bm1 -
bm1.Or(bm2)
:執行集合並集,會修改 bm1
迭代
roaring 位圖支持迭代。
func main() {
bm := roaring.BitmapOf(1, 2, 3, 4, 5, 100, 1000)
i := bm.Iterator()
for i.HasNext() {
fmt.Println(i.Next())
}
}
與很多編程語言支持的迭代器一樣,先調用對象的Iterator()
返回一個迭代器,然後循環調用HasNext()
檢查是否有下一個元素,調用i.Next()
返回下一個元素。
上面代碼依次輸出 1,2,3,4,5,100,1000。
並行操作
roaring 支持位圖集合運算的並行執行。可以指定使用多少個 goroutine 對集合執行交集、並集等。同時可以傳入可變數量的位圖集合:
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
}
並行操作使用相應接口的Par*
版本,第一個參數指定 worker 數量,接着傳入任意多個 bitmap。
寫入與讀取
roaring 可以將壓縮的位圖寫入到文件中,並且格式與其他語言的實現保持兼容。也就是說,我們可以用 Go 將 roaring 位圖寫入文件,然後通過網絡發送給另一臺機器,在這臺機器上使用 C++ 或 Java 的實現讀取這個文件。
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)
:寫入一個 io.Writer,可以是內存(byte.Buffer),可以是文件(os.File),甚至可以是網絡(net.Conn) -
ReadFrom(r io.Reader)
:從一個 io.Reader 中讀取,來源同樣可以是內存、文件或網絡等
注意WriteTo
的返回值爲size
和err
,使用時需要處理錯誤情況。ReadFrom
也是返回size
和err
,同樣需要處理處理。
64 位版本
默認情況下,roaring 位圖只能用來存儲 32 位整數。所以 roaring 位圖最多能包含 4294967296(2^32
) 個整數。
roaring 也提供了存儲 64 位整數的擴展,即github.com/RoaringBitmap/roaring/roaring64
。提供的接口基本相同。然而,64 位版本不保證與 Java/C++ 等格式兼容。
存儲格式
roaring 可以寫入文件中,也可以從文件中讀取。並且提供多種語言兼容的格式。下面我們一起來看看存儲的格式。
roaring 位圖默認只能存儲 32 位的整數。在序列化時,將這些整數分容器(container)存儲。每個容器有一個 16 位表示的基數(Cardinality,即元素個數,範圍[1,2^16]
)和一個鍵(key)。鍵取元素的最高有效 16 位(most significant),所以鍵的範圍爲[0, 65536)
。這樣如果兩個整數的最高 16 位有效位相同,那麼它們將被保存在同一個容器中。這樣做還有一個好處:可以減少佔用的空間。
所有整數均採用小端存儲。
概覽
roaring 採用的存儲格式佈局如下:
從上到下依次介紹。
開始部分是一個 Cookie Header。它用來識別一個二進制流是不是一個 roaring 位圖,並且存儲一些少量信息。
cookie 這個詞有點意思,本意是餅乾。我的理解是指小物件,所以 http 中的 cookie 只是用來存儲少量信息。這裏的 Cookie Header 也是如此。
接下來是 Descriptive Header。見名知義,它用來描述容器的信息。後面會詳細介紹容器。
接下來有一個可選的 Offset Header。它記錄了每個容器相對於首位的偏移,這讓我們可以隨機訪問任意容器。
最後一部分是存儲實際數據的容器。roaring 中一共有 3 種類型的容器:
-
array(數組型):16bit 整數數組
-
bitset(位集型):使用上一篇文章介紹的 bitset 存儲數據
-
run:這個有點不好翻譯。有些人可能聽說過 run-length 編碼,有翻譯成遊程編碼的。即使用長度 + 數據來編碼,比如 "0000000000" 可以編碼成 "10,0",表示有 10 個 0。run 容器也是類似的,後文詳述
設計這種的佈局,是爲了不用將存儲的位圖全部載入內存就可以隨機讀取它的數據。並且每個容器的範圍相互獨立,這使得並行計算變得容易。
Cookie Header
Cookier Header 有兩種類型,分別佔用 32bit 和 64bit 的空間。
第一種類型,前 32bit 的值爲 12346,此時緊接着的 32bit 表示容器數量(記爲 n)。同時這意味着,後面沒有 run 類型的容器。12346 這魔術數字被定義爲常量SERIAL_COOKIE_NO_RUNCONTAINER
,含義不言自明。
第二種類型,前 32bit 的最低有效 16 位的值爲 12347。此時,最高有效 16 位存儲的值等於容器數量 - 1。將 cookie 右移 16 位再加 1 即可得到容器數量。由於這種類型的容器數量不會爲 0,採用這種編碼我們能記錄的容器數量會多上 1 個。這種方法在很多地方都有應用,例如 redis。後面緊接着會使用 (n+7)/8
字節(作爲一個 bitset)表示後面的容器是否 run 容器。每位對應一個容器,1 表示對應的容器是 run 容器,0 表示不是 run 容器。
由於是小端存儲,所以流的前 16bit 一定是 12346 或 12347。如果讀取到了其它的值,說明文件損壞,直接退出程序即可。
Descriptive Header
Cookie Header 之後就是 Descriptive Header。它使用一對 16bit 數據描述每個容器。一個 16bit 存儲鍵(即整數的最高有效 16bit),另一個 16bit 存儲對應容器的基數(Cardinality)-1(又見到了),即容器存儲的整數數量)。如果有 n 個容器,則 Descriptive Header 需要 32n 位 或 4n 字節。
掃描 Descriptive Header 之後,我們就能知道每個容器的類型。如果 cookie 值爲 12347,cookie 後有一個 bitset 表示每個容器是否是 run 類型。對於非 run 類型的容器,如果容器的基數(Cardinality)小於等於 4096,它是一個 array 容器。反之,這是一個 bitset 容器
Offset Header
滿足以下任一條件,Offset Header 就會存在:
-
cookie 的值爲 SERIAL_COOKIE_NO_RUNCONTAINER(即 12346)
-
cookie 的值爲 SERIAL_COOKIE(即 12347),並且至少有 4 個容器。也有一個常量
NO_OFFSET_THRESHOLD = 4
Offset Header 爲每個容器使用 32bit 值存儲對應容器距離流開始處的偏移,單位字節。
Container
接下來就是實際存儲數據的容器了。前面簡單提到過,容器有三種類型。
array
存儲有序的 16bit 無符號整數值,有序便於使用二分查找提高效率。16bit 值只是數據的最低有效 16bit,還記得 Descriptive Header 中每個容器都有一個 16bit 的 key 吧。將它們拼接起來纔是實際的數據。
如果容器有 x 個值,佔用空間 2x 字節。
bitmap/bitset
bitset 容器固定使用 8KB 的空間,以 64bit 爲單位(稱爲字,word)序列化。因此,如果值 j 存在,則第 j/64 個字(從 0 開始)的 j%64 位會被設置爲 1(從 0 開始)。
run
以一個表示 run 數量的 16bit 整數開始。後續每個 run 用一對 16bit 整數表示,前一個 16bit 表示開始的值,後一個 16bit 表示長度 - 1(又雙見到了)。例如,11,4 表示數據 11,12,13,14,15。
手擼解析代碼
驗證我們是否真的理解了 roaring 佈局最有效的方法就是手擼一個解析。使用標準庫encoding/binary
可以很容易地處理大小端問題。
定義常量:
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)
}
}
}
讀取容器,根據類型調用不同的函數:
// 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())
}
我將寫入讀取那個示例中的 byte.Buffer 保存到文件roaring.bin
中。上面的程序就可以解析這個文件:
12346 1 []
container 0 key 0 card 8
offset 0 16
{1,3,5,7,100,300,500,700}
成功還原了位圖😀
總結
本文我們首先介紹了 roaring 壓縮位圖的使用。如果不考慮內部實現,壓縮位圖和普通的位圖在使用上並沒有多少區別。
然後我通過 8 張原理圖詳細分析了存儲的格式。
最後通過手擼一個解析來加深對原理的理解。
大家如果發現好玩、好用的 Go 語言庫,歡迎到 Go 每日一庫 GitHub 上提交 issue😄
參考
-
roaring GitHub:github.com/RoaringBitmap/roaring
-
roaring 文件格式:https://github.com/RoaringBitmap/RoaringFormatSpec
-
Go 每日一庫 GitHub:https://github.com/darjun/go-daily-lib
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/zu0HyJybjwb19nNMDeFcEw