By

## Algorithm Monday: The Wonder of Map/Reduce

======☆

Map/Reduce, when first encountering it, sounds scary. It’s known to be one of the most powerful tools for organizations like Google and Amazon, but it seems strange for those used to SQL. Much like functional programming, it’s outward simplicitly masks it’s depth – often leading to very dense code.

# Learning Map/Reduce

This article will be a short introduction to map/reduce. By the end of it, I hope I can have you, the reader, thinking about ways map/reduce can benefit you. These examples are written in CouchDB, no prior experience with CouchDB is assumed.

## The Example

For xander.io – an automated multivariate testing platform, we use map/reduce to analyze data sent to us from browsing habits. It is a complicated thing, so I will create a more simplistic example to show the power of map/reduce.

## Color

Cerill was an awkward kid growing up. Throughout his life he hid behind books, acquiring knowledge as a form of escape. But year after year that awkwardness faded away. Eventually what was left was an extremely clever man, who was now well liked.

Cerill decided to capitalize on this. He formed a startup called Kolor. The startup was masquerading as a social network for people who liked colors. It was a ridiculous premise, but it bought him cover. What the investors and all 50 of his security-cleared employees knew was that he was creating a new type of color. This new color would allow a short subliminal message to be encoded within another color. The problem, however, is that this material had to be printed. It couldn’t just be a png image on the web, or a frame on the TV.

Once Cerill had a prototype working. He wrote two words into a bullseye sign. ‘Buy this’. He contacted the government, and the government set up an experiment with the local store. His bullseye sign would sit on top of a display case filled with a thoroughly retarded and unsellable item – a blanket with pre-made holes in it. Cerill knew that he needed to get this working, as this item would obviously not sell itself.

There was one problem though. He needed to know the most popular color. See, the trick would only work if the bullseye was a customer’s favorite color.

Every survey was transcribed by the rest of the staff, and a wonderful OCR reader, into CouchDB documents. Every survey was one document. They looked something like this:

``````
{
"favorite-color" : "red",
"gender" : "male",
"zipcode" : "80203"
}
``````

Cerill had to find the most popular color among a million of these.

## Installation

For this example we will be using CouchDB. The good news is that this is available as a completely hosted service. You can get a free account with cloudant here.

For this example, we will be using our local installation of CouchDB.

## Check installation

Couch is built for the web. We will use curl for all of our examples.
`curl http://localhost:5984`

Result
`{"couchdb":"Welcome","version":"1.2.0"}`

## Create our database

List all of the databases.
`curl http://localhost:5984/_all_dbs`

Create the database
`curl http://localhost:5984/colors -X PUT`

List the new database
`curl http://localhost:5984/_all_dbs`

## Inserting Colors

We will insert favorite colors at random to simulate survey data using bash and curl.

``````
colors=(red green blue lavender)
for i in {0..999}
do
color=\${colors[\$((\$RANDOM % \${#colors[@]}+1))]}
curl -X PUT http://localhost:5984/colors/\$i -d '{"favorite-color" : "'\$color'"}'
done
``````

So now if we look in CouchDB we see lots of information:

`curl http://localhost:5984/colors/_all_docs\?include_docs\=true\&limit\=10`

## Map/Reduce

### Understanding Map

Map is a method with the following signature:

`function(doc) {}`

It will run exactly once for each document in the document store. It expects no return value.

It has one method which you need to worry about:

`emit(key, value);`

This means any one document could map to anywhere from 0 to many emit statements. But what does an emit statement do?

Emit just means that we have an index associated with some data. What does this mean? Let me show you.

``````
function(doc) {
if(doc['favorite-color']) emit(doc['favorite-color'], 1);
}
``````

Can you guess what this does? If you guessed ‘emits the value 1 using color as the index’ you were correct.

Our records will look like this:

## Reduce

So, what do you do with all those emit statements? Easy! You can reduce the information into something useful.

### Understanding Reduce

Reduce is a more complex method. It takes three arguments and returns a useful value.

``````
function(key, values, rereduce) {
return null;
}
``````

key is the index you’ve created. In this case it’s the favorite color for the survey taker.

values is an array containing all the values with the same key. In this example it would be [1,1,...].

rereduce is a boolean flag signifying if reduce is taking it’s return value in it’s list of values. It is not useful in this example.

A reduce function is expected to return a value. In our example, we want to sum our values together.

### The Color Reduce

This takes all those emits, and gives us a mapping of “favorite-color” : “number of people”.

``````
function(key, values, rereduce) {
var sum = 0;
values.forEach(function(value){
sum+=value;
});
return sum;
}
``````

## Putting it together

### The Design Document

Great! That’s a lot to soak in without seeing it run. So lets get it running.

Let’s turn this into a design document. Design documents in CouchDB hold map/reduce functions, called ‘views’ among other things. In fact it’s completely possible to build an app entirely in a design document. But that is out of the scope of this article.

### Our Design Document

Like other Couch documents, design documents are written in JSON. Create this file and save it to colors.json

``````
{
"id" : "design/colors",
"views" : {
"count" : {
"map" : "function(doc) {
if(doc['favorite-color']) emit(doc['favorite-color'], 1);
}",
"reduce" : "function(key, values, rereduce) {
var sum = 0;
values.forEach(function(value){
sum+=value;
});
return sum;
}"
}
}
}
``````

### Add Design Document To Couch

`curl -X PUT http://localhost:5984/colors/_design/colors -d @colors.json`

### Query our design

You can view your map/reduce in the shell or the browser.
`curl http://localhost:5984/colors/_design/colors/_view/count\?group_level\=1`
You can see this in action with futon (couchdb’s built-in UI):
http://localhost:5984/utils/database.html?colors/design/colors/_view/count

Make sure you click the reduce button (top right) to see the effect of the reduction.

## Epilogue

Cerill’s subliminal messaging experiment didn’t work. Turns out, the human mind is more resilient than Cerill had estimated. In desperation Cerill turned to alcoholism. He had money. Investors had yet to find out the results. Cerill packed his bags and went to Hawaii for two months. His employees were worried. As were his investors. He had no plans to return.

That is, until he met Stan.

Stan was a tall man with piercing eyes, almost as if he could see into you. Stan told Cerill, I have a way you can get out of this. Cerill, not believing him, said “I don’t believe you”. Stan replied “I bet on your soul I can sell them in a week”.

Stan had a secret. He knew there was a market for fat and lazy in America. He had seen it on the streets when he lived in San Antonio. Additionally, Stan was the antichrist. He once put his hands on a person’s head, and sucked the soul right out of the person’s body. It was like drinking milk, he later remarked.

And the rest is history. Stan sold all the blankets and got Cerills soul. Some say if you listen closely to an infomercial at night, you can still hear Cerill’s scream.