Paul Ingles

The quantity of data we analyse at Forward every day has grown nearly ten-fold in just over 18 months. Today we run almost all of our automated daily processing on Hadoop. The vast majority of that analysis is automated using Ruby and our open-source gem: Mandy.

In this post I’d like to cover a little background to MapReduce and Hadoop and a light introduction to writing a word count in Ruby with Mandy that can run on Hadoop.

Mandy’s aim is to make MapReduce with Hadoop as easy as possible: providing a simple structure for writing code, and commands that make it easier to run Hadoop jobs.

Since I left ThoughtWorks and joined Forward in 2008 I’ve spent most of my time working on the internal systems we use to work with our clients, track our ads, and analyse data. Data has become truly fundamental to our business.

I think it’s worth putting the volume of our processing in numbers: we track around 9 million clicks a day across our campaigns- averaged out across a day that’s over 100 every second (it actually peaks up to around 1400 a second).

We automate the analysis, storage, and processing of around 80GB (and growing) of data every day. In addition, further ad-hoc analysis is performed through the use of a related project: Hive (more on this in a later blog post).

We’d be hard pressed to work with this volume of data in a reasonable fashion, or be able to change what analysis we run, so quickly if it wasn’t for Hadoop and it’s associated projects.

Hadoop is an open-source Apache project that provides “open-source software for reliable, scalable, distributed computing”. It’s written in Java and, although relatively easy to get into, still falls foul of Java development cycle problems: they’re just too long. My colleague (Andy Kent) started writing something we could prototype our jobs in Ruby quickly, and then re-implement in Java once we understood things better. However, this quickly turned into our platform of choice.

To give a taster of where we’re going, here’s the code needed to run a distributed word count:

require "rubygems"
require "mandy"

Mandy.job "Word Count" do
  map_tasks 5
  reduce_tasks 3

  map do |line|        
    line.split(' ').each do |word|
      word.downcase!
      word.gsub!(/\W|[0-9_]/, '')
      next if word.size == 0
      emit(word, 1)
    end
  end

  reduce do |word, occurrences|
    emit(word, occurrences.size)
  end
end

And how to run it?

mandy-hadoop wordcount.rb hdfs-dir/war-and-peace.txt hdfs-dir/wordcount-output

The above example comes from a lab Andy and I ran a few months ago at our office. All code (and some readmes) are available on GitHub.

What is Hadoop?

The Apache Hadoop project actually contains a number of sub-projects. MapReduce probably represents the core- a framework that provides a simple distributed processing model, which when combined with HDFS provides a great way to distribute work across a cluster of hardware. Of course, it goes without saying that it is very closely based upon the Google paper.

Parallelising Problems

Google’s MapReduce paper explains how, by adopting a functional style, programs can be automatically parallelised across a large cluster of machines. The programming model is simple to grasp and, although it takes a little getting used to, can be used to express problems that are seemingly difficult to parallelise.

Significantly, working with larger data sets (both storage and processing) can be solved by growing the cluster’s capacity. In the last 6 months we’ve grown our cluster from 3 ex-development machines to 25 nodes and taken our HDFS storage from just over 1TB to nearly 40TB.

An Example

Consider an example: perform a subtraction across two sets of items. That is

{1,2,3} - {1,2} = {3}

. A naive implementation might compare every item for the first set against those in the second set.

numbers = [1,2,3]
[1,2].each { |n| numbers.delete(n) }

This is likely to be problematic when we get to large sets as the time taken will grow very fast (m*n). Given an initial set of 10,000,000 items, finding the distinct items from a second site of even 1,000 items would result in 10 billion operations.

However, because of the way the data flows through a MapReduce process, the data can be partitioned across a number of machines such that each machine performs a smaller subset of operations with the result then combined to produce a final output.

It’s this flow that makes it possible to ‘re-phrase’ our solution to the problem above and have it operate across a distributed cluster of machines.

Overall Data Flow

The Google paper and a Wikipedia article provide more detail on how things fit together, but here’s the rough flow.

Map and reduce functions are combined into one or more ‘Jobs’ (almost all of our analysis is performed by jobs that pass their output to further jobs). The general flow can be seen to be made of the following steps:

1. Input data read
2. Data is split
3. Map function called for each record
4. Shuffle/sort
5. Sorted data is merged
6. Reduce function called
7. Output (for each reducer) written to a split
8. Your application works on a join of the splits

First, the input data is read and partitioned into splits that are processed by the Map function. Each map function then receives a whole ‘record’. For text files, these records will be a whole line (marked by a carriage return/line feed at the end).

Output from the Map function is written behind-the-scenes and a shuffle/sort performed. This prepares the data for the reduce phase (which needs all values for the same key to be processed together). Once the data has been sorted and distributed to all the reducers it is then merged to produce the final input to the reduce.

Map

The first function that must be implemented is the map function. This takes a series of key/value pairs, and can emit zero or more pairs of key/value outputs. Ruby already provides a method that works similarly: Enumerable#map.

For example:

names = %w(Paul George Andy Mike)
names.map {|name| {name.size => name}} # => [{4=>"Paul"}, {6=>"George"}, {4=>"Andy"}, {4=>"Mike"}]

The map above calculates the length of each of the names, and emits a list of key/value pairs (the length and names). C# has a similar method in ConvertAll that I mentioned in a previous blog post.

Reduce

The reduce function is called once for each unique key across the output from the map phase. It also produces zero or more key value pairs.

For example, let’s say we wanted to find the frequency of all word lengths, our reduce function would look a little like this:

def reduce(key, values)
  {key => values.size}
end

Behind the scenes, the output from each invocation would be folded together to produce a final output.

To explore more about how the whole process combines to produce an output let’s now turn to writing some code.

Code: Word Count in Mandy

As I’ve mentioned previously we use Ruby and Mandy to run most of our automated analysis. This is an open-source Gem we’ve published which wraps some of the common Hadoop command-line tools, and provides some infrastructure to make it easier to write MapReduce jobs.

Installing Mandy

The code is hosted on GitHub, but you can just as easily install it from Gem Cutter using the following:

$ sudo gem install gemcutter
$ gem tumble
$ sudo gem install mandy

… or

$ sudo gem install mandy --source http://gemcutter.org

If you run the mandy command you may now see:

You need to set the HADOOP_HOME environment variable to point to your hadoop install    :(
Try setting 'export HADOOP_HOME=/my/hadoop/path' in your ~/.profile maybe?

You’ll need to make sure you have a 0.20.x install of Hadoop, with HADOOP_HOME set and $HADOOP_HOME/bin in your path. Once that’s done, run the command again and you should see:

You are running Mandy!
========================

Using Hadoop 0.20.1 located at /Users/pingles/Tools/hadoop-0.20.1

Available Mandy Commands
------------------------
mandy-map       Run a map task reading on STDIN and writing to STDOUT
mandy-local     Run a Map/Reduce task locally without requiring hadoop
mandy-rm        remove a file or directory from HDFS
mandy-hadoop    Run a Map/Reduce task on hadoop using the provided cluster config
mandy-install   Installs the Mandy Rubygem on several hosts via ssh.
mandy-reduce    Run a reduce task reading on STDIN and writing to STDOUT
mandy-put       upload a file into HDFS

If you do, you’re all set.

Writing a MapReduce Job

As you may have seen earlier to write a Mandy job you can start off with as little as:

require "rubygems"
require "mandy"

Mandy.job "Word count" do
  map do |line|
    # code here
  end
end

Of course, you may be interested in writing some tests for your functions too. Well, you can do that quite easily with the Mandy::TestRunner. Our first test for the Word Count mapper might be as follows:

describe "Word Count" do
  before(:all) do
    job_name = "Word Count"
    @runner = Mandy::TestRunner.new(job_name)
  end

  describe "mapper" do
    it "splits on spaces and emits words" do
      @runner.map("Fake carl") do |mapper|
        mapper.should_receive(:emit).with('fake', 1)
        mapper.should_receive(:emit).with('carl', 1)
      end
    end
  end
end

Our implementation for this might look as follows:

Mandy.job "Word Count" do
  map do |line|
    line.split(' ').each do |word|
      emit(word, 1)
    end
  end
end

Of course, our real mapper needs to do more than just tokenise the string. It also needs to make sure we downcase and remove any other characters that we want to ignore (numbers, grammatical marks etc.). The extra specs for these are in the mandy-lab GitHub repository but are relatively straightforward to understand.

Remember that each map works on a single line of text. We emit a value of 1 for each word we find which will then be shuffled/sorted and partitioned by the Hadoop machinery so that a subset of data is sent to each reducer. Each reducer will, however, receive all the values for that key. All we need to do in our reducer is sum all the values (all the 1’s) and we’ll have a count. First, our spec:

describe "reducer" do
  it "counts occurrences" do
    occurrences = [1,1,1,1]
    @runner.reduce('andy' => occurrences) do |reducer|
      reducer.should_receive(:emit).with('andy', 4)
    end
  end
end

And our implementation:

Mandy.job "Word Count" do
  # ... snipped for brevity

  reduce do |word, occurrences|
    emit(word, occurrences.size)
  end
end

In fact, Mandy has a number of built-in reducers that can be used (so you don’t need to re-implement this). To re-use the Sum-ming reducer replace the reduce statement above to reduce(Mandy::Reducers::SumReducer).

Our mandy-lab repository includes some sample text files you can run the examples on. Assuming you’re in the root of the repo you can then run the following to perform the wordcount across Alice in Wonderland locally:

$ mandy-local word_count.rb input/alice.txt output
Running Word Count...
/Users/pingles/.../output/1-word-count

If you open the /Users/pingles/.../output/1-word-count file you should see a list of words and their frequency across the document set.

Running the Job on a Cluster

The mandy-local command just uses some shell commands to imitate the MapReduce process. If you try running the same command over a larger dataset you’ll come unstuck. So let’s see how we run the same example on a real Hadoop cluster. Note, that for this to work you’ll need to either have a Hadoop cluster or Hadoop running locally in pseudo-distributed mode.

If you have a cluster up and running, you’ll need to write a small XML configuration file to provide the HDFS and JobTracker connection info. By default the mandy-hadoop command will look for a file called cluster.xml in your working directory. It should look a little like this:

<?xml version="1.0" encoding="UTF-8"?>
<configuration>
  <property>
    <name>fs.default.name</name>
    <value>hdfs://datanode:9000/</value>
  </property>
  <property>
    <name>mapred.job.tracker</name>
    <value>jobtracker:9001</value>
  </property>
  <property>
    <name>hadoop.job.ugi</name>
    <value>user,supergroup</value>
  </property>
</configuration>

Once that’s saved, you need to copy your text file to HDFS so that it can be distributed across the cluster ready for processing. As an aside: HDFS shards data in 64MB blocks across the nodes. This provides redundancy to help mitigate in the case of machine failure. It also means the job tracker (the node which orchestrates the processing) can move the computation close to the data and avoid copying large amounts of data unnecessarily.

To copy a file up to HDFS, you can run the following command

$ mandy-put my-local-file.txt word-count-example/remote-file.txt

You’re now ready to run your processing on the cluster. To re-run the same word count code on a real Hadoop cluster, you change the mandy-local command to mandy-hadoop as follows:

$ mandy-hadoop word_count.rb word-count-example/remote-file.txt word-count-example/output

Once that’s run you should see some output from Hadoop telling you the job has started, and where you can track it’s progress (via the HTTP web console):

Packaging code for distribution...
Loading Mandy scripts...

Submitting Job: [1] Word Count...
Job ID: job_200912291552_2336
Kill Command: mandy-kill job_200912291552_2336 -c /Users/pingles/.../cluster.xml
Tracking URL: http://jobtracker:50030/jobdetails.jsp?jobid=job_200912291552_2336

word-count-example/output/1-word-count

Cleaning up...
Completed Successfully!

If you now take a look inside ./word-count-example/output/1-word-count you should see a few part-xxx files. These contain the output from each reducer. Here’s the output from a reducer that ran during my job (running across War and Peace):

abandoned   54
abandoning  26
abandonment 14
abandons    1
abate   2
abbes   1
abdomens    2
abduction   3
able    107

Wrap-up

That’s about as much as I can cover in an introductory post for Mandy and Hadoop. I’ll try and follow this up with a few more to show how you can pass parameters from the command-line to Mandy jobs, how to serialise data between jobs, and how to tackle jobs in a map and reduce stylee.

As always, please feel free to email me or comment if you have any questions, or (even better) anything you’d like me to cover in a future post.

During the most recent ThoughtWorks away-day (a chance for the office to get together, catch-up, drink etc.), George and I presented on a number of Ruby and Rails lessons we learned from our (now previous) project. One of the most interesting sections (to us anyway) was on declarative programming, specifically, refactoring to a declarative design.

I guess much like DSLs, its easier to feel when you’re achieving something declarative as opposed to necessarily defining what makes it. But, I’ll try my clumsy best to define something.

Almost every language I’ve turned my hand to (save for Erlang) are imperative languages - where programs are written as sequences of operations, with changes of state. You determine the what and the how of the system - what to do and how to do it.

Declarative programming is an alternative paradigm, whereby code is expressed as what’s. How the system executes is someone else’s responsibility.

So, for the purposes of this discussion let’s consider that application code can be split into two groups

1. Logic- the rules, the guts of things- that what’s.


2. Control- statements about execution flow.

Interestingly, one of the principles listed in Kent Beck’s most recent book (Implementation Patterns) includes “Declarative Expression” - that you should be able to read what your code is doing, without having to understand the wider execution context.

Declarative languages are all around us, with most developers I’m guessing using them almost daily.

Think of SQL, when you write a statement such like SELECT [Name], [Age] FROM [Person] WHERE [Age] > 15 you’re making a statement about what you’d like, not how you get there- that’s up for the database engine to figure out. And a good thing to! Have you ever taken a look at an execution plan for modestly complex queries?

Closter to home - think of .NET and Java Annotations- where you can decorate constructs with additional behaviours. They look and feel like core extensions to the language, but are programmable and can be used to adapt the runtime behaviour of the system.

Before working for ThoughtWorks, I worked on a system where we used attributes to allow us to add validations to properties, allowing us to re-use code and extend easily.

[LengthMustBeAtLeast(6)]
public property string FirstName
{
  get { ... }
  set { ... }
}

Everything was nicely decoupled, read well, and reduced the amount of clutter in our code. More importantly, our validation code was not spread throughout every setter of every property. We could isolate responsibilities making code easier to digest and understand, and test!

Onto Ruby. A substantial part of our project involved reading lots of CSV files from different sources to update our deal information. The answer was a kind of anticorruption layer (borrowing heavily from domain-driven design) for each different feed.

Quickly, we ended up with a few concrete classes and a base class that co-ordinated effort. Dependencies were shared both ways, imagine a number of template methods that are called in sequence to accomplish their work. Over time it grew complex, and with Ruby it’s a little tougher (than with languages like Java or .NET) to navigate and browse around the code without strong IDE support.

It was starting to get a little too complex and we felt we needed to change things, so we did (bolstered somewhat by having Jay with us).

Onto the code.

So imagine we have a class representing a Feed of information (read from a CSV file), and we want to be able to ask that Feed to provide us with a number of Deals. Internally, it will iterate over the items in the Feed, creating a Deal for each one (if possible).

Our first solution looked a little like this, firstly in the ‘abstract’ base class:

def create_deal
  Deal.create(:network_name => network_name)
end

and in the feed’s concrete implementation:

FIELD_INDICES = {:name => 1, :network_name => 2}
def network_name
  read_cell(FIELD_INDICES[:network_name])
end

Our main feed class asks our implementation class for the network_name - a template method. Not bad, now build that up to tens of attributes, a bit longer. Since we’ve defined column indices in a constant, we also now have to navigate up and down lots to determine where we’re reading from. Add in a few other tables with look-ups for other bits that we need to do the mapping and it can get a little complex pretty quick.

Our code is not only made up of the stuff determining what it is to translate between a CSV representation of our Deals to an object model one, but also all of the code necessary to find out which CSV column we’re in, how we map that column etc. They were essentially just reading values from cells, no translation needed. Most of the code we had was infrastructural, and the logic (the what of our application) was hidden amongst the noise.

This complexity, combined with the split of flow between abstract and concrete classes, made it difficult to follow and understand. Our goal was to try and reduce each concrete implementation to a single page on our screens.

These little ‘mapping’ translation methods were our first target - reduce the amount of code for each of these to one line that described the mapping, rather than how we get it all.

Firstly, we introduced a convention - every attribute of a Deal could be retrieved by calling a deal_attribute_my_attribute style method. So, we renamed all our methods, ran the tests, and then started to make steps towards having each deal_attribute_blah method defined dynamically.

We went from:

def network
  ...
end

to

def deal_attribute_network
  ...
end

to … nothing.

Well, not quite. Instead, what we wanted was to have a method constructed by adding a class method to a module that we could mix-in. Then, we could just define the mapping and Ruby would wire up the rest. We settled on the following syntax

deal_attribute :name => 'NAME'

Neat. A little classeval and instanceeval magic later we were able to push our infrastructural code out of our concrete feed class and into the co-ordinator.

Our code is now more declarative. We’re stating what we need to do our work, rather than worrying about how we get at it. Not only that, for the common case (where we may be just moving values from one place to another) there’s no need to do anything more than describe that relationship. Declarative programming makes it much easier to express important relationships. It’s now much easier to see the relationship between the name attribute of a Deal and the NAME column for this CSV feed.

Notice also how we’re pushing our dependencies up to our caller- the coupling is now one-way. We state what we need from our caller (the main deal feed class) - our caller is able to then pass the information on. We’re just answering questions, rather than answering questions and asking questions (of our caller).

The syntax also lends itself to explaining a dependency, that an attribute of our deal is read from ‘NAME’ (for example).

That’s great, next step was to tidy up some of the slightly more complex examples where we do some additional translation. For example, where we take the name of something and we need to pull back an object from the database instead. Let’s say we keep track of the Phone that a Deal is for.

So, from

def deal_attribute_phone
  Phone.find(deal_attribute_brand, deal_attribute_model)
end

to

deal_attribute(:phone => ['MAKE', 'MODELNAME']) do |brand, model|
  Phone.find(brand, model)
end

We’ve extended the syntax to reveal that this translation needs values from both the ‘MAKE’ and ‘MODELNAME’ columns. From our perspective, we’re pushing responsibility up and keeping our code focused on what we need to map this attribute.

This is a little more complex to achieve since we’re also passing arguments across (and our deal_attribute translator methods also sometimes need to access instance variables) so we need to use instance_exec instead of the standard instance_eval.

The end result was feed classes that looked as follows

class MySpecialFeed
  deal_attribute :name => 'NAME'
  deal_attribute(:description => 'DESC') {|desc| cleanse_description(desc) }
  deal_attribute(:phone => ['MAKE', 'MODELNAME']) do |brand, model|
    Phone.find(brand, model)
  end
  ...
end

In total, it took us probably just over a day to refactor the code for all of our classes. Most of which we managed to get down to some 40 or 50 lines total. We didn’t refactor all the code, so there’s still potential for exploiting it further but it was definitely a very exciting thing to see happen.

From across the desk, George asks “can you copy classes in Ruby?”. We talk about it quickly and reason that since everything’s an Object (even classes), you probably can. Since the constant isn’t changed or duplicated (you’re essentially assigning a new one) then it ought to be possible.

Turns out it is!

class First
  def initialize
    @value = 99
  end
  def say_value
    @value
  end
end
First.new.say_value # => 99
Second = First.clone
Second.class_eval do
  define_method :say_value do
    @value + 100
  end
end
Second.new.say_value # => 199

Neat.

I’m not sure quite why you would want to clone a class to take advantage of re-use - rather than extract to a module (and share the implementation that way) or, if there’s a strong relationship that doesn’t violate the LSP etc. then look for some kind of inheritance-based design.

But, I guess you could work some kind of cool ultra-dynamic super-meta system from it. Perhaps someone with way more of a Ruby-thinking brain than me could offer some thoughts?

The project I’m currently working on uses both the Asset Packager and Distributed Assets to ensure we have only a few external assets, and that we can load assets across more than one host - all so that the pages for our site load nice and quick.

Unfortunately, wiring in the Asset Packager plugin caused the Distributed Assets plugin to break, and I spent an hour or two tracking it down yesterday. The cause? Asset Packager redefines the compute_public_path method.

# rewrite compute_public_path to allow us to not include the query string timestamp
    # used by ActionView::Helpers::AssetTagHelper
    def compute_public_path(source, dir, ext=nil, add_asset_id=true)
      source = source.dup
      source << ".#{ext}" if File.extname(source).blank? && ext
      unless source =~ %r{^[-a-z]+://}
        source = "/#{dir}/#{source}" unless source[0] == ?/
        asset_id = rails_asset_id(source)
        source << '?' + asset_id if defined?(RAILS_ROOT) and add_asset_id and not asset_id.blank?
        source = "#{ActionController::Base.asset_host}#{@controller.request.relative_url_root}#{source}"
      end
      source
    end

Distributed Assets works by chaining compute_public_path - decorating the calculated path, adding the asset host prefix onto the url. But, Asset Packager works by defining the method into ActionView::Base. So, when DistributedAssets::AssetTagHelper is included with ActionView::Helpers::AssetTagHelper, it chains a (now) hidden method.

But, the only places that use the new compute_public_path code inside the Asset Packager Helper (which just avoids using the query string timestamp) is within Asset Packager itself.

So, I tweaked the implementation of AssetPackageHelper to

def compute_public_path_for_packager(source, dir, ext, add_asset_id=true)
  path = compute_public_path(source, dir, ext)
  return path if add_asset_id
  path.gsub(/\?\d+$/, '')
end
def javascript_path(source)
  compute_public_path_for_packager(source, 'javascripts', 'js', false)       
end

Beware the monkey patch.

Rails makes heavy use of a declarative style around it’s codebase- for example the has_one and belongs_to declarations inside ActiveRecord (amongst others). These are just class methods defined on modules, letting Rails wire up relationships, but they read like fully-fledged statements within a mini-language:

class Student < ActiveRecord::Base
  has_many :tutorials

We can take advantage of the same in our code- letting us write in a declarative-style (hopefully revealing stronger intent) and reduce the amount of code we write (by using declarations to meta-program for us). I posted a little while ago that we’d used such an approach for marking attributes as immutable.

Anyway, back to the title of the post- #instance_exec, it’s a method defined in Ruby Facets. Like it’s documentation says, it’s equivalent to instance_eval but also lets you pass parameters- roll on the meta magic.

Let’s say we’re writing a system to calculate the monthly salary payment for an employee. We want to be able to say what the payment is rather than how it’s calculated.

class FullTimeEmployee
  include Employee
  bill_at {|hours| 50.pounds_sterling * hours}

In the snippet above, we’re making a declaration - defining the relationship between an hourly rate and the number of hours the employee works. We can implement bill_at in Employee as follows:

module Employee
  module ClassMethods
    def bill_at &block
      define_method(:calculate_bill) do |hours|
        instance_exec hours, &block
      end
  ...

Our assertion could be:

assert_equal 500.pounds_sterling, employee.calculate_bill(5.hours)