面向时序数据的两阶段日志结构合并树文件合并框架

（清华大学软件学院，北京 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对时序数据近期查询的延迟影响，成为需要解决的关键问题。

针对上述问题，本文分析了面向时间序列数据的近期热数据即席查询和历史冷数据分析型查询这两类查询的特点，设计了同时优化这两类查询的两阶段LSM 合并策略：在第一阶段，仅将乱序文件合并为顺序文件，以实现最快速度的近期热数据整理；在第二阶段，将顺序小文件合并为大文件，以实现大块数据的读取。此外，为了减少第一阶段的LSM 工作量，在实时数据写入时，直接将局部有序的数据写入C1层，从而减少C0层的数据量。与传统LSM 合并策略下的系统的读写性能对比结果表明，两阶段的LSM 合并能提高数据的合并效率，并且能够有效提高数据的查询效率。论文的工作与贡献如下：

1）研究了主流NoSQL 数据库合并模块的设计，发现基于LSM 合并得到的数据块并不是越大越好，而是与用户特定查询习惯有关［9］。为此，调研了时序数据即席热数据和分析型冷数据查询的访问特点。

2）设计并实现了两阶段LSM 两阶段合并框架，并在时序数据库Apache IoTDB中进行了验证。

3）在两阶段框架中实现了一些特定的合并策略，并与传统LSM合并策略下的系统读写性能进行对比。

1 研究背景

本章主要从传统的LSM 出发，分析LevelDB、InfluxDB［10］的变种LSM结构。

1.1 LSM

LSM 树是专门为键值（KV）存储系统设计的，其思想主要是利用磁盘的顺序写来加速海量数据的存储和读写。传统的LSM是一个多层结构，上层小下层大，其中C0层保存了所有最近写入的键值数据。这个内存结构是有序的，并且可以随时原地更新，同时支持随时查询。剩下的C1到Ck层都在磁盘上，每一层都是一个在key上有序的结构，如图1所示。

读写放大是LSM 树合并的主要问题［11］。这里本文以RocksDB 的合并算法（Level Style Compaction）为例，这种合并机制每次会拿Ci层的所有文件和Ci+1层合并，层与层之间的比例M=(Size(Ci+1)/Size(Ci))，这样子在最坏的情况下（写入一条数据导致每一层合并），会重复读写Size(C1)+Size(C2)+…+Size(Ci)的数据，这也是各类LSM 的变种致力于解决和优化的问题。

图1 传统LSMFig.1 Traditional LSM

1.2 LevelDB

LevelDB的合并过程与引言中提到的RocksDB不同，它不选取上一层的所有数据和下一层进行合并，而是当Ci层达到阈值时，就要在Ci层选择一个文件合并到Ci+1层去，由此保证除了C0层，其他层的key都是全局有序的［12］。

这种合并方式相比RocksDB 来说，大大减少了合并造成的写放大，对于上文所说的最坏的情况来说，假设一个文件的大小Size(B)=1 MB，那么当系统要写入一个新数据，只需要重新对C0层和C1层进行合并，读写1 MB的数据。

传统LSM 和LevelDB 的LSM 策略均未面向时间序列数据的查询进行优化。

1.3 InfluxDB

InfluxDB 基于LSM 自研了TSM（时间结构合并树），主要采用了LevelCompaction［13］策略，并针对历史时序数据的管理进行了不同时间序列分离和单时间序列整理两部分优化。

1）LevelCompaction：InfluxDB 将TSM 文件分为4 个层级（C1C2C3C4），compaction 只会发生在同层级文件内，同层级的文件compaction 后会晋升到下一层级，相当于基于对LSM 固定了合并的最大层数为4。

2）IndexOptimizationCompaction：因为固定了层级，所以C4层文件会越来越大，使查询效率变低，所以这种合并的主要作用就是将同一时间序列下的数据合并到同一个TSM 文件中，尽量减少不同TSM文件间的时间序列重合度。

3）FullCompaction：InfluxDB在判断某个Shared（TSM中的一个时间块）长时间没有新数据后，会做FullCompaction 对本块数据进行规整，提高压缩率。

这种合并方式相比RocksDB、LevelDB 更接近于时间序列数据的存储，因为限制了总的合并层数和合并次数，写放大不会因为数据量的不断增大不断提高。此外，InfluxDB 通过两部分优化工作，确保了在大量数据下，访问历史数据仍然能够保持较低延迟。

1.4 Cassandra

Cassandra 基于传统的LSM 结构开发了四种不同的合并策略，分别适用于不同的场景。

1）STCS（Size Tiered Compaction Strategy）：这是一个典型的Size-Tired Compaction 策略。当有（默认4个）数据块的大小相似的时候，STCS 便会启动。压缩过程将这些数据块合并成一个大的数据块。这种策略在写密集的负载中工作良好，当需要读数据的时候，需要尝试读取多个数据块来找到一行中的所有的数据。策略无法保证同一行的数据被限制在一小部分的数据块中。同时可以预测删除的数据是不均匀的，因为数据块的数量是触发压缩的条件，并且数据块可能增长的不够快以便合并旧的数据。

2）TWCS（Time Window Compaction Strategy）：TWCS 通过使用一系列的时间窗口将数据块进行分组。在compaction 阶段，TWCS 在最新的时间窗口内使用STCS 去压缩数据块。在一个时间窗口的结束，TWCS 将落在这个时间窗口的所有的数据块压缩成一个单独的数据块。

3）LCS（Leveled Compaction Strategy）：LCS 用于解决STCS在读操作上的问题。当数据块的体积增长到一个不大的体积，它被写入第0 级。在每个从C1开始的级别，单个级别中所有的数据块都确保没有重复数据，在此基础上，LCS 会分割数据块以确保文件大小相同，每个级别都是上一个级别大小的固定倍数，以此减少查询时磁盘的seek次数。

4）DTCS（Date Tiered Compaction Strategy）：DTCS 和STCS很像，但是它不是基于数据块的大小进行压缩的，DTCS 通过判断数据块的创建时间进行压缩。使用这种策略压缩的数据块可以高效读取近期数据（上一小时的数据），但会导致过期数据不容易写入。

2 两阶段合并框架

2.1 时序数据的访问特点

用户对于时序数据的访问一般来说需要返回有序的数据段，并且有以下两种常用的访问类型［14］：

1）面向近期写入数据的即席查询。时序数据库的一个重要作用是进行实时监控，在这种场景下，用户往往读取最近写入的一小段时间的数据。例如，读取最近5 min的数据。因此，这类查询的特点是：①访问近期写入的数据；②访问的数据时间段较短；③要求较高的系统响应速度。

2）面向历史数据的分析型查询。在分析应用中，用户往往需要获取一天、一个月甚至一年的数据，才能进行规律性总结、训练模型等。因此，这类查询的特点是：①访问不太热的历史数据；②访问的数据时间段较长。

传统LSM 通过多层级合并，能够高效支持第二类查询。本章通过设计两阶段LSM，解决由于C0层堆积导致的第一类查询性能下降的问题。

2.2 核心设计

2.2.1C0层拆分

在传统LSM 中，内存中的数据（即C0层）在到达一定大小后会被刷写到磁盘上形成C1层。C0层的多次刷写造成了C1层多个文件之间存在乱序。在时间序列数据库中，同一条时间序列的数据是以时间戳排序的。因此，通过在内存中记录每条时间序列的最新时间戳，可以准确判断出该序列新写入的数据点与C1层已有的数据相比是顺序的（即时间戳更大）还是乱序的（即时间戳更小）。

利用上述特性，本文将LSM 中的C0层内存结构拆分为乱序缓冲区与顺序缓冲区。对于C0层顺序缓冲区的数据，当其大小达到阈值时，将被直接刷写入C2层。对于C0层的乱序数据则只能被刷写入C1层，并等待LSM的文件合并。

在时间序列数据应用中，数据在多数情况下是沿着时间戳维度增序到达的。因此，在上述改造下，C1层仅存在少量的乱序数据。那些近期写入的在时间维度上顺序递增的数据，则直接在C2层。

对于近期数据的即席查询来说，其访问的数据往往来自内存、C1层和C2层。由于C2层的多个文件之间保持有序（从而可以在时间维度上进行剪枝查询），因此在C2层的近期数据查询延迟较低。内存中的数据由于不涉及IO 操作，其查询延迟也较低。因此，如何加速近期数据的即席查询，其关键就在于如何将少量的C1层数据快速合并为C2层的有序数据。

2.2.2 两阶段合并框架

如图2 所示，本文将合并过程分为两个阶段，乱序文件合并为顺序文件和顺序小文件合并为大文件。乱序数据为C1层，第一阶段会将乱序数据合并为C2层的顺序数据。第一阶段完成后，第二阶段将顺序小文件合并为更规整化的顺序大文件为C3层或更多的Cn层。C3C4…Cn的写入和合并由不同的顺序文件合并策略决定。

在该设计中，第一阶段的文件合并的目的即快速减少乱序数据，从而支持高效的近期数据的即席查询。显然地，与传统LSM 相比，在进行相同多次IO 操作时，第一阶段文件合并能比传统LSM 将更多的乱序数据整理为顺序数据。第二阶段的文件合并的目的是生成大块的数据文件，从而减少分析型查询批量读取数据时的频繁磁盘seek操作。

图2 两阶段的文件合并Fig.2 Two-stage file compaction

在实际应用中，可以根据系统的查询负载进行两阶段合并的资源分配。例如，当用户频繁进行大量近期数据即时查询时，合并乱序数据的优先级就更高，将小文件合并为大文件就不是很必要，反而会因为占用过多IO 和CPU 资源而阻塞系统的即时查询和写入性能。在这种情况下，可以给第一阶段较多的线程资源、并增加第一阶段的合并触发频率，从而加速第一阶段的合并，再慢慢运行第二阶段文件合并，最终将小文件合并为大文件。

与传统LSM 相比，两阶段文件合并的一个负面影响是增大了写放大。为了减少写放大，本文借鉴MapReduce 计算框架中在Map阶段内增加Combiner的思想对两阶段框架进行改造：当系统的CPU 资源较为富裕时，本文可以在第一阶段执行乱序文件合并为顺序文件时，同时将所涉及的小文件合并成大文件，从而减少第二阶段的触发频率，由此减小两阶段框架的写放大。并且，在第一阶段的乱序合并过程中，本文会尽可能地保留原文件的数据块，选择写放大最小的目标顺序文件写入方法。

2.3 多种合并策略

两阶段合并框架仅定义了第一阶段主要目的是进行乱序数据合并，第二阶段进行小文件合并。在每个阶段中，可以采用工业界和学术界现有的各种合并策略进行文件的合并。

为了更好地说明核心设计思想，本文在实现两阶段合并模块的框架下，同时实现了四种文件合并策略。1）INPLACE：该策略用于第一阶段文件合并，合并后的乱序数据将被写入原文件中，其目的是以较少IO 的方式完成文件乱序到顺序的合并。2）SQUEEZE：混合合并策略，在完成乱序文件合并的同时完成一部分顺序文件合并的工作，合并后的乱序数据将被统一整理到新文件中，其目的是减少写放大。3）REGULARIZATION：小文件合并策略，其目的是以高效率的方式完成小文件到大文件的合并，并确保文件中每一条时间序列的连续数据块阈值达到最低标准。4）INDEPENDENCE：小文件合并策略，其目的是在REGULARIZATION 基础上保证每个文件有且仅有一个设备的数据，方便进行单设备查询的用户获得更快的查询效率。该策略与InfluxDB的优化类似。

2.4 写放大评估

上文中提到，两阶段的文件合并策略除了最基础的C0和C1层，可以将最终的合并结果文件配置成Cn层。在实际时序数据库中，数据块并不是越大越好［15］，因此本文采用合并为n=3的结构进行评估。

在两阶段的合并框架中，写入一条无规律乱序数据最多会造成Size(C0B) +Size(C2B)（其中Size(CiB)为Ci层数据块的平均大小）的数据重复读写，写入一条有规律乱序数据最多造成(Size(C0B) +N1*Size(C1B) +N2*Size(C2B))/M（其中N1、N2表示有与乱序文件有重叠的顺序文件，M表示同时一起进行读写的当时乱序数据点数量，N1+N2 ≪M）的数据重复读写。这与RocksDB 的Size(C0)+Size(C1)+Size(C2)相比，减少了在合并模块造成的写放大。

3 实验与评估

本章首先设计实验验证在相同写放大因子下（即进行相同多次IO 操作后），两阶段框架带来的近期数据即席查询的收益。进而，本章设计实验对比在Apache IoTDB 系统中，传统LSM（RocksDB 的LSM 实现和合并方法）和两阶段LSM 合并框架在内存占用和数据读写性能的差异。

3.1 实验环境

本实验使用一台配置如表1的服务器。

表1 实验环境配置Tab.1 Configuration of experimental environment

3.2 实验数据

实验采用时间序列数据库性能测试工具IoTDBBenchmark［16］产生数据，然后分别使用两阶段合并以及传统LSM 合并对数据进行合并操作，直到合并到第n层（n=3）为止，然后再模拟客户端对以上两者的合并结果进行查询测试。测试工具共创建1 000 条时间序列（10 个设备，每个设备100个传感器），每个序列写入100 000 个数据点。每个序列的数据均为64 位浮点数，并按照泊松分布以10%、30%、50%的比例生成时间戳乱序的数据。顺序数据中，相邻两个数据点时间戳相差1 s。

在第一阶段本文采用SQUEEZE 策略，在第二阶段本文采用REGULARIZATION 策略。对于传统LSM 合并的参数配置，本文设置C0层为100 个点，层与层之间比例为10，整个LSM树合并结果也是三层。

3.3 性能测试

3.3.1 相同写放大时的查询收益对比

对面向近期写入数据的即席查询而言，乱序文件合并比小文件合并更重要。在本次实验中，本文首先在原始写入的数据上进行查询（即在包含10%、30%、50%乱序数据的数据集上进行查询），其查询代价作为基准。然后，在相同写放大下（即在文件合并过程中进行相同次数的IO 操作后）进行传统LSM 和两阶段LSM 的查询测试。在实际实验中，本文以两阶段框架下第一阶段完成全部合并时的写放大值为准，停止传统LSM 的文件合并进程，此时传统LSM 仅合并了10%、30%、50%的乱序数据（即还剩下9%、21%、25%的乱序数据）。

测试结果如图3所示，随着乱序数据的增多，传统LSM 对原始查询的优化比例逐渐提高（从10%乱序时的15%到50%乱序时的110%），而完成了第一阶段合并后查询所需读数据块的次数是一个定值（且远小于原始数据和传统LSM 合并后所需查询次数），乱序数据比例越大，这种对即席查询的优化越明显。可见，在相同写放大下，先合并乱序数据显然优于传统LSM。

图3 每次查询平均读数据块次数Fig.3 Average number of read chunks per query

3.3.2 历史数据分析查询

接下来，本文对传统LSM 和两阶段LSM 合并完的结果进行测试，传统LSM 与两阶段LSM 的结果文件相比原始文件均有了极大的压缩，LSM 合并后文件压缩至原来的1/4，两阶段合并后文件压缩至原来的1/2.5，这是因为传统LSM最后一层的数据块大小相比两阶段LSM 大很多，但往往对用户的查询来说，不需要这么大的单个数据块，太大的数据块提高了数据块的读取延迟和解析延迟，造成了更多的读放大。

对合并后的结果进行读写性能测试，写延迟几乎没有变化，两阶段LSM 相比传统LSM 优化了约10%。读延迟优化则比较明显，降低了约20%。这是因为对于两阶段LSM来说，本文可以灵活控制合并后的结果文件数据块大小，使其既不太大，读盘次数也不过多，更符合查询规律，也就提高了查询性能。

综合上述结果，相比传统LSM，两阶段LSM在历史数据分析查询方面没有过大的影响，并能使用户更加灵活地控制结果数据块大小，达到贴合查询规律以提升读写性能的目的。

图4 合并后文件大小Fig.4 File size after compaction

4 结语

本文针对时序数据的查询需求，对LSM 文件合并流程进行了改进，设计了两阶段文件合并框架。该框架通过分离乱序数据整理和小文件整理这两个任务目标，使得系统能够尽快完成乱序数据整理，带来近期写入数据查询的性能优化。

为验证框架的有效性，本文在Apache IoTDB 中同时实现了RocksDB的传统LSM文件合并策略和两阶段文件合并框架并进行对比实验，实验表明，该框架与传统LSM 合并相比，显著提高了即席查询的效率，并且用户可以通过灵活配置结果文件大小，提高历史数据分析查询效率。

未来，将继续在以下方面展开工作：

1）优化两阶段合并框架的调度算法，当前的两阶段合并只是默认在固定的时间间隔下每次顺序执行，但没有对冷热数据及查询负载进行感知。

2）在内存和C0层之间增加基于last 文件的热合并算法，避免在内存极端受限场景下C1层文件过小导致的读写放大，并提高后续文件合并效率。

3）设计和研发更多动态的合并策略，当前的合并策略只保证了目标文件的写入、生成和大小控制，这需要数据库管理员有一定的调参能力，因此接下来本文还会实现更加动态的算法配置策略，尽可能提高算法的易用性。