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 可以进行如下的查询过程：

  1. 通过 anchor key 二分查找，定位到 17 落在第二个 segment 的 key range 内。
  2. 由于 cursor offsets 代表着各个 run 中首个大于等于 anchor 的 key，17 > 11，所以直接将它作为各个 run 的初始 cursor，即 (1, 2, 1)。
  3. 将当前 pointer 设置为 run selectors 中的第一个，即 run 0，相当于原先的最小堆 top。
  4. 从 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）。
  5. 查询结束。

范围查询过程：不断地根据 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 即可完成。

参考

  1. 论文https://www.usenix.org/system/files/fast21-zhong.pdf
  2. https://github.com/wuxb45/remixdb 代码
  3. https://www.youtube.com/watch?v=9F4AzqBp8Ng 演讲