ACM通信
研究突出了
技术角度:SuRF的优势
为点或范围查询过滤数据的数据结构在所有数据驱动的应用程序中普遍存在，从分析到事务，以及现代机器学习应用程序。主要目标很简单:查找数据库中是否存在一个或多个数据项。然而，这个简单的任务非常难以高效地执行，而且对于依赖于过滤的数据密集型应用程序的整体属性非常关键。
这是一个困难的问题，因为有许多关键参数和权衡。许多参数来自工作负载，例如，点查询与更新的确切百分比，空结果查询的百分比，等等。其他参数来自底层硬件;例如，过滤器通常驻留在内存中，但是随着数据大小呈指数级增长，我们需要注意过滤器大小和内存层次结构。总的来说，需要进行复杂的权衡:内存、读和写放大。例如，对于点查询和范围查询，数据结构不能同时有效地支持高效的写操作。然而，许多应用程序需要公开这两种读取模式。
过滤器的一个典型应用是基于日志结构合并树(LSM-tree)的存储引擎。lsm树按照数据到达不可变文件的顺序存储数据，并定期将数据排序合并到更大的文件中。通过这种方式，它在日志和排序数组之间运行，根据精确的调优(文件大小、缓冲区大小等)提供良好的读写性能平衡。lsm树存储引擎被用作大多数分布式键值存储和应用程序的主干，包括社交媒体、web应用程序、电子购物、物联网等。由于lsm -树引擎的多层架构强制执行全局时间顺序，因此它们严重依赖于内存中的过滤器。
SuRF基于尝试的设计允许构造一个过滤器，它可以支持性能范围查询、点查询和近似计数。
简洁范围滤波器(SuRF)作为一种新的简洁滤波器在ACM SIGMOD 2018年会议上被引入。1SuRF基于一种类似尝试的结构，称为“快速简洁尝试”。基于尝试的设计使过滤器的构造成为可能，该过滤器可以支持单个查询峰范围查询、点查询和近似计数。SuRF的作者做了以下批判性和深刻的观察，把所有的东西结合在一起，并允许SuRF平衡各种硬件和工作负载。对于给定的查询集，trie的上层会比下层招致更多的访问。因此，SuRF设计对tritry的顶部使用了密集的、性能优化的编码方案，对底部使用了稀疏的、内存优化的编码方案。这就产生了一种既快速又节省内存的数据结构。上层由少量节点组成，但需要大量访问，在一种名为louds - density的新方案下编码密钥，这种方案牺牲了空间效率以实现快速查找。较低的层次包含大多数节点，但具有更稀疏的访问模式，使用一种称为loud - sparse的方案进行编码，这种方案牺牲了快速查找，以提高空间效率。
与最先进的基于布隆过滤器的解决方案(例如前缀布隆过滤器)相比，SuRF提供了一个通用的解决方案，即它可以支持任何范围查询以及高效的点查询。与最先进的树型或基于尝试的解决方案相比，基于尝试的设计使过滤器的构造能够支持性能范围查询、点查询和近似计数。SuRF以更小的内存占用率提供了类似或更好的性能。随后的SuRF论文展示了将SuRF集成到RocksDB(最成熟的基于lsm树的存储引擎)中的端到端影响，并展示了在点查询和范围查询的时间序列应用中强大的结果(例如，高达5倍)。SuRF可以广泛应用于任何需要简洁过滤器的应用程序，如监控、隐私/安全和图分析。最后，SuRF设计的核心精神体现了优雅的研究品味，追求混合、硬件和工作负荷意识的设计。
参考文献
1.Zhang, H.， Lim, H.， Leis, V.， Andersen, D.G.， Kaminsky, M.， Keeton, K.和Pavlo, A. SuRF:快速简洁尝试的实用范围查询过滤。在美国ACM SIGMOD 2018年会论文集．
数字图书馆是由计算机协会出版的。版权所有©2021 ACM, Inc。
没有发现记录