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

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

图 11 展示了 CBS、SWTC 和 FP、CBS-FP 算法的对比. 我们调节 CBS 算法和 SWTC 算法的样本比例展开
实验, 并同时调节 FP 和 CBS-FP 算法的采样概率, 使得 4 种算法的内存消耗保持一致. 从图 11 中可以看出, 采用
固定空间消耗的两种算法的平均误差低于各自的固定概率采样变体, 最大误差则没有明显区别. 这是由于基于固
定概率采样的方案需要按照流量峰值预留内存, 而非峰值时刻, 样本集合大小会随着流量降低而降低, 无法充分利
用预留内存, 导致非峰值时刻的准确度不如固定空间消耗的方案. 但是最大误差主要受峰值时刻影响, 这时两类方
案的样本大小相近, 因此最大误差区别较小. 此外, CBS-FP 和 CBS 算法的平均相对误差均低于 SWTC 算法. 但是
需要注意的是, 实际应用中是无法预估峰值流量的, 所以固定概率采样方案的应用场景会更加受限.

CBS SWTC CBS SWTC
20 CBS-FP FP 120 CBS-FP FP
平均相对误差 (%) 12 8 最大相对误差 (%) 80
100
16
60

4 40
20
1.0 1.5 2.0 2.5 3.0 3.5 4.0 1.0 1.5 2.0 2.5 3.0 3.5 4.0
样本比例 (%) 样本比例 (%)
图 11 固定概率采样算法和固定空间消耗算法的误差对比

图 12 则展示了 CBS、SWTC 算法和全动态模型算法的 ThinkD 和 WRS 的对比, 通过调节算法的内存占用来
进行实验. 可以看出, ThinkD、WRS 在内存达到 153 MB 以上时才开始工作, 这些算法需要 240 MB 以上的内存才
能将平均误差控制在 2% 左右, CBS 和 SWTC 算法则只需要 80 MB 内存就能达到该效果. 这说明了将全动态模型
算法直接迁移到滑动窗口模型是十分低效的. 而相比 SWTC 算法, CBS 算法具有更低的误差.

CBS SWTC CBS SWTC
14
WRS ThinkD 60 WRS ThinkD
12
平均相对误差 (%) 10 8 6 最大相对误差 (%) 40
50
30

10
2 4 20
0 0
40 80 120 160 200 240 40 80 120 160 200 240
内存占用 (MB) 内存占用 (MB)
图 12 CBS、SWTC 算法与全动态模型算法的误差对比

4.6 消融实验
本节分析 CBS 算法的误差随着区间划分数量 d 的变化, 并分析 ETM 误差修正算法的影响. 我们测试了没有
误差修正的 CBS 算法, 称为 CBS-bias 的估算误差, 和完整版的 CBS 算法对比, 如图 13 所示. 该图采用了指数坐标
轴, 因为 CBS-bias 算法的误差变化范围极大. 实验采用 StackOverflow 数据集, 滑动窗口长度设置为 4M, 采样比例
设置为 4%. 图 13 加入 SWTC 算法的误差作为对比. 由于 SWTC 算法中没有参数 d, 所以其误差曲线为一条水平
线. 从图 13 中可以看出, CBS 和 CBS-bias 算法的误差都会随着 d 的增加而降低, 而 CBS-bias 算法收到的影响尤
为明显. 由于缺乏误差修正, 当 d 较小时, CBS-bias 算法报告的事实上是一个远大于滑动窗口的区间中的三角形数