将Roaring Bitmap序列化为JSON

本文永久链接 – https://tonybai.com/2023/02/01/serialize-roaring-bitmap-to-json

近期在实现一个数据结构时使用到了位图索引(bitmap index)，本文就来粗浅聊聊位图(bitmap)。

一. 什么是bitmap

位图索引使用位数组(bit array，也有叫bitset的，通常被称为位图(bitmap)，以下均使用bitmap这个名称)实现。一个bitmap是一个从某个域（通常是一个整数范围）到集合{0，1}中的值的映射：

映射：f(x) -> {0, 1}， x是[0, n)的集合中的元素。

以n=8的集合{1, 2, 5}为例：

f(0) = 0
f(1) = 1
f(2) = 1
f(3) = 0
f(4) = 0
f(5) = 1
f(6) = 0
f(7) = 0

如果用bit来表示映射后得到的值，我们将得到一个二进制数0b00100110(最右侧的bit位上的值指示集合中数值0的存在性)，这样我们就可以用一个字节大小的数值0b00100110来表示{1, 2, 5}这个集合中各个位置的数值的存在性了。

我们看到相比于使用一个byte数组来表示{1, 2, 5}这个集合(即便是8个数值，也至少要8x8=64个字节)，bitmap无疑具有更高的空间利用率。同时，通过bitmap的与、或、异或等操作，我们可以很容易且高性能地得到集合的交、并、Top-K等集合操作的结果。

不过，传统的bitmap并不总能带来空间上的节省，比如我们要表示{1, 2, 10, 50000000}这样一个集合，那么使用传统bitmap将带来很大的空间开销。对于这样的具有稀疏元素特性的集合，传统位图实现就失去了其优势，而压缩位图(compressed bitmap)则成为了更佳的选择。

二. 压缩位图(compressed bitmap)

压缩位图既可以很好的支持稀疏集合，又保留了传统位图的空间和高性能的集合操作优势。最常见的压缩位图的方案是RLE(run-length encoding)，对这种方案的粗浅理解是对连续的0和1进行分别计数，比如下面这bitmap就可以压缩编码为n个0和m和1：

0b0000....00001111...111

RLE方案(以及其变体)具有很好的压缩比并且编解码也很高效。不过其不足是很难随机访问某个bit，每次访问特定的bit都要从头进行解压缩。如果你想将两个大的bitmap进行交集操作，你必须解压缩整个大bitmap。

一种名为roaring bitmap的压缩位图方案可以解决上述的问题。

三. roaring bitmap工作原理简介

roaring bitmap 的工作方式是这样的：它将32位整型所能表示的整型数[0, 4294967296)划分为2^16个chunk（例如，[0，2^16)，[2^16，2x2^16)，...）。当向roaring bitmap加入一个数或从roaring bitmap获取一个数的存在性时，roaring bitmap通过这个数的前16位决定该数在哪个trunk中。一旦确定trunk后，便可以通过与该trunk关联的container指针找到真正存储该数后16位值的container，在container中通过查找算法定位：

如上图所示：roaring bitmap的trunk关联的container类型不止有一种：

array container：这是一个有序的16bit整型数组，也是默认的container type，最多存储4096个数值。当超出这个数量时，会考虑用bitset container存储；
bitset container：就是一个非压缩的bitmap，有2^16个bit位；
run container：这是一个采用RLE压缩的、适合存储连续数值的container type，从上面图中也可以看出，这个container中存储的是一个个数对<s,l>，表示的数值范围为[s, s + l]。

roaring bitmap会根据trunk中的数的特征选择适当的container类型，并且这种选择是动态的，以尽量减少内存使用为目标。当我们向roaring bitmap添加或删除值时，对应trunk的container type都可能会改变。不过从整体视角看，无论使用哪种container，roaring bitmap都支持对某个bit的快速随机访问。同时roaring bitmap在实现层面也更容易利用现代cpu提供的高性能指令，并且是缓存友好的。

四. roaring bitmap的效果

roaring bitmap官方提供了多种主流语言的实现，其中Go语言的实现是roaring包。roaring包的使用十分简单，下面就是一个简单的示例：

package main

import (
    "fmt"

    "github.com/RoaringBitmap/roaring"
)

func main() {
    rb := roaring.NewBitmap()
    rb.Add(1)
    rb.Add(100000000)
    fmt.Println(rb.String())
    fmt.Println(rb.Contains(1))
    fmt.Println(rb.Contains(2))
    fmt.Println(rb.Contains(100000000))

    fmt.Println("cardinality:", rb.GetCardinality())
    fmt.Println("rb size=", rb.GetSizeInBytes())
}

运行示例得到如下结果：

{1,100000000}
true
false
true
cardinality: 2
rb size= 16

我们看到{1, 100000000}的稀疏集合映射到roaring bitmap仅占用了16个字节的空间(和非压缩bitmap对比)。

下面是一个由3000w以内的随机整数构成的集合到roaring bitmap的映射示例：

func main() {
    rb := roaring.NewBitmap()

    for i := 0; i < 30000000; i++ {
        rb.Add(uint32(rand.Int31n(30000000)))
    }

    fmt.Println("cardinality:", rb.GetCardinality())
    fmt.Println("rb size=", rb.GetSizeInBytes())
}

下面是其执行结果：

cardinality: 18961805
rb size= 3752860

我们看到集合中一共加入近1900w个数，roaring bitmap总共占用了3.6MB的内存空间，这个和非压缩bitmap没有拉开差距。

下面是一个连续的3000w数字的集合到roaring bitmap的映射示例：

func main() {
    rb := roaring.NewBitmap()

    for i := 0; i < 30000000; i++ {
        rb.Add(uint32(i))
    }

    fmt.Println("cardinality:", rb.GetCardinality())
    fmt.Println("rb size=", rb.GetSizeInBytes())
}

其执行结果如下：

cardinality: 30000000
rb size= 21912

显然针对这样的连续数字集合，roaring bitmap的空间效率体现的十分明显。

五. roaring bitmap的序列化

以上是对roaring bitmap的粗浅入门介绍，如果对roaring bitmap感兴趣，可以去其官方站点或开源项目主页做深入了解和学习。不过这里我要说的是roaring bitmap的序列化问题(序列化后便可以传输和持久化存储了)，以序列化为JSON和从JSON反序列化为例。

考虑到性能问题，json序列化我选择的是字节开源的sonic项目。sonic虽然说是一个Go开源项目，但由于其对JSON解析的极致优化的要求，目前该项目中Go代码的占比仅有30%不到，60%多都是汇编代码。sonic提供与Go标准库json包兼容的函数接口，并且sonic还支持streaming I/O模式，支持将特定类型对象序列化到io.Writer或从io.Reader中反序列化数据为一个特定类型对象，这个也是标准库json包所不支持的。当遇到超大JSON时，streaming I/O模式十分惯用，io.Writer和Reader可以让你的Go应用不至于瞬间分配大量内存，甚至被oom killed掉。

不过roaring bitmap并没有原生提供序列化(marshal)到JSON(或反向序列化)的函数/方法，那么我们如何将一个roaring bitmap序列化为一个JSON文本呢？Go标准库json包提供了Marshaler和Unmarshaler接口，凡是实现了这两个接口的自定义类型，json包都可以支持该自定义类型的序列化和反序列化。在这方面，sonic项目与Go标准库json包保持兼容。

不过roaring.Bitmap类型并没有实现Marshaler和Unmarshaler接口，roaring.Bitmap的序列化和反序列化需要我们自己来完成。

那么，我们首先想到的就是基于roaring.Bitmap自定义一个新类型，比如MyRB：

// https://github.com/bigwhite/experiments/blob/master/roaring-bitmap-examples/bitmap_json.go
type MyRB struct {
    RB *roaring.Bitmap
}

然后，我们给出MyRB的MarshalJSON和UnmarshalJSON方法的实现以满足Marshaler和Unmarshaler接口的要求：

// https://github.com/bigwhite/experiments/blob/master/roaring-bitmap-examples/bitmap_json.go
func (rb *MyRB) MarshalJSON() ([]byte, error) {
    s, err := rb.RB.ToBase64()
    if err != nil {
        return nil, err
    }

    r := fmt.Sprintf(`{"rb":"%s"}`, s)
    return []byte(r), nil
}

func (rb *MyRB) UnmarshalJSON(data []byte) error {
    // data => {"rb":"OjAAAAEAAAAAAB4AEAAAAAAAAQACAAMABAAFAAYABwAIAAkACgALAAwADQAOAA8AEAARABIAEwAUABUAFgAXABgAGQAaABsAHAAdAB4A"}

    _, err := rb.RB.FromBase64(string(data[7 : len(data)-2]))
    if err != nil {
        return err
    }

    return nil
}

我们利用roaring.Bitmap提供的ToBase64方法将roaring bitmap转换为一个base64字符串，然后再序列化为JSON；反序列化则是利用FromBase64对JSON数据进行解码。下面我们测试一下MyRB类型与JSON间的相互转换：

// https://github.com/bigwhite/experiments/blob/master/roaring-bitmap-examples/bitmap_json.go

func main() {
    var myrb = MyRB{
        RB: roaring.NewBitmap(),
    }

    for i := 0; i < 31; i++ {
        myrb.RB.Add(uint32(i))
    }
    fmt.Printf("the cardinality of origin bitmap = %d\n", myrb.RB.GetCardinality())

    buf, err := sonic.Marshal(&myrb)
    if err != nil {
        panic(err)
    }

    fmt.Printf("bitmap2json: %s\n", string(buf))

    var myrb1 = MyRB{
        RB: roaring.NewBitmap(),
    }
    err = sonic.Unmarshal(buf, &myrb1)
    if err != nil {
        panic(err)
    }

    fmt.Printf("after json2bitmap, the cardinality of new bitmap = %d\n", myrb1.RB.GetCardinality())
}

运行该示例：

the cardinality of origin bitmap = 31
bitmap2json: {"rb":"OjAAAAEAAAAAAB4AEAAAAAAAAQACAAMABAAFAAYABwAIAAkACgALAAwADQAOAA8AEAARABIAEwAUABUAFgAXABgAGQAaABsAHAAdAB4A"}
after json2bitmap, the cardinality of new bitmap = 31

输出结果符合预期。

基于支持序列化的MyRB，顺便我们再看一下sonic和标准库json的benchmark对比，我们编写一个简单的对比测试用例：

// https://github.com/bigwhite/experiments/blob/master/roaring-bitmap-examples/benchmark_test.go

type Foo struct {
    N    int    `json:"num"`
    Name string `json:"name"`
    Addr string `json:"addr"`
    Age  string `json:"age"`
    RB   MyRB   `json:"myrb"`
}

func BenchmarkSonicJsonEncode(b *testing.B) {
    var f = Foo{
        N: 5,
        RB: MyRB{
            RB: roaring.NewBitmap(),
        },
    }

    for i := 0; i < 3000; i++ {
        f.RB.RB.Add(uint32(i))
    }

    b.ReportAllocs()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _, err := sonic.Marshal(&f)
        if err != nil {
            panic(err)
        }
    }
}

func BenchmarkSonicJsonDecode(b *testing.B) {
    var f = Foo{
        N: 5,
        RB: MyRB{
            RB: roaring.NewBitmap(),
        },
    }

    for i := 0; i < 3000; i++ {
        f.RB.RB.Add(uint32(i))
    }

    buf, err := sonic.Marshal(&f)
    if err != nil {
        panic(err)
    }
    var f1 = Foo{
        RB: MyRB{
            RB: roaring.NewBitmap(),
        },
    }

    b.ReportAllocs()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        err = sonic.Unmarshal(buf, &f1)
        if err != nil {
            panic(err)
        }
    }
}

func BenchmarkStdJsonEncode(b *testing.B) {
    var f = Foo{
        N: 5,
        RB: MyRB{
            RB: roaring.NewBitmap(),
        },
    }

    for i := 0; i < 3000; i++ {
        f.RB.RB.Add(uint32(i))
    }

    b.ReportAllocs()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _, err := json.Marshal(&f)
        if err != nil {
            panic(err)
        }
    }
}

func BenchmarkStdJsonDecode(b *testing.B) {
    var f = Foo{
        N: 5,
        RB: MyRB{
            RB: roaring.NewBitmap(),
        },
    }

    for i := 0; i < 3000; i++ {
        f.RB.RB.Add(uint32(i))
    }

    buf, err := json.Marshal(&f)
    if err != nil {
        panic(err)
    }
    var f1 = Foo{
        RB: MyRB{
            RB: roaring.NewBitmap(),
        },
    }

    b.ReportAllocs()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        err = json.Unmarshal(buf, &f1)
        if err != nil {
            panic(err)
        }
    }
}

执行这个benchmark：

$go test -bench .
goos: darwin
goarch: amd64
pkg: demo
... ...
BenchmarkSonicJsonEncode-8         71176         16331 ns/op       49218 B/op         13 allocs/op
BenchmarkSonicJsonDecode-8         85080         13710 ns/op       37236 B/op         11 allocs/op
BenchmarkStdJsonEncode-8           24490         49345 ns/op       47409 B/op         10 allocs/op
BenchmarkStdJsonDecode-8           20083         59593 ns/op       29000 B/op         15 allocs/op
PASS
ok      demo    6.166s

从我们这个benchmark结果可以看到，sonic要比标准库json包快3-4倍。

本文中代码可以到这里下载。

六. 参考资料

Roaring Bitmap : June 2015 report - https://es.slideshare.net/lemire/roaringprezi-49478534
Roaring Bitmap官网 - https://roaringbitmap.org/
Roaring Bitmap Spec - https://github.com/RoaringBitmap/RoaringFormatSpec
Roaring Bitmap Go实现 - https://github.com/RoaringBitmap/roaring
字节跳动的sonic项目 - https://github.com/bytedance/sonic
paper: Consistently faster and smaller compressed bitmaps with Roaring - https://arxiv.org/pdf/1603.06549.pdf
基于Bitmap的精确去重和用户行为分析 - http://ai.baidu.com/forum/topic/show/987701
paper: Roaring Bitmaps: Implementation of an Optimized Software Library - https://arxiv.org/pdf/1709.07821.pdf

“Gopher部落”知识星球旨在打造一个精品Go学习和进阶社群！高品质首发Go技术文章，“三天”首发阅读权，每年两期Go语言发展现状分析，每天提前1小时阅读到新鲜的Gopher日报，网课、技术专栏、图书内容前瞻，六小时内必答保证等满足你关于Go语言生态的所有需求！2023年，Gopher部落将进一步聚焦于如何编写雅、地道、可读、可测试的Go代码，关注代码质量并深入理解Go核心技术，并继续加强与星友的互动。欢迎大家加入！

img{512x368}

著名云主机服务厂商DigitalOcean发布最新的主机计划，入门级Droplet配置升级为：1 core CPU、1G内存、25G高速SSD，价格5$/月。有使用DigitalOcean需求的朋友，可以打开这个链接地址：https://m.do.co/c/bff6eed92687 开启你的DO主机之路。

Gopher Daily(Gopher每日新闻)归档仓库 - https://github.com/bigwhite/gopherdaily

我的联系方式：

微博(暂不可用)：https://weibo.com/bigwhite20xx
微博2：https://weibo.com/u/6484441286
博客：tonybai.com
github: https://github.com/bigwhite

商务合作方式：撰稿、出书、培训、在线课程、合伙创业、咨询、广告合作。

将Roaring Bitmap序列化为JSON

一. 什么是bitmap

二. 压缩位图(compressed bitmap)

三. roaring bitmap工作原理简介

四. roaring bitmap的效果

五. roaring bitmap的序列化

六. 参考资料

添加新评论

欢迎使用邮件订阅我的博客

文章

评论

分类

归档

链接

开源项目

翻译项目

将Roaring Bitmap序列化为JSON

一. 什么是bitmap

二. 压缩位图(compressed bitmap)

三. roaring bitmap工作原理简介

四. roaring bitmap的效果

五. roaring bitmap的序列化

六. 参考资料

添加新评论

欢迎使用邮件订阅我的博客

文章

评论

分类

标签

归档

链接

开源项目

翻译项目