# Dostoevsky -- Better Space-Time Trade-Offs for LSM-Tree

## Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging

### 0x00 引言

..., we introduce Lazy Leveling, a new de-sign that removes merge operations from all levels of LSM-tree but the largest. Lazy Leveling improves the worst-case complexity of update cost while maintaining the same bounds on point lookup cost, long range lookup cost, and storage space. We further introduce Fluid LSM-tree, a generalization of the entire LSM-tree design space that can be parameterized to assume any existing design. Relative to Lazy Leveling, Fluid LSM-tree can optimize more for updates by merging less at the largest level, or it can optimize more for short range lookups by merging more at all other levels.
We put everything together to design Dostoevsky, a key-value store that adaptively removes superfluous merging by navigating the Fluid LSM-tree design space based on the application workload and hardware.


### 0x01 基本思路

Dostoevsky的内容主要就是三点：

• Lazy Leveling，第一点是最核心的，基本思路就是结合LSM-tree中leveing和tiering合并策略，在除了最后(也就是最大的一层)使用leaving的方法，在其余的层使用的是tiering的方法。这么做基于这样的考虑：在上面的表格给出的复杂度可以看出，在较小的levels上面使用leveling的方法，会明显的增加更新操作的成本，而对查找的提高却不是很明显。这样Lazy Leveling的思路就是只在largest level使用level的方法。下面的图是使用这种方法的一个复杂度的分析，

1. K =1 and Z =1时就是leveling模式；
2. K = T −1 and Z =T −1就是tiering模式；
3. K =T −1 and Z =1就是lazy leveling模式；

这里Paper中也对这样得方式进行了具体得分析，下面是这样的策略的一个复杂度：

• Dostoevsky，Dostoevsky的目的就是在一定限制条件下将这三个参数调整的最优的值，

We now introduce Dostoevsky to find and adapt to the best tuning of Fluid LSM-tree subject to a constraint on space-amplification. Dostoevsky models and optimizes throughput with respect to up- date cost W in Equation 12, zero-result point lookup cost R in Equation 10, non-zero result point lookup cost V in Equation 8, and range lookup cost Q in Equation 11. It monitors the proportion of these operations in the workload and weights their costs using coefficients w, r, v, and q, respectively.


下面几个计算方式: $$\\ Equation 12: W = \frac{\phi}{\mu\cdot B}\cdot(\frac{T-1}{K+1}\cdot(L-1)+\frac{T-1}{Z-1}), \\ Equation 10: R = e^{-\frac{M}{N}\cdot\ln(2)^{2}}\cdot Z^{\frac{T-1}{T}}\cdot K^{\frac{1}{T}}\cdot \frac{T^{\frac{T}{T-1}}}{T-1},\\ Equation 8: V = 1+R-p_{L},\\ Equation 11: Q = K\cdot(L-1)+Z+\frac{1}{\mu}\cdot\frac{s}{B}\cdot(Z+\frac{1}{T}), \\$$ .

利用上面的公式和下面的the weighted worst-case throughput τ计算公式： $${,} \\ Equation 14:\tau = \Omega^{-1}\cdot(\omega\cdot W + r\cdot R + v\cdot V + q\cdot Q)^{-1},$$ .

通过迭代K Z和T的可能的取值来计算求得 τ得最大值。迭代的复杂度： $$\\ T可能的取值的范围的量级为 \lceil\log_{2}(\frac{N}{PB})\rceil, \\ 而由于Equation 14对于K和Z来说都满足凸函数的性质(可以参考数据优化和凸优化的教材)，\\ 它们可以在对数时间内找到一个T下面的最优的值，所以(这里没有具体证明)复杂度就是: \\ O(\log_{2}(\frac{N}{B\cdot P})^{3}),$$

## 参考

1. Niv Dayan, Stratos Idreos. 2018. Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging . In Proceedings of 2018 International Conference on Management of Data (SIGMOD’18). ACM, New York, NY, USA, 16 pages. https://doi.org/10.1145/3183713.3196927.
2. Monkey: Optimal Navigable Key-Value Store, SIGMOD 2017.