本文Monkey: Optimal Navigable Key-Value Store为
哈佛大学DASLab自研的CrimsonDB存储系列文章第一篇,完整的系列文章列表见http://daslab.seas.harvard.edu/projects/crimsondb-demo/#publications
本文的核心是通过对LSM tree进行建模，根据建模分析得出了LSM的一些优化方向，并提出了基于动态调整bloom filter的方式来优化查询性能的方法。
先说结论: 通过在较低层级设置更多的bit降低FPR，不同层级间FPR与层级数i层指数正比可以提高查询效率。通俗点就是由于level越大包含的entry越多，只有分配的bit越少才能减少总的 M(buffer)的使用。下面根据数学模型进行详细的结合分析。
LSM 建模
在LSM 中，内存包含了M(buffer) M(filter) M(point), M(buffer)用户缓存磁盘数据以加速对磁盘数据的访问，M(filter)通过bloom filter进行过滤，可以减少不存在的key对磁盘的访问，M(point) 则存储数据区间到page的指针映射。
对于LSM ，目前主流的存储引擎compaction实现主要包含Tiered和leveled，两种compaction策略的区别如图，本文不做详细展开说明。两种策略的开销分析如下
两种策略其实再试读开销与写开销之间进行平衡，当T为1的时候，Tiering退化为append log，此时写入开销最小，当 T= N*E/M(buffer)的时候 Leveling退化为sorted array，此时查询开销最小。
优化分析
根据上面的建模，以tiered的查询开销为例，因为N E 是固定的，不考虑M(point)的情况下 M(buffer) + M(filter) = M. M 大小也是固定的. 因此可以根据数学模型得出几个优化的方向:
- 调整T的大小以及compact policy的策略
- 调整M(buffer) 以及M(filter) 的分配
- 在 M(filter) 固定的情况下如何调整不同 bloomfilter 的分配来建下 False Positive Ratio (FPR)
为了方便表述，定义了如下的标识符进行指代:
降低查询开销
最坏情况的查询开销取决于FPR，对于leveled，最坏情况下每一层都是出现了FPR，那么最差的查询开销为每一层的累加，由于tiered每层最多可能包含 T-1 个重叠的run，因此可以得出两种policy的最差开销为
根据公式3 和 4 问题可以转化为在R 一定的情况下，如何使 M(filter) 最少。数学证明部分此处不做详细说明，如果感兴趣可以去看论文附录的证明环节。直接看论文中的结论，根据公式5 和 6 可以得出，在R 一定的情况下，以指数方式递增提升FPR可以实现M(filter) 最小。这里和传统的LSM 最大的不同是传统的LSM 每一层都是同样的FPR，传统的设计会导致最底层的level占用大量的内存。通过降低 M(filter)的大小， 倒换个角度，在M(filter) 固定的情况下，monkey的方式会使得 R 最小。
查询开销指标化
传统的调优很多时候都是基于经验测试值，对于不同的负载这会导致调优变得异常困难。通过将开销进行数字化，可以快速根据具体的负载调整不同的参数来使得负载开销最小化. 对于查询到不存在的数据的场景，极端开销根据 公式4 5 6可以得出公式 7 8。 对于最差在最底层查询的到场景开销则为：V = R - P(L) + 1, 因此该数据肯定在最后一层被读取到，因此只需要加上1即可。R 取决于 R(filter) 于 R(unfiltered) 之和，这两个值则受 M(filter) 影响。当T =2时，M(threshold)的值为1.44 ，而传统的LSM 实现 bit/entry 为10，因此传统的实现查询复杂度为 R(filter). 此外还可以看到 R 与层数无关，也与entry大大小无关，只与entry num有关。
另外论文里来对更新开销以及range查询开销进行了建模，详细模型分析可以去原文。
merge policy与 T 的调节
前面提到不同的 T 以及 merge policy 会影响查询以及更新的性能开销，如何选择合适的T以及merge policy 以达到最优解，论文的附录部分给出了详细的迭代计算过程。r v q w 分别表示不同的操作类型在总体负载中的占比，基于此可以根据负载信息动态计算出合适的 T 以及 merge policy。
动态调整filter
论文的正文部分，也就是降低查询开销的部分，基于entry size固定的前提进行bit/entry 的计算， 但是实际负载下entry size大多数不一样的，在论文的附录部分，给出了对于entry size 动态变化的情况下如何动态调整filter 的计算策略。为了实现这一方法，monkey在每一个run中额外保存了 metadata信息记录每个run的entry num。结论基本以上述一直，让level小的run拥有更多的bit能有效降低R
总结
本文通过数学推导计算得出了bloom filter的优化算法，通过调整bloom filter即达到了性能 吞吐的提升。通过数学工具进行分析的思路方法论非常的具有参考意义，是时候好好复习下数学了。
