SuRF: Practical Range Query Filtering with Fast Succinct Tries 阅读笔记

SuRF(Succinct Range Filter)是一种快速而紧凑的过滤器，同时支持点查询和范围查询(包括开区间查询、闭区间查询、范围计数)，可以在RocksDB中用SuRF来替换Bloom过滤器。

FAST SUCCINCT TRIES

SuRF是基于FST(Fast Succinct Tries)的，这是一种同时支持点查询和范围查询，且具有高效的空间利用率的静态字典树。FST的设计是基于如下观察结果：字典树的上层包含了相对较少的节点，但却发生了相对较多的访问，而字典树的下层包含了相对较多的节点，但发生的访问较少。因此FST包含了LOUDS-Dense和LOUDS-Sparse两个部分，LOUDS-Dense优先考虑性能而不是空间占用，LOUDS-Sparse高效地利用空间从而限制了FST的总体空间占用。

下图(引用自论文)是一个FST的例子：

LOUDS-Dense

LOUDS-Dense中的每个节点包含了3个256位的bitmap和一个字节序列，他们的含义如下：

1. D-Labels：标记该节点的分支表示的字符。如果一个节点的分支表示的字符在bitmap中的相应位是1，该位的下标为这个字符的ASCII码值。$是一个特殊字符，表示到该节点某个分支位置的前缀也是一个合法的key。
2. D-HasChild：标记该节点的每个分支是否还有子节点。
3. D-IsPrefixKey：标记到该节点某个分支为止的前缀是否也是一个合法的key。
4. D-Values：是按序排列的一些与每个key对应的定长的值。

两个公式：

1. D-ChildNodePos(pos) = 256 ×rank1(D-HasChild, pos)：计算第一个子节点的位置。
2. ParentNodePos(pos) = 256 ×select1 (D-HasChild, ⌊pos/256⌋) ：计算父节点的位置。

LOUDS-Sparse

LOUDS-Dense中的每个节点包含了2个字节序列和2个bitmap，他们的含义如下：

1. S-Labels：标记该节点的分支表示的字符。
2. S-HasChild：标记该节点的每个分支是否还有子节点。
3. S-LOUDS：标记该节点的每个分支是否是该节点的第一个分支。
4. S-Values：和D-Values一样。

三个公式：

1. S-ChildNodePos(pos) = select1(S-LOUDS, rank1(S-HasChild, pos) + 1)
2. S-ParentNodePos(pos) = select1(S-HasChild, rank1(S-LOUDS, pos) - 1)
3. S-ValuePos(pos) = pos - rank1(S-HasChild, pos) - 1

FST的优化

FST中最典型的操作就是rank、select和label search，FST对这三个都做了优化。

下图(引用自论文)是FST优化的一个例子：

1. rank优化：对于一个bit-vector，每B位作为一个block，每个block在LUT中分配32位的空间来存储这个block起始位置的rank值。LOUD-Dense的B是64，这就保证了popcount指令在每次rank计算时只需要调用一次，LOUD-Sparse的B是512，适应于cacheline的大小，而且可以节省空间。
2. select优化：对于每一个采样查询，在LUT中分配32位的空间来存储这次采样查询得到的select的值。

SUCCINCT RANGE FILTERS

为了平衡FPR和空间占用，基于FST的SuRF采用了删减的字典树，并有四种模式：

1. SuRF-Base：对于用于构建SuRF的key，只截取在所有key中能唯一区分这个key的最短的前缀。这种模式的空间占用最小，但是FPR最高。
2. SuRF-Hash：在SuRF-Base的基础上，对于每个key，在叶节点的Values里存储这个key的哈希值的后n位，当搜索到叶节点后，还需要比较这个哈希值的后n位。这种模式能极大的减小点查询的FPR，但是并不会减小范围查询的FPR，因为key的哈希值无法用于比较key的顺序。
3. SuRF-Real：在SuRF-Base的基础上，对于每个key，存储这个key用于构建SuRF的前缀之后的n位，当搜索到叶节点后，还需要比较这n位。这种模式可以同时提升点查询和范围查询的FPR，但是提升的效果不如SuRF-Hash。
4. SuRF-Mixed：SuRF-Hash和SuRF-Real的结合。

382 Love u