本文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)

为了方便表述，定义了如下的标识符进行指代:

4.png

降低查询开销

最坏情况的查询开销取决于 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 有关。

9.png

另外论文里来对更新开销以及 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 即达到了性能 吞吐的提升。通过数学工具进行分析的思路方法论非常的具有参考意义。