问题描述

Rosetta[1]的介绍部分的Range Queries Are Hards说

While LSM-based key-value stores support efficient writes and point queries, they suffer with range queries, This is because we cannot rule out reading any data blocks of the target key range across all levels of the tree.

其中的cannot rule out data block是具体怎么样发生的呢？没必要读取的data block是什么样的block呢？为什么范围查询不能过滤掉这些block呢？

可能的可能性

一、Prefix Bloom filter带来的假阳率

它可能是指用了Prefix Bloom Filter[1][2]的实现，Prefix Bloom Filter只会存储Key的固定长度的前缀，检查前缀不存在，就可以确认这个范围内的Key都不存在。但是Prefix Bloom Filter存在更严重的假阳性，前缀不同，但是前缀hash值相同的Key会发生碰撞，一些不存在的Key也会因此被误判为存在，而读取没有用的Block。

问题：LevelDB并没有使用Prefix Bloom Filter，而是对多个Run的有序链表用最小堆进行排序[3]，Prefix Bloom Filter只能算是一种改进，并不是标准LSM Tree里的设计。

二、无法判断是否是旧数据

有一些Block虽然包含了要查询范围内的Key，但是它们是旧数据，所以是失效数据，即使读取出来，也要被丢弃，所以相当于白读了，而标准的LSM Tree并不能提前过滤掉这些，所以影响了性能。

问题：Rosetta是一个支持范围查询的Bloom Filter，它可以过滤掉一些没有KV的范围，以此来提升性能，但是它无法判断数据是否是旧数据。

三、查询的范围与SSTable的范围的交界处的小范围不存在KV

感觉也可能是范围查询的时候需要用要查询的范围与fence pointer是否重叠来判断SSTable内是否有需要的KV，但是可能重叠的那部分并没有，继续读就白读了。

比如说要查询的是[10, 100]，而SSTable的范围是[123, 2000]，那么是有重叠的，重叠的部分是[123， 100]，那么正常情况下应该在这个SSTable中Seek(123)一下，但是这个SSTable恰好[123, 100]这个范围内没有KV，在[100, 2000]内才有KV，所以Seek那个存在读取的index block就算是白读了。

问题：是不是空，Seek一下最多只需要读index block，最起码到bloom filter就能判断出不存在，要读取不存在需要KV的data block，最起码是bloom filter也误判了。

参考文献

[1] Siqiang Luo, Subarna Chatterjee, Rafael Ketsetsidis, Niv Dayan, Wilson Qin, and Stratos Idreos. 2020. Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD '20).
[2] Sarang Dharmapurikar, Praveen Krishnamurthy, and David E. Taylor. 2003. Longest prefix matching using bloom filters. In Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications (SIGCOMM '03).
[3] Wenshao Zhong, Chen Chen, and Xingbo Wu, University of Illinois at Chicago. 2021. REMIX: Efficient Range Query for LSM-trees. FAST '21.