MTree：一种基于分层的键值存储系统，由高性能的层次化数据管理技术驱动

《ACM Transactions on Storage》：MTree: A Tiering-based Key-Value Store Powered by High-performance Hierarchical Data Management

基于LSM树的键值存储在写密集场景下存在显著写放大问题，传统分层压缩策略面临层级过多、键分区不足及优化成本过高等挑战。本文提出MTree方案，通过分层日志与LSM树结合的结构，结合动态键范围分区策略，在维持低成本的条件下将层级数量减少至接近单层，同时优化数据分布使写放大率降至2以下，随机写吞吐量较现有系统提升6.9倍。

　　

摘要

基于日志结构化合并树（LSM树）的键值存储（KV存储）在写入密集型工作负载下提供了显著的性能提升，但存在明显的写入放大（WA）问题。为了减少写入放大，分层压缩策略在KV存储中被广泛采用。然而，基于分层的KV存储存在三个主要问题：首先，LSM树结构中的层级过多会导致较高的读写放大；其次，如果没有键分区支持，这些KV存储会增加写入延迟；仅依赖基于哈希的键分区方案是不够的，因为它不支持范围查询；此外，仅使用基于键范围的分区方案的KV存储会忽略键空间内的键分布情况。第三，现有的具有层级优化的KV存储可能会产生较高的成本。一种常见的减少LSM树层级数量的方法是增加MemTable的大小，但这会消耗更多内存，从而增加成本。因此，在层级优化和成本之间找到平衡至关重要。为了解决这些问题，我们提出了一种基于分层的键值存储方案，该方案利用高性能的分层数据管理技术。我们提出的KV存储将键空间划分为m个部分，每个部分都包含一个LSM树。在本文中，我们将这种KV存储称为MTree。MTree能够在不增加成本的情况下将LSM树的结构层级数量降至接近1。MTree采用了一种分层结构，结合了日志结构和LSM树的特点，通过在日志中积累数据来减少LSM树的层级数量。通过这种分层结构，我们为键范围设计了一种考虑长期和短期键密度分布的分区方案，该方案能够动态调整分区大小，平衡分区内的数据分布，并将大部分数据存储在大型日志中。这样一来，MTree减少了LSM树的层级数量，从而优化了读写放大效果。实验结果表明，MTree将写入放大限制在了2以内，并将现有最先进KV存储的随机写入吞吐量提高了多达6.9倍。