这是2024年的第30篇文章
（ 本文阅读时间：15分钟 ）
01
前言
时序数据库管理系统（TSDB）近些年受到较多的关注，在性能监控场景更是起到了至关重要的作用。Khronos是阿里目前规模最大的时序存储引擎，由智能引擎事业部自研推出，为集团业务提供时序数据的存储能力和实时分析能力。我们之前的技术文章对该引擎进行过系统性的介绍，感兴趣的读者可以阅读回顾：《Khronos: 面向万亿规模时间线的性能监控引擎建设实践》在本篇文章中，我们将着重介绍Khronos在实时索引构建优化上的实践。
我们定义实效性延迟为用户写入数据到数据可被检索到的时间gap。在TSDB中，用户期待实时写入的指标数据立即可见（秒级实效性），然而我们发现通用的Log-Structured Merge-Tree（LSM）架构在segment切换时，由于索引构建压力加剧，会出现写入实效性延迟到分钟级别的抖动，严重影响用户体验。本文首先通过实验分析了基于LSM架构数据实效性延迟的原因，并针对性地提出了补集索引的设计思路，即依赖前序构建好的索引，仅对之前未出现的时间线构建索引，减少索引构建开销。第二，我们设计了基于Minimum Excluded（Mex）的索引结构高效的复用前序segment构建的索引。第三，我们利用补集索引无冗余的特性，提出了查询中间结果复用的方案避免查询过程中索引的重复遍历。最后，我们提出索引补全策略避免过长依赖带来的查询和内存开销。
实验证明Khronos提出的补集索引方案大幅降低了实效性延迟，系统的最高实效性延迟从分钟级别降低到秒级，同时和业界时序数据库InfluxDB和TimeScaleDB相比，Khronos写入吞吐提升至少4倍，查询延迟降低至少6倍。补集索引的设计也被信息检索领域顶会之一CIKM2023接收。
论文题目：《Khronos: A Real-Time Indexing Framework for Time Series Databases on Large-Scale Performance Monitoring Systems》
论文链接：https://dl.acm.org/doi/10.1145/3583780.3614944
【文末点击阅读原文即可跳转哦】
02
背景知识
KMonitor是阿里集团搜索推荐业务广泛使用的数据监控平台，它具有实时性、巨量metric和多指标运算性能的特点。经过多年的稳定运行和不断优化，KMonitor 已经广泛部署于集团电商业务的核心集群中，并且逐步替换成为基础系统监控的主力。支撑KMonitor的核心是Khronos时序存储引擎，自2020年起，为KMonitor平台提供了强有力的后端支持，满足了业务每年呈倍数增长的需求。Khronos已经连续四年稳健应对“双十一”期间的查询和写入高峰，累计存储了超过数十PB的监控数据，同时确保了秒级的响应时延。
2.1 数据建模
监控数据一般被建模为多维度时间序列。图1 (a)展示了我们的数据建模方式，series key唯一决定一条时间线，由metric指标名和一组tags（tagk:tagv）组成。同时每条时间线还包含一组时间点序列，每个时间点由一个时间戳和多个field值组成。例如图(a)中最后一行表示部署在机器10.10.10.5上的khronos的应用，每10s会汇报cpu各个核的使用率。tagk一般表示被监控实体的属性和维度（例如app，tenant，host）。
2.2 查询模式
时序数据的查询通常包括一个指标名，一个时间区间和一组tag条件，tag条件又可分为直接匹配和模糊匹配。例如：
在上面的查询中，我们期待召回时间10-35区间，khronos应用下，机器ip满足一个正则表达式的cpu利用率。app="khronos"就是直接匹配而host=Regex(xxx)即为模糊匹配。
2.3 时间线索引
在Khronos中我们对每条时间线构建倒排和前缀树索引，如图1（b)所示。每个时间线分配唯一的seriesId（图1(a)的第一列）。对于倒排索引，我们将seriesKey拆分成metric和tagk:tagv的token，将seriesId写入对应的倒排列表（如图1（b)上）。对于前缀树索引，我们将seriesKey拆分metric-tagk-tagv的token插入前缀树（如图1（b)下）。倒排索引一般用于直接匹配而前缀树索引的作用是为了模糊匹配和查询下拉提示等。
2.4 写入负载分析
时间局部性：性能监控场景的时序数据通常具有时间局部性，即一条时间线通常会稳定的按照某个固定的时间间隔汇报数据，例如每台物理机每10s汇报其cpu使用情况。
Series churn问题 [1]：随着时间的推移，不断有时间线消亡（也就是不再有新的时间点写入），同时也不断有新的时间线产生。这就意味着数据库中的时间线总基数会随时间不断增长，而活跃的时间线规模远小于总基数，业界通常称其为series churn。Khronos中我们发现时间线的生命周期通常小于1h（如图2右），这通常是由于任务自动调度或者定时的短期任务导致。
例如图2左上，taskB任务首先调度在host 1.1.1.2上，汇报了红色的三条时间线，某时刻由于负载均衡等原因taskB被调度到新的机器上host 1.1.1.5，生成了新的不同host tag的黄色时间线。而原机器上的时间线（红色）不再汇报，变为不活跃（消亡）。Series Churn问题意味着，在一定时间T内活跃的线（活跃指的是线的生命周期与指定时间范围T有交集）的比例远小于数据库中总时间线数量。
例如图2左中时间60-90区间，仅有4条时间线活跃（taskB 3条黄色和taskA一条蓝色），而数据库中总线数是12条。
2.5 布局存储
在这种数据负载下，全局索引将会引入极大的读放大。一方面写入过程中需要判断每一条消息是否是存量的时间线，如果是则不需要构建索引，如果不是则需要分配seriesId，构建对应的索引。而查找的效率随着全局索引的规模增大而逐步降低。另一方面，虽然绝大部分时间线在数据库中已经消亡，活跃的时间线集合很小，但查询过程仍需要在全局索引中召回满足条件的时间线，读放大明显 。图3左展示了Khronos中部分租户的时间线基数。图3右中我们测试了基于全局索引的InfluxDB，我们发现其写入性能和查询效率随着数据库中累计的时间线基数增加而逐步下降，系统只能支持30M的基数，完全无法满足我们线上万亿时间线的基数规模。
因此对于性能监控这种高基数场景，通常采用根据时间区间分segment的数据组织方式。写入数据根据时间范围划分segment，每个segment是自解释的，包含其对应时间区间的局部索引和时间点数据。实时写入数据先在内存中构建，当segment大小或时间区间超过阈值，会seal该segment，进行整理刷盘，同时内存中开启一个新的segment接受实时写入。
这种类LSM的设计避免了全局索引的放大，也更好的适应用户查询。首先最近的数据一般访问频率更高，其驻留在内存，查询性能更优。而且在查询过程中，可根据用户指定的时间区间访问对应的segment，避免GL中对消亡线的索引遍历。
03
Motivation
3.1 实效性延迟抖动分析
然而在SL的设计中，每个segment启动时，segment从空开始构建，也就意味着此时每个写入消息都会被认为是一条新线（即不在SL索引中），需要构建索引，例如图5中和在启动时需要构建索引（虽然这两条线已经在中构建过索引了）。因此在segment启动阶段索引的构建压力飙高（图4左上所示）。而索引构建相比于数据点的写入引入了更多的计算和内存访问，因此索引写入能力更低。综上，SL的设计在segment启动时会导致巨大的索引构建压力，超过系统处理上限，从而导致数据堆积，数据实效性受到影响（图4左下所示）。在生产环境我们发现，这种数据实效性抖动每30分钟触发一次，每次持续几分钟，极大的影响了用户体验。
3.2 现有解决方案
加资源 [2, 3]：最直接的方式是增加更多的计算资源，但是在segment启动时启动更多构建线程会抢占查询的cpu，影响实时查询效率，同时我们测试发现索引构建开销是写入点数据的10-15倍，理论上需要加10-15倍的计算资源才可解决实效性延迟问题，非常浪费。
强schema [4-6]：业界的另一种方案[2,3]是通过强制schema限制tag和field的数量，从而控制时间线基数。然而这种方案限制了使用的灵活性，每次加入一个维度都需要更新配置，同时也增加了配置管理的难度。
定期清理消亡线 [7]：Prometheus采用定期起任务从实时索引中删除不活跃的线对应的索引来解决series churn问题，然而删除操作会阻塞实时数据写入，引入了新的实效性延迟，如图4右侧。
3.3 补集索引的设计思路和挑战
SL索引实效性问题的关键在于索引的冗余构建：如果一条时间线的生命周期横跨多个segment，那它会在每个segment中被重复构建索引，比如图5中线。我们分析数据特征可发现，由于时序数据的时间局部性，相邻的segment间的时间线至少70%是重叠的，也就意味着对这70%的时间线我们可以保存他们在上segment中构建索引的引用，而真正的索引构建由另外30%的新线触发。如下图所示。
由此在Khronos中，我们提出了补集索引（Complementary index）的概念，即仅构建不在上个segment中的时间线。每个segment的补集索引包括两个部分（a) 在当前segment中新线构建的索引（局部索引）和(b) 对上一个segment的索引的引用（依赖索引）。例如在下图中对于，其补集索引包括（a) 和（b）,。
图5展示了GL、SL、和补集索引的索引构建部分。和GL相比，SL根据时间划分segment，避免了GL的读放大问题；和SL相比，SL去除了冗余索引的构建从而避免了实效性延迟的问题。补集索引结合了GL索引无冗余的优势和SL索引极低的读放大的特点，取得了更好的tradeoff。
然而补集索引的设计也带来了诸多挑战：
索引组织：为了复用之前segment的索引内容，索引的结构需重新设计，例如seriesId的分配。全局seriesId很容易突破4字节的位宽，影响存储和压缩效率，而segment内自编号则可能导致倒排索引复用时出现seriesId冲突。
查询效率：补集索引需要从多个依赖的segment中遍历索引，有可能增加查询延迟。
索引依赖：在segment间连续的索引依赖形成了一条依赖链，例如图5中的索引实际只在中构建，和只存储其索引的引用。因此依赖，而依赖，形成了一条长度为3的依赖链。如果依赖链无限延长，就趋近于一个GL，过长的依赖链会增加内存使用，同时也会影响查询效率。
至此，我们已经介绍了补集索引的基本思路，即通过减少冗余的索引构建降低实效性延迟，而后续的部分我们将详细解释补集索引的实现细节，例如索引的引用如何实现，索引如何组织来支持segment间索引的复用，查询如何保证高效且准确，过长索引依赖如何处理等。
04
系统架构
图6展示了我们的数据处理流程，从被监控实体采集的时序数据定期发送到Khronos，每条消息根据series key被散列到不同的partition，每个partition之间相互独立，互不通信。在每个partition中，构建线程将实时写入数据写进building segment，其中点数据写入buffer，并且为新线构建补集索引。
内存数据采用追加形式，支持实时查询。一旦building segment的时间区间超过一定阈值，系统会自动创建一个新的空segment用于接收实时写入，而之前的segment转化为dumping segment由异步线程进行整理、排序、去重，索引补全等操作，形成immutable segment，交由异步刷盘线程写入远端存储或者本地磁盘。同时离线会定期触发compaction任务进行数据整理，将flushed segment合并/拆分为时间区间无交集的compacted segment，减少查询访问的segment数量。
图7展示了我们的查询流程。查询首先(1)通过QRS被广播到全部partition。每个partition中，我们只会(2)访问与查询时间区间有交集的segment。在segment内，查询线程(3)遍历补集索引召回满足条件的seriesId。然后(4)根据seriesId取线和点数据，(5)相同时间线在不同segment中的时间线段会根据时间戳进行归并排序。(6)排序好的数据在返回QRS进行聚合，最终返回用户。segment内部索引部分的查询细节将在后续章节介绍。
05
5.1 写入流程
我们首先介绍一下Khronos的数据写入流程（算法1），我们为每个时间线分配一个点数据buffer。当从空初始创建时，我们首先判断输入的series key是否存在于前序中，如果存在，我们将其在中分配的seriesId作为引用存储到seriesIdList结构中，仅将点数据p写入buffer（算法4-6行），从而减少冗余索引的构建。反之，我们会通过Mex函数计算seriesId，并实际构建索引并插入点数据（算法8-11行）。在算法1中，seriesIdList可以看作一个特殊的倒排列表，其记录着写入segment的全部时间线（包含上个segment的引用和实际构建索引的时间线）。
seriesIdList在查询过程中起到了过滤不相关时间线的作用，我们在下一节详细介绍。
5.2 seriesId的分配方式
为了保证查询能准确的召回，seriesId的分配应该遵循以下原则：
seriesId应该单调递增以支持倒排列表的插入和高效的求交/求或计算。
对于之前已经存在的时间线，其seriesId应该和上一个segment保持一致以复用倒排索引，也就是有依赖关系的segment的倒排列表可以直接求交求或而无需转换seriesId。
新的时间线分配的seriesId应该保证和上一个segment的seriesIdList无交集以避免冲突。
基于以上原则，最直观的方式就是分配全局递增的seriesId，然而随着数据库中存储时间线基数的增加，全局seriesId很容易突破4字节位宽的限制（尤其是在khronos这种单租户万亿基数的场景下），增加存储成本同时也降低了压缩效率。因此我们引入了Mex函数来计算seriesId。Mex(S)返回集合S中最小的不在S中的整数。
例如Mex({0, 1, 3, 5}) = 2。在Khronos中，我们为每条新时间线分配最小的不在上一个和当前segment中的seriesId，即算法1中第8行。图8展示了全局递增（Max）和Mex seriesId的分配方式。其中方框内的字符标识时间线，而方框竖直对应的id标识其被分配的seriesId。例如中的seriesId被分配为4。图9展示了补集倒排索引的构建流程（和图8对应）。
Mex设计的精髓在于它安全地复用了不活跃的seriesId。在图8和9中，seriesId 2在中被分配给线，然而的生命周期并没有延续到。seriesId 2在和求交之后可以被轻易的过滤掉，因此seriesId 2对于来说是不活跃的。基于此，对于来说，不在和中的seriesId都可以安全的被复用。Mex索引的另一优势是其通过复用seriesId减少了倒排列表内id的gap值，更利于压缩，例如图8中，对，Max的而Mex方案的，gap值大大减小。
06
在本节中，我们将介绍补集索引的查询流程，其中我们提出了中间结果复用的方案避免重复的索引遍历，保证准确的结果召回。在介绍补集索引查询之前，我们先了解单个segment内部索引如何配合，根据用户查询召回满足条件的seriesId集合，如图10所示。
其中我们召回应用khronos，部署在特定机器上的cpu指标。(1) 我们遍历前缀树索引，得到所有tag host以10.10.12为前缀的tagv；(2) 通过正则过滤器过滤出10.10.12.11和10.10.12.15两个tagv；(3) 根据查询指定的metric和tag条件构造一棵查询树，每个叶子结点对应一个倒排列表，中间节点代表and/or操作；(4) 根据查询树和对应的倒排列表执行求交求或操作得到满足条件的seriesId集合{0, 2, 3, 7}。而后可根据seriesId在segment取出对应时间线的点数据进行归并等后续操作。
对于补集索引，我们首先在每个segment的局部索引中进行上图所示的索引遍历得到一个满足条件的seriesId集合。为了保证召回结果的完整，我们还需要沿着segment的依赖链遍历所有依赖的segment的索引。我们先从一个简单的例子开始，假设查询只需要访问一个segment，其索引只依赖，那么应召回的完整seriesId集合可表示为：
其中是遍历局部索引（也就是实际构建的索引）的召回结果，流程如图10。我们首先将的召回结果和求交，过滤掉不属于的不相关时间线，再将结果和的局部召回结果合并，即可得到完整准确的seriesId集合。之前提到记录了segment内的全部时间线，可通过与其求交过滤掉那些只属于前序segment的时间线。对于前缀树，由于索引复用，召回的tagv集合可能会存在false positive，但后续的倒排计算可保证最终召回seriesId集合的准确性。
接下来我们考虑复杂一点的情况，假设依赖，而依赖，那么的完整召回结果可表示为：
首先和求交，过滤掉不在中的时间线，在这步操作后，那些不活跃的seriesId将不会向后传递继续计算，因此这部分seriesId可以被安全的在中复用。上述公式进一步证明了Mex索引的正确性。举例来说，对于图9，如果我们想要从中召回token A，
需要注意，对于依赖链的初始segment，例如，。
让我们考虑更复杂的情况，假设查询召回多个segment的数据，也就是查询的时间范围和多个segment有交集。在SL索引模式下，每个segment相互独立，相同时间线的索引会在多个segment内被重复的构建，查询过程也会被重复的遍历，有很大浪费。反观我们的补集索引设计中，上一个segment的召回结果是当前segment召回结果的一部分（参看上面公式1）。
因此在每个查询session中，我们按照依赖顺序处理segment，并将上个segment得到的中间结果缓存下来用于下一个segment查询。通过这种方式，在每个segment中，我们仅需访问构建的局部索引，而无需重复遍历每个segment前序依赖的索引，从而避免了SL模式下重复索引的遍历。图11展示了中间结果复用的流程。总结来说，补集索引一方面减少了构建过程中冗余的索引构建，提升了数据实效性，另一方面也减少了查询过程中重复索引的遍历，因此有明显收益。
07
索引补全
在本节中，我们会分析索引依赖链带来的额外开销，并提出了细粒度的索引补全策略切断较长的依赖链。
7.1 依赖链开销
上面的章节我们都在讨论依赖链带来的收益，比如去除了冗余的索引构建和遍历，这些收益其实都是全局索引GL的优势。假如依赖链可无限延长，那就退化回了GL版本，又会带来之前提到的series churn负载下的读放大问题。较长的依赖链将会带来如下开销：
内存膨胀：最新的数据会被高频访问，同时希望保持极低的查询延迟，因此最近数据一般会保留在内存中，对于补集索引，这也就意味着实时segment的所有依赖数据都需要留在内存中以保证查询延迟，如果依赖链过长，这部分内存会不断膨胀。
查询递归开销：在上一节的查询流程介绍中，虽然我们减少了重复的索引访问，但是引入了额外的递归开销，也就是我们由于索引依赖访问了前序segment中不属于我们的数据。例如在图9中当我们在中召回token A对应的seriesId集合时，和无关的seriesId 5因为索引依赖也会参与倒排计算。而依赖链越长，这部分额外的递归开销越大。当依赖链无限大时，这部分递归开销就等同于GL索引对消亡线索引的遍历。
因此，我们需要在特定的时候补全segment中的索引，斩断前序依赖。
7.2 索引补全算法
在Khronos中，我们选择在dump阶段进行索引的异步补全。之所以在dump阶段处理，是基于以下原因：(a）内存segment依赖磁盘segment的索引会引入额外的I/O开销，增大查询延迟；（b）持久化的segment保持自解释的特性有助于数据的迁移的导出。
算法2介绍了我们的补全过程。我们先将series key按照metric排序。对于前缀树索引，我们按照metric粒度进行补全，当某个metric对应的数据都补全完毕，原始前缀树索引中的对应metric子树可立即释放，减少补全过程中的索引膨胀。而对于倒排索引，我们以倒排列表为粒度补全。查询会保存正在访问索引的引用，避免查询过程内存的释放。
之前我们提到在查询过程中，补集索引相比SL方案，可以减少重复的索引遍历，但同时会引入额外的递归开销。在论文中我们证明了当相邻segment间时间线的重复度超过一定阈值，补集方案的查询效率更高。具体细节感兴趣的同学可以阅读论文Section 7的部分。在Khronos的线上租户中，相邻segment的时间线重复度一般在70%-80%，去重复索引遍历的收益远高于额外的递归开销，因而补集索引查询效率更高。
08
实验总结
在实验中我们比较了SL版本和补集索引版本的写入吞吐、实效性、查询延迟和内存开销， 测试了不同写入和查询场景的收益；同时我们还和业界知名的开源数据库InfluxDB[8] 和TimeScaleDB[9] 就构建和查询性能进行测试。和开源TSDB相比，Khronos写入吞吐提升至少4倍，实效性延迟降低近百倍，查询效率提高至少6倍，证明了Khronos的高效性。
8.1 实效性延迟
SL方案是Khronos在补集索引方案上线前的原始版本，而CPL是补集索引方案上线后版本。图14展示了升级前后在segment启动期间写入吞吐（上）和实效性延迟（下）的变化。我们可以看出，在SL方案中，当segment启动时，由于索引构建压力加大，实效性延迟抖动到5min，持续了近8分钟，同时由于索引构建的开销更大，写入吞吐也有大幅下跌，见橙色线。而CPL补集索引方案中，在segment启动时，实效性延迟保持在1s以下，相比SL有大幅提升，见蓝色线。
2022年下半年补集索引优化上线后，双十一实效性延迟相比2021年有几百倍的下降（实现了分钟到秒级的突破），大幅提升用户体验。
8.2 查询效率
图15展示了不同租户ASI、HI（Hippo Docker）、IG（IGraph）、TPP在使用补集索引前后的查询延迟，查询按照时间区间分桶，注意延迟纵坐标是指数增加。图中箭头标识CPL方案相比于SL方案的延迟降低比例。表3展示了不同租户召回的时间线和点的数据规模，结合图15和表3，我们可看出当召回上千条线，百万个点的情况下，引擎依然可保证低于200ms的查询延迟。具体分析补集索引的延迟收益，我们可以对比同颜色的实线和虚线。
对于绝大部分查询，补集索引都会带来正向的延迟收益，至多19%。我们发现对于时间范围小于半个小时的查询，查询通常只访问一到两个segment，在这种情况下，补集索引减少重复索引遍历的优势很难发挥，反而由于额外的递归依赖降低了查询效率至多6%（见HI租户）。而当查询时间区间超过3个小时，大部分会访问本地磁盘或远端存储，因此补集索引的收益比例不那么明显。
引文
[01]Fabian Reinartz. 2022. Writing a Time Series Database from Scratch.
https://web.archive.org/web/20210622211933/https://fabxc.org/tsdb/
[02] Franco Solleza, AndrewCrotty, Suman Karumuri, Nesime Tatbul, and Stan Zdonik. 2022. Mach: A Pluggable Metrics Storage Engine for the Age of Observability. In Proc. CIDR.
[03] Rahul Potharaju, Terry Kim, Wentao Wu, Vidip Acharya, Steve Suh, Andrew Fogarty, Apoorve Dave, Sinduja Ramanujam, Tomas Talius, Lev Novik, and Raghu Ramakrishnan. 2020. Helios: Hyperscale Indexing for the Cloud & Edge. Proc. VLDB Endow. 13, 12 (2020), 3231–3244.
[04] Colin Adams, Luis Alonso, Benjamin Atkin, John Banning, Sumeer Bhola, Rick Buskens, Ming Chen, Xi Chen, Yoo Chung, Qin Jia, Nick Sakharov, George Talbot, Nick Taylor, and Adam Tart. 2020. Monarch: Google’s Planet-Scale In-Memory Time Series Database. Proc. VLDB Endow. 13, 12 (2020), 3181–3194.
[05] 2022. Timescale: Time-series data simplified.
[06] Zhiqi Wang and Zili Shao. 2022. TimeUnion: An Efficient Architecture with Unified Data Model for Timeseries Management Systems on Hybrid Cloud Storage. In Proc. SIGMOD. ACM, 1418–1432.
[07] 2022. Prometheus-Monitoring system & time series database.
[08] 2022. InfluxDB: Open Source Time Series Database.
[09] 2022. Timescale: Time-series data simplified.
欢迎留言一起参与讨论~
