facebook-github-bot
commented
4 months ago Hi @hcwang512!
Thank you for your pull request and welcome to our community.
Action Required
In order to merge any pull request (code, docs, etc.), we require contributors to sign our Contributor License Agreement, and we don't seem to have one on file for you.
Process
In order for us to review and merge your suggested changes, please sign at https://code.facebook.com/cla. If you are contributing on behalf of someone else (eg your employer), the individual CLA may not be sufficient and your employer may need to sign the corporate CLA.
Once the CLA is signed, our tooling will perform checks and validations. Afterwards, the pull request will be tagged with CLA signed. The tagging process may take up to 1 hour after signing. Please give it that time before contacting us about it.
If you have received this in error or have any questions, please contact us at cla@meta.com. Thanks!
性能提升
与 skiplist 相比，读写速度提升 1.8x, scan 性能持平。
Motivation
rocksdb 官方支持的5种 mem table 中，hash 类型的结构支持快速的查询，vector 类型的结构支持快速的写入，另外的一个缺陷是它们都没法支持 range scan. 因此在实际使用中更多会用 SkipList . 但是 SkipList 在并发读写的情况下性能不会太好。 需要一种新的结构(hash_sorted_vector)同时拥有 hash 的查询速度，vector 的写入速度，而且支持 range scan.
如上图所示，在 hash_sorted_vector 中，数据会同时写入 hash 和 vector 中。hash 由大量的 bucket 组成，bucket 里是链表，锁作用在每个 bucket 内，以缓解锁带来的性能损失。 sorted_vector 由大量 sorted vector 和头部的 unsorted vector 组成，排序 vector 是只读的，数据只写入 unsorted vector. scan操作则只从 sorted vectors 里以 multi-way merge sort 的方式读取数据。每次的 scan 操作会将当前的 unsorted vector 排序，作为 sorted vectors 的一员，并生成一个新的 unsorted vector.
benchmarks
跑了 rocksdb 自带的 randomreadrandomwrite 和 newiterator, 运行环境是 ubuntu docker hosted in macbook pro m1 pro.
截图如下: