lucene posting list 编码之Frame of Reference

本文是：https://www.elastic.co/cn/blog/frame-of-reference-and-roaring-bitmaps 文章的翻译及理解。

lucene 在存储 doc 时，会为每个 doc 分配一个 doc_id。doc_id 是 segment 维度（index->shard->segment）的一个数值，这个数值的范围是[0,2^32-1]，因此：一个 segment 最多允许存储 2^32-1 个 doc

Inside each segment, documents are given an identifier between 0 and the number of documents in the segment (up to 231-1)

一个倒排链(posting list)中的 doc_id 是有序的，为了高效地存储倒排链，lucene 使用了 FOR（Frame Of Reference） 编码，其核心是 for-delta。

现在有一个 posting list，其中有 6 个 doc_id：[73，300，302，332，343，372]，应该如何高效存储呢？Java 中一个 int 型占用 4B，存储 6 个 int 型数字需要：4B*6=24B。那：FOR 编码之后是如何存储的呢？看下图：

第1步：delta 编码

第1个 doc_id 是73，加上 delta 227 等于：300，就是第2个 doc_id 的数值。类似地，73+227+2=302 就是第3个 doc_id 的数值。因此，只需要把第1个doc_id记录下来，然后保存后面每个doc_id 的 delta 值，就能知道每个 doc_id 的数值了。

73 0+73=73
227 73+227=300
302 300+2=302
332 302+30=332
343 332+11=343
372 343+29=372

如果 delta 的取值范围是[0,255]，那么只需要 1B 就可以存储 delta。因此，相比于存储 doc_id 原始值（需要 4B），存储 delta 能起到压缩效果。

第2步：split into blocks

第1步的分析有个前提假设是： delta 的取值范围是[0,255]，实际中：delta 的取值范围是不确定的，为了 delta 的取值范围不大于“某个值”，可以将 posting list 拆分成 block，计算出这个 block 内最大的 delta 是多少，然后将该 delta 存储到 block 表头，block 表头 delta 占用的 bit 数量就是：后续 delta 所需要的 bit 数量的最大值。

Lucene computes the maximum number of bits required to store deltas in a block, adds this information to the block header, and then encodes all deltas of the block using this number of bits

以上图示例：拆分了 2 个 block 块，第1个 block 块的 delta 取值是：[73,227,2]，最大的 delta 是 227，这个 block 块中的每个 delta 需要使用 8个bit 存储。而第2个 block 块的 delta 取值是：[30,11,29]，最大的 delta 是 30，这个 block 块中每个 delta 只需要使用 5个 bit （因为 5个 bit 存储范围是： 2^5-1=31）都可以存储下来。

因此，经过 delta-encoding 之后，6个 doc_id 所需要的存储从原来的 24B 减少到现在的 7B。（38bit + 35bit = 7B）

可以看出：block 块的拆分，其目的是在一部分 doc_id 中寻找一个合适的 最大 delta 值，使得这部分doc_id 对应的 delta 不超过 最大 delta，从而保证最佳压缩效果。

还有一个需要对 posting list 的 doc_id 压缩编码的地方是：ES 的 filter cache。关于 filter cache 可先参考：https://www.elastic.co/guide/en/elasticsearch/reference/current/query-cache.html

filter cache 有3种数据结构来实现：

1. integer array
2. bitmap
3. roaring bitmap

对于 integer array，如果 filter cache 只缓存几个 doc_id（少量的doc_id），那么使用 integer array 内存是OK的，但是若 filter cache 缓存了100M个 doc_id，则需要 400MB 内存空间，因此integer array 不适用于“dense sets” 场景。

bitmap 和 roaring bitmap 是采用 bit 思想存储 int 型整数，一个 int 型整数只需要1个bit存储，100万个 int 型整数大约需要12.5MB内存空间，压缩效果非常好。

A bitmap is an array where each entry takes only one bit, so they only have two possible values: 0 or 1.... If we compare to option 1, memory usage is much better on dense filters since we would now only need 100M bits = 12.5MB

roaring bitmap 相比于 bitmap，多了一个 split block 步骤，简单说就是：高16位与低16位分别encoding，进一步优化压缩效果。

文章的最后对比了这3种数据结构在：内存占用、遍历操作、skip操作 这2种 Lucene 最基本的 search operation 的性能。总结起来就是：如果 filter cache 需要缓存的 doc_id 非常的多，那么很适用 bitmap。integer array 虽然快，但是太耗费内存。