Streaming Analytics

Windowed aggregates & watermarks

Prerequisites

graph TD
  Streams[Unbounded event streams] --> Algo[Streaming Algorithms]
  Algo --> Analytics[Streaming Analytics]
  Batch[MapReduce / batch] -.->|contrast| Analytics
  Windows[Event-time windows] --> Analytics
  WM[Watermarks & lateness] --> Analytics

When to use

Continuous dashboards (trending topics, fraud spikes, live revenue) where batch dams are too slow.
Event-time correctness when mobile or edge devices deliver events out of order after tunnels or offline queues.
Composable windowed metrics backed by probabilistic sketches (HLL, CMS, T-Digest) for fixed RAM per window.

When not to use

You can replay the full stream into a warehouse hourly — batch may be simpler and exact.
Every late event must count for billing or compliance — tighten SLAs or use processing-time / correction streams, not a single tight watermark.
The workload is low volume and fits in a SQL database — streaming ops cost more than you save.

Lab

On the interactive streaming analytics lab, scrub ingest progress through a synthetic clickstream processed in receive order. Tune allowed lateness Δ and tumbling window width, watch the watermark close windows on a scrolling event-time timeline, and compare emitted window totals to hindsight exact sums. Try Tunnel late (wide Δ), Tight watermark, or Before window close presets, then predict whether tunnel events arriving after close will be dropped.

Simple Fundamental Explanation

Imagine you are standing next to a massive river, and your boss asks you: “Exactly how many gallons of water flowed past you today?”

The Batch Approach: You build a giant dam, stop the entire river, put all the water into a massive bucket, weigh the bucket, and then release the water. This gives an exact number, but it ruins the ecosystem and takes forever. (This is traditional Hadoop/MapReduce batch processing).
The Streaming Approach: You dip a small bucket into the river every 5 seconds, measure the speed of the water, and calculate an estimate. You never stop the river. You give your boss a real-time, highly accurate estimation that updates every second. (This is Streaming Analytics).

Streaming Analytics is the processing of continuous, never-ending data streams in real-time. Because you cannot store a never-ending stream in memory, you must use probabilistic algorithms to summarize, count, and analyze the data as it flies past you.

Deep Dive: How It Works Under the Hood

Modern streaming engines (like Apache Flink or Apache Kafka Streams) process unbounded data.

Windows and Event Time

Because streams never end, analytics are run over “Windows” (e.g., a Tumbling Window of 5 minutes). However, in distributed networks, a mobile phone might send an event at 1:00 PM, but the data center might not receive it until 1:05 PM due to a tunnel. Streaming engines probabilistically handle “late data” using Watermarks. A watermark is a heuristic assertion: “I am 99% confident that I have received all data that occurred before 1:00 PM.” Once the watermark passes 1:00 PM, the system calculates the final analytics for that window and emits the result.

Probabilistic Sketches in Streams

If a stream processes 1 million credit card transactions per second, how do you detect fraud (e.g., “Has this card been used in 5 different cities in the last minute?”)? You cannot query a relational database 1 million times a second.

Instead, the streaming engine updates probabilistic sketches in RAM:

HyperLogLog: “How many unique IPs visited the site in the last window?”
Count-Min Sketch: “What are the top 10 trending hashtags right now?”
T-Digest: “What is the 99th percentile (p99) latency of all API requests in the last hour?”

Visual Diagram: The T-Digest for Percentiles

Stream of API Latencies (ms):
10, 15, 12, 100, 11, 14, 500, 12 ... (Millions of events)

If you store everything to find the exactly p99: Memory explodes (O(N)).

T-Digest Approach:
Group nearby values into "Centroids" (averages with weights).

Centroid 1 (Mean 12.5, Weight 10,000)   <-- Normal requests
Centroid 2 (Mean 105.0, Weight 500)     <-- Slow requests
Centroid 3 (Mean 498.2, Weight 50)      <-- Very slow requests (The tail)

The T-Digest dynamically adjusts so centroids near the edges (the 1st and 99th percentiles) are smaller and more accurate, while the middle is heavily compressed.
Memory: Fixed (e.g., 2 KB). Output: Highly accurate p99 estimate.

Twitter ingests hundreds of thousands of tweets per second. The “Trending Topics” algorithm must calculate the fastest-growing keywords globally.

If they used a traditional database (SELECT word, count(*) GROUP BY word ORDER BY count DESC), the database would instantly melt.

Instead, Twitter uses a streaming topology (traditionally Apache Storm or Heron). As tweets flow through the network, the text is tokenized, and the words are fed into a distributed layer of Count-Min Sketches. A heavy-hitter algorithm continuously pulls the highest estimated values from the sketches. The list of trending topics updates globally in milliseconds, using only a tiny fraction of the memory required for exact counting.

The Mathematics: Equations and In-Depth Analysis

1. The Heavy Hitters Problem (Misra-Gries Algorithm)

A classic probabilistic streaming algorithm is identifying elements that appear more than $N / k$ times in a stream (where $N$ is total items).

The Misra-Gries algorithm keeps at most $k - 1$ counters.

When a new item arrives, if it has a counter, increment it.
If it does not have a counter, and there are less than $k - 1$ counters, create a new counter for it and set it to 1.
If there are already $k - 1$ counters, decrement all counters by 1. (If a counter hits 0, delete it).

Mathematically, if an item actually appears more than $N / k$ times, it is absolutely guaranteed to survive the decrement process and remain in the counter list at the end of the stream. The exact count will be slightly underestimated, but the “Heavy Hitter” is successfully identified using only $O (k)$ memory, regardless of how massive $N$ becomes.

2. Watermark Generation Probabilities

In stream processing (like Apache Flink), generating a watermark $W (t)$ means declaring that no data with an event time $t^{'} < W (t)$ will arrive in the future. Because networks are chaotic, this is a probabilistic declaration. If the network delay $D$ follows a Gamma or Exponential distribution, the system calculates $W (t) = CurrentTime - Δ$ , where $Δ$ is chosen such that:

P (D > Δ) < ϵ

Where $ϵ$ is the acceptable percentage of dropped late data (e.g., 0.001%). The system continuously analyzes the real-time distribution of packet delays and dynamically adjusts $Δ$ to balance latency (fast analytics) against completeness (accurate analytics).

Lab

Scrub ingest progress through a synthetic mobile clickstream processed in receive order. Tumbling event-time windows accumulate revenue-like totals; the watermark closes a window when max(event time) − Δ passes its end. Late tunnel events after close are dropped — compare emitted totals to hindsight ground truth.

Ingest progress100% · 20 events

Allowed lateness Δ3 event-time units

Window width[0, 10)

Event-time timeline (dots = processed events; vertical line = watermark):

[0, 10) ✓

[10, 20) ✓

[20, 30) ✓

[30, 40) …

W=32

Event time →

Recent ingest order (newest right):

c07+10c08+8c09+9c10+5c11+3c12+4c13+6c14+2c15+5c16+7c17+4c18+8c19+6c20+3

[0, 10)

Partial (open)27

Emitted27

Exact (hindsight)49

Late dropped3

[10, 20)

Partial (open)30

Emitted30

Exact (hindsight)30

[20, 30)

Partial (open)15

Emitted15

Exact (hindsight)15

[30, 40)

Partial (open)13

Emitted—

Exact (hindsight)13

After the full stream with Δ=3, will the emitted total for window [0, 10) match the hindsight exact sum, or will tunnel events that arrive after the watermark closes the window be dropped?

20 events ingested · watermark 32 · 3 late dropped (22 value lost).