TSM（InfluxDB 底层数据存储格式）

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

InfluxDB存储引擎看起来非常类似于LSM树。 它有一个提前写日志和一组只读数据文件，这些文件在概念上类似于LSM树中的表。 TSM文件包含排序的压缩系列数据。 InfluxDB将为每个时间段创建一个[分片](/influx db/v 1.8/concepts/glossary/#分片)。 例如，如果您有一个无限期的[保留策略](/influx db/v 1.8/concepts/glossary/# retention-policy-RP)，将为每个7天的时间段创建碎片。 这些碎片中的每一个都映射到底层存储引擎数据库。 每个数据库都有自己的[WAL](/influx db/v 1.8/concepts/glossary/# WAL-write-pre-log)和TSM文件。 我们将深入研究存储引擎的每个部分。

存储引擎

存储引擎将许多组件联系在一起，并为存储和查询系列数据提供外部接口。它由许多组件组成，每个组件都有特定的作用:

• 内存中索引-内存中索引是每个分片之间的共享索引，可快速的measurement，tag和series,索引油引擎使用，但并不特定于存储引擎本身

  WAL - The WAL是一种写优化存储格式，允许持久写入，但不易查询，对WAL的写入将附加到固定大小的段中

• Cache - 缓存是WAL中存储的数据内存表示形式，它在运行时被查询，并与存储在TSM文件中的数据合并；

• TSM Files - TSM文件以列格式存储压缩的系列数据

• FileStore - FileStore介导对磁盘上所有TSM文件的访问，可以确保在替换现有的文件后自动安装TSM文件，并删除不再使用的TSM文件吧.

• Compactor -Compactor负责将优化程序较低的Cache和TSM数据转换为更多的读取优化格式。通过压缩序列，删除已删除的数据，优化索引并将较小的文件合并为较大的文件来实现。

• Compaction Planner - Compaction Planner 压缩计划程序确定哪些TSM文件已经准备好进行压缩，并确保多个并发压缩不会相互影响

• Compression -压缩由各种用于特定数据类型的编码器和解码器处理，有些编码器时相当静态的，总是以相同的方式编码相同的类型，其他人则根据数据的形状切其压缩策略

• Writers/Readers - 每种文件类型 (WAL 段t, TSM 文件, tombstones, etc..) 都有作家和读者用于处理格式.

预写日志 (WAL)

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

写入后，新的点将被序列化，使用Snappy压缩并写入WAL文件。fsync在成功返回之前，将文件’d并将数据添加到内存索引中。这意味着需要批处理点在一起才能实现高吞吐性能。（在许多用例中，最佳批次大小似乎是每批次5,000-10,000点。）

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

Cache

缓存是当前存储在WAL中的所有数据点的内存中副本。这些点由键组织，即测量，标签集和唯一字段。每个字段都保留为自己的时间范围。缓存数据不在内存中时被压缩。

对存储引擎的查询将合并缓存中的数据与TSM文件中的数据。查询将在查询处理时对从缓存生成的数据副本执行。这样，在查询运行时输入的内容将不会影响结果。

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

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

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

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

TSM files

TSM文件时内存 映射的只读文件的集合，这些文件的结构看起来与LevelDB或其他LSM Tree 变体中的SS Table 非常相似

TSM文件由四个部分组成：标头，快，索引和页脚

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

Header是一个用来标识文件类型和版本号的神奇数字

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

Blocks块是CRC32校验和数据对的序列 block块数据对文件是不透明的. 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文件中的每个块都有一个索引块条目。

索引结构可以提供对所有块的有效访问，以及确定与访问给定密钥相关联的成本的能力。
给定一个密钥和时间戳，我们可以确定一个文件是否包含该时间戳的块。
我们还可以确定该块驻留在哪里，以及检索该块必须读取多少数据。
知道了块的大小，我们就可以高效地提供我们的输入输出语句

+-----------------------------------------------------------------------------+
│                                   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 │
+---------+

Compression

每个数据块都会被压缩，以减少查询时的存储空间和磁盘输入输出。 块包含给定系列和字段的时间戳和值。 每个块都有一个字节头，后跟压缩时间戳和压缩值

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

时间戳和值使用取决于数据类型及其形状的编码进行压缩和单独存储。 独立存储它们允许时间戳编码用于所有时间戳，同时允许不同的字段类型使用不同的编码。

例如，一些点可能能够使用游程编码，而其他点可能不能。

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

Timestamps

时间戳编码是自适应的，并且基于被编码的时间戳的结构。 它使用增量编码、缩放和压缩的组合，使用简单的8b游程编码，以及在需要时返回到无压缩状态。

时间戳分辨率是可变的，但可以小到纳秒，需要多达8个字节来存储未压缩的数据。

在编码过程中，首先对值进行增量编码。

第一个值是起始时间戳，后续值是与前一个值的差异。 这通常会将这些值转换成更小、更容易压缩的整数。 许多时间戳也是单调递增的，并且落在时间的偶数边界上，例如每10秒。 当时间戳具有这种结构时，它们被最大公约数缩放，该公约数也是因子10。

这具有将非常大的整数增量转换成更好压缩的较小增量的效果。 使用这些调整后的值，如果所有的增量都相同，则使用游程编码来存储时间范围。 如果游程编码不可能且所有值都小于(1 « 60) - 1 ([~36.5年](https://www . wolframalpha . com/input/？I = (1+% 3C % 3C+60 )+-+1+纳秒+到+年)，然后使用[simple8b编码]对时间戳进行编码(https://github . com/jwilder/encoding/tree/master/simple8b)。 Simple8b编码是一种64位字对齐的整数编码，将多个整数打包成一个64位字。 如果任何值超过最大值，增量将以未压缩的方式存储，每个数据块使用8个字节。 未来的编码可能会使用修补的方案，如修补的参考框架(PFOR)，以更有效地处理异常值。

Floats

浮点数是使用[Facebook Gorilla论文](http://www . vldb . org/pvl db/vol 8/p 1816-teller . pdf)的实现进行编码的。

当两个值接近时，编码异或连续值，产生一个小结果。 然后，使用控制位存储增量，以指示异或值中有多少前导零和尾随零。

我们的实现删除了在论文中描述的时间戳编码，只对浮点值进行编码

Integers

整数编码使用两种不同的策略，这取决于未压缩数据中的值的范围。

编码值首先使用[ZIgZG编码]进行编码(https://developers . Google . com/protocol-buffers/docs/encoding # signed-integers)。

这将正整数和负整数交错在一个正整数范围内。 例如，[-2，-1，0，1]变成[3，1，0，2]。 详见Google的【协议缓冲区文档】(https://developers . Google . com/Protocol-Buffers/docs/encoding # signed-integers)。 如果所有ZigZag编码值都小于(1 « 60) - 1，则使用simple8b编码对其进行压缩。 如果任何值大于最大值，则所有值都以未压缩的形式存储在块中。 如果所有值都相同，则使用游程编码。 这对于经常是常量的值非常有效。

Booleans

Booleans 使用简单的位打包策略进行编码，其中每个Booleans使用1位，编码的Booleans使用可变字节编码存储在block块的开头

Strings

字符串正在使用【Quick】(http://Google.gitgub.io/Quick)压缩进行编码。

每个字符被连续大包，并被压缩为一个更大的块

Compactions

压缩是将以写优化格式存储的数据迁移到读优化格式的循环过程，

碎片处于热写入状态时，会发生多个压缩阶段：

• Snapshots - 缓存和WAL中的值必须转换为TSM文件，以释放WAL段使用 的内存和磁盘空间 这些压缩时基于缓存内存和时间阀值进行的.

• 级别压缩-级别压缩(级别1-4)随着TSM文件的增长而发生。

  TSM文件从快照压缩为1级文件。

  压缩多个1级文件以产生2级文件。

  该过程一直持续到文件达到级别4和TSM文件的最大大小。 除非需要运行删除、索引优化压缩或完全压缩，否则不会进一步压缩它们。

  低级压缩使用避免像解压缩和合并块这样的CPU密集型活动的策略。

  更高层次(因此频率更低)的压缩将重新组合块，以完全压缩它们并提高压缩比。

• 索引优化——当许多4级TSM文件累积时，内部索引变得更大，访问成本更高。

  索引优化压缩将系列和索引拆分到一组新的TSM文件中，将给定系列的所有点排序到一个TSM文件中。

  在索引优化之前，每个TSM文件包含大多数或所有系列的点，因此每个都包含相同的系列索引。

经过索引优化后，每个TSM文件包含最小系列的点，文件之间几乎没有系列重叠。

因此，每个TSM文件都有一个较小的唯一系列索引，而不是完整系列列表的副本。

此外，特定系列的所有点在一个TSM文件中是连续的，而不是分布在多个TSM文件中。

• 完全压缩-当碎片长时间变冷而无法写入时，或者当碎片上发生删除时，执行完全压缩。 完全压缩生成一组最佳的TSM文件，并包括级别和索引优化压缩的所有优化。 一旦碎片被完全压缩，除非存储新的写入或删除，否则不会在其上运行其他压缩。

Writes

写入被追加到当前的WAL段，并被添加到缓存中。 每个WAL段都有一个最大大小。 当前文件填满后，将滚动写入新文件。 缓存也有大小限制；当高速缓存变得太满时，拍摄快照并启动WAL压缩。 如果入站写入速率持续超过WAL压缩速率，缓存可能会变得太满，在这种情况下，新的写入将会失败，直到快照过程赶上。 当WAL段填满并关闭时，压缩程序会对缓存进行快照，并将数据写入新的TSM文件。 当TSM文件成功写入并“同步”后，它将被文件存储加载和引用

Updates

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

Deletes

通过将测量值或系列的删除条目写入WAL，然后更新缓存和文件存储来进行删除。 缓存会驱逐所有相关条目。 文件存储为每个包含相关数据的TSM文件写入一个逻辑删除文件。 这些逻辑删除文件在启动时用来忽略块，在压缩时用来删除已删除的条目。 对部分删除的序列的查询在查询时处理，直到压缩从TSM文件中完全删除数据。

Queries

当存储引擎执行查询时，它本质上是对与特定系列关键字和字段相关联的给定时间的查找。

首先，我们对数据文件进行搜索，以找到包含与查询匹配的时间范围以及包含匹配系列的文件。 一旦我们选择了数据文件，我们接下来需要找到系列关键索引条目在文件中的位置。 我们对每个TSM索引运行一个二分搜索法，以找到其索引块的位置。

在常见情况下，块不会在多个TSM文件中重叠，我们可以线性搜索索引条目，以找到要读取的起始块。 如果有重叠的时间块，将对索引条目进行排序，以确保较新的写入优先，并且在查询执行期间可以按顺序处理这些块。 当迭代索引条目时，从块部分顺序读取块。 块被解压缩，我们寻找特定的点。

新的 InfluxDB 存储引擎: 从 LSM 树到 B+树，再返回来创建时间结构合并树

编写新的存储格式应该是最后的手段。 那么InfluxData最终是如何编写我们自己的引擎的呢？ InfluxData对许多存储格式进行了试验，发现每种格式都存在一些根本性的缺陷。 对InfluxDB的性能要求很高，最终会超过其他存储系统。

InfluxDB的0.8行允许多个存储引擎，包括级别数据库、RocksDB、HyperLevelDB和LMDB。 InfluxDB的0.9行使用BoltDB作为底层存储引擎。 这篇文章是关于在0.9.5中发布的时间结构化合并树存储引擎，它是InfluxDB 0.11+中唯一支持的存储引擎，包括整个1.x系列。 时间序列数据用例的属性使得它对许多现有的存储引擎具有挑战性。 在Influxdb的开发过程中，Influxdb数据尝试了一些更受欢迎的选项。 我们从LevelDB开始，这是一个基于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次以上。 然而，我们有那些附加发生在个别时间序列。 因此，与仅追加插入相比，插入最终看起来更像随机插入。 我们在时间序列数据中发现的最大问题之一是，在超过一定期限后删除所有数据是非常常见的。 这里常见的模式是，用户拥有高精度的数据，这些数据会保留很短一段时间，比如几天或几个月。 然后，用户对这些数据进行下采样，并将其聚合到精度较低的卷中，这些卷会保留更长时间。 最简单的实现是，一旦每个记录过了到期时间，就删除它。 然而，这意味着一旦写入的第一个点到达它们的到期日期，系统将处理与写入一样多的删除，这是大多数存储引擎不适合的。 让我们深入了解一下我们尝试的两种存储引擎的细节，以及这些属性如何对我们的性能产生重大影响。

级别数据库和日志结构合并树

当InfluxDB项目开始时，我们选择LevelDB作为存储引擎，因为我们在InfluxDB的前身产品中使用了它来存储时间序列数据。 我们知道它对于写吞吐量有很好的特性，一切似乎都“正常工作”。 LevelDB是一个日志结构的合并树(LSM树)的实现，它是作为一个开源项目在谷歌构建的。 它公开了一个键值存储的应用编程接口，在键值存储中对键空间进行排序。 最后一部分对于时间序列数据很重要，因为它允许我们快速扫描时间范围，只要时间戳在关键字中。 LSM树是基于一个接受写操作的日志和两个被称为内存表和表的结构。 这些表表示排序的键空间。 表是只读文件，会被其他将插入和更新合并到键空间中的表连续替换。 LevelDB对我们来说最大的两个优势是高写入吞吐量和内置压缩。 然而，随着我们更多地了解人们对时间序列数据的需求，我们遇到了一些无法克服的挑战。 我们遇到的第一个问题是LevelDB不支持热备份。 如果您想对数据库进行安全备份，您必须先关闭它，然后再复制它。 LevelDB变体RocksDB和HyperLevelDB解决了这个问题，但是还有一个我们认为他们无法解决的更紧迫的问题。 我们的用户需要一种自动管理数据保留的方法。 这意味着我们需要大规模的删除。 在《LSM树》中，删除和写一样昂贵，如果不是更贵的话。 删除操作会写入一条新记录，称为Tombatone。 之后，查询将结果集与任何Tombatone合并，以从查询返回中清除已删除的数据。 稍后，将运行一个压缩，删除表文件中的逻辑删除记录和基础已删除记录。 为了避免删除，我们将数据分割成我们称之为碎片的部分，即连续的时间块。 碎片通常会保存一天或七天的数据。 每个碎片映射到一个底层的级别数据库。 这意味着我们只需关闭数据库并删除底层文件，就可以丢弃一整天的数据。 RocksDB的用户可能会在此时调出一个名为ColumnFamilies的功能。 当将时间序列数据放入Rocks时，通常会将时间块分割成列族，然后在时间用完时丢弃它们。 这是相同的一般想法:创建一个单独的区域，当您删除一大块数据时，您可以在这里只删除文件，而不是更新索引。 删除列族是一种非常有效的操作。 然而，列族是一个相当新的特性，我们有另一个碎片用例。 将数据组织成碎片意味着它可以在集群内移动，而不必检查数十亿个密钥。 在撰写本文时，不可能将一个RocksDB中的列族移动到另一个RockSdb中。 旧碎片通常对写入很冷，因此移动它们既便宜又容易。 我们还有一个额外的好处，就是在键空间中有一个对写入很冷的位置，这样以后进行一致性检查就更容易了。 将数据组织到碎片中的方法一度非常有效，直到大量数据进入InfluxDB。 LevelDB将数据分割成许多小文件。 在一个过程中打开几十个或几百个这样的数据库最终会产生一个大问题。 拥有六个月或一年数据的用户会用完文件句柄。 这不是我们在大多数用户身上发现的东西，但是任何将数据库推向极限的人都会遇到这个问题，我们对此没有解决办法。 打开的文件句柄太多了。

BoltDB 和 mmap B+Trees

在与LevelDB及其变体斗争了一年后，我们决定转向BoltDB，一个纯粹的Golang数据库，深受LMDB的启发，一个用C语言编写的mmap B+Tree数据库。 它具有与LevelDB相同的API语义:一个键值存储，其中键空间是有序的。 我们的许多用户感到惊讶。 我们自己发布的对LevelDB变体与LMDB的测试显示RocksDB是最佳表现者。 然而，除了纯粹的写性能之外，这个决定还考虑了其他因素。 在这一点上，我们最重要的目标是得到一些稳定的东西，可以在生产中运行和备份。 BoltDB还具有用纯Go编写的优势，这极大地简化了我们的构建链，并使其易于为其他操作系统和平台构建。 我们最大的胜利是BoltDB使用了一个文件作为数据库。 在这一点上，我们最常见的错误报告来源于文件句柄用完的人。 Bolt同时解决了热备份问题和文件限制问题。 如果这意味着我们可以构建一个更可靠、更稳定的系统，我们愿意在写吞吐量上受到冲击。 我们的推理是，对于任何推动真正大的写负载的人来说，他们无论如何都会运行一个集群。 我们发布了基于BoltDB的0.9.0到0.9.2版本。 从发展的角度来看，这是令人愉快的。 干净的应用编程接口，快速简单地构建在我们的围棋项目中，并且可靠。 然而，运行一段时间后，我们发现写吞吐量有一个大问题。 当数据库超过几GB后，写入将开始冲击IOPS。 一些用户能够通过将InfluxDB放在具有几乎无限IOPS的大硬件上来克服这个问题。 但是，大多数用户都在云中资源有限的虚拟机上。 我们必须想办法减少一次把一堆点写成几十万个系列的影响。 对于0.9.3和0.9.4版本，我们的计划是在博尔特前面放一个提前写日志。 这样我们就可以减少向键空间中随机插入的次数。 相反，我们会缓冲多个相邻的写操作，然后立即刷新它们。 然而，这只能推迟问题的解决。 高IOPS仍然是一个问题，对于任何在中等工作负荷下工作的人来说，这个问题很快就会出现。 然而，我们在博尔特面前构建第一个WAL实现的经验给了我们解决写问题所需的信心。 沃尔玛本身的表现太棒了，指数根本跟不上。 在这一点上，我们开始再次思考如何创建一个类似于LSM树的东西来跟上我们的写负载。

时间结构合并树就这样诞生了！