在本节中，我们将介绍补集索引的查询流程，其中我们提出了中间结果复用的方案避免重复的索引遍历，保证准确的结果召回。在介绍补集索引查询之前，我们先了解单个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展示了中间结果复用的流程。总结来说，补集索引一方面减少了构建过程中冗余的索引构建，提升了数据实效性，另一方面也减少了查询过程中重复索引的遍历，因此有明显收益。





在本节中，我们会分析索引依赖链带来的额外开销，并提出了细粒度的索引补全策略切断较长的依赖链。

上面的章节我们都在讨论依赖链带来的收益，比如去除了冗余的索引构建和遍历，这些收益其实都是全局索引GL的优势。假如依赖链可无限延长，那就退化回了GL版本，又会带来之前提到的series churn负载下的读放大问题。较长的依赖链将会带来如下开销：

• 内存膨胀：最新的数据会被高频访问，同时希望保持极低的查询延迟，因此最近数据一般会保留在内存中，对于补集索引，这也就意味着实时segment的所有依赖数据都需要留在内存中以保证查询延迟，如果依赖链过长，这部分内存会不断膨胀。

• 查询递归开销：在上一节的查询流程介绍中，虽然我们减少了重复的索引访问，但是引入了额外的递归开销，也就是我们由于索引依赖访问了前序segment中不属于我们的数据。例如在图9中当我们在中召回token A对应的seriesId集合时，和无关的seriesId 5因为索引依赖也会参与倒排计算。而依赖链越长，这部分额外的递归开销越大。当依赖链无限大时，这部分递归开销就等同于GL索引对消亡线索引的遍历。

因此，我们需要在特定的时候补全segment中的索引，斩断前序依赖。

在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%，去重复索引遍历的收益远高于额外的递归开销，因而补集索引查询效率更高。



在实验中我们比较了SL版本和补集索引版本的写入吞吐、实效性、查询延迟和内存开销， 测试了不同写入和查询场景的收益；同时我们还和业界知名的开源数据库InfluxDB[8] 和TimeScaleDB[9] 就构建和查询性能进行测试。和开源TSDB相比，Khronos写入吞吐提升至少4倍，实效性延迟降低近百倍，查询效率提高至少6倍，证明了Khronos的高效性。



图15展示了不同租户ASI、HI（Hippo Docker）、IG（IGraph）、TPP在使用补集索引前后的查询延迟，查询按照时间区间分桶，注意延迟纵坐标是指数增加。图中箭头标识CPL方案相比于SL方案的延迟降低比例。表3展示了不同租户召回的时间线和点的数据规模，结合图15和表3，我们可看出当召回上千条线，百万个点的情况下，引擎依然可保证低于200ms的查询延迟。具体分析补集索引的延迟收益，我们可以对比同颜色的实线和虚线。

对于绝大部分查询，补集索引都会带来正向的延迟收益，至多19%。我们发现对于时间范围小于半个小时的查询，查询通常只访问一到两个segment，在这种情况下，补集索引减少重复索引遍历的优势很难发挥，反而由于额外的递归依赖降低了查询效率至多6%（见HI租户）。而当查询时间区间超过3个小时，大部分会访问本地磁盘或远端存储，因此补集索引的收益比例不那么明显。