从 https://www.jianshu.com/p/8fb8f2458253 看到了 Dostoevsky, 研究了下论文

tired & level

基本原理

  • stcs:

每一层文件大小按比例增加, 每一层的文件数量固定. 比如 4层文件, 每层大小4倍增长, 则分别是: 100 MB, 400 MB, 1.6 GB and 6.4 GB.

层间compaction, 比如 level(i) -> level(i+1), 当i层四个文件都写满了, 则会触发. 会将 level(i) 的四个文件进行 compaction 放到 level(i+1) 【空间放大的原因】

经典的图, 参考论文

  • level:

每一层的文件大小固定, 文件数量按照层级按比例增长, 比如 4(level 0)、10、100、1000, 每个文件都是 16MB

层间compaction 是当 level(i) 文件数满的时候触发的. 会从 level(i) 中选取一个文件 和 level(i+1) 的10个文件进行compaction, 并写入11个文件 【写放大的原因】

经典的图, 参考论文

写放大

写放大: 一次byte写入, 在磁盘上读写了多少次 (注意: lsm 因为有一次日志写commit-log, 因此至少有一次写放大)

stcs:

O(L), 因为写放大只会放生在层间compaction, 对于图例 4层的 写入, 也就是 5倍写放大

level:

O(T * L), 很严重, 也放在层间, 但是level的模型是, 从 level(i) 选取一个文件, 和 level(i+1) 的10个文件进行compaction, 最终导致11倍的写放大(这里的场景是 层间10倍关系, 10个文件是因为 token range 关系是10, 比如上一层10个文件, 下一层就是100个文件, 一般假设是从100个文件中选取10个有重叠的文件进行compaction)

试验中并没有达到这么多的写放大, 仅仅是11倍, 因为 写入的时间局部性原理(大部分数据是最近修改的, 很少添加新数据或者修改很老的数据), 很多写放大的 overlap 都在 L0/L1 处理了 (L0/L1 的 input sstfile 不止一个)

需要注意的是, 及时是 读多写少的场景, 当读需要走文件, 写放大由于磁盘竞争也会严重影响读, 除此之外, 当 写放大占用太多磁盘带宽导致 compaction 跟不上, 那么大量数据就会停留在 L0, 导致很严重的读放大

空间放大

空间放大: 同一份数据, 被存储了多少遍

STCS 空间放大严重, 试验中最严重可以观测到 8倍, 主要是由于两个原因:

  • input->ouput 的 level compaction 导致的文件临时放大两倍
  • 因为相同一层数据存在 overlap, 那么可能相邻文件存在被删除的数据 (最差情况下, 不同层也存在overlap), 试验得到了8倍 (1.2GB的数据写15次)

level空间放大相对比较轻, 如下:

  • 分层压缩的时候, 假设分层比例是10, 160M文件大小, 因为总是从 level(i) -> level(i+1) 的比例是 1/10, 因此最多重复 11 个文件, 固定大小就是 160 * 11 < 2GB
  • 同一层因为没有overlap, 所以只存在 分层之间的数据重复, 如果 level(larget) 填满了, 3层10倍最多也就 1.11倍, 最差情况下, level(larget) 没有填满, 比如 l2 和 l3 都一样大的时候, 那么存在略大于 2倍的 空间放大

在相同的试验中, 试验2(1.2GB的数据写15次) 略微大于预期的 [1.1, 2] 的放大, 因为 l0 存在overlap 导致的. 试验1符合预期

论文

引入了三个新的设计: lazy leve & Fluid LSM-Tree & Dostoevsky

基本原理

  • Lazy Leveling

只有最后一层进行 level compaction(merge), 其他层不进行merge

  • Fluid LSM-Tree

控制了 largest level 和 其他level 的merge的频率

  • Dostoevsky

Dostoevsky: Space-Time Optimized Evol- vable Scalable Key-Value Store.

论文一开始详细分析了不同情况下 level/tiering 的复杂度.

贴图:

update:

level: O(L * T/B), 每一层都是 T个文件更新, 最差更新L层的次数, 分摊到 B上的entries tiering: O(L/B), 每一层都是直接merge, 最差合并L层的次数, 分摊到 B 上的entries

point lookup:

level: 每一层的误判率, 优化后和level无关 tiering: T * 误判率, 优化后和level无关

short range:

level: O(L), 因为每一层层内不重叠, 每层最多查一次, 最多L层 tiering: O(T * L), 因为每一层重叠, 所以 一层最差T次, 最多L层

long range:

level: tiering:

需要看下

参考