FAST21-REMIX Range-query Efficient Multi-table IndeX汇总
rocksdb范围查询性能差主要原因在于排序信息是用到再查的,这里的解决方案就是高效处理这个信息
回想一下bitcask的设计,hashkv,但是重启需要整个加载一遍,很慢,为了避免这个问题引入索引文件hint
这里的remix就是把sst的排序给保存了下来,方便范围查询,但肯定会影响写性能,因为你修改的同时也要维护这个索引文件
想法有了,如何实现?
根据key范围分片
引自 https://zhuanlan.zhihu.com/p/357024916
REMIX 将 sorted view 涉及到的 key range 按照顺序划分为多个 segment,每个 segment 内保存一个 anchor key,记录该 segment 内最小的 key。
此外,每个 segment 内还维护了 cursor offsets 和 run selectors 两个信息。Cursor offsets 记录了每个 run 中首个大于等于 anchor key 的 key offset,比如 11 这个 segment,run 1,2,3 首个大于等于该值的 key 是 11, 17, 31(offset 1, 2, 1)。Run selectors 顺序记录了 segment 内每个 key 所在的 run 序号,以 71 这个 segment 为例,71, 73, 79 分别在 run 0, 1, 0 中。
假设点查 17,基于 REMIX 可以进行如下的查询过程:
- 通过 anchor key 二分查找,定位到 17 落在第二个 segment 的 key range 内。
- 由于 cursor offsets 代表着各个 run 中首个大于等于 anchor 的 key,17 > 11,所以直接将它作为各个 run 的初始 cursor,即 (1, 2, 1)。
- 将当前 pointer 设置为 run selectors 中的第一个,即 run 0,相当于原先的最小堆 top。
- 从 pointer 指向的 run 开始比较,11 (run 0) < 17,所以推进 run 0 的 cursor,即 offsets 变为 (2, 2, 1)。同时,run selectors 也向前推进,由 run0 切换至 run1,表示下一个需要访问的是 run1 在 cursor offsets 中对应的 key,即 run1 中下标为 2 的 key(17)。
- 查询结束。
范围查询过程:不断地根据 run selectors 调整访问的 run 及 offset,并结合与 end key 的比较结果,即可将点查过程扩展为范围查询。
但从上面的查询过程可知,segment 内查询是从 anchor key 开始,这个过程还是可能会产生不必要的比较和 run 访问。这和 segment 内的 key 数量有关,如果数量多,顺序查询性能差,但存储效率高(只用存储 anchor key),反之 anchor key 会变多,存储开销大。
- 通过全局的二分查找(segment 间基于 anchor key、segment 内基于 selectors),有效地减少了定位一个 key 时的复杂度。传统方式 M * logN,REMIX logMN。
- Run selectors 可以帮助 REMIX 在查询时快速地在不同 run 的 key 间顺序推进,不用维护最小堆,也就避免了在每次 pop 时通过 key 比较进行重排,降低了计算开销。
- 基于 anchor key 的二分也使得查询过程有机会跳过一些无需访问的 run,以先前的图片为例,如果一次点查询基于 anchor 二分的结果是第三个 segment,那么本次查询只需要访问 run2 即可完成。
参考
- 论文https://www.usenix.org/system/files/fast21-zhong.pdf
- https://github.com/wuxb45/remixdb 代码
- https://www.youtube.com/watch?v=9F4AzqBp8Ng 演讲