Stream Processing

Fullscreen

A stream is data made incrementally available over time. An event is a small, self-contained, immutable object describing something that happened at a point in time (with a timestamp). It's generated once by a producer (publisher) and processed by multiple consumers (subscribers); related events form a topic / stream. Polling a datastore for new events is expensive at low latency, so consumers should be notified, which is what messaging systems provide (database triggers are too limited).

---

Transmitting Event Streams

Messaging systems

A pub/sub messaging system pushes producer messages to consumers. Two defining questions:

Fullscreen

• Direct messaging (no broker): UDP multicast (stock feeds), brokerless libraries (ZeroMQ, nanomsg), StatsD over UDP, webhooks (HTTP/RPC callbacks). Works, but the app must tolerate message loss and assumes producers/consumers are constantly online.
• Message brokers (message queues): a database optimized for message streams. Centralizing in the broker tolerates clients coming and going; durability moves to the broker; consumers are asynchronous (the producer waits only for the broker to buffer, not for processing).

Brokers vs databases: brokers often delete a message after delivery (not for long-term storage), assume a small working set (short queues), support topic subscriptions rather than rich queries, and notify on new data rather than returning a point-in-time snapshot. Standards: JMS, AMQP (RabbitMQ, ActiveMQ, IBM MQ, Azure Service Bus, Google Cloud Pub/Sub).

Multiple consumers, acknowledgments, redelivery

Fullscreen

Consumers send acknowledgments; an unacked message (consumer crashed, or ack lost) is redelivered. Combined with load balancing, redelivery can reorder messages (m3 redelivered after m4). A poison message that always crashes its consumer loops forever, handled by moving it to a dead letter queue (DLQ) for monitoring/manual fixing.

Log-based message brokers

A hybrid combining database durability with messaging's low-latency notification: store messages in an append-only log.

Fullscreen

Apache Kafka, Amazon Kinesis work this way (millions of msg/s via sharding + replication). Compared to traditional messaging: fan-out is trivial; load balancing is coarse (a partition goes to one consumer, so parallelism ≤ number of partitions, and a slow message causes head-of-line blocking). Route messages needing a fixed order to the same partition (partition key = user ID). Consumer offsets are like a replication log sequence number (broker = leader, consumer = follower); a failed consumer resumes from the last recorded offset (so some messages may be seen twice). Disk space: the log is split into segments; old ones are deleted (a disk-backed circular buffer, a 20TB disk buffers ~22 hours at full write rate, often days in practice). Modern brokers add tiered/object storage (Kafka, Redpanda, WarpStream), often as Iceberg tables. A slow consumer falling past the retained window misses messages, but only that consumer is affected, so you can safely consume production logs for testing. Replaying old messages (rewind the offset) makes log-based messaging much like batch processing.

---

Databases and Streams

A replication log is a stream of write events; state machine replication (apply the same events in the same order → same state) is just an event stream. Every write to any database is an event that can be captured.

Keeping systems in sync, and CDC

The same data lives in many systems (DB, cache, search index, warehouse) that must stay in sync. Dual writes (the app writes each system itself) are broken:

Fullscreen

Change data capture (CDC) observes all changes to a database and emits them as a stream, making the source DB the leader and derived systems followers. Tools: Debezium, Maxwell, GoldenGate, Kafka Connect. CDC is usually asynchronous (so replication lag applies). Practical concerns: an initial snapshot (tied to a log offset) for systems needing a full copy; log compaction (retain only the latest value per key; tombstones mark deletes) so you can rebuild a derived system from offset 0 without a fresh snapshot. CDC vs event sourcing: CDC extracts low-level row changes from an existing mutable DB (easy to bolt on); event sourcing makes the app log high-level intent events as the system of record (bigger commitment; later events don't override earlier ones, so log compaction differs and snapshots are a read optimization). CDC turns the DB schema into a public API, decouple with the outbox pattern (a dedicated outbox table written in the same transaction).

State, streams, and immutability

Fullscreen

Mutable state is the result of a sequence of immutable events; state is the integral of the event stream, and the changelog is its derivative. "There is no fundamental need to keep a database at all; the log contains all the information" (Gray & Reuter). Advantages of immutable events: auditability (the accounting ledger never erases, it adds compensating entries), recovery from buggy code, and capturing more information (a cart add-then-remove still records intent). You can derive several views from one log and evolve schemas by running new views alongside old ones (CQRS), making the normalization debate moot. Concurrency control simplifies: a self-contained event is a single atomic append; a single-threaded per-shard consumer needs no write concurrency control. Limitations: high churn makes the immutable history huge; deletion for GDPR/privacy requires truly rewriting history (Datomic excision, Fossil shunning), hard because copies live everywhere, so crypto-shredding (encrypt, then forget the key) is used, though it only moves the problem to key management.

---

Processing Streams

Three things to do with a stream: (1) write it to storage (DB/cache/index), (2) push it to users (alerts, dashboards), or (3) process input streams into derived output streams. A stream processor is an operator/job (like a Unix process or MapReduce task), but the stream never ends, so sort-merge joins don't apply and fault tolerance must differ.

Uses of stream processing

• Complex event processing (CEP), search for patterns of events (like regex over a stream). The relationship is inverted: queries are stored long-term and each arriving event is checked against them (Esper, Flink/Spark SQL).
• Stream analytics, windowed aggregations and statistics (rates, rolling averages, percentiles). Often uses probabilistic algorithms (Bloom filters, HyperLogLog) as an optimization, not because streaming is inherently approximate (Storm, Spark Streaming, Flink, Samza, Beam, Kafka Streams).
• Maintaining materialized views, keep derived systems up-to-date; needs a window stretching back to the beginning of time. Incremental view maintenance (IVM) recomputes only what changed (Materialize, RisingWave, ClickHouse, Feldera), far more efficient than periodic full REFRESH.
• Search on streams, standing full-text queries matched against each document (Elasticsearch percolator).
• Event-driven architectures / actors are message-based but usually not stream processors (ephemeral one-to-one vs durable multi-subscriber; arbitrary cyclic vs acyclic pipelines).

Reasoning about time

Fullscreen

Event time vs processing time matters: windowing by processing time creates artifacts (a redeploy's backlog appears as a traffic spike). Ordering can be inconsistent (the Star Wars release-vs-narrative-order analogy). Stragglers arrive late; you either ignore them or emit a correction. With untrusted device clocks, log three timestamps (event time per device, send time per device, receive time per server) to estimate and correct the clock offset.

Window types:

Fullscreen

Stream joins

Fullscreen

All three maintain state derived from one input and query it for the other. Time dependence: if events across streams aren't ordered, the join is nondeterministic; data warehouses handle this as a slowly changing dimension (SCD), version the joined record (e.g., tax rate at time of sale), which prevents log compaction, or denormalize the value into the event.

Fault tolerance

The batch guarantee is exactly-once (really effectively-once) semantics: discard partial output of failed tasks. Streams can't wait until "finished," so finer-grained recovery is needed.

Fullscreen

• Microbatching (Spark Streaming, ~1s blocks) and checkpointing (Flink, barriers + durable snapshots) give exactly-once within the framework, but once output leaves it (DB write, email), a retry causes double side effects.
• Atomic commit revisited: keep transactions internal to the framework (Google Cloud Dataflow, VoltDB, Kafka), amortizing overhead across many messages, not heterogeneous XA.
• Idempotence: make repeated application harmless (e.g., store the triggering offset with each write; skip if already applied), requiring deterministic replay in order, no concurrent writers, and fencing on failover.
• Rebuilding state after failure: remote replicated store (slow per-message), or local state replicated periodically (Flink snapshots, Kafka Streams changelog topic with compaction, VoltDB redundant processing), or simply replayed from the input stream / log-compacted changelog.

---

Real-world examples and analogies

• Stream vs batch, a live broadcast vs a recorded box set. Batch is the box set: a complete, finite thing you process start to finish. A stream is the live broadcast: it never "ends," so you handle each moment as it airs and can never wait for the whole show.
• Polling vs notification, refreshing your inbox vs a push alert. Constantly hitting refresh (polling) wastes effort when nothing's new; a push notification (the broker) tells you the moment a message arrives.
• Load balancing vs fan-out, a shared task list vs a group announcement. Load balancing is a team task list where each item is grabbed by one person; fan-out is an all-hands announcement everyone hears independently.
• Log-based broker, a TV channel with DVR. Everyone tunes to the same channel and can rewind to any earlier point (replay by offset); old recordings eventually age off the DVR (segment deletion). A traditional broker is a one-time phone call, once heard, it's gone.
• Dual writes failure, two clerks updating two ledgers in different orders. Without a single authority deciding order, the two ledgers can end up permanently disagreeing. CDC appoints one ledger as the boss and has the other copy its entries in the same order.
• State = integral of events, a bank balance from a transaction history. Your balance isn't a primary fact; it's the sum of every deposit and withdrawal. The transaction log is the truth; the balance is just a fast-to-read derivative.
• Immutable ledger, accountants never erase. A mistaken charge isn't deleted; a compensating refund is added. The full history stays for audit, the same reason immutable event logs aid debugging and recovery.
• Event time vs processing time, the Star Wars saga. Episode numbers are event time; the dates you watched them are processing time. Watching them in release order scrambles the narrative, exactly the reordering a stream processor must handle.
• Straggler events, a postcard that arrives weeks late. You "closed the books" on July, then a July-dated postcard shows up in August. You either ignore it or reopen July's tally and correct it.
• Stream-table enrichment, a cashier with a local price list. Rather than phoning the head office for every item's price (slow remote lookup), the cashier keeps a local price list that head office keeps updated (CDC), fast joins without a round trip.
• Exactly-once via idempotence, a numbered delivery slip. If each delivery carries a unique slip number, the warehouse can check "already received slip 57?" and avoid logging it twice, even if the truck redelivers.

---

Cheat-sheet flashcards

Cover the answer and recall it.

• What is a stream? → Data made incrementally available over time (unbounded).
• What is an event? → A small, immutable, self-contained record of something at a point in time.
• Producer vs consumer vs topic? → Publisher / subscriber / a named group of related events.
• Why prefer notification over polling? → Polling is wasteful at low latency.
• Three responses to consumer overload? → Drop, buffer, or apply backpressure.
• Examples of direct (brokerless) messaging? → UDP multicast, ZeroMQ, StatsD, webhooks.
• What is a message broker? → A database optimized for message streams.
• How do brokers differ from databases? → Delete after delivery, small working set, subscriptions not queries, notify on change.
• Load balancing vs fan-out? → Each message to one consumer vs to all consumers.
• What are Kafka consumer groups? → Combine load balancing (within group) and fan-out (across groups).
• What is an acknowledgment, and what triggers redelivery? → Consumer confirms processing; missing ack → redeliver.
• Side effect of load balancing + redelivery? → Message reordering.
• What is a dead letter queue? → Where poison messages are moved to unblock consumers.
• What is a log-based message broker? → A broker storing messages in an append-only, sharded log (Kafka).
• What is an offset? → A monotonic per-partition sequence number; total order only within a partition.
• Log-based broker load-balancing limit? → Parallelism ≤ number of partitions; head-of-line blocking.
• What are consumer offsets analogous to? → A replication log sequence number.
• How does a log broker reclaim disk? → Segment deletion (a disk-backed circular buffer).
• Advantage of replaying old messages? → Reprocess with new code; experiment without disrupting others.
• Why are dual writes broken? → Race conditions and partial failures cause permanent inconsistency.
• What is change data capture? → Observing all DB changes and emitting them as an ordered stream.
• What does CDC make the source DB? → The single leader; derived systems become followers.
• A CDC tool? → Debezium (also Maxwell, GoldenGate, Kafka Connect).
• Why an initial snapshot in CDC? → A truncated log lacks un-updated records; need a full base.
• What is log compaction? → Retain only the latest value per key (tombstones mark deletes).
• CDC vs event sourcing? → Low-level row changes on a mutable DB vs high-level intent events as the system of record.
• What is the outbox pattern? → A dedicated table written in-transaction to decouple internal schema from CDC.
• State vs changelog mathematically? → State = integral of events; changelog = derivative of state.
• Three advantages of immutable events? → Auditability, recovery from bugs, richer captured information.
• What is CQRS here? → Deriving multiple read-optimized views from one write-optimized log.
• Why is immutability hard to keep forever? → Churn, and legal deletion (GDPR) requires rewriting history.
• What is crypto-shredding? → Encrypt deletable data, then forget the key.
• Three things you can do with a stream? → Store it, push it to users, or derive new streams.
• What is complex event processing? → Searching for event patterns with standing queries.
• Why do stream analytics use probabilistic algorithms? → Less memory; it's an optimization, not inherent inexactness.
• What is incremental view maintenance? → Recompute only changed data for a materialized view.
• Event time vs processing time? → When it happened vs when it was processed.
• What artifact does processing-time windowing cause? → A false spike when a backlog is processed.
• What is a straggler event? → One arriving after its window was declared complete.
• Four window types? → Tumbling, hopping, sliding, session.
• Three stream join types? → Stream-stream (window), stream-table (enrichment), table-table (materialized view).
• What is stream enrichment? → Joining activity events with a local DB copy kept fresh by CDC.
• What is a slowly changing dimension? → Versioning a joined record so the join is deterministic.
• Exactly-once vs effectively-once? → Same observable result despite retries (the more accurate term).
• Four stream fault-tolerance techniques? → Microbatching, checkpointing, atomic commit, idempotence.
• Why isn't checkpointing enough for external side effects? → A retry repeats the external effect (e.g., email).
• How is idempotence achieved with offsets? → Store the triggering offset; skip already-applied updates.

---

Common interview questions

1. How does stream processing differ from batch, and why does "unbounded" change everything? (Never finishes; no sort-merge join; different fault tolerance.)
2. Compare AMQP/JMS brokers with log-based brokers. (Delete-on-ack/per-message vs retained log/offsets; reordering vs replay; coarse load balancing.)
3. What are load balancing and fan-out, and how do Kafka consumer groups provide both? (One vs all consumers; within-group vs across-group.)
4. Why are dual writes unsafe, and how does CDC fix it? (Race/partial-failure inconsistency; single leader + ordered change stream.)
5. Contrast CDC and event sourcing. (Low-level row changes on a mutable DB vs high-level intent events as system of record.)
6. Explain log compaction and why it matters for rebuilding derived systems. (Keep latest per key; rebuild from offset 0 without a snapshot.)
7. Explain "state is the integral of an event stream" and the advantages of immutable events. (Changelog duality; auditability, recovery, richer info, CQRS.)
8. Event time vs processing time, what goes wrong and how do you handle stragglers? (False spikes; ignore or correct; three-timestamp clock correction.)
9. Describe the four window types. (Tumbling, hopping, sliding, session.)
10. Walk through the three stream join types. (Stream-stream window, stream-table enrichment, table-table materialized view.)
11. What is time-dependence/SCD in joins, and why does it cause nondeterminism? (Cross-stream ordering; version the joined record.)
12. How is exactly-once achieved in stream processing? (Microbatching/checkpointing within the framework; atomic commit or idempotence for external effects.)

---

Key terms glossary

---

Forward links (where these ideas return)

• Joining across multiple state shards; the broader philosophy of streaming systems → Chapter 13
• Timeliness vs integrity, decoupling, end-to-end correctness → Chapter 13
• Legal deletion, privacy, self-regulation → Chapter 14
• Batch processing, sort-merge joins, the filesystem analogy → Chapter 11
• Event sourcing and CQRS, change streams → Chapter 3
• Log-structured storage, write-ahead logs, log compaction → Chapter 4
• Replication logs, state machine replication, consensus, exactly-once/2PC → Chapters 6, 8, 10