4 ms·

Map Reduce seems very interesting, but every example I have seen explains it in terms of counting frequency of words in documents. I would love to have someone

by briffle 13y ago

Map Reduce seems very interesting, but every example I have seen explains it in terms of counting frequency of words in documents. I would love to have someone explain it with an actual business example. I can't think of many real world uses where counting the frequency of words would matter to most businesses. (besides maybe some analysis of log files)

svachalek 13y ago
The earliest search engines could be described as pretty much exactly this map-reduce.
bretthoerner 13y ago
Here's a tiny twist on WordCount that many, many companies use MR for (often their first foot in the water): you have many gigabytes or terabytes of web access logs and need to bill customers via some API scheme like /api/3001?x=1&y=2 where "3001" there is the customer ID. You add some regex and now you're doing "WordCount" on the customer ID (per day, month, etc).
pacala 13y ago
You can implement SQL on top of MapReduce.
agibsonccc 13y ago
Let's use a simple data mining example with logs. You want to count the number of users by region visiting your website to understand where your users are coming from. In your log files you have the IP which you can use to geolocate those users. These counts can be caluclated in parallel. We do this by first "mapping" each line in a log file extracting out the IP. The output of map will be a geolocated hash by region. Reduce's goal is to calculate an answer based on these keys. If we think about the output of map being the geo location, we can then collect a count by geo located hash of where our users are coming from. Map: Map the raw input to some key value space Reduce: Reduce the output of the map to some aggregate result, think of this like the sql aggregation functions Hope that helps!
patrickmay 13y ago
I've used it for calculating Value at Risk on a portfolio consisting of thousands of books and millions of positions. With the books spread over a distributed, in-memory data grid of 20 or so nodes, the system sent a command object to each node to do the calculations in parallel in the same process context as the position data. The data was partitioned so that all positions for each book were in the same node. When the calculations were complete, the reduce process consolidated the results. VaR requires storing interim results to roll the calculation up the hierarchy of books, but that was straightforward with this approach. Any time you can parallelize the calculations, map-reduce is worth considering. Incidentally, the core idea (like all good software ideas) was present in Lisp decades before Google popularized it. The words map and reduce are even in the language.
yid 13y ago
Think of the SQL GROUP BY functionality as an example. You have a giant terabyte-scale text file that is a CSV of observations (say the raw US census results). You want to group people by some facet (say zipcode and household income) and compute some complex, arbitrary function for each group. Your map function scans the rows and outputs the kv pair (zipcode+","+income, csv line). All the csv lines in a group go to the same instance of the reduce function, where you can run any code you like (compute averages, do deep learning, etc). The output is the results of what you want to compute for each group. This is a pretty simple example, but does demonstrate where the power of mr comes from -- arbitrary functions in the map and reduce functions that are allowed restricted one-way communication from the mapper to the reducer. It also should help you understand the glib "you can implement SQL on mapreduce" comment below, which is what Apache Hive does.
estebank 13y ago
Think about it this way: you can't have 1 baby with 9 pregnant women in a month, but you can have 9 babies in 9 months with 9 pregnant women. In this analogy, the pregnant woman is the node and the baby is the processed data (of course). MapReduce is all about dividing tasks as small as they can be and then executing those tasks in parallel in several nodes. Most examples are of counting words because it's very straight forward to explain that you can give one page of a book to N people, have them count the words, and afterwards merge sort the sums into M counters and just sum it again.
alexatkeplar 13y ago
Part of the difficulty is that there are very few open source _applications_ (vs frameworks) built using MapReduce available to study. The only ones I know of are: https://github.com/snowplow/snowplow https://github.com/PredictionIO/PredictionIO We (Snowplow) use MapReduce primarily to: 1. Scale our event enrichment process horizontally - raw events come in, we validate them, enrich them (IP -> geo etc), store them. With MapReduce, we just throw more boxes at the enrichment process for larger users (we enrich 200m events in ~90 mins on 6 x c3.2xlarges, spot cost of $0.58) 2. Do easy recomputations across user's full history of raw events - e.g. we add a new enrichment or a user's business logic changes, we can rerun over their full history going back to 2012 Hope this helps!
OhHeyItsE 13y ago
I agree. I hate this example. Not sure why it's so ubiquitous. Think of like this: Each record in your dataset goes through the "map" phase. This is really just a categorization. You look at each record and assign it, or some parts of it, a "key" based on what it contains, and send those KV pairs back out into the ether. The framework will then automatically group those by key and send them, in no guaranteed order and in parallel, to your "reduce" phase. You get a key, and a list of all of those data points that were assigned that key. You do some computation on them, and return the result. When all of this is done, the process is complete. I think what makes this example so confusing (as well as the other common hadoop example where you do a partial count in the mapper "hello":3, "goodbye":2) is that the keys mean nothing to the final result (unless you really wanted to know the frequency of each word) - they are only used to shard the work. Sorry I don't have a real-world example (crunching log files as you mentioned is a common one, but it's really just the same thing: counting frequencies)
dirkgently 13y ago
A very simple (or simplified) example could be - say you have just one table - a transaction table from a local deli shop with a volume of around 500 transactions / day, and all you are doing with it is producing a report of how many items of each type (sugar/salt/bread) is sold. Say, you produced this report on daily, monthly and yearly basis. You decided to use, say, just a spreadsheet, which is sufficient to store this data, as well as running the calculation using pivot tables. This works for a year. The shop is now more popular, and a bit bigger too. The volume increases to say 2000 transactions a day, and you say, well, let's use mysql to store this. You are still comfortably generating the report at the end of the year using simple sql queries. Now suddenly, they decide go really big, to expand and open more stores across the city or state, say about 500 stores. They also expand the items in the stores from just few hundreds to few thousands. They project the transactions across all stores to be in the range of 1,000,000, on average containing about 10 items in each. They also want more reports on which products are doing good/bad, what are the buying habits, what's the trend over Thanksgiving, do year-to-year comparisons on various matrix. And the mysql solution no longer works - storing 10,000,000 rows on daily basis and running those sql queries is turning out to be practically impossible. In a year, you now have 3,650,000,000 rows that needs to be joined with 100,000 items. Yes, you can add more space and more resources to the machine, but running all those queries are now taking hours or days instead of seconds. This is the point where Hadoop/Map-Reduce comes to rescue. You now have a cluster of, say, 5 machines, each having, say, 64G or RAM and 1 PB of storage, but still costing just around 25000$. Since you are not familiar with Java or Map - Reduce, and/or don't have time to learn it, you decide to use Hive - an important tool of the Hadoop ecosystem among others - that still let's you access and process the data in the familiar sql query way - but generating map-reduce jobs on your behalf on the nodes. They split the processing across different nodes, bring required outputs together, may run through other map-reduce jobs if required, and ultimately, give you the results that you can use produce those reports - in a reasonable time, of course. This is very simplified but real-life business use case.
zenbowman 13y ago
Here you go, I wrote this a little while ago: http://tech.hulu.com/blog/2014/04/10/beaconspec/ http://tech.hulu.com/blog/2014/04/10/beaconspec/ The first part covers MapReduce, the rest you can skip.
jasode 13y ago
>I can't think of many real world uses where counting the frequency of words would matter to most businesses. The idea is that it's the simple "hello world" of teaching mapreduce. Likewise for teaching new programming language syntax, the idea of literally displaying the phrase "hello world" is not useful for explaining more real world business uses. Since everybody presumably already knows what "hello world" means, they can ignore that string and instead, pay attention to the surrounding syntax (printf, WriteLine, println, puts, echo, etc) of whatever new programming language they're trying to learn. Since counting words is very easy to do without mapreduce (using dictionaries or associative arrays) and it also doesn't require any particular business domain knowledge, people can ignore it and just concentrate on the structure of setting up mapreduce. In that context, the "uselessness" of counting word frequencies makes it easier to isolate the learning of mapreduce.
mimighost 13y ago
In realworld, people barely use "MapReduce", they use a high-level wrapper, that provides a more friendly user interface similar to SQL, like Hive, and to a lesser extent, Pig.
gengstrand 13y ago
I could not agree more. That is why I published an introductory example of map reduce that is still simple enough for educational purposes yet of a more real world nature. glennengstrand.info/analytics/oss Here you will see a blog, paper, and github repo of some map reduce jobs that take openly available San Francisco crime data and load it into an OLAP cube.

by briffle 13y ago

svachalek 13y ago

The earliest search engines could be described as pretty much exactly this map-reduce.

bretthoerner 13y ago

Here's a tiny twist on WordCount that many, many companies use MR for (often their first foot in the water): you have many gigabytes or terabytes of web access logs and need to bill customers via some API scheme like /api/3001?x=1&y=2 where "3001" there is the customer ID. You add some regex and now you're doing "WordCount" on the customer ID (per day, month, etc).

pacala 13y ago

You can implement SQL on top of MapReduce.

agibsonccc 13y ago

Let's use a simple data mining example with logs. You want to count the number of users by region visiting your website to understand where your users are coming from. In your log files you have the IP which you can use to geolocate those users. These counts can be caluclated in parallel. We do this by first "mapping" each line in a log file extracting out the IP. The output of map will be a geolocated hash by region. Reduce's goal is to calculate an answer based on these keys. If we think about the output of map being the geo location, we can then collect a count by geo located hash of where our users are coming from. Map: Map the raw input to some key value space Reduce: Reduce the output of the map to some aggregate result, think of this like the sql aggregation functions Hope that helps!

patrickmay 13y ago

I've used it for calculating Value at Risk on a portfolio consisting of thousands of books and millions of positions. With the books spread over a distributed, in-memory data grid of 20 or so nodes, the system sent a command object to each node to do the calculations in parallel in the same process context as the position data. The data was partitioned so that all positions for each book were in the same node. When the calculations were complete, the reduce process consolidated the results. VaR requires storing interim results to roll the calculation up the hierarchy of books, but that was straightforward with this approach. Any time you can parallelize the calculations, map-reduce is worth considering. Incidentally, the core idea (like all good software ideas) was present in Lisp decades before Google popularized it. The words map and reduce are even in the language.

yid 13y ago

Think of the SQL GROUP BY functionality as an example. You have a giant terabyte-scale text file that is a CSV of observations (say the raw US census results). You want to group people by some facet (say zipcode and household income) and compute some complex, arbitrary function for each group. Your map function scans the rows and outputs the kv pair (zipcode+","+income, csv line). All the csv lines in a group go to the same instance of the reduce function, where you can run any code you like (compute averages, do deep learning, etc). The output is the results of what you want to compute for each group. This is a pretty simple example, but does demonstrate where the power of mr comes from -- arbitrary functions in the map and reduce functions that are allowed restricted one-way communication from the mapper to the reducer. It also should help you understand the glib "you can implement SQL on mapreduce" comment below, which is what Apache Hive does.

estebank 13y ago

Think about it this way: you can't have 1 baby with 9 pregnant women in a month, but you can have 9 babies in 9 months with 9 pregnant women. In this analogy, the pregnant woman is the node and the baby is the processed data (of course). MapReduce is all about dividing tasks as small as they can be and then executing those tasks in parallel in several nodes. Most examples are of counting words because it's very straight forward to explain that you can give one page of a book to N people, have them count the words, and afterwards merge sort the sums into M counters and just sum it again.

alexatkeplar 13y ago

Part of the difficulty is that there are very few open source _applications_ (vs frameworks) built using MapReduce available to study. The only ones I know of are: https://github.com/snowplow/snowplow https://github.com/PredictionIO/PredictionIO We (Snowplow) use MapReduce primarily to: 1. Scale our event enrichment process horizontally - raw events come in, we validate them, enrich them (IP -> geo etc), store them. With MapReduce, we just throw more boxes at the enrichment process for larger users (we enrich 200m events in ~90 mins on 6 x c3.2xlarges, spot cost of $0.58) 2. Do easy recomputations across user's full history of raw events - e.g. we add a new enrichment or a user's business logic changes, we can rerun over their full history going back to 2012 Hope this helps!

OhHeyItsE 13y ago

I agree. I hate this example. Not sure why it's so ubiquitous. Think of like this: Each record in your dataset goes through the "map" phase. This is really just a categorization. You look at each record and assign it, or some parts of it, a "key" based on what it contains, and send those KV pairs back out into the ether. The framework will then automatically group those by key and send them, in no guaranteed order and in parallel, to your "reduce" phase. You get a key, and a list of all of those data points that were assigned that key. You do some computation on them, and return the result. When all of this is done, the process is complete. I think what makes this example so confusing (as well as the other common hadoop example where you do a partial count in the mapper "hello":3, "goodbye":2) is that the keys mean nothing to the final result (unless you really wanted to know the frequency of each word) - they are only used to shard the work. Sorry I don't have a real-world example (crunching log files as you mentioned is a common one, but it's really just the same thing: counting frequencies)

dirkgently 13y ago

A very simple (or simplified) example could be - say you have just one table - a transaction table from a local deli shop with a volume of around 500 transactions / day, and all you are doing with it is producing a report of how many items of each type (sugar/salt/bread) is sold. Say, you produced this report on daily, monthly and yearly basis. You decided to use, say, just a spreadsheet, which is sufficient to store this data, as well as running the calculation using pivot tables. This works for a year. The shop is now more popular, and a bit bigger too. The volume increases to say 2000 transactions a day, and you say, well, let's use mysql to store this. You are still comfortably generating the report at the end of the year using simple sql queries. Now suddenly, they decide go really big, to expand and open more stores across the city or state, say about 500 stores. They also expand the items in the stores from just few hundreds to few thousands. They project the transactions across all stores to be in the range of 1,000,000, on average containing about 10 items in each. They also want more reports on which products are doing good/bad, what are the buying habits, what's the trend over Thanksgiving, do year-to-year comparisons on various matrix. And the mysql solution no longer works - storing 10,000,000 rows on daily basis and running those sql queries is turning out to be practically impossible. In a year, you now have 3,650,000,000 rows that needs to be joined with 100,000 items. Yes, you can add more space and more resources to the machine, but running all those queries are now taking hours or days instead of seconds. This is the point where Hadoop/Map-Reduce comes to rescue. You now have a cluster of, say, 5 machines, each having, say, 64G or RAM and 1 PB of storage, but still costing just around 25000$. Since you are not familiar with Java or Map - Reduce, and/or don't have time to learn it, you decide to use Hive - an important tool of the Hadoop ecosystem among others - that still let's you access and process the data in the familiar sql query way - but generating map-reduce jobs on your behalf on the nodes. They split the processing across different nodes, bring required outputs together, may run through other map-reduce jobs if required, and ultimately, give you the results that you can use produce those reports - in a reasonable time, of course. This is very simplified but real-life business use case.

zenbowman 13y ago

Here you go, I wrote this a little while ago: http://tech.hulu.com/blog/2014/04/10/beaconspec/ http://tech.hulu.com/blog/2014/04/10/beaconspec/ The first part covers MapReduce, the rest you can skip.

jasode 13y ago

>I can't think of many real world uses where counting the frequency of words would matter to most businesses. The idea is that it's the simple "hello world" of teaching mapreduce. Likewise for teaching new programming language syntax, the idea of literally displaying the phrase "hello world" is not useful for explaining more real world business uses. Since everybody presumably already knows what "hello world" means, they can ignore that string and instead, pay attention to the surrounding syntax (printf, WriteLine, println, puts, echo, etc) of whatever new programming language they're trying to learn. Since counting words is very easy to do without mapreduce (using dictionaries or associative arrays) and it also doesn't require any particular business domain knowledge, people can ignore it and just concentrate on the structure of setting up mapreduce. In that context, the "uselessness" of counting word frequencies makes it easier to isolate the learning of mapreduce.

mimighost 13y ago

In realworld, people barely use "MapReduce", they use a high-level wrapper, that provides a more friendly user interface similar to SQL, like Hive, and to a lesser extent, Pig.

gengstrand 13y ago

I could not agree more. That is why I published an introductory example of map reduce that is still simple enough for educational purposes yet of a more real world nature. glennengstrand.info/analytics/oss Here you will see a blog, paper, and github repo of some map reduce jobs that take openly available San Francisco crime data and load it into an OLAP cube.