1. 论文基本信息

1.1. 标题

Sieve: Attention-based Sampling of End-to-End Trace Data in Distributed Microservice Systems

1.2. 作者

• Zicheng Huang

• Pengfei Chen* (通讯作者)

• Guangba Yu

• Hongyang Chen

• Zibin Zheng

  机构: School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China

1.3. 发表期刊/会议

论文内容未明确指出具体的发表期刊或会议名称。但根据论文的结构、内容以及致谢部分提及的国家重点研发计划、广东省重点领域研发计划和国家自然科学基金等资助项目，推测其为一份在相关领域（如分布式系统、微服务、AIOps）有影响力的学术会议或期刊上发表的研究论文。

1.4. 发表年份

论文中未明确给出具体的发表年份。但根据致谢部分提及的资助项目（如2019YFB1804002）以及参考文献中最新的年份（例如 [16] 是 2020 年，[7]、[10]、[11]、[16]、[23]、[14]、[15] 也是 2019-2020 年），可以推断该论文的发表年份大约在 2019-2021年 之间。

1.5. 摘要

端到端追踪 (end-to-end tracing) 对于理解和监控分布式微服务系统至关重要，但巨大的追踪数据量给分析和存储带来了挑战。现有的均匀采样 (uniform sampling) 方法经常会遗漏不常见但信息量大的追踪 (uncommon yet informative traces)。为了解决这个问题，本文提出了 Sieve，一个在线采样器 (online sampler)，它利用注意力机制 (attention mechanism) 偏向采样那些在结构和时间上不常见的追踪。Sieve 将追踪编码为路径向量 (path vectors)，捕获时间和结构差异，应用鲁棒随机切分森林 (Robust Random Cut Forest, RRCF) 来检测不常见模式，并计算注意力分数 (attention scores) 以指导采样概率。在四个真实世界和实验性微服务追踪数据集上的实验评估表明，Sieve 能有效增加信息丰富的不常见追踪的选择，同时在低采样率下大幅降低存储成本。此外，Sieve 在不同程度的不常见性和参数设置下表现出鲁棒性，使其适用于大规模微服务系统。

1.6. 原文链接

/files/papers/6901a5c984ecf5fffe471754/paper.pdf (PDF文件)

2. 整体概括

2.1. 研究背景与动机

微服务架构 (microservice architecture) 将应用程序解耦为一组松散分布的细粒度服务，这些服务之间存在复杂的交互，这给微服务系统的运维带来了巨大挑战。分布式追踪 (distributed tracing) 在分析、诊断和调试微服务系统方面发挥着重要作用，它通过记录请求的执行路径来帮助理解系统行为、检测异常并定位故障根源。

然而，追踪数据 (trace data) 的庞大体量是其主要问题。例如，微信系统每天处理 $10^{10} \sim 10^{11}$ 次请求，产生数十 TB 的追踪数据。存储和分析如此巨大的数据量代价高昂，而且其中大部分数据是相似和冗余的。运维人员真正感兴趣的是那些表示系统异常或处于边缘情况的、具有高信息量的不常见追踪 (uncommon traces)。

现有的采样技术，如 Zipkin 和 Jaeger 中使用的头端采样 (head-based sampling)，在追踪开始时做出采样决策，因此无法感知后续执行路径的“有趣性”，导致随机采样可能会错过有价值的追踪。尾端采样 (tail-based sampling) 虽然在追踪结束时做出决策，可以考虑延迟或 HTTP 状态码等信息，但它主要关注单个追踪的属性，而忽略了当前追踪与之前追踪之间的差异，因此在检测不常见追踪方面仍然不足。

核心问题: 如何在海量追踪数据中，高效、准确地识别并采样那些具有高信息量、结构或时间上不常见的追踪，从而在显著降低存储和分析成本的同时，保留关键的系统洞察。

现有挑战或空白 (Gap):

• 现有采样方法难以捕获不常见且信息量大的追踪。

• 部分关注结构差异的方法（如 [3], [4]）忽略了时间差异。

• 缺乏一种能同时考虑结构和时间差异的在线采样方法。

• 在线采样对时间和空间复杂度的严格要求。

  论文的切入点/创新思路: 提出一种基于注意力机制的在线采样器 Sieve，通过偏向采样那些在结构和时间上不常见的追踪来解决上述问题。

2.2. 核心贡献/主要发现

本文的主要贡献体现在以下四个方面：

1. 引入注意力机制 (Attention Mechanism): 提出了一种关注追踪的时间 (temporal) 和结构 (structural) 差异的注意力机制，以有效捕获不常见追踪。
2. 路径向量编码方法 (Path Vector Encoding Method): 设计了一种路径向量编码方法，将追踪编码为融合了时间和结构信息的向量，便于算法处理。
3. 偏向采样方案 (Biased Sampling Scheme): 基于注意力分数 (attention score) 提出了偏向采样方案，使得不常见追踪的采样概率高，而常见追踪的采样概率极低，从而显著减少存储空间。
4. Sieve 的设计与实现 (Design and Implementation of Sieve): 设计并实现了 Sieve 作为一个低成本的在线采样器 (online sampler)，并在多个微服务系统上进行了有效性评估。

关键结论或发现:

• Sieve 能够有效识别并增加结构和时间上不常见追踪的采样概率。
• 在低采样率下，Sieve 显著降低了追踪数据的存储成本。
• Sieve 对不常见程度和参数设置（如 RRCT 的数量和大小，以及阈值 $h$）表现出良好的鲁棒性。
• Sieve 的采样开销足够低，适用于大规模微服务系统的实时在线采样场景。

3. 预备知识与相关工作

3.1. 基础概念

为了更好地理解 Sieve 的工作原理，需要首先了解以下几个基础概念：

• 微服务架构 (Microservice Architecture): 一种将单个应用程序分解为一组小型、松散耦合、可独立部署的服务的方法。每个服务运行在自己的进程中，并通过轻量级机制（通常是 HTTP API）进行通信。这种架构提高了系统的可伸缩性、弹性和开发效率，但也带来了分布式系统固有的复杂性，如服务间依赖管理和故障诊断。

• 分布式追踪 (Distributed Tracing): 一种用于监控和排查微服务架构中请求执行流程的技术。它通过在请求流经各个服务时收集数据，构建一个端到端 (end-to-end) 的请求视图。

  • 追踪 (Trace): 表示一个请求从开始到结束在分布式系统中经历的完整执行路径，通常是一个有向无环图 (DAG)。
  • 跨度 (Span): 追踪中的基本工作单元，代表了服务内或服务间的某个操作。每个 span 包含操作名称、开始时间、持续时间、标签 (tags) 和日志 (logs) 等信息，并记录了与其他 span 的因果关系（父子关系）。
  • 根跨度 (Root Span): 追踪中的第一个 span，代表了整个请求的入口点。

• 采样 (Sampling): 在大数据场景下，为了节省存储和计算资源，从大量数据中选择一部分进行处理的技术。

  • 头端采样 (Head-based Sampling): 在请求开始（即生成根 span 时）就决定是否采样整个追踪。一旦决定，这个决策会沿着请求传播到所有下游服务。缺点是无法预知追踪的后续行为，可能错过有价值的追踪。
  • 尾端采样 (Tail-based Sampling): 在请求结束（即所有 span 都生成并收集完毕）时才决定是否采样整个追踪。这允许采样器根据追踪的完整信息（如总延迟、错误状态码）做出更明智的决策，从而捕获更多信息量大的追踪。

• 隔离森林 (Isolation Forest, IF): 一种基于决策树的异常检测算法。其核心思想是异常点 (outliers) 相比于正常点 (inliers) 更容易被“隔离”出来。通过随机选择特征和切分点，构建多棵隔离树 (Isolation Tree)，异常点通常会在更浅的层级就被分到叶子节点，而正常点需要更深的层级才能被隔离。异常分数 (anomaly score) 与隔离路径的长度呈负相关。

• 鲁棒随机切分森林 (Robust Random Cut Forest, RRCF): 隔离森林的一种变体，特别适用于流数据 (streaming data) 的异常检测。它通过维护一个森林中的多棵树，并支持实时地插入新数据点和删除旧数据点，从而适应数据分布的变化。RRCF 能够处理高维数据，并且对噪声和无关特征具有鲁棒性。

• 注意力机制 (Attention Mechanism): 在机器学习和深度学习中广泛使用的一种技术，其核心思想是让模型在处理数据时，能够动态地关注输入数据中最重要的部分。例如，在自然语言处理中，一个词的表示可以根据其与句子中其他词的相关性来加权求和得到。在 Sieve 中，注意力机制体现在根据追踪的结构和时间特征，为其分配一个“注意力分数”，表示其作为不常见追踪的重要性。

3.2. 前人工作

• 分布式追踪系统:

  • Dapper [8]: Google 内部使用的分布式追踪平台，是现代分布式追踪系统的鼻祖。它提出了 trace 和 span 的概念，并实现了大规模的生产级追踪。Dapper 使用随机采样 (random sampling) 来降低存储成本，采样率通常低于 0.1%，但这导致了信息量大的追踪丢失。
  • Zipkin [1] 和 Jaeger [2]: 开源的分布式追踪系统，也遵循 Dapper 的模型，并广泛使用头端采样。
  • X-Trace [19]: 另一个追踪框架，侧重于在不同网络层追踪应用程序，以提供系统行为的全面视图。

• 采样技术:

  • 随机采样 (Random Sampling): 简单，但如 Dapper 所示，会丢失大量异常信息。
  • 基于错误采样: JCallGraph [25] 仅采样成功追踪，并保留所有失败调用追踪。虽然减少了传输带宽，但高延迟等非失败类异常追踪仍可能丢失。
  • 基于一致性采样的持续采样: Martin Bauer 等人 [26] 提出持续采样追踪，直到没有发现具有新信息的一致性追踪。
  • 基于结构差异的采样:
    • 分层聚类 (Hierarchical Clustering, HC) 方法 [3]: 尝试通过分层聚类来最大化样本中追踪的多样性，主要关注追踪的结构（例如 span 数量）。然而，它不适合在线采样，且无法检测时间上的不常见性。
    • Sifter [4]: 通过构建低维模型来近似系统的常见行为，并偏向采样那些模型捕获不佳的追踪。Sifter 也主要关注追踪的结构，因此会忽略具有不常见时间特征的追踪。
  • 错误边界分层采样 (Error-bounded stratified sampling) [27]: 数据库领域的工作，通过了解数据分布来减少样本量，与 Sieve 的目标有相似之处，但应用于不同领域。

3.3. 技术演进

分布式追踪技术从早期的 Dapper 奠定了 trace 和 span 的基础，并逐步发展出 Zipkin、Jaeger 等开源实现。随着微服务架构的普及和系统规模的不断扩大，追踪数据量呈爆炸式增长，使得传统的随机采样或简单的头端采样无法满足需求。这促使研究人员探索更智能的采样策略，以在有限的资源下捕获最具价值的异常信息。

早期的智能采样方法开始关注追踪的结构差异，试图保留更多不同执行路径的追踪。然而，仅仅关注结构是不够的，因为系统异常可能表现为结构不变但时间属性异常（如延迟增加）。这进一步推动了对结合时间和结构信息的采样方法的需求。Sieve 正是这一技术演进中的一步，它通过引入 RRCF 和注意力机制，实现了对结构和时间差异的全面考量，从而在在线、高吞吐量的微服务环境中进行高效的偏向采样。

3.4. 差异化分析

Sieve 与相关工作的主要区别和创新点在于：

• 同时关注结构和时间差异: 大多数现有工作（如 [3], [4]）仅关注追踪的结构差异。Sieve 通过其 路径向量编码器 将结构信息（路径存在与否）和时间信息（路径末端 span 的延迟）融合到一个向量中，并利用 RRCF 检测这两种类型的不常见性。
• 在线采样能力: Sieve 是一个设计的在线采样器，能够实时处理流式追踪数据。它通过 RRCF 的维护阶段，动态适应数据分布的变化，并具有恒定的时间和空间复杂度，适用于生产环境。
• 注意力机制的引入: Sieve 明确提出了“注意力机制”的概念，通过计算注意力分数来量化追踪的不常见程度，并以此指导采样概率，使得对“不常见”的偏向更为明确和可控。
• 鲁棒随机切分森林 (RRCF) 的定制化应用: Sieve 针对追踪数据的特点，改进了 RRCF，使其能够处理可变维度的路径向量，并优化了 切分维度 (cutting dimension) 的选择方法，优先考虑结构差异，从而加速不常见追踪的隔离。
• 兼顾高信息量和存储成本: Sieve 的目标是高概率采样信息量大的不常见追踪，同时以极低的概率采样冗余的常见追踪，从而在保证系统可观测性的前提下，大幅降低存储开销。

4. 方法论

本节将详细描述 Sieve 的设计，包括其如何编码追踪、如何评估其不常见性以及如何根据评估结果进行偏向采样。Sieve 的核心目标是保留那些对调试或诊断有用的追踪，并丢弃冗余的追踪。在微服务系统中，大多数追踪是相似的，而罕见的执行（不常见追踪）是少数，S但却更值得关注。Sieve 利用基于隔离的方法来发现这些罕见的执行。

4.1. 方法原理

Sieve 的设计理念是利用基于隔离 (isolation-based) 的方法来发现不常见的执行。它通过以下三个主要组件实现这一目标：

1. 路径向量编码器 (Path Vector Encoder): 将原始的追踪数据（半结构化文本）转换为算法可处理的数值型路径向量 (path vectors)。这个向量融合了追踪的结构信息和时间信息。

2. 自适应评分器 (Adaptive Scorer): 接收路径向量，并利用鲁棒随机切分森林 (Robust Random Cut Forest, RRCF) 检测其不常见模式，计算出一个注意力分数 (attention score)，该分数反映了追踪的不常见程度。

3. 偏向采样器 (Biased Sampler): 根据当前追踪的注意力分数和历史追踪的分数，计算出采样概率，并决定是存储该追踪还是丢弃它。

   Sieve 的采样工作流程如下图所示（原文 Figure 2）：

   图注：Sieve 采样工作流概览。传入的追踪首先由 路径向量编码器 转换为 路径向量。路径向量 随后被送入 自适应评分器，该评分器使用 RRCF 生成 注意力分数。注意力分数 进一步传递给 偏向采样器，偏向采样器 根据分数和设定的阈值，决定是否 采样 或 丢弃 追踪。被 采样 的追踪会被持久化存储。

4.2. 路径向量编码器 (Path Vector Encoder)

追踪 (trace) 记录了一个请求的执行路径。它是一个有向无环图 (DAG)，由多个 span 组成，其中第一个 span 是 根跨度 (root span)。Sieve 从 根跨度 开始，遍历追踪中的所有 span，识别出所有从 根跨度 到任意 span 的唯一路径 (path)。

例如，如果有一个路径 $A \to B \to C$，其中 $A$ 是 根跨度，那么这条路径会被提取出来。对于每条路径 $p$，Sieve 会记录该路径末端 span 的 延迟 (latency) $l_t$。

通过这种方式，Sieve 为每个追踪构建了一个 路径集合 (path set) $P$ 和对应的 延迟集合 (latency set) $L$。然后，Sieve 将这些信息编码成一个 路径向量 $\mathbf{x} = (x_1, ..., x_n)$。

• 向量维度: 路径向量的每个索引 $i$ 都与一个唯一的路径 $p_i$ 相关联。
• 向量值: 如果追踪包含路径 $p_i$，则 $x_i$ 的值被设置为该路径末端 span 的 延迟 $l_i$。
  • 如果一个追踪包含多条相同的路径（例如，在一个循环调用或重试场景中），则选择这些路径中的最大 延迟 值进行编码，以反映最耗时的执行情况。
• 缺失路径: 如果一个追踪不包含路径 $p_i$，那么 $x_i$ 被赋值为 -1，表示这是一个无效索引。

融合结构与时间信息: 这种编码方式巧妙地将结构信息和时间信息融合到单个向量中：

• 结构信息: 路径向量中有效索引（非 -1）的位置反映了追踪的执行路径结构。

• 时间信息: 有效索引上的值（延迟）反映了执行的时间特性。

  当比较两个结构不同的追踪时，它们路径向量中无效索引的位置会有所不同，从而使其可区分。当比较两个结构相同但延迟不同的追踪时，它们路径向量中有效索引上的值会有所不同，同样使其可区分。

特征扩展: Sieve 还可以扩展 路径向量 以包含更多有意义的特征，例如 span 的数量、请求状态码 (request status code) 等，只需将这些特征简单地拼接 (concatenate) 到 路径向量 的末尾，以构建更具信息量的追踪编码，这有助于后续的隔离过程。

以下是路径向量编码的示例（原文 Figure 3）：

图注：两个追踪的路径向量编码示例。Sieve 提取所有从根跨度开始的路径。在路径向量中，每个索引关联一条路径，索引中的值是关联路径的尾跨度延迟。如果追踪不包含某条路径，则对应索引的值设为 -1。如果追踪中存在多条相同路径，则选择这些路径中的最大延迟进行编码。

4.3. 自适应评分器 (Adaptive Scorer)

由于追踪已被编码为 路径向量，因此发现不常见追踪的问题就转化为发现不常见 路径向量 的问题。不常见性意味着与大多数数据的偏差。Sieve 利用 RRCF 来实现这种隔离，并根据隔离结果计算 注意力分数。

4.3.1. 隔离 (Isolation)

RRCF 是一种适用于流数据异常检测的算法，Sieve 利用其能力来发现不常见追踪。Sieve 构建一个增强的 RRCF 模型来计算追踪的 注意力分数。原始的 RRCF 模型只能处理固定维度的数据，而 路径向量 的维度会随着新路径的出现而变化。Sieve 的创新之一是使 RRCF 适应这种维度变化。

RRCF 由多个 鲁棒随机切分树 (Robust Random Cut Tree, RRCT) 组成，每棵树都是从头开始构建，并最终增长到固定大小。一个 RRCT 的生命周期分为两个阶段：构建阶段 (construction stage) 和 维护阶段 (maintenance stage)。

以下是构建阶段和维护阶段的工作流程图（原文 Figure 4）：

图注：构建阶段（左）和维护阶段（右）的工作流程。$X$ 是路径向量集合，XL 和 XR 是 $X$ 的子集。PV 是路径向量。

构建阶段 (Construction Stage): 假设每棵 RRCT 的最终大小为 $m$，路径向量 的维度为 $n$。Sieve 使用 $m$ 个路径向量来构建 RRCT。这 $m$ 个路径向量形成一个集合 $X = \{ \mathbf{x}_i = (x_{i1}, ..., x_{in}) | \mathbf{x}_i \in X, 1 \leq i \leq m \}$。每棵 RRCT 通过递归地切分 $X$ 来构建。

1. 选择切分维度 (Cutting Dimension): 从 RRCT 的根节点开始，Sieve 选择一个最有可能隔离不常见追踪的切分维度 $j (1 \leq j \leq n)$。这是对原始 RRCF 模型的改进。

   • 结构区分优先: Sieve 优先考虑结构区分。如果存在某个维度 $j$ 对某些路径向量而言是 无效维度（即 $x_{ij} = -1$），则 Sieve 会选择一个 无效维度 作为 切分维度。
   • 维度权重 (Dimension Weight): 如果不存在 无效维度，Sieve 则根据 维度权重 来选择 切分维度。维度 $j$ 的权重 $w_j$ 的计算方式如下： $$w _ { j } = \frac { \underset { 1 \leq i \leq m } { m a x } \ x _ { i j } - \underset { 1 \leq i \leq m } { m i n } \ x _ { i j } } { \underset { j = 1 } { \sum } \ \underset { 1 \leq i \leq m } { m a x } \ x _ { i j } - \underset { 1 \leq i \leq m } { m i n } \ x _ { i j } }$$
     • 符号解释:
       • $w_j$: 维度 $j$ 的权重。
       • $\underset{1 \leq i \leq m}{\mathrm{max}} \ x_{ij}$: 在集合 $X$ 中，所有路径向量在维度 $j$ 上的最大值。
       • $\underset{1 \leq i \leq m}{\mathrm{min}} \ x_{ij}$: 在集合 $X$ 中，所有路径向量在维度 $j$ 上的最小值。
       • $\sum_{j=1} \dots$: 分母表示所有维度上 (最大值 - 最小值) 的总和。
     • 目的分析: 这个公式计算了维度 $j$ 上数值范围占所有维度数值范围总和的比例。因此，数值差异最大的维度（即最有区分度的维度）被选中的概率最高。

2. 选择切分值 (Cutting Value):

   • 如果 切分维度 $j$ 对某些路径向量是 无效索引，则 切分值 $q_j$ 总是设为 -0.5。这个值将把所有包含该无效维度（值为 -1）的路径向量与不包含该维度的路径向量隔离开。
   • 否则，切分值 $q_j$ 会在选定维度 $j$ 的最大值和最小值之间随机选择。

3. 递归切分:

   • 将集合 $X$ 分为两个子集：

     • $XL = \{ \mathbf{x}_i = (x_{i1}, ..., x_{in}) | \mathbf{x}_i \in X, x_{ij} \leq q_j \}$：在维度 $j$ 上的值小于或等于 $q_j$ 的路径向量被分配到左子节点。
     • $XR = X \setminus XL$：其余在维度 $j$ 上的值大于 $q_j$ 的路径向量被分配到右子节点。

   • Sieve 递归地对左子节点和右子节点进行上述切分，直到每个叶子节点只包含一个 路径向量。

     以下是一个 RRCT 构建过程的示意图（原文 Figure 5）：

     图注：一个 RRCT 构建过程的图示。不同颜色的块代表不同的跨度，块内的数字代表延迟。第三个路径向量的维度 3（用 $\bullet$ 表示）是无效索引，因此维度 3 被优先选为切分维度。第一个和第二个路径向量在 RRCT 根的右子节点上再次被切分。维度 $\otimes$ 被选中，因为它与其他维度有很大差异。边界框记录了每个维度上值的上限和下限。

     维护阶段 (Maintenance Stage): 在构建阶段结束后，RRCT 进入维护阶段。当一个新的 路径向量 到来时，会执行以下操作以保持 RRCT 的固定大小 $m$：

4. 移除最旧的叶子 (Remove Oldest Leaf): 移除包含最早生成的 路径向量 的叶子节点。

   • 除了 切分维度 和 切分值，RRCT 的每个内部节点还维护一个其叶子节点的 边界框 (bounding box)，记录了每个维度上值的上限和下限。

   • 当最旧的叶子被移除后，RRCT 会进行调整：移除叶子的父节点会被其兄弟节点替代，并且更新其兄弟节点上方内部节点的 边界框。

   • 以下是移除最旧叶子的示例（原文 Figure 6）：

     图注：移除最旧叶子的示意图。当最旧的叶子（右下角）被移除时，它的父节点被其兄弟节点替代，并更新了父节点上方内部节点的边界框。

5. 插入新的路径向量 (Insert New Path Vector):

   • 处理新维度: 如果新的 路径向量 包含以前从未出现过的新维度 (new dimensions)，插入过程分为三步：

     1. Sieve 扩展树中已有的 路径向量，在新维度上追加 -1。
     2. Sieve 以相同方式扩展 边界框。
     3. Sieve 生成一个新的根节点：将其 切分维度 设为其中一个新维度，切分值 设为 -0.5，其左子节点设为旧根节点，右子节点设为新的 路径向量，并设置新根节点的 边界框。

     • 以下是插入带有新维度的路径向量的示例（原文 Figure 7）：

       图注：插入带有新维度的路径向量的示意图。当新的路径向量（PV）引入了新维度时，树中所有现有路径向量（例如 X1, X2）都通过追加 -1 进行扩展，边界框也随之扩展。然后创建一个新的根节点，其切分维度设置为新维度，切分值设置为 -0.5，旧树成为其左子树，新 PV 成为其右子树。

   • 处理无新维度: 如果新的 路径向量 没有引入新维度，Sieve 使用 RRCT 的原始方法进行插入 [5]。

     通过移除最旧的叶子和插入新的 路径向量，每棵 RRCT 的大小在维护阶段保持恒定。这使得 Sieve 能够在一个包含最新 $m$ 个 路径向量 分布的上下文中评估 路径向量，从而适应追踪数据流的变化。

4.3.2. 注意力分数 (Attention Score)

RRCT 构建完成后，不常见的 路径向量 将在树中处于更浅的层级（从根到叶子的路径更短）。RRCT 根据 路径向量 在树中的深度为其分配 注意力分数。

给定 深度 $\mathit{depth}(l, t)$ 表示叶子 $l$ 在树 $t$ 中的深度，路径向量 $\mathbf{x}_i$ 在树 $t_j$ 的叶子 $l'$ 中的 注意力分数 $s_i$ 计算如下： $$s _ { i } = \frac { m a x _ { \mathit { \theta } } d e p t h ( l , t _ { i } ) } { d e p t h ( l ^ { \prime } , t _ { j } ) }$$

• 符号解释:

  • $s_i$: 路径向量 $\mathbf{x}_i$ 在树 $t_j$ 中获得的注意力分数。
  • $\mathit{max}_{\mathit{\theta}} \mathit{depth}(l, t_i)$: 树 $t_i$ 中所有叶子的最大深度。这里原文的 $t_i$ 应该是指当前树 $t_j$，即当前树的最大深度。
  • $\mathit{depth}(l', t_j)$: 路径向量 $\mathbf{x}_i$ 所属的叶子 $l'$ 在树 $t_j$ 中的深度。

• 目的分析: 根据这个公式，如果一个 路径向量 位于较浅的层级（即 $depth(l', t_j)$ 较小），则其 注意力分数 $s_i$ 会较高。这与隔离森林的原理一致：异常点更容易被隔离，因此路径更短，分数更高。

  一个 RRCF 包含 $k$ 棵 RRCT。当一个 路径向量 从大多数树中获得高分时，它很可能是一个不常见追踪。最终分配给 路径向量 的分数是通过对所有 RRCT 给出的分数求平均得到的： $$s = \frac { s _ { 1 } + \ldots + s _ { k } } { k }$$

• 符号解释:

  • $s$: 路径向量的最终注意力分数。
  • $s_j$: 第 $j$ 棵 RRCT 为该路径向量计算的注意力分数。
  • $k$: RRCF 中 RRCT 的总数量。

• 目的分析: 通过对多棵树的分数取平均，可以减少单棵树随机性带来的偏差，提高分数的鲁棒性。

4.3.3. 维度降低 (Dimension Reduction)

Sieve 旨在适应具有以前从未存在过的执行路径的新追踪，这通过 路径向量扩展机制 实现。然而，这种机制的一个副作用是 路径向量 的维度会持续增长，导致 维度灾难 (curse of dimensionality)，严重影响 Sieve 的在线采样能力。因此，维度降低 技术是必要的。

维度灾难 的原因是 Sieve 记录了它迄今为止看到的所有执行路径，而 RRCT 仅保留了最近追踪的 路径向量。在 RRCT 中，有很多维度对所有 路径向量 都是无效的。

以下是无效维度和弱维度的数量图（原文 Figure 8）：

图注：无效维度和弱维度的数量。不同的线条代表不同的 RRCT 大小。X 轴表示 Sieve 处理的追踪数量。

Sieve 采用了以下两种方法进行维度降低：

1. 移除无效维度: Sieve 可以安全地移除那些对 RRCT 中所有 路径向量 都无效的维度（即在这些维度上所有路径向量的值都是 -1）。这些维度对切分过程没有影响，因为它们永远不会被选为 切分维度。

2. 移除弱维度 (Weak Dimensions): Sieve 采用更积极的方法来移除满足以下两个标准的维度：

   • 该维度不是当前的 切分维度。

   • 该维度中值的方差 (variance) 低于 0.1。

   • 目的分析: 满足这些标准的维度很少有机会被选为 切分维度，因为它们对数据点区分的贡献很小。Sieve 将它们称为 弱维度。

     与完全移除 无效维度 不同，Sieve 暂时移除 弱维度，并持续监控这些 弱维度 中值的方差。当某个 弱维度 的方差再次大于 0.1 时，它会变回 正常维度，RRCT 中的所有 路径向量 都会随之扩展，重新包含该维度。

4.4. 偏向采样器 (Biased Sampler)

Sieve 根据其 注意力分数 和之前追踪的分数来计算追踪的 采样概率。Sieve 维护一个包含 $k$ 个最近分数和当前分数在内的 滑动窗口 (sliding window)。

在 滑动窗口 中，Sieve 计算过去 $k$ 个分数的方差 $var_k$ 和 $k+1$ 个分数的方差 $var_{k+1}$。$var_{k+1}$ 和 $var_k$ 之间的差异表示当前分数 $s_{k+1}$ 与过去 $k$ 个分数分布的偏差程度。

• 高偏差情况: 如果差异程度超过预设阈值 $h$（即 $var_{k+1} - var_k > h$），Sieve 会采用 Sigmoid 函数 (sigmoid function) 大幅提高当前追踪的 采样概率，使其趋近于 1。 $$f ( s _ { k + 1 } ) = \frac { 1 } { 1 + e ^ { 2 \overline { { W } } - s _ { k + 1 } } }$$

  • 符号解释:
    • $f(s_{k+1})$: 当前追踪的采样概率。
    • $s_{k+1}$: 当前追踪的注意力分数。
    • $\overline{W}$: 滑动窗口 $W = [s_1, ..., s_{k+1}]$ 中所有分数的平均值。
    • $e$: 自然对数的底数。
  • 目的分析: 当当前分数 $s_{k+1}$ 显著高于窗口平均值 $\overline{W}$ 时（表明当前追踪非常不常见），分母 $1 + e^{2\overline{W} - s_{k+1}}$ 将趋近于 1，从而使采样概率 $f(s_{k+1})$ 趋近于 1。这确保了高度不常见的追踪几乎总是被采样。

• 低偏差情况: 如果差异程度未超过阈值 $h$（即 $var_{k+1} - var_k \leq h$），Sieve 会按比例计算当前追踪的 采样概率。 $$f ( s _ { k + 1 } ) = \frac { s _ { k + 1 } } { \sum _ { i = 1 } ^ { k + 1 } s _ { i } }$$

  • 符号解释:

    • $f(s_{k+1})$: 当前追踪的采样概率。
    • $s_{k+1}$: 当前追踪的注意力分数。
    • $\sum_{i=1}^{k+1} s_i$: 滑动窗口 $W$ 中所有分数的总和。

  • 目的分析: 在这种情况下，采样概率与当前追踪的注意力分数成正比，即分数越高，采样概率越大，但不会强制接近 1，从而允许更多常见但仍略有信息量的追踪以较低概率被采样。

    最后，在得到 采样概率 $f(s_{k+1})$ 后，Sieve 生成一个介于 [0, 1] 之间的随机数，如果 采样概率 不小于该随机数，则采样该追踪，否则丢弃。

4.5. 在线采样 (Online Sampling)

Sieve 是一个实时在线采样器，旨在为不常见追踪实现高采样概率。当流式追踪数据到来时，Sieve 会首先收集足够的追踪，将其编码为 路径向量，并构建 RRCF。之后，Sieve 进入 维护阶段。随着更多追踪的到来，在插入新追踪之前，最旧的追踪会被移除。

对于插入到树中的每个追踪，都会由 RRCF 的所有 RRCT 评估其 注意力分数。然后，使用公式 (4) 计算 采样概率。最后，Sieve 根据计算出的 采样概率 决定是否采样该追踪。

以下是 Sieve 在维护阶段的在线采样算法流程 (Algorithm 1):

# Algorithm 1 Online Sampling Algorithm

Input: The trace $t$; the RRCF rrcf; the sliding window `sw` of the previous $k$ scores; the threshold $h$.
Output: The sampling decision decision; the updated sliding window `sw`; the updated RRCF rrcf.

1: $x \leftarrow \mathrm{encode}(t)$  // 将追踪 $t$ 编码为路径向量 $x$
2: $scores \leftarrow []$      // 初始化用于存储各 RRCT 分数的列表
3: for all $rrct \in rrcf$ do   // 遍历 RRCF 中的每棵 RRCT
4:     $rrct.\mathrm{remove\_oldest()}$ // 移除当前 RRCT 中最旧的路径向量
5:     $rrct.\mathrm{insert}(x)$     // 插入新的路径向量 $x$
6:     $s \leftarrow rrct.\mathrm{score}(x)$ // 计算当前路径向量 $x$ 在此 RRCT 中的注意力分数
7:     $scores.\mathrm{append}(s)$   // 将分数添加到列表中
8: $avg \leftarrow \mathrm{average}(scores)$ // 计算所有 RRCT 分数的平均值
9: $sw.\mathrm{append}(avg)$        // 将平均分数添加到滑动窗口中

10: if $\mathrm{variance}(sw) - \mathrm{variance}(sw[1:k]) > h$ then // 如果当前分数导致方差显著增加（超过阈值 h）
11:     $p \leftarrow \frac { 1 } { 1 + e ^ { 2 \ast \mathrm{average}(sw) - avg } }$ // 使用 Sigmoid 函数计算采样概率
12: else // 否则
13:     $p \leftarrow \frac { avg } { \sum _ { i = 1 } ^ { k + 1 } sw [ i ] }$ // 使用比例函数计算采样概率

14: $sw.\mathrm{remove}(sw[0])$ // 移除滑动窗口中最旧的分数
15: if $\mathrm{random}(0, 1) < p$ then // 如果随机数小于采样概率
16:     $decision \leftarrow \mathrm{True}$ // 决定采样
17: else
18:     $decision \leftarrow \mathrm{False}$ // 决定丢弃
19: return `decision, sw, rrcf` // 返回采样决策、更新后的滑动窗口和 RRCF

4.6. 实现 (Implementation)

Sieve 使用 Python 实现，基于一个开源的 RRCF 实现进行了修改。主要的改进包括：

• 切分维度选择: 改进了 切分维度 的选择方法，优先考虑 无效维度 和 新维度，从而加速了结构不常见性的隔离。
• 评分方案: 替换了原始的评分方案，使用了本文介绍的、基于深度的 注意力分数 计算方式。
• 路径向量扩展: 增强了 RRCF 模型，使其能够通过 路径向量扩展机制 处理不定长（可变维度）的向量。
• 维度降低: 实现了通过移除 无效维度 和 弱维度 的 维度降低 方案，以解决 维度灾难 问题。

5. 实验设置

本节详细描述了 Sieve 的实验设置，包括所使用的数据集、评估指标、对比基线以及参数配置。

5.1. 数据集

实验使用了四个不同的微服务追踪数据集，以全面评估 Sieve 的有效性。

1. VWR (Virtual War Room):

   • 来源: 一个模拟的微服务系统，由 Virtual War Room (VWR) [16] 生成。
   • 特点: 包含 6 个微服务，并注入了两种类型的故障：网络延迟 (network delay) 和提前停止 (early stop)。追踪数据使用 OpenTracing 收集。
   • 规模: 总计 34167 条追踪，其中 32592 条是正常追踪，66 条具有高网络延迟，1509 条具有提前停止故障。
   • 代表性: 用于模拟在受控环境中注入特定故障时的系统行为。

2. AIOps:

   • 来源: 真实世界微服务应用生成的数据集，部署在某 ISP 的私有云环境中，并用于一次国际 AIOps 挑战赛。
   • 特点: 包含 13 个微服务，部分服务具有多个实例。为了制造多样化的异常，向不同实例注入了不同类型的故障。
   • 规模: 包含 164340 条正常追踪和 4092 条异常追踪。
   • 代表性: 反映了真实生产环境中微服务系统的复杂性和异常的多样性。

3. Boutique (Online Boutique):

   • 来源: Google 的 Online Boutique 微服务演示应用程序，一个由 10 层微服务组成的系统。
   • 特点: 使用 OpenCensus 对应用程序进行了检测，并部署在有 8 个节点的 Kubernetes 集群上。模拟工作负载以生成追踪，并注入了两种类型的故障：一个故障导致电子邮件微服务响应延迟，另一个故障导致产品目录微服务崩溃。
   • 规模: 收集了 2000 条追踪，其中 99 条是异常追踪。
   • 代表性: 一个标准化的微服务基准测试应用，便于复现和比较。

4. TC (Telecommunication):

   • 来源: 来自一家大型电信企业的真实生产追踪数据。
   • 特点: 包含 6561 条追踪，可分为 10 种不同的 API 类型。最长的追踪包含 451 个 span。
   • 代表性: 反映了大型企业级生产系统的复杂追踪模式和数据量。

不同数据集的延迟设置 (Table I) 和追踪结构设置 (Table II):

以下是原文 Table I 所示的不同数据集的延迟设置：

TABLE I Latency SeTting

以下是原文 Table II 所示的不同数据集的追踪结构设置：

TABLE II Trace Structure Setting

5.2. 评估指标

论文使用了以下指标来评估 Sieve 的性能和有效性：

1. 采样率 (Sampling Rate):

   • 概念定义: 指被 Sieve 采样（保留）的追踪数量占总追踪数量的比例。这是一个衡量存储成本节省程度的关键指标，采样率越低，存储节省越多。
   • 数学公式: 论文未直接给出公式，但其含义明确。 $$\text{采样率} = \frac{\text{采样到的追踪数量}}{\text{总追踪数量}}$$
   • 符号解释:
     • $\text{采样到的追踪数量}$: 经过 Sieve 处理后，被决定保留的追踪总数。
     • $\text{总追踪数量}$: 原始数据集中的追踪总数。

2. 不常见追踪比例 (Proportion of Uncommon Traces):

   • 概念定义: 在采样的追踪集合中，不常见追踪的数量占采样总数或原始不常见追踪总数的比例。这衡量了采样方法在保留信息量大的不常见追踪方面的有效性。
   • 数学公式: 论文中在性能对比部分（Section V.C）使用“采样的不常见追踪占样本的比例”来衡量采样质量，公式可表示为： $$\text{不常见追踪比例} = \frac{\text{采样到的不常见追踪数量}}{\text{采样到的总追踪数量}}$$
   • 符号解释:
     • $\text{采样到的不常见追踪数量}$: Sieve 成功采样到的不常见追踪的数量。
     • $\text{采样到的总追踪数量}$: Sieve 决定保留的所有追踪（包括不常见和常见）的总数。

3. 真阳性 (True Positive, TP):

   • 概念定义: 指一个实际为不常见追踪，并且 Sieve 成功识别并决定采样的追踪。在论文的敏感性分析中，具体定义为：不常见追踪的注意力分数导致方差差异超过阈值 $h$ 的情况。
   • 数学公式: 无直接公式，是计数性质的指标。
   • 符号解释: 在实验中，是指那些被人工标记为不常见，且被 Sieve 的偏向采样器因方差差异超过阈值 $h$ 而判断为“有趣”并可能被采样的追踪。

4. 假阳性 (False Positive, FP):

   • 概念定义: 指一个实际为常见追踪，但 Sieve 错误地识别并决定采样的追踪。在论文的敏感性分析中，具体定义为：常见追踪的注意力分数导致方差差异超过阈值 $h$ 的情况。
   • 数学公式: 无直接公式，是计数性质的指标。
   • 符号解释: 在实验中，是指那些被人工标记为常见，但被 Sieve 的偏向采样器因方差差异超过阈值 $h$ 而错误地判断为“有趣”并可能被采样的追踪。

5. 采样延迟 (Sampling Latency):

   • 概念定义: 指 Sieve 处理一个追踪并做出采样决策所需的时间。这是一个衡量 Sieve 在线处理效率和开销的指标。
   • 数学公式: 无直接公式，通常以毫秒 (ms) 为单位测量。
   • 符号解释: 通常指从追踪数据输入到 Sieve 到输出采样决策的平均或累积分布时间。

5.3. 对比基线

Sieve 的采样结果与以下两种方法进行了比较：

1. 随机采样 (Random Sampling):
   • 代表性: 最简单、最常见的采样方法，作为衡量其他采样方法效果的基础基线。它不考虑追踪的任何特性，只按固定概率随机选择追踪。
2. 分层聚类 (Hierarchical Clustering, HC) 方法 [3]:
   • 代表性: 一种旨在偏向采样以最大化追踪多样性的方法，主要关注追踪的结构（例如 span 数量）。它能够检测结构上的不常见性。
   • 局限性: 论文指出 HC 不适合在线采样，且无法检测时间上的不常见性。将其作为基线，可以突出 Sieve 在处理时间差异和在线能力上的优势。

5.4. 参数设置

在实验中，Sieve 默认的参数设置如下：

• RRCT 数量 (Number of RRCTs): 50

• RRCT 大小 (Size of RRCT): 128

• 滑动窗口长度 (Length of Sliding Window): 50

• 阈值 (Threshold $h$): 0.3

  这些参数可以根据不同的系统进行调整，但在敏感性分析中会单独探讨它们的影响。

6. 实验结果与分析

本节详细分析 Sieve 在四个追踪数据集上的实验结果，展示了其偏向采样能力、对不常见程度和参数的敏感性、与基线方法的性能比较、代表性采样能力以及开销。

6.1. 偏向采样 (Biased Sampling)

6.1.1. 时序注意力 (Temporal Attention)

本实验旨在评估 Sieve 识别和偏向采样具有时间异常的追踪的能力。实验中使用了 1000 条追踪，其中 990 条是正常延迟范围内的追踪，10 条是延迟偏离正常分布的追踪。所有这 1000 条追踪的结构（span 数量、因果关系）是相同的，以避免结构差异的干扰。具体的数据集延迟设置如 Table I 所示。

以下是四个数据集中，Sieve 在时序注意力方面的得分和采样概率图（原文 Figure 9）：

图注：四个微服务系统（VWR、AIOps、Boutique、TC）追踪数据中得分与采样概率关系的图表。图中上半部分为分数趋势，下半部分展示对应采样概率，红圈标记了采样点，反映了不同系统中采样方法对重要追踪的选择效果。

分析:

• VWR (Figure 9a): 不常见追踪（延迟异常）获得了更高的注意力分数，因为它们更容易被隔离到树的较浅层。不常见追踪的平均采样概率高达 0.990，而常见追踪的平均采样概率仅为 0.018。这种显著差异归因于 Sieve 在方差差异超过阈值时采用 Sigmoid 函数使采样概率快速趋近于 1 的策略。对于大多数常见追踪，采样概率是线性计算的，并在滑动窗口长度为 50 时，其采样概率围绕 0.02 波动。

• AIOps (Figure 9b): 少数不常见追踪的注意力分数显著高于多数常见追踪。不常见追踪的平均采样概率为 0.999，常见追踪为 0.019。图中有一个常见追踪的采样概率接近 1，这被认为是假阳性 (false positive)，可能是由于阈值设置不理想（0.3）导致。但论文指出，这种次优阈值只会增加少量样本，对整体采样结果影响不大。

• Boutique (Figure 9c) 和 TC (Figure 9d): 类似地，这两个数据集的结果也表明 Sieve 能够检测到所有不常见追踪并大幅提高其采样概率。即使在 TC 数据集中，常见和不常见追踪的延迟范围差异较小（22~30ms vs 50~66ms），Sieve 也能有效区分它们。

  结论: Sieve 在时序注意力方面表现出色，能够精准识别出具有异常延迟的追踪，并为其分配高采样概率，有效偏向采样信息量大的时序不常见追踪。

6.1.2. 结构注意力 (Structural Attention)

本实验旨在评估 Sieve 识别和偏向采样具有结构异常的追踪的能力。实验中使用了 1000 条追踪，其中 990 条是结构常见追踪，10 条是结构不常见追踪。为了避免时间差异的干扰，所有追踪的延迟被限制在特定范围内。具体的数据集结构设置如 Table II 所示。

以下是四个数据集中，Sieve 在结构注意力方面的得分和采样概率图（原文 Figure 10）：

分析:

• VWR (Figure 10a): 常见追踪的采样概率远低于不常见追踪。前者的平均采样概率为 0.020，后者为 0.996。图中出现两个假阳性，经过检查，这两个假阳性追踪的延迟极低（低于 10ms），偏离了整体延迟分布，因此 Sieve 将它们视为不常见追踪并赋予高注意力分数。

• AIOps (Figure 10b): 由于延迟范围较小（400~450ms），未出现假阳性。常见追踪的平均采样概率为 0.018，不常见追踪为 0.997。

• Boutique (Figure 10c): 所有不常见追踪都被 Sieve 检测到并以高概率采样。常见和不常见追踪的平均采样概率分别为 0.018 和 0.997。

• TC (Figure 10d): 实验中，990 条具有 15 个 span 的追踪被视为常见，10 条具有 14 个 span 的追踪被视为不常见。两者结构上仅相差一个 span。尽管结构差异微妙，Sieve 仍然检测到了所有不常见追踪。

  结论: Sieve 在结构注意力方面同样有效，能够识别出结构不常见追踪并赋予高采样概率。即使是微小的结构差异，Sieve 也能敏感地捕获。

6.2. 敏感性 (Sensitivity)

本节评估 Sieve 对不常见程度以及 RRCT 的数量、大小和阈值等参数的敏感性。主要关注时序不常见性，因为它通常比结构不常见性更具挑战性。

定义:

• 真阳性 (True Positive, TP): 不常见追踪的注意力分数使方差差异超过阈值 $h$。
• 假阳性 (False Positive, FP): 常见追踪的注意力分数使方差差异超过阈值 $h$。

6.2.1. 对不常见程度的敏感性

实验使用 AIOps 数据集中的 1000 条追踪。其中 990 条常见追踪的延迟低于 200ms，10 条不常见追踪的延迟高于 200ms。通过改变这 10 条不常见追踪的延迟范围来模拟不同程度的不常见性。

以下是 Sieve 对不常见程度的敏感性图（原文 Figure 11）：

分析:

• Sieve 在大多数场景下都检测出了所有 10 条不常见追踪。

• 在不常见追踪延迟范围为 200~250ms 时，Sieve 的表现略差，因为常见追踪的延迟低于 200ms，导致常见与不常见之间的界限模糊。

• 随着不常见程度的增加（延迟范围拉大，即不常见追踪与常见追踪的差异更明显），Sieve 的检测能力迅速提高，并且 假阳性 (FP) 率保持在较低水平。

  结论: Sieve 对不常见程度具有鲁棒性。当不常见性更明显时，其检测效果更佳，并且能保持较低的误报率。

6.2.2. 对参数的敏感性

实验使用 AIOps 数据集中的 1000 条追踪，其组成如 Table III 所示：

TABLE III TRace COMpositIon

这 1000 条追踪中包含 990 条常见追踪，以及 5 条时序不常见追踪（延迟 > 400ms）、2 条结构不常见追踪（59 个 span）和 3 条结构不常见追踪（7 个 span）。

以下是 Sieve 对其参数（RRCT 大小、RRCT 数量、阈值）敏感性的图（原文 Figure 12）：

分析:

• RRCT 大小 (Figure 12a): RRCT 大小设置为 32, 64, 128, 256, 512 时，Sieve 的准确性几乎不受影响。这表明 Sieve 在不同 RRCT 大小配置下性能稳定。
• RRCT 数量 (Figure 12b): RRCT 数量设置为 10, 30, 50, 70, 90 时，Sieve 的准确性也几乎不受影响。这表明 Sieve 在不同 RRCT 数量配置下性能稳定。
• 阈值 (Threshold $h$) (Figure 12c): 阈值 $h$ 对 Sieve 的准确性有直接影响。

  • 当阈值低于 0.55 时，假阳性 (FP) 数量显著减少，而 真阳性 (TP) 数量保持最大。

  • 当阈值介于 0.6 和 0.85 之间时，真阳性 (TP) 数量保持稳定，略有下降，而 假阳性 (FP) 数量减少到 0。

  • 当阈值高于 1 时，真阳性 (TP) 数量下降到 7 并保持稳定。

    结论: Sieve 对 RRCT 的大小和数量不敏感，在不同配置下性能稳定。阈值对其准确性有直接影响，但 Sieve 在有限的阈值范围内不敏感。建议设置一个较低的阈值，可以在少量 假阳性 的情况下获得较高的 真阳性 覆盖率。

6.3. 性能对比 (Performance Comparison)

为了评估 Sieve 的采样质量，将其结果与 随机采样 (Random) 和 分层聚类 (Hierarchical Clustering, HC) 方法 [3] 进行比较。实验设定了采样预算 (sampling budget)，即样本大小，并计算样本中不常见追踪的比例。实验重复 50 次取平均值。不同数据集的 1000 条追踪组成如 Table IV 所示：

TABLE IV Trace Composition Of Different Dataset

以下是三种方法在不同追踪数据集上采样的不常见追踪比例图（原文 Figure 13）：

分析:

• 整体表现: Sieve 在所有四个数据集上都实现了最佳性能，采样的不常见追踪比例显著高于 随机采样 和 HC。
• 随机采样 (Random Sampling): 其不常见追踪比例大致等于采样率，表现最差。
• 分层聚类 (HC): 性能优于 随机采样，但其比例增长缓慢，并且未能超过 60%。这是因为 HC 只能检测结构上的不常见性，因此只能采样 5 条结构不常见追踪，而忽略了另外 5 条时序不常见追踪。
• Sieve:

  • 在采样预算开始时，Sieve 的比例可能低于 HC，因为其在线采样机制。如果信息量大的不常见追踪没有在早期出现，Sieve 可能会在常见追踪上消耗一部分预算。

  • 随着预算的增加，Sieve 采样的不常见追踪比例迅速增长，并最终趋近于 100%。

  • 在 TC 数据集上，Sieve 的表现尤其突出，因为 HC 的效果大幅下降（可能因为 TC 的不常见性在结构和时间上都比较微妙，且 HC 主要关注结构），而 Sieve 仍能保持理想性能。

    结论: Sieve 在捕获不常见追踪方面表现出卓越的采样质量，明显优于 随机采样 和 分层聚类 方法，尤其是在处理结构和时间上的不常见性时。

6.4. 代表性采样 (Representative Sampling)

本实验评估 Sieve 获得具有代表性样本的能力，即包含不同模式追踪的样本。使用 TC 数据集（6561 条追踪，可分为 10 个 API 组）作为总体。为了与 HC 和 随机采样 进行比较，后两种方法的样本量设定为 Sieve 产生的样本数量。实验重复 50 次。

以下是三种方法在 TC 数据集上不同 API 组的代表性采样结果（原文 Table V）：

TABLE V RESULTS OF REPRESENTATIVE SAMPLING

分析:

• Sieve 在保留不常见追踪方面比 HC 更有效。对于数量非常少的追踪（如 API-1、API-2），Sieve 几乎全部保留。

• Sieve 丢弃了大部分常见追踪，这有助于节省存储空间。例如，对于 Population 为 4519 的 API-10，Sieve 仅保留 65.4 个，而 Random 采样了 217 个。

• 随机采样 在数量大的 API 组中采样更多，但在小数量 API 组中表现不佳。

• HC 在一些 API 组中（如 API-7, API-8, API-9）采样的数量比 Sieve 多，但这可能并非是由于它更好地识别了不常见性，而是由于其多样性目标导致的。

  结论: Sieve 能够更好地保留具有代表性的不常见追踪，尤其是在处理少数类追踪时表现突出，同时显著减少了常见追踪的存储。

6.5. 存储节省 (Storage Saving)

本实验评估 Sieve 带来的存储节省效果。

以下是 Sieve 在不同数据集上的采样率（原文 Table VI）：

TABLE VI SAMPLING RATES OF DIFFERENT DATASETS

分析:

• Sieve 能够将追踪数量大幅减少。在 VWR 数据集上，采样率低至 2.5%，即减少了 97.5% 的追踪。

• 即使在 AIOps 和 Boutique 数据集上，采样率也只有 4.5% 和 5.9%。

  结论: Sieve 实现了极低的采样率，从而带来了显著的存储成本节省。

6.6. 开销 (Overhead)

本实验测量 Sieve 进行采样所需的时间开销。将 RRCT 数量设置为 20（因为其性能与设置为 50 时近似）。

采样延迟包括三个部分：

1. 路径向量编码 时间。

2. 注意力分数 计算时间。

3. 采样概率 计算时间。

   以下是 Sieve 处理不同数据集时的采样延迟累积分布函数 (CDF) 图（原文 Figure 14）：

   

   分析:

• 采样延迟在 3ms 到 33ms 之间变化。

• 即使对于包含数百个 span 的生产追踪（如 TC 数据集），Sieve 也能高效处理。例如，在 TC 数据集上，大约 80% 的追踪在 20ms 内完成采样决策。

  结论: Sieve 的开销足够低，能够满足实时在线采样的需求。

7. 总结与思考

7.1. 结论总结

Sieve 提出了一种针对分布式微服务系统端到端追踪数据的、基于注意力机制的在线采样方法。它有效地解决了传统均匀采样方法容易丢失信息量大的不常见追踪的问题。通过将追踪编码为融合结构和时间信息的路径向量，并利用定制化的鲁棒随机切分森林 (RRCF) 算法，Sieve 能够准确识别结构和时间上的不常见模式，并为其分配高注意力分数。

实验结果表明，Sieve 能够显著提高不常见追踪的采样概率，同时大幅降低常见冗余追踪的存储，从而实现了高达 97.5% 的存储节省。Sieve 在不同程度的不常见性和参数设置下均表现出良好的鲁棒性，并且其低延迟的在线采样能力（3ms 到 33ms）使其适用于大规模生产环境。与现有的随机采样和分层聚类方法相比，Sieve 在捕获和保留不常见追踪方面展示了卓越的性能。

7.2. 局限性与未来工作

论文本身没有明确的“局限性”部分，但可以从实验结果和方法设计中推断出一些潜在的局限和未来工作方向：

• 阈值敏感性: 尽管实验表明 Sieve 对阈值 $h$ 在一定范围内不敏感，但选择一个全局最优的阈值可能仍然具有挑战性，并且可能需要针对不同系统或不同异常场景进行精细调整。不合适的阈值可能导致假阳性增加或真阳性遗漏。
• “注意力”的语义深度: Sieve 的“注意力机制”主要体现在其基于 RRCF 异常分数来调整采样概率。这与一些基于深度学习的更复杂的注意力机制（如 Transformer 中的 self-attention）在语义深度上有所不同。如果追踪的不常见性模式更加复杂，仅依赖路径向量和 RRCF 可能不足以捕获。
• 对新型、未知异常的适应性: RRCF 擅长识别与现有多数数据分布偏差较大的点。如果某种新型异常一开始就以一种“常见”的模式出现，或者其偏离程度非常微小但具有重要意义，Sieve 可能会面临挑战。
• 特征工程的扩展: 论文提到 路径向量 可以扩展以包含更多有意义的特征（如 span 数量、HTTP 状态码）。未来工作可以进一步探索更丰富的特征工程，例如结合上下文信息、用户行为或来自日志的语义特征，以提高不常见性检测的能力，就像 MEPFL [15] 所做的那样。
• 多目标优化: Sieve 主要目标是最大化不常见追踪的捕获并最小化存储。未来可以探索多目标优化，例如在保持一定采样率的同时，兼顾不同类型异常的覆盖率，或者优化采样策略以支持特定类型的离线分析任务。
• 可解释性增强: 尽管 RRCF 具有一定的可解释性（通过隔离路径长度），但对于复杂的 路径向量 和 注意力分数 机制，进一步提高其对运维人员的解释性，说明为什么某个追踪被认为是“不常见”并被采样，将是很有价值的。

7.3. 个人启发与批判

• 个人启发:

  • 问题切入点精准: 论文抓住了分布式追踪数据量大与信息密度低的核心矛盾，并明确提出通过偏向采样“不常见”追踪来解决，目标非常清晰。
  • 路径向量编码的巧妙: 将复杂的半结构化追踪数据巧妙地编码为融合了结构和时间信息的数值向量，这为后续的机器学习算法处理奠定了良好基础。这种编码方式在其他需要量化复杂图结构数据（如程序调用图、网络拓扑）的场景中也具有借鉴意义。
  • RRCF 在线能力的利用: RRCF 作为流数据异常检测的强大工具，被成功地适应并应用于在线追踪采样场景，体现了对现有算法的深度理解和创新应用。其维度扩展和维度降低机制是解决实际工程问题的关键。
  • 偏向采样策略的务实性: 结合方差差异阈值和 Sigmoid 函数的采样概率计算方式，能够有效地区分高度不常见和普通不常见追踪，并赋予不同的采样权重，这在实际系统中非常实用。

• 批判:

  • “注意力机制”的命名: 论文标题和摘要中多次提到“注意力机制”，但其具体实现主要是基于 RRCF 的异常分数，这在机器学习领域中通常不会被认为是狭义上的“注意力机制”（如 self-attention 或 transformer-attention），更像是基于异常值检测的权重分配。这种命名可能会让具有深度学习背景的读者产生一定的预期落差。建议在后续工作中更精确地描述这一部分，或者如果未来真的引入更复杂的注意力网络，则该名称将名副其实。
  • 注意力分数公式的表述存在歧义: 在方法论的 4.3.2 小节中，关于注意力分数 $s_i = \frac { m a x _ { \mathit { \theta } } d e p t h ( l , t _ { i } ) } { d e p t h ( l ^ { \prime } , t _ { j } ) }$ 的描述，论文原文“Intuitively, the significance of uncommonness should increase as the tree becomes deeper.”与“uncommon path vectors will have a shorter path from the root to leaf”以及公式的实际效果（浅层路径分数高）存在矛盾。这个表述需要更正或更清晰的解释，以避免读者误解。我已在方法论部分对此进行了说明和澄清。
  • 阈值 $h$ 的调优挑战: 尽管论文声称 Sieve 对阈值 $h$ 在有限范围内不敏感，但从 Figure 12c 的结果来看，$h$ 的选择确实对 FP 和 TP 的数量有显著影响。在实际生产环境中，确定一个合适的 $h$ 值可能仍需要一定的经验和试错，尤其是在面对新的、未知的异常模式时。这可能需要引入一些自适应的阈值调整机制。
  • “不常见”的定义: Sieve 将“不常见”等同于“容易被隔离”的模式，这在大多数情况下是合理的。然而，如果一个系统出现某种“慢毒”式故障，即在很长一段时间内，所有请求都受到轻微影响，导致整体延迟增加，但每个追踪的结构和相对延迟变化不大，这种“普遍的异常”可能不会在 RRCF 中表现出很高的“不常见分数”，从而被 Sieve 忽略。Sieve 更适合检测尖锐的、少数的异常，而不是普遍的、渐进的系统退化。