Go壓縮點陣相簿roaring安裝使用詳解

2022-07-22 14:02:04

簡介

集合是軟體中的基本抽象。實現集合的方法有很多，例如 hash set、tree等。要實現一個整數集合，點陣圖（bitmap，也稱為 bitset 位集合，bitvector 位向量）是個不錯的方法。使用 n 個位（bit），我們可以表示整數範圍[0, n)。如果整數 i 在集合中，第 i 位設定為 1。這樣集合的交集（intersection）、並集（unions）和差集（difference）可以利用整數的按位元與、按位元或和按位元與非來實現。而計算機執行位運算是非常迅速的。

上一篇文章我介紹了bitset這個庫。

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 := &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)：寫入一個 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, &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)
    }
  }
}

讀取容器，根據型別呼叫不同的函數:

// 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())
}

我將寫入讀取那個範例中的 byte.Buffer 儲存到檔案roaring.bin中。上面的程式就可以解析這個檔案: