labs/lab8/lab8_mapreduce.ipynb

{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Lab 8: MapReduce, mrjob, and EC2"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In this week's lab, we will mostly ignore statistics and instead focus on some practical issues that you will encouter on Homework 4. Section 4 of that homework includes new python techniques (classes, inheritance), an unfamiliar approach to breaking up large computing problems (MapReduce), code that has to be run outside the friendly confines of an ipython notebook, and then you are asked to put it all to use on Amazon's Elastic Compute Cloud (EC2). This sounds very complicated, but the end result is a simpler algorithm for that problem of calculating similarity scores, as well as the ability to expand to arbitrarily large data sets."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "1. Classes and generators in python"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "On previous homeworks, nearly all of the coding has been done by writing python functions plus a small amount of code that calls the functions you have written. Included below is the code for the mrjob word_count example that was covered in lecture (the canonical MapReduce example). There are a lot of new features here!\n",
      "\n",
      "Below is the code for a simple MapReduce algorithm to count the number of words in a text file. This is one of the simplest examples of a problem that can be solved using MapReduce (I even took it from the Section \"[Writing your first job](http://mrjob.readthedocs.org/en/latest/guides/quickstart.html#writing-your-first-job)\" in the mrjob documentation). If you try to run the cell in this notebook, it will not work! We will get to running programs with mrjob soon, but for now it will just serve as reference for some topics we want to cover."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "from mrjob.job import MRJob\n",
      "\n",
      "class MRWordFrequencyCount(MRJob):\n",
      "\n",
      "    def mapper(self, _, line):\n",
      "        yield \"chars\", len(line)\n",
      "        yield \"words\", len(line.split())\n",
      "        yield \"lines\", 1\n",
      "\n",
      "    def reducer(self, key, values):\n",
      "        yield key, sum(values)\n",
      "\n",
      "if __name__ == '__main__':\n",
      "    MRWordFrequencyCount.run()\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "1.1 Classes"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Classes are the basis of object-oriented programming in python. For all of the problems on previous homework assignments, we have written functions to do calculations, draw figures, etc. To use mrjob, we have to switch gears and use a different style of programming. \n",
      "\n",
      "As you can see in the example above, the <span style=\"font-family: monospace\">MRWordFrequencyCount</span> class is defined with an indented block similar to a function definition, except with <span style=\"font-family: monospace; color: green; font-weight: bold;\">class</span> instead of <span style=\"font-family: monospace; color: green; font-weight: bold;\">def</span>. Instead of a list of arguments, the item in parentheses (<span style=\"font-family: monospace;\">MRJob</span>) is a *base class* that our newly defined class will inherit most of its features from. Even though there is very little code written above for <span style=\"font-family: monospace\">MRWordFrequencyCount</span>, it knows how to do many complex operations (running a mapper and a reducer, submitting jobs to EC2, etc.) because it inherited these abilities from the base class.\n",
      "\n",
      "There are two methods, <span style=\"font-family: monospace\">mapper</span> and <span style=\"font-family: monospace\">reducer</span>, that have been written specifically for <span style=\"font-family: monospace\">MRWordFrequencyCount</span>. These methods are also defined for the <span style=\"font-family: monospace\">MRJob</span> base class, but the methods defined here supercede the inherted ones. A class method is similar to a function (as you might guess, since it is also defined with a <span style=\"font-family: monospace; color: green; font-weight: bold;\">def</span> statement), but the first argument to a class method will always be <span style=\"font-family: monospace\">self</span>, a reference back to the object to which the method belongs. The always-present <span style=\"font-family: monospace\">self</span> argument allows the method to access other members of the same object (both data and methods). However, when you actually call a class method, you don't have to supply anything for the <span style=\"font-family: monospace\">self</span> argument -- it is implicit. For example, to call the <span style=\"font-family: monospace;\">reducer</span> method defined above, you would use:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Call reducer method of MRWordFrequencyCount object using some key and values.\n",
      "MRWordFrequencyCount.reducer(my_key, my_values) # Did not specify 'self' argument"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The next mrjob example -- [Writing your second job](http://mrjob.readthedocs.org/en/latest/guides/quickstart.html#writing-your-second-job) -- processes text to find the most commonly used word. That algorithm involves two MapReduce steps, so it is necessary to write a <span style=\"font-family: monospace;\">MRMostUsedWord.steps</span> method to override the inherited method. Notice that the <span style=\"font-family: monospace;\">self</span> is used repeatedly to specify the function references inside the list returned by the <span style=\"font-family: monospace;\">steps</span> method."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import re\n",
      "\n",
      "WORD_RE = re.compile(r\"[\\w']+\")\n",
      "\n",
      "\n",
      "class MRMostUsedWord(MRJob):\n",
      "\n",
      "    def mapper_get_words(self, _, line):\n",
      "        # yield each word in the line\n",
      "        for word in WORD_RE.findall(line):\n",
      "            yield (word.lower(), 1)\n",
      "\n",
      "    def combiner_count_words(self, word, counts):\n",
      "        # optimization: sum the words we've seen so far\n",
      "        yield (word, sum(counts))\n",
      "\n",
      "    def reducer_count_words(self, word, counts):\n",
      "        # send all (num_occurrences, word) pairs to the same reducer.\n",
      "        # num_occurrences is so we can easily use Python's max() function.\n",
      "        yield None, (sum(counts), word)\n",
      "\n",
      "    # discard the key; it is just None\n",
      "    def reducer_find_max_word(self, _, word_count_pairs):\n",
      "        # each item of word_count_pairs is (count, word),\n",
      "        # so yielding one results in key=counts, value=word\n",
      "        yield max(word_count_pairs)\n",
      "\n",
      "    def steps(self):\n",
      "        return [\n",
      "            self.mr(mapper=self.mapper_get_words,\n",
      "                    combiner=self.combiner_count_words,\n",
      "                    reducer=self.reducer_count_words),\n",
      "            self.mr(reducer=self.reducer_find_max_word)\n",
      "        ]\n",
      "\n",
      "\n",
      "if __name__ == '__main__':\n",
      "    MRMostUsedWord.run()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "[More about classes in python](http://docs.python.org/2/tutorial/classes.html#)"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "1.2 Generators"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Generators are necessary to understand all of those <span style=\"font-family: monospace; font-weight: bold; color: green;\">yield</span> statements popping up in the mapper and reducer methods. The main issue, in the case of industrial-strength MapReduce, is that you don't have enough memory to store all of your data at once. This is true even after you have split your data between many compute nodes. So instead of getting an enormous list of data, the mapper and reducer functions both receive and emit generators.\n",
      "\n",
      "When you run a function, it chugs along until it hits a <span style=\"font-family: monospace; font-weight: bold; color: green;\">return</span> statement, at which point it returns some results and then it is done. A generator does its specified calculations until it hits a <span style=\"font-family: monospace; font-weight: bold; color: green;\">yield</span> statement. It passes along whatever values it was supposed to yield and then it *pauses* and waits for someone to tell it to continue. It continues until it reaches another <span style=\"font-family: monospace; font-weight: bold; color: green;\">yield</span>, and so on.\n",
      "\n",
      "Not only are mapper and reducer generators, their (key, value) inputs are also generators. This means that for each step of the mapper, it pulls in one (key, value) pair, does some processing, and then emits one or more key value pairs, which move along to a combiner or a shuffler or whatever. This is how MapReduce avoids ever having to load huge datasets into limited memory.\n",
      "\n",
      "A common stumbling block with generators is the fact that once you have iterated through an entire generator, it is done. You can see an example of this mistake by trying to run the code block below."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# This function converts a list into a generator.\n",
      "def example_generator(list):\n",
      "    for item in list:\n",
      "        yield item\n",
      "        \n",
      "# Create a generator.\n",
      "my_generator = example_generator([0, 1, 2, 3, 4])\n",
      "\n",
      "# Iterating over the generator works great the first time.\n",
      "print \"generator iteration 1\"\n",
      "print \"---------------------\"\n",
      "for value in my_generator:\n",
      "    print value\n",
      "    \n",
      "# ...but it doesn't work the second time.\n",
      "print \"\\n\"\n",
      "print \"generator iteration 2\"\n",
      "print \"---------------------\"\n",
      "for value in my_generator:\n",
      "    print value"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "1.3 What does <span style=\"font-family: monospace;\">\\_\\_name\\_\\_ <span style=\"color: violet;\">==</span> <span style=\"color: red;\">'\\_\\_main\\_\\_'</span></span> mean??"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Python is *really* into namespaces (see, for example, [The Zen of Python](http://www.python.org/dev/peps/pep-0020/)). The <span style=\"font-family: monospace;\">\\_\\_name\\_\\_</span> keyword tells you what namespace it is in. For example, if we <span style=\"font-family: monospace;\"><span style=\"font-weight: bold; color: green;\">import</span> numpy</span>, then all of the numpy features are in the numpy namespace."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy as np\n",
      "print np.__name__\n",
      "\n",
      "import matplotlib.pyplot as plt\n",
      "print plt.__name__"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "If you try to import the above file containing the definition for <span style=\"font-family: monospace;\">MRMostUsedWord</span>, then python will interpret the file all the way down until it hits that last <span style=\"font-family: monospace; font-weight: bold; color: green;\">if</span> statement. <span style=\"font-family: monospace;\">\\_\\_name\\_\\_</span> will evaluate to <span style=\"font-family: monospace;\">MRMostUsedWord</span> (or whatever the name was of the file we imported) and the line inside the if statement will be ignored. On the other hand, if you run this code from the command line, python will interpret it *without* importing it and <tt>\\_\\_name\\_\\_</tt> will be the python top level namespace, which is <tt><span color=\"red\">'\\_\\_main\\_\\_'</span></tt>, so <tt>MRMostUsedWord.run()</tt> gets called.\n",
      "\n",
      "In (many) fewer words: it tells you to run the job only when invoked from the command line.\n",
      "\n",
      "Try copying the code for MRMostUsedWord to a file, named <tt>MRMostUsedWord.py</tt>, and then running it on any old text file you might have lying around. The invokation will be somthing like this (modify based on your particular python installation):"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "python MRMostUsedWord.py some_file.txt > most_used_word.out"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "2. Setting up your Amazon Web Services account"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "There is quite a bit of overhead involved in setting up an AWS account and keeping an eye on the jobs that you end up running. In lab, we will run through an example account activation including:\n",
      "\n",
      "* Account creation\n",
      "* Signing up for Elastic MapReduce\n",
      "* Storing security credentials in your mrjob.conf file\n",
      "* Redeeming account credits\n",
      "* Billing alerts\n",
      "* Checking on running jobs using the console\n",
      "\n",
      "These documents (also linked from HW4) are very useful: [Instructions for Amazon Setup notebook](http://nbviewer.ipython.org/urls/raw.github.com/cs109/content/master/InstructionsForAmazonEMR.ipynb), [Elastic MapReduce Quickstart](http://pythonhosted.org/mrjob/guides/emr-quickstart.html)\n",
      "\n",
      "Once you have this all set up and working, then mrjob makes it *very easy* to run a MapReduce job with EMR. Using the same MRMostUsedWord example as above, the command line invokation to run with EMR is:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "python MRMostUsedWord.py -r emr some_file.txt > most_used_word.out"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "3. MapReduce exercises"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "![MapReduce schematic](https://developers.google.com/appengine/docs/python/images/mapreduce_mapshuffle.png)\n",
      "<br /> \\[<span style=\"font-size: small;\">Image from [https://developers.google.com/appengine/docs/python/dataprocessing/](https://developers.google.com/appengine/docs/python/dataprocessing/)</span>\\]\n",
      "\n",
      "Below are two practice problems to get the hang of writing MapReduce algorithms. Remember, you will be writing these programs in separate files that you run from the command line. You are welcome to try out EC2, but these are small datasets and it will generally be much faster to run locally."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "3.1 Anagram finder"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "First, grab the file [word_list.txt](https://raw.github.com/cs109/content/master/labs/lab8/word_list.txt). This contains a list of six-letter words that I dumped from my spellchecker. To keep things simple, all of the words consist of lower-case letters only."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "word_list = [word.strip() for word in open(\"word_list.txt\").readlines()]\n",
      "print \"{0} words in list\".format(len(word_list))\n",
      "print \"First ten words: {0}\".format(\", \".join(word_list[0:10]))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Use mrjob to write a class that finds all anagrams in word_list.txt. \n",
      "\n",
      "**UPDATE**: [My solution to exercise 3.1](https://raw.github.com/cs109/content/master/labs/lab8/anagrams.py)"
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "3.2 Friends don't let friends root for the Cardinals"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "![Cardinals v. Red Sox](http://www.stlcardinalbaseball.com/wp-content/uploads/2013/10/CARDINALS-V-RED-SOX-650x325.jpg)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "For the next problem, download the file [baseball_friends.csv](https://raw.github.com/cs109/content/master/labs/lab8/baseball_friends.csv). Each row of this csv file contains the following:\n",
      "\n",
      "* A person's name\n",
      "* The team that person is rooting for -- either \"Cardinals\" or \"Red Sox\"\n",
      "* A list of that person's friends, which could have arbitrary length\n",
      "\n",
      "Let's take a look at one line:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "friends = open(\"baseball_friends.csv\").readlines()\n",
      "print friends[0].strip()\n",
      "print len(friends[0].split(\",\")) - 2"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This line tells us that Aaden is a Red Sox friend and he has 65 friends, who are all listed here. For this problem, it's safe to assume that all of the names are unique and that the friendship structure is symmetric (*i.e.* if Alannah shows up in Aaden's friends list, then Aaden will show up in Alannah's friends list).\n",
      "\n",
      "Write an mrjob class that lists each person's name, their favorite team, the number of Red Sox fans they are friends with, and the number of Cardinals fans they are friends with.\n",
      "\n",
      "After running that program, we can look at the results to get an idea of the absurdly simple model that I used to generate the input csv file. You might need to modify the code below if the format of your output file doesn't quite match mine."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import pandas as pd\n",
      "import json\n",
      "\n",
      "# Read results.\n",
      "result_file = \"baseball_friends.out\"\n",
      "result = [[json.loads(field) for field in line.strip().split('\\t')] for line in open(result_file)]\n",
      "\n",
      "# Break out columns.\n",
      "names = [x[0] for x in result]\n",
      "teams = [x[1][0] for x in result]\n",
      "redsox_count = [x[1][1] for x in result]\n",
      "cardinals_count = [x[1][2] for x in result]\n",
      "\n",
      "# Combine in data frame.\n",
      "result = pd.DataFrame(index=names, data={'teams': teams, 'redsox_count': redsox_count, \n",
      "                                         'cardinals_count': cardinals_count})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%matplotlib inline\n",
      "import matplotlib.pyplot as plt\n",
      "from matplotlib import rcParams\n",
      "rcParams['figure.figsize'] = (10, 6)\n",
      "rcParams['font.size'] = 14\n",
      "\n",
      "# Average number of friends by affiliation.\n",
      "print result.groupby('teams').mean()\n",
      "\n",
      "# Histogram the affiliations of people who are friends of Red Sox fans.\n",
      "plt.hist(result.redsox_count[result.teams == \"Red Sox\"], label=\"Red Sox friend Red Sox\")\n",
      "plt.hist(result.cardinals_count[result.teams == \"Red Sox\"], label=\"Red Sox friend Cardinals\")\n",
      "plt.xlabel('number of friends')\n",
      "plt.ylabel('count')\n",
      "plt.legend(loc=0)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**UPDATE**: [My solution to exercise 3.2](https://raw.github.com/cs109/content/master/labs/lab8/friend_affiliations.py)"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}