SIGMOD'22 论文阅读：TimeUnion一种具有统一数据模型和 ...

西门无雪

本文阅读了下SIGMOD'22发表的有关时序数据库的一篇论文，论文题目为：《TimeUnion: An Efficient Architecture with Unified Data Model for Timeseries Management Systems on Hybrid Cloud Storage 》，即一种具有统一数据模型和混合云存储支持的高效时间序列管理系统架构。论文先阐明了当前时序数据存储管理上存在的问题和面临的挑战，然后针对这些挑战在数据模型、内存结构、弹性时间分区LSM-Tree等几个方面提出了相应的解决方案，并通过实验验证了这些方案是可行的。文中斜体为笔者注。
论文原文下载地址。论文代码下载地址。
背景

这篇论文首先分析了云存储的特性和优势，然后指出了现有时序数据库（如InfluxDB、Prometheus等）存在的资源使用问题和数据模型问题以及在云上部署现有系统以管理大量时间序列时，存在的几个关键问题，如下所示。

• 资源利用不平衡。在现有时序管理系统的设计中，在内存分区中为每个时间线的每个标签对动态建立倒排索引。这样的索引占用大量内存，特别是对于高基数时间序列数据（即所有时间序列的数百万个唯一标签对）。此外，对于磁盘分区，元数据（例如标签对和符号）通常被加载到内存中以加速查询，这会导致不可忽略的内存使用。此外，为了获得高压缩比，每个时间序列的数据样本首先被缓存并用相对较大的内存块（例如 Prometheus 中的 120 个样本）进行压缩。因此，随着系统管理的时间序列数量的增加，内存使用量会呈爆炸式增长，系统很容易因内存耗尽而挂起。即现有的时序数据库在高基数时间序列数据场景下内存使用上存在较大的挑战。
  
• 未探索的多层云存储。没有探索在多层存储和混合云存储上部署时间序列管理系统。引入混合云存储时，成本/性能差距会带来新的挑战。首先，我们需要在不阻塞数据插入的情况下，快速处理系统写入路径中的冷热数据分离和迁移。其次，由于快速存储有限，需要设计一种新的机制来动态调整快速存储中的数据大小。第三，由于大多数冷数据都保存在慢速存储中，因此对系统查询路径的优化至关重要（例如缓存机制和缓存粒度）。因此，迫切需要一种新的时间序列管理系统设计，以充分利用不同的云存储层。即在云上部署时保持时序数据读写的高性能，同时利用冷热分层存储降低时序数据的存储成本。
  
• 有限的分组支持。时间序列组在许多现实世界的用例中自然形成（例如来自同一虚拟机、docker 容器、物联网传感器等的指标）。然而现有的系统，如 Prometheus 和 InfluxDB，在物理上独立地管理和存储每个时间序列。在数据模型层面，InfluxDB 支持时间序列共享一组标签对并拥有自己的字段/度量的简单分组。但是，该方案不能覆盖组中的时间序列也有自己独特的标签的情况，这是性能监控中的常见情况。 即使用分组模式进行索引成本和存储成本优化。
  

为了解决上述问题，论文提出了 TimeUnion，即一种具有统一数据模型和混合云存储支持的高效时间序列管理系统，主要贡献包括云存储特性探索、统一数据模型、高效的内存数据结构、弹性时间分区LSM-Tree等四个方面。
其中，对于云存储特性的探索。论文基于AWS对比了内存和块存储EBS以及对象存储S3的价格和性能差距。对于价差异，内存价格至少比EBS贵了两个数量级。对于读写性能，比较了EBS和S3在读写不同大小的数据块时性能上的差距。如图 1b 所示，对于小型写入，EBS 至少比 S3 快三个数量级。尽管由于 S3 的高网络带宽，差距随着写入大小的增加而逐渐缩小，但对于 32MB 的写入，EBS 仍然比 S3 快 3 倍。如图 1c 所示，EBS 平均比 S3 快 30 倍。此外，第一次读取比 EBS 和 S3 的后续读取慢 1.8 倍和 71%。此外，对于EBS和S3，当读取大小小于16KB时，读取延迟是稳定的，这可以作为有效阅读的单位。  


设计

时间序列管理系统需要保证大量时间序列的高插入吞吐量和频繁的数据样本生成。因此，时序数据库的一般系统架构，如图 2 所示。系统首先会在内存中为传入时间序列进行批量写入和构建索引。在特定时间段后（例如 Prometheus 中的 2 小时），所有内存数据被刷新到磁盘，形成一个独立的分区，该分区具有对应于特定时间范围的持久索引。此外，对于磁盘上的块，当它们的数量达到特定阈值时，它们将被合并成更大的块。


然而，这样的架构暴露了以下几个问题。

• 内存压力大。因为所有时间序列的数据样本和索引都需要先在内存中进行批处理。随着时间序列的数量和数据样本密度的增加，内存使用量会呈爆炸式增长。
  
• 数据刷盘会严重影响系统的性能。在数据flushing的时候，系统需要flush和clean所有相关的内存数据结构，这会导致与此时传入的insertion和query发生严重的争用。
  
• 处理乱序数据样本很困难（例如 Prometheus 甚至不支持这一点）。乱序的数据样本会影响内存数据的刷盘时机，因此需要一个额外的机制来批处理和刷盘这些乱序的数据样本。例如，在内存中为那些乱序的时间序列维护额外的空间，并且在数据刷盘时，需要在现有块下创建额外的数据块文件和索引。
  

统一数据模型

对于时序数据而言，时间序列由两个部分组成，即标识符和数据样本。标识符是一组标签对，数据样本为时间戳和指标值。其中，标签对通常会用于构建倒排索引以支持时间序列的多维检索，如Promethues和InfluxDB。
论文中提到的统一数据模型，包含逻辑视图和物理视图两个部分。
逻辑视图。逻辑视图的如图6所示。在统一数据模型中，时间序列可以表示为单独或属于特定组的一个时间序列。时间序列标识符由一组标签表示，它们可以转换为组表示。


需要为组中的所有时间序列指定共享组标签。当向组中添加新的时间序列时，提取组标签，而其他标签用于唯一标识组内的时间序列。对于每个组为其分配一个唯一的 ID，并且在为组时间序列的所有标签构建倒排索引时，使用分组 ID 作为倒排列表ID。
图 5 是为分组构建倒排索引的示例，图中显示了同一区域下两个设备的时间序列示例。如果不分组，“region=1”和“device=1”的postings列表的长度都是2000。如果将所有时间序列聚集到一个组中，共享组标签“region=1”，分组ID为1，长度“region=1”和“device=1”的倒排列表的数量都变为1，因为它们都表示分组1。此外，通过分组只需要为整个组存储一次标签“region=1”。 由此可见，分组后的倒排索引的的倒排列表能大大减少，相同分组下的时间线越多，节省的索引项的存储成本越多。


但是这里面存在两个挑战，首先，需要另一层索引来定位组内的特定时间序列。其次，在将组数据模型与物理数据存储连接起来时，需要考虑（1）当前元组中新增和缺失时间序列的数据样本； (2)乱序数据样本。
物理视图。论文提出的物理视图如 图7 所示。内存中分别管理单独的时间序列和分组后时间序列。其中，对于每个分组，通过共享相同的时间戳列来删除冗余时间戳；而每个时间序列的度量值是独立存储的。这个做法和Apache IoTDB的对齐时间序列相似，多个指标值的时间戳只存储一份，降低了时间戳的存储开销。


对于一个组的数据插入，有以下四种情况：
(1) 普通插入：将时间戳附加到时间戳列Timestamps，度量值附加到各自时间序列的度量值列Values中。
(2) 插入新的时间序列：首先，从新的时间序列中提取唯一标签并将它们插入组的时间序列标签数组中。其次，创建一个新的度量值列，并用 NULL 值填充此列中的先前值。论文扩展了Gorilla中的XOR 算法，使用额外的控制位来支持 NULL 值。最后，执行正常插入。
(3) 插入缺少时间序列：对于本轮缺失的timeseries，用NULL值填充，如图7中TS3所示。
(4) 乱序插入：根据时间戳搜索相应的槽，并确定是替换现有值还是插入新值。此外，如果插入时间戳早于当前时间分区，它可能会触发当前块的早期刷新，细节部分将在 “弹性时间分区LSM-Tree”中讨论。
高效的内存数据结构

论文中，测试了时序数据库Promtheus在不同场景下的内存消耗情况，实验表明内存压力主要集中在倒排索引、块元数据、数据样本等几个部分上面。
如图3a所示，当只有索引而没有任何数据样本时，内存使用量随着时间序列的数量线性增加。当以 10 秒和 60 秒的数据间隔分别插入 2 小时的随机数据样本时， 10 秒和 60 秒采样间隔的整体内存使用率比没有数据采样时高 51% 和 31%。当将数据样本的时间跨度增加到 12 小时时，内存使用量可能会进一步增加，因为 Prometheus 需要加载刷新分区的元数据。
在数据间隔为60 秒，且时间跨度为 12 小时的情况下，倒排索引、块元数据和数据样本分别占内存使用的 51%、34% 和 15%，如图3b所示。倒排索引和块元数据内存占用高的主要原因是它们是由嵌套哈希表维护的，需要额外的空间来降低碰撞率。 因此，迫切需要利用更高效的内存数据结构来处理倒排索引和块元数据。此外，还需要通过在压缩块完成后将其移动到持久存储来减少缓存数据样本的大小。


论文中针对倒排索引、块元数据和数据样本的内存占用过高问题，主要是通过mmap文件进行避免。

• 倒排索引：使用的是double-array trie 结合mmap文件的方式避免内存占用过高的问题。
  
• 时间序列标签：通过倒排索引，可以获得倒排列表，通过倒排列表中的ID，可以定位到目标时间序列。对于每个时间序列，它作为一个内存对象进行管理，其中包含该时间序列的所有标签对和内存数据样本。同样，为了避免 OOM 问题，论文中将这些标签存储在 mmap 文件中。
  
• 数据样本：对于每个时间序列和分组，在内存中批处理少量数据样本（即 32 个）以进行即时压缩和高效刷新。用户可以调整此数字以在压缩率和内存使用之间进行权衡（即，较大的块具有更好的压缩率）。图 9 显示了时间序列和组的不同 mmap 文件数组，可以动态扩展。 mmap文件被分割成一系列固定大小的chunk来存储数据样本的压缩字节，header包含一个位图来指示每个chunk的占用。其中，对于单独的时间序列，时间戳和度量值一起存储到各个时间序列的同一块中；对于分组的时间序列，共享时间戳和指标值分开存储。最后如图7所示，当当前chunk满时，将其序列化为byte数组，然后作为key-value对的值插入到时间分区LSM-tree中，同时清理mmap 文件中对应的区域。
  

弹性时间分区LSM-Tree

日志结构合并树LSM-Tree以其良好的插入性能和可接受的查询性能下降而闻名。时序数据的主要特点是写多读少，吞吐量高，因此LSM-Tree天然就是比较适合用于时序数据的存储。但是基于LSM-Tree的键值存储引擎，一般具有不同程度的读/写/空间放大问题，比如 LevelDB 和 RocksDB等。
论文中，将Golang 版本的 LevelDB 实现集成到 Prometheus tsdb 中，对比了基于LevelDB的存储引擎和原始 Prometheus tsdb存储引擎在写入吞吐、写放大两个方面的差异，以研究利用 LSM-Tree 作为时间序列管理系统的存储数据结构的能力，如 图4 所示。


如图 4a 的顶部图表所示，集成原型的写入吞吐量仅比 Prometheus tsdb 低 1.6%。如图 4a 底部图表所示，与 Prometheus tsdb 相比，LevelDB 花费了 18% 更多的时间来完成所有compaction。如图 4b 的顶部图表所示，与 Prometheus tsdb 相比，LevelDB 向磁盘写入的数据仅多 2.4%。但是如图 4b 所示，平均而言在compaction中却多读取了36% 的 SSTable。另外，实验结果显示对于每个compaction，至少需要从下一层读取一个重叠的SSTable。
LSM-Tree存储需要通过compaction机制来平衡写、读、空间等放大问题。论文上述实验结果表明，不考虑时序数据的特性情况下，直接套用通用的LSM-Tree存储结构下，在写放大、空间放大等方面仍然有较大的挑战。
时序数据天然带有时间戳，数据在时间戳的加持下，极少有重复数据，几乎没有update和delete操作，大部分时间下数据是按照时间顺序写入的，偶尔有乱序数据。如果写入处理得当，时序数据落盘的SSTable几乎是没有重叠的，自然不用考虑通过compaction机制来平衡读写放大问题了，只需主要考虑通过compaction机制来增加数据的压缩率或者将数据移动到低成本的存储介质上存储或者两者并重。
在论文中，针对时序数据的特性，提出了一种为混合云存储量身定制的弹性时间分区 LSM-Tree，针对不同的存储层应用不同的compaction机制，并且可以动态适配快速存储的预定义的使用阈值，以减少compaction过程中低效的数据读取，如 图10 所示。 整体上，论文中提出的LSM-Tree是基于LevelDB改进而来，主要改进了WAL和Compaction机制。


论文提出的弹性时间分区 LSM-Tree共计包括键值格式、存储结构、在快云存储上的compaction、在慢云存储上的compaction、Compaction成本分析、乱序数据处理、动态大小控制、日志、数据保留等9个部分。
键值格式

如图 10 顶部所示，分别使用大端编码将时间序列/组 ID 和时间序列/组块的起始时间戳存储在第一和第二个 64 位中。因此，可以将来自相同时间序列/组的块组合在一起，同时根据起始时间戳对它们进行排序，这提供了数据局部性以加速扫描查询。对于键值对的值，直接使用特定时间序列/组的数据块的序列化字节。
存储结构

如图 10 所示，LSM-tree 仅维护位于不同存储层的三个级别。 0 级和 1 级在快速云存储（即 AWS EBS）上管理相对少量的时间序列数据（即最近 2 小时）。对于较旧的数据，仅在存储在慢速云存储（即 AWS S3）上的一级（即 2 级）中进行管理，以避免不必要的compaction。由于时间序列数据是按时间戳排序的，可以根据不同级别的不同时间范围对SSTables进行分区，以控制每个级别的大小。对于 0 级和 1 级，时间分区长度从一个相对较小的值开始（例如 30 分钟），该值将根据快速存储的预定义大小限制进行动态调整。特定时间分区的SSTables中数据块的数据样本严格受分区时间范围的限制。当 SSTables 被合并到 2 级时，几个分区被合并以创建更大的分区（即 2 小时）。同样，此时分区长度也是自动适配的。
在快云存储上的compaction

当在内存中批处理的小块数据样本已满时，它将被序列化并插入到 MemTable 中。当 MemTable 已满时，它会切换到 Immutable MemTable 并创建一个新的 MemTable。为了减轻 Immutable MemTable 刷盘期间的插入阻塞，论文使用 Immutable MemTable 队列扩展 LevelDB 以允许同时进行多个刷盘。在 Immutable MemTable 的刷新过程中，键值对根据键中包含的时间戳分为不同的时间分区（即最初为 30 分钟）。
当level 0的累计时间分区超过阈值（比如2个）时，会触发将level 0中最旧的时间分区从level 0 compaction到level 1。在快云存储上保持两个level有两个考虑。首先，将相同时间序列/组的键值对合并为更大的键值对，以获得更好的压缩率。其次，由于level 0 的时间分区中相同时间序列/组的数据块可能分散在不同的 SSTable 中，因此在压缩过程中，将相同时间序列/组的键值对收集到相同的 SSTable 中以实现更好的数据局部性。如果所选的 level 0 分区是无序的（陈旧的），TimeUnion 会将其与 level 1 中的重叠分区合并。
在慢云存储上的compaction

当 level 0 时间分区的总时间跨度超过 level 2 分区长度（例如最初为 2 小时）时，将触发从 level 1 到 level 2 的的compaction。Compaction的过程如下。

• 首先，选择时间范围在level 2层中最新时间分区的时间范围内的level 1的最老时间分区。如 图10 中的 "16:00 - 16: 30" 和 "16:30 - 17: 00" 两个level 1时间分区将会被选择。
  
• 其次，将键值对排序合并生成新的SSTable，并将相同时间序列/组的键值对聚集在同一个SSTable中。
  
• 最后，将新的 SSTables 上传到慢云存储，并删除快云存储中的临时 SSTables。如果所选的 level 1 分区是乱序的并且与现有的 level 2 分区重叠，则将生成“patches”并将其附加到相应的分区，这将在后面的乱序数据处理中进行介绍。
  

通过这种compaction机制，慢速云存储只需一层，避免了在compaction过程时从慢云存储中读取重叠的SSTables中的大部分有序数据，显着减少了到慢云存储的流量请求。
Compaction成本分析

这个小节，主要通过成本分析公式以定量分析在慢云存储上只保留一个level的好处。由于慢云存储的数据流量是读写的主要瓶颈，因此论文使用慢云存储中的数据写入大小来衡量成本，compaction写入到慢云存储中的总大小越小越好。 更多详情可以参考论文原文。
乱序数据处理

在 Immutable MemTable 的刷盘过程中，会检测到乱序的数据，并将其插入相应的时间分区（例如图 10 中 L0 中的 8:30-9:00 时间分区）。
对于 level 0 中的乱序时间分区的compaction，如果在level 1 中存在时间范围重叠的时间分区，TimeUnion 将像传统的基于level的compaction一样将它们排序合并在一起。如果有多个具有相同时间戳的相同时间序列的数据样本，TimeUnion 将从最新的 SSTable 中保留数据样本。
此外，对于分组块，通过向那些缺失的时间序列填充 NULL 值来处理两个分组块（即新的和缺失的时间序列）中的不一致。（笔者注：造成填充NULL值问题的原因是因为分组块中多个时间序列共享了时间戳）。因为 level 0 和 level 1 驻留在快云存储中，所以合并乱序时间分区的开销相对较小。
对于从 level 1 到 level 2 的乱序时间分区的compaction，通过时间分区的设计，我们可以避免合并存储在慢云存储中 level 2中的 SSTables 的巨大开销。具体来说，在level 2的时间分区中记录每个SSTable的时间序列/分组的ID range。根据SSTables的ID ranges，分离键值对，生成特殊的SSTables——即patches，附加到在level 2中相应时间分区的的SSTables集合中。
为了避免为level 2 中的每个 SSTable 积累过多的patches，为用户提供了一个可调整的阈值（例如3）。当一个 SSTable 的patches数量超过阈值时，将触发合并，合并该 SSTable 及其所有patches。如图 11 所示，SSTable 1 及其patches被合并，并生成两个具有不相交 ID 范围的新 SSTable（即 SSTable 1-1 和 SSTable 1-2）。


动态大小控制

考虑到快云存储的成本相对较高，需要考虑在快存储有限的可用容量上存储尽可能多的数据。因此，论文中提出了一种根据快存储使用率自动调整时间分区长度的机制，基本逻辑如算法 1 所示。如果当前 level 0 和 level 1的大小超过阈值，将减少时间分区的长度的大小。如果level 1 的总时间跨度足够大但总大小小于阈值（例如，数据样本稀疏，或者时间序列数量少），会增加分区长度。此外，为了便于compaction期间的时间分区对齐，在动态控制期间将可调的时间分区长度乘/除以 2。


通过动态大小控制，可能需要在compaction期间处理具有不同时间分区长度的时间分区。因此需要仔细的时间分区拆分和对齐，策略如下：

• (1) 对于 L0-L1 compaction，由于所有重叠的 SSTable 将被读取和合并，TimeUnion 使用所有选定分区的最短时间分区长度作为新分区的长度，并将它们与其对齐。
  
• (2) 对于 L1-L2 compaction，由于重叠的 level-2 分区中的数据不会被合并，TimeUnion 需要保留这些分区并为它们生成patches。而对于时间范围未被选中的level-2分区覆盖的时间分区，则按照选中的level 2分区的最短时间分区长度进行拆分对齐。
  

在图 12 中，L0-L1 compaction生成具有最短时间分区长度的新分区（“8:00-8:15”分区的 15 分钟）。对于右边的L1-L2 compaction，“8:30-8:45”和“9:00-10:00” level 2分区保持不变。而对于这两个分区未覆盖的时间段，则按照最短的level 2时间分区长度（“8:30-8:45”分区的15分钟）进行拆分对齐。


日志

为了从崩溃中恢复内存中的索引、数据样本、MemTable 和 Immutable MemTable，论文禁用了 LevelDB 中的原始日志记录实现，并重新设计了一个新的日志记录方案。对于每个时间序列和组，都有一个序列 ID（笔者注：这个序列ID就是日志序列编号LSN，与倒排索引中的ID是不同的。），它会随着每个插入的数据样本进行记录和递增。当一个数据块被刷新到时间分区的 LSM-tree 时，序列 ID 被嵌入到序列化字节的开头。然后，当一个MemTable被刷盘到level 0时，对于每一个键值对，会写一条特殊的日志记录和对应的序列ID，来表示在这个ID之前的日志项都可以安全被删除，后台线程将定期清除这些陈旧的日志记录。
数据保留

在 TimeUnion 中，后台线程将定期检查用户提供的保留时间之外的旧时间分区，然后删除那些旧分区中包含的 SSTable。此外，还需要清除内存中那些那些数据样本全部被删除的旧时间序列的内存对象，具体做法是，TimeUnion在时间序列的内存对象中记录每个时间序列的最新数据样本的时间戳，那些比保留时间戳更旧的内存对象对象将被清除。
总结

论文中主要针对现有时间序列管理系统面临的内存压力、乱序数据写入等问题，并结合云存储的特性，提出了一种具有统一数据模型和混合云存储支持的高效时间序列管理系统架构，包含分组数据模型、高效的内存数据结构、弹性时间分区LSM-Tree引等部分，在一定程度上缓解了时间序列管理系统的不平衡资源使用问题。
其中，分组数据模型、按照时间分区的compaction机制、乱序数据处理机制具有较大的借鉴价值。但是论文中只提及了对于数据样本的时间分区，没有对时间序列的元数据及倒排索引进行时间分区，在时间序列发散的场景下（比如K8s场景下的朝生夕死的POD应用监控），时间序列的元数据和倒排索引的时间过期依然存在较大的挑战。