Streaming

Streaming#

Streaming and online algorithms operate on data that either does not fit in memory or arrives faster than the operator can afford to recompute. The bargain is approximation, the algorithm returns an answer that is provably close to the exact answer, with sub-linear memory and one (or a few) passes over the data.

The operator’s working set covers counts, distincts, frequencies, quantiles, sketches, and stream-shaped windowed statistics.

Reservoir sampling#

Sample k items uniformly from a stream of unknown length. Memory O(k).

import random

def reservoir(stream, k):
    res = []
    for i, x in enumerate(stream):
        if i < k:
            res.append(x)
        else:
            j = random.randint(0, i)
            if j < k:
                res[j] = x
    return res

Bloom filter#

Probabilistic set membership. Tests are either “definitely not in the set” or “probably in the set” (with controllable false-positive rate). Constant time per insert / lookup; constant memory.

  • Used: dedupe streams, URL-seen-before, distributed cache negative lookups, password-breach checks.

  • Variants: counting Bloom (supports deletes), scalable Bloom (grows when full), Cuckoo filter (supports deletes, better performance at high load).

HyperLogLog#

Probabilistic count-distinct. Estimates the cardinality of a multiset using only a fixed-size sketch (typically 1.5 KB for ~2% error).

  • Used: count unique visitors / IPs / device IDs at warehouse scale. Built into Redis (PFADD / PFCOUNT), ClickHouse, BigQuery (APPROX_COUNT_DISTINCT), Postgres extensions.

Count-Min Sketch#

Approximate frequency of items in a stream. Overestimates counts; never underestimates. Memory sub-linear in stream size.

  • Used: heavy-hitter detection (top-k), DDoS source-IP ranking, real-time rate limiting.

T-digest and KLL#

Streaming quantile sketches.

  • T-digest (Dunning): merge centroids weighted by quantile. Good accuracy at the tails. Used in InfluxData, ClickHouse quantileTDigest, Datadog’s distributions.

  • KLL (Karnin-Lang-Liberty): theoretically tight quantile sketch. Used in Apache DataSketches.

Frequency / top-k#

Algorithm

Detail

Misra-Gries

Find approximate top-k heavy hitters in a single pass with O(k) memory.

Space-Saving

Improvement on Misra-Gries; tracks counts with bounded error.

Count-Min + heap

Combine sketch with a top-k heap; standard pattern at scale.

Sliding-window statistics#

When the operator needs “the last N events” or “the last T seconds” without recomputing.

Window

Detail

Tumbling

Fixed non-overlapping bucket: 1m, 5m, 1h. The simplest aggregation.

Hopping (sliding)

Overlapping windows: every 30s, look back 5m.

Session

Window closes after a gap of inactivity.

Punctuated

Window closes on an explicit marker (end-of-batch token).

For event-time correctness with out-of-order data, the operator uses watermarks (Apache Flink, Beam) to declare “this much out-of-orderness is allowed.”

Online learning#

Models that update on each example without retraining from scratch.

Method

Detail

Stochastic gradient descent (SGD)

Update parameters on each example. The basis for almost every online learner.

Online logistic regression

Classification with constant per-example update. Used in ad-click models.

Online k-means

Each new point updates the nearest centroid.

Vowpal Wabbit

Production online learning toolkit; linear models, contextual bandits.

River

Modern Python online-learning library.

Hoeffding trees

Online decision trees with bounded loss versus batch tree.

Concept drift#

Detect when the data-generating process has shifted:

  • ADWIN (Adaptive Windowing), keeps a window that auto-shrinks on drift.

  • DDM, EDDM, error-rate-based drift detectors.

  • Page-Hinkley, cumulative-deviation test on a metric.

Streaming engines#

Engine

Detail

Apache Kafka Streams

Library on top of Kafka. Stateful processing, exactly-once semantics, RocksDB-backed state.

Apache Flink

Standalone distributed stream processor. Strong event-time + watermarks; first-class CDC.

Apache Beam

Unified batch + stream API. Runs on Flink, Spark, Dataflow.

Spark Structured Streaming

Micro-batch (or continuous) stream processing on top of Spark.

Materialize / RisingWave

Streaming SQL databases. Write SQL queries that maintain materialised views incrementally.

Faust / Bytewax / Quix

Python-native stream processors.

Patterns#

  • Lambda, batch + stream pipelines with a serving layer that merges. Older pattern; complexity cost is high.

  • Kappa, stream only; reprocess historical data by replaying the log. The modern default given Kafka / Pulsar.

Pitfalls#

  • Skew, hot keys make stateful streams unbalanced. Salt or pre-aggregate.

  • Late arrival, watermarks let the operator bound waiting; past the watermark, late records are dropped or routed separately.

  • Exactly-once, available in Kafka Streams, Flink, Beam (with the right sinks). Verify end-to-end; the marketing claim often hides a “with-some-caveats.”

  • Backpressure, sink-driven; if the downstream cannot keep up, the source slows down. Plan capacity at the slowest stage.

References#

Contents