[TOC]

参考

读后感 SuRF: Practical Range Query Filtering with Fast Succinct Tries
SuRF: 基于Fast Succinct Tries的Range Query Filter

1. Succinct Data Structure

1.1. 简介

Succinct 数据结构的主要思想就是使用非常少量的空间（接近信息编码的下界）来
存储数据，是一种通过位图形式表达数据结构的技术。可以认为它就是使用了一种非常高效的压缩算法，但不同于压缩，它同时来提供非常高效的查询。开源实现可见sdsl-lite

1.2. LOUDS

对于 Succinct data structure 来说，我们会将数据按 0 和 1 来编码，所以可以用 bits，而不是 bytes。操作 succinct 数据，通常的就是以下几个操作函数：

// x 表示比特位的位置
rank1(x) - 返回在 range [0, x] 里面 1 的个数
select1(y) - 返回第 y 个 1 所在的位置
rank0(x) - 返回在 range [0, x] 里面 0 的个数
select0(y) - 返回第 y 个 0 所在的位置

在 SuRF 中，参考的基础编码方式是 Level order unary degree sequence(LOUDS)，在 LOUDS 里面，我们会将一颗树，分层依次进行编码。而规则也是非常的简单，如果这个树的节点有 N 个子节点，那么就用 N 个 1 来编码，然后最后加上 0。如图1，把每个节点的编码顺序排列，就得到了 LOUDS 编码。

观察上图，有两个核心点需要理解：

• 对于节点位置i，i之前比特值为0的个数表示前面存在的节点数量，如节点4之前，有4个0，表示节点4之前有4个节点，分别是0，1，2，3；
• 对于节点位置i，i之前比特值为1的个数表示前面存在的节点数量加上这些节点对应的直接子节点个数，如节点4之前，有8个1，说明加上直接子节点，共有8个节点，分别是，0，1，2，3，5，6，7，8.
  注：前面 是 相对层次遍历而言

# i 表示节点编号（从0开始），p表示bit位编号（从0开始）
第i个节点的起始bit位置 = select0(i) + 1
已知bit位等于1且bit位置为p，该比特位对应节点的子节点编号i = rank1(p)
第i个节点的父节点起始bit位置 = select1(i)
起始bit位置为p的节点编号 = rank0(p)
第i个节点(其bit位置=p)的第k个子节点（k从0开始）的起始bit位置 = select0(rank1(p+k)) + 1
第i个节点的父节点的起始bit位置 = select1(rank0(p))

举例说，取节点3，那么他的子节点是5、6，父节点是0。

• 节点3的起始bit位置 = select0(3) + 1 = 7
• 节点3第一个子节点编号 = rank1(7 + 0) = 5
• 节点3第二个子节点编号 = rank1(7 + 1) = 6
• 节点3的父节点起始bit位置 = select1(3) = 2，父节点编号 = rank0(select1(3)) = rank0(2) = 0
• 节点3的第1个子节点的起始bit位置 = select0(rank1(7 + 0)) + 1 = select0(5) + 1 = 11
• 节点3的第2个子节点的起始bit位置 = select0(rank1(7 + 1)) + 1 = select0(6) + 1 = 12
• 节点5的父节点起始bit位置 = select1(5) = 7，父节点编号 = rank0(select1(5)) = rank0(7) = 3
• 节点6的父节点起始bit位置 = select1(6) = 8，父节点编号 = rank0(select1(6)) = rank0(8) = 3

2. SuRF: 一个优化的 Fast Succinct Tries

2.1. Fast Succinct Tries

SuRF 的核心数据结构就是 Fast Succinct Tries（FST），一种空间节省，支持 point 和 range query 的静态 trie。
基于LOUDS编码方式, FST对LOUDS进行了进一步压缩, 下图介绍了基本的压缩方法:

在很多时候，对于一棵树来说，上层的 trie 节点较少，但访问频繁，也就是我们俗称的 hot，而下层的节点则相对的 cold 一点。因此，SuRF 使用了两种数据结构来分别处理 hot 和 cold 节点。在 upper 层上面使用了 LOUDS-Dense，而在 lower 层上面使用 LOUDS-Sparse。

2.1.1. LOUDS-Dense

假设每个节点最多有256个子节点, 那么在LOUDS-Dense编码方式中, 每个节点使用3个256个bit的bitmap来保存信息. 这3个bitmap分别是:

• D-Labels: 将子节点的label变化置位，表示这个 node 是否有 label i，如果有，那么第 i bit 位就是 1。譬如上面的例子，Dense 的 label 在 level 1 有 f，s 和 t，那么在第 102（f），115（s） 和 116 （t）bit 位就会设置为 1。大家其实可以看到，具体哪一个 bit 位，就是 ASCII 码的值。
• D-HasChild: 标记对应的子节点是否是叶子节点还是中间节点，如果一个 node 下面还有子节点，那么就将该 label 对应的 bit 在 D-HasChild 里面设置为 1。继续上面的例子，f 和 t 都有子节点，而 s 没有，所以 102 和 116 bit 都会设置为 1。
• D-IsPrefixKey: 标记当前前缀是否是有效的key 我们仍然可以使用select&rank操作来访问对应的tree节点。这个解释其实有点绕，主要是用来表示一个 prefix 是否也是一个合法的 key。还是上面的例子，我们可以看到，f 这个 node 是有子节点的，所以它是一个 prefix，但同时，f 也是一个 key。在上图中， SuRF 使用了 ‘$’ 这个符号（实际对应的值是 0xFF）来表示这样的情况。

最后一个字节序列就是 D-Values，存储的是固定大小的 value。Value 就是按照 每层 level 的顺序存放的。

如果要进行遍历 LOUDS-Dense，我们可以使用之前提到的 rank 和 select 操作。对于 bit 序列bs来说，我们用rank1/select1(bs, pos)来表示在bs上面pos的rank和select操作。譬如，假设pos是D-Labels上面的当前bit pos，如果D-HasChild[pos] = 1，那么第一个子节点的pos则是D-ChildNodePos(pos) = 256 x rank1(D-HasChild, pos)，而父节点则是ParentNodePos(pos) = 256 x select1(D-HasChild, pos / 256)。

2.1.2. LOUDS-Sparse

LOUDS-Sparse使用3个bit序列来对trie树进行编码, 在整个bit序列中, 每个节点的长度相同, 这三个bit序列分别是

• S-Labels: 记录每个节点的label编号, key节点用0xFF标记, 按照树的层数按顺序记录(如果最多有256个子节点, 则每个节点占用4个byte)。譬如上图的 rst 这样的 bytes 顺序，Sparse 仍然使用了 0xFF（也就是上图的 $ 符号）来表示一个 prefix key。因为这样的 0xFF 只会出现在第一个子节点上面，所以是能跟实际的 0xFF label 进行区分的。
• S-HasChild: 记录每个节点是否含有子节点, 有的话标记为1, 每个节点使用一个bit
• S-LOUDS: 记录每个节点是否是第一个节点, 每个节点使用一个bit 仍然可以使用rank&select操作来访问整个trie树。如果一个 label 是第一个节点，那么对应的 S-LOUDS 就设置为 1，否则为 0。譬如上图第三层，r，p 和 i 都是第一个节点，那么对应的 S-LOUDS 就设置为 1 了。

2.1.3. 好处和空间开销

2.1.3.1. 好处

trie树经过LOUDS-DS编码之后, 可以高效支持下面3个操作:

• ExtractKeySearch(key): 如果key存在, 返回value
• LowerBound(key): 返回一个迭代器, 迭代器指向第一个大于等于key的位置
• MoveToNext(iter): 移动迭代器指向下一个key-value

2.1.3.2. 空间复杂度分析

给定一个含有n个节点的trie树, S-labes需要使用8n个bits, S-HasChild和S-LOUDS一共使用2n个bits, 所以LOUDS-Sparse使用10n个bits. LOUDS-Dense的空间与Sparse和Dense的分界线有关, 通常情况下, Dense占用的空间要远远小于Sparse部分. 这样整个LOUDS-DS编码的Trie树接近10n个bits, 理论证明最少的编码数量大约是9.44n个bits, 接近理论的下限了.

2.2. 优化

对于 SuRF 来说，为了提高查询的速度，一个重要的优化手段就是提高 rank 和 select 执行的效率，在 SuRF 里面，引入了 LookUp Table（LUT）。

对于 rank 来说，会将 bit vector 切分成 B bits 大小的块，每块都使用 32 bits 的字段来预先保存了计算好的到这个 block 的 rank 值。譬如，在上面的例子，第三个就是 7，保存的就是前两个 block 总的 rank 数量。

而对于一个 pos 来说，它的 rank1(pos) = LUT[i / B] + popcount[i / B * B, i]，popcount 是一个 CPU 指令，用来快速的计算某一段区间的 1 的个数。假设我们现在要得到 pos 12 的 rank 值，先通过 LUT[12 / 5] = LUT[2] = 7，然后得到 range [12 / 5 * 5, 12] = [10, 12]，使用 popcount 得到 2，那么 12 的 rank 就是 9。
对于 select 来说，也是使用的 LUT 方法，预先记录算好的值。具体到上面，假设将采样的周期设置为 3，那么第三个 LUT 就保存的是 3 x 2，也就是第 6 的 1 的 pos 值，也就是 8。对于一个 pos 来说，select1(i) = LUT[i / S] + (selecting (i - i / S * S)th set bit starting from LUT[i / S] + 1) + 1。譬如，如果我们要得到 select1(8)，首先得到 LUT[8 / 3] = LUT[2] = 8，然后需要从 position LUT[8 / 3] + 1 = 9 这个位置，得到第 (8 - 8 / 3 * 3) = 2 个位置的 bit，也就是 1，所以 select1(8) 就是 10。

当然，SuRF 还有其它很多优化手段，譬如使用 SIMD 来提速 label 的查找，使用 prefetch 技术等，这里就不说明了。

2.3. Succinct Range Filter

对于通常的 SuRF 来说，它因为对这个 trie 都进行了编码，所以它是完全精确的，虽然它是一种省空间的数据结构，但很多时候，我们仍然需要能保证在内存里面存储所有的 SuRF 数据，所以我们就需要对 SuRF 进行裁剪，不存储所有的信息，也就是说，我们需要在查询的 False Positive Rate（FPR）和空间上面做一个权衡。

在 SuRF 里面，有几种方式，Basic，Hash，Real 以及 Mixed。

1. Basic SuRF

FST是一个完整的索引结构, 可以存储全部的索引数据, 这种情况下是100%精确的. Basic SuRF的思想就是只存储key的前缀, 实际上就是砍掉树的部分叶子节点. 我们使用FPR(false positive rate)来衡量效果, 具体的FPR与key的分布有关, 论文中给出了Basic SuRF的FPR的上限.

2. SuRF with Hashed Key Suffixes

为了降低FPR, 在Basic SuRF的基础上, 对key进行hash计算之后, 将hash值的n个bits存储到value中, 查询的时候还原回来完整的key. 这种方法可以降低FPR, 论文中有计算公式, 但是这种方法对range query没什么帮助.

3. SuRF with Real Key Suffixes

和SuRF with Hashed Key Suffixes不同, SuRF-Real存储n个bits的真实key, 这样point查询和range查询都可以获益, 但是在point查询下, FPR比SuRF-Hash要高.

4. SuRF with Mixed Key Suffixes

为了享受Hash和Real两种方式的优点, Mix模式就是将两种方式混合使用, 混合的比例可以根据数据分布进行调节来获得最好的效果.

2.4. 应用场景

试想如果我们把rocksdb的所有key都复制一份存储在SuRF中的话(不存储value), 那么SuRF起的作用不就和bloomfilter一样了么, 同时还可以支持range query了。具体的性能测试可见（读后感 SuRF: Practical Range Query Filtering with Fast Succinct Tries） 为此论文将SuRF应用在了Rocsdb中, 替换了bloomfilter, 并且进行了对比测试(占用的空间和bloomfiler相同). 测试程序运行在普通的SSD上, 下图是性能对比数据:

从性能数据上看, 对于point query, SuRF的效果比bloomfilter相比还是差一些, 但是在range query下, 效果比bloomfilter要好很多了, IO减少的次数还是非常明显的.