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

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

InfluxDB 将为每个时间块创建一个 分片 (shard)。例如，如果您有一个具有无限持续时间的 保留策略 (retention policy)，则将为每 7 天的时间块创建分片。这些分片中的每一个都映射到一个底层的存储引擎数据库。这些数据库中的每一个都有自己的 WAL 和 TSM 文件。

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

存储引擎

存储引擎将许多组件联系在一起，并为存储和查询序列数据提供外部接口。它由许多组件组成，每个组件都服务于特定的角色

• 内存索引 - 内存索引是跨分片的共享索引，可提供对 度量 (measurements)、标签 (tags) 和 序列 (series) 的快速访问。索引由引擎使用，但并非特定于存储引擎本身。
• WAL - WAL 是一种写入优化的存储格式，允许写入是持久的，但不容易查询。写入 WAL 将附加到固定大小的段。
• 缓存 - 缓存是 WAL 中存储的数据的内存表示。它在运行时被查询，并与 TSM 文件中存储的数据合并。
• TSM 文件 - TSM 文件以列式格式存储压缩的序列数据。
• FileStore - FileStore 协调对磁盘上所有 TSM 文件的访问。它确保在替换现有 TSM 文件时以原子方式安装 TSM 文件，并删除不再使用的 TSM 文件。
• Compactor - Compactor 负责将不太优化的缓存和 TSM 数据转换为更优化的读取格式。它通过压缩序列、删除已删除的数据、优化索引以及将较小的文件合并为较大的文件来实现此目的。
• Compaction Planner - Compaction Planner 确定哪些 TSM 文件已准备好进行压缩，并确保多个并发压缩不会相互干扰。
• 压缩 - 压缩由各种编码器和解码器针对特定数据类型处理。一些编码器是相当静态的，并且始终以相同的方式编码相同的类型；其他编码器则根据数据的形状切换其压缩策略。
• 写入器/读取器 - 每种文件类型（WAL 段、TSM 文件、tombstone 等）都有用于处理格式的写入器和读取器。

预写日志 (WAL)

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

当写入进入时，新点被序列化，使用 Snappy 压缩，并写入 WAL 文件。该文件被 fsync’d，并且数据在返回成功之前被添加到内存索引中。这意味着需要批量处理点才能实现高吞吐量性能。（对于许多用例，最佳批量大小似乎是每个批次 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 文件中创建多个索引条目。每个索引条目都以键长度和键开头，后跟块类型（浮点型、整型、布尔型、字符串型）以及该键后续索引块条目的数量计数。每个索引块条目都由块的最小和最大时间、块在文件中的偏移量以及块的大小组成。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 字节的标头，指示剩余字节的压缩类型。高四位存储压缩类型，低四位供编码器在需要时使用。

时间戳

时间戳编码是自适应的，并且基于编码的时间戳的结构。它使用增量编码、缩放和使用 simple8b 游程编码进行压缩的组合，并在需要时回退到不压缩。

时间戳分辨率是可变的，但可以精细到纳秒，最多需要 8 个字节来存储未压缩的数据。在编码期间，值首先进行增量编码。第一个值是起始时间戳，后续值是与先前值的差异。这通常将值转换为更小的整数，这些整数更容易压缩。许多时间戳也是单调递增的，并且落在均匀的时间边界上，例如每 10 秒。当时间戳具有这种结构时，它们会按最大公约数进行缩放，该最大公约数也是 10 的因子。这具有将非常大的整数增量转换为更小的整数的效果，这些整数的压缩效果更好。

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

浮点数

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

整数

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

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

如果所有 ZigZag 编码值都小于 (1 « 60) - 1，则使用 simple8b 编码对其进行压缩。如果任何值大于最大值，则所有值都以未压缩的方式存储在块中。如果所有值都相同，则使用游程编码。这对于经常恒定的值非常有效。

布尔值

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

字符串

字符串使用 Snappy 压缩进行编码。每个字符串都连续打包，并将它们压缩为一个更大的块。

压缩

压缩是将以写入优化格式存储的数据迁移到更优化的读取格式的定期过程。当分片对于写入是热的时，会发生许多阶段的压缩

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

写入

写入将附加到当前的 WAL 段，并且还会添加到缓存。每个 WAL 段都有最大大小。一旦当前文件已满，写入将滚动到新文件。缓存的大小也有限制；当缓存变得太满时，将拍摄快照并启动 WAL 压缩。如果传入写入速率在持续一段时间内超过 WAL 压缩速率，则缓存可能会变得太满，在这种情况下，新的写入将失败，直到快照过程赶上。

当 WAL 段填满并关闭时，Compactor 会快照缓存并将数据写入新的 TSM 文件。当 TSM 文件成功写入并 fsync’d 时，它会被加载并由 FileStore 引用。

更新

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

删除

删除通过将删除条目写入度量或序列的 WAL，然后更新缓存和 FileStore 来发生。缓存会驱逐所有相关条目。FileStore 为每个包含相关数据的 TSM 文件写入 tombstone 文件。这些 tombstone 文件在启动时用于忽略块，以及在压缩期间用于删除已删除的条目。

针对部分删除的序列的查询在查询时处理，直到压缩将数据完全从 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 树的引擎，LSM 树针对写入吞吐量进行了优化。在那之后，我们尝试了 BoltDB，这是一个基于内存映射 B+ 树的引擎，它针对读取进行了优化。最后，我们最终构建了自己的存储引擎，该引擎在许多方面类似于 LSM 树。

使用我们的新存储引擎，我们能够将磁盘空间使用量从我们的 B+ 树设置中减少多达 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 树基于日志，该日志接受写入和两个称为 Mem Table 和 SSTable 的结构。这些表表示排序的键空间。SSTable 是只读文件，这些文件不断被其他 SSTable 替换，这些 SSTable 将插入和更新合并到键空间中。

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

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

我们的用户需要一种自动管理数据保留的方法。这意味着我们需要大规模的删除。在 LSM 树中，删除与写入一样昂贵，甚至更昂贵。删除会写入一个称为 tombstone 的新记录。之后，查询将结果集与任何 tombstone 合并，以从查询返回中清除已删除的数据。稍后，压缩会运行，它会删除 tombstone 记录和 SSTable 文件中底层的已删除记录。

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

RocksDB 的用户此时可能会提出一个名为 ColumnFamilies 的功能。当将时间序列数据放入 Rocks 中时，通常将时间块拆分为列族，然后在时间到期时删除这些列族。这是一样的总体思路：创建一个单独的区域，您可以在其中仅删除文件，而不是在删除大量数据块时更新索引。删除列族是一个非常高效的操作。但是，列族是一个相当新的功能，我们在分片方面还有另一个用例。

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

将数据组织成分片在一段时间内运行良好，直到大量数据进入 InfluxDB。LevelDB 将数据拆分到许多小文件中。在一个进程中打开数十个或数百个这些数据库最终造成了一个大问题。拥有六个月或一年数据的用户将耗尽文件句柄。这不是我们在大多数用户中发现的问题，但是任何将数据库推向极限的人都会遇到这个问题，我们对此无能为力。打开的文件句柄太多了。

BoltDB 和 mmap B+ 树

在与 LevelDB 及其变体斗争了一年后，我们决定迁移到 BoltDB，这是一个纯 Golang 数据库，其灵感来自 LMDB，这是一个用 C 编写的 mmap B+ 树数据库。它具有与 LevelDB 相同的 API 语义：键空间已排序的键值存储。我们的许多用户感到惊讶。我们自己发布的 LevelDB 变体与 LMDB（mmap B+ 树）的测试表明 RocksDB 是最佳性能者。

但是，此决定还考虑了纯写入性能之外的其他因素。此时，我们最重要的目标是获得可以在生产中运行和备份的稳定产品。BoltDB 还具有用纯 Go 编写的优势，这极大地简化了我们的构建链，并使其易于为其他操作系统和平台构建。

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

我们愿意在写入吞吐量方面受到打击，如果这意味着我们将拥有一个更可靠和稳定的系统，我们可以在此基础上进行构建。我们的理由是，对于任何推动真正大的写入负载的人来说，他们无论如何都会运行集群。

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

一些用户可以通过将 InfluxDB 放在具有接近无限 IOPS 的大型硬件上来解决此问题。但是，大多数用户都在云中资源有限的 VM 上。我们必须找出一种方法来减少一次将一堆点写入数十万个序列的影响。

在 0.9.3 和 0.9.4 版本中，我们的计划是在 Bolt 前面放置一个预写日志 (WAL)。这样，我们可以减少对键空间的随机插入次数。相反，我们将缓冲多个彼此相邻的写入，然后一次刷新它们。但是，这只能延迟问题。高 IOPS 仍然成为问题，对于任何即使在中等工作负载下运行的人来说，它也会很快出现。

但是，我们在 Bolt 前面构建第一个 WAL 实现的经验使我们有信心可以解决写入问题。WAL 本身的性能非常出色，索引根本无法跟上。此时，我们再次开始考虑如何创建类似于 LSM 树的东西，该树可以跟上我们的写入负载。

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