前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >RocksDB 的范围查询是如何优化的?

RocksDB 的范围查询是如何优化的?

作者头像
老钱
发布2020-07-10 11:35:34
3.4K0
发布2020-07-10 11:35:34
举报
文章被收录于专栏:码洞

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 数量是有限的,前缀设置的比较短的话,对应的的前缀数量也会非常少,消耗的内存就可以忽略不计了。

聪明的同学可能想到了,这个前缀的长度取多少比较合适呢?要是用户的索引字段值上自带了前缀字符串,那切割出来的前缀有可能完全一样,这前缀布隆过滤器岂不是要形同虚设么?

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-07-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 码洞 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
云数据库 SQL Server
腾讯云数据库 SQL Server (TencentDB for SQL Server)是业界最常用的商用数据库之一,对基于 Windows 架构的应用程序具有完美的支持。TencentDB for SQL Server 拥有微软正版授权,可持续为用户提供最新的功能,避免未授权使用软件的风险。具有即开即用、稳定可靠、安全运行、弹性扩缩等特点。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档