Lecture
MapReduce is an approach to processing data that has two serious advantages over traditional solutions. The first and most important advantage is performance. In theory, MapReduce can be parallelized, which lets you process huge volumes of data across many cores/processors/machines. As already mentioned, this isn't yet an advantage of MongoDB. The second advantage of MapReduce is the ability to describe data processing with ordinary code. Compared to what you can do with SQL, the code inside MapReduce is far more powerful and lets you push the boundaries of what's possible even without specialized solutions.
First, let's clarify once again the meaning of the fundamental functions of the computational model :
To process data according to the MapReduce computational model, you need to define both of these functions and specify the names of the input and output files, as well as the processing parameters.
The computational model itself consists of a three-step combination of the functions above :
How MapReduce works
MapReduce is a pattern that is rapidly gaining popularity and can already be used almost anywhere; implementations already exist for C#, Ruby, Java, and Python. I should warn you that at first it may seem very unfamiliar and complicated. Don't get discouraged — take your time and experiment with it yourself. It's worth it, whether or not you use MongoDB.
MapReduce is a two-stage process. First comes map (map), then — reduce (reduce). At the map stage, the input documents are transformed (map) and emit (emit) key=>value pairs (both the key and the value can be composite). At reduce (reduce), the input is a key and an array of values produced for that key, and the output is the final result. Let's look at both stages and their output data.
In our example, we'll generate a report on the daily number of hits for some resource (for example, a web page). This is the hello world of MapReduce. For our purposes, we'll use the hits collection with two fields: resource and date. The result we want is a report broken down by resource, year, month, day, and count.
Suppose hits contains the following data:
resource date index Jan 20 2010 4:30 index Jan 20 2010 5:30 about Jan 20 2010 6:00 index Jan 20 2010 7:00 about Jan 21 2010 8:00 about Jan 21 2010 8:30 index Jan 21 2010 8:30 about Jan 21 2010 9:00 index Jan 21 2010 9:30 index Jan 22 2010 5:00
On the output side, we want the following result:
resource year month day count index 2010 1 20 3 about 2010 1 20 1 about 2010 1 21 3 index 2010 1 21 2 index 2010 1 22 1
(The beauty of this approach lies in how the results are stored; reports are generated quickly and data growth is kept under control – for a single resource, at most one document will be added per day.)
Let's now focus on understanding the concept. At the end of the chapter, sample data and code will be provided.
First, let's look at the map function. The job of the map function is to emit values that will later be used during reduce. Values can be emitted zero or more times. In our case – as is most often true – this will always be done once. Imagine that map loops over each document in the hits collection. For each document, we need to emit a key made up of the resource, year, month, and day, and a primitive value – one:
function() {
var key = {
resource: this.resource,
year: this.date.getFullYear(),
month: this.date.getMonth(),
day: this.date.getDate()
};
emit(key, {count: 1});
}
this refers to the document currently being examined. Hopefully the resulting data will make what's happening clearer. Using our test data, we get:
{resource: 'index', year: 2010, month: 0, day: 20} => [{count: 1}, {count: 1}, {count:1}]
{resource: 'about', year: 2010, month: 0, day: 20} => [{count: 1}]
{resource: 'about', year: 2010, month: 0, day: 21} => [{count: 1}, {count: 1}, {count:1}]
{resource: 'index', year: 2010, month: 0, day: 21} => [{count: 1}, {count: 1}]
{resource: 'index', year: 2010, month: 0, day: 22} => [{count: 1}]
Understanding this intermediate stage is the key to understanding MapReduce. The emitted data is collected into arrays grouped by identical key. .NET and Java developers can think of this as a type of IDictionary>(.NET) or HashMap (Java).
Let's change our map function in a somewhat contrived way:
function() {
var key = {resource: this.resource, year: this.date.getFullYear(), month: this.date.getMonth(), day: this.date.getDate()};
if (this.resource == 'index' && this.date.getHours() == 4) {
emit(key, {count: 5});
} else { emit(key, {count: 1}); }
}
The first intermediate result now changes to:
{resource: 'index', year: 2010, month: 0, day: 20} => [{count: 5}, {count: 1}, {count:1}]
Notice how each emit produces a new value, which is grouped by key.
The reduce function takes each of these intermediate values and produces the final result. Here's what our function looks like:
function(key, values) {
var sum = 0;
values.forEach(function(value) {
sum += value['count'];
}); return {count: sum};
};
On the output we get:
{resource: 'index', year: 2010, month: 0, day: 20} => {count: 3}
{resource: 'about', year: 2010, month: 0, day: 20} => {count: 1}
{resource: 'about', year: 2010, month: 0, day: 21} => {count: 3}
{resource: 'index', year: 2010, month: 0, day: 21} => {count: 2}
{resource: 'index', year: 2010, month: 0, day: 22} => {count: 1}
In MongoDB, technically, the result looks like this:
_id: {resource: 'home', year: 2010, month: 0, day: 20}, value: {count: 3}
This is our final result.
If you were paying attention, you should be asking yourself: why didn't we just write sum = values.length? That would be an efficient approach if we were always summing an array of ones. In practice, reduce isn't always called with a complete and perfect set of intermediate data. For example, instead of being called with:
{resource: 'home', year: 2010, month: 0, day: 20} => [{count: 1}, {count: 1}, {count:1}]
Reduce may be called with:
{resource: 'home', year: 2010, month: 0, day: 20} => [{count: 1}, {count: 1}]
{resource: 'home', year: 2010, month: 0, day: 20} => [{count: 2}, {count: 1}]
The final result is the same (3), but it's arrived at via slightly different paths. This means reduce must always be idempotent. In other words, calling reduce multiple times should give us the same result as calling it once.
We won't cover it here, but it's common practice to chain reduces together when a more complex analysis is needed.
With MongoDB, we call the mapReduce. mapReduce command on a collection. It takes a map function, a reduce function, and directives for the result. In the console we can create and pass JavaScript functions directly. From most libraries you'll be passing a string representation of the function (which can look a bit ugly). First, let's create a data set:
db.hits.insert({resource: 'index', date: new Date(2010, 0, 20, 4, 30)});
db.hits.insert({resource: 'index', date: new Date(2010, 0, 20, 5, 30)});
db.hits.insert({resource: 'about', date: new Date(2010, 0, 20, 6, 0)});
db.hits.insert({resource: 'index', date: new Date(2010, 0, 20, 7, 0)});
db.hits.insert({resource: 'about', date: new Date(2010, 0, 21, 8, 0)});
db.hits.insert({resource: 'about', date: new Date(2010, 0, 21, 8, 30)});
db.hits.insert({resource: 'index', date: new Date(2010, 0, 21, 8, 30)});
db.hits.insert({resource: 'about', date: new Date(2010, 0, 21, 9, 0)});
db.hits.insert({resource: 'index', date: new Date(2010, 0, 21, 9, 30)});
db.hits.insert({resource: 'index', date: new Date(2010, 0, 22, 5, 0)});
Now we can create the map and reduce functions (the MongoDB console lets you enter multi-line constructs):
var map = function() {
var key = {resource: this.resource, year: this.date.getFullYear(), month: this.date.getMonth(), day: this.date.getDate()};
emit(key, {count: 1});
};
var reduce = function(key, values) {
var sum = 0;
values.forEach(function(value) {
sum += value['count'];
});
return {count: sum};
};
We'll run the mapReduce command on the hits collection as follows:
db.hits.mapReduce(map, reduce, {out: {inline:1}})
If you run the code above, you'll see the expected result. By setting out to inline, we tell mapReduce to return the result directly to the console. Right now the result size is limited to 16 megabytes. Instead, we could write {out: 'hit_stats'}, and the result would be saved to the hit_stats collection:
db.hits.mapReduce(map, reduce, {out: 'hit_stats'});
db.hit_stats.find();
In that case, all existing data in the hit_stats collection would first be deleted. If we wrote {out: {merge: 'hit_stats'}}, existing values for matching keys would be replaced with the new ones, while others would be inserted. And finally, for more complex cases you can use out with a reduce function.
The third parameter accepts additional values – for example, you can sort, filter, or limit the data being analyzed. We can also pass a finalize method, which is applied to the result returned by the reduce stage.
This is the first chapter in which we've covered a topic completely new to you. If you're feeling uncomfortable, you can always turn to other aggregation tools and simpler scenarios. Still, MapReduce is one of the most important features of MongoDB. To learn to write map and reduce functions, you need a clear picture of what your data looks like and how it's transformed on its way through map and reduce.
Comments