[RocksDB剖析系列] Log-structured merge-tree
B+ Tree的缺点
B+树最大的性能问题是会产生大量的随机IO,随着新数据的插入,叶子节点会慢慢分裂,逻辑上连续的叶子节点在物理上往往不连续,甚至分离的很远,但做范围查询时,会产生大量随机读IO。
对于大量的随机写也一样,新插入的数据在磁盘上的位置可能相隔很远,会产生大量的随机写IO。
相比B+ Tree,LSM-Tree可能会损失一部分读性能,但换来了巨大的写性能的提升。
LSM-Tree原理
文章图片
Memtable
当一个Memtable被写满时,它将变为immutable的,后面进来的数据将写入一个新的Memtable。而后台线程将会将Immutable Memtable flush进一个SST文件,并在flush好后将该Memtable销毁
数据结构
可选择的数据结构
- SkipList (Default)
- HashLinkList
- HashSkipList
- Vector
而哈希跳表我之前没有接触过,结果搜索后发现是先对哈希值取模放入对应的桶中,再在每个哈希桶中维护跳表结构。
这样的话应该会提升随机单个查询的速度,而范围查询应该会变慢一点。
此外,根据官方文档,只有SkipList支持并发插入。
Flush 三种情况下会触发flush操作
- 当某一个Memtable的大小超出了
ColumnFamilyOptions::write_buffer_size
- 当所有列族的Memtable的总大小超出了
DBOptions::db_write_buffer_size
,或者DBOptions::write_buffer_manager
发出了flush的信号。这种情况下size最大的那个Memtable将被flush - WAL的大小超过了
DBOptions::max_total_wal_size
。这种情况下最老的Memtable将被flush,以便清空它相应的WAL中的部分。
RocksDB的每次更新都会写入两个位置:内存中的memtable(稍后将flush到SST文件)和磁盘上的预写日志(WAL)。而当Memtable中的数据flush后,WAL中对应的数据将被删除
【[RocksDB剖析系列] Log-structured merge-tree】WAL被用作故障后恢复数据,它默认是开启的。也可以通过配置关闭它。
推荐阅读
- 【欢喜是你·三宅系列①】⑶
- 你不可不知的真相系列之科学
- 人脸识别|【人脸识别系列】| 实现自动化妆
- 2018-06-13金句系列7(金句结构-改编古现代诗词)
- Unity和Android通信系列文章2——扩展UnityPlayerActivity
- 乡野村趣系列之烧仙草
- Java内存泄漏分析系列之二(jstack生成的Thread|Java内存泄漏分析系列之二:jstack生成的Thread Dump日志结构解析)
- 15、IDEA学习系列之其他设置(生成javadoc、缓存和索引的清理等)
- 【年终激励系列】之五(年终奖如何与考核紧密相连)
- Spring|Spring 框架之 AOP 原理剖析已经出炉!!!预定的童鞋可以识别下发二维码去看了