, I’ll give a quick introduction to the MapReduce programming mannequin. Hopefully after studying this, you permit with a strong instinct of what MapReduce is, the function it performs in scalable knowledge processing, and the right way to acknowledge when it may be utilized to optimize a computational activity.
Contents:
Terminology & Helpful Background:
Beneath are some phrases/ideas that could be helpful to know earlier than studying the remainder of this text.
What’s MapReduce?
Launched by a few builders at Google within the early 2000s, MapReduce is a programming mannequin that permits large-scale knowledge processing to be carried out in a parallel and distributed method throughout a compute cluster consisting of many commodity machines.
The MapReduce programming mannequin is right for optimizing compute duties that may be damaged down into unbiased transformations on distinct partitions of the enter knowledge. These transformations are sometimes adopted by grouped aggregation.
The programming mannequin breaks up the computation into the next two primitives:
- Map: given a partition of the enter knowledge to course of, parse the enter knowledge for every of its particular person data. For every file, apply some user-defined knowledge transformation to extract a set of intermediate key-value pairs.
- Scale back: for every distinct key within the set of intermediate key-value pairs, mixture the values in some method to provide a smaller set of key-value pairs. Sometimes, the output of the scale back part is a single key-value pair for every distinct key.
On this MapReduce framework, computation is distributed amongst a compute cluster of N machines with homogenous commodity {hardware}, the place N could also be within the a whole lot or hundreds, in apply. One in every of these machines is designated because the grasp, and all the opposite machines are designated as employees.
- Grasp: handles activity scheduling by assigning map and scale back duties to out there employees.
- Employee: deal with the map and scale back duties it’s assigned by the grasp.
Every of the duties inside the map or scale back part could also be executed in a parallel and distributed method throughout the out there employees within the compute cluster. Nevertheless, the map and scale back phases are executed sequentially — that’s, all map duties should full earlier than kicking off the scale back part.
That every one most likely sounds fairly summary, so let’s undergo some motivation and a concrete instance of how the MapReduce framework might be utilized to optimize widespread knowledge processing duties.
Motivation & Easy Instance
The MapReduce programming mannequin is usually finest for giant batch processing duties that require executing unbiased knowledge transformations on distinct teams of the enter knowledge, the place every group is usually recognized by a singular worth of a keyed attribute.
You’ll be able to consider this framework as an extension to the split-apply-combine sample within the context of information evaluation, the place map encapsulates the split-apply logic and scale back corresponds with the mix. The important distinction is that MapReduce might be utilized to attain parallel and distributed implementations for generic computational duties exterior of information wrangling and statistical computing.
One of many motivating knowledge processing duties that impressed Google to create the MapReduce framework was to construct indexes for its search engine.
We are able to specific this activity as a MapReduce job utilizing the next logic:
- Divide the corpus to go looking by way of into separate partitions/paperwork.
- Outline a map() perform to use to every doc of the corpus, which can emit <phrase, documentID> pairs for each phrase that’s parsed within the partition.
- For every distinct key within the set of intermediate <phrase, documentID> pairs produced by the mappers, apply a user-defined scale back() perform that can mix the doc IDs related to every phrase to provide <phrase, listing(documentIDs)> pairs.
For added examples of information processing duties that match properly with the MapReduce framework, take a look at the unique paper.
MapReduce Walkthrough
There are quite a few different nice sources that walkthrough how the MapReduce algorithm works. Nevertheless, I don’t really feel that this text can be full with out one. In fact, consult with the unique paper for the “supply of reality” of how the algorithm works.
First, some primary configuration is required to organize for execution of a MapReduce job.
- Implement map() and scale back() to deal with the info transformation and aggregation logic particular to the computational activity.
- Configure the block measurement of the enter partition handed to every map activity. The MapReduce library will then set up the variety of map duties accordingly, M, that will probably be created and executed.
- Configure the variety of scale back duties, R, that will probably be executed. Moreover, the person might specify a deterministic partitioning perform to specify how key-value pairs are assigned to partitions. In apply, this partitioning perform is usually a hash of the important thing (i.e. hash(key) mod R).
- Sometimes, it’s fascinating to have superb activity granularity. In different phrases, M and R needs to be a lot bigger than the variety of machines within the compute cluster. For the reason that grasp node in a MapReduce cluster assigns duties to employees based mostly on availability, partitioning the processing workload into many duties decreases the probabilities that any single employee node will probably be overloaded.
As soon as the required configuration steps are accomplished, the MapReduce job might be executed. The execution technique of a MapReduce job might be damaged down into the next steps:
- Partition the enter knowledge into M partitions, the place every partition is related to a map employee.
- Every map employee applies the user-defined map() perform to its partition of the info. The execution of every of those map() features on every map employee could also be carried out in parallel. The map() perform will parse the enter data from its knowledge partition and extract all key-value pairs from every enter file.
- The map employee will kind these key-value pairs in rising key order. Optionally, if there are a number of key-value pairs for a single key, the values for the important thing could also be mixed right into a single key-value pair, if desired.
- These key-value pairs are then written to R separate recordsdata saved on the native disk of the employee. Every file corresponds to a single scale back activity. The places of those recordsdata are registered with the grasp.
- When all of the map duties have completed, the grasp notifies the reducer employees the places of the intermediate recordsdata related to the scale back activity.
- Every scale back activity makes use of distant process calls to learn the intermediate recordsdata related to the duty saved on the native disks of the mapper employees.
- The scale back activity then iterates over every of the keys within the intermediate output, after which applies the user-defined scale back() perform to every distinct key within the intermediate output, together with its related set of values.
- As soon as all of the scale back employees have accomplished, the grasp employee notifies the person program that the MapReduce job is full. The output of the MapReduce job will probably be out there within the R output recordsdata saved within the distributed file system. The customers might entry these recordsdata straight, or move them as enter recordsdata to a different MapReduce job for additional processing.
Expressing a MapReduce Job in Code
Now let’s take a look at how we are able to use the MapReduce framework to optimize a standard knowledge engineering workload— cleansing/standardizing giant quantities of uncooked knowledge, or the remodel stage of a typical ETL workflow.
Suppose that we’re accountable for managing knowledge associated to a person registration system. Our knowledge schema might comprise the next data:
- Identify of person
- Date they joined
- State of residence
- E mail deal with
A pattern dump of uncooked knowledge might appear like this:
John Doe , 04/09/25, il, [email protected]
jane SMITH, 2025/04/08, CA, [email protected]
JOHN DOE, 2025-04-09, IL, [email protected]
Mary Jane, 09-04-2025, Ny, [email protected]
Alice Walker, 2025.04.07, tx, [email protected]
Bob Stone , 04/08/2025, CA, [email protected]
BOB STONE , 2025/04/08, CA, [email protected]Earlier than making this knowledge accessible for evaluation, we most likely need to remodel the info to a clear, customary format.
We’ll need to repair the next:
- Names and states have inconsistent case.
- Dates range in format.
- Some fields comprise redundant whitespace.
- There are duplicate entries for sure customers (ex: John Doe, Bob Stone).
We might want the ultimate output to appear like this.
alice walker,2025-04-07,TX,[email protected]
bob stone,2025-04-08,CA,[email protected]
jane smith,2025-04-08,CA,[email protected]
john doe,2025-09-04,IL,[email protected]
mary jane,2025-09-04,NY,[email protected]The information transformations we need to perform are simple, and we might write a easy program that parses the uncooked knowledge and applies the specified transformation steps to every particular person line in a serial method. Nevertheless, if we’re coping with tens of millions or billions of data, this method could also be fairly time consuming.
As an alternative, we are able to use the MapReduce mannequin to use our knowledge transformations to distinct partitions of the uncooked knowledge, after which “mixture” these reworked outputs by discarding any duplicate entries that seem within the intermediate outcome.
There are lots of libraries/frameworks out there for expressing packages as MapReduce jobs. For our instance, we’ll use the mrjob library to precise our knowledge transformation program as a MapReduce job in python.
mrjob simplifies the method of writing MapReduce because the developer merely wants to offer implementations for the mapper and reducer logic in a single python class. Though it’s now not below energetic growth and should not obtain the identical stage of efficiency as different choices that permit deployment of jobs on Hadoop (as its a python wrapper across the Hadoop API), it’s an effective way for anyone aware of python to start out studying the right way to write MapReduce jobs and recognizing the right way to break up computation into map and scale back duties.
Utilizing mrjob, we are able to write a easy MapReduce job by subclassing the MRJob class and overriding the mapper() and reducer() strategies.
Our mapper() will comprise the info transformation/cleansing logic we need to apply to every file of enter:
- Standardize names and states to lowercase and uppercase, respectively.
- Standardize dates to %Y-%m-%d format.
- Strip pointless whitespace round fields.
After making use of these knowledge transformations to every file, it’s doable that we might find yourself with duplicate entries for some customers. Our reducer() implementation will get rid of such duplicate entries that seem.
from mrjob.job import MRJob
from mrjob.step import MRStep
from datetime import datetime
import csv
import re
class UserDataCleaner(MRJob):
def mapper(self, _, line):
"""
Given a file of enter knowledge (i.e. a line of csv enter),
parse the file for <Identify, (Date, State, E mail)> pairs and emit them.
If this perform isn't applied,
by default, <None, line> will probably be emitted.
"""
strive:
row = subsequent(csv.reader([line])) # returns row contents as an inventory of strings ("," delimited by default)
# if row contents do not observe schema, do not extract KV pairs
if len(row) != 4:
return
identify, date_str, state, e-mail = row
# clear knowledge
identify = re.sub(r's+', ' ', identify).strip().decrease() # substitute 2+ whitespaces with a single area, then strip main/trailing whitespace
state = state.strip().higher()
e-mail = e-mail.strip().decrease()
date = self.normalize_date(date_str)
# emit cleaned KV pair
if identify and date and state and e-mail:
yield identify, (date, state, e-mail)
besides:
move # skip unhealthy data
def reducer(self, key, values):
"""
Given a Identify and an iterator of (Date, State, E mail) values related to that key,
return a set of (Date, State, E mail) values for that Identify.
It will get rid of all duplicate <Identify, (Date, State, E mail)> entries.
"""
seen = set()
for worth in values:
worth = tuple(worth)
if worth not in seen:
seen.add(worth)
yield key, worth
def normalize_date(self, date_str):
codecs = ["%Y-%m-%d", "%m-%d-%Y", "%d-%m-%Y", "%d/%m/%y", "%m/%d/%Y", "%Y/%m/%d", "%Y.%m.%d"]
for fmt in codecs:
strive:
return datetime.strptime(date_str.strip(), fmt).strftime("%Y-%m-%d")
besides ValueError:
proceed
return ""
if __name__ == '__main__':
UserDataCleaner.run()This is only one instance of a easy knowledge transformation activity that may be expressed utilizing the mrjob framework. For extra complicated data-processing duties that can not be expressed with a single MapReduce job, mrjob helps this by permitting builders to jot down a number of mapper() and producer() strategies, and outline a pipeline of mapper/producer steps that outcome within the desired output.
By default, mrjob executes your job in a single course of, as this permits for pleasant growth, testing, and debugging. In fact, mrjob helps the execution of MapReduce jobs on numerous platforms (Hadoop, Google Dataproc, Amazon EMR). It’s good to bear in mind that the overhead of preliminary cluster setup might be pretty vital (~5+ min, relying on the platform and numerous components), however when executing MapReduce jobs on really giant datasets (10+ GB), job deployment on certainly one of these platforms would save vital quantities of time because the preliminary setup overhead can be pretty small relative to the execution time on a single machine.
Try the mrjob documentation if you wish to discover its capabilities additional 🙂
MapReduce: Contributions & Present State
MapReduce was a big contribution to the event of scalable, data-intensive functions primarily for the next two causes:
- The authors acknowledged that primitive operations originating from useful programming, map and scale back, might be pipelined collectively to perform many Huge Information duties.
- It abstracted away the difficulties that include executing these operations on a distributed system.
Mapreduce was not vital as a result of it launched new primitive ideas. Fairly, MapReduce was so influential as a result of it encapsulated these map and scale back primitives right into a single library, which robotically dealt with challenges that come from managing distributed techniques, akin to activity scheduling and fault tolerance. These abstractions allowed builders with little distributed programming expertise to jot down parallel packages effectively.
There have been opponents from the database neighborhood who have been skeptical in regards to the novelty of the MapReduce framework — previous to MapReduce, there was present analysis on parallel database techniques investigating the right way to allow parallel and distributed execution of analytical SQL queries. Nevertheless, MapReduce is usually built-in with a distributed file system with no necessities to impose a schema on the info, and it gives builders the liberty to implement customized knowledge processing logic (ex: machine studying workloads, picture processing, community evaluation) in map() and scale back() that could be unattainable to precise by way of SQL queries alone. These traits allow MapReduce to orchestrate parallel and distributed execution of normal goal packages, as an alternative of being restricted to declarative SQL queries.
All that being stated, the MapReduce framework is now not the go-to mannequin for many fashionable large-scale knowledge processing duties.
It has been criticized for its considerably restrictive nature of requiring computations to be translated into map and scale back phases, and requiring intermediate knowledge to be materialized earlier than transmitting it between mappers and reducers. Materializing intermediate outcomes might end in I/O bottlenecks, as all mappers should full their processing earlier than the scale back part begins. Moreover, complicated knowledge processing duties might require many MapReduce jobs to be chained collectively and executed sequentially.
Trendy frameworks, akin to Apache Spark, have prolonged upon the unique MapReduce design by choosing a extra versatile DAG execution mannequin. This DAG execution mannequin permits all the sequence of transformations to be optimized, in order that dependencies between phases might be acknowledged and exploited to execute knowledge transformations in reminiscence and pipeline intermediate outcomes, when acceptable.
Nevertheless, MapReduce has had a big affect on fashionable knowledge processing frameworks (Apache Spark, Flink, Google Cloud Dataflow) attributable to basic distributed programming ideas that it launched, akin to locality-aware scheduling, fault tolerance by re-execution, and scalability.
Wrap Up
If you happen to made it this far, thanks for studying! There was loads of content material right here, so let’s shortly flesh out what we mentioned.
- MapReduce is a programming mannequin used to orchestrate the parallel and distributed execution of packages throughout a big compute cluster of commodity {hardware}. Builders can write parallel packages utilizing the MapReduce framework by merely defining the mapper and reducer logic particular for his or her activity.
- Duties that encompass making use of transformations on unbiased partitions of the info adopted by grouped aggregation are splendid suits to be optimized by MapReduce.
- We walked by way of the right way to specific a standard knowledge engineering workload as a MapReduce activity utilizing the MRJob library.
- MapReduce because it was initially designed is now not used for contemporary massive knowledge duties, however its core elements have performed a signifcant function within the design of recent distributed programming frameworks.
If there are any vital particulars in regards to the MapReduce framework which are lacking or deserve extra consideration right here, I’d love to listen to it within the feedback. Moreover, I did my finest to incorporate all the nice sources that I learn whereas writing this text, and I extremely advocate checking them out in the event you’re all for studying additional!
The creator has created all photos on this article.
Sources
MapReduce Fundamentals:
mrjob:
Associated Background:
MapReduce Limitations & Extensions: