Spark and Storm: after MapReduce (Lambda and Kappa architectures)

01 · CONTEXT

What MapReduce left unanswered

In the cluster analytics frameworks of the RDD paper's era, such as MapReduce, reusing data between two computations had a high cost: in most of them, the only way was to write the result to an external stable storage system, such as a distributed file system. That path brings replication, disk I/O and serialization overhead.

Spark was born from this limitation. The paper that introduces it starts from two classes of application that the frameworks of the time handled inefficiently: iterative algorithms and interactive data mining tools. Spark's answer to these two classes is the starting point of this case, which continues through to stream processing.

02 · RDDS AND LINEAGE

In-memory data without paying for replicas

1. To reuse data between two computations, most frameworks of the time required writing it to external stable storage.

2. With RDDs, the user can explicitly ask for intermediate results to stay persisted in memory.

3. If a partition of an RDD is lost, the RDD has enough information about how it was derived from other RDDs to recompute only that partition.

4. Fault tolerance comes from recording the transformations used to build the dataset, the lineage, instead of the data itself.

The trick is in the interface. RDDs offer coarse-grained transformations, such as map, filter and join, which apply the same operation to many items. In fine-grained state update interfaces, the only ways to tolerate failures are to replicate the data across machines or to log the updates across machines.

03 · MICRO-BATCH STREAMING

Spark Streaming: the stream becomes a sequence of batches

The RDD paper itself points to the path of periodic batch processing: applications that update a result with new data, such as ad click statistics every 15 minutes, combining the state of the previous window with the new logs. The systems of this kind cited in the paper keep application state in distributed file systems, and the next step, in this case, is to see how Spark Streaming handles this flow in data pipelines.

1. Spark Streaming receives live data streams, from sources such as Kafka and Kinesis, and divides them into batches.

2. Each batch is processed by the Spark engine, and the stream of results also comes out in batches.

3. To avoid losing data already received, Spark introduced write-ahead logs; with them and with reliable receivers there is no data loss, and the semantics are at-least-once.

4. For end-to-end exactly-once, every processing stage needs to offer that guarantee, including delivery to the destination.

04 · STORM

Topologies that run forever

1. In Storm, the application logic is a topology: a graph of spouts and bolts connected by stream groupings, which runs forever, unlike a MapReduce job.

2. The stream is an unbounded sequence of tuples, processed and created in parallel in a distributed way.

3. A tuple that left the spout is considered fully processed when the tuple tree has been exhausted and all the messages in the tree have been processed.

4. If the tree is not fully processed and the tuple times out, Storm calls the fail method on the spout; with anchored tuples, the root tuple is re-emitted.

05 · PROCESSING SEMANTICS

Exactly once, but where?

In the Spark Streaming documentation, the processing of any stream has, broadly, three stages. In the transformation stage, all received data is processed exactly once, thanks to the RDD guarantees, as long as the received input data remains accessible. In reception, each input source offers different guarantees, and so the end-to-end guarantee depends on all the stages.

In Storm, the page on processing guarantees describes the at-least-once level based on the tuple tree, the timeout that generates failure and the re-emission of the root tuple.

06 · LAMBDA ARCHITECTURE

Two layers for fast, correctable queries

1. Events arrive at a master dataset of immutable data, which only receives appends.

2. The batch layer precomputes queries over the whole dataset, the easiest way to make them fast.

3. Data older than a few hours is already in the batch views; the real-time layer precomputes queries only for the last few hours.

4. To respond, the service queries the batch view and the real-time view and merges the results.

5. An error in the real-time layer is corrected by the batch layer, which ends up overwriting what the real-time layer computed.

The same design provides a path for correction. If a query has a bug, just fix it, deploy the fixed version and recompute everything from the master dataset; and, since the data is immutable and the dataset only receives appends, writing bad data does not overwrite or destroy good data.

07 · CURRENCY

What has changed since then

The current Spark documentation describes Spark Streaming (DStreams) as the previous generation of Spark's streaming engine.