乐趣区

关于godailylib:Go-每日一库之-roaring

jiezi

简介

汇合是软件中的根本形象。实现汇合的办法有很多，例如 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 := &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😄

参考

  1. roaring GitHub：github.com/RoaringBitmap/roaring
  2. roaring 文件格式：https://github.com/RoaringBitmap/RoaringFormatSpec
  3. Go 每日一库 GitHub：https://github.com/darjun/go-daily-lib

我

我的博客：https://darjun.github.io

欢送关注我的微信公众号【GoUpUp】，独特学习，一起提高~

退出移动版