一句话总结

爱丁堡大学提出 Stable-Sketch，这是一种面向 Web 规模数据流处理的通用 sketch，利用元素统计信息和新颖的桶稳定性（bucket stability）指标等多维信息来驱动随机替换决策，从而在内存预算紧张的情况下，相较当前最先进 sketch 大幅更准确且更快速地检测热点元素、高变化元素和持久元素，同时通过 SIMD 指令获得额外吞吐收益，并以 P4 实现展示实际部署可行性。

核心贡献

• 引入桶稳定性作为量化已记录元素变化的指标，并证明它有助于识别相关元素类型，例如热点元素、高变化元素和持久元素。

• 提出 Stable-Sketch，它是一种基于 sketch 的结构，将元素统计信息与桶稳定性相结合，并应用随机替换决策，以在内存预算紧张时提高检测准确率。

• 理论误差界和大量实验证明，Stable-Sketch 相较当前最先进 sketch 具有更高检测准确率和更快处理速度，同时 SIMD 与 P4 实现支持高吞吐部署。

引言

以 Web 为中心的流测量对于用户行为分析、流量分析、入侵检测和 Web 个性化至关重要，但在高速率下逐元素跟踪不切实际，因此使用 sketch 在有限内存内近似检测热点元素、高变化元素和持久元素。先前方案通常使用一维元素特征决定何时替换已存储元素，这会在 L1 缓存预算紧张、偏斜分布、频繁哈希冲突、指针或 DRAM 开销以及精细参数调优等情况下损害准确率，并且可能难以部署到快速硬件平台上。作者利用桶稳定性（反映桶变化频率的多维信号）和元素信息定义 Stable-Sketch，这是一种使用基于这两种信号的替换概率的通用 sketch。该工作给出理论误差界、SIMD 加速、跨检测任务的实验以及 P4 原型，以表明其具备高准确率、紧凑内存、快速更新和实际部署能力。

方法

作者采用扁平 sketch 架构，解决紧凑流式检测中的核心可靠性问题：仅依赖单一计数器（如频率或持久性）的替换策略可能错误驱逐有用的热点元素或持久元素。其关键洞察是，已记录元素持久性更高的桶更可能包含真正重要的数据。他们将这一思想形式化为桶稳定性：当到达元素映射到某个桶但未能改变已记录键时，该桶的稳定性增加；当已记录键实际被替换时，稳定性减少，并以零为下限。由于热点元素预期会随着时间占据其映射到的桶，追踪热点元素的桶应表现出更高稳定性。参见下图：

这一观察启发了一种多维替换决策，它将元素相关性信息与桶稳定性相结合，使非热点元素在内存预算紧张时越来越难以取代潜在热点元素。

Stable-Sketch 的数据结构是具有 $m$m 行 $u$u 列的扁平数组。每一行关联不同的两两独立哈希函数 $h_1, \ldots, h_m$h1​,…,hm​，$B(i,j)$B(i,j) 表示第 $i$i 行第 $j$j 列的桶。每个桶存储三个字段：键字段 $B(i,j).K$B(i,j).K、值计数器 $B(i,j).V$B(i,j).V 和稳定性计数器 $B(i,j).S$B(i,j).S。键字段可以存储完整元素键以实现可逆性，或在内存受限变体中存储指纹。值计数器存储任务特定统计量，例如频率或持久性，而稳定性计数器汇总同一元素占据该桶的一致程度。参见框架图：

Stable-Sketch 执行两项主要操作：更新和查询。更新期间，到达元素 $f$f 依次通过各行进行哈希。如果映射到的桶为空，则插入该元素，并将桶初始化为 $B(1,h_1(f)).K = f$B(1,h1​(f)).K=f、$B(1,h_1(f)).V = 1$B(1,h1​(f)).V=1 和 $B(1,h_1(f)).S = 1$B(1,h1​(f)).S=1。如果映射到的桶已经存储 $f$f，则 $V$V 和 $S$S 都递增。如果元素没有找到可用桶，则更新进入概率衰减阶段。该 sketch 从 $m$m 个哈希桶中选择值计数器最小的桶，记为 $B(R,M)$B(R,M)。然后计算替换概率

$$p_{R,M} = \frac{1}{B(R,M).V \times B(R,M).S + 1}.$$pR,M​=B(R,M).V×B(R,M).S+11​.

该概率设计意味着，已记录值和稳定性都较高的桶更不容易被替换。如果随机试验失败，则丢弃新元素。如果成功，则所选桶的值计数器减 1。如果该计数器变为 0，则桶采用新元素，值计数器重置为 1，稳定性计数器减 1。由于该过程使用衰减而非立即驱逐，估计误差是单边的，只影响低估。查询操作扫描所有桶，并返回估计值超过设定阈值的元素。

对于热点元素检测，更新过程可通过三种代表性情况理解。找到空桶的元素会立即插入，并终止哈希查找。找到已包含自身键的桶的元素会增加对应的值计数器和稳定性计数器。在每一行都发生冲突的元素会选择值计数器最小的桶，并应用上述衰减规则。参见更新示例：

同一基础结构可适配其他检测任务。对于高变化元素检测，作者在连续时间区间上分别构造多个 sketch，并在查询时比较每个元素的频率差。差值超过阈值的元素被报告为高变化元素。对于持久元素检测，每个桶增加一个标志位，以确保每个时间窗口内持久性至多递增一次。该标志在每窗口开始时重置，如果所选桶在当前窗口已具有活动标志，则拒绝替换尝试。这可防止重复持久性更新，同时保留稳定性驱动的保护机制。

该方法伴有形式化误差保证。对于实际值为 $V(f)$V(f)、估计值为 $\hat{V}(f)$V^(f) 的任意元素 $f$f，该设计满足

$$\hat{V}_t(f) \le V_t(f),$$V^t​(f)≤Vt​(f),

这意味着 Stable-Sketch 不会高估元素值。在假设热点元素插入后仍留在其桶中的情况下，作者进一步推导出如下形式的低估误差界

$$\Pr\left\{V(f) - \hat{V}(f) \ge \lceil \beta N \rceil\right\} \le \frac{\ln(V(f)) + \varphi}{\beta N \ln(S)},$$Pr{V(f)−V^(f)≥⌈βN⌉}≤βNln(S)ln(V(f))+φ​,

其中 $S$S 是与记录 $f$f 的桶关联的稳定性，$\varphi$φ 是欧拉-马斯刻若尼常数，$N$N 表示所有元素的总条目数。该界刻画了稳定性在降低低估风险中的作用。

为提升部署效率，更新路径可用 SIMD 指令加速。该实现不再逐行检查，而是使用强哈希原语 MurmurHash3_x64_128 计算哈希值，并将其拆分为对应各行的 $m$m 部分。随后，使用 SIMD 相等原语（例如 _mm256_cmpeq_epi64）将新到达元素的键与多个行中已记录的键并行比较。这将定位第一个可用匹配桶的开销从顺序行扫描降低为并行比较步骤。参见吞吐比较：

该优化提升了更新吞吐，同时保留“每个元素在第一个可用桶中被跟踪”的语义行为。当 sketch 超过最快缓存层级时，从较慢内存区域读取数据会增加延迟并可能降低吞吐，因此当活跃工作集保持缓存友好时，加速效果最强。

实验

实验在真实流量数据集上评估 Stable-Sketch 的热点元素、高变化元素和持久元素检测能力，并在不同内存预算下与代表性 sketch 基线进行比较。Stable-Sketch 始终实现更高检测准确率和更低估计误差，同时消融实验和阈值研究确认其鲁棒性以及各设计组件的贡献。它也比基线方法提供更快更新和查询，并且经 SIMD 加速并部署在可编程交换机上后，其性能仍然具有实用价值。

在三个 CAIDA 跟踪数据上，随着内存大小从 16KB 增加到 256KB，MV-Sketch 中非热点元素错误替换热点元素的事件急剧减少。内存紧张会导致数十万次错误替换事件，而更大内存可将其降至数百次或更少。CAIDA 2016 在 16KB 时错误替换次数最多，CAIDA 2018 在 256KB 时最少。内存压力会显著增加 MV-Sketch 中错误驱逐热点元素的情况。更高的内存预算在所有三个跟踪数据上都一致减少错误替换事件。

该实验评估内存大小如何在三个 CAIDA 网络跟踪数据中影响 MV-Sketch 内非热点元素对热点元素的错误替换。结果验证了内存预算紧张会导致热点元素频繁被错误驱逐，而增加可用内存会显著减少这些替换错误。总体而言，这些发现表明内存压力是 MV-Sketch 准确率的主导因素，更大的内存分配会持续改善热点元素保留能力。