内容简介:因为 LevelDB 的增删改都是通过追加写来实现的,所以需要通过后台线程的 compaction 来:除了从外部调用 CompactRange,LevelDB 有几种情况会自动触发 compaction:Minor Compaction 比较简单,基本代码路径是:
Compaction 的作用
因为 LevelDB 的增删改都是通过追加写来实现的,所以需要通过后台线程的 compaction 来:
-
清理过期(旧版本或者已删除)的数据。
-
维护数据的有序性。
Compaction 的触发
除了从外部调用 CompactRange,LevelDB 有几种情况会自动触发 compaction:
-
当 MemTable 的大小达到阈值时,进行 MemTable 切换,然后需要将 Immutable MemTable 刷到外存上 —— 一般称之为 Minor Compaction。
-
当 level-n 的 SSTable 超过限制,level-n 和 level-n+1 的 SSTable 会进行 compaction —— 一般称之为 Major Compaction。
-
level-0 是通过 SSTable 的数量来判断是否需要 compaction。
-
level-n(n > 0) 是通过 SSTable 的大小来判断是否需要 compaction。
Minor Compaction
Minor Compaction 比较简单,基本代码路径是: DBImpl::CompactMemTable [1] => DBImpl::WriteLevel0Table [2] => BuildTable [3] 。
Major Compaction
-
每次 compaction 结束,更新 manifest 之后,都会调用 VersionSet::Finalize [4] 计算下一次要进行 major compaction 的 level。
-
每次 major compaction 开始时,调用 VersionSet::PickCompaction [5] 计算需要进行 compaction 的 SSTable。
-
如果选中的 level-n 的 SSTable 和 level-n+1 的 SSTable 的 key 范围没有重叠,可以直接将 level-n 的 SSTable “移动”到 level-n+1,只需要修改 Manifest。
-
否则,调用 DBImpl::DoCompactionWork [6] 对 level-n 和 level-n+1 的 SSTable 进行多路归并。
Compaction 的问题
Compaction 会对 LevelDB 的性能和稳定性带来一定影响:
-
消耗 CPU:对 SSTable 进行解析、解压、压缩。
-
消耗 I/O:大量的 SSTable 批量读写,十几倍甚至几十倍的写放大会消耗不少 I/O,同时缩短 SSD 的寿命(SSD 的写入次数是有限的)。
-
缓存失效:删除旧 SSTable,生成新 SSTable。新 SSTable 的首次请求无法命中缓存,可能引发系统性能抖动。
常见的做法是,控制 compaction 的速度(比如 RocksDB 的 Rate Limiter [7] ),让 compaction 的过程尽可能平缓,不要引起 CPU、I/O、缓存失效的毛刺。这种做法带来一个问题:compaction 的速度应该控制在多少?Compaction 的速度如果太快,会影响系统性能;Compaction 的速度如果太慢,会阻塞写请求。这个速度和具体的硬件能力、工作负载高度相关,往往只能设置一个“经验值”,比较难通用。同时这种做法只能在一定程度上减少系统毛刺、抖动,Compaction 带来的写放大依然是那么大。
写放大简单分析
-
+1 - WAL 的写入。
-
+1 - Immutable Memtable 写入到 level-0 文件。
-
+2 - level-0 和 level-1 的 compaction(level-0 的每个 SSTable 的 key 范围是重叠的。一般控制 level-0 和 level-1 的数据大小是一样的,每次拿全量 level-0 的数据和全量 level-1 的数据进行 compaction)。
-
+11 - level-n 和 level-n+1 合并的写入(n >= 1,默认情况下,level-n+1 的数据大小是 level-n 的 10 倍)。
所以,总的写放大是 4 + 11(n-1) = 11n - 7 倍。
假设有 5 个 level,写放大最大是 48 倍——也就是说,外部写入 1GB 的数据,内部观察到的 I/O 写流量会有 48GB。
关于 LSM-Tree 的写放大有不少论文进行了详细的介绍、讨论和提出优化方案,比如:
-
Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging - 这篇论文将各种 compaction 方式和影响介绍得非常清楚。
-
WiscKey: Separating Keys from Values in SSD-conscious Storage - 通过将键值分离,大大减少了写放大。
-
...
小结
-
根据实际经验,在大部分场景下, compaction 带来的问题不是特别明显。
-
一些会有突发流量的情况,很容易造成 compaction 的速度跟不上实际写入的速度,导致写失败。
-
Write intensive 的场景,写放大缩短了 SSD 的寿命也是个问题。
参考资料
DBImpl::CompactMemTable: https://github.com/google/leveldb/blob/1.22/db/db_impl.cc#L535
DBImpl::WriteLevel0Table: https://github.com/google/leveldb/blob/1.22/db/db_impl.cc#L491
BuildTable: https://github.com/google/leveldb/blob/1.22/db/builder.cc#L17
VersionSet::Finalize: https://github.com/google/leveldb/blob/1.22/db/version_set.cc#L1050-L1086
VersionSet::PickCompaction: https://github.com/google/leveldb/blob/1.22/db/version_set.cc#L1270
DBImpl::DoCompactionWork: https://github.com/google/leveldb/blob/1.22/db/db_impl.cc#L878
Rate Limiter: https://github.com/facebook/rocksdb/wiki/Rate-Limiter
以上所述就是小编给大家介绍的《LevelDB 完全解析(十一):Compaction》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 每秒解析千兆字节的 JSON 解析器开源,秒杀一大波解析器!
- 注册中心 Eureka 源码解析 —— EndPoint 与 解析器
- 新一代Json解析库Moshi源码解析
- mybatis源码配置文件解析之三:解析typeAliases标签
- MySQL内核源码解读-SQL解析之解析器浅析
- Laravel 核心——IoC 服务容器源码解析(服务器解析)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
《裂变:秒懂人工智能的基础课》
王天一 / 电子工业出版社·博文视点 / 2018-6-13 / 59.00元
人工智能是指通过普通计算机程序实现的人类智能技术,这一学科不仅具有非凡的科学意义,对人类自身生存方式的影响也在不断加深。本书作为人工智能领域的入门读物,内容围绕人工智能的核心框架展开,具体包括数学基础知识、机器学习算法、人工神经网络原理、深度学习方法与实例、深度学习之外的人工智能和实践应用场景等模块。本书力图为人工智能初学者提供关于这一领域的全面认识,也为进一步的深入研究建立坚实的基础。一起来看看 《《裂变:秒懂人工智能的基础课》》 这本书的介绍吧!