Stream concepts and algorithms

Batch versus stream processingSearch on YouTubeBookmarkSaved

Batch processing works on a bounded data set at rest. Stream processing works on unbounded events that keep arriving. Batch runs periodically (hourly, nightly) with latency of minutes to hours. Streaming runs continuously with latency of milliseconds to seconds.

Batch asks: what happened? Streaming asks: what is happening right now, and what should we do about it?

What a data stream isSearch on YouTubeBookmarkSaved

A data stream is a potentially infinite, time-ordered sequence of events. Events arrive continuously, often at high and varying speed. Each event is usually seen only once.

Five properties define a stream:

• Continuous. Data keeps arriving. There is no end-of-file to wait for.
• Unbounded. Total size is unknown and unlimited. You cannot store it all.
• Time-ordered. Each event carries a timestamp. Order and recency matter.
• Fast, bursty. Arrival rate is high and changes. A sale or a match spikes it.
• Transient. Events are processed on the fly, then discarded or archived.

Stream sources and questionsSearch on YouTubeBookmarkSaved

Streams come from sensors, users, markets, machines and phones. Each source has a typical standing question:

• IoT sensors. Temperature, vibration, smart meters. Query: alert if any machine exceeds 80°C.
• Clickstreams. Every page view, click and add-to-cart. Query: trending products in the last 10 min.
• Financial ticks. Stock trades, UPI and card transactions. Query: flag a card used in two cities within minutes.
• Logs and metrics. Web server, application and security logs. Query: 5xx error rate per minute.
• Social media. Posts, likes, hashtags, comments. Query: top hashtags in the last hour.
• Mobility and GPS. Ride-hailing, delivery fleets, buses. Query: surge pricing by area demand.

Why stream processing is hardSearch on YouTubeBookmarkSaved

Six constraints shape every streaming design:

• Single pass. Each event is seen once. You cannot rewind and re-scan the stream like a file.
• Bounded memory. Data is unlimited but RAM is limited. Keep summaries, samples or sketches, not everything.
• Low latency. The answer is worth most now. A fraud alert after an hour is useless.
• Approximate answers. Systems often trade a little accuracy for big savings. Unique users ±2% is fine.
• Out-of-order data. Network delays mean an event from 10:00 may arrive after one from 10:02.
• Variable rate. Bursts can exceed capacity. The system needs buffering and backpressure.

Stream data modelSearch on YouTubeBookmarkSaved

Each element is a tuple: a key, one or more values, and a timestamp. The schema may be fixed (sensor readings) or semi-structured (JSON click events). A stream is append-only: the past is never updated, and new facts are appended. Queries see the stream through a window of recent events or a compact summary (synopsis). Many streams can be processed together, e.g. join clicks with ad impressions.

Example from the slides, a temperature stream S:

The stream continues forever. This page calls each element an event below.

DSMS architectureSearch on YouTubeBookmarkSaved

A Data Stream Management System (DSMS) has five parts. They are input streams, the stream processor with its standing and ad-hoc queries, and output streams. The other two are limited working storage and archival storage.

Standing versus ad-hoc queriesSearch on YouTubeBookmarkSaved

A standing (continuous) query is registered once and evaluated on every new event or window. Example: emit an alert whenever any sensor reads above 40°C. Example: every minute, output the average temperature per sensor over the last 5 minutes. Implementation keeps only the state the query needs, e.g. a running sum and count per sensor.

An ad-hoc (one-time) query is asked once about the current state of the stream. Example: what was the maximum temperature in the last hour? It can only be answered if the system kept enough: a window of the last hour, or a summary like max per hour. Design rule: anticipate likely ad-hoc questions and keep a sliding window or sketch for them.

WindowsSearch on YouTubeBookmarkSaved

A window bounds an unbounded stream so a query can run on recent events. Three types exist:

• Tumbling. Fixed size, no overlap. Each event belongs to exactly one window.
• Sliding. Fixed size, slides by a smaller step. Windows overlap, so events repeat.
• Session. Variable length. It closes after a gap of inactivity.

The slides use the same eight events everywhere: $t = 1, 2.5, 4, 6, 7.5, 11, 12, 14$ s.

Event time, processing time, watermarkSearch on YouTubeBookmarkSaved

Two clocks exist:

• Event time. When the event happened, stamped at the source (sensor, phone). Use it for correct results.
• Processing time. When the streaming system sees the event. It is simple, but results change with network delays and restarts.

A watermark is the system's estimate that events up to time $T$ have arrived. Here: watermark = max event time seen $- 10$ min.

The slide example: a user scores a goal in a mobile game at 10:00:05, but the phone is in a tunnel and uploads at 10:03:40. By processing time the goal lands in the 10:03 window, which is wrong. By event time it lands in 10:00, where it belongs. With a 10-minute watermark it is accepted. An event 2 hours late would be dropped or sent to a late-data path.

One-pass algorithmsSearch on YouTubeBookmarkSaved

One pass and bounded memory force approximate methods. The slides name five:

Reservoir samplingSearch on YouTubeBookmarkSaved

Fill the reservoir with the first $k$ events. For event $i \gt k$, keep it with probability $k/i$. If kept, it replaces a uniformly random slot. Result: every event seen so far is in the sample with probability $k/n$.

Bloom filterSearch on YouTubeBookmarkSaved

A Bloom filter tests whether an event belongs to a large set without storing the set. It keeps a bit array of $m$ bits and $h$ hash functions. To insert, set all $h$ hashed bits to 1. To query, check all $h$ bits. If any bit is 0, the event is definitely absent. If all bits are 1, it is possibly present (it may be a false positive).

Counting distinct eventsSearch on YouTubeBookmarkSaved

Flajolet–Martin (FM) estimates how many different events appeared without storing them. Hash each event to a binary string. Count the trailing zeros of each hash. Let $R$ be the longest run seen. Estimate the distinct count as $2^R$. Reason: about half the hashes end in 0, and a quarter end in 00. An eighth end in 000. So a run of $R$ zeros appears once the count reaches about $2^R$. HyperLogLog extends this with many registers and a harmonic mean for a tighter estimate.

DGIM: counting ones in a windowSearch on YouTubeBookmarkSaved

DGIM answers "how many 1s were among the last $N$ bits?" using much less than $N$ bits of memory. It groups the 1s into buckets whose sizes are powers of two (1, 2, 4, …), with at most two buckets of each size. Old buckets expire as the window slides. Estimate: sum all bucket sizes except the oldest, plus half of the oldest bucket.

Count-Min sketchSearch on YouTubeBookmarkSaved

Count-Min estimates how often each event occurs, so you can find the heavy hitters. It keeps a small 2-D counter array with one hash function per row. To insert, increment one counter per row. To query, take the minimum across the rows. Collisions only add counts, so the estimate is never below the truth.

Fast data platformsSearch on YouTubeBookmarkSaved

Fast data is value that decays with time. A fraud score matters now, not next week.

Fast data platforms usually have three capabilities. First, durable high-throughput ingestion (Kafka). Second, a stream processing engine (Spark Structured Streaming, Flink). Third, fast serving storage (key-value stores, time-series databases, dashboards). Typical uses: fraud detection, live recommendations, predictive maintenance, network monitoring, live sports analytics, dynamic pricing.

Lambda architectureSearch on YouTubeBookmarkSaved

Lambda runs two paths: a batch layer and a speed layer. The batch layer recomputes complete views over the immutable master data set (Hadoop, Spark); views are hours old but accurate. The speed layer builds incremental views over recent data only (Storm, Flink, Spark Streaming); views are fresh but approximate. A serving layer merges both views per query. Batch recomputation also fixes errors in the speed layer.

Strength: accurate batch results plus low-latency recent results. Weakness: the same logic is written and maintained twice, in two systems that must agree (e.g. a Hive job plus a Storm topology).

Kappa architectureSearch on YouTubeBookmarkSaved

Kappa keeps one path. New events append to a durable, replayable log (a Kafka topic with long retention). A single stream processing job (Spark, Flink, Kafka Streams) reads the log and writes tables, dashboards and APIs. To reprocess, start a new job version from offset 0 and swap it in when it catches up.

Lambda is still useful when large historical computations, such as training ML models over years of data, run better as batch jobs. In practice many platforms are hybrids. Spark runs the same DataFrame code in batch and streaming mode. Lakehouse tables like Delta Lake or Iceberg serve as both streaming sinks and batch sources.

Streaming platform landscapeSearch on YouTubeBookmarkSaved

Two layers exist. Transport and storage of events: Kafka, Pulsar, Kinesis, plus Google Pub/Sub and Azure Event Hubs. They receive events from producers, store them durably and deliver them to consumers, but do little computation. Processing engines: Spark Structured Streaming, Flink, Storm, Kafka Streams. They read from the transport layer, compute (filter, aggregate, join, window) and write results. A typical stack is Kafka plus Spark or Kafka plus Flink.

Storm was the first widely used open-source stream processor. Flink is built for true streaming with strong event-time and state support. Spark Structured Streaming wins when the team already uses Spark for batch: the same DataFrame API works for both. Kafka Streams is a library, not a cluster: you embed it in an ordinary Java application.

Record-at-a-time versus micro-batchSearch on YouTubeBookmarkSaved

Four design questions shape a streaming system. How are events grouped for processing? What happens to events when something fails? Where does state live? How does the system scale and cope with bursts?

Delivery guaranteesSearch on YouTubeBookmarkSaved

Scenario: payment event P1 is read, the worker crashes, then restarts. Is P1 counted 0, 1 or 2 times?

State and checkpointsSearch on YouTubeBookmarkSaved

Stateless operations (map, filter, parse JSON) handle each event alone. They keep nothing to remember and restart with ease. Stateful operations (counts, windows, joins, deduplication, sessions) need memory across events, so the state must survive failures.

A checkpoint store (HDFS or S3) holds offsets plus a state snapshot. Example from the slides: the Kafka source sits at offsets 0 to 150. The operator holds running counts per user (u1: 12, u2: 7, u3: 30). The last checkpoint is at offset 120.

Scaling and backpressureSearch on YouTubeBookmarkSaved

Partitioning splits the stream by key (e.g. user id), so many workers process partitions in parallel. Events of one key stay together and in order. Parallelism grows with partitions and workers: in Kafka plus Spark, one Kafka partition maps to at least one Spark task.

If the sink is slower than the source, backpressure slows the intake rather than running out of memory: Spark's maxOffsetsPerTrigger, Flink's flow control. Buffering absorbs bursts: during a flash sale, events wait safely in the Kafka log and are processed as capacity allows.

Quick self-testSearch on YouTubeBookmarkSaved

1. Differentiate batch processing and stream processing on input, latency and answer.

Batch works on a bounded data set at rest, with latency of minutes to hours and an exact answer over complete data. Streaming works on unbounded arriving events, with latency of milliseconds to seconds and an incremental, per-window answer that may be approximate.

2. Events arrive at t = 0.5, 2, 4.5, 5.5, 9 s. Give the counts for 4 s tumbling windows.

Windows are $[0,4)$, $[4,8)$, $[8,12)$. $[0,4)$ holds 0.5, 2, so 2. $[4,8)$ holds 4.5, 5.5, so 2. $[8,12)$ holds 9, so 1. Counts: 2, 2, 1.

3. Watermark delay is 10 min and the max event time seen is 11:00. An event stamped 10:55 and one stamped 10:40 arrive. Which is accepted?

$W = 11{:}00 - 10\,\text{min} = 10{:}50$. The 10:55 event is $\gt W$, so it is accepted. The 10:40 event is $\lt W$, so it is late and dropped (or sent to a late-data path).

4. Reservoir with k = 3 sees 8 events. With what probability is the 6th event kept, and with what probability is any given event in the final sample?

$P(\text{keep 6th}) = 3/6 = 1/2$. After $n = 8$, every event is present with probability $k/n = 3/8$.

5. A 10-bit Bloom filter with h1(x) = x mod 10 and h2(x) = (2x+3) mod 10 holds bits 7. Query 35 and 31.

35 gives $h_1 = 5$ and $h_2 = 3$. Both bits are set, so possibly present: a false positive (35 was never inserted). 31 gives $h_1 = 1$. Bit 1 is 0, so definitely absent.

6. Differentiate event time and processing time. Why does the game-goal example need event time?

Event time is when the event happened (stamped at the source). Processing time is when the system sees it. The goal happened at 10:00:05 but uploaded at 10:03:40. Processing time puts it in the 10:03 window, which is wrong. Event time puts it in 10:00, where it belongs.

7. Differentiate at-most-once, at-least-once and exactly-once delivery. What decides the guarantee?

At-most-once commits the offset before processing (loss possible, no duplicates). At-least-once commits it after (duplicates possible, no loss). Exactly-once commits output and offset atomically via checkpoints, replayable sources and idempotent or transactional sinks. The commit order decides the first two.

8. Differentiate Lambda and Kappa. When would you still choose Lambda?

Lambda runs two paths (batch plus speed) and merges the views. Kappa runs one streaming path over a replayable log. Choose Lambda when heavy historical computations, such as training ML models over years of data, run better as batch jobs.

9. Why can an exact distinct count not run on an unbounded stream, and what does FM store instead?

Exact counting stores every distinct event, but the stream is unbounded and memory is bounded. FM stores only the longest run $R$ of trailing zeros in the hashes and estimates $2^R$.

10. Why do Count-Min estimates never fall below the truth, and how does the query keep the error small?

Counters only increase and collisions only add counts, so no estimate falls short. The query takes the minimum across hash rows, and the least-collided row is closest to the truth.