Roaring Bitmap Basics

最近因为一个奇怪的性能问题看了一下 Roaring Bitmap 的代码，发现里面有一些逻辑和我预想的还不太一样。Roaring Bitmap 在数据系统里面是一个非常常被用到的东西。从 Apache Iceberg V3 / Delta Lake 到 ElasticSearch 都有 Roaring Bitmap 的身影，同时 ClickHosue 的 Bitmap 类型在实现上甚至就有 Roaring Bitmap。

Roaring 的抽象是一个 uint32 范围的 bitmap，在官方实现中，也有 Roaring64 ( 64 位的 Roaring Bitmap），但最近实现刚刚被用 adaptive radix trie 重构过，不知道是否稳定。在 Delta Lake 中，它也用32 bit 和自己一些编码的方式来实现 64位 roaring bitmap 的抽象。我们暂时只看 32 位的 Roaring Bitmap

RoaringBitmap 把内容切分成高16位和低16位，在内存中有下列的表示：

  1. RoaringBitmap: RoaringBitmap 是一个 array 的有序数组，array 的成员是 container，每个 container 包含自身的 flag ( 是否 cow），type ( 自己是什么类型的 container )，和 high 16bit key。这块的 Container 是有序的，所以 container 定位依赖一个 binary search。
  2. Array container: 少于 4096 （ 代码见 DEFAULT_MAX_SIZE 的）size 的容器，最，以有序的 uint16 存储，capacity 未定义的变长容器（等价于 vector）。在里面查询做二分搜索 + 线形查找（在 search 的时候如果 left range 在 16以内切换成线性查找）。
  3. Bitmap container: 大于等于 4096B，或者在执行位操作的时候临时使用的固定长度容器（lazy 操作实现的时候，会把别的容器转化为 bitmap container，然后用 bitmap 做快速操作）。这里会有一个摘要信息 cardinarity 表示元素数量（在 lazy 操作的情况下允许不存在）。这里实际存储大小是 2**16/8 = 2^13 = 8192 ，实际上

img

我先自己强行讲 Roaring Bitmap 的 api 分为下列类型（不考虑初始化）

  1. 简单的单个元素的查询存在性、插入、删除、某个值的 rank、按照 rank 来选择值
    1. 有一类 api 是 Bulk api，即插入/查找的时候，如果多次插入或者查找的信息是临近的话，那么几个查询或者大概率在同一个 container 内，Bulk api 会在上下文中记录
  2. 多个元素的范围查找、插入、删除、范围（或者全 bitmap）的 cardinality 估计
  3. 集合 api 和 bitmap api，包含：父子集关系判断、并集(bit or)、交集(bit and)、差集、bit or、andnot、取反（flip） 、shifting 等 api，这些支持生成一个新的 Roaring Bitmap，也支持 inplace 的操作（在 C++ binding 里为 & 和 &= 之类的区别，也比较好区分）。这里也支持多组操作，即同 api 处理多个集合
    1. 这里支持一类「Lazy」api，本质上是在一些耗时操作（比如大 array 和大 array 的 container 做 union 之类的位操作的时候），转 bitmap 之类的临时对象来操作，来高效处理。这种 api 在多 bitmap 的操作中更高效。
  4. 内存占用的估算，统计 roaring 信息的 api
  5. 序列化、反序列化到标准的（各个格式相同的 fmt）和非标准的（一些快速操作的格式）
  6. 转 bitmap （23 年新加的）和 uint32_t* 数组的 api
  7. Iterator api
  8. 尝试切换为 run container 的 api 和尝试取消所有 run container 的 api ( 其实 run container 默认你插入一般是不会启用的）

哈哈，好一篇罗列 api 的烂博客…

值得一提的是，Roaring 有个地方比较神秘，就是它在库上会有一些 namespace，检测你是 C 语言还是 C++ 语言，然后如果是 C++ 加上对应的 namespace…我觉得还是挺神秘的，见 https://github.com/RoaringBitmap/CRoaring/blob/master/src/bitset.c#L11 . 最终这里会由脚本 https://github.com/RoaringBitmap/CRoaring/blob/master/amalgamation.sh 生成一组 header only 的文件作为库.

本节咱不介绍 SIMD 相关的内容。

Basic Operations

首先介绍一下 add 相关的接口和 contains 相关的接口，来了解一下基础的内容

1
2
3
4
5
void roaring_bitmap_add_bulk(roaring_bitmap_t *r,
                             roaring_bulk_context_t *context, uint32_t val);
void roaring_bitmap_add_many(roaring_bitmap_t *r, size_t n_args,
                             const uint32_t *vals);
void roaring_bitmap_add(roaring_bitmap_t *r, uint32_t x);

Container 是 Roaring 里面最重要的元素之一，这里有几个 container type( 你可以看到我还截图了一个 PAIR_CONTAINER_TYPES, 这个单纯是我觉得代码有点意思，值得看看）。

代码最上层是 roaring_bitmap_t 和 roaring_array_t 一层，代码非常直接，贴了就能看懂，search 全是二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct roaring_array_s {
    // container 的数量
    int32_t size;
    // container 申请的数量
    int32_t allocation_size;
    ROARING_CONTAINER_T **containers;  // Use container_t in non-API files!
    // 每个容器的 key, 保留高 16b
    uint16_t *keys;
    // 每个对应的 typecode, 包含 shared 容器, 搜 `_CONTAINER_TYPE`
    uint8_t *typecodes;
    // cow and frozen flags
    // `ROARING_FLAG_` 常数
    uint8_t flags;
} roaring_array_t;

typedef struct roaring_bitmap_s {
    roaring_array_t high_low_container;
} roaring_bitmap_t;

这里面 containers, keys, typecodes 的内存都是指针，但它们的分配是连续的，类似下图，空框代表分配了但是没有使用的内存。

whiteboard_exported_image

在 roaring array 层插入的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
static inline void ra_unshare_container_at_index(roaring_array_t *ra,
                                                 uint16_t i) {
    assert(i < ra->size);
    ra->containers[i] =
        get_writable_copy_if_shared(ra->containers[i], &ra->typecodes[i]);
}

void roaring_bitmap_add(roaring_bitmap_t *r, uint32_t val) {
    roaring_array_t *ra = &r->high_low_container;

    // 拿到 high 16 bits
    const uint16_t hb = val >> 16;
    // 通过二分查找(和先尝试 peek 最右侧插入) 找到对应的 container
    const int i = ra_get_index(ra, hb);
    uint8_t typecode;
    if (i >= 0) {
        // 对 cow 容器拿到 write-only copy for write
        // 内存管理: 这套如果 cow 发生了，这里内部维护了一套引用计数来回收内部
        // 的 shared 内存.
        ra_unshare_container_at_index(ra, (uint16_t)i);
        // 拿到容器的指针和 typecode
        container_t *container =
            ra_get_container_at_index(ra, (uint16_t)i, &typecode);
        uint8_t newtypecode = typecode;
        container_t *container2 =
            container_add(container, val & 0xFFFF, typecode, &newtypecode);
        if (container2 != container) {
            // roaring 常见 pattern: 内部 add 的时候, 可能返回一个新容器,
            // 这个时候要把老得 free 掉
            container_free(container, typecode);
            ra_set_container_at_index(&r->high_low_container, i, container2,
                                      newtypecode);
        }
    } else {
        // 创建并且插入一个新 container, 然后新 container 默认是 arary container
        // 直接插入就行.
        array_container_t *newac = array_container_create();
        container_t *container =
            container_add(newac, val & 0xFFFF, ARRAY_CONTAINER_TYPE, &typecode);
        // we could just assume that it stays an array container
        // 插入 roaring array
        ra_insert_new_key_value_at(&r->high_low_container, -i - 1, hb,
                                   container, typecode);
    }
}

Bitset, array, run 我们都介绍过，这里可以关注 SHARED_CONTAINER_TYPE, 这里如果是 cow 而且复制的话，就会把 type 设置成 container type.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * The switch case statements follow
 * BITSET_CONTAINER_TYPE -- ARRAY_CONTAINER_TYPE -- RUN_CONTAINER_TYPE
 * so it makes more sense to number them 1, 2, 3 (in the vague hope that the
 * compiler might exploit this ordering).
 */

#define BITSET_CONTAINER_TYPE 1
#define ARRAY_CONTAINER_TYPE 2
#define RUN_CONTAINER_TYPE 3
#define SHARED_CONTAINER_TYPE 4

/**
 * Macros for pairing container type codes, suitable for switch statements.
 * Use PAIR_CONTAINER_TYPES() for the switch, CONTAINER_PAIR() for the cases:
 *
 *     switch (PAIR_CONTAINER_TYPES(type1, type2)) {
 *        case CONTAINER_PAIR(BITSET,ARRAY):
 *        ...
 *     }
 */
#define PAIR_CONTAINER_TYPES(type1, type2) (4 * (type1) + (type2))

#define CONTAINER_PAIR(name1, name2) \
    (4 * (name1##_CONTAINER_TYPE) + (name2##_CONTAINER_TYPE))

于是，我们下面就应该了解 container 的逻辑了

Containers

我们会发现，这里有个 SHARED_CONTAINER_TYPE。我们先再来介绍一下 Cow 这一套。container_t*相当于一个 void*或多态的对象。贴一下几种容器的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/* struct array_container - sparse representation of a bitmap
 *
 * @cardinality: number of indices in `array` (and the bitmap)
 * @capacity:    allocated size of `array`
 * @array:       sorted list of integers
 */
STRUCT_CONTAINER(array_container_s) {
    int32_t cardinality;
    int32_t capacity;
    uint16_t *array;
};

typedef struct array_container_s array_container_t;

STRUCT_CONTAINER(bitset_container_s) {
    // 注意设置成 BITSET_UNKNOWN_CARDINALITY 的时候
    // 这个 card 只是成员数量, 这个 words 内容大小是固定的.
    int32_t cardinality;
    uint64_t *words;
};

typedef struct bitset_container_s bitset_container_t;

/* struct rle16_s - run length pair
 *
 * @value:  start position of the run
 * @length: length of the run is `length + 1`
 *
 * An RLE pair {v, l} would represent the integers between the interval
 * [v, v+l+1], e.g. {3, 2} = [3, 4, 5].
 */
struct rle16_s {
    uint16_t value;
    uint16_t length;
};

typedef struct rle16_s rle16_t;

/* struct run_container_s - run container bitmap
 *
 * @n_runs:   number of rle_t pairs in `runs`.
 * @capacity: capacity in rle_t pairs `runs` can hold.
 * @runs:     pairs of rle_t.
 */
STRUCT_CONTAINER(run_container_s) {
    int32_t n_runs;
    int32_t capacity;
    rle16_t *runs;
}; 

/**
 * A shared container is a wrapper around a container
 * with reference counting.
 */
STRUCT_CONTAINER(shared_container_s) {
    container_t *container;
    uint8_t typecode;
    croaring_refcount_t counter;  // to be managed atomically
};

typedef struct shared_container_s shared_container_t;

Array 和 Bitmap 很基础，我们就先不介绍了。

我们之前没有聊 shared, shared container 这里内部是个 atomic shared counter 组成的 COW 容器。本质上也是靠 fencing 来 gc 的：

1
2
3
4
5
6
7
8
void shared_container_free(shared_container_t *container) {
    if (croaring_refcount_dec(&container->counter)) {
        assert(container->typecode != SHARED_CONTAINER_TYPE);
        container_free(container->container, container->typecode);
        container->container = NULL;  // paranoid
        roaring_free(container);
    }
}

为什么需要 cow 呢？在 or 之类的操作的时候，如果两个 roaring 长度对不齐，哪很多地方就会被 lazy 的共享出来。

正常插入的时候是不会有 run container 的，runOptimize 可能会产生这样的东西，这套逻辑大概是：

  1. 比较本 container 的 serialize size
  2. 比较 run container 的 serialize size
  3. 权衡是否 serialize 成 run container

我们最后看 container_add:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
static inline container_t *container_add(
    container_t *c, uint16_t val,
    uint8_t typecode,  // !!! should be second argument?
    uint8_t *new_typecode) {
    c = get_writable_copy_if_shared(c, &typecode);
    switch (typecode) {
        case BITSET_CONTAINER_TYPE:
            bitset_container_set(CAST_bitset(c), val);
            *new_typecode = BITSET_CONTAINER_TYPE;
            return c;
        case ARRAY_CONTAINER_TYPE: {
            array_container_t *ac = CAST_array(c);
            if (array_container_try_add(ac, val, DEFAULT_MAX_SIZE) != -1) {
                *new_typecode = ARRAY_CONTAINER_TYPE;
                return ac;
            } else {
                bitset_container_t *bitset = bitset_container_from_array(ac);
                bitset_container_add(bitset, val);
                *new_typecode = BITSET_CONTAINER_TYPE;
                return bitset;
            }
        } break;
        case RUN_CONTAINER_TYPE:
            // per Java, no container type adjustments are done (revisit?)
            run_container_add(CAST_run(c), val);
            *new_typecode = RUN_CONTAINER_TYPE;
            return c;
        default:
            assert(false);
            roaring_unreachable;
            return NULL;
    }
}

Bulk

我们再回头看一下 Bulk API

1
2
3
4
5
6
typedef struct roaring_bulk_context_s {
    ROARING_CONTAINER_T *container;
    int idx;
    uint16_t key;
    uint8_t typecode;
} roaring_bulk_context_t;

这么看 Bulk API 就非常简单，这里实际上就是缓存了 container 处理的逻辑。

小小的疑问: add / contains 到底有多重？

  • Run: 使用 interleavedBinarySearch，纯二分查找定位到 lower_bound，然后看看有没有对应的 Run
  • Bitmap: 直接定位，O(1)
  • Array: 这里代码比较奇怪，算是一个拙劣的优化查询。这里导致其实在稀疏的容器中调用 contains 可能比想象的还重呢!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* Check whether x is present.  */
inline bool array_container_contains(const array_container_t *arr,
                                     uint16_t pos) {
    //    return binarySearch(arr->array, arr->cardinality, pos) >= 0;
    // binary search with fallback to linear search for short ranges
    int32_t low = 0;
    const uint16_t *carr = (const uint16_t *)arr->array;
    int32_t high = arr->cardinality - 1;
    //    while (high - low >= 0) {
    while (high >= low + 16) {
        int32_t middleIndex = (low + high) >> 1;
        uint16_t middleValue = carr[middleIndex];
        if (middleValue < pos) {
            low = middleIndex + 1;
        } else if (middleValue > pos) {
            high = middleIndex - 1;
        } else {
            return true;
        }
    }

    for (int i = low; i <= high; i++) {
        uint16_t v = carr[i];
        if (v == pos) {
            return true;
        }
        if (v > pos) return false;
    }
    return false;
}

而 add 的时候又是纯 binary search，屋檐了. 我在想这玩意改掉成统一的 binary search 会不会好些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Add value to the set if final cardinality doesn't exceed max_cardinality.
 * Return code:
 * 1  -- value was added
 * 0  -- value was already present
 * -1 -- value was not added because cardinality would exceed max_cardinality
 */
static inline int array_container_try_add(array_container_t *arr,
                                          uint16_t value,
                                          int32_t max_cardinality) {
    const int32_t cardinality = arr->cardinality;

    // best case, we can append.
    if ((array_container_empty(arr) || arr->array[cardinality - 1] < value) &&
        cardinality < max_cardinality) {
        array_container_append(arr, value);
        return 1;
    }

    const int32_t loc = binarySearch(arr->array, cardinality, value);

    if (loc >= 0) {
        return 0;
    } else if (cardinality < max_cardinality) {
        if (array_container_full(arr)) {
            array_container_grow(arr, arr->capacity + 1, true);
        }
        const int32_t insert_idx = -loc - 1;
        memmove(arr->array + insert_idx + 1, arr->array + insert_idx,
                (cardinality - insert_idx) * sizeof(uint16_t));
        arr->array[insert_idx] = value;
        arr->cardinality++;
        return 1;
    } else {
        return -1;
    }
}

Iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Roaring-internal type used to iterate within a roaring container.
 */
typedef struct roaring_container_iterator_s {
    // For bitset and array containers this is the index of the bit / entry.
    // For run containers this points at the run.
    int32_t index;
} roaring_container_iterator_t;

/**
 * A struct used to keep iterator state. Users should only access
 * `current_value` and `has_value`, the rest of the type should be treated as
 * opaque.
 */
typedef struct roaring_uint32_iterator_s {
    const roaring_bitmap_t *parent;        // Owner
    const ROARING_CONTAINER_T *container;  // Current container
    uint8_t typecode;                      // Typecode of current container
    int32_t container_index;               // Current container index
    uint32_t highbits;                     // High 16 bits of the current value
    roaring_container_iterator_t container_it;

    uint32_t current_value;
    bool has_value;
} roaring_uint32_iterator_t;

这里注意，container 上只有 index。这里推断一下，我们可以得出结论：

  1. 对于 array 来说，contains 可能执行的很慢，但是 iterator 开销比较低
  2. 对于 bitmap 来说，可能反过来，bulk-contains 可能比较快，iterator 反而要看一下后面的 bit 是否都 set 了

我们看到，实际上性能也会跟容器（或者甚至内容是否稀疏）相关，开销，很神奇吧！

Lazy Operations

1
2
3
4
5
6
7
8
9
roaring_bitmap_t *roaring_bitmap_lazy_or(const roaring_bitmap_t *r1,
                                         const roaring_bitmap_t *r2,
                                         const bool bitsetconversion);
void roaring_bitmap_lazy_or_inplace(roaring_bitmap_t *r1,
                                    const roaring_bitmap_t *r2,
                                    const bool bitsetconversion);
void roaring_bitmap_repair_after_lazy(roaring_bitmap_t *r1);
roaring_bitmap_t *roaring_bitmap_lazy_xor(const roaring_bitmap_t *r1,
                                          const roaring_bitmap_t *r2);

Lazy 本质上是：

  1. 在一些操作的时候，如果是 array-array，就构造出一些 bitmap 来，也不设置 cardinality
  2. 最后通过 roaring_bitmap_repair_after_lazy 修复 bitmap 和实现

比如观看这个实现，这里把一个非 lazy 操作封装成了好几步 lazy 操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
roaring_bitmap_t *roaring_bitmap_xor_many(size_t number,
                                          const roaring_bitmap_t **x) {
    if (number == 0) {
        return roaring_bitmap_create();
    }
    if (number == 1) {
        return roaring_bitmap_copy(x[0]);
    }
    roaring_bitmap_t *answer = roaring_bitmap_lazy_xor(x[0], x[1]);
    for (size_t i = 2; i < number; i++) {
        roaring_bitmap_lazy_xor_inplace(answer, x[i]);
    }
    roaring_bitmap_repair_after_lazy(answer);
    return answer;
}