（清华大学软件学院，北京 100085）

0 引言

日志结构合并树（Log Structure Merge-tree，LSM）［1］存储结构在非关系型数据库（Not only SQL，NoSQL）尤其是时序数据库中应用广泛，例如OpenTSDB［2］、LevelDB［3］、KairosDB［4］、InfluxDB［5］等均采用了LSM 结构，从而实现了对海量键值（Key-Value，KV）数据有序存储及低延迟查询。

LSM 核心思想是通过多次合并数据，将数据集组织成有序的、大块的文件［6］。对于实时写操作，LSM 系统只更新内存，再批量将内存中的数据以块数据的形式刷到磁盘，并通过特定合并策略异步整理数据文件为多层。对于读操作，LSM系统从内存缓冲区、磁盘文件逐层地查找所需的数据。在传统的LSM 结构（以RocksDB 的LSM 结构为例［7］）中，通常以C0、C1、…、Ck的多层的方式存储数据文件，层与层之间保持固定比例M=（Size（Ci+1）/Size（Ci））（Size（Ci）表示Ci层的文件大小阈值）。当Ci层达到阈值时，就将Ci层合并（compaction）到Ci+1层去，每次这样的合并操作都要读写Size（Ci+1）+Size（Ci）字节的数据。该合并流程保证了仅C0、C1层的文件之间存在乱序数据，从C2、C3、…、Ck多层文件中的所有key 都是有序的［8］。时序数据是指数据可以沿时间维度排序的数据。因此，LSM 通过合并带来的数据排序特性十分适用于时序数据管理。

然而，在写入负载较高时，异步的LSM 文件合并有可能跟不上数据的入库速度，造成C0层数据的堆积。由于C0层是最新写入的数据，这就造成系统对近期写入的数据（往往为热数据）的查询延迟较高。此外，由于LSM 在合并过程中需要占用较多的读写（Input Output，IO）资源用于读写数据和中央处理器（Central Processing Unit，CPU）资源用于排序，一些系统（如Cassandra）等还限制了LSM 的合并速率，进一步加剧了对近期写入数据的查询延迟；但是，时序数据对刚刚写入的数据的查询需求最为频繁，为此，如何在保留LSM 合并后实现数据排序特性、支持历史数据快速查询的基础上，降低LSM对时序数据近期查询的延迟影响，成为需要解决的关键问题。……