Page 387 - 《软件学报》2025年第9期

4298 软件学报 2025 年第 36 卷第 9 期

判断目标跨度的目标位置的参数索引是否在符合要求的取值索引中. 如果符合条件, 则交由重构器还原该追踪的
文本表示.

算法 3. 单字段搜索过程.
输入: 目标字段 key, 比较符 operator, 比较取值 value, 跨度容器 span_containers, 结构列表 structs, 压缩分组
groups;
输出: 符合条件的追踪数据 traces.
1. spans ← {}, structs ← {}, traces ← []
2. for each span in span_containers //遍历所有跨度容器, 寻找符合条件的跨度
3. if key in span.key_dict and index_of(value, span.param_dict[key], operator, value) > 0
4. spans[span] ← index_of(value, span.param_dict[key], operator, value) //记录符合条件的取值索引
5. for each struct in structs //遍历所有结构, 寻找包含目标跨度的结构
6. if struct.spans ∩ spans is not empty
7. structs[struct] ← position_of(struct, spans) // 记录目标跨度在结构中的位置
8. for each group in groups
9. if group.structs ∩ structs is not empty
10. data ← decompress(group) // 解压符合条件的压缩分组
11. for each trace in data
12. if trace.struct ∈ structs and trace.get_value(structs[trace.struct]) ∈ spans
13. traces ← trace ∪ traces //将符合条件的数据加入结果列表中
14. return traces

跨度容器 1 结构容器 分组 1 索引
索引字典 组合字典
ID 字段值 指针 ID 参数值 ID 组合 追踪 ID 结构 ID 开始时间
http.status_code>200 0 kind 0 200 0 (0, 1) 0 1 1 0 1700000
1 http. status_code 1 400 1 (0, 1, 2) ... ... ... ...
... ... 2 500 ... ...

跨度 ID 组合索引 位置 取值索引 结构 ID 跨度 ID 位置
1 0 1 [1, 2] 0 1 [1]
1 1 ... ... ...
... ... ... ...
图 8 字段搜索示例流程

除了字段查询以外, NCQT 还支持根据结构搜索相关追踪. 由于结构容器中记录了每种结构的序列化表示, 定
位器既可以快速判断被查询的两个跨度是否在某个结构中属于祖先与后代的关系, 又可以找出被查询跨度指定跳
数以内的上下游节点. 相较于字段搜索, 结构搜索无需遍历跨度容器, 因此拥有更快的查询速度.
NCQT 通过预加载的方式缓解了搜索冷数据的问题. 如果查询过程中定位到的分组尚未解压, 则会带来较长
的解压时间开销, 第 4 节给出了分组是否需要解压时的查询延迟对比. 考虑到用户在查询数据时可能围绕同一场
景对相关追踪进行搜索, 且压缩的追踪数据根据相似性分组, NCQT 在解压时可以选择对被解压分组的相邻分组
后台并行解压, 从而提高后续查询命中已解压分组的概率.

3.3.2 解 压
从编码器解压数据的过程与压缩过程相似. 算术编码使用网络模型的概率估计解析数据, 然后网络模型根据
新窗口输出下个字符的概率, 重复该过程直至所有数据解压完成. 具体而言, NCQT 首先使用相同的均匀分布概率