SuRF: Range Query Filter

发表于

SuRF

本文介绍了一种SuRF的数据结构实现，用以替代传统的布隆过滤器，支持单点查询和范围查询使用。

INTRODUCTION

LSM树是市面上数据库常用的底层存储引擎，能提供快速写和一定速度的读取。但该设计的一个问题是由于SSTable的多层设计导致大量磁盘IO读取，由此引入了布隆过滤器作为内存数据结构来帮助查询。布隆过滤器对于单点查询很有用，但并不能处理范围查找，尽管也有一些类似的设计（如前缀布隆过滤器）做了优化，但总体不够灵活通用。

因此本文提出了Succinct Range Filter（下文简称SuRF），这是一种快速紧凑的过滤器，提供了精确匹配过滤、范围过滤和近似范围计数等功能。SuRF是建立在Fast Succinct Trie（FST）这一新型空间高效简洁的数据结构上，FST每个trie节点仅需要10bit。文章使用SuRF替代了RocksDB的布隆过滤器，这将范围查询的速度提高了1.5倍到5倍，但极端情况下会导致单点查询变慢40%。

FAST SUCCINCT TRIES

SuRF的核心数据结构是FST，这是一种空间优化的静态tire，可以做单点查询和范围查询，其设计基于以下的思路：一个tire的上层节点较少，但访问量很大；下层节点虽多，但访问不算频繁。因此FST使用了基于位图的快速编码方案（LOUDS-Dense）来对上层节点编码，下层则用LOUDS-Sparse方案来编码，节省空间。

Background

如果一颗树所占用的空间接近于信息论的下限，则该树可以认为是succinct。论文使用的是一种叫Level-Ordered Unary Degree Sequence的技术，LOUDS以广度优先的顺序遍历节点，并使用一元编码Unary coding对每个节点的度进行编码，例如下图节点3有三个字节点，因此被编码成"1110"。

编码完成后，该树会变成一组bit序列，需要访问节点时，则使用rank＆select两种操作：

  • rank1(i): 返回[0, i]位置区间中, 1的个数；
  • select1(i): 返回第i个1的位置(整个bit序列)；
  • 对应的则是rank0(i)和select0(i)操作；

如今关于rank＆select的实现会使用查找表预算存取计算好的结果，保证查询时可以在常数时间里完成。有了rank＆select的支持，LOUDS就可以在常数时间内实现SuRF需要的点查询和范围查询。假设节点代号和bit位置都是从0开始的：

  • 在bit序列中第i个节点的位置：select0(i)+1；
  • 在bit序列中从p开始的节点的第k个子节点：select0 (rank1 (p + k)) + 1；
  • 始于p的节点的父节点位置：select1 (rank0 (p))；

LOUDS-Dense

LOUDS-Dense使用三个bit map和一个value的字节序列对每个trie节点按层级进行编码：

  • D-Labels：记录每个节点的分支标签；上图中根节点具有标记为f，s和t的三个分支。 D-Labels位图设置第102位（f），115位（s）和116位（t）并清除其余位；
  • D-HasChild：表示节点是叶子节点还是中间节点，以上图根节点为例，f和t都有子节点，但s没有，所以102和106两个bit会设置为1；
  • D-IsPrefixKey：标记当前前缀是否为有效key；以上图根节点为例，f既作为前缀，同时也是trie里的有效key；
  • D-Values : 存储的是固定大小的 value，本文中则是三种后缀的指针；

用rank&select操作trie树，则是：

  • 第一个孩子节点：D-ChildNodePos(pos)=256 × rank1(D-HasChild, pos)；
  • 父节点：DParentNodePos(pos)=select1(D-HasChild,[pos / 256])；

LOUDS-Sparse

如上图所示，LOUDS-Sparse使用四个字节或者bit序列对trie节点进行编码，然后将编码的节点按层次顺序进行串联。

  • S-Labels：记录分支标签，按level order顺序记录所有节点的label，并且使用0xFF($)来标记该key同时也是key节点；
  • S-HasChild：使用一个bit记录节点的label是否含有分支子节点；
  • S-LOUDS：使用一个bit记录每个label是否为该节点的第一个label；
  • S-Values：与上面类似；

用rank&select操作trie树，则是：

  • 孩子节点：S-ChildNodePos(pos) = select1(S-LOUDS, rank1(S-HasChild, pos) + 1);；
  • 父节点：S-ParentNodePos(pos) = select1(S-HasChild, rank1(S-LOUDS, pos) - 1)；

LOUDS-DS and Operations

LOUDS-DS就是一种混合trie，上层用LOUDS-Dense编码，下层使用LOUDS-Sparse编码。其中的分界点则根据性能和空间进行调整，LOUDS-Dense-Size(l)表示从0到l（不包含l）层采用LOUDS-Dense编码，而LOUDS-Sparse-Size(l)则表示从l到H层采用LOUDS-Sparse方式编码：

1
LOUDS-Dense-Size(l) × R ≤ LOUDS-Sparse-Size(l) // 通常使用R = 64作为默认值，R越小，性能越好但空间使用更多

LOUDS-DS支持三个基本操作：

  • ExactKeySearch(key)：如果key存在，则返回key的值（否则返回NULL）；
  • LowerBound(key)：返回一个迭代器，该迭代器指向的键-值对(k, v)，其中k是按字典顺序的满足k≥key的最小的键；
  • MoveToNext(iter)：将迭代器移至下一个键值；

对于点查询，则是先在LOUDS-Dense上查询，查不到即到LOUDS-Sparse查询。对于范围查询，则是执行LowerBound，找到最小的满足k≥key的键后，则光标将从当前的叶子标签位置开始并向前移动，就是正常的tree搜索方式。

Space and Performance Analysis

考虑到在LOUDS-DS中LOUDS-Sparse的节点更多，假设这是一个具备n个节点的trie，其中会有8n位用于S标签，2n位用于S-HasChild和S-LOUDS，总共10n位。

对于点查询，在每个LOUDS-Dense级别上进行搜索都需要两次数组查找，以及对位向量D-HasChild的rank操作。因此，主要操作是对所有位向量进行rank和 select，并在LOUDS-Sparse层进行标签搜索。

Optimizations

论文针对LOUDS-DS中的三个关键操作：rank、select和label search进行了优化。

  • Rank

上图展示了一个简洁的Rank结构，将bit vector分割成B bits大小的块，每个块用32bits的字段预先计算好的到这个block的rank值。对于一个pos来说，就有rank1(pos) = LUT[i / B] + popcount[i / B * B, i]。popcount是内置的CPU指令，可以快速计算出某一段区间1的个数。

  • Select

同样是使用LUT的方法，预先计算好值。假设采样周期是3，上图中第三个LUT保存的就是3x2，也就是第6个1的pos值，即8。那就有select1(i) = LUT[i / S] + (selecting (i - i / S * S)th set bit starting from LUT[i / S] + 1) + 1。

  • Label Search

使用SIMD指令在LOUDS-Sparse中执行标签搜索。

  • Prefetching

在切换到LOUDS-DS中的不同位/字节序列之前进行预取。

SUCCINCT RANGE FILTERS

基于FST构建SuRF，最重要的是在false positive rate和filter所需要的内存使用之间取得平衡。论文的做法是使用裁剪trie，通过截断低层次的trie，并使用从key获得的后缀位（key本身或者key的哈希值）做替代。论文介绍了4种不同的trie树裁剪方式。

  1. Basic SuRF

Basic SuRF的基本思路就是只存储key的共有前缀和一个额外的byte，裁剪掉树的部分叶节点。Basic SuRF的FPR与key的分布有关。

  1. SuRF with Hashed Key Suffixes

在Basic SuRF基础上，通过对key进行哈希计算，将hash值的n个bits存储到value中，这种方法可以降低FPR，但对范围查询没有帮助。

  1. SuRF with Real Key Suffixes

SuRF-Real存储n个bits的真实key，这样同时增强了Point query和Range query，但其FPR还是要比SuRF-Hash高。

  1. SuRF with Mixed Key Suffixes

SuRF-Mixed的做法是混合使用2和3两种方式，一部分是real key，另一部分是hashed key。

Operations

论文总结了如何使用FST实现SuRF的基本操作。

  • build(keyList)：根据给定的key构建fitter；
  • result = lookup(k)：对k执行点查询，返回true意味着k可能存储。以上面SuRF为例，首先搜寻key，直到叶子结点。如果未到叶节点就终止了则返回false；否则计算k的相关bits与叶节点的相关bits做比较；
  • iter, fp_flag = moveToNext(k)：这个操作实际上是LowerBound执行，返回满足>=k的最小key的双向迭代器；
  • count, low_fp_flag, high_fp_flag = count(lowKey, highKey)：返回在[lowKey, highKey]范围内的key个数；

EXAMPLE APPLICATION: ROCKSDB

论文将SuRF与RocksDB集成在一起，以替代其Bloom过滤器。下图显示了RocksDB中Get，Seek和Count查询的执行路径。Next的核心算法类似于Seek。过滤器操作在红色框中。如果该框为虚线，则可能由于误报需要检查边界key。

对于Get(key)，SuRF的用法与Bloom过滤器完全相同。

对于Seek(lk, hk)，RocksDB首先通过在块索引中搜索lk来决定所有级别的候选SSTable。在没有SuRF的情况下，RocksDB会检查每个候选SSTable并获取满足>=lk的最小的块。 RocksDB然后比较候选key，找到全局最小key。使用SuRF，则无需获取实际的块，RocksDB可以通过在其SuRF上执行moveToNext(lk)查询来避免每个SSTable都进行IO，从而获取每个SSTable的候选key。如果查询成功（例如，是Open Seek或K≤hk），RocksDB将从选定的SSTable中精确地获取一个包含全局最小值K的块。如果查询失败（即，K>hk），则不没有读盘IO。

CONCLUSION

本文介绍了SuRF，该filter支持单点查询、范围查询和计数查询，SuRF建立在一个新的succinct数据结构上，即FST。FST的性能极高，并且SuRF本身的内存使用也是较为搞笑的，其空间使用与FPR的权衡可以通过不同数量的后缀位来调整。通过在RocksDB上替换了bloom filter的测试，显著地减少了IO并提高了范围查询的吞吐量。