Cruxly › System design › Foundations of Data Systems

Batch and Stream Processing

the same computation over data that has an end, or data that never does, and the price of each

Batch and stream processing are two answers to one question: when do you compute over your data, and what do you do when the answer is wrong or late? This lesson treats them as data-system design, not as product names. It covers the shuffle that makes batch scale, event time and watermarks that make streams correct, what exactly-once really means, and how to choose.

Systems of record and derived data: where processing fits

Claim: every pipeline is a function from a source of truth to a derived copy, and the design question is how stale the copy may be.

A system of record holds the facts once: the orders table, the ledger, the append-only event log. Everything else is derived data: a search index, a cache, a daily revenue table, a recommendation model, a materialised dashboard. A derived copy can be thrown away and recomputed from the record, which is the property processing systems exploit. If a derived view is wrong, you fix the code and recompute, rather than patching rows by hand.

That reframes batch versus stream as a freshness choice. Both compute the same function over the same inputs. They differ in when the work happens and what each recomputation costs.

The two sit on the same dataflow. The Dataflow paper (Google, VLDB 2015) argues that a batch job is a special case of a stream: a bounded input whose completion is known, so the watermark can stay at the beginning of time until all data is read and then jump to infinity. Practically, the engines differ because bounded input lets you use simpler, cheaper strategies (sort everything, no state to checkpoint), and unbounded input does not.

What a senior says in the room: "What is the system of record here, and can I rebuild this view from it? If I can, I am free to choose the cheapest processing that meets the freshness target. If the view is the only copy, I have a database, not a pipeline, and I should design it like one." What they check: that every derived store has a named source and a documented rebuild path, and how long a full rebuild takes at today's data size.

The applied halves of this lesson are Ad Click Aggregation and Metrics Pipeline, which run the stream side end to end. How a durable log stores and replicates events is in Kafka as a log store: ISR, acks, compaction, transactions and LinkedIn scale, and the queue-versus-log distinction is in Queues and Async Work. This lesson does not repeat them.

Batch: the MapReduce idea (partition, map, shuffle, reduce) and why Spark generalised it

Claim: batch scales because the only expensive step is the shuffle, and everything else is embarrassingly parallel and restartable.

The MapReduce paper (Dean and Ghemawat, OSDI 2004) gave the shape that every later batch engine inherits. You write two functions: map turns each input record into zero or more intermediate key/value pairs; reduce merges all values that share a key. The runtime does the rest.

1. Split the input into M pieces, typically 16 to 64 MB each, so tasks are small and can be placed near their data.
2. Map tasks run in parallel and write their output to the local disk of the worker, partitioned into R pieces by a function such as hash(key) mod R.
3. Shuffle: each reduce task pulls its partition from every map worker's disk over the network, then sorts it by key.
4. Reduce tasks write final output to a global file system.

The shuffle is the all-to-all step: every map task may have data for every reduce task. In the paper's own example, M = 200,000 and R = 5,000 on 2,000 workers. Worked arithmetic (not the paper's figure): 200,000 x 5,000 is 10^9 potential map-to-reduce partition pieces, and 200,000 splits at 16 to 64 MB is 3.2 to 12.8 TB of input. Skew breaks this: if one key holds 30% of the records, one reducer receives 30% of the data and the job's runtime is that one reducer's runtime.

Fault tolerance is re-execution, not replication. The paper says completed map tasks are re-run when their worker dies, because their output sits on that worker's local disk and is gone. Completed reduce tasks are not re-run, since their output is already in the global file system. In one run, network maintenance made groups of 80 machines unreachable for several minutes, and the job still finished. Tasks must be deterministic and side-effect free for this to be safe.

Stragglers are the quiet cost. The paper's backup-task mechanism launches duplicate copies of the last few in-progress tasks and takes whichever finishes first, for a few percent more resources. Its sort of about 1 TB (10^10 100-byte records) took 891 seconds with backup tasks and 1,283 seconds without, 44% longer, because five reduce tasks dragged on for 300 seconds after 960 seconds. The same idea as a tail-latency technique is in The Tail at Scale (Dean and Barroso).

The combiner is the cheap optimisation to remember: when the reduce function is commutative and associative (summing counts), run a partial reduce on each map worker before the shuffle. Word frequencies follow a Zipf distribution, so a single map task can emit thousands of <the, 1> pairs; combining them first can cut shuffle bytes dramatically.

Why Spark generalised it. MapReduce writes every stage's output to disk and chains stages through the file system, so a multi-step job pays disk and a scheduling round trip per step. Spark expresses the whole job as a graph of operations over partitioned datasets and can keep intermediate data in memory between stages. The shuffle remains: any groupBy, join or distinct on non-co-partitioned data still moves data across the network. The takeaway is that the model matured (graphs of operators, not just two functions), while the cost model did not change.

:::key What to remember from the original paper Task sizes of 16 to 64 MB, partitioning by hash(key) mod R, re-execution of completed map tasks after a worker failure, and backup tasks for stragglers (sort: 891 s versus 1,283 s without them). From the MapReduce paper, OSDI 2004, read November 2026. The paper's cluster figures are historical; use them for shape, not for sizing today's hardware. :::

What a senior says in the room: "The job is as slow as its biggest partition. Before I add machines I look at key skew, and I ask whether a combiner or a pre-aggregation removes shuffle bytes." What they check: shuffle read/write bytes per stage, the max-to-median task duration ratio (a large ratio means skew or stragglers), and whether the job is deterministic enough to be retried.

What batch is good at: reprocessing, backfills, large joins

Claim: batch wins when correctness over the full history matters more than seconds of latency, and when you need to change your mind about the past.

Four jobs where a bounded, rerunnable computation is the right tool:

• Reprocessing after a bug. A stream job had a wrong currency conversion for two days. With the source events retained, you rerun the corrected code over those two days and replace the derived output. The job reads a fixed input and overwrites a fixed output, so it can be run twice without harm.
• Backfills. A new metric, a new model feature or a new index needs history that the live pipeline never computed. A batch job reads months of data in parallel at the speed of the cluster, rather than replaying at the live rate.
• Large joins and global aggregations. Joining a billion-row fact table to a dimension, or computing a global top-k, is naturally a sort-merge or hash join over the shuffle. A stream engine can do this only by holding the join state for the whole window.
• Training and analytics scans. Whole-dataset passes that read most of the data are cheaper per byte in a batch with large sequential reads and a columnar layout, as covered in Storage engines: B-trees, LSM-trees, row vs column.

Batch also gives you simple operational semantics. If a job fails at 3 a.m., the runbook is "rerun it". Idempotence is by construction: the job writes to a fresh output location and then atomically swaps it in. That works because the input is a snapshot. If upstream data keeps changing, define the cut-off explicitly, for example "all events with event time before midnight UTC, read at 02:00", and record it.

Where batch hurts:

• Latency floor. A daily job means the freshest data is a day old, plus runtime. Hourly is possible, but small frequent batches multiply fixed scheduling and startup overhead.
• Late data is a calendar problem. If events arrive after the batch ran, you rerun or you accept a correction window. State that policy.
• The thundering recompute. Recomputing everything to update 0.1% of rows wastes the cluster. Incremental processing, covered next, is the answer, and it is the point where batch and stream meet.

Worked arithmetic (illustrative numbers, not a benchmark): reprocessing 90 days of 2 TB per day is 180 TB. At an aggregate scan rate of 10 GB/s, that is 18,000 seconds, five hours. A stream replay at the original live rate would take 90 days. This is why a replayable source plus a batch-speed backfill path is a standard requirement.

What a senior says in the room: "If I cannot rerun history, I cannot fix a bug in the past. So the raw events are the asset, and the pipelines are disposable." What they check: raw-event retention that outlasts the longest plausible correction window, and a tested backfill that completes inside an acceptable window.

Stream: events, topics and consumer state

Claim: a stream processor is a loop that reads events from a durable log, updates state, and records how far it got. Everything else follows from those three things.

An event is an immutable fact with a timestamp: "user 7 clicked ad 42 at 10:03:11". Events are written to a topic, an ordered, partitioned, retained log. A consumer's progress is tiny. The Kafka design docs say each partition is consumed by one consumer in a group, so the position is a single integer, the offset of the next message to read. Because that state is small, acknowledging is cheap, and a consumer can rewind to reprocess. Replay is the property that connects stream processing to batch: a retained log makes a backfill a matter of reading from an earlier offset.

Stateless work (filter, map, parse) is easy: any worker can handle any event. The interesting jobs are stateful: counts per user, the last N events per session, a join between two streams. State lives with the operator that owns the key, so the stream is first partitioned by key: all events for user 7 go to the same worker, the same idea as the shuffle in batch, now continuous. Flink's docs describe state in terms of key groups, whose number equals the configured maximum parallelism and which are the unit by which state is redistributed when you rescale.

State size is the number that decides the architecture:

• Small state (per-key counters) fits in memory. A 50-byte counter for 10 million keys is 500 MB (worked arithmetic).
• Large state (long windows, joins over hours of history) needs an embedded on-disk store. Flink's docs name an in-memory hash map and RocksDB as two state backends, configurable without changing application logic. The disk-backed one trades speed for capacity and for cheaper, incremental snapshots of a big state.

Two kinds of lag to watch. Consumer lag is the distance in offsets or seconds between the newest event and the consumer's position. Growing lag means you are slower than the producers, and you are accumulating a backlog that is bounded only by retention. If lag exceeds retention, events expire before they are read and data is silently lost. Event-time lag is how far the pipeline's notion of "now" trails reality, covered in the next section.

Back pressure is the protective behaviour: when a downstream operator is slow, upstream operators slow down or buffer, rather than falling over. A log in front of the processor helps, because the log absorbs the spike and the processor catches up at its own speed, the same spike-absorbing idea as in Queues and Async Work.

What a senior says in the room: "Which keys, how much state per key, and what is the state's retention? That fixes the partition count and the backend." What they check: consumer lag in seconds with an alert well below retention, state size per task, and the skew of keys across partitions (one hot key pins one partition and one task).

Event time versus processing time, windows and watermarks

Claim: windows by arrival time are easy and wrong; windows by event time are right and force you to decide when to stop waiting.

The Dataflow paper separates two clocks. Event time is when the thing happened, and it never changes for an event. Processing time is when the pipeline observes it. The gap between them, the skew, changes constantly because of network delay, mobile devices that were offline, retries and backlogs. Count "clicks per minute" by arrival time and a ten-minute outage replays as a giant spike in one minute. Count by event time and the numbers land in the minutes where the clicks happened.

Windows slice an unbounded stream into finite groups to aggregate. The common kinds: tumbling (fixed, non-overlapping, such as each 5 minutes), sliding (fixed length, advancing by a smaller step, so events fall into several windows) and session (grouped by gaps in activity, so window boundaries depend on the data). Spark's docs make the point that a window aggregation is just a grouping on the event-time column.

The question a window forces: when have I seen all the events for the 10:00 to 10:05 window? You never know for certain. The paper says to assume you never know whether you have seen all the data. The practical device is the watermark, a lower bound on event time that the system believes has been fully observed. The paper describes it as often heuristic, and gives the example of someone taking a phone into the wilderness and uploading viewing data days later. No system can know that.

The paper names both failure directions precisely:

• Too fast. The watermark passes the window end, then data arrives behind it. That data is late and needs a policy.
• Too slow. A single straggling datum holds the watermark back for the whole pipeline, so all results are delayed, even those that are complete.

The model answers with triggers and accumulation modes. A trigger says when to emit a window's result: at the watermark, at periodic processing-time intervals, or per count of records. Emitting early gives a fast, approximate answer; emitting again on late data gives a correction. Accumulation then says how corrections relate: discarding (each firing is a delta), accumulating (each firing replaces the previous total), or accumulating and retracting (emit a retraction of the earlier value, then the new one, so that a downstream grouping stays correct). Pick based on the sink: a key-value store that overwrites suits accumulating, an additive counter suits discarding, and a multi-stage aggregation needs retractions.

Spark Structured Streaming exposes the same idea as a watermark threshold: you specify how late data may be, and the engine uses it to drop old state. That is the other half of the bargain. A watermark is also a state garbage-collection rule: once it passes a window, the window's state can be freed. With no bound on lateness, state grows without limit.

What a senior says in the room: "What lateness can the business tolerate, and what is the cost of a wrong early number versus a late right one? I would fire early for the dashboard and correct on the late data, and I would send anything beyond the lateness bound to a side output and count it." What they check: the late-record rate, the watermark lag against wall-clock time, and the size of window state.

Exactly-once effect: checkpoints plus idempotent sinks

Claim: nothing is delivered exactly once over an unreliable network. What you can build is an exactly-once effect: at-least-once delivery plus state that is restored consistently plus a sink that tolerates repeats.

A worker crashes after it updated its state and before it told anyone. On restart it must decide whether it processed event 500. Three outcomes exist: lose it (at-most-once), process it again (at-least-once) or arrange that processing it again changes nothing (exactly-once effect). Real systems build the third from the second.

Checkpoints give consistent state. Flink's docs describe snapshots based on a lightweight asynchronous approach inspired by Chandy and Lamport. Barriers are injected at the sources and flow with the records; they never overtake records. When an operator has received the barrier from its inputs, it snapshots its state and forwards the barrier. A checkpoint is complete when all sinks acknowledge. On failure, the job restores the last complete checkpoint and the sources rewind to the positions recorded in it. Two details matter:

• Alignment. An operator with several inputs waits for the barrier on all of them, so records from different snapshots do not mix. Skipping alignment lowers latency but then records after barrier n can be processed before snapshot n, so they are seen twice on restore: that mode is at-least-once. Unaligned checkpoints (since Flink 1.11) let barriers overtake in-flight data, which is stored as part of the state, aimed at pipelines with a slow path where alignment can take very long. The docs note it adds I/O pressure.
• Checkpointing is off by default in Flink, and savepoints are the manually triggered kind for upgrades, which do not expire when newer checkpoints finish.

Spark's Structured Streaming reaches the same end differently: checkpointing and write-ahead logs record the offset range each trigger processes. Its docs state the recipe plainly: replayable sources (offsets) plus idempotent sinks give end-to-end exactly-once under failure.

The sink is where the guarantee ends. Checkpoints cover the engine's state, not the outside world. An email already sent cannot be unsent. Two patterns make a sink safe:

• Idempotent writes. Write with a deterministic key, so a repeat overwrites with the same value: UPSERT INTO totals (window, key) VALUES (...). An accumulating window result suits this, because the second write simply replaces the first. A non-idempotent += 1 does not.
• Transactional commit with the position. The Kafka design docs say that for destinations outside Kafka, exactly-once requires cooperation from the destination, and suggest storing the consumer's offset alongside its output so that both update together or neither does. Within Kafka, the docs describe idempotent producers (sequence numbers for deduplication, since 0.11.0.0) and transactions across partitions, which a consumer sees only if it sets isolation.level=read_committed. Kafka Streams uses this to write offsets and output in one transaction. The mechanics are in Kafka as a log store.

:::key Verified November 2026 Flink stable docs: checkpointing disabled by default; unaligned checkpoints since 1.11; savepoints always aligned. Kafka 4.1 design docs: transactional exactly-once requires isolation.level=read_committed and enable.auto.commit=false on the consumer. Spark 4.x overview: micro-batch latencies as low as 100 ms with exactly-once, continuous processing as low as 1 ms with at-least-once. Re-check version-specific defaults before relying on them. :::

What a senior says in the room: "I never promise exactly-once to the business. I promise that the effect on the database is the same as if each event were processed once, and I show them the idempotent key that makes it true. Side effects like emails get a dedupe key and are treated as at-least-once." What they check: that every sink has an idempotency key or a transactional offset commit, the checkpoint duration versus the interval (if a checkpoint takes longer than the interval, the job spends its life checkpointing), and a periodic restore-from-checkpoint drill.

Lambda, Kappa and unified batch/stream: when one pipeline is enough

Claim: the lambda architecture exists because streams were once approximate and batch was exact. The reason to avoid it today is that it makes you write, test and operate the same logic twice.

Lambda runs two paths in parallel over the same input: a speed layer (stream) gives low-latency, possibly approximate results, and a batch layer recomputes the accurate answer later and overwrites it. A serving layer merges the two. The Dataflow paper's reading is that Lambda sidesteps the completeness problem instead of solving it: it offers the best quick estimate now, with eventual correctness when the batch catches up, at the price of building and maintaining two systems. The paper also notes that tools that hide both engines behind one API reduce the code duplication but not the operational burden of two runtimes.

The failure modes of lambda are practical:

• Two codebases, two sets of bugs. The stream and batch versions of the same logic drift. A fix lands in one path, and the dashboard flickers when the batch result replaces the stream result with a different number.
• Merge logic in the serving layer is its own source of bugs.
• Double the capacity and on-call burden.

Kappa drops the batch layer. There is one stream-processing path and one durable, replayable log. To reprocess, you start a second copy of the job with new code, replay the log from the beginning into a new output, and switch readers when it catches up. This needs a log with retention long enough to hold the history you might need, and a processor that can replay fast. The cost is storage in the log and the replay time, which is the same arithmetic as the backfill example earlier.

Unified engines take the Dataflow model's claim at face value: one API and one set of semantics, where batch is a bounded stream. Flink's docs, for example, state that batch programs do not use checkpoints; they recover by replaying the bounded input, backtracking only to the stages whose intermediate results are no longer available. Spark's structured streaming uses the same DataFrame operations in batch and streaming. The code is shared; the runtime strategies still differ underneath.

When one pipeline is enough: if the stream result is exact once late data is handled (event time, watermarks, idempotent sink), there is nothing for a batch layer to correct, and Kappa or a unified job is enough. Keep a separate batch path when: the logic needs the full history in a way state cannot hold cheaply (a model retrained on years of data), the log cannot retain what a replay needs, or finance requires an audited, reproducible, closed-book number at a fixed cut-off.

What a senior says in the room: "I would not start with two pipelines. I would ask whether the stream result can be made exact with event-time and late-data handling. If a reconciliation job still catches differences, that is a monitor, not a second source of truth." What they check: retention versus the longest replay, a diff job comparing stream totals against the source of truth, and who owns the logic in a single place.

Choosing: a decision table and three worked workloads

Claim: choose from the freshness the business pays for, the cost of a wrong number, and whether you can replay.

Default to the simplest thing that meets the freshness target. A nightly batch that works is better than a stream that nobody understands.

Workload 1: daily revenue report for finance. Bounded (yesterday's orders), needs to match the ledger exactly, runs once a day. Choose batch: a scheduled job over a snapshot cut at a fixed time, writing to a fresh partition, with a reconciliation against the system of record. Streaming would add complexity for freshness nobody asked for.

Workload 2: card fraud scoring. A decision is worth something only within about a second of the swipe, and the features (transactions in the last 10 minutes per card) are windowed aggregates. Choose stream, with state per card, event-time windows, and a bound on lateness. Add a batch job for the part that needs history: retraining the model on months of labelled data, whose output is a new model version loaded by the stream job. This is two paths with different jobs, not lambda's two paths for the same job.

Workload 3: ad click counts per campaign for a billing dashboard. Clicks arrive late and duplicated, billing needs correct counts, and the dashboard wants near-real-time. This is the case in Ad Click Aggregation: a stream with event-time windows gives the fresh view, idempotent upserts keyed by campaign and window make replay safe, and a periodic reconciliation against the raw log catches drift. The raw events are retained so any window can be recomputed.

One more shape, generic and not any company's design: a payments platform needs a seconds-level fraud stream and an end-of-day settlement batch. Both read the same transaction log, and the settlement batch is the number that must tie out exactly.

What a senior says in the room: "I pick by the freshness the user pays for, and I make the log the common input so I can always rebuild. I keep the stream result honest with a reconciliation, not with a second pipeline." What they check: the end-to-end freshness SLO and how it is measured, the replay time for the longest retained window, and a clear owner for the logic.

Further reading: Designing Data-Intensive Applications by Martin Kleppmann covers batch processing, stream processing and the dataflow viewpoint at book length. The primary papers are Dean and Ghemawat, MapReduce: Simplified Data Processing on Large Clusters (OSDI 2004) and Akidau et al., The Dataflow Model (VLDB 2015).

How to say it in the interview

"First I split the data into the system of record and what is derived from it. Derived views can be rebuilt, so I pick batch when the input is bounded and hours of latency are fine, because it is simple and reruns cleanly. I pick a stream when the answer is worth something within seconds. Then I say three things: windows are by event time, not arrival time; the watermark is a guess, so late data needs a policy; and exactly-once is checkpointed state plus an idempotent sink, not magic. In the original MapReduce paper a one-terabyte sort ran in 891 seconds, and in the Dataflow paper the lesson is that batch is just a stream whose watermark jumps to infinity."

Checklist

• Named the system of record and the derived views, and how each view is rebuilt
• Chose batch or stream from the freshness target and cost of a wrong number, not from a product name
• Checked key skew and shuffle volume before adding machines to a slow batch job
• Defined windows by event time and stated the allowed lateness and the late-data policy
• Treated the watermark as a guess and alerted on its lag against wall-clock time
• Made every sink idempotent (deterministic key or offset committed with the output)
• Set consumer-lag alerts well below log retention
• Sized operator state per key and chose the state backend and checkpoint interval from it
• Kept raw events long enough to cover the longest correction window and tested a backfill
• Avoided a second pipeline for the same logic, and used reconciliation to catch drift

Related lessons

• Reliable, Scalable, Maintainable: Measuring a System
• Clocks, Ordering and Partial Failure
• Choosing a Datastore
• How Indexes Actually Work
• Replication and Consistency
• Partitioning and Sharding