从零写一个时间序列数据库
编者按：Prometheus 是 CNCF 旗下的开源监控告警解决方案，它已经成为 Kubernetes 生态圈中的核心监控系统。本文作者 Fabian Reinartz 是 Prometheus 的核心开发者，这篇文章是其于 2017 年写的一篇关于 Prometheus 中的时间序列数据库的设计思考，虽然写作时间有点久了，但是其中的考虑和思路非常值得参考。长文预警，请坐下来慢慢品味。
我从事监控工作。特别是在 Prometheus 上，监控系统包含一个自定义的时间序列数据库，并且集成在 Kubernetes 上。
在许多方面上 Kubernetes 展现出了 Prometheus 所有的设计用途。它使得 持续部署 ， 弹性伸缩 和其他 高动态环境 下的功能可以轻易地访问。查询语句和操作模型以及其它概念决策使得 Prometheus 特别适合这种环境。但是，如果监控的工作负载动态程度显著地增加，这就会给监控系统本身带来新的压力。考虑到这一点，我们就可以特别致力于在高动态或 瞬态服务 环境下提升它的表现，而不是回过头来解决 Prometheus 已经解决的很好的问题。
Prometheus 的存储层在历史以来都展现出卓越的性能，单一服务器就能够以每秒数百万个时间序列的速度摄入多达一百万个样本，同时只占用了很少的磁盘空间。尽管当前的存储做的很好，但我依旧提出一个新设计的存储子系统，它可以修正现存解决方案的缺点，并具备处理更大规模数据的能力。
备注：我没有数据库方面的背景。我说的东西可能是错的并让你误入歧途。你可以在 Freenode 的 #prometheus 频道上对我（fabxc）提出你的批评。
问题，难题，问题域
首先，快速地概览一下我们要完成的东西和它的关键难题。我们可以先看一下 Prometheus 当前的做法 ，它为什么做的这么好，以及我们打算用新设计解决哪些问题。
时间序列数据
我们有一个收集一段时间数据的系统。
identifier -> (t0, v0), (t1, v1), (t2, v2), (t3, v3), ....
每个数据点是一个时间戳和值的元组。在监控中，时间戳是一个整数，值可以是任意数字。64 位浮点数对于计数器和测量值来说是一个好的表示方法，因此我们将会使用它。一系列严格单调递增的时间戳数据点是一个序列，它由标识符所引用。我们的标识符是一个带有 标签维度 字典的度量名称。标签维度划分了单一指标的测量空间。每一个指标名称加上一个唯一标签集就成了它自己的时间序列，它有一个与之关联的 数据流 。
这是一个典型的 序列标识符 集，它是统计请求指标的一部分：
requests_total{path="/status", method="GET", instance=”10.0.0.1:80”}
requests_total{path="/status", method="POST", instance=”10.0.0.3:80”}
requests_total{path="/", method="GET", instance=”10.0.0.2:80”}
让我们简化一下表示方法：度量名称可以当作另一个维度标签，在我们的例子中是 __name__。对于查询语句，可以对它进行特殊处理，但与我们存储的方式无关，我们后面也会见到。
{__name__="requests_total", path="/status", method="GET", instance=”10.0.0.1:80”}
{__name__="requests_total", path="/status", method="POST", instance=”10.0.0.3:80”}
{__name__="requests_total", path="/", method="GET", instance=”10.0.0.2:80”}
我们想通过标签来查询时间序列数据。在最简单的情况下，使用 {__name__="requests_total"} 选择所有属于 requests_total 指标的数据。对于所有选择的序列，我们在给定的时间窗口内获取数据点。
在更复杂的语句中，我们或许想一次性选择满足多个标签的序列，并且表示比相等条件更复杂的情况。例如，非语句（method!="GET"）或正则表达式匹配（method=~"PUT|POST"）。
这些在很大程度上定义了存储的数据和它的获取方式。
纵与横
在简化的视图中，所有的数据点可以分布在二维平面上。水平维度代表着时间，序列标识符域经纵轴展开。
series
^
| . . . . . . . . . . . . . . . . . . . . . . {__name__="request_total", method="GET"}
| . . . . . . . . . . . . . . . . . . . . . . {__name__="request_total", method="POST"}
| . . . . . . .
| . . . . . . . . . . . . . . . . . . . ...
| . . . . . . . . . . . . . . . . . . . . .
| . . . . . . . . . . . . . . . . . . . . . {__name__="errors_total", method="POST"}
| . . . . . . . . . . . . . . . . . {__name__="errors_total", method="GET"}
| . . . . . . . . . . . . . .
| . . . . . . . . . . . . . . . . . . . ...
| . . . . . . . . . . . . . . . . . . . .
v
<-------------------- time --------------------->
Prometheus 通过定期地抓取一组时间序列的当前值来获取数据点。我们从中获取到的实体称为目标。因此，写入模式完全地垂直且高度并发，因为来自每个目标的样本是独立摄入的。
这里提供一些测量的规模：单一 Prometheus 实例从数万个目标中收集数据点，每个数据点都暴露在数百到数千个不同的时间序列中。
在每秒采集数百万数据点这种规模下，批量写入是一个不能妥协的性能要求。在磁盘上分散地写入单个数据点会相当地缓慢。因此，我们想要按顺序写入更大的数据块。
对于旋转式磁盘，它的磁头始终得在物理上向不同的扇区上移动，这是一个不足为奇的事实。而虽然我们都知道 SSD 具有快速随机写入的特点，但事实上它不能修改单个字节，只能写入一页或更多页的 4KiB 数据量。这就意味着写入 16 字节的样本相当于写入满满一个 4Kib 的页。这一行为就是所谓的写入放大，这种特性会损耗你的 SSD。因此它不仅影响速度，而且还毫不夸张地在几天或几个周内破坏掉你的硬件。
关于此问题更深层次的资料，“Coding for SSDs”系列博客是极好的资源。让我们想想主要的用处：顺序写入和批量写入分别对于旋转式磁盘和 SSD 来说都是理想的写入模式。大道至简。
查询模式比起写入模式明显更不同。我们可以查询单一序列的一个数据点，也可以对 10000 个序列查询一个数据点，还可以查询一个序列几个周的数据点，甚至是 10000 个序列几个周的数据点。因此在我们的二维平面上，查询范围不是完全水平或垂直的，而是二者形成矩形似的组合。
记录规则可以减轻已知查询的问题，但对于 点对点 查询来说并不是一个通用的解决方法。
我们知道我们想要批量地写入，但我们得到的仅仅是一系列垂直数据点的集合。当查询一段时间窗口内的数据点时，我们不仅很难弄清楚在哪才能找到这些单独的点，而且不得不从磁盘上大量随机的地方读取。也许一条查询语句会有数百万的样本，即使在最快的 SSD 上也会很慢。读入也会从磁盘上获取更多的数据而不仅仅是 16 字节的样本。SSD 会加载一整页，HDD 至少会读取整个扇区。不论哪一种，我们都在浪费宝贵的读取吞吐量。
因此在理想情况下，同一序列的样本将按顺序存储，这样我们就能通过尽可能少的读取来扫描它们。最重要的是，我们仅需要知道序列的起始位置就能访问所有的数据点。
显然，将收集到的数据写入磁盘的理想模式与能够显著提高查询效率的布局之间存在着明显的抵触。这是我们 TSDB 需要解决的一个基本问题。
当前的解决方法
是时候看一下当前 Prometheus 是如何存储数据来解决这一问题的，让我们称它为“V2”。
我们创建一个时间序列的文件，它包含所有样本并按顺序存储。因为每几秒附加一个样本数据到所有文件中非常昂贵，我们在内存中打包 1Kib 样本序列的数据块，一旦打包完成就附加这些数据块到单独的文件中。这一方法解决了大部分问题。写入目前是批量的，样本也是按顺序存储的。基于给定的同一序列的样本相对之前的数据仅发生非常小的改变这一特性，它还支持非常高效的压缩格式。Facebook 在他们 Gorilla TSDB 上的论文中描述了一个相似的基于数据块的方法，并且引入了一种压缩格式，它能够减少 16 字节的样本到平均 1.37 字节。V2 存储使用了包含 Gorilla 变体等在内的各种压缩格式。
+----------+---------+---------+---------+---------+ series A
+----------+---------+---------+---------+---------+
+----------+---------+---------+---------+---------+ series B
+----------+---------+---------+---------+---------+
. . .
+----------+---------+---------+---------+---------+---------+ series XYZ
+----------+---------+---------+---------+---------+---------+
chunk 1 chunk 2 chunk 3 ...
尽管基于块存储的方法非常棒，但为每个序列保存一个独立的文件会给 V2 存储带来麻烦，因为：
- 实际上，我们需要的文件比当前收集数据的时间序列数量要多得多。多出的部分在 序列分流 上。有几百万个文件，迟早会使用光文件系统中的 inode。这种情况我们只能通过重新格式化来恢复磁盘，这种方式是最具有破坏性的。我们通常不想为了适应一个应用程序而格式化磁盘。
- 即使是分块写入，每秒也会产生数千块的数据块并且准备持久化。这依然需要每秒数千次的磁盘写入。尽管通过为每个序列打包好多个块来缓解，但这反过来还是增加了等待持久化数据的总内存占用。
- 要保持所有文件打开来进行读写是不可行的。特别是因为 99% 的数据在 24 小时之后不再会被查询到。如果查询它，我们就得打开数千个文件，找到并读取相关的数据点到内存中，然后再关掉。这样做就会引起很高的查询延迟，数据块缓存加剧会导致新的问题，这一点在“资源消耗”一节另作讲述。
- 最终，旧的数据需要被删除，并且数据需要从数百万文件的头部删除。这就意味着删除实际上是写密集型操作。此外，循环遍历数百万文件并且进行分析通常会导致这一过程花费数小时。当它完成时，可能又得重新来过。喔天，继续删除旧文件又会进一步导致 SSD 产生写入放大。
- 目前所积累的数据块仅维持在内存中。如果应用崩溃，数据就会丢失。为了避免这种情况，内存状态会定期的保存在磁盘上，这比我们能接受数据丢失窗口要长的多。恢复检查点也会花费数分钟，导致很长的重启周期。
我们能够从现有的设计中学到的关键部分是数据块的概念，我们当然希望保留这个概念。最新的数据块会保持在内存中一般也是好的主意。毕竟，最新的数据会大量的查询到。
一个时间序列对应一个文件，这个概念是我们想要替换掉的。
序列分流
在 Prometheus 的 上下文 中，我们使用术语 序列分流 来描述一个时间序列集合变得不活跃，即不再接收数据点，取而代之的是出现一组新的活跃序列。
例如，由给定微服务实例产生的所有序列都有一个相应的“instance”标签来标识其来源。如果我们为微服务执行了 滚动更新 ，并且为每个实例替换一个新的版本，序列分流便会发生。在更加动态的环境中，这些事情基本上每小时都会发生。像 Kubernetes 这样的 集群编排 系统允许应用连续性的自动伸缩和频繁的滚动更新，这样也许会创建成千上万个新的应用程序实例，并且伴随着全新的时间序列集合，每天都是如此。
series
^
| . . . . . .
| . . . . . .
| . . . . . .
| . . . . . . .
| . . . . . . .
| . . . . . . .
| . . . . . .
| . . . . . .
| . . . . .
| . . . . .
| . . . . .
v
<-------------------- time --------------------->
所以即便整个基础设施的规模基本保持不变，过一段时间后数据库内的时间序列还是会成线性增长。尽管 Prometheus 很愿意采集 1000 万个时间序列数据，但要想在 10 亿个序列中找到数据，查询效果还是会受到严重的影响。
当前解决方案
当前 Prometheus 的 V2 存储系统对所有当前保存的序列拥有基于 LevelDB 的索引。它允许查询语句含有给定的 标签对 ，但是缺乏可伸缩的方法来从不同的标签选集中组合查询结果。
例如，从所有的序列中选择标签 __name__="requests_total" 非常高效，但是选择 instance="A" AND __name__="requests_total" 就有了可伸缩性的问题。我们稍后会重新考虑导致这一点的原因和能够提升查找延迟的调整方法。
事实上正是这个问题才催生出了对更好的存储系统的最初探索。Prometheus 需要为查找亿万个时间序列改进索引方法。
资源消耗
当试图扩展 Prometheus（或其他任何事情，真的）时，资源消耗是永恒不变的话题之一。但真正困扰用户的并不是对资源的绝对渴求。事实上，由于给定的需求，Prometheus 管理着令人难以置信的吞吐量。问题更在于面对变化时的相对未知性与不稳定性。通过其架构设计，V2 存储系统缓慢地构建了样本数据块，这一点导致内存占用随时间递增。当数据块完成之后，它们可以写到磁盘上并从内存中清除。最终，Prometheus 的内存使用到达稳定状态。直到监测环境发生了改变——每次我们扩展应用或者进行滚动更新，序列分流都会增加内存、CPU、磁盘 I/O 的使用。
如果变更正在进行，那么它最终还是会到达一个稳定的状态，但比起更加静态的环境，它的资源消耗会显著地提高。过渡时间通常为数个小时，而且难以确定最大资源使用量。
为每个时间序列保存一个文件这种方法也使得一个单个查询就很容易崩溃 Prometheus 进程。当查询的数据没有缓存在内存中，查询的序列文件就会被打开，然后将含有相关数据点的数据块读入内存。如果数据量超出内存可用量，Prometheus 就会因 OOM 被杀死而退出。
在查询语句完成之后，加载的数据便可以被再次释放掉，但通常会缓存更长的时间，以便更快地查询相同的数据。后者看起来是件不错的事情。
最后，我们看看之前提到的 SSD 的写入放大，以及 Prometheus 是如何通过批量写入来解决这个问题的。尽管如此，在许多地方还是存在因为批量太小以及数据未精确对齐页边界而导致的写入放大。对于更大规模的 Prometheus 服务器，现实当中会发现缩减硬件寿命的问题。这一点对于高写入吞吐量的数据库应用来说仍然相当普遍，但我们应该放眼看看是否可以解决它。
重新开始
到目前为止我们对于问题域、V2 存储系统是如何解决它的，以及设计上存在的问题有了一个清晰的认识。我们也看到了许多很棒的想法，这些或多或少都可以拿来直接使用。V2 存储系统相当数量的问题都可以通过改进和部分的重新设计来解决，但为了好玩（当然，在我仔细的验证想法之后），我决定试着写一个完整的时间序列数据库——从头开始，即向文件系统写入字节。
性能与资源使用这种最关键的部分直接影响了存储格式的选取。我们需要为数据找到正确的算法和磁盘布局来实现一个高性能的存储层。
这就是我解决问题的捷径——跳过令人头疼、失败的想法，数不尽的草图，泪水与绝望。
V3—宏观设计
我们存储系统的宏观布局是什么？简而言之，是当我们在数据文件夹里运行 tree 命令时显示的一切。看看它能给我们带来怎样一副惊喜的画面。
$ tree ./data
./data
+-- b-000001
| +-- chunks
| | +-- 000001
| | +-- 000002
| | +-- 000003
| +-- index
| +-- meta.json
+-- b-000004
| +-- chunks
| | +-- 000001
| +-- index
| +-- meta.json
+-- b-000005
| +-- chunks
| | +-- 000001
| +-- index
| +-- meta.json
+-- b-000006
+-- meta.json
+-- wal
+-- 000001
+-- 000002
+-- 000003
在最顶层，我们有一系列以 b- 为前缀编号的 块 。每个块中显然保存了索引文件和含有更多编号文件的 chunk 文件夹。chunks 目录只包含不同序列 数据点的原始块 。与 V2 存储系统一样，这使得通过时间窗口读取序列数据非常高效并且允许我们使用相同的有效压缩算法。这一点被证实行之有效，我们也打算沿用。显然，这里并不存在含有单个序列的文件，而是一堆保存着许多序列的数据块。
index 文件的存在应该不足为奇。让我们假设它拥有黑魔法，可以让我们找到标签、可能的值、整个时间序列和存放数据点的数据块。
但为什么这里有好几个文件夹都是索引和块文件的布局？并且为什么存在最后一个包含 wal 文件夹？理解这两个疑问便能解决九成的问题。
许多小型数据库
我们分割横轴，即将时间域分割为不重叠的块。每一块扮演着完全独立的数据库，它包含该时间窗口所有的时间序列数据。因此，它拥有自己的索引和一系列块文件。
t0 t1 t2 t3 now
+-----------+ +-----------+ +-----------+ +-----------+
| | | | | | | | +------------+
| | | | | | | mutable | <--- write ---- ┤ Prometheus |
| | | | | | | | +------------+
+-----------+ +-----------+ +-----------+ +-----------+ ^
+--------------+-------+------+--------------+ |
| query
| |
merge -------------------------------------------------+
每一块的数据都是 不可变的 。当然，当我们采集新数据时，我们必须能向最近的块中添加新的序列和样本。对于该数据块，所有新的数据都将写入内存中的数据库中，它与我们的持久化的数据块一样提供了查找属性。内存中的数据结构可以高效地更新。为了防止数据丢失，所有传入的数据同样被写入临时的 预写日志 中，这就是 wal 文件夹中的一些列文件，我们可以在重新启动时通过它们重新填充内存数据库。
所有这些文件都带有序列化格式，有我们所期望的所有东西：许多标志、偏移量、变体和 CRC32 校验和。纸上得来终觉浅，绝知此事要躬行。
这种布局允许我们扩展查询范围到所有相关的块上。每个块上的部分结果最终合并成完整的结果。
这种横向分割增加了一些很棒的功能：
- 当查询一个时间范围，我们可以简单地忽略所有范围之外的数据块。通过减少需要检查的数据集，它可以初步解决序列分流的问题。
- 当完成一个块，我们可以通过顺序的写入大文件从内存数据库中保存数据。这样可以避免任何的写入放大，并且 SSD 与 HDD 均适用。
- 我们延续了 V2 存储系统的一个好的特性，最近使用而被多次查询的数据块，总是保留在内存中。
- 很好，我们也不再受限于 1KiB 的数据块尺寸，以使数据在磁盘上更好地对齐。我们可以挑选对单个数据点和压缩格式最合理的尺寸。
- 删除旧数据变得极为简单快捷。我们仅仅只需删除一个文件夹。记住，在旧的存储系统中我们不得不花数个小时分析并重写数亿个文件。
每个块还包含了 meta.json 文件。它简单地保存了关于块的存储状态和包含的数据，以便轻松了解存储状态及其包含的数据。
mmap
将数百万个小文件合并为少数几个大文件使得我们用很小的开销就能保持所有的文件都打开。这就解除了对 mmap(2) 的使用的阻碍，这是一个允许我们通过文件透明地回传虚拟内存的系统调用。简单起见，你可以将其视为 交换空间 ，只是我们所有的数据已经保存在了磁盘上，并且当数据换出内存后不再会发生写入。
这意味着我们可以当作所有数据库的内容都视为在内存中却不占用任何物理内存。仅当我们访问数据库文件某些字节范围时，操作系统才会从磁盘上 惰性加载 页数据。这使得我们将所有数据持久化相关的内存管理都交给了操作系统。通常，操作系统更有资格作出这样的决定，因为它可以全面了解整个机器和进程。查询的数据可以相当积极的缓存进内存，但内存压力会使得页被换出。如果机器拥有未使用的内存，Prometheus 目前将会高兴地缓存整个数据库，但是一旦其他进程需要，它就会立刻返回那些内存。
因此，查询不再轻易地使我们的进程 OOM，因为查询的是更多的持久化的数据而不是装入内存中的数据。内存缓存大小变得完全自适应，并且仅当查询真正需要时数据才会被加载。
就个人理解，这就是当今大多数数据库的工作方式，如果磁盘格式允许，这是一种理想的方式，——除非有人自信能在这个过程中超越操作系统。我们做了很少的工作但确实从外面获得了很多功能。
压缩
存储系统需要定期“切”出新块并将之前完成的块写入到磁盘中。仅在块成功的持久化之后，才会被删除之前用来恢复内存块的日志文件（wal）。
我们希望将每个块的保存时间设置的相对短一些（通常配置为 2 小时），以避免内存中积累太多的数据。当查询多个块，我们必须将它们的结果合并为一个整体的结果。合并过程显然会消耗资源，一个星期的查询不应该由超过 80 个的部分结果所组成。
为了实现两者，我们引入 压缩 。压缩描述了一个过程：取一个或更多个数据块并将其写入一个可能更大的块中。它也可以在此过程中修改现有的数据。例如，清除已经删除的数据，或重建样本块以提升查询性能。
t0 t1 t2 t3 t4 now
+------------+ +----------+ +-----------+ +-----------+ +-----------+
| 1 | | 2 | | 3 | | 4 | | 5 mutable | before
+------------+ +----------+ +-----------+ +-----------+ +-----------+
+-----------------------------------------+ +-----------+ +-----------+
| 1 compacted | | 4 | | 5 mutable | after (option A)
+-----------------------------------------+ +-----------+ +-----------+
+--------------------------+ +--------------------------+ +-----------+
| 1 compacted | | 3 compacted | | 5 mutable | after (option B)
+--------------------------+ +--------------------------+ +-----------+
在这个例子中我们有顺序块 [1,2,3,4]。块 1、2、3 可以压缩在一起，新的布局将会是 [1,4]。或者，将它们成对压缩为 [1,3]。所有的时间序列数据仍然存在，但现在整体上保存在更少的块中。这极大程度地缩减了查询时间的消耗，因为需要合并的部分查询结果变得更少了。
保留
我们看到了删除旧的数据在 V2 存储系统中是一个缓慢的过程，并且消耗 CPU、内存和磁盘。如何才能在我们基于块的设计上清除旧的数据？相当简单，只要删除我们配置的保留时间窗口里没有数据的块文件夹即可。在下面的例子中，块 1 可以被安全地删除，而块 2 则必须一直保留，直到它落在保留窗口边界之外。
|
+------------+ +----+-----+ +-----------+ +-----------+ +-----------+
| 1 | | 2 | | | 3 | | 4 | | 5 | . . .
+------------+ +----+-----+ +-----------+ +-----------+ +--------