surf-cn

摘要
我们提出了简洁范围过滤器（SuRF），这是一种快速而紧凑的数据
近似会员资格测试的结构。不像传统
Bloom过滤器，SuRF支持单键查询和通用查询
范围查询：开放范围查询，封闭范围查询和范围
计数。 SuRF基于称为快速精简的新数据结构。
匹配点和范围查询性能的Trie（FST）
最新的订单保存索引，而仅消耗
每个trie节点10位。 SuRF中两点的误报率
和范围查询是可调的，以满足不同的应用程序需求。
我们评估了RocksDB中的SuRF，以替代其Bloom过滤器
通过在访问磁盘数据之前过滤请求来减少I / O
结构。我们对100 GB数据集的实验表明
RocksDB的带有SuRF的Bloom过滤器可加快开放搜索（无需
上限）和封闭式查询（具有上限）
至1.5倍和5倍，最坏情况下的成本适中（全失）
点查询吞吐量，因为误报率略高。

1 介绍
写优化的日志结构合并（LSM）树[44]是通用数据库的流行的低级存储引擎，
提供快速写入[5，50]和大量摄取的DBMS，例如时间序列数据库[11，48]。快速查询的主要挑战之一
处理是项目可以驻留在不可变文件（SSTables）中
从各个层次[3，36]。基于LSM树的设计中的项目检索
因此可能会导致多个昂贵的磁盘I / O [44、50]。这个
挑战要求内存中的数据结构，以帮助查找
查询项目。 Bloom过滤器非常适合此任务[48，50]
因为它们足够小以驻留在内存中，并且它们具有
仅“单面”错误-如果存在密钥，则布隆过滤器
返回true；如果缺少键，则过滤器可能会返回
错误，但可能会导致误报。

尽管Bloom过滤器对于单键查找很有用（“是键
SSTable中的42？”），它们无法处理范围查询（“是否存在
键在SSTable中的42到1000之间？”）。仅使用Bloom过滤器，
基于LSM树的存储引擎必须读取其他表块
从磁盘进行范围查询。或者，可以维持一个
辅助索引，例如B + Tree，以支持此类范围查询。
范围查询的I / O成本很高，以至于基于LSM树
设计通常使用前缀Bloom过滤器来优化某些固定前缀
查询（例如，“电子邮件以com.foo @开头的位置”）[6、25、48]，尽管
它们对于一般范围查询的灵活性差。设计师
RocksDB的[6]表示希望拥有更灵活的功能
为此目的的数据结构[24]。少数近似数据
存在结构（包括前缀Bloom过滤器）可以加速
范围查询的特定类别，但都不是通用的。

本文提出了一种简洁的范围滤波器（SuRF）
紧凑型过滤器，可提供精确匹配过滤，范围过滤和近似范围计数。像Bloom过滤器一样，SuRF
保证了点和范围隶属度测试的单方面错误。
SuRF可以在误报率和内存消耗之间进行权衡，并且这种权衡可以半独立地针对点和范围查询进行调整。 SuRF建立在新的节省??空间（简洁）的基础上
数据结构称为快速简洁Trie（FST）。对于整数和字符串工作负载，它的性能都可以与最新的未压缩索引结构（例如B + tree [18]，ART [37]）相媲美或更好。 FST每个trie节点仅消耗10位，接近
信息理论的下限。
SuRF中的关键见解是通过删除Trie和的等级，将FST转换为近似匹配（范围）成员资格过滤器。
用一些后缀位替换它们。的数量
这样的位（来自密钥本身或来自密钥的哈希值-正如我们
本文稍后讨论）为减少误报而交易空间。
我们通过微基准和布鲁姆过滤器评估SuRF
在RocksDB中进行替换。我们在100 GB时间序列上的实验
数据集显示用相同的SuRF替换Bloom过滤器
过滤器尺寸会减少I / O。这样可以加快开放范围查询的速度
上限）的1.5倍和近距离查询（上限）
与原始实施方案相比，最高可放大5倍。对于点
查询，最坏的情况是没有查询键
存在于数据集中。在这种情况下，RocksDB的使用速度降低了40％
SuRF代替Bloom滤光片，因为它们具有更高的滤光片（0.2％vs.
0.1％）的误报率。可以消除这种性能差距
通过将SuRF的大小每个键增加几位。

本文做出了三个主要贡献。首先，我们描述
在第2节中，我们的FST数据结构的空间消耗为
接近信息论所需的最小位数
但性能等同于未压缩的订单保留
索引。其次，在第3节中，我们将介绍如何使用FST来
构建SuRF，这是一种对两种方法都支持的近似成员资格测试
单键和范围查询。最后，我们更换Bloom过滤器
在RocksDB中使用大小匹配的SuRF，并表明它可以改善
范围查询性能，在最坏的情况下成本适中
点查询吞吐量，因为误报率略高。

2快速成功案例
SuRF中的核心数据结构是FST。节省空间，
回答点和范围查询的静态特里。 FST快4–15倍
比以前更简洁的尝试使用其他树表示[15，17，
31、32、34、39、40、46、49]，达到与
比最新的基于指针的索引更好。
FST的设计基于以下观察：
一个trie的节点数很少，但会带来许多访问。下层
级别包括大多数节点，但相对“冷淡”。
因此，我们使用基于快速位图的上层编码
编码方案（LOUDS-Dense），其中子节点搜索仅需要一次数组查找，即可在空间上选择性能。我们
使用节省空间的LOUDS-Sparse对较低级别进行编码
方案，因此编码特里树的整体大小是有界的。
FST的贡献是双重的。虽然算法
LOUDS-Dense和LOUDS-Sparse的设计并不新鲜，其组合（我们称为混合编码方案LOUDS-DS）
相同的数据结构是。如第4.1节所示，LOUDS-DS
在保持简洁的同时实现高性能的关键。
第二，就我们所知，FST是第一个简洁的尝试
与基于最新指针的性能相匹配
索引结构（现有的简洁Trie实现通常是
至少慢一个数量级）。这种性能改进允许简洁地尝试满足很多要求
更广泛的实际应用。
对于本节的其余部分，我们假定特里映射了键
到固定长度值。我们还假定特里的扇形为
256（即每级一个字节）。

2.1背景
如果表示所占的空间为close1，则树表示为“简洁”
到信息理论的下界
是区分任何对象所需的最小位数
在课堂上。大小为n的一类至少需要log2 n位才能进行编码
每个对象。度为k的特里树是根结点树，其中每个节点
最多可以有k个带有从集合中选择的唯一标签的孩子
{0，1，， 。 。 ，k∥1}。既然有
kn + 1 n / kn + 1个n节点尝试的度数k，信息理论的下界约为
n（k log2 k∥（k∥1）log2（k∥1））位[17]。序树是有根的
每个节点可以有任意数量的子节点的树
订购。因此，简洁地编码序数树是必要的步骤
对简洁的尝试。
Jacobson [34]率先研究了简洁的树表示，并介绍了层序一元度序列
（LOUDS）对序数树进行编码。顾名思义，LOUDS
以广度优先的顺序遍历节点，并对每个节点的
学位使用一元代码。例如，图1中的节点3具有
三个孩子，因此编码为“ 1110”。
导航用LOUDS编码的树会使用等级和选择
原语。给定位向量，rank1（i）会计算1的个数
直到位置i（rank0（i）计数为0），而select1（i）返回
第i个1的位置（select0（i）选择0）。现代排名和选择
实现[30、43、53、58]通过使用
查找表（LUT），用于存储预先计算的结果的样本
这样他们只需要在样本之间计数即可。
有了适当的等级和选择支持，LOUDS可以执行树导航，足以实现该点和
持续时间内SuRF中需要的范围查询。我们假设
节点/子代号和位位置均从零开始：
?第i个节点的位置= select0（i）+ 1?从p开始的节点的第k个子节点的位置=
select0（rank1（p + k））+1?节点的父节点的位置始于p = select1（rank0（p））

2.2大声-密集
LOUDS-Dense使用三个大小的位图对每个trie节点进行编码
256（因为节点扇出为256）和字节序列
值如图2的上半部分所示。编码如下
级别顺序（即广度优先顺序）。
第一个位图（D-Labels）记录了每个位图的分支标签
节点。具体来说，位图中的第i位，其中0≤i≤255，
指示节点是否具有带有标签i的分支。例如，
图2中的根节点具有三个传出分支，分别标记为f，s，
和T。 D-Labels位图设置第102（f），115（s）和116
（t）清除其余部分。
第二个位图（D-HasChild）指示是否分支
指向子trie或终止（即，指向值或
分支不存在）。以图2中的根节点为例
例如，f和t分支以子尝试继续，而
s分支以一个值终止。在这种情况下，D-HasChild
位图仅设置节点的第102位（f）和第116位（t）。
第三位图（D-IsPrefixKey）每个节点仅包含一位。
该位指示通向该节点的前缀是否也是
有效密钥。例如，在图2中，级别1的第一个节点的f为
它的前缀。同时，“ f”也是存储在特里树中的键。表示
在这种情况下，必须设置此子节点的D-IsPrefixKey位。
最后的字节序列（D值）存储固定长度的值
键所映射的（例如，指针）。这些值串联在
级别顺序：与三个位图相同。
树导航使用数组查找以及排序和选择操作。
我们将位置pos上的位序列bs上的rank1 / select1表示为
rank1 / select1（bs，pos）。令pos为D标签中的当前位位置。
给定pos，其中D-HasChild [pos] = 1，以遍历trie
D-ChildNodePos（pos）= 256×rank1（D-HasChild，pos）计算
第一个子节点的位位置。为了向上移动树，D ParentNodePos（pos）= select1（D-HasChild，?pos/256?）计算
父节点的位位置。访问值，给定pos
其中D-HasChild [pos] = 0，D-ValuePos（pos）= rank1（D-Labels，
pos）-rank1（D-HasChild，pos）+ rank1（D-IsPrefixKey，?pos/256?）-1
给出查找位置。

2.3 LOUDS-稀疏
如图2下半部分所示，LOUDS-Sparse编码为
节点使用四个字节或位序列。编码的节点是
然后按级别顺序连接。
第一个字节序列S-Labels记录所有分支标签
对于每个特里节点。例如，第2级的第一个非值节点
图2中有三个分支。 S标签包含其标签r，s和
按顺序排列。我们表示通向节点的前缀为
也是有效的密钥，在密钥的开头使用特殊字节0xFF
节点（这种情况由LOUDS-Dense中的D-IsPrefixKey处理）。对于
例如，在图2中，第3级的第一个非值节点的“ fas”为
它的传入前缀。由于“ fas”本身也是存储的密钥，因此该节点
将0xFF添加到S-Labels作为第一个字节。因为特殊字节
总是出现在节点的开头，可以区分
来自真实的0xFF标签。
第二个位序列（S-HasChild）每个包含一个位
S-Labels中的字节，以指示子分支是否继续（即，
指向子Trie）或终止（即指向一个值）。服用
以图2中2级最右边的节点为例，因为
标记为i的分支指向子trie，其中的对应位
S-HasChild已设置。另一方面，标为y的分支指向
值。其S-HasChild位被清除。
第三位序列（S-LOUDS）也每个包含一个位
S标签中的字节。 S-LOUDS表示节点边界：如果标签是
首先在节点中，将其S-LOUDS位置1。否则，该位被清除。
例如，在图2中，级别2的第一个非值节点具有
三个分支，并在S-LOUDS序列中编码为100。
最终字节序列（S值）的组织方式与
LOUDS-Dense中的D值。
LOUDS-Sparse上的树导航如下：移动
向下，S-ChildNodePos（pos）= select1（S-LOUDS，rank1（S HasChild，pos）+1）;向上移动，S-ParentNodePos（pos）= select1（S HasChild，rank1（S-LOUDS，pos）-1）;访问值S-ValuePos
（pos）= pos-rank1（S-HasChild，pos）。

2.4 LOUDS-DS和操作
LOUDS-DS是混合式特里，其中上层被编码
使用LOUDS-Dense，使用较低级别的LOUDS-Sparse。的
上层和下层之间的分界点可调整为
贸易表现和空间。 FST保持上层人数
较小，而支持LOUDS-Sparse提供的空间效率。
我们在LOUDS-Sparse和LOUDS Dense之间保持大小比R，以确定级别之间的分界点。假设
特里有H级。令LOUDS-Dense-Size（l）为0≤l≤H
LOUDS密集编码级别的大小，最大为l（不包括在内）。让
LOUDS-Sparse-Size（l），表示LOUDS-Sparse编码的大小
级别从1（含）到H。截止水平定义为最大
l使得LOUDS-Dense-Size（l）×R≤LOUDS-Sparse-Size（l）。减少R会导致更多级别，从而使性能胜于空间。我们
使用R = 64作为默认值。
LOUDS-DS有效地支持三个基本操作：
?ExactKeySearch（key）：如果key存在，则返回key的值（或
否则为NULL。
?LowerBound（key）：返回指向键值的迭代器
对（k，v），其中k按字典顺序最小，满足k≥键。 ?MoveToNext（iter）：将迭代器移至下一个键值。
在LOUDS-DS上进行点查询的方法是先搜索
大声-密集级别。如果搜索未终止，则继续
进入LOUDS稀疏级别。的高级搜索步骤为
无论采用哪种编码机制，每个级别都是相似的：首先，
在标签序列中的当前节点范围内搜索tar获取关键字节。如果密钥字节不存在，终止并返回
空值。否则，检查HasChild位序列中的相应位。如果该位为1（即分支指向子节点），
计算标签序列中子节点的起始位置
并继续下一个阶段。否则，返回对应的
值序列中的值。我们预先计算两个合计值
基于LOUDS-Dense级别：节点数和数量
已设置HasChild位。使用这两个值，LOUDS-Sparse可以
就像整个特里树都用LOUDS-Sparse编码一样进行操作。
范围查询使用类似于该点的高级算法
查询实现。执行LowerBound时，代替
在标签序列中进行精确搜索，算法搜索
对于最小标签≥目标标签。移至下一个
键，光标从当前叶子标签位置开始并移动
向前。如果在节点内找到另一个有效标签l，则算法会在以l为根的子树中找到最左侧的叶子关键字。如果
光标击中了节点边界，算法移动了光标
直到父节点中的相应位置。

我们在迭代器中包含每级游标，以最大程度地减少
相对昂贵的“向父母移动”和“向孩子移动”电话，
需要排名和选择操作。这些游标记录跟踪
从根到叶（即标签序列中的每级位置）
当前的密钥。由于LOUDS-DS的级别顺序布局，
每个级别光标仅顺序移动而不会跳过项目。
使用此属性，可以在LOUDS-DS中实现范围查询
有效率的。每个级别光标都通过其上级光标的“移动到子代”调用进行一次初始化。之后，范围查询
此级别的操作仅涉及光标移动，即
缓存友好且快速。第4部分显示了FST中的范围查询
比基于指针的尝试更快。
可以通过一次扫描键值列表来构建LOUDS-DS。

2.5空间与性能分析
给定一个n节点的特里，LOUDS-Sparse使用8n位进行S标签，n位
对于S-HasChild，n位用于S-LOUDS，总共10n位（加上辅助位用于等级和选择）。参考第2.1节，信息理论下限（Z）约为9.44n位。虽然
LOUDS-Sparse占用的空间接近于信息理论
从技术上讲，LOUDS-Sparse只能在紧凑的分类方案中归类为紧凑型，而不是简洁的，因为
LOUDS-Sparse占用O（Z）空间（尽管乘数很小），而不是Z + o（Z）。但是，实际上，FST小于其他
简洁的尝试（请参阅第4.1.2节）。
LOUDS-Dense的大小受比率R的限制，以确保
不会影响LOUDS-DS的整体空间效率。值得注意的是
LOUDS-Dense并不总是比LOUDS Sparse消耗更多的空间：如果节点的扇出大于51，则只需花费较少的位即可
使用前者代替后者来表示节点。由于这样
节点在trie的上层很常见，增加了LOUDS-Dense
在LOUDS-Sparse之上通常可以提高空间效率。
对于点查询，需要在每个LOUDS-Dense级别进行搜索
在位向量D-HasChild上进行两次数组查找以及排序操作；
在每个LOUDS-Sparse级别进行搜索都涉及标签搜索
子例程，以及分别对S-HasChild和S LOUDS进行排名和选择操作。因此，主要操作是等级
并在LOUDS-Sparse上选择所有位向量和标签搜索
水平。接下来，我们描述这些关键操作的优化。

2.6优化
我们专注于三个最关键的操作：排名，选择和
标签搜索。因为LOUDS-DS中的所有位序列都需要
排名或选择支持，但不能同时获得两者，我们将获得灵活性
分别优化排名和选择结构。我们提出一个
性能细分以在第4.1.3节中显示其效果。
秩。图3（左半部分）显示了我们的轻量级排名结构。
取代了Poppy [58]中的三个LUT（查找表）级别，
我们只包括一个级别。位向量被分成大小为B（位）的固定长度基本块。每个基本块都拥有一个32位
存储了起点的预先计算的排名的排名LUT中的条目
块的位置。例如，在图3中，
排名LUT为7，这是前两个的1的总数
块。给定位i，等级1（i）= LUT [?i/B?] +（popcount
从位（?i/B?×B）到位i），其中popcount是内置CPU
指令。例如，要计算图3中的rank1（12），我们首先
在等级LUT中查找插槽?12/5?= 2并得到7。我们计算1
在剩余的3位中（位?12/5?×5 = 10至位i = 12）使用
popcount指令并获得2。因此，最终结果为7 + 2 = 9。
我们对LOUDS-Dense和LOUDS Sparse使用不同的块大小。在LOUDS-Dense中，我们通过设置
B = 64，以便在每个等级查询中最多调用一个popcount。
尽管这种密集采样会给位向量带来50％的开销，但由于大部分
特里使用LOUDS-Sparse编码，我们将B = 512设置为
一个块适合一个缓存行。 512位块仅需6.25％
在保持高性能的同时为LUT提供了额外的空间[58]。
选择。图3的右半部分显示了我们的轻量选择
结构体。选择结构是一个简单的LUT（每项32位）
它为样本查询存储了预先计算的答案。对于
例如，在图3中，因为采样率S = 3，
LUT中的条目存储3×2 = 6th（从零开始）的位置
设置位8。给定位位置i，select1（i）= LUT [i / S] +
（从位置LUT [i / S]开始选择第（i?i/ S×S）个设置位

• 1）+1。例如，要计算select1（8），我们首先查找插槽
  LUT中的8/3 = 2并得到8。然后选择（8?8/ 3×3）= 2nd
  通过二进制搜索设置从位置LUT [8/3] +1 = 9）开始的位
  在第三基本块中使用popcount。该选择等于1。
  select1（8）的最终结果是8 + 1 + 1 = 10。

在我们的情况下，采样效果很好，因为
需要选择支持的LOUDS-DS是S-LOUDS，这相当
密集（通常设置了17-34％的位），并且具有相对均匀的
设置位的分布（每256位中至少有一个设置位）。
这意味着选择之后剩余的位的复杂性
咨询抽样答案是不变的（需要在
（最多256S位）并且速度很快。默认采样率S设置为
64，可提供良好的查询性能，但仅产生9-17％的费用
本地空间开销（总计1-2％）。
标签搜索。大多数简洁的Trie实现都是线性搜索
序列中的标签。这是次优的，尤其是当
节点扇出很大。尽管二进制搜索可以提高性能，但是最快的方法是使用矢量指令。我们使用128位
SIMD指令，用于在LOUDS-Sparse中执行标签搜索。
我们首先通过计算S-LOUDS比特序列中节点的起始位置后连续的0来确定节点的大小。然后我们
将节点边界内的标签分成128位的块，
每个包含16个标签，并执行组相等性检查。这个
搜索需要使用128位最多16个SIMD相等性检查
SIMD指令。我们在第4节中的实验表明，更多
超过90％的trie节点的大小小于8，这意味着
标签搜索仅需要进行一次SIMD相等性检查。
预取。在我们的FST实施中，预取是最重要的
在切换到LOUDS-DS中的不同位/字节序列之前调用时很有用。因为LOUDS-DS中的序列
有位置对应，当搜索位置在一个
确定顺序，其他顺序中的相关地址可以
计算并预取以备后用。

3个成功的范围过滤器
在使用FST构建SuRF时，我们的目标是平衡低误报率。
过滤器所需内存的正速率。关键思想是
使用截短的特里;也就是说，删除较低级别的特里和
将其替换为从密钥中提取的后缀位（可以是密钥
本身或密钥的哈希值）。我们介绍了SuRF的四个变体。
我们描述了它们的特性以及它们如何保证单面
错误。当前的SuRF设计是静态的，需要完全重建以
插入新密钥。我们在附录A中讨论了处理更新的方法。
3.1基本SuRF
FST是基于Trie的索引结构，用于存储完整密钥。作为一个
过滤器，FST是100％准确的；缺点是，全部
结构可以很大。在许多应用中，过滤器必须适合内存
以保护对慢速存储中存储的数据结构的访问。这些
应用程序无法提供完整密钥的空间，因此
必须以空间精度为代价。
SuRF的基本版本（SuRF-Base）存储最小长度的密钥前缀，以便它可以唯一地标识每个密钥。
具体来说，SuRF-Base仅为每个密钥存储一个额外的字节
超出共享前缀。图4显示了一个示例。代替
存储完整密钥（“ SIGAI”，“ SIGMOD”，“ SIGOPS”），SuRF-Base
通过仅包含共享前缀（'SIG'）来截断完整Trie
并为每个键（“ C”，“ M”，“ O”）再分配一个字节。
以这种方式修剪Trie会影响过滤器空间和准确性。
与布鲁姆过滤器的键是散列的不同，
SuRF-Base取决于存储的密钥的分布。因此，
SuRF-Base的大小在理论上没有上限。从经验上讲，SuRF-Base对于64位仅使用每个密钥10位（BPK）
电子邮件的随机整数和14 BPK，如第4.2节所示。
直觉是，SuRF-Base构建的特里树通常有一个
平均扇出F>2。当F = 2（例如完整的二进制trie）时，
节点数是键的两倍。因为FST（LOUDS-Sparse是
精确）使用10位编码一个trie节点，SuRF-Base的大小为
F> 2时小于20 BPK

过滤精度由误报率（FPR）来衡量，定义为FP
FP + TN，其中FP是误报的数量，而
TN是真实负数的数量。 SuRF-Base中的误报
当不存在的查询关键字的前缀重合时发生
带有存储的键前缀。例如，在图4中，查询键
“ SIGMETRICS”会在SuRF-Base中引起误报。 SuRF Base中的FPR取决于存储和查询的密钥的分布。
理想情况下，如果两个发行版是独立的，则SuRF-Base的FPR
由N·256 * Hmin限制，其中N是存储的密钥数
Hmin是最小叶高。但实际上，查询
密钥几乎总是与存储的密钥相关。例如，
如果SuRF-Base存储电子邮件地址，则查询关键字很可能是
相同的类型。我们在第4.2节中的结果表明，SuRF-Base会导致
整数密钥的FPR为4％，电子邮件密钥的FPR为25％。改善
FPR，我们包括以下三种主要的后缀形式
允许SuRF更好地区分存储的键前缀。
3.2具有散列键后缀的SuRF
如图4所示，带有散列键后缀的SuRF（SuRF-Hash）
在SuRF-Base的每个键中添加一些哈希位以降低FPR。让H
是哈希函数。对于每个密钥K，SuRF-Hash存储n（n
是固定的）FST的值数组中的H（K）的最低有效位（即
在SuRF-Base中为空）。当一个键（K′
）查找到一片叶子
SuRF-Hash节点提取H（K'）的n个最低有效位，然后
对关联的存储的哈希位执行相等性检查
与叶节点。每个密钥使用n个哈希位可确保
SuRF-Hash的点查询FPR小于2×n
（部分哈希
碰撞概率）。即使SuRF-Base的点查询FPR
是100％，在SuRF-Hash中每个密钥只有7个哈希位可提供127?1％
点查询FPR。 4.2.1节中的实验表明SuRF-Hash
仅需要2至4个散列位即可达到1％FPR。
SuRF-Hash中的多余位无助于范围查询，因为
他们不提供按键的订购信息。

3.3具有真实键后缀的SuRF
具有实键后缀（SuRF-Real）的SuRF代替哈希位
紧随存储的密钥前缀之后的n个密钥位。图4显示了当n = 8时的示例。SuRF-Real包括下一个
每个键的字符（“ I”，“ O”，“ P”）以提高键的可区分性：例如，不再查询“ SIGMETRICS”
导致误报。与SuRF-Hash不同，点和范围
查询受益于真实的后缀位，以减少误报。
对于点查询，实后缀位的使用方式与
哈希后缀位。对于范围查询（例如，移至下一个键

K），当到达叶节点时，SuRF-Real比较存储的
在相应的查询关键字的后缀位s到关键位ks
位置。如果ks≤s，则迭代器指向当前密钥；否则，迭代器指向当前密钥。除此以外，
它前进到Trie中的下一个键。
尽管SuRF-Real改善了点和范围的FPR
查询时，需要权衡的是使用实键作为后缀位不能
提供与使用散列位一样好的FPR，因为分布
存储的键和查询键之间的相关性减弱
真实后缀位的可区分性。

3.4具有混合键后缀的SuRF
带有混合键后缀的SuRF（SuRF-Mixed）包括一个组合
哈希键和真实键后缀位的集合。相同键的后缀位
连续存储，以便可以通过以下方式获取两个后缀
单个内存引用。两种后缀类型的长度均为
可配置的。 SuRF-Mixed提供了混合点的完整调谐范围（SuRF Hash和SuRF-Real是两个极端）。
范围查询工作负载。
3.5操作
我们总结了如何使用以下方法实现SuRF的基本操作
FST。关键是要保证单方面错误（没有误报）。
build（keyList）：根据给定的键列表构造过滤器。
result = lookup（k）：对k执行点查询。如果k返回真
可能存在（可能是假阳性）；错误保证不存在。
此操作首先在FST中搜索k。如果搜索终止但没有到达叶子，则返回false。如果搜索达到
一片叶子，在SuRF-Base中返回true。在其他SuRF变体中，获取
存储叶节点的键后缀ks并执行相等性检查
针对根据后缀类型从k中提取的后缀位
如3.2至3.4节所述。

iter，fp_flag = moveToNext（k）：返回指向
最小密钥≥k。迭代器支持检索下一个
和过滤器中的上一个键。此操作在FST上执行下界搜索，以到达叶节点。如果是一个近似值
出现在搜索中（即，特定级别的密钥字节不存在，并且必须移至下一个有效标签），然后
函数将fp_flag设置为false并返回当前的迭代器。
否则，k的前缀与存储的密钥的前缀匹配（k'
） 在里面
特里。 SuRF-Base和SuRF-Hash没有辅助后缀位
可以确定k和k'之间的顺序
;他们必须设置
fp_flag为true并返回指向k'的迭代器
。 SuRF-Real和
SuRF-Mixed包含实后缀位k'r
叉子'
进一步比较
对应于k的相应后缀位kr。如果k'r> kr，fp_flag =
false并返回当前的迭代器；如果k'r = kr，fp_flag = true并且
返回当前的迭代器；如果k'r <kr，fp_flag = false并返回
高级迭代器（iter ++）。

count，low_fp_flag，high_fp_flag = count（lowKey，highKey）：返回
[lowKey，highKey]中包含的键数。 low_fp_flag
和high_fp_flag表示可能过度计算每个
边界键的数量（当边界键的前缀匹配时
存储的密钥，SuRF无法确定边界密钥是否应
计入在内）。此操作执行moveToNext
在lowKey上，必要时设置low_fp_flag。然后它前进
迭代器并递增计数，直到由指向的键k'
迭代器大于或等于highKey。如果k′
是的前缀
highKey，设置high_fp_flag。最后，返回计数。
4 FST和SURF微型基准
在本节中，我们首先评估SuRF及其基础FST数据
使用内存中的微基准测试的结构，可以全面了解过滤器的优缺点。
第6节创建了一个示例应用场景并进行了评估
RocksDB中的SuRF，具有端到端系统测量功能。
雅虎！云服务基准（YCSB）[21]是一种工作负载
生成工具，对大型云服务进行建模。我们使用其默认工作负载C和E生成点和范围查询。我们测试
两种代表性的密钥类型：生成的64位随机整数
YCSB和电子邮件地址（主机反向，例如“ com.domain@foo”）
从实际数据集中绘制（平均长度= 22个字节，最大
长度= 129个字节）。我们运行实验的机器
有两个Intel Xeon E5-2680v2 CPU @ 2.80 GHz，4×32 GB RAM。
实验在单线程上运行。我们进行每个实验
3次并报告平均结果。由于方差很小，因此我们省略误差线。

4.1 FST评估
我们分三个步骤评估FST。首先，我们将FST与三个
最先进的基于指针的索引结构。我们使用等价
曲线展示了FST在性能空间权衡方面的相对优势。其次，我们将FST与两个备选方案进行了比较
特里实现。我们证明FST快4-15倍，而
使用更少的内存。最后，我们给出了性能细分
第2.6节中介绍的我们的优化技术。
我们通过将排序后的密钥列表批量加载到其中来开始每个实验
索引。该列表包含5000万个整数键和
2500万个电子邮件密钥条目。我们报告平均吞吐量
索引上的10M点或范围查询。 YCSB默认范围
查询简短：大多数查询扫描50-100个项目，访问权限
模式遵循Zipf分布。这里的平均查询延迟
指吞吐量的倒数，因为我们的微基准测试
在单个线程中串行执行查询。对于所有索引类型，
报告的内存号不包括该值占用的空间
指针。

4.1.1 FST与基于指针的索引。我们检查以下内容
在我们的测试框架中索引数据结构：
?B + tree：这是数据库系统中最常用的索引结构。我们使用快速的STX B +树[18]与
FST。为了获得最佳的内存性能，将节点大小设置为512字节。我们仅使用固定长度的密钥（即64位整数）进行了测试。
?ART：自适应基数树（ART）是最新的索引
为内存数据库设计的结构[37]。自适应ART
根据分支从四种不同的节点布局中选择
密度以获得更好的缓存性能和空间效率。
?C-ART：我们通过构建一个
纯ART实例并将其转换为静态版本[57]。
ART，C-ART和FST在此仅存储唯一的键前缀
如3.1节所述进行实验。图5显示了比较结果。每个子图都绘制了四个位置（三个用于
电子邮件密钥）在性能空间（延迟与内存）中的索引
地图。我们观察到FST是所有情况下最快的选择之一
同时占用更少的空间。为了更好地理解这种权衡，我们
定义成本函数C = Pr S，其中P代表绩效
（延迟），S表示空间（内存）。指数r表示P和S之间的相对重要性。r> 1表示
该应用程序对性能至关重要，并且0 <r <1表示
除此以外。我们定义“差异曲线”为一组点
具有相同成本的性能空间图。我们画
使用成本函数C = PS（r = 1）的图5中的等成本曲线，
假设在性能和空间之间取得平衡。我们观察到
在所有情况下，FST的成本最低（即效率最高）。为了
第二名（C-ART）的费用与
例如第一个子图，成本函数中的r必须为6.7，
表示对性能的极端偏爱。

4.1.2 FST与其他简洁的尝试。我们将FST与
以下替代方法：
?tx-trie：这是一个开源的简洁trie实现
基于LOUDS [1]。它的设计类似于LOUDS-Sparse，但
没有2.6节中的任何优化。
?PDT：路径分解树[32]是基于DFUDS的最新成功树实现（请参见第7节）。太平洋夏令时
使用路径分解技术重新平衡特里
实现良好的延迟并减少空间。
我们评估点查询的性能和内存
整数和电子邮件密钥工作负载。这三个尝试都存储完整
键（即包括唯一的后缀）。图6显示FST为
比tx-trie快6–15倍，比PDT快4–8倍，并且更小
比两者。尽管tx-trie与以下用户共享LOUDS-Sparse设计
FST，如果没有LOUDS-Dense的性能提升，它的速度会变慢
和其他优化。我们还注意到性能差距
PDT和FST之间的冲突减少了电子邮件的工作量，因为
键的长度变化较大，PDT的路径分解
帮助重新平衡特里。

4.1.3性能细分。接下来，我们将分析这些性能测量结果，以更好地了解使FST快速运行的原因。
图7显示了两种情况下点查询的性能细分
整数和电子邮件密钥工作负载。我们的基线特里是使用
仅LOUDS-Sparse以Poppy [58]为排名，然后选择支持。
“ + LOUDS-Dense”表示使用
改为LOUDS-Dense，从而完成LOUDS-DS设计。
“ + rank-opt”，“ + select-opt”，“ + SIMD-search”和“ + prefetching”对应于2.6节中描述的每个优化。我们
观察到由于LOUDS-DS设计，FST速度很快。将LOUDS-Dense引入Trie的高层提供了
显着的性能提升，而空间成本却可以忽略不计。其余的部分
优化的结果使整体查询延迟减少了3–12％。

4.2 SuRF评估
评估SuRF的三个最重要指标
误报率（FPR），性能和空间。数据集
是100M个64位随机整数密钥和25M个电子邮件密钥。在里面
实验中，我们首先使用一半的
随机选择的数据集。然后我们执行10M点，范围或
过滤器上的混合查询（50％点和50％范围，交错）。
查询关键字（K）从整个数据集中得出
到YCSB工作负载C，以便大约50％的查询返回false。
我们测试了两种查询访问模式：统一和Zipf分布。
我们只显示Zipf分布结果，因为观察
从这两种模式都是相似的。对于64位随机整数键，
范围查询为[K + 2
37
，K + 2
38]，其中46％的查询
返回true。对于电子邮件密钥，范围查询为[K，K（最后一个字节
++）]（例如[org.acm @ sigmod，org.acm @ sigmoe]），其中52％
查询返回true。我们使用Bloom过滤器实现
RocksDB2。

4.2.1误报率。我们首先研究SuRF的误报
费率（FPR）。 FPR是误报与错误总和的比率
正面和负面。图8显示了FPR比较
在SuRF变体和Bloom滤光片之间通过改变
过滤器。布隆过滤器仅出现在点查询中。注意
SuRF-Base每个密钥在电子邮件中消耗14（而不是10）位
关键工作量。这是因为电子邮件密钥共享更长的前缀，
这增加了SuRF中的内部节点数量（请记住，
SuRF节点使用10位进行编码）。 SuRF-Mixed配置为
具有相同数量的散列和实数后缀位。
对于点查询，尽管SuRF-Hash可以捕获，但在大多数情况下，Bloom过滤器的FPR低于相同大小的SuRF变体。
随着每个密钥位数的增加而迅速增加，因为每个
添加的哈希位将FPR减少了一半。 SuRF-Real中的实数后缀位
对于点查询，它们通常不如哈希位有效。对于
范围查询，只有SuRF-Real可从增加过滤器尺寸中受益
因为SuRF-Hash中的哈希后缀不提供排序
信息。电子邮件密钥中的SuRF-Real曲线的形状
工作量（即后4个后缀位比前4个后缀位在识别误报时更有效）是因为ASCII编码
字符。对于混合查询，增加后缀数
SuRF-Hash中的比特产生的FPR收益递减，因为它们
不帮助范围查询。 SuRF混合（具有相同数量的
散列和实数后缀位）可以提高SuPR-Real的FPR
一些后缀长度的配置。实际上，SuRF-Real是一个极端
在SuRF-Mixed的调谐范围内这表明调整比例
哈希后缀的长度和实际后缀的长度之间可以
在混合点和范围查询工作负载中改善SuRF的FPR。
我们还观察到SuRF变体具有较高的FPR
电子邮件关键工作负载。这是因为数据集中的电子邮件密钥
非常相似（即密钥分布密集）。两个电子邮件密钥
通常在最后一个字节上有所不同，或者一个可能是另一个的前缀。如果
其中一个键显示在过滤器中，另一个键则不显示，
在SuRF-Base上查询丢失的密钥可能会产生错误
积极的。 SuRF-Base的高FPR显着降低了
如图所示，添加后缀位。

4.2.2性能。图9显示了吞吐量比较。
SuRF变体的运行速度可与Bloom滤光片相媲美
借助第2.6节中提到的LOUDS-DS设计和其他性能优化，可以处理64位整数密钥工作负载。
对于电子邮件密钥，SuRF变体比Bloom过滤器慢
由于搜索/遍历长前缀的开销
在特里。布隆过滤器的吞吐量会随着每个密钥的位数的增加而降低，因为较大的布隆过滤器需要
更多哈希探针。 SuRF变量的吞吐量不
遭受增加后缀位的数量，因为只要
后缀长度小于64位，请检查后缀位
仅涉及一个内存访问和一个整数比较。的
添加第一个后缀时，图中的（轻微）性能下降
位（即整数键从10到11，电子邮件为14到15）
键）演示了额外的内存访问开销
获取后缀位。 SuRF中的范围查询比点慢
查询，因为每个查询都需要向下浏览
特里（没有提前退出）。另外，施工速度
SuRF与Bloom过滤器相当（图中未显示）
因为它们可以建立在对已排序输入键的单次扫描中。
实验中的一些高级总结：（1）SuRF可以
布隆过滤器无法执行范围过滤； （2）如果tar get应用程序仅需要具有中等FPR的点查询过滤
要求，布隆过滤器通常比SuRF更好。
（3）对于点查询，SuRF-Hash可以提供类似的理论
保证FPR作为布隆过滤器，而SuRF-Real的FPR
取决于密钥分配； （4）调和SuRF-Mixed以进行混合
点和范围查询，应该从SuRF-Real开始，因为
实际后缀位对两种查询类型均有利，然后逐渐替换
它们带有哈希后缀，直到FPR达到最佳。
第6节显示了在以下情况下对SuRF的评估
端到端应用程序（即RocksDB），其中SuRF可以提高速度
通过保存I / O进行点和范围查询。下一节介绍
在RocksDB中使用SuRF的方式。

5示例应用程序：ROCKSDB
我们将SuRF与RocksDB集成在一起，以替代其Bloom
过滤。图10说明了RocksDB的日志结构合并树
建筑。传入的写入会进入MemTable，并附加到日志文件（忽略）以保持持久性。当MemTable
已满（例如，超过4 MB），引擎会对其进行排序，然后将其转换为
成为级别0一部分的SSTable。SSTable包含已排序的
键值对，并分为固定长度的块匹配
最小的磁盘访问单元。为了定位块，RocksDB存储了
“重新开始点”（一个字符串，该字符串≥当前块中的最后一个键
和<下一个块中的第一个键）作为每个块的索引。
当级别的大小达到阈值时，RocksDB将选择一个
此级别的SSTable并将其合并到下一个级别的SSTable中
具有重叠的键范围。此过程称为压缩。
除0级外，同一级别的所有SSTable都具有脱节密钥
范围。换句话说，对每个级别的键进行全局排序
≥1.与全局表缓存结合使用时，此属性可确保
对于级别≥1的条目，每个级别最多可以读取一个SSTable。
为了促进搜索并减少I / O，RocksDB包括
两种类型的缓冲区高速缓存：表高速缓存和块高速缓存。
表缓存包含有关打开的SSTable的元数据，而
块缓存包含最近访问的SSTable块。块是
也由OS页面缓存隐式缓存。当压缩为
打开后，操作系统页面缓存包含压缩块，而
块缓存始终存储未压缩的块。
我们修改了RocksDB的点（Get）和范围（Seek，Next）查询
使用SuRF的实现。我们还实现了一个新的近似计数查询，该查询返回键范围内的条目数。

近似计数可能会使删除和修改条目过多，因为它无法区分更新/删除记录
从插入记录。如果数据集是静态的，则计数是准确的。
这表明SuRF支持除过滤之外的功能。
图11显示了Get，Seek和Count的执行路径
RocksDB中的查询。 Next的核心算法类似于Seek。我们
使用颜色突出显示通过使用滤镜可能减少的I / O。
如果请求块，则蓝色框中的操作可以触发I / O。
没有缓存。过滤器操作在红色框中。如果盒子是
虚线，检查（通过从SSTables中获取实际的键）
由于误报，可能需要使用边界键。
对于Get（key），SuRF的用法与Bloom过滤器完全相同。具体来说，RocksDB逐级搜索。在每个级别，RocksDB
通过表缓存中的块索引找到候选SSTable和块（级别0可能有多个候选）。对于每个
候选SSTable，如果有过滤器可用，则RocksDB查询过滤器
首先，仅当过滤结果为肯定时，才获取SSTable块。
如果过滤结果为负，则跳过候选SSTable并
不必要的I / O被保存。
对于Seek（lk，hk），如果未指定hk（高键），则将其称为
打开寻求。否则，我们称其为“封闭寻求”。要实现Seek（lk，
hk），RocksDB首先收集各个级别的候选SSTable
通过在块索引中搜索lk（低键）。
在没有SuRF的情况下，RocksDB会检查每个候选SSTable和
获取包含最小密钥≥lk的块。 RocksDB
然后比较候选键并找到全局最小
密钥K≥lk。

对于Open Seek，查询成功并返回
迭代器（每级至少一个）。对于封闭式寻求，
RocksDB对hk进行额外检查：如果K≤hk，则
查询成功；否则查询将返回无效的迭代器。
但是，使用SuRF，而不是获取实际的块，
RocksDB可以通过在SuRF上形成一个moveToNext（lk）查询来避免每个I / O以获得每个SSTable的候选键。
每个SSTable。如果查询成功（例如，Open Seek或K≤hk），
RocksDB会从所选的SSTable中精确地获取一个块
包含全局最小值K。如果查询失败（即K> hk），则否
涉及I / O。由于SuRF的moveToNext查询仅返回一个
密钥前缀Kp，还需要进行三项检查以确保
正确性。首先，如果moveToNext查询设置了误报
标志，RocksDB必须从SSTable获取完整的密钥K
判断K≥lk。如果未设置，则RocksDB将获取
K之后的下一个键。第二，如果Kp是hk的前缀，则完整键
还需要K来验证K≤hk。如果不是，则当前的SSTable为
跳过了。第三，多个键前缀可以捆绑在一起。在
在这种情况下，RocksDB必须获取其相应的完整密钥
从SSTable块中查找全局最小的块。尽管
三个潜在的附加检查，在RocksDB中使用SuRF可以减少
每个Seek（lk，hk）查询的平均I / O，如第6节所示。
为了说明SuRF如何使范围查询受益，假设
RocksDB实例具有SSTables的三个级别（LN，LN N1，LN N2）
在磁盘上。 LN的SSTable块包含键2000、2011、2020
以2000作为块索引； LN N1有一个SSTable块，其中包含键2012、2014、2029，其中2012为块索引；和LN N2
具有包含键2008、2021、2023和2008的SSTable块
作为块索引。考虑范围查询[2013，2019]。使用
仅块索引，RocksDB必须从磁盘读取所有三个块
验证2013年至2019年之间是否有密钥。
SuRFs消除了LN和LN N2中的块，因为用于
那些SSTables将返回false以查询[2013，2019]高
可能性。 I / O的数量可能会从3个减少到1个。
Next（hk）与Seek（lk，hk）类似，但是每个级别的迭代器
已经初始化。 RocksDB必须仅增加迭代器
指向当前键，然后重复“查找全局
Seek中的“最小”算法。

对于Count（lk，hk），RocksDB首先对lk执行一次Seek初始化
迭代器，然后计算lk和之间的项目数
hk每个级别。如果没有SuRF，DBMS将通过以下方式计算计数：
扫描SSTable中的块，直到密钥超过上限
界。如果有SuRF，则通过迭代进行计数
在过滤器中。与Seek中一样，需要类似的边界键检查
以避免偏离一错误。计数而不是扫描磁盘块
使用SuRF最多需要两个磁盘I / O（一个可能的I / O用于
每个边界）。然后返回累计计数。
6系统评估
时间序列数据库通常使用RocksDB或类似的LSM树
存储引擎的设计。例如InfluxDB [12]，
QuasarDB [8]，LittleTable [48]和基于Cassandra的系统[7，36]。
因此，我们创建了一个综合的RocksDB基准，以对由分布式传感器生成的时间序列数据集进行建模，并将其用于
端到端性能测量。我们模拟了2K传感器
记录事件。每个事件的关键是一个128位的值，包括一个64位的时间戳和一个64位的传感器ID。的
记录中的关联值长度为1 KB。每个的发生
每个传感器检测到的事件遵循泊松分布，其中
预期频率为每0.2秒1个。每个传感器运行
持续10K秒，并记录约5万个事件。起始时间戳
在最初的0.2秒内随机生成每个传感器的。
原始记录的总大小约为100 GB。
我们的测试框架支持以下数据库查询：
？点查询：给定时间戳记和传感器ID，返回
记录是否有事件。

？开放式查询：给定开始时间戳，返回指向该时间之后最早事件的迭代器。
？封闭式查询：给定时间范围，确定是否
在这段时间内发生的任何事件。如果是，则返回
迭代器指向范围中最早的事件。
我们的测试机器具有Intel Core i7-6770HQ CPU，32 GB RAM，
和Intel 540s 480 GB SSD。我们使用Snappy（RocksDB的默认设置）
用于数据压缩。生成的RocksDB实例具有四个级别（包括级别0），并使用52 GB的磁盘空间。我们配置了3
RocksDB根据Facebook的建议[25，26]。
我们使用不同的过滤器选项创建了四个RocksDB实例：
（1）无过滤器，（2）布隆过滤器，（3）SuRF-Hash，和（4）SuRF-Real。我们
配置每个过滤器以使用相同数量的内存。盛开
过滤器每个键使用14位。大小相等的SuRF哈希和SuRF Real每个密钥包含4位后缀。我们先用1M预热缓存
对现有键进行统一分布的点查询，以便每个
SSTable被触摸?1000次，并且块索引和过滤器
被缓存。预热后，RocksDB的块缓存和
操作系统页面缓存已满。然后，我们执行5万个应用程序查询，
记录端到端的吞吐量和I / O计数。我们计算
通过将查询计数除以执行时间来获得DBMS的吞吐量，
在I / O计数之前和之后从系统统计信息中读取
执行。查询键（对于范围查询，起始键）
是随机生成的。报告的数字是
三轮。即使RocksDB支持前缀Bloom过滤器，我们
将它们排除在我们的评估之外，因为它们没有提供好处
在这种情况下超过Bloom过滤器：（1）使用任意范围查询
整数没有预定的键前缀，这使得它
很难生成这样的前缀，并且（2）即使键前缀可以
确定，前缀Bloom过滤器始终返回假阳性
用于在缺少键的任何键共享相同前缀的情况下进行点查找
当前密钥，导致较高的误报率。
图12（左两图）显示了点查询的结果。
由于查询关键字是随机生成的，因此几乎所有查询
返回false。查询性能由I / O数量决定：
它们成反比。不包括0级，每个点查询
预计将访问三个SSTable，每个级别一个（表1，
2、3）。如果不使用过滤器，则点查询会产生大约1.5个I / O
根据图12的每个操作，这意味着整个
1级和2级的大约一半可能已缓存。这个
同意典型的RocksDB应用程序设置
两个级别未缓存在内存中[24]。

在点查询中使用过滤器可减少I / O，因为它们可防止不必要的块检索。使用SuRF-Hash或SuRF-Real较慢
比使用Bloom过滤器要好，因为4位后缀不会减少
误报率与布隆过滤器配置一样低（请参阅
第4.2.1节）。 SuRF-Real提供与SuRF-Hash类似的好处
因为密钥分配稀疏。
使用SuRF的主要好处是可以加快范围查询的速度。图12（右两个图）显示使用SuRF-Real可以提高速度
将“公开搜索”查询提高了50％。 SuRF-Real无法进一步改善
因为Open-Seek查询需要读取至少一个SSTable
块，如第5节所述，并且可能会读取SSTable块
发生在数据块不可用的最后一级
缓存。实际上，I / O图（最右侧）表明使用SuRF-Real
将每次操作的I / O数量减少到1.023，接近
最大程度地减少了Open-Seeks的I / O。
图13显示了Closed-Seek的吞吐量和I / O数量
查询。在x轴上，我们以空值控制查询的百分比
通过更改范围大小可以得到结果。事件的泊松分布
来自所有传感器的信号的预期频率为每λ= 105 ns一个。
对于长度为R的区间，范围包含的概率
e÷R /λ没有给出事件
。因此，对于目标百分比（P）
空结果的封闭式查询，我们将范围大小设置为
λln（1P）。例如，对于50％，范围大小为69310 ns。
类似于Open-Seek查询结果，Bloom过滤器不会
帮助范围查询，相当于没有过滤器。但是，使用SuRF Real时，如果有99％的查询，查询速度将提高5倍
返回空。同样，I / O数量支配性能。不带
一个范围过滤器，每个查询都必须获取候选SSTable块
从每个级别确定范围内是否有键。
但是，使用SuRF变体可以避免许多不必要的情况
I / O； RocksDB执行对包含以下内容的SSTable块的读取：
最小键仅当过滤器返回的最小键时
每个级别都属于查询范围。使用SuRF-Real不仅如此
在这种情况下比SuRF-Hash有效，因为真正的后缀位
帮助减少范围边界处的误报。

为了在Seek之后继续扫描，DBMS调用Next并推进迭代器。我们没有观察到性能改善
使用SuRF时用于Next，因为相关的SSTable块是
已经加载到内存中。因此，SuRF主要有助于短距离
查询。随着范围变大，过滤收益将摊销。
RocksDB API不支持近似查询。我们
使用来衡量近似计数查询的性能
LevelDB中的简单原型，发现使用
SuRF与“封闭式”查询的加速类似。 （此结果
基于图11中的执行路径）。我们相信
整合近似值是未来工作的有趣元素
计数（对于静态数据集准确）计入RocksDB或其他
系统更明确地设计用于近似查询。
最后，我们在以下环境中评估了RocksDB：
内存与存储预算比较大。 DBMS将受益
在更严格的约束和/或更大的数据集下，SuRF提供了更多功能。

7相关工作
FST的替代品，用于范围过滤。布隆过滤器[19]
它的主要变体[20、27、45]是紧凑的数据结构，设计用于快速近似成员资格测试。他们广泛
用于存储系统，尤其是LSM树，如
引入，以减少昂贵的磁盘I / O。类似的应用程序可以
在分布式系统中可以减少网络I / O [2，51，56]。
但是，布隆过滤器的不利之处在于它们无法处理
范围查询，因为其哈希不会保留键顺序。
实际上，人们使用前缀Bloom过滤器来帮助回答范围空度查询。例如，RocksDB [6]，LevelDB [3]和
LittleTable [48]将预定义的键前缀存储在Bloom过滤器中，因此
他们可以找到一个空结果查询，如果他们找不到
过滤器中的匹配前缀。与SuRF相比，这种方法
但是，过滤能力较差，灵活性较差。它还需要额外的空间来支持点和范围查询。
自适应范围滤波器（ARF）[14]被引入
Hekaton [23]中的西伯利亚项目，以保护寒冷的数据。 ARF是
覆盖整个密钥空间的简单二进制树（例如，对于64位
整数键，根节点表示范围[0，2
64
-1]及其子项表示[0，2
63
-1]和[2
63
，2
64
-1]）。

每个叶节点表示
在其范围内是否有任何钥匙或绝对没有钥匙。
使用ARF涉及三个步骤：构建完美的Trie，训练样本查询以确定要包含在其中的节点
ARF，然后将经过训练的ARF编码为位序列
以广度优先的顺序是静态的。 ARF与SuRF的不同之处在于
它针对不同的应用程序和可扩展性目标。首先，ARF
行为比通用过滤器更像是缓存。训练
ARF需要有关先前查询的知识。 ARF实例
在特定的查询模式上表现出***r>训练有素。如果查询模式发生变化，则ARF需要重建（即，
解码，重新训练和编码）以保持有效。 ARF运作良好
在西伯利亚项目中，但其工作量假设受到限制
其作为通用范围过滤器的有效性。另一方面，SuRF
不承担任何工作量。可用作布隆过滤器
替换，但具有范围过滤功能，如第6节所示。
此外，ARF的二叉树设计使其难以容纳可变长度的字符串键，因为拆分键会均匀
将父节点的键空间划分为其子节点的键空间为
在长度可变的字符串键空间中定义不正确。相反，
SuRF本机支持Trie设计的可变长度字符串键。最后，ARF在整个水平上执行线性扫描
穿过树。线性查找的复杂性阻止了ARF
从缩放；作者建议将许多小型ARF嵌入
Hekaton的热商店中现有的B树索引，但查找
在单个ARF中，仍然需要进行线性扫描。 SuRF避免线性
通过使用rank＆select导航其内部树结构来进行扫描
操作。我们在附录B中比较了ARF和SuRF。

LSM树。许多现代键值存储都采用日志结构化合并树（LSM-tree）设计[44]，因为它具有较高的写入率
吞吐量和低空间放大。此类系统包含LevelDB [3]，RocksDB [6]，Cassandra [36、52]，HBase [4]，
来自Yahoo Labs的WiredTiger [54]和cLSM [29]。猴子[22]
探索LSM树设计空间并提供调整模型
使LSM树在更新和更新之间达到帕累托最优
给定一定的主内存预算，查找速度。 RocksDB
团队发布了一系列优化（包括前缀Bloom）
滤波器）以减少空间放大率，同时保持可接受的水平
性能[25]。这些优化属于RUM猜想[16]：对于读取，更新和内存，只能优化
两个以第三个为代价。 FST的设计也属于
RUM猜想，因为它以更新效率为代价来快速读取
和小空间。 LSM-trie [55]提高了读写吞吐量
在LevelDB上获取较小的键/值对，但不支持
范围查询。

为什么我们选择LOUDS与替代方案。简洁的树表示通常使用LOUDS（如FST一样）或“平衡括号”
（BP）序列[40]。 BP表示在恒定时间内支持更多的树操作[28、38、41、42、49]，但对于
FST [15]所需的简单“父子”导航。
许多最简洁的尝试[17、32、47]都是基于
结合了LOUDS的第三种简洁树表示
和BP，称为深度一元数列（DFUDS）[17]。
它使用与LOUDS中相同的一元编码，但遍历
与BP中一样，树按深度优先顺序排列。 DFUDS提供了中间立场
介于快速操作和其他功能之间，在
建立一般的简洁尝试。 Grossi和Ottaviano [32]提供了
基于DFUDS的最新精简Trie实现，
我们将在4.1.2节中进行比较。
简洁数据结构的其他系统应用程序。成功案例[13]和后续工作BlowFish [35]是为数不多的
系统研究尝试在通用的分布式数据存储中广泛使用简洁的数据结构。他们存储数据集
使用压缩后缀数组[33]并获得大量空间
储蓄。与其他非压缩系统相比，Succinct和
BlowFish主要通过将更多数据保留在DRAM中来实现更好的查询性能。 FST可以提供类似的好处
当用于大于DRAM的工作负载时。此外，FST确实
即使整个数据集都适合，也不会降低系统速度
DRAM。

8结论
本文介绍了SuRF筛选器结构，该结构支持对单个键和范围以及计数查询的近似成员资格测试。 SuRF建立在新的简洁数据结构上，称为
快速简洁的Trie（FST），每个节点仅需要10位
编码特里。 FST经过设计，具有与基于指针的最新索引相同的性能。 SuRF是记忆
效率高，其空间/误报率可以通过选择
要包含的后缀位数不同。我们已经展示了
广泛的微基准测试表明FST与州相比都有优势
精巧的尝试，以及SuRF在时空中的适合位置
权衡空间。用相同的SuRF替换Bloom过滤器
RocksDB的大小，大大减少了I / O，并通过范围查询的put进行了改进，在最坏的情况下成本适中
查询吞吐量。因此，我们认为SuRF是有前途的
用于优化未来存储系统的技术等。

附录
A 支持更新的扩展内容
如本文所述，SuRF的当前版本以
静态用例，例如在日志结构的合并树中，如所述
在第5节中。对于需要动态使用范围的应用程序
过滤器，可以扩展SuRF以支持更新。为了支持插入，
SuRF可以利用混合索引技术[57]来包括
它前面的小型动态Trie可吸收所有写入并执行
批处理定期合并，因此单个插入的成本为
SuRF被摊销。为了支持删除，SuRF可以添加一个“墓碑”
位数组，每个键一位，以指示该键是否已
是否删除。使用逻辑删除位阵列，删除的成本
SuRF中的内容几乎与查找相同。定期垃圾
需要收集以保持SuRF较小。支持中的更新
SuRF不在本文讨论范围之内，因此我们推迟解决该问题
将来的工作。

B比较ARF和SURF
本节扩展了我们对自适应范围滤波器的讨论
（ARF），请提供实验评估。我们整合了论文作者发表的ARF实施[9]
进入我们的测试框架。我们将ARF的空间限制设置为7 MB
并对SuRF使用4位实数后缀，以便两个过滤器都使用
每个密钥14位。我们使用第4.2节中的YCSB工作负载C设置。但是，我们将数据集缩小10倍，因为ARF
需要大量的内存来进行训练。具体来说，
数据集包含10M个64位整数键（ARF仅支持
固定长度的密钥（最高64位）。我们从中随机选择5M个密钥
数据集并将其插入过滤器。工作量包括
10M Zipf分布范围查询，范围大小为2
40，其中
使大约50％的查询返回false。对于ARF，我们使用20％
（即2M）进行培训，其余则进行评估。
表1比较了ARF的性能和资源使用情况
和SuRF。对于查询处理，SuRF快20倍，快12倍
即使它们的最终滤波器大小相同，也比ARF精确。
此外，ARF需要大量资源用于建筑
和培训：其峰值内存使用量为26 GB，
即使最终的滤镜大小，训练时间约为4分钟
是7 MB。相反，构建SuRF仅使用0.02 GB内存
并在1.2秒内完成。

C多方面的冲浪实验
本节验证SuRF在多核系统上是否可扩展。
我们使用与第4.2节中相同的基于YCSB-C的工作负载。的
数据集包括100M 64位整数密钥。我们使用以下方法构造SuRF
随机选择了一半的密钥（即50M）。然后我们执行100M
YCSB在整个数据集上生成的点查询，有所不同
线程数。查询在整个查询之间平均分配
线程;例如，如果有10个并发线程，则每个线程
将执行1000万个查询。实验在Intel Xeon E5-上运行
2680 v2 @ 2.80 GHz，具有256 KB L2缓存，25 MB L3缓存和
4×32 GB RAM。它具有10个物理核心和20个硬件线程
（启用超线程）。
图14将总吞吐量显示为
线程增加。在不使用超线程的情况下，SuRF可以完美缩放（由于缓存争用而只有一点点偏离）。 SuRF的吞吐量不断提高，即使性能下降
超线程。由于SuRF是只读数据结构且完全无锁，几乎没有锁定，因此可以得到此结果
与许多并发线程争用。我们忽略了可扩展性
范围查询的图形显示相似的结果。
致谢
这项工作得到了美国国家科学基金会的资助
基金会获得CCF-1535821奖，并获得英特尔科学与技术奖
可视云系统技术中心。
本文致力于纪念莱昂·皱纹。
愿他饱受折磨的灵魂安息。