LSM-TREE 存储结构的空间放大

栏目: 数据库 · 发布时间: 6年前

内容简介:根据

log structured merge tree 已经是现代数据库常用的一种数据结构,其优点就是能够将全部操作都转化为写入,从而使磁盘的连续写入优势发挥最大等。但是会带来 写放大空间放大 。但是 读放大写放大空间放大 是一对矛盾体。因此,由于有着不同的取舍,就有了不同的 compaction 算法。使用不同的 compaction 算法,导致的 空间放大 会有不同,但是BigTable, HBase、Cassandra、LevelDB、RocksDB等都使用了 leveled compaction ,则我们根据 leveled compaction 算法来谈谈 空间放大

leveled compaction 拥有最小的 空间放大 ,但是带来很大的 写放大读放大

空间放大产生的原因

根据 LSM 的定义,其将所以的操作都转化为一个新的 op 写入存储结构,增删改查都是一个对应的 op ,当查找对应的KEY时,就查找对应的最新的 op ,如果未找到或者最新的 op 是“删除”,则该KEY不存在,否则返回最新 op 对应的值。因此一个KEY在存储中会对应多个 op ,从而导致实际使用的磁盘空间大于存储中的数据量大小,也就是 空间放大

LSM-TREE 存储结构的空间放大

其中省略一些细节,为了节省存储空间,将这些 op 按层级组织起来,然后从上到下,每层的存储容量依次增加。通常规定

的容量是 增长系数 倍,这个值通常是 10

LSM-TREE 存储结构的空间放大

按照 op 的写入时间顺序,逐层安排。最新写入的在内存中,然后到达 写缓存 容量后,生成一个存储文件放置到L0层,当每一层的文件到达给层容量限制后,就会开启一个 compaction 工作:

LSM-TREE 存储结构的空间放大

当L1的文件总大小超过该层限制后,会继续进行 compaction 工作,会挑选适当的文件合并入L2层:

LSM-TREE 存储结构的空间放大

如果 compaction 后,使得L2层的总大小超过该层的限制,则继续向下 compaction

LSM-TREE 存储结构的空间放大

以此类推,最终将每层的文件大小控制在要求内。

那么我们就可以分析其中产生的空间放大:

首先,我们 忽略 WAL 占用的额外空间 ,因为这个占用的磁盘空间大小是一个常数,通常这个值远小于磁盘容量,所以不太需要关注。

然后,然后分析每个场景的 空间放大

  1. 每层的数据都不重叠,很明显此时 空间放大 为1
  2. 每层的数据都重叠,而且每层数据都填充慢,此时我们按照 增长系数 = 10 ,来计算,总数据容量为最后一层的大小,则 空间放大1.111...
  3. 每层的数据都重叠,但是最后一层数据没有被填充慢,只略微比上一层大一点点,此时我们按照 增长系数 = 10 ,来计算,总数据容量为最后一层的大小,则 空间放大2.011...

实验

ScyllaDB 进行了两个实验,测试不同场景下 leveled compaction空间放大 的实际表现

连续写入新KEY

在这个场景中,连续写入不重复的新KEY。可以看出, 空间放大 几乎为 1

LSM-TREE 存储结构的空间放大

反复修改KEY

在这个场景中,反复修改1.2 GB数据,重复15次。可以看出, 空间放大 的范围为 1.1-2

LSM-TREE 存储结构的空间放大

附录

rocksdb 目前支持4中 compaction 算法,在 Options::compaction_style 可以选择:

参考

5 中间讲了很多不同的 compaction 算法,中间会引用一个概念 run / runs ,在 2 中得到了这个概念的解释:

A run is a log-structured-merge (LSM) term for a large sorted file split into several smaller files. In other words, a run is a collection of sstables with non-overlapping token ranges.

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

数据结构与算法

数据结构与算法

[美] 乔兹德克 (Drozdek, A. ) / 郑岩、战晓苏 / 清华大学出版社 / 2006-1 / 69.00元

《国外计算机科学经典教材·数据结构与算法:C++版(第3版)》全面系统地介绍了计算机科学教育中的一个重要组成部分——数据结构,并以C++语言实现相关的算法。书中主要强调了数据结构和算法之间的联系,使用面向对象的方法介绍数据结构,其内容包括算法的复杂度分析、链表、栈队列、递归技术、二叉树、图、排序以及散列。《国外计算机科学经典教材·数据结构与算法:C++版(第3版)》还清晰地阐述了同类教材中较少提到......一起来看看 《数据结构与算法》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

随机密码生成器
随机密码生成器

多种字符组合密码

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具