Welcome to another article on Batch Processing. We have already discussed a brief overview of a typical batch processing workflow, its major components and the problems we face when dealing with such distributed batch processes.
As always, the cover image is hand - sketched by me, head to the end of the article for a little note behind it.
In this article, we are going to discuss typical Batch Processing models. The most important among them is MapReduce.
MapReduce
MapReduce has largely been replaced by dataflow engines (another batch processing framework/model), but it is important to understand, as it is a core influence behind all batch processing frameworks. We will surely discuss such use cases/modern frameworks in future articles. But for now, let's stick to MapReduce.
We will understand the MapReduce algorithm using the given figure.
The problem here is to count the occurrences of each letter in a doc (as in the figure). The input data (the document) is very large and contains a large amount of data that cannot be processed serially, or, if processed serially, will make fault handling difficult and result in super high latency.
MapReduce follows this simple algorithm:
- The set of inputs (files/docs) is split into records. We see 3 splits in the above figure. In the case of distributed MapReduce, these splits are stored in distributed filesystems like HDFS, or even in object stores like S3. Various file formats can be used. The most common one is Apache Parquet. At my current organisation, where we deal with huge workflows and batch processing, we have our native file format.
- The mapper then extracts the key and value from each input and leaves the value empty or sets it to a default. Here, the key is the letter and the value is its frequency. The default value of the frequency is 1. This step is called Mapping.
- All the keys are then sorted by key. In the figure above, the 3rd column shows the net output after steps 2 and 3. Keys are sorted and values are kept at their defaults.
- Now, the Reducer function is used to iterate over the sorted key-value pairs. Since identical keys are kept adjacent to each other, combining the values (here, frequencies) is now very easy. The net frequency of each letter is calculated in each HDFS file/partition. Then, the reducer can easily combine the output into net frequencies, as the keys are adjacent and sorted. The 4th column in the figure is the output of the Reducer.
If you are clear on the algorithm, we can easily infer that there are 2 major functions in MapReduce - the Mapper and the Reducer.
Mapper and Reducer
The Mapper is called once for each input record (3 records in the picture). The job of the Mapper is to extract the key and value of the record (the value is either empty, set to a default or, in some cases, given). It does not keep any state from one input record to the next, and we can observe in the above example that each input record is independently handled. So, many mappers can be run in parallel.
The key-value pairs produced by the Mapper are passed to the reducer function. The reducer collects the values and combines them by iterating over the collection. The output is then produced by the reducers. We can observe again that reducers can also be run in parallel.
Some of you can now also relate this to the map and reduce functions in programming languages such as JavaScript and Rust. The core idea is the same. They have now become mainstream in modern programming languages as well.
The independent behaviour of mappers and reducers ensures that the data (input) remains in an immutable state. So, parallel execution can make processing fast. Also, in the case of failure, these can be rerun without affecting the output, as the input is the same.
Why is MapReduce getting replaced?
Even SQL engines can be built on top of MapReduce. But complex jobs like join algorithms, AOU calls, etc., are very laborious to implement. Also, modern batch processing engines are quite fast compared to MapReduce. Another reason is that file I/O operations prevent job pipelining. In simple words, processing output data in a downstream job is prevented before the upstream job is complete.
DataFlow Engines
The MapReduce problems are fixed by several new dataflow engines. The most well-known are Spark and Flink. One common thing in these modern engines is that they handle an entire workflow as one job rather than breaking it into independent subjobs (as we do in MapReduce).
Low-level operations like API calls and user-defined function calls are supported in these engines. Higher-level operations like JOIN and GROUPBY are also offered. Parallelization here is achieved by sharding inputs and then copying the output of one task over the network to become the input of another. There need not be alternating layers of mappers and reducers here. The arrangement of tasks is flexible.
The modern dataflow APIs generally use relational-style building blocks to perform computations like joining, grouping by, filtering or aggregating. These high-level operations are implemented using shuffle algorithms that we will discuss in the next article.
So, these processing engines are based on the following principles:
Avoid expensive operations wherever we can. Operations like sorting should only be done whenever required, unlike in MapReduce, where we always perform them.
If there are several operators in a row, we need not shard the data again or change anything in the sharding. In MapReduce, for map or filter operations, we need to shard-map-reduce-combine again for each operation. So, here, the data copying overhead is removed.
In these dataflow engines, the entire workflow is explicitly declared with all operators. The scheduler already has an overview of what data is required where, so it can make locality optimizations. For example, tasks that utilize the same data can be run on the same host/machine where the data was produced. Network copying overhead is saved.
The intermediate state between operators is usually kept in memory or written to a local disk rather than to a distributed filesystem or object store. These I/O operations are less expensive, as distributed ones involve network overhead, replication, etc. This optimization was also utilized in MapReduce for mapper output. But in dataflow engines, the idea is generalized to all intermediate state.
The operations here start as soon as their input is ready. There is no waiting for the entire preceding stage to finish before the next one starts.
Existing running processes can be reused to run new operators. This saves startup overhead compared to MapReduce, where a new JVM is launched for each task.
Usually, workflows in dataflow engines are faster than the same workflows implemented in MapReduce due to all the optimizations discussed above.
Fortunately, I work in a team where we have our native workflow engine, and we deal with a lot of the problems faced in distributed batch processing.
Conclusion
MapReduce lays the foundation for understanding batch processing, while modern dataflow engines build on these ideas to execute workflows more efficiently.
In the next article, we will discuss the algorithms behind the high-level operations of dataflow engines and explore batch processing use cases. Stay tuned!
Not an interesting fact: The cover image is sketched by me, remembering 19 November 2023 - a day that still hurts. A tribute to Virat, Rohit and a team that made us believe until the very end. Some campaigns deserve a happier ending.

Top comments (1)
The hand-sketched cover suits a series like this. Sorting only when you have to is the rule that does the most work in that list.