内容简介:根据
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
,从而导致实际使用的磁盘空间大于存储中的数据量大小,也就是 空间放大
。
其中省略一些细节,为了节省存储空间,将这些 op
按层级组织起来,然后从上到下,每层的存储容量依次增加。通常规定
增长系数
倍,这个值通常是
10
:
按照 op
的写入时间顺序,逐层安排。最新写入的在内存中,然后到达 写缓存
容量后,生成一个存储文件放置到L0层,当每一层的文件到达给层容量限制后,就会开启一个 compaction
工作:
当L1的文件总大小超过该层限制后,会继续进行 compaction
工作,会挑选适当的文件合并入L2层:
如果 compaction
后,使得L2层的总大小超过该层的限制,则继续向下 compaction
:
以此类推,最终将每层的文件大小控制在要求内。
那么我们就可以分析其中产生的空间放大:
首先,我们 忽略 WAL
占用的额外空间 ,因为这个占用的磁盘空间大小是一个常数,通常这个值远小于磁盘容量,所以不太需要关注。
然后,然后分析每个场景的 空间放大
:
- 每层的数据都不重叠,很明显此时
空间放大
为1 - 每层的数据都重叠,而且每层数据都填充慢,此时我们按照
增长系数 = 10
,来计算,总数据容量为最后一层的大小,则空间放大
为1.111...
- 每层的数据都重叠,但是最后一层数据没有被填充慢,只略微比上一层大一点点,此时我们按照
增长系数 = 10
,来计算,总数据容量为最后一层的大小,则空间放大
为2.011...
实验
在 ScyllaDB
进行了两个实验,测试不同场景下 leveled compaction
的 空间放大
的实际表现
连续写入新KEY
在这个场景中,连续写入不重复的新KEY。可以看出, 空间放大
几乎为 1 。
反复修改KEY
在这个场景中,反复修改1.2 GB数据,重复15次。可以看出, 空间放大
的范围为 1.1-2 。
附录
rocksdb
目前支持4中 compaction
算法,在 Options::compaction_style
可以选择:
-
kCompactionStyleLevel
,如上文所述。 -
kCompactionStyleUniversal
,本质上是tiered compaction
算法,写放大
比较低,但是读放大
和空间放大
比较高。 -
kCompactionStyleFIFO
,通常用于几乎不修改的场景,比如消息队列、时序数据库等。 -
kCompactionStyleNone
,关闭自动compaction
,可以手动发起。
参考
注 : 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.
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 让 Vuepress 支持图片放大功能
- jquery实现放大镜简洁代码
- jQuery:案例11 放大镜效果
- 随机放大的不规则瀑布流
- 为BlueLake主题增加图片放大效果
- Memcache UDP 反射放大攻击技术分析
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。