MySQL 的存储引擎除了最常用的是 InnoDB 引擎之外还有一个 MyRocks 引擎也经常会用到,它是基于 RocksDB 开发的一套存储引擎,比 InnoDB 性能要高出 N 倍。
在索引实现上,InnoDB 的索引使用 B+ 树实现,B+ 树的叶子节点上存储了索引的 key,所有的叶子结点使用指针串了起来,非常易于索引的遍历操作。比如下面这个语句(key1 字段加了索引)的范围查询就可以很好的利用这个特性
select key1 from t where key1 > 'abc'
and key1 < 'def'
但是 MyRocks 的索引实现不一样,MyRocks 的索引使用 LSM Tree 来实现,通常 LSM Tree 都不支持高效的范围遍历。原因在于 LSM Tree 是多层结构 —— 内存里的 MemTable 和磁盘上的 7 层 SST 文件,范围遍历需要对内存里的多个 MemTable 和这磁盘上的 7 层文件都需要读取后 Merge 在一起才能拿到最终的范围遍历的结果。如果查询范围比较窄,其中 0 层文件可能需要全部读取,其它 6 层通常只需要读取一个文件,因为 0 层文件的多个文件 Key 之间是有重叠的,而其它 6 层中每层的多个文件之间是严格根据 Key 范围切割的。即使对应 SST 文件里面不存在目标范围的 Key,这样的磁盘读取还是不可避免。
我们知道 RocksDB 磁盘上的每个SST 文件里面里面都存了一个布隆过滤器,布隆过滤器的内容通常是缓存(固定)在内存中的。如果布隆过滤器能帮我们提前把查询范围过滤掉,判断出目标 SST 文件是否存在目标查询范围,这样就可以减少磁盘读取了。
但问题是布隆过滤器也是不存在范围查询的能力的,通常也只能判断一下过滤器中是否存在某个 Key。为了解决这个问题,RocksDB 引入了 prefix_extractor ,它可以很好的解决这个难题。那这个 prefix_extractor 又是个什么高深的技术呢?其实也很简单,它就是 prefix bloom filter。
这个「前缀布隆过滤器」 Add 进来的 Key 不再是原来的 Key,而是 Key 的固定长度的前缀,它带来的好处之一是布隆过滤器占用的空间变小了,坏处是误判率也会跟着提高了一点。假设前缀长度是 3,那么把 abcd 这个 Key 加进去后会认为 abce 也在里面,因为它们共享了 abc 这个前缀。这省下来的空间可以用来存储一个附加的数据结构 —— Key 前缀 的有序集合,它里面容纳了所有的 Key 前缀的值。通过这个有序的 Key 前缀集合可以快速判断出目标范围是否存在于当前的 SST 文件中。
和布隆过滤器的数据一样,这个 Key 前缀的有序集合也是缓存(固定)在内存中的。因为单个 SST 文件的 Key 数量是有限的,前缀设置的比较短的话,对应的的前缀数量也会非常少,消耗的内存就可以忽略不计了。
聪明的同学可能想到了,这个前缀的长度取多少比较合适呢?要是用户的索引字段值上自带了前缀字符串,那切割出来的前缀有可能完全一样,这前缀布隆过滤器岂不是要形同虚设么?