知识卡片
LSM-tree用分片把写放大从T降到1
LSM-tree靠”合并(compaction)”维持每层数据全局有序,但这个维持 有序的代价是真实写入磁盘的数据量远大于用户实际写入的数据量—— 这就是写放大。因为LevelDB相邻层之间的存储空间是按固定倍数(如 10倍)递增的,合并一个文件时要把它和下一层所有key有重叠的文件 一起读入内存、归并、再整体写回下一层,随着数据从Level 1一路 迁移到Level 6,写放大系数可能超过50倍。要压低这个代价,思路是 让每次合并不必牵动整层数据:分区把每一层拆成多个互不重叠的 区域,一次合并操作只需要处理其中一个小分区,减少了单次合并 占用的磁盘空间和对其他读写的资源挤占;分片则更进一步,让每一 层内部允许存在多个”范围重叠但内部有序”的分片,某一层需要向 下合并时,不需要再和下一层做一次全量归并排序,而是先把本层 的所有分片先归并成一个有序整体、再作为一个新分片直接写入下层—— 这样每次合并的写放大就能从原来的T(层间大小比例)降到1。这个 机制的关键洞察是:写放大的根源是”每次合并都要重新触碰整层 数据”,而分区/分片本质是把”整层”拆成更细的可独立处理单元, 用更小的合并粒度换取更低的重复写入代价。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《新型数据库系统:原理、架构与实践》第4章"键值数据库
技术"4.4.3节"基于LSM-tree的存储引擎"(源文件:
_epub-src/EPUB/xhtml/Section0001_0006.xhtml)
- 结论依据:原文明确"很多专家尝试减少LSM-tree的写放大……优化
写性能主要的方法为分区和分片……当采用分片机制时,当某一层
发生合并时,并不需要与下层执行归并排序,而是将该层的所有
分片执行归并排序,将排序后的分片作为一个新分片写入下层,
从而将每次合并写放大从T下降到1",直接给出分片机制降低写
放大的具体原理。
- 原始内容:分片意味着每一层存在多个范围重叠的键值区域,每个
区域内部是有序的……将该层的所有分片执行归并排序,将排序后
的分片作为一个新分片写入下层,从而将每次合并写放大从T下降
到1(其中T为不同层间的大小比例)。