本文为哈佛大学DASLab自研的CrimsonDB存储系列文章第二篇,完整的系列文章列表见http://daslab.seas.harvard.edu/projects/crimsondb-demo/#publications

CrimsonDB第一篇 Monkey: Optimal Navigable KeyValue Store

与第一篇类似，本文在 Monkey的数学基础之上，通过建模的方式对LSM 的时间复杂度和写放大度进行了建模分析，通过权衡时间复杂度和写放大，提出了lazy compaction的设计方案。本文的核心启发来源于最底层的数据量最多，因此主要得查询开销来自与最底层。第一篇文章提到上层的数据需要的bloom filter内存空间很小，因此上层的数据查询大部分可以通过bloom filter进行优化。那么是否可以通过降低上层的compaction来减少io放大呢，延时上层compact会由于overloap带来部分的查询放大，但是这些放大和降低io的开销相比起来某些时候是可以忽略的，因此可以通过动态调节compaction来达到时间复杂度和io写放大的平衡。

空间放大

在分析空间放大之前，再次简单介绍下tiering compaction和leveling compaction。level层内部不存在overlap，tiering层内部则可能存在overlap。因此对于tiering，极端情况下 如果每一个run之间都存在overlap，那么空间放大为O(T),。对于leveling，由于层内部不存在overlap，层级之间的数据层T倍增长，因此极端情况下L(n-1)的数据都被更新了，此时leveling的空间放大为N(1/T).

IO 放大

通过对点查和scan进行建模复杂度分析，发现主要的查询开销来自于最底层。因为最底层的entry数量最多，同时基于第一篇提到的，上层的run可以通过设置bloom filter来优化查询，因此可以通过延时上层run的compaction来减少io的开销，通过牺牲一定的查询开销来大幅降低merge io，上层的查询开销大部分可以被 bloom filter所处理因此相比于减小IO放大带来的收益这个开销可以忽略不计。

通过delay compaction来降低merge的IO 开销，其实就是在tiering与leveling两种策略之间进行权衡。rocksdb默认的compaction策略是L0 使用了tiering，其他level使用了leveling。本文则更近一步，在除掉最底层level的层级进行进行compaction策略的权衡。

Lazy leveling

lazy leveling的思想是在1到L-1层使用tiering ，在L层使用leveling。通过该策略可以保证在1到L-1层每层之内最多包含T-1个run，在L层最多包含1个run，因此空间放大依然是O(1/T). 与第一篇提到的一样，Dostoevsky 每一层的FPR也是指数递增的。

通过下面的建模分析可以发现，lazy leveling在降低merge IO的同时并不会给查询带来额外大的开销

Fluid LSM-Tree

lazy leveling的思想是L 层使用leveling，其他层使用tiering。将该模式进行抽象可以得出如下通用式子,其中K 表示1到L-1 层的run数量， Z 表示L层的run数量.

• K = 1 and Z = 1 give leveling.
• K = T − 1 and Z = T − 1 give tiering.
• K = T − 1 and Z = 1 give Lazy Leveling

通过该式子尽心建模可以得出如下的复杂度分析

具体哪一层如何选择K和Z 则需要根据具体的负载进行计算权衡。

总结

在所有的领域都不可能存在完美的方案，每一个方案都是对不同功能点之间的取舍。功能点之间的关联几乎都可以抽象成类似存储CAP的选择。本文的核心在于根据实际建模分析，在不同功能点之间抽象出通用模型，并根据负载特征对模型进行迭代选择最优的参数解。