Large Data - II

Consider this simple problem: Count the number of occurrences of each word in a document. Since hash tables are cool, let’s use them. Look at each word. If it is already in the hash table, increment the count. Otherwise, add it to the hash table and set the count to 1.

That’s a reasonably good answer. However,

I get to ask the questions. I’ve found you look a lot smarter asking the questions than dumbly not answering.

Gregory House

So, the smart thing to do is to ask. “How big is the document?”. The approach mentioned above will work for reasonably sized data. It’s better to use a stream reader or lazy evaluation (generators in Python) than a str.split() equivalent on a huge portion of the data.

So, what happens when the data is large?

It’s almost like magic when tasks run on a distributed system. If a problem can be modeled in the Map-Reduce (MR) paradigm, it’s straightforward to write code for it without any optimization. The code is easily tested on a single node installation. And here’s the kicker: the code is unchanged when it has to be run on more than one node. For brevity, I’ve used the Python for the WordCount job. Java code tends to get verbose at times.

#mapper.py
import sys

for l in sys.stdin:
  words = l.strip().split()
  for w in words:
    print w + "\t" + str(1)
#reducer.py
import sys

cur_word = None
cur_count = 0

for l in sys.stdin:
  w,c = l.strip().split('\t',1) # word and count
  if cur_word == w:
    cur_count += int(c)
  else:
    if cur_word: #is not None
      print cur_word + "\t" + str(cur_count)
    cur_word = w
    cur_count = int(c)

To run the MR job, specify the -file as mapper.py and reducer.py for -mapper and -reducer respectively. If there are more clusters, MR executes the job in those clusters which have the data. As the tasks get significantly more complicated, MR offers more abstractions for more control (limited to the JVM as far as I know).

However, it incurs a lot of overhead by writing to the disk after every step. More importantly, not all problems involving Big Data are fit for MR. A striking example for this is iterative algorithms.

Footnotes

Back