Go壓縮位圖庫roaring安裝使用詳解

更新時(shí)間：2022年07月22日 09:28:12 作者：darjun

這篇文章主要為大家介紹了Go壓縮位圖庫roaring安裝使用詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

簡(jiǎn)介

集合是軟件中的基本抽象。實(shí)現(xiàn)集合的方法有很多，例如 hash set、tree等。要實(shí)現(xiàn)一個(gè)整數(shù)集合，位圖（bitmap，也稱為 bitset 位集合，bitvector 位向量）是個(gè)不錯(cuò)的方法。使用 n 個(gè)位（bit），我們可以表示整數(shù)范圍[0, n)。如果整數(shù) i 在集合中，第 i 位設(shè)置為 1。這樣集合的交集（intersection）、并集（unions）和差集（difference）可以利用整數(shù)的按位與、按位或和按位與非來實(shí)現(xiàn)。而計(jì)算機(jī)執(zhí)行位運(yùn)算是非常迅速的。

上一篇文章我介紹了bitset這個(gè)庫。

bitset 在某些場(chǎng)景中會(huì)消耗大量的內(nèi)存。例如，設(shè)置第 1,000,000 位，需要占用超過 100kb 的內(nèi)存。為此 bitset 庫的作者又開發(fā)了壓縮位圖庫：roaring。

本文首先介紹了 roaring 的使用。最后分析 roaring 的文件存儲(chǔ)格式。

安裝

本文代碼使用 Go Modules。

創(chuàng)建目錄并初始化：

$ 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)                       // 執(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)：添加元素 n
bm.GetCardinality()：返回集合的基數(shù)（Cardinality），即元素個(gè)數(shù)
bm1.And(bm2)：執(zhí)行集合交集，會(huì)修改 bm1
bm1.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())
  }
}

與很多編程語言支持的迭代器一樣，先調(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。

寫入與讀取

roaring 可以將壓縮的位圖寫入到文件中，并且格式與其他語言的實(shí)現(xiàn)保持兼容。也就是說，我們可以用 Go 將 roaring 位圖寫入文件，然后通過網(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 := &amp;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)：寫入一個(gè) io.Writer，可以是內(nèi)存（byte.Buffer），可以是文件（os.File），甚至可以是網(wǎng)絡(luò)（net.Conn)
ReadFrom(r io.Reader)：從一個(gè) io.Reader 中讀取，來源同樣可以是內(nèi)存、文件或網(wǎng)絡(luò)等

注意WriteTo的返回值為size和err，使用時(shí)需要處理錯(cuò)誤情況。ReadFrom也是返回size和err，同樣需要處理處理。

64 位版本

默認(rèn)情況下，roaring 位圖只能用來存儲(chǔ) 32 位整數(shù)。所以 roaring 位圖最多能包含 4294967296（2^32）個(gè)整數(shù)。

roaring 也提供了存儲(chǔ) 64 位整數(shù)的擴(kuò)展，即github.com/RoaringBitmap/roaring/roaring64。提供的接口基本相同。然而，64 位版本不保證與 Java/C++ 等格式兼容。

存儲(chǔ)格式

roaring 可以寫入文件中，也可以從文件中讀取。并且提供多種語言兼容的格式。下面我們一起來看看存儲(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ǔ)格式布局如下：

從上到下依次介紹。

開始部分是一個(gè) Cookie Header。它用來識(shí)別一個(gè)二進(jìn)制流是不是一個(gè) roaring 位圖，并且存儲(chǔ)一些少量信息。

cookie 這個(gè)詞有點(diǎn)意思，本意是餅干。我的理解是指小物件，所以 http 中的 cookie 只是用來存儲(chǔ)少量信息。這里的 Cookie Header 也是如此。

接下來是 Descriptive Header。見名知義，它用來描述容器的信息。后面會(huì)詳細(xì)介紹容器。

接下來有一個(gè)可選的 Offset Header。它記錄了每個(gè)容器相對(duì)于首位的偏移，這讓我們可以隨機(jī)訪問任意容器。

最后一部分是存儲(chǔ)實(shí)際數(shù)據(jù)的容器。roaring 中一共有 3 種類型的容器：

array（數(shù)組型）：16bit 整數(shù)數(shù)組
bitset（位集型）：使用上一篇文章介紹的 bitset 存儲(chǔ)數(shù)據(jù)
run：這個(gè)有點(diǎn)不好翻譯。有些人可能聽說過 run-length 編碼，有翻譯成游程編碼的。即使用長(zhǎng)度+數(shù)據(jù)來編碼，比如"0000000000"可以編碼成"10,0"，表示有 10 個(gè) 0。run 容器也是類似的，后文詳述

設(shè)計(jì)這種的布局，是為了不用將存儲(chǔ)的位圖全部載入內(nèi)存就可以隨機(jī)讀取它的數(shù)據(jù)。并且每個(gè)容器的范圍相互獨(dú)立，這使得并行計(jì)算變得容易。

Cookie Header

Cookier Header 有兩種類型，分別占用 32bit 和 64bit 的空間。

第一種類型，前 32bit 的值為 12346，此時(shí)緊接著的 32bit 表示容器數(shù)量（記為 n）。同時(shí)這意味著，后面沒有 run 類型的容器。12346 這魔術(shù)數(shù)字被定義為常量SERIAL_COOKIE_NO_RUNCONTAINER，含義不言自明。

第二種類型，前 32bit 的最低有效 16 位的值為 12347。此時(shí)，最高有效 16 位存儲(chǔ)的值等于容器數(shù)量-1。將 cookie 右移 16 位再加 1 即可得到容器數(shù)量。由于這種類型的容器數(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。如果讀取到了其它的值，說明文件損壞，直接退出程序即可。

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（又見到了），即容器存儲(chǔ)的整數(shù)數(shù)量）。如果有 n 個(gè)容器，則 Descriptive Header 需要 32n 位或 4n 字節(jié)。

掃描 Descriptive Header 之后，我們就能知道每個(gè)容器的類型。如果 cookie 值為 12347，cookie 后有一個(gè) bitset 表示每個(gè)容器是否是 run 類型。對(duì)于非 run 類型的容器，如果容器的基數(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)容器距離流開始處的偏移，單位字節(jié)。

Container

接下來就是實(shí)際存儲(chǔ)數(shù)據(jù)的容器了。前面簡(jiǎn)單提到過，容器有三種類型。

array

存儲(chǔ)有序的 16bit 無符號(hào)整數(shù)值，有序便于使用二分查找提高效率。16bit 值只是數(shù)據(jù)的最低有效 16bit，還記得 Descriptive Header 中每個(gè)容器都有一個(gè) 16bit 的 key 吧。將它們拼接起來才是實(shí)際的數(shù)據(jù)。

如果容器有 x 個(gè)值，占用空間 2x 字節(jié)。

bitmap/bitset

bitset 容器固定使用 8KB 的空間，以 64bit 為單位（稱為字，word）序列化。因此，如果值 j 存在，則第 j/64 個(gè)字（從 0 開始）的 j%64 位會(huì)被設(shè)置為 1（從 0 開始）。

run

以一個(gè)表示 run 數(shù)量的 16bit 整數(shù)開始。后續(xù)每個(gè) run 用一對(duì) 16bit 整數(shù)表示，前一個(gè) 16bit 表示開始的值，后一個(gè) 16bit 表示長(zhǎng)度-1（又雙見到了）。例如，11,4 表示數(shù)據(jù) 11,12,13,14,15。

手?jǐn)]解析代碼

驗(yàn)證我們是否真的理解了 roaring 布局最有效的方法就是手?jǐn)]一個(gè)解析。使用標(biāo)準(zhǔn)庫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, &amp;cookie)
  switch cookie {
  case SERIAL_COOKIE_NO_RUNCONTAINER:
    var dummy uint16
    binary.Read(r, binary.LittleEndian, &amp;dummy)
    binary.Read(r, binary.LittleEndian, &amp;containerNum)
  case SERIAL_COOKIE:
    var u16 uint16
    binary.Read(r, binary.LittleEndian, &amp;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 &lt; int(containerNum); i++ {
    binary.Read(r, binary.LittleEndian, &amp;key)
    binary.Read(r, binary.LittleEndian, &amp;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 &amp;&amp; containerNum &gt;= NO_OFFSET_THRESHOLD) {
    // have offset header
    var offset uint32
    for i := 0; i &lt; int(containerNum); i++ {
      binary.Read(r, binary.LittleEndian, &amp;offset)
      fmt.Println("offset", i, offset)
    }
  }
}

讀取容器，根據(jù)類型調(diào)用不同的函數(shù):

// array
func readArrayContainer(r io.Reader, key, card uint16, bm *roaring.Bitmap) {
  var value uint16
  for i := 0; i &lt; int(card); i++ {
    binary.Read(r, binary.LittleEndian, &amp;value)
    bm.Add(uint32(key)&lt;&lt;16 | uint32(value))
  }
}
// bitmap
func readBitmapContainer(r io.Reader, key, card uint16, bm *roaring.Bitmap) {
  var u64s [1024]uint64
  for i := 0; i &lt; 1024; i++ {
    binary.Read(r, binary.LittleEndian, &amp;u64s[i])
  }
  bs := bitset.From(u64s[:])
  for i := uint32(0); i &lt; 8192; i++ {
    if bs.Test(uint(i)) {
      bm.Add(uint32(key)&lt;&lt;16 | i)
    }
  }
}
// run
func readRunContainer(r io.Reader, key uint16, bm *roaring.Bitmap) {
  var runNum uint16
  binary.Read(r, binary.LittleEndian, &amp;runNum)
  var startNum uint16
  var length uint16
  for i := 0; i &lt; int(runNum); i++ {
    binary.Read(r, binary.LittleEndian, &amp;startNum)
    binary.Read(r, binary.LittleEndian, &amp;length)
    length += 1
    for j := uint16(0); j &lt; length; j++ {
      bm.Add(uint32(key)&lt;&lt;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 &lt; uint32(containerNum); i++ {
    if runFlagBitset != nil &amp;&amp; runFlagBitset[i/8]&amp;(1&lt;&lt;(i%8)) != 0 {
      // run
      readRunContainer(r, keycards[i].key, bm)
    } else if keycards[i].card &lt;= 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())
}

我將寫入讀取那個(gè)示例中的 byte.Buffer 保存到文件roaring.bin中。上面的程序就可以解析這個(gè)文件: