Lesson 11: Stream Processing

Lesson 0011 — 45 min read

Chapter 10 covered batch processing — bounded datasets, deterministic jobs, materialized intermediate state. Chapter 11 removes the bounded assumption. The input is unbounded: events arrive continuously, and you never finish processing. This changes everything about how you reason about time, joins, ordering, and fault tolerance.

The central insight: a stream is the derivative of a database, and a database is the integral of a stream. State is just an event log that has been accumulated over time. This idea connects change data capture, event sourcing, materialized views, and stream processing into a single framework.

From Batch to Stream

Batch processing assumes bounded input — a known, finite dataset. The job knows when it's done. MapReduce's sort step must read the entire input before producing any output (the last record might be the one with the lowest key). This is fundamentally incompatible with unbounded data.

You can fudge it by slicing time into chunks: process a day's worth of data every day, or an hour's worth every hour. But daily batch means 24-hour delay. Hourly means 1-hour delay. The logical conclusion is to process continuously — every event as it arrives. That's stream processing.

Stream = data incrementally made available over time. The concept already exists everywhere: stdin/stdout, TCP connections, audio/video streaming, lazy lists. This chapter treats event streams as a data management mechanism — the unbounded counterpart to batch files.

Transmitting Event Streams

An event is a small, self-contained, immutable object recording something that happened at a point in time. It contains a timestamp (according to some clock), and is encoded as text, JSON, or binary (Avro, Thrift — see Chapter 4).

The naive approach: producers write to a database, consumers poll for new events. But polling is expensive when delays are low — most polls return nothing. Better to notify consumers when new events arrive.

Messaging Systems

A messaging system decouples producers from consumers. Two critical questions differentiate every system:

1. What happens if producers outpace consumers? Three answers: drop messages, buffer in a queue, or apply backpressure (block the producer). Unix pipes/TCP use backpressure with a fixed-size buffer.
2. What happens if nodes crash — are messages lost? Durability costs: write to disk, replicate, or accept loss for higher throughput.

Direct Messaging

No intermediary: UDP multicast (financial tick data, low latency), ZeroMQ/nanomsg (brokerless pub/sub over TCP), StatsD (unreliable UDP metrics — approximate only), webhooks (HTTP callback). All assume producers and consumers are constantly online. If a consumer is offline, it misses messages (unless the producer buffers + retries, risking producer crash = data loss).

Message Brokers (JMS/AMQP style)

Centralized broker (RabbitMQ, ActiveMQ, IBM MQ, Google Cloud Pub/Sub). Producers and consumers connect as clients. Durability moves to the broker.

Consumer Patterns: Load Balancing vs Fan-Out

• Load balancing — each message delivered to one consumer (work sharing). AMQP: multiple clients on same queue. JMS: shared subscription.
• Fan-out — each message delivered to all consumers (independent processing). JMS: topic subscription. AMQP: exchange bindings.

The two can be combined: multiple consumer groups, each doing fan-out within the group.

Acknowledgments and Redelivery

Consumers acknowledge processed messages so the broker can delete them. If the connection drops without acknowledgment, the message is redelivered to another consumer. Caveat: the original consumer may have fully processed the message but lost the acknowledgment in transit. Result: message reordering (Figure 11-2). Load balancing + redelivery inevitably reorders messages. Use separate queues per consumer if ordering matters.

Partitioned Logs (Kafka-style)

JMS/AMQP treats messaging as transient — receiving + acknowledging a message deletes it. This is destructive: you can't rerun the same consumer and get the same result, and new consumers can't read past messages.

Log-based message brokers (Kafka, Kinesis, DistributedLog) combine database durability with message broker notification. The core data structure is an append-only log — exactly the same as the write-ahead log from Chapters 3 and 5.

Log-Based Architecture

• Partitions — the log is split across machines. Each partition is a separate append-only file on disk.
• Offsets — monotonically increasing sequence number per partition. Messages within a partition are totally ordered. No ordering across partitions.
• Producers append to the end of a partition.
• Consumers read sequentially; tail -f model.
• Consumer groups — each partition assigned to one consumer in the group (coarse-grained load balancing). Max parallelism = number of partitions.

Log vs Traditional Messaging

Consumer Offsets and Disk Management

The consumer offset is like a database log sequence number (LSN). If a consumer fails, another picks up at the last recorded offset — may reprocess some messages (at-least-once). The offset is under consumer control, so replaying old messages is trivial: just reset the offset.

The log is a circular buffer on disk. A 6 TB drive at 150 MB/s sequential write holds ~11 hours of max-throughput data. In practice, deployments retain days or weeks of data. If a consumer falls behind and its offset points to a deleted segment, it misses messages — but only that consumer is affected.

Databases and Streams

The connection between databases and streams is fundamental: a replication log is a stream of database write events. State machine replication says: if every replica processes the same events in the same order, they end up in the same state.

The Dual Writes Problem

Real applications need multiple data systems: OLTP database + cache + search index + data warehouse. Keeping them in sync via dual writes (app code writes to each system) has two problems:

1. Race condition (Figure 11-4): two concurrent updates arrive in different orders at database vs search index. The systems diverge permanently.
2. Partial failure: one write succeeds, the other fails — systems diverge. Fixing this requires atomic commit (expensive 2PC).

The solution: make the database the single leader, and turn everything else into followers that consume its change stream.

Change Data Capture (CDC)

CDC observes all data changes written to a database and exposes them as a stream. The database is the system of record; derived systems (search index, cache, warehouse) consume the change stream.

• Implementation: parse the replication log (binlog for MySQL, WAL for PostgreSQL, oplog for MongoDB). Tools: Debezium, Maxwell (MySQL), Bottled Water (PG), LinkedIn Databus, Facebook Wormhole.
• Asynchronous by default — the source database doesn't wait for consumers. Replication lag issues apply (see Chapter 5).
• Initial snapshot: for a new consumer, start with a consistent snapshot at a known log offset, then apply incremental changes.
• Log compaction: retain only the most recent value per key (like LSM-Tree compaction). A new consumer can start from offset 0 and get a full copy of the database without a separate snapshot.

Event Sourcing

Event sourcing takes CDC's idea up one level of abstraction. Instead of capturing low-level state changes, the application logic is built on immutable events in an append-only log. Updates and deletes are discouraged.

Commands vs Events: a request is a command (may fail validation). Once validated and accepted, it becomes a durable, immutable event. Consumers cannot reject events — by the time they see one, it's a fact.

Derive current state by replaying the event log (deterministic transformation). Snapshots optimize reads. The relationship: state = ∫ event stream, change stream = d(state)/dt.

State, Streams, and Immutability

The key realization: mutable state and an append-only event log are two sides of the same coin. The log is the truth; the database is a cache of the latest value per key (Pat Helland). This is exactly how accounting works: ledgers are append-only, and accounts are derived by summing transactions.

Advantages of Immutable Events

• Auditability: never lose information. Even "removed from cart" is valuable for analytics. Buggy code → rollback + rerun, no data corruption.
• Multiple read views (CQRS): from one event log, derive different read-optimized representations. Evolve applications by adding new consumers without schema migrations.
• Simplified concurrency: each event is a self-contained description of a user action. Only one write needed (append to log) vs many writes (update multiple tables). Single-threaded log consumer needs no concurrency control.

Limitations of Immutability

• Storage churn: high update/delete rate on small dataset → log grows fast. Compaction and garbage collection become critical.
• Regulatory deletion: GDPR "right to be forgotten" requires actual deletion, not just appending a deletion event. Excision (Datomic), shunning (Fossil).
• Hard to truly delete: copies exist in storage engines, filesystem caches, SSDs, backups. Deletion is about making data hard to retrieve, not impossible.

Processing Streams

Three things you can do with a stream once you have it:

1. Write to a database / cache / index — keep derived systems in sync.
2. Push to users — email alerts, push notifications, real-time dashboards.
3. Process to produce derived streams — pipeline of operators.

Complex Event Processing (CEP)

Search for patterns in event streams (1990s technology). Declarative queries specify event patterns; the engine maintains state machines. Reversed relationship: queries are stored long-term, events flow past them. Systems: Esper, IBM Streams, Apama, TIBCO StreamBase.

Stream Analytics

Aggregations over windows: rates, rolling averages, comparisons to previous intervals. Uses probabilistic algorithms: Bloom filters (set membership), HyperLogLog (cardinality), t-digest (percentiles). Systems: Storm, Spark Streaming, Flink, Samza, Kafka Streams, Google Cloud Dataflow.

Important: probabilistic algorithms are an optimization, not a necessity. Stream processing can be exact — don't assume approximation.

Materialized Views Maintenance

Stream of database changes → keep derived systems up to date. Unlike analytics, this needs a window that stretches back to the beginning of time (or log-compacted to full state). Samza and Kafka Streams support this via Kafka's log compaction.

Reasoning About Time

This is the hardest part of stream processing. Two kinds of time:

• Event time — the timestamp embedded in the event (when it happened). Used by batch jobs. Enables deterministic reprocessing.
• Processing time — the local system clock when the stream processor sees the event. Simple but breaks under lag.

Why processing time fails: queueing, network faults, restart, reprocessing of past events all create a gap between event time and processing time. Using processing time for windowing creates artifacts (Figure 11-7): a backlog replay looks like a traffic spike.

Window Types

Knowing When You're Ready

When do you declare a window complete? Events can arrive late (stragglers) due to buffering, network delays, or offline devices. Options:

1. Ignore stragglers — track drop rate, alert if significant.
2. Publish corrections — emit updated window values with retraction of prior output.
3. Watermarks — a special message says "no more events before timestamp T will arrive." Requires tracking minimum timestamp per producer.

Trusting Clocks

Device clocks are untrusted. Mitigation: log three timestamps — (1) event occurred (device clock), (2) event sent to server (device clock), (3) event received (server clock). Subtract (2) from (3) to estimate clock offset, apply to (1).

Stream Joins

Three types of stream joins, each with different state requirements:

Stream-Stream Join (Window Join)

Two activity event streams. Example: search events + click events for click-through rate. Maintain state: all search events in the last hour indexed by session ID, all click events in the last hour indexed by session ID. When a search event arrives, check for matching click. When a click arrives, check for matching search. Emit join results or "not clicked" expirations.

Challenge: events may arrive out of order (click before search). The window must be wide enough to accommodate delays. A session may last days.

Stream-Table Join (Stream Enrichment)

Activity events + database changelog. Example: enrich user activity with profile information. Load a local copy of the database (from CDC changelog) into the stream processor. For each activity event, look up in the local hash table. Keep the local copy up to date by consuming the profile changelog stream.

This is basically a broadcast hash join (Chapter 10) that runs continuously, with the "small" input kept up to date via CDC. The join window is conceptually infinite for the table side; no window for the stream side.

Table-Table Join (Materialized View Maintenance)

Two database changelogs. Example: Twitter home timeline cache. Streams: tweets (send/delete) + follows (follow/unfollow). The join maintains a materialized view of "SELECT ... FROM tweets JOIN follows ON ... GROUP BY follower_id."

Mathematically: if u and v are tables, then (u·v)' = u'·v + u·v' (the product rule from calculus). Changes to either input produce changes to the join result.

Time-Dependence of Joins

If state changes over time, which version do you join with? Example: tax rates change over time; invoices need the rate at the time of sale, not the current rate. If event ordering across streams is undetermined, the join becomes nondeterministic — rerunning the same job on the same input may produce different results.

In data warehouses this is a slowly changing dimension (SCD). Solution: versioned identifiers — every time the tax rate changes, it gets a new ID; invoices reference the ID at the time of sale. This makes joins deterministic but prevents log compaction (all versions must be retained).

Fault Tolerance

Batch processing's fault tolerance is easy: discard the output of failed tasks, retry. Stream processing can't do this because the stream never ends. Key techniques:

Microbatching (Spark Streaming)

Break the stream into small batches (~1 second). Each batch is processed like a miniature MapReduce job. If a batch fails, retry it. Implicitly provides a tumbling window equal to the batch size (by processing time, not event time).

Checkpointing (Flink)

Periodically save operator state to durable storage (HDFS). Barriers in the message stream trigger checkpoints without forcing a fixed window size. On crash, restart from the latest checkpoint.

Atomic Commit within the Framework

To prevent external side effects (database writes, downstream messages) from being applied twice on retry, the stream processing framework must atomically commit both the output and the consumer offset. Google Cloud Dataflow, VoltDB, and Kafka (KIP-98) implement this internally — unlike XA, they don't span heterogeneous systems.

Idempotence

Design operations so performing them twice has the same effect as once:

• Setting a key to a fixed value = naturally idempotent.
• Incrementing a counter = not idempotent.
• Make it idempotent: include the Kafka message offset in the write. Check if the offset has already been applied before updating.

Requires: deterministic processing, same-order replay (log-based broker), and fencing (to prevent zombie nodes). Idempotence can achieve exactly-once semantics with low overhead.

Rebuilding State After Failure

Stream processors maintain state for windows, joins, and aggregations. Recovery options:

• Remote replicated state — query a remote DB for each message (slow).
• Local state with periodic snapshots — Flink checkpoints to HDFS; Samza/Kafka Streams replicate state changes to a compacted Kafka topic.
• Rebuild from input streams — replay the input events for the lost window. Fast for short windows; for full DB replicas, use log compaction.

Summary

The key ideas of Chapter 11:

1. Stream processing = batch processing on unbounded data. Same patterns (map, filter, join, aggregate), but continuous and with time-aware windowing.
2. Two broker philosophies: JMS/AMQP (transient, message-level ack) vs log-based (durable, offset-based, replayable). Kafka-style logs enable derived data systems.
3. Databases produce streams. CDC turns a DB's write-ahead log into a consumable event stream. Event sourcing models the application itself as an append-only log of domain events.
4. State = accumulated stream. The changelog is the truth; the database is a cache. CQRS separates write-optimized logs from read-optimized views.
5. Time is the hard part. Event time ≠ processing time. Windows (tumbling, hopping, sliding, session) must handle stragglers, clock skew, and out-of-order events.
6. Three stream joins: stream-stream (windowed), stream-table (enrichment), table-table (materialized view maintenance). All require state.
7. Exactly-once is achievable via microbatching, checkpointing, atomic commit within the framework, or idempotent operations.

Quiz

Select the correct answer for each question.

Notes

Primary source: Kleppmann, M. (2017). Designing Data-Intensive Applications, Chapter 11: “Stream Processing.” O'Reilly Media.
Recommended supplements: Jay Kreps' "The Log: What Every Software Engineer Should Know" (the single best explanation of Kafka's design), the Dataflow Model paper (Akidau et al., VLDB 2015), the Flink checkpointing paper (Carbone et al., arXiv 2015), the Spark Streaming paper (Zaharia et al., HotCloud 2012), Pat Helland's "Immutability Changes Everything" (CIDR 2015), and the MillWheel paper (Akidau et al., VLDB 2013).

Ask follow-up questions to drill into: how Kafka achieves 2M writes/sec on 3 machines, the exact mechanism of Flink's checkpointing barriers, how watermarks work in practice, the Lambda Architecture debate (why Jay Kreps says it's obsolete), how CDC handles schema changes, the subtleties of exactly-once vs effectively-once semantics, or how CQRS and event sourcing play out in production.