Stream Processing : Episode 14

Distributed systems from scratch. This is episode 14 stream processing. Back in episode 2 we proved exactly once delivery is mathematically impossible. By the end of this episode you will know how Flink ships it anyway and why both statements are true at the same time. Last episode we studied distributed storage, how to organize data at rest on thousands of machines, B-trees, LSM trees, GFS, Bigtable. Today we shift from data at rest to data in motion. How do you process events as they arrive? Continuously, in real time, at scale. A user clicks, a sensor fires, a payment occurs. Each event needs to be processed immediately, not batched and handled hours later. This is stream processing. The traditional approach is batch processing. Collect events over some time period, an hour, a day, then process them all at once. MapReduce is the classic example. Input is finite, output is finite, and latency is measured in minutes or hours. Stream processing inverts this. Process each event as it arrives. The input stream is infinite. It never ends. The output is continuous. Latency is measured in milliseconds or seconds. Batch tells you what happened yesterday. Streaming tells you what's happening right now. Jay Krebs, one of the co-creators of Kafka at LinkedIn, wrote a famous essay called The Log. In it, he describes the log as the simplest possible storage abstraction. An append-only, totally ordered sequence of records ordered by time. This sounds trivial. But the distributed log turns out to be one of the most powerful abstractions in all of systems design. It decouples producers from consumers, it provides durability, it enables replay, and it scales horizontally through partitioning. Kafka is the log. Apache Kafka. Originally built at LinkedIn in 2010. Open sourced in 2011. Now the central nervous system of modern data infrastructure at thousands of companies a distributed partition and replicated commit log here's kafka's architecture producers write events to topics a topic is a named stream think orders clicks payments each topic is split into partitions partitions are the unit of parallelism just like the partitioning we learned in episode 9 a messages key determines which partition it goes to via hashing messages with the same key go to the same partition an order is guaranteed within a partition each partition is replicated across multiple brokers for fault tolerance just like replication from episode 8 one replica is the leader others are followers if the leader dies a follower takes over consumers read from partitions a consumer group is a set of consumers that cooperatively read from a topic. Each partition is assigned to exactly one consumer in the group. Add more consumers and the partitions are redistributed. This is how Kafka scales reads. Messages are retained for a configurable duration, days, weeks or forever. Consumers track their position using offsets. They can rewind to any offset and replay. Let me highlight the key concepts. A topic is like a database table but append only. You never update a record. You append a new one. Partitions enable parallelism. The number of partitions determines the maximum consumer parallelism. Add more consumers to a group than there are partitions and the extras just sit idle. Each partition is consumed by exactly one member of the group. Each message has an offset. A sequential ID. within its partition. Consumers commit offsets to track progress. If a consumer crashes and restarts, it resumes from its last committed offset. Consumer groups enable independent processing. Group A might be the analytics pipeline. Group B might be the alerting system. Both read the same data independently at their own pace. And retention decouple speed from durability. A slow consumer doesn't block a fast one. Data stays in Kafka until the retention period expires. This enables replay. You can reprocess last week's data just by resetting the offset. Before Kafka, if you had N systems that needed to share data, you'd build point-to-point connections between them. N systems meant N squared connections. Every new system meant integrating with every existing one. Fragile, unmaintainable. Kafka inverts this. Every system publishes to Kafka. Every system reads from Kafka and systems means two and connections. Each system just talks to Kafka. The log is the single source of truth. This is why Kafka is often called the central nervous system of data infrastructure. It's the communication backbone that everything else plugs into. Now let's talk about the hardest problem in stream processing, time. We thought we dealt with time in episode three, Lamport clocks. vector clocks the happens before relation but in streaming time comes back with a vengeance there are two notions of time in stream processing and confusing them causes real bugs event time is when the event actually happened the timestamp embedded in the event by the producer a user clicked a button at 1400 hours 0 minutes 1.234 seconds this is the ground truth Processing time is when the system processes the event. The wall clock time at the stream processor. The click arrives at 1400 hours, 0 minutes, 3.789 seconds, two and a half seconds late. Maybe there was network delay. Maybe it was buffered. The problem, events don't arrive in event time order. A click from 1400 hours might arrive after a click from 1401. If you process by arrival order, processing time your results are wrong but if you process by event time you need to handle events that arrive late here's the concrete problem you're computing count of clicks per minute the window for 1400 to 1401 closes you've counted the events emitted the result then an event arrives with event time 14 hours 45 seconds it belongs in the window that already closed What do you do? Drop it. Your count is wrong. Recompute. How long do you wait? You could wait forever. Some events might be hours late. But you need to produce results. You can't wait indefinitely. This is why we need watermarks. A watermark is the system's estimate of progress in event time. It says, I believe all events with event time less than or equal to w have arrived. Look at the timeline. Three events land inside the 1400 to 1401 window and notice they arrived out of order E3 showed up before E2 With event time that's fine. They all belong to the window Then the watermark the purple line passes 1401 the end of the window. That's the signal close the window emit the count three Done and then a4 arrives event time 1445 it belongs to a window that's already closed this is the late data decision update the result emit a correction downstream or drop it which brings us to the trade-off at the bottom a conservative watermark waits longer fewer late events delayed results billing accurate analytics and aggressive watermark advances fast quick results more efforts to handle dashboards monitoring The watermark is the fundamental mechanism that bridges event time and processing time. Windows are how you turn an unbounded stream into finite computations. Tumbling windows are fixed size and non-overlapping. Every 5 minutes, one bucket. Each event belongs to exactly one window. Count events per 5 minute bucket. Sliding windows are fixed size but overlapping. A 5 minute window that slides every 1 minute means an event can belong to up to 5 windows. Average over the last 5 minutes. Updated every minute. Session windows are gap based and per key. A user's session window stays open as long as events keep arriving. After 30 minutes of inactivity, the window closes. Window length varies per user. Total actions per user session. Kafka is the log. It stores and distributes events. But it doesn't process them in sophisticated ways. For that, you need a stream processing engine. Apache Flink. The most powerful stream processor available today. First class support for event time, stateful processing and exactly once semantics. Flink models computation as a data flow graph. Events flow from sources, typically Kafka topics. through a chain of operators to syncs, databases, other Kafka topics, file systems. Each operator can maintain local state. A windowed aggregation, for example, keeps running counts in a local rocks DB instance. This state is the operator's memory. It persists across events. The critical feature is checkpointing. Periodically. Flink takes a consistent snapshot of all operator states across the entire cluster and saves it to durable storage. S3 HDFS If any operator fails, Flink restores from the last checkpoint and replace events from Kafka starting at the checkpointed offset. This is how Flink achieves fault tolerance without losing state. And this brings us to the holy grail of stream processing, exactly once semantics. In episode two, the two generals problem, we proved that exactly once delivery is impossible over unreliable networks. So how can Flink claim to provide it? Flink uses a variant of the Chandi Lamport distributed snapshot algorithm. The coordinator periodically injects barrier markers into the source streams. These barriers flow through the data flow graph like regular events. They write the same channels. When an operator receives barriers from all of its input channels, it takes a snapshot of its local state and writes it to durable storage. Then it forwards the barrier downstream. When the sync receives the barrier, it commits its pending output to a database, to an output Kafka topic, whatever. If a failure occurs, Flink restores every operator state from the last completed checkpoint. It resets Kafka consumer offsets to the checkpoint position. Events between the checkpoint and the failure are replayed. The result, every event's effect appears exactly once in the output. Even if events are physically replayed during recovery, the restored state ensures the output is as if no failure occurred. The key distinction. Exactly once doesn't mean each event is processed exactly once. Under the hood, events might be processed multiple times during recovery. What it means is that the effect of each event appears exactly once in the output. At least once processing, combined with idempotent checkpointed state, produces exactly once results. This connects back to episode 2. True exactly once delivery is indeed impossible. but exactly once effect is achievable through the combination of at least once delivery state checkpointing and deterministic replay the two generals were right about delivery but they didn't account for state management two main options for stream processing today kafka streams is a library it runs inside your application process no separate cluster needed it only reads from kafka state is stored in local rocks tb It supports exactly once via Kafka transactions. Flink is a standalone cluster. It reads from Kafka, files, sockets and custom sources. State is checkpointed to remote storage. It supports exactly once via Chandi Lamport snapshots. Its event time support is more sophisticated. Kafka Streams is simpler. Great for Kafka-centric workloads that don't need complex event processing. Flink is more powerful. The choice for multi-source complex stateful processing. Real-world applications of stream processing. Fraud detection. Analyze payment events in real-time. Flag suspicious patterns within milliseconds before the transaction completes. Flink's stateful processing tracks per user spending patterns. Real-time analytics. Live dashboards showing clicks, revenue, error rates. windowed aggregations over the last 5, 15 and 60 minutes. Event sourcing. The Kafka log is the database. Every state change is recorded as an event. You can rebuild any services state by replaying its input topic from the beginning. Change data capture. Debezium captures every insert, update and delete from a database and streams them to Kafka. Downstream systems. Search indexes, caches, Stay in sync by consuming the change stream. Let me connect this to previous episodes. Kafka partitions are hash partitioning from episode 9. Messages keyed by user underscore id consistently hash to the same partition, giving per user ordering. Kafka replication uses in-sync replicas, essentially single leader replication from episode 8. The partition leader handles reads and writes. Followers replicate. Flink checkpointing is based on distributed snapshots. The same Chandy-Lamport algorithm that descends from the logical clocks lineage in episode 3 and exactly one semantics combined idempotency from episodes 2 and 10 with at least one's delivery and state checkpoints. The same building blocks composed for a new purpose. Let's recap. 1. Kafka is a distributed partitioned replicated commit log. It decouples producers from consumers and serves as the backbone of stream architecture. 2. Event time and processing time are different. Watermarks tell you when it's safe to close a window and emit results. 3. Flink achieves exactly once effects via Chandy-Lamport checkpoints combined with Kafka Offset Replay. Events may be processed multiple times. but the output is as if each was processed once. 4. Exactly once delivery is impossible, but exactly once effect is achievable through careful state management. 5. Window types, tumbling, sliding, session determine how you group unbounded streams into finite computations. Next episode, System Design Patterns, the season 3 finale. We take every protocol, every storage engine, every processing model we've learned and combine them into real system designs. URL shortener, chat system, distributed cache, from whiteboard to architecture. That's episode 14, stream processing, Kafka as the log, Flink as the brain, and the art of processing infinite data streams in real time. Next time, system design patterns.

Distributed Systems — from scratch.

This is Episode Fourteen: Stream Processing.

Back in Episode 2, we proved exactly-once delivery is mathematically impossible. By the end of this episode, you'll know how Flink ships it anyway — and why both statements are true at the same time.