rocksdb-doc-cn

MemTable是一个内存数据结构,他保存了落盘到SST文件前的数据。他同时服务于读和写——新的写入总是将数据插入到memtable,读取在查询SST文件前总是要查询memtable,因为memtable里面的数据总是更新的。一旦一个memtable被写满,他会变成不可修改的,并被一个新的memtable替换。一个后台线程会把这个memtable的内容落盘到一个SST文件,然后这个memtable就可以被销毁了。

影响memtable的最重要的几个选项是:

默认的memtable实现是基于skiplist的。除了默认的memtable实现,用户可以使用其他memtable实现,例如HashLinkList,HashSkipList或者Vector,以加快查询速度。

Skiplist Memtable

基于Skiplist的memtable在多数情况下都有较好读,写,随机访问以及序列化扫描性能。除此之外,他还提供其他memtable没有的有用的功能,比如并发插入以及带Hint插入

HashSkiplist Memtable

正如他们的名字暗示的,HashSkipList用一张哈希表组织数据,每个哈希桶内都是一个的skiplist,而HashLinkList则是用一张哈希表组织数据,每个哈希桶内则是使用一个排序好的链表。两种类型都是为了减少查询的时候的比较次数。一种好的使用例子是使用PlainTable SST格式结合他们,然后把数据存储在RAMFS里。

当做数据查询或者插入一个key的时候,目标key的前缀通过Options.prefix_extractor被提取出来,用于找到具体的哈希桶。在哈希桶里面,所有的比较都是完整(内部)key比较,跟SkipList的memtable一样。

使用基于哈希的memtable最大的限制就是做多个前缀扫描的时候需要拷贝和排序,这非常慢并且浪费内存

落盘

有三种场景会导致memtable落盘被触发:

就结果来说,memtable可能还没写满就落盘了。这是为什么生成的SST文件小于对应的memtable大小。压缩是另一个导致SST文件变小的原因,因为memtable里的数据是没有压缩的。

并发插入

如果不支持对memtable进行并发插入,从多个线程过来的并发写会按顺序应用到memtable中。并发memtable插入是默认打开的,可以通过allow_concurrent_memtable_write选项来关闭,尽管只有skip-list的memtable支持这个功能。

带Hint插入

原地更新

对比

Memtable类型 SkipList HashSkipList HashLinkList Vector
最佳使用场景 通用 带特殊key前缀的范围查询 带特殊key前缀,并且每个前缀都只有很小数量的行 大量随机写压力
索引类型 二分搜索 哈希+二分搜索 哈希+线性搜索 线性搜索
是否支持全量db有序扫描? 天然支持 非常耗费资源(拷贝以及排序一生成一个临时视图) 同HashSkipList 同HashSkipList
额外内存 平均(每个节点有多个指针) 高(哈希桶+非空桶的skiplist元数据+每个节点多个指针) 稍低(哈希桶+每个节点的指针) 低(vector尾部预分配的内存)
Memtable落盘 快速,以及固定数量的额外内存 慢,并且大量临时内存使用 同HashSkipList 同HashSkipList
并发插入 支持 不支持 不支持 不支持
带Hint插入 支持(在没有并发插入的时候) 不支持 不支持 不支持
看到这里或许你有建议或者疑问或者指出错误,请留言评论! 多谢! 你的评论非常重要!也可以帮忙点赞收藏转发!多谢支持! 觉得写的不错那就给点吧, 在线乞讨 微信转账