ACM通信

研究突出了

简洁的系列过滤器

作者:张焕辰、林铉泽、维克多·莱斯、大卫·g·安徒生、迈克尔·卡明斯基、金伯利·基顿、安德鲁·帕夫洛
ACM通讯，2021年4月，第64卷第4期，166-173页
10.1145 / 3450262
评论

我们现在简洁的范围过滤器(SuRF)，一种用于近似隶属度测试的快速紧凑的数据结构。与传统的Bloom过滤器不同，SuRF既支持单键查找，也支持常见的范围查询，比如范围计数。SuRF基于一种新的数据结构，称为快速简练Trie (FST)这与最先进的保序索引的性能相匹配，而每个trie节点只消耗10位——接近信息论所需的最小空间。我们的实验表明，在一个广泛使用的数据库存储引擎中，SuRF可以使范围查询速度提高5倍。

回到顶部

1.简介

写优化的日志结构合并(LSM)树¹⁶提供快速写入的通用数据库的流行的底层存储引擎^1，14，18并吸收大量的dbms，如时间序列数据库。^5，17快速查询处理的一个主要挑战是项目可能驻留在不同级别的不可变文件(sstable)中。因此，这些系统中的项检索可能会招致多个昂贵的磁盘I/ o。^16，18

基于树的系统使用Bloom过滤器来“保护”磁盘上的文件，以减少不必要的I/ o数量^{2，3.，17，18}:只有当与之相关联的内存中Bloom过滤器表示查询项可能存在于该文件中时，才会读取磁盘上的文件。Bloom过滤器很适合这个任务。首先，Bloom过滤器快速且足够小，可以驻留在内存中。第二，Bloom过滤器用“片面”错误回答近似成员测试——如果查询项是成员，过滤器保证返回true;否则，过滤器可能会返回false，但也可能导致假阳性。

虽然Bloom过滤器对于单键查找很有用(“SSTable中的键是50吗?”)，但它们不能处理范围查询(“SSTable中是否有40到60之间的键?”)。如果只使用Bloom过滤器，基于LSM树的存储引擎仍然需要为范围查询读取额外的磁盘块。另外，还可以维护一个辅助索引，例如B+Tree，以加速范围查询，但是内存成本将非常大。为了部分解决范围查询的高I/O成本，基于LSM树的设计经常使用前缀布鲁姆过滤器要优化某些固定前缀的查询(例如，“电子邮件以com.foo@开头”)，^2，11，17尽管它们对于更通用的范围查询不灵活。

为了解决这些限制，我们提出苏ccinctR安吉F教师SuRF，一种快速紧凑的数据结构，提供精确匹配过滤、距离过滤和近似距离计数。与Bloom过滤器一样，SuRF保证点和范围成员关系测试出现片面错误。SuRF可以在假阳性率和内存消耗之间进行交换，这种交换对于点查询和范围查询是半独立可调的。

SuRF建立在一种新的高效空间数据结构之上，称为快速简练Trie (FST)．对于整数和字符串工作负载，它的性能与最先进的未压缩索引结构相当，甚至更好。FST每个try节点只消耗10比特，接近信息理论的下限。

SuRF的关键思想是将FST转换为近似(范围)成员滤波器，方法是去除tritry的级别，并用一些后缀位替代它们。这样的位的数量(来自键本身或键的散列(我们将在本文后面讨论)交换空间以减少误报。

我们通过微基准测试来评估SuRF，并在rocksdb(一个广泛使用的数据库存储引擎)中作为Bloom过滤器的替代品。²我们在100GB时间序列数据集上的实验表明，用相同过滤器大小的surf替换Bloom过滤器可以减少I/O。与原始实现相比，这种方法提高了近距离查询(即有一个上界)最多5倍的速度，但由于假阳性率略高，在最差情况点查询吞吐量方面的成本并不高。我们可以通过每个键增加几个位来消除这种性能差距。

回到顶部

2.快速简洁的尝试

SuRF的核心数据结构是快速简练Trie (FST)．FST是一个回答点查询和范围查询的有效的静态try。FST比之前简洁的尝试快4 - 15倍，^6，12实现与最先进的基于指针的索引相当或更好的性能。^8，15，19

FST的设计基于这样一种观察:trie的上层包含很少的节点，但会招致很多访问。较低的级别包含了大多数节点，但相对“较冷”。因此，我们使用简洁语句对try的较低级别进行编码LOUDS-Sparse方案保证了数据结构的整体空间效率。在这里，LOUDS代表l埃维尔•-小O请给U连Degree年代所以．¹³相比之下，我们使用快速的基于位图的编码方案对上层进行编码，称为LOUDS-Dense，其中子节点搜索只需要一个数组查找，选择性能而不是空间。

在本节的其余部分中，我们假设trie将键映射到固定长度的值。我们还假设trie的扇出为256(即每层一个字节)。

2.1 LOUDS-Sparse

LOUDS-Sparse使用4个字节/位序列按照级别顺序对trie节点进行编码，如图的下半部分所示图1．

图1。一个快速简洁的例子。tritry的上层和下层分别使用louds - density和LOUDS-Sparse进行编码。"$"表示ASCII码为O×FF的字符。它用于指示指向节点的前缀也是有效键的情况。

第一个字节序列,S-Labels，记录每个try节点的所有分支标签。例如，在第2级的第二个节点图1有三个分支机构。S-Labels包括它的标签(r, s),t在秩序。我们使用特殊字节O×FF表示指向节点的前缀也是有效键的情况¹在节点的开始。例如,在图1，第3级的第二个节点以“fas”作为传入前缀。由于'fas'本身也是存储在try中的键，节点将O×FF添加到S-Labels作为第一个字节。因为特殊字节总是出现在节点的开头，所以可以将其与真正的O×FF标签区分开来。

第二个位序列(S-HasChild中的每个字节包含一个位S-Labels指示子分支是继续(即指向子分支)还是终止(即指向一个值)。取第2级最右边的节点图1作为例子，因为分支标记我指向子try，对应位在S-HasChild是集。分支标记y，但是，它指向一个值，其S-HasChild清除。

第三位序列(S-LOUDS)表示节点边界:如果一个标签是节点中的第一个标签，则其S-LOUDS一些设置。否则，该位被清除。例如,在图1，第2级的第二个节点有三个分支，编码为100S-LOUDS．

最后的字节序列(差值)存储由键映射的固定长度的值(例如指针)。这些值按级别顺序连接—与三个位图相同。

树导航依赖于快速排序和选择原语。给定一个向量,排名（我)对1的个数进行计数我,而选择（我)返回的位置我th 1。现代排名和选择实现，如²¹实现常数时间通过使用查找表来存储预计算结果的样本，这样它们只需要在样本之间进行计数。我们表示排名/选择在位序列废话在位置pos是排名/选择（废话,pos）.

让pos的当前位位置S-Labels．假设S-HasChild［pos= 1，表示分支在pos指向子节点。要移动到子节点，我们首先计算子节点在整个层次有序节点列表中的排名:r =排名（S-HasChild, pos) + 1。因为每个节点都只有第一个比特S-LOUDS，我们可以使用选择（S-LOUDS r)来查找子节点的位置。

要移动到父节点，我们首先获得当前节点的秩rr =排名（S-LOUDS, pos)因为1的个数S-LOUDS节点数量。然后查找包含(的节点。r−1)th孩子:选择（S-HasChild，r−1)。

鉴于S-HasChild［pos= 0时，为了访问关联值，我们计算它的索引S-Values．因为每清除一点S-HasChild有价值的，有吗pos−排名（S-HasChild, pos)值之前pos．

2.2 LOUDS-Dense

如上半部分所示图1， LOUDS-Dense使用三个256大小的位图和一个字节序列对每个trie节点进行编码以保存值。编码遵循级别顺序。

第一个位图(D-Labels)记录每个节点的分支标签。具体来说,我位图中的第0位(0≤我≤255)表示该节点是否有带标签的分支我．中的根节点图1是否有三个分支被标记f,年代,t。的D-Labels位图设置第102位(f)、115 (年代)及第116 (t)并清除其余部分。

第二个位图(D-HasChild)表示分支是指向子项还是终止(即指向该值或分支不存在)。引入根节点图1例如f和t分支继续使用子try，而年代分支以一个值结束。在这种情况下，是D-HasChild位图只设置102^nd（f)和116^th（t)位为节点。

第三个位图(D-IsPrefixKey)每个节点只包含一个比特，用于指示指向该节点的前缀是否也是有效的密钥。同样的情况由LOUDS-Sparse中的特殊字节O×FF处理。

最后的字节序列(差值)的组织方式与S-Values在LOUDS-Sparse。

louds - density中的树导航也使用了排序和选择原语。给定一个棋位在D-Labels pos，移动到子节点:256 ×排名（D-HasChild, pos）;移动到父节点:选择（D-HasChild,⌊pos/ 256⌋);访问该值。排名（D-Labels, pos)−排名（D-HasChild, pos) +排名（D-IsPrefixKey,⌊pos/ 256⌋)1。

louds - density比LOUDS-Sparse更快，因为(1)一个节点内的标签搜索只需要对位图进行一次查找，而不是二进制搜索;(2)移动到子节点只计算一个位向量的秩，而不是对不同位向量的秩和选择。

2.3 FST和操作

FST是一种混合尝试，其中上层用louds - density编码，下层用LOUDS-Sparse编码。上层和下层之间的分界点可以根据交易性能和空间进行调整。默认情况下，我们保持大小比例Rlouds - density和LOUDS-Sparse之间的比例应小于1:64，以保证LOUDS-Sparse提供的空间效率。

FST高效支持四种基本操作:

• ExactKeySearch（关键的值关键如果关键存在(否则为NULL)。
• 下界（关键):返回指向键值对的迭代器(k、v),k按字典-图形顺序最小的满足吗k≥关键．
• MoveToNext（iter):将迭代器移动到下一个键。
• 数（lowKey, highKey):返回范围中包含的键的数量(lowKey, highKey）.

点查询(例如，ExactKeySearch)在FST的工作首先搜索的声音-密度水平。如果搜索没有终止，它将继续到LOUDS-Sparse级别。无论编码机制如何，每一层的高级搜索步骤都是相似的:首先，搜索当前节点的标签序列以找到目标键字节。如果密钥字节不存在，终止并返回零．否则，请检查对应的位HasChild位序列。如果设置了位，则计算子节点在标签序列中的起始位置，并继续到下一级。否则，返回值序列中的相应值。

下界使用类似于点查询实现的高级算法。该算法不是精确匹配，而是在当前节点的标签序列中搜索大于或等于该级别搜索字节的最小标签。如果搜索到达节点边界，算法可以递归向上移动到父节点。一旦这样的标签l，算法将迭代器移动到子树中最左边的键，根为l．

我们在迭代器中包括了逐级游标，用于记录当前键从根到叶的跟踪(即标签序列中的逐级位置)。使用游标，范围扫描(MoveToNext)在FST中有效地实现。每一级游标通过对其上级游标的“move-to-child”调用初始化一次。在此之后，这个级别的扫描操作只涉及游标移动，这是缓存友好且快速的。我们的计算表明，FST中的范围查询甚至比基于指针的尝试更快。

为数，算法首先执行MoveToNext并获得两个迭代器。它扩展try下的每个迭代器，并将每一层的游标设置为大于当前键的最小叶键的位置，直到两个迭代器满足或达到try的最大高度。然后，该算法通过计算两个迭代器在迭代器上的秩差来计算每一层叶子节点的数量D-HasChild / S-HasChild向量。返回这些计数的总和。

最后，可以通过对排序键值列表进行一次扫描来构建FST。

2.4空间分析

如果表示所占用的空间接近信息论的下界，即区分集合中任何对象所需的最小比特数，那么树表示就是“简洁”的。三度的信息论下界k大约是n（k日志₂k−(k−1)日志₂（k−1))位(当k= 256)。⁷

给定一个n-node try, LOUDS-Sparsen位为S-Labels，n位为S-HasChild,n位为S-LOUDS，共10个n位(加上用于排序和选择的辅助位)。虽然LOUDS-Sparse所占用的空间接近信息理论的下界，但在技术上，LOUDS-Sparse只能被归类为紧凑的而不是简洁的更精细的分类方案，因为LOUDS-SparseO（Z)空间(尽管乘数很小)而不是Z+o（Z）.

louds - density的尺寸受尺寸比的限制R以确保不影响FST的整体空间效率。值得注意的是，LOUDS-Dense并不总是比LOUDS-Sparse占用更多的空间:如果一个节点的扇出大于51，使用前者而不是后者来编码节点需要更少的比特。由于这样的节点在tritry的上层很常见，在LOUDS-Sparse上添加louds - density通常可以提高空间效率。

回到顶部

3.简洁的系列过滤器

在使用FST构建SuRF时，我们的目标是平衡滤波器所需的内存和较低的假阳性率。关键思想是使用截断的try，也就是说，删除较低级别的try，并用从键中提取的后缀位替换它们。我们介绍了SuRF的三种变体。我们描述了它们的性质以及它们如何保证片面错误。当前的SuRF设计是静态的，需要完全重建才能插入新的键。

3.1基本冲浪

FST是一个基于尝试的索引结构，它存储完整的键。作为一个过滤器，FST是100%准确的;然而，缺点是整个结构可能很大。在许多应用程序中，过滤器必须适合内存，以保护对存储在较慢存储上的数据结构的访问。这些应用程序无法提供完整键的空间，因此必须以精度换取空间。

SuRF (SuRF- base)的基本版本存储最小长度的键前缀，以便惟一地标识每个键。具体来说，SuRF-Base只为共享前缀之外的每个键存储一个额外的字节。图2显示了一个示例。代替存储完整的键('SIGAI'， 'SIGMOD'， 'SIGOPS')， SuRF-Base通过只包括共享前缀('SIG')和每个键('C'， 'M'， 'O')多一个字节来截断完整的尝试。

图2。冲浪的变化。从一个完整的尝试中得到SuRF的变化。

以这种方式修剪try会影响过滤器空间和准确性。不像Bloom过滤器那里的密钥是哈希的，SuRF-Base的tritry形状取决于存储的密钥的分布。因此，SuRF-Base的规模没有理论上的上界。然而，从经验上讲，SuRF-Base对64位随机整数只使用每个密钥(BPK) 10位，对电子邮件只使用14个BPK。直觉是，SuRF-Base建立的尝试通常有一个平均扇出F> 2:节点数小于键数的两倍。因为FST(准确地说是LOUDS-Sparse)使用10比特来编码一个trie节点，所以SuRF-Base的大小小于20 BPKF> 2。

滤波精度由假阳性率(FPR)来衡量。当不存在的查询键的前缀与存储的键前缀重合时，SuRF-Base中就会出现误报。例如,在图2，查询键'SIGMETRICS'将导致SuRF-Base误报。SuRF-Base中的FPR依赖于存储键和查询键的分布。我们在第4.2节中的结果显示，SuRF-Base对整数键产生4%的FPR，对邮件键产生25%的FPR。为了改进FPR，我们包含了这里描述的两种形式的键后缀，以允许SuRF更好地区分键前缀。

3.2带哈希键后缀的SuRF

所示图2， SuRF with hash key suffix (SuRF- hash)为每个key添加几个哈希位，以减少SuRF- base的FPR。让H是哈希函数。为每一个关键K， SuRF-Hash存储n（n是固定的)最小有效位H（K)在FST的值数组(这是空的SuRF-Base)。当钥匙(K”)查询到达叶节点时，SuRF-Hash提取叶节点n最低的H（K”)，并对与叶节点关联的存储散列位执行相等性检查。使用n每个键的哈希位数保证了SuRF-Hash的点查询FPR小于2⁻ⁿ(部分哈希碰撞概率)。第4.2节的实验表明，SuRF-Hash只需要2-4个哈希位就可以达到1%的FPR。

SuRF-Hash中的额外位对范围查询没有帮助，因为它们不提供键的排序信息。

3.3实键后缀冲浪

使用真正的键后缀(SuRF- real)代替哈希位存储n紧跟在存储的密钥前缀之后的密钥位。图2显示了当n= 8。SuRF-Real包含每个键的下一个字符('I'， 'O'， 'P')，以提高键的可区分性:例如，查询'SIGMETRICS'不再导致误报。与SuRF-Hash不同的是，点查询和范围查询都受益于真正的后缀位以减少误报。对于点查询，实际后缀位的使用方式与散列后缀位相同。对于范围查询(例如，移动到下一个键>)K)，当到达叶节点时，SuRF-Real会比较存储的后缀位年代关键部分k_年代查询键的对应位置。如果k_年代≤年代，迭代器指向当前键;否则，它将前进到try中的下一个键。

虽然SuRF-Real改进了点查询和范围查询的FPR，但其代价是对后缀位使用真实键不能像使用散列位那样提供良好的FPR，因为存储的键和查询键之间的分布相关性削弱了真实后缀位的可区分性。

回到顶部

4.冲浪微基准测试

在本节中，我们使用内存中的微基准测试来评估SuRF，以全面了解该过滤器的优点和缺点。

在我们的原始论文中，底层数据结构FST是单独评估的。^20.我们发现，与最先进的基于指针的索引(如B+tree)相比⁸以及适应性根树(ART)，¹⁵FST与它们的表现相匹配，但比它们小一个数量级。我们还将FST与其他简洁的try方案进行了比较^6，12结果表明，FST算法的速度比之前的算法快4 - 15倍，而且比之前的算法小。

4.1实验设置

我们用的是YCSB⁹工作负载C和E生成点和范围查询。我们测试了两种代表性的密钥类型:由YCSB生成的64位随机整数和从真实数据集(平均长度= 22字节，最大长度=129字节)提取的电子邮件地址(主机反转，例如“com.domain@foo”)。

评估SuRF的三个最重要的指标是假阳性率(FPR)、性能和空间。数据集是100M 64位随机整数键和25M电子邮件键。在实验中，我们首先使用随机选择的一半数据集构造待测滤波器。然后在过滤器上执行10M点或范围查询。查询键(K)都是从整个数据集根据YCSB工作负载C，因此大约50%的查询返回false。对于64位随机整数键，范围查询是[K+ 2³⁷，K+ 2³⁸其中46%的查询返回true。对于电子邮件键，查询范围为[K，K(最后一个字节++)](例如，[org。acm@sigmod, org.acm@sigmoe])，其中52%的查询返回true。

4.2假阳性率

图3通过改变滤波器的大小，显示了SuRF变量和Bloom滤波器之间的假阳性率(FPR)比较。Bloom过滤器只出现在点查询中。注意，对于电子邮件键工作负载，SuRF-Base每个键消耗14位(而不是10位)。这是因为电子邮件密钥共享更长的前缀，这增加了SuRF内部节点的数量。

图3。SuRF假阳性率。SuRF变量和Bloom filter之间的假阳性率比较(越低越好)。

对于点查询，Bloom过滤器在大多数情况下比相同大小的SuRF变体具有更低的FPR，尽管随着每个键位数的增加，SuRF- hash会很快赶上，因为每增加一个哈希位，FPR就会减少一半。对于点查询，SuRF-Real中的实数后缀位通常不如哈希位有效。对于范围查询，只有SuRF-Real受益于增加过滤器大小，因为SuRF-Hash中的哈希后缀不提供排序信息。在电子邮件关键工作负载中，SuRF-Real曲线的形状(即后四个后缀位在识别误报方面比前四个更有效)是由于字符的ASCII编码。

我们还观察到SuRF变体对于电子邮件关键工作负载有更高的FPRs。这是因为数据集中的电子邮件密钥非常相似(即，密钥分布密集)。两个电子邮件键的最后一个字节往往不同，或者一个可能是另一个的前缀。如果其中一个密钥在过滤器中表示，而另一个密钥没有，在SuRF-Base上查询丢失的密钥很可能会产生误报。如图所示，添加后缀位可以显著降低SuRF-Base的高FPR。

4.3性能

图4显示吞吐量比较。SuRF变体的运行速度与64位整数键工作负载的Bloom过滤器相当，这要归功于混合编码和其他性能优化，如向量化标签搜索和内存预取。对于电子邮件密钥，SuRF变体比Bloom过滤器慢，这是因为在try中搜索/遍历长前缀的开销。Bloom过滤器的吞吐量随着每个键的比特数的增加而降低，因为更大的Bloom过滤器需要更多的散列探测。SuRF变体的吞吐量不会受到后缀位数量增加的影响，因为只要后缀位长度小于64位，对后缀位的检查只涉及一次内存访问和一次整数比较。SuRF中的范围查询比点查询慢，因为每个查询都需要遍历(没有提前退出)。

图4。冲浪的性能。SuRF变体和Bloom filter之间的性能比较(越高越好)。

从实验中得到的一些高级结论如下:(1)SuRF可以进行范围滤波，而Bloom filter不能。(2)如果目标应用只需要点查询过滤，FPR要求适中，Bloom filter通常是比SuRF更好的选择。(3)对于点查询，SuRF-Hash在FPR上可以提供类似Bloom filter的理论保证，而SuRF-Real的FPR取决于密钥分布。

回到顶部

5.示例应用程序:RocksDB

我们将SuRF与RocksDB集成，作为Bloom滤波器的替代品。写入到RocksDB的MemTable中。当MemTable被填满时(例如，超过4MB)，引擎将其排序，然后将其转换为0级的SSTable。一个SSTable包含经过排序的键值对，并被划分为匹配最小磁盘访问单元的固定长度块。为了定位块，RocksDB存储每个块的“重启点”(一个≥当前块的最后一个键，<下一个块的第一个键的字符串)作为块索引。当一个level的大小达到一个阈值时，RocksDB会选择这个level上的一个SSTable，并将其合并到下一个key范围重叠的SSTable中。这个过程被称为压缩。每个级别≥1的键都是在sstable中全局排序的。该属性确保对于≥1的级别，条目查找每个级别最多读取一个SSTable。

我们修改了RocksDB的点(得到)及量程(寻求)查询实现使用SuRF。为得到（关键)， RocksDB使用SuRF就像Bloom filter一样，在每一层，它通过块索引定位候选SSTable(s)和块(s)。对于每个候选的SSTable, RocksDB首先查询内存中的过滤器，只有当过滤器结果为阳性时，才提取SSTable块。

来实现寻求（路，香港)， RocksDB首先通过搜索从所有级别收集候选sstable路在块索引中。在没有surf的情况下，RocksDB检查每个候选SSTable，并获取包含最小键值≥的块路．然后，RocksDB找到全局最小的密钥K≥路在这些候选密钥中。如果K≤香港，查询成功;否则，查询返回空。

然而，对于surf, RocksDB不是获取实际的块，而是通过执行a来获取每个SSTable的候选密钥下界在它的SuRF上查询，以避免每个SSTable一次I/O。如果查询成功，RocksDB将从所选的SSTable中精确获取一个包含全局最小值的blockK．如果查询结果为空，说明无I/O操作。由于SuRF只存储键前缀，系统必须执行额外的检查来打破平局并防止误报。额外的检查在我们的原始论文中描述。^20.尽管存在这些潜在的检查，但在RocksDB中使用SuRF可以降低平均I/ o寻求（路，香港)查询。

5.1评价设置

时间序列数据库通常使用RocksDB或类似的lsm树设计作为存储引擎。^5，17因此，我们创建了一个合成的RocksDB基准，为分布式传感器生成的时间序列数据集建模，用于端到端性能测量。我们模拟了2k个传感器来记录事件。每个事件的键是一个128位值，由一个64位的时间戳和一个64位的传感器ID组成。记录中的相关值为1KB。每个传感器检测到的每个事件的发生遵循泊松分布，其预期频率为每0.2 s发生一次。每个传感器工作10K秒和记录~50K事件。每个传感器的启动时间戳是在前0.2秒内随机生成的。原始记录的总大小大约为100GB。

我们的测试框架支持以下查询:

• 点查询:给定时间戳和传感器ID，如果有事件，则返回该记录。
• 范围查询:给定一个时间范围，确定是否有任何事件在该时间段内发生。如果是，返回指向范围内最早事件的迭代器。

我们的测试机器使用英特尔酷睿i7-6770HQ CPU, 32gb RAM和英特尔540 480GB SSD。我们配置²根据Facebook的推荐。^4，11生成的RocksDB实例有4个级别，使用了52GB的磁盘空间。

我们用不同的过滤选项创建了RocksDB的四个实例:no filter、Bloom filter、SuRF-Hash和SuRF-Real。我们将每个过滤器配置为使用等量的内存。Bloom过滤器每个密钥使用14位。相同大小的SuRF-Hash和SuRF-Real每个键包含一个4位后缀。我们首先用100万个均匀分布的对现有键的点查询来温暖缓存，这样每个SSTable大约会被访问1000次，并且缓存块索引和过滤器。预热之后，RocksDB的块缓存和OS页面缓存都已满。然后，我们执行50k个应用程序查询，记录DBMS的端到端吞吐量和I/O计数。查询键(对于范围查询，是开始键)是随机生成的:操作时间范围内的随机时间戳+随机选取的传感器ID。报告的数据是三次测试的平均值。

5.2点查询结果

图5显示点查询的结果。因为查询键是随机生成的，所以几乎所有查询都返回false。查询性能主要由I/O计数决定:它们成反比。除了0级，每个点查询预计访问三个sstable，每个级别(1、2、3)。没有过滤器，点查询产生大约1.5 I/ o根据图5，这意味着整个Level 1和Level 2的大约一半可能会被缓存。这是典型的RocksDB配置，最后两层不缓存在内存中。¹⁰

图5。点查询。不同滤波器配置下的RocksDB点查询评估。

在点查询中使用过滤器可以减少I/O，因为它们可以防止不必要的块检索。使用SuRF-Hash或SuRF-Real比使用Bloom filter要慢，因为4位后缀不会减少像Bloom filter配置那样低的误报(参见第4.2节)。SuRF-Real提供了与SuRF-Hash类似的好处，因为密钥分布是稀疏的。

5.3范围查询结果

使用SuRF的主要好处是加速范围查询。图6显示范围查询的吞吐量和I/O计数。在x轴上，我们通过改变范围大小来控制查询结果为空的百分比。来自所有传感器的事件的泊松分布的期望频率为1 / λ = 10⁵ns。对于有长度的区间R，区间不包含事件的概率由e^−R/λ．因此，对于目标百分比(P)对于结果为空的Closed-Seek查询，我们将range size设置为．例如，对于50%，范围大小是69310 ns。

图6。范围查询。RocksDB在不同滤波器配置和范围大小下的范围查询评估。

所示图6， Bloom过滤器不能帮助范围查询，相当于没有过滤器。然而，当99%的查询返回空值时，使用SuRF-Real可以将查询速度提高5倍。同样，I/O计数主导性能。如果没有范围过滤器，每个查询必须从每个级别获取候选SSTable块，以确定范围内是否有键。然而，使用SuRF变体可以避免许多不必要的I/ o;只有当各级过滤器返回的最小键值在查询范围内时，RocksDB才会对包含该最小键值的SSTable块进行读取。使用SuRF-Real比SuRF-Hash更有效，因为真正的后缀位有助于减少范围边界的误报。

回到顶部

6.结论

本文介绍了SuRF滤波器结构，它支持对单键和范围的近似隶属度测试。SuRF建立在一种新的简洁的数据结构上，称为快速简洁尝试(FST)，它只需要每个节点10位来编码尝试。FST被设计成具有相当于最先进的基于指针的索引的性能。SuRF是内存高效的，它的空间和假阳性率可以通过选择不同数量的后缀位来调整。在RocksDB中，用相同大小的surf替换Bloom过滤器大大减少了I/O，并提高了范围查询的吞吐量，同时略微降低了最坏情况点查询的吞吐量。因此，我们相信SuRF在优化未来存储系统等方面是一种很有前途的技术。SuRF的源代码可以在https://github.com/efficient/SuRF．

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2021 ACM, Inc。

---

没有发现记录