Stable-Sketch: A Versatile Sketch for Accurate, Fast, Web-Scale Data Stream Processing

Weihe Li, Paul PatrasWWW 2024 · OpenReview

In the world of web-scale data—think click fraud detection or real-time recommendation systems—speed is everything. Engineers often use "sketches," which are compact, probabilistic data structures that summarize massive streams of data using very little memory. However, as data rates climb and CPU L1 caches remain stubbornly small, traditional sketches struggle. They often accidentally "evict" important items (heavy hitters) to make room for a flood of insignificant ones.

A new paper, "Stable-Sketch: A Versatile Sketch for Accurate, Fast, Web-Scale Data Stream Processing," introduces a clever way to solve this by looking at more than just frequency: it looks at "stability."

TL;DR

Stable-Sketch is a novel data structure that uses "bucket stability"—a measure of how often a memory slot changes—to protect important items from being accidentally deleted. It achieves significantly higher accuracy (up to 6x better F1 scores in some cases) and faster processing speeds than current state-of-the-art methods, even when restricted to tiny L1 cache sizes.

What Problem Does This Paper Address?

Data streams are highly "skewed": a few items (the "heavy hitters") appear constantly, while the vast majority appear only once or twice. To keep up with millions of packets per second, sketches must fit into the CPU's fastest memory (the L1 cache, usually $\le$ 64KB).

The challenge is imprudent replacement. Most existing sketches use a "uni-dimensional" approach—they only look at an item's current frequency to decide if it should be replaced by a newcomer. In a crowded, high-speed stream, a heavy hitter might be kicked out by a burst of "noise" items before it has a chance to prove its importance. This leads to poor detection accuracy for heavy hitters, heavy changers, and persistent items.

Methods

The authors propose Stable-Sketch, which introduces a multi-dimensional approach to item replacement.

  1. The Data Structure: It uses a 2D array of buckets. Each bucket tracks three things: the item's Key, its Value (frequency or persistence), and its Bucket Stability.
  2. Bucket Stability ($S$): This is the "secret sauce." If a new item arrives and matches the stored key, $S$ increases. If the bucket is full and a different item tries to enter but fails to replace the incumbent, $S$ also increases. If an item is successfully replaced, $S$ decreases. Essentially, $S$ quantifies how "settled" a bucket is.
  3. Stochastic Decay: Instead of a simple "if-then" replacement, Stable-Sketch uses a probability-based decay formula: $P_{replace} = \frac{1}{V \times S + 1}$. The higher the frequency ($V$) and the higher the stability ($S$), the harder it is for a newcomer to evict the stored item.
  4. Hardware Optimization: The team used SIMD (Single Instruction, Multiple Data) instructions to parallelize the process of checking multiple rows at once, and they implemented the design in P4, a language for programming high-speed hardware switches.

Datasets

The researchers evaluated Stable-Sketch using several diverse, real-world datasets:

  • CAIDA (2015, 2016, 2018): Anonymized IP traffic traces from a major internet backbone.
  • MAWI: A 15-minute trace from a Japanese wide-area network.
  • Campus DNS: Traffic gathered from a university DNS network over 10 days.
  • Synthetic Intrusion Dataset: Used specifically to test performance in anomaly detection scenarios.

Key Insights and Ideas

  • Stability as a Proxy for Importance: The "aha moment" is realizing that a bucket that hasn't changed in a while is likely tracking something important. By protecting "stable" buckets, the sketch naturally filters out the noise of infrequent items.
  • Multi-Dimensionality Wins: Moving beyond just "frequency" allows the sketch to be much more "prudent" with its limited memory.
  • Early Exit: Unlike some sketches that hash an item into every single row (wasting time), Stable-Sketch stops as soon as it finds an available bucket or a match. This significantly boosts throughput.

Key Results

The performance gains were substantial across heavy hitter, heavy changer, and persistent item detection:

  • Accuracy: Stable-Sketch consistently achieved the highest F1 scores. On the CAIDA 2018 dataset, it improved accuracy by 12.7% to 542% compared to nine other state-of-the-art sketches.
  • Error Reduction: The Average Relative Error (ARE) was reduced by massive margins—for example, by over 1800% compared to the RAP sketch on CAIDA 2015.
  • Speed: It outperformed MV-Sketch by 16% and On-Off Sketch by 25% in update throughput. Using SIMD instructions further boosted speed by roughly 78%.
  • Deployment: The P4 implementation showed that Stable-Sketch uses very few hardware resources (only ~3% of SRAM and ~20% of ALUs on a switch), making it viable for real-world network hardware.

Limitations and Future Work

While Stable-Sketch is highly effective, the authors note a few areas for consideration:

  • The "Heavy-on-Heavy" Eviction: While rare, a heavy hitter can still be evicted by another heavy hitter if they collide in the same buckets.
  • Memory vs. Speed Trade-off: To further reduce errors, one could use "hash chains" to find alternative buckets, but the authors admit this would slow down the update speed, which is a deal-breaker for some web-scale applications.
  • Future Directions: The authors suggest applying the "stability" concept to other tasks like finding "superspreaders" or detecting traffic bursts.

Paper Citation: Anonymous Author(s).

  1. Stable-Sketch: A Versatile Sketch for Accurate, Fast, Web-Scale Data Stream Processing. In Proceedings of ACM Conference (WebConf’24). Source Code Available on GitHub.

Summary updated

Abstract

Data stream processing plays a pivotal role in various web-related applications, including click fraud detection, anomaly identification, and recommendation systems. Accurate and fast detection of items relevant to such tasks within data streams, e.g., heavy hitters, heavy changers, and persistent items, is however non-trivial. This is due to growing streaming speeds, limited fast memory (L1 cache) available in current systems, and highly skewed item distributions encountered in practice. In effect, items of interest that are tracked only based on their features (e.g., item frequency or persistence value) are susceptible to replacement by non-relevant ones, leading to modest detection accuracy, as we reveal. In this work, we introduce the notion of bucket stability, which quantifies the degree of recorded item variation, and show that this is a powerful metric for identifying distinct item types. We propose Stable-Sketch, an elegant and versatile sketch that exploits multidimensional information, including item statistics and bucket stability, and adopts a stochastic approach to drive replacement decisions. We present a theoretical analysis of the error bounds of Stable-Sketch, and conduct extensive experiments to demonstrate that our solution achieves substantially higher accuracy and faster processing speeds than state-of-the-art sketches in a range of item detection tasks, even with tight memories. We further enhance Stable-Sketch's update throughput with Single Instruction Multiple Data (SIMD) instructions and implement our solution with P4, demonstrating real world deployment viability. We make the source code of Stable-Sketch publicly available on GitHub.
BibTeX
@inproceedings{li2024stable,
  author = {Weihe Li and Paul Patras},
  title = {{Stable-Sketch: A Versatile Sketch for Accurate, Fast, Web-Scale Data Stream Processing}},
  booktitle = {WWW},
  year = {2024},
  url = {https://openreview.net/forum?id=lMzaCOz8oh},
}
Figure