InfluxDB 存储引擎和时间结构合并树 (TSM)

InfluxDB 存储引擎看起来非常像 LSM 树。它有一个写前日志和一组只读数据文件，这些文件在概念上类似于 LSM 树中的 SSTables。TSM 文件包含排序、压缩的系列数据。

InfluxDB 将为每个时间块创建一个 shard。例如，如果您有一个持续时间无限的 retention policy，将为每个 7 天的时间块创建 shards。每个这些 shards 映射到一个底层存储引擎数据库。每个这些数据库都有其自己的 WAL 和 TSM 文件。

我们将深入研究存储引擎的每个部分。

存储引擎

存储引擎将多个组件连接在一起，并提供存储和查询系列数据的外部接口。它由多个每个具有特定角色的组件组成：

• 内存索引 - 内存索引是跨分片的共享索引，提供对测量、标签和系列的快速访问。该索引用于引擎，但并不特定于存储引擎本身。
• WAL - WAL是一种写优化的存储格式，允许写入持久化，但查询并不容易。写入WAL的内容会附加到固定大小的段上。
• 缓存 - 缓存是WAL中存储数据的内存表示。它在运行时被查询，并与存储在TSM文件中的数据合并。
• TSM 文件 - TSM 文件以列式格式存储压缩的系列数据。
• 文件存储 - 文件存储介导对磁盘上所有 TSM 文件的访问。它确保在替换现有文件时，TSM 文件以原子方式安装，并移除不再使用的 TSM 文件。
• 压缩器 - 压缩器负责将优化较差的缓存和TSM数据转换为更适合读取的格式。它通过压缩序列、删除已删除的数据、优化索引和将较小的文件合并为较大的文件来实现这一点。
• 压缩计划器 - 压缩计划器确定哪些TSM文件准备进行压缩，并确保多个并发的压缩不会相互干扰。
• 压缩 - 压缩由针对特定数据类型的各种编码器和解码器处理。一些编码器相对固定，总是以相同的方式编码相同类型的数据；而其他编码器根据数据的形状切换其压缩策略。
• 写入者/读取者 - 每种文件类型（WAL段，TSM文件，墓碑等）都有用于处理这些格式的写入者和读取者。

前写日志 (WAL)

WAL被组织为一组文件，看起来像 _000001.wal。文件编号是单调递增的，称为WAL段。当一个段的大小达到10MB时，它被关闭并打开一个新的段。每个WAL段存储多个压缩的写入和删除块。

当写入操作发生时，新数据点会被序列化，使用 Snappy 压缩，并写入一个 WAL 文件。 文件会被 fsync，并在返回成功之前，数据会被添加到内存索引中。 这意味着将数据点进行批处理是实现高吞吐量性能所必需的。 （对许多使用案例而言，最佳批处理大小似乎是每批 5,000-10,000 个数据点。）

WAL中的每个条目遵循TLV标准，其中一个字节表示条目的类型（写入或删除），一个4字节的uint32表示压缩块的长度，然后是压缩块。

缓存

缓存是当前存储在WAL中的所有数据点的内存副本。 这些点按键组织，键是测量、tag set和唯一的field。 每个字段都保持为自己的时间排序范围。 缓存数据在内存中时不被压缩。

对存储引擎的查询将会将来自缓存的数据与来自TSM文件的数据合并。查询是在查询处理时从缓存中制作的数据的副本上执行的。这样，在查询运行期间到来的写入将不会影响结果。

发送到缓存的删除操作将清除给定键或给定键的特定时间范围。

缓存公开了一些用于快照行为的控制选项。最重要的两个控制是内存限制。存在一个下限，cache-snapshot-memory-size，当超过该限制时，将触发快照到TSM文件并移除相应的WAL段。还有一个上限，cache-max-memory-size，当超过该限制时，将导致缓存拒绝新的写入。这些配置有助于防止内存不足的情况，并对以比实例能够持久化更快速度写入数据的客户端施加反压。内存阈值的检查在每次写入时都会发生。

其他快照控制是基于时间的。 空闲阈值，cache-snapshot-write-cold-duration，如果在指定的时间间隔内没有收到写入，则强制缓存快照到TSM文件。

内存中的缓存在重启时通过重新读取磁盘上的WAL文件来重新创建。

TSM 文件

TSM 文件是一组只读文件，这些文件是内存映射的。 这些文件的结构看起来与 LevelDB 或其他 LSM 树变体中的 SSTable 非常相似。

一个TSM文件由四个部分组成：头部、块、索引和脚注。

+--------+------------------------------------+-------------+--------------+
| Header |               Blocks               |    Index    |    Footer    |
|5 bytes |              N bytes               |   N bytes   |   4 bytes    |
+--------+------------------------------------+-------------+--------------+

头部是一个魔术数字，用于识别文件类型和版本号。

+-------------------+
|      Header       |
+-------------------+
|  Magic  │ Version |
| 4 bytes │ 1 byte  |
+-------------------+

区块是CRC32校验和与数据对的序列。
区块数据对文件是不可见的。
CRC32用于块级错误检测。
区块的长度存储在索引中。

+--------------------------------------------------------------------+
│                           Blocks                                   │
+---------------------+-----------------------+----------------------+
|       Block 1       |        Block 2        |       Block N        |
+---------------------+-----------------------+----------------------+
|   CRC    |  Data    |    CRC    |   Data    |   CRC    |   Data    |
| 4 bytes  | N bytes  |  4 bytes  | N bytes   | 4 bytes  |  N bytes  |
+---------------------+-----------------------+----------------------+

后面的块是文件中块的索引。 索引由按键和时间字典顺序排列的一系列索引条目组成。 键包括测量名称、标签集和一个字段。 每个点的多个字段在TSM文件中创建多个索引条目。 每个索引条目以键长度和键开始，后面跟着块类型（float、int、bool、string）和随后的索引块条目数量。 每个索引块条目由块的最小和最大时间、块在文件中的偏移量以及块的大小组成。 TSM文件中包含键的每个块都有一个索引块条目。

索引结构可以有效地访问所有块，并能够确定与访问给定键相关的成本。 给定一个键和时间戳，我们可以确定一个文件是否包含该时间戳的块。 我们还可以确定该块所在的位置以及检索该块需要读取多少数据。 知道块的大小，我们可以有效地配置我们的IO语句。

+-----------------------------------------------------------------------------+
│                                   Index                                     │
+-----------------------------------------------------------------------------+
│ Key Len │   Key   │ Type │ Count │Min Time │Max Time │ Offset │  Size  │...│
│ 2 bytes │ N bytes │1 byte│2 bytes│ 8 bytes │ 8 bytes │8 bytes │4 bytes │   │
+-----------------------------------------------------------------------------+

最后一部分是存储索引开始偏移量的页脚。

+---------+
│ Footer  │
+---------+
│Index Ofs│
│ 8 bytes │
+---------+

压缩

每个块都经过压缩以减少存储空间和查询时的磁盘IO。 一块包含给定系列和字段的时间戳和值。 每个块有一个字节的头，后面是压缩的时间戳，然后是压缩的值。

+--------------------------------------------------+
| Type  |  Len  |   Timestamps    |      Values    |
|1 Byte | VByte |     N Bytes     |    N Bytes     │
+--------------------------------------------------+

时间戳和值被压缩并独立存储，使用依赖于数据类型和形状的编码。独立存储允许对所有时间戳使用时间戳编码，同时允许不同字段类型使用不同的编码。例如，某些点可能能够使用游程编码，而其他点则可能无法使用。

每个值类型还包含一个1字节的头部，用于指示剩余字节的压缩类型。四个高位存储压缩类型，四个低位在编码器需要时使用。

时间戳

时间戳编码是自适应的，基于被编码时间戳的结构。它使用 delta 编码、缩放和简单的 8b 运行长度编码组合进行压缩，如果需要，也可以回退到不压缩。

时间戳的分辨率是可变的，但可以精确到纳秒，需要多达8个字节来存储未压缩的值。 在编码过程中，值首先进行增量编码。 第一个值是起始时间戳，后续值是与前一个值的差。 这通常将值转换为更小的整数，便于压缩。 许多时间戳也呈单调递增，并且落在每10秒等时间的偶数边界上。 当时间戳具有这种结构时，它们会被按最大的公约数缩放，而该公约数也是10的因子。 这会将非常大的整数增量转换为更小的增量，从而实现更好的压缩效果。

使用这些调整后的值，如果所有的增量都是相同的，则时间范围使用游程长度编码来存储。 如果无法进行游程长度编码，并且所有值都小于 (1 « 60) - 1 (~36.5年，以纳秒为分辨率)，则时间戳使用simple8b编码进行编码。 Simple8b编码是一种64位字对齐的整数编码，将多个整数打包到一个64位字中。 如果任何值超过最大值，则增量将以每个块8字节的方式未压缩存储。 未来的编码可能采用补丁方案，例如修补的参考框架 (PFOR)，以更有效地处理离群值。

浮动数

浮点数通过对Facebook Gorilla paper的实现进行编码。 当数值相近时，编码将连续值进行异或，以产生一个小的结果。 然后，使用控制位存储增量，以指示异或值中有多少个前导零和尾随零。 我们的实现去除了论文中描述的时间戳编码，仅对浮动值进行编码。

整数

整数编码根据未压缩数据的值范围使用两种不同的策略。编码值首先使用 ZigZag 编码 进行编码。这在一系列正整数中交错了正整数和负整数。

例如，[-2,-1,0,1] 变为 [3,1,0,2]。有关更多信息，请参阅 Google 的 Protocol Buffers documentation。

如果所有ZigZag编码的值都小于(1 « 60) - 1，它们将使用simple8b编码进行压缩。 如果任何值大于最大值，则所有值都以未压缩的形式存储在块中。 如果所有值相同，则使用游程编码。 这对于频繁为常量的值效果很好。

布尔值

布尔值使用一种简单的位打包策略进行编码，其中每个布尔值使用1位。 编码的布尔值数量在区块的开头使用可变字节编码存储。

字符串

字符串使用 Snappy 压缩编码。 每个字符串连续打包，它们作为一个较大的块被压缩。

压缩

压缩是将以写优化格式存储的数据迁移到更适合读取的格式的重复过程。 在分片处于热写状态时，会发生多个压缩阶段：

• 快照 - 缓存和WAL中的值必须转换为TSM文件，以释放WAL段使用的内存和磁盘空间。这些压缩操作基于缓存内存和时间阈值。%
• 级别压缩 - 级别压缩（级别 1-4）随着 TSM 文件的增长而发生。 TSM 文件从快照压缩到级别 1 文件。 多个级别 1 文件被压缩以生成级别 2 文件。 该过程持续进行，直到文件达到级别 4（完全压缩）和 TSM 文件的最大大小。 除非需要运行删除、索引优化压缩或完全压缩，否则不会进一步压缩。 较低级别的压缩使用避免 CPU 密集型活动（如解压缩和组合块）的策略。 较高级别（因此不那么频繁）的压缩将重新组合块以完全压缩它们并增加压缩比。
• 索引优化 - 当许多级别4的TSM文件积累时，内部索引变得更大且访问成本更高。 索引优化压缩将系列和索引分割到一组新的TSM文件中，将给定系列的所有点排序到一个TSM文件中。 在索引优化之前，每个TSM文件包含大多数或所有系列的点，因此每个文件包含相同的系列索引。 在索引优化之后，每个TSM文件包含来自最小系列的点，并且文件之间几乎没有系列重叠。 因此，每个TSM文件具有更小的唯一系列索引，而不是完整系列列表的重复。 此外，特定系列的所有点在一个TSM文件中是连续的，而不是分散在多个TSM文件中。
• 完全压缩 - 完全压缩（级别 4 压缩）在分片长时间未进行写入或在分片上发生删除时运行。 完全压缩生成一组最佳的 TSM 文件，并包括来自级别和索引优化压缩的所有优化。 一旦分片被完全压缩，除非存储了新的写入或删除，否则不会在其上运行其他压缩。

写入

写操作被附加到当前的WAL段中，并且也被添加到缓存中。每个WAL段都有一个最大大小。写操作一旦当前文件填满，就会滚动到一个新的文件。当缓存变得过满时，会进行快照并启动WAL压缩。 如果入口写入速率在持续一段时间内超过WAL压缩速率，缓存可能会变得过满，在这种情况下，新的写入将失败，直到快照过程跟上。

当WAL段满并关闭时，压缩器会对缓存进行快照并将数据写入新的TSM文件。当TSM文件成功写入并执行fsync后，它将被加载并在FileStore中引用。

更新

更新（为已存在的点写入新值）按正常写入进行。由于缓存值会覆盖现有值，因此更新写入具有优先权。如果写入会覆盖先前TSM文件中的点，则在查询运行时，这些点会合并，并且更新写入具有优先权。

删除

删除是通过为度量或系列写入删除条目到WAL，然后更新缓存和文件存储来实现的。 缓存驱逐所有相关条目。 文件存储为每个包含相关数据的TSM文件写入墓碑文件。 这些墓碑文件在启动时用于忽略块，以及在压缩期间用于移除已删除条目。

对部分删除的系列的查询在查询时处理，直到压缩将数据完全从TSM文件中删除。

查询

当存储引擎执行查询时，本质上是对与特定系列键和字段关联的给定时间进行查找。首先，我们在数据文件中搜索，以找到包含与查询匹配的时间范围和匹配系列的文件。

一旦选择了数据文件，我们接下来需要找到文件中系列键索引条目的位置。我们对每个TSM索引进行二进制搜索，以找到其索引块的位置。

在常见的情况下，这些块不会在多个TSM文件中重叠，我们可以线性搜索索引条目以找到读取的起始块。如果存在时间重叠的块，索引条目会被排序，以确保较新的写入将优先，并且在查询执行期间可以按照顺序处理块。

在遍历索引条目时，块是从块部分顺序读取的。 块被解压缩，我们寻找特定的点。

新的InfluxDB存储引擎：从LSM树到B+树，再回到时间结构合并树

编写新的存储格式应该是最后的手段。 那么，InfluxData是如何最终编写我们自己的引擎的呢？ InfluxData尝试了许多存储格式，发现每种格式在某些基本方面都有所欠缺。 InfluxDB的性能要求是很高的，最终超越了其他存储系统。 InfluxDB的0.8版本允许多个存储引擎，包括LevelDB、RocksDB、HyperLevelDB和LMDB。 InfluxDB的0.9版本使用BoltDB作为底层存储引擎。 这篇文章是关于在0.9.5中发布的时间结构合并树存储引擎的，该引擎是InfluxDB 0.11+中唯一支持的存储引擎，包括整个1.x系列。

时间序列数据用例的特性使许多现有存储引擎面临挑战。在InfluxDB的发展过程中，InfluxData尝试了几种更受欢迎的选项。我们从LevelDB开始，它是一个基于LSM树的引擎，针对写入吞吐量进行了优化。之后我们尝试了BoltDB，它是一个基于内存映射B+树的引擎，针对读取进行了优化。最后，我们最终构建了自己的存储引擎，在许多方面与LSM树相似。

通过我们新的存储引擎，我们能够实现磁盘空间使用量减少多达45倍，写入吞吐量和压缩性能均优于我们在LevelDB及其变体中看到的表现。 这篇文章将涵盖该演变的细节，并以对我们新的存储引擎及其内部工作原理的深入研究结束。

时间序列数据的属性

时间序列数据的工作负载与普通数据库工作负载有很大不同。 有许多因素共同作用，使得扩展和保持性能变得非常困难：

• 数十亿个数据点
• 高写入吞吐量
• 高读取吞吐量
• 大规模删除（数据过期）
• 主要是插入/追加的工作负载，很少有更新

第一个也是最明显的问题是规模问题。 在DevOps、物联网或APM中，每天收集数亿或数十亿个独特的数据点是很容易的。

例如，假设我们有200个虚拟机或服务器在运行，每个服务器每10秒收集平均100个测量值。 考虑到一天有86,400秒，单个测量值每天每个服务器将生成8,640个数据点。 这使我们每天总共有172,800,000 (200 * 100 * 8,640) 个独立的数据点。 在传感器数据用例中，我们发现类似或更大的数据量。

数据量意味着写入吞吐量可以非常高。 我们经常收到能够处理每秒数十万次写入的配置请求。 一些更大公司只会考虑能够处理每秒数百万次写入的系统。

与此同时，时间序列数据可以成为一个高读取吞吐量的用例。 确实，如果你在跟踪700,000个独特的度量或时间序列，你无法期望可视化所有这些。 这导致许多人认为你实际上并没有读取大多数进入数据库的数据。 然而，除了人们在屏幕上展示的仪表板外，还有自动化系统用于监控或将大量时间序列数据与其他类型的数据结合在一起。

在InfluxDB内部，瞬时计算的聚合函数可以将数万个不同的时间序列合并成一个单一的视图。每一个这样的查询必须读取每个聚合的数据点，因此对于InfluxDB来说，读吞吐量通常是写吞吐量的很多倍。

考虑到时间序列主要是一个仅追加的工作负载，你可能会认为在B+树上获得出色的性能是可能的。 在键空间的追加操作是高效的，你可以实现每秒超过100,000次的操作。 然而，我们在单独的时间序列中进行这些追加操作。 因此，插入最终看起来更像是随机插入，而不是仅追加插入。

我们发现与时间序列数据相关的一个最大问题是，删除所有超过某个年龄的数据是非常常见的。 这里的常见模式是用户拥有高精度的数据，这些数据仅保留短时间，比如几天或几个月。 然后用户将这些数据进行降采样并聚合为低精度的汇总，后者会保留更长的时间。

幼稚的实现方法是简单地在每条记录达到其过期时间后将其删除。 但是，这意味着一旦第一批写入的点到达其过期日期，系统正在处理的删除操作与写入操作一样多，这是大多数存储引擎不适合的。

让我们深入了解我们尝试的两种存储引擎的细节，以及这些属性如何对我们的性能产生重大影响。

LevelDB 和日志结构合并树

当InfluxDB项目开始时，我们选择了LevelDB作为存储引擎，因为我们曾在InfluxDB之前的产品中使用它进行时间序列数据存储。我们知道它在写入吞吐量方面具有很好的特性，一切似乎“都能正常工作”。

LevelDB 是一种日志结构合并树（LSM 树）的实现，作为一个开源项目在 Google 开发。它暴露了一个用于键值存储的 API，键空间是有序的。最后这一部分对于时间序列数据很重要，因为它允许我们快速扫描时间范围，只要时间戳在键中。

LSM树基于一个日志，该日志接收写入，并有两个结构，称为内存表和SSTable。这些表代表了已排序的键空间。SSTable是只读文件，这些文件不断被其他SSTable替换，后者将插入和更新合并到键空间中。

LevelDB对我们最大的两个优势是高写入吞吐量和内置压缩。 然而，随着我们对人们在时间序列数据方面需求的了解，我们遇到了一些无法克服的挑战。

我们遇到的第一个问题是 LevelDB 不支持热备份。如果你想安全地备份数据库，必须先关闭它，然后再进行复制。LevelDB 的变体 RocksDB 和 HyperLevelDB 修复了这个问题，但还有另一个更迫切的问题，我们认为他们无法解决。

我们的用户需要一种自动管理数据保留的方法。 这意味着我们需要进行大规模的删除。 在LSM树中，删除的成本与写入一样高，甚至更高。 删除会写入一个称为墓碑的新记录。 之后，查询将结果集与任何墓碑合并，以便从查询返回中清除已删除的数据。 后来，进行压缩操作，删除墓碑记录和在SSTable文件中的基础删除记录。

为了避免进行删除操作，我们将数据分割成我们所称的分片，这些是连续的时间块。 分片通常会保存一天或七天的数据。 每个分片映射到一个底层的LevelDB。 这意味着我们可以通过关闭数据库并删除底层文件来删除整整一天的数据。

RocksDB的用户此时可能会提到一个叫做ColumnFamilies的功能。 在将时间序列数据放入Rocks时，通常将时间块分割成列族，然后在时间到期时将其丢弃。 这个思路是相同的：创建一个单独的区域，以便在删除大量数据时只丢弃文件，而不是更新索引。 丢弃列族是一个非常高效的操作。 然而，列族是一个相对较新的特性，我们还有另一个用于分片的用例。

将数据组织成分片意味着可以在集群内移动，而无需检查数十亿个键。 在撰写本文时，无法将一个RocksDB中的列族移动到另一个。 旧的分片通常对于写入是冷的，因此移动它们会便宜且简单。 我们将额外受益于在键空间中有一个冷的写入位置，这样后续进行一致性检查会更容易。

将数据组织成分片的方式在一段时间内非常有效，直到大量数据存入InfluxDB。 LevelDB将数据拆分成许多小文件。 在单个进程中打开几十个或数百个这样的数据库最终导致了一个大问题。 拥有六个月或一年数据的用户会耗尽文件句柄。 这并不是我们在大多数用户中发现的，但任何将数据库推向极限的用户都会遇到这个问题，而我们对此没有解决方案。 开放的文件句柄实在是太多了。

BoltDB 和 mmap B+ 树

经过一年的挣扎与LevelDB及其变体后，我们决定转向BoltDB，这是一个纯Golang数据库，深受LMDB的启发，LMDB是用C语言编写的mmap B+Tree数据库。 它与LevelDB具有相同的API语义：一个键值存储，其中键空间是有序的。我们的许多用户感到惊讶。我们自己发布的LevelDB变体与LMDB（一个mmap B+Tree）的测试显示RocksDB表现最佳。

然而，这个决定还考虑了其他因素，而不仅仅是写入性能。此时我们最重要的目标是达到一个可以在生产环境中运行和备份的稳定状态。BoltDB 还具有用纯 Go 编写的优势，这大大简化了我们的构建链，并使得为其他操作系统和平台构建变得简单。

对我们来说最大的胜利是BoltDB使用一个单一的文件作为数据库。 此时我们最常见的错误报告来源于文件句柄耗尽的用户。 Bolt同时解决了热备份问题和文件限制问题。

如果这意味着我们可以构建一个更可靠、更稳定的系统，我们愿意在写入吞吐量上承受损失。我们推测，对于任何出写入负载非常大的用户，他们反正会运行一个集群。

我们发布了基于 BoltDB 的 0.9.0 到 0.9.2 版本。 从开发的角度来看，这是令人愉快的。 干净的 API，快速且容易集成到我们的 Go 项目中，并且可靠。 然而，在运行了一段时间后，我们发现了写入吞吐量的一个大问题。 当数据库超过几 GB 后，写入操作的 IOPS 开始激增。

一些用户能够通过将InfluxDB放在大硬件上，配备几乎无限的IOPS，来绕过这个问题。 然而，大多数用户都在云中使用资源有限的虚拟机。 我们必须找到一种方法，以减少在一次写入成千上万的系列时所造成的影响。

在0.9.3和0.9.4版本中，我们的计划是在Bolt前面添加一个预写日志（WAL）。这样我们可以减少对键空间的随机插入数量。相反，我们会将多个紧挨着的写入缓冲起来，然后一次性刷新它们。然而，这只会延迟问题的出现。高IOPS仍然成为一个问题，并且对于任何即使是中等工作负载的操作来说，这个问题很快就会显现出来。

然而，我们在Bolt面前构建第一个WAL实现的经验让我们有信心解决写入问题。
WAL本身的性能非常出色，索引根本无法跟上。
在这一点上，我们又开始思考如何创建类似于LSM树的东西，以便能够应对我们的写入负载。

因此，时间结构合并树诞生了。