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

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

● 单调值处理. 在跨度数据中, 通常可以看到一些字段具有单调的值, 尤其对于连续的条目, 可能会有相近的
取值, 这些字段包括时间戳、数据库事务标识符、计数器等. 例如, “startTimeUnixNano”和“endTimeUnixNano”字
段是由 19 个字符的长字符串组成, 而一个请求通常在秒甚至毫秒级别即可执行完成, 时间戳中代表年份、月份和
日期部分的数字是多余的. 对于这些单调值的字段, NCQT 首先记录最小的值, 然后用偏移量代替原始值, 从而删
除大量不必要的数字. 在解压缩时, 只需要通过最小值和偏移量重新计算实际值. 在图 4 中可知, 跨度大多数字段
涵盖了字段取值的类型, 因此很容易即可找出可以处理的字段, 而对于跨度开始和结束时间, 我们记录根跨度的开
始时间, 对于每条追踪以此作为基准值计算每个跨度的时间偏移.
图 5 展示了一个跨度容器如何抽取数据冗余并返回编码后的数据. 最终的输出为一个元组, 其中包括一个 32
位组合 ID, 两个 64 位的时间偏移以及一个 32 位参数 ID 组成的序列, 序列的长度对应于该组合下字段的个数. 这
种结构旨在提供对跨度数据的紧凑表示, 有助于进一步的压缩和处理, 同时确保了重要信息的完整性.

跨度数据
参数值
字段值 指针
索引字典
参数值

参数值
组合
组合字典

开始时间偏移 结束时间偏移 参数索引
编码后数据

图 5 预处理

3.1.2 调用图嵌入和聚类
在原始的追踪文件中, 追踪按照收集的时间顺序存储, 不同请求产生的追踪交错排列. 这种排列方式不利于压
缩算法识别数据中的重复模式, 且进一步增大了搜索的时间成本. 图嵌入和聚类旨在通过识别不同追踪结构的相
似性, 将具有相似跨度组成或调用关系的追踪数据组织在一起, 减少局部信息熵, 进而提高编码器的压缩率以及搜
索器的查询效率.
追踪的调用图是由跨度节点组成的多叉树, 理论上, 基于树编辑距离的方法可以更好地衡量追踪结构之间的
2
差异. 然而, 在许多微服务系统中它们的成本太高, 因为比较所需的时间复杂度为 O(N ), 其中, N 为追踪调用图中
包含的跨度数量. 因此, 已有研究提出了一些轻量级的嵌入方法 [6,17] 以获取追踪图的向量表示, 从而减少不同追踪
间比较的时间开销. 然而, 这些方法要么忽略了追踪的树状结构, 要么与具体的跨度数据相关. 因此, 我们提出了一
种轻量的基于 N-gram 的追踪结构嵌入方法, 通过在图上滑动一个长度为 N 的窗口提取局部特征.
如算法 1 和图 6 所示, NCQT 通过以下方式生成追踪的表示. 首先, 通过深度优先搜索的顺序遍历每一个调用
图的节点, 并将节点加入从根节点开始的路径列表, 其中每一层中优先遍历开始时间较早的节点. 当列表长度不小
于 N 时, 将列表末尾 N 个节点的服务调用序列作为尾节点的调用路径. 如果遍历到叶子节点时列表长度小于 N,
则将从根节点开始的完整调用链加入该调用图的路径表中. 最后, 方法收集所有调用图的调用路径, 并根据调用路
径为每种结构生成一个向量表示. 具体而言, 方法判断每个调用路径的存在性, 如果某个调用路径存在, 方法将该
维度的取值设为此调用路径的数量, 否则设为 0. 值得注意的是, 由于一个追踪中可能含有重复的跨度, 因此可能
存在某个调用路径出现多次的情况.