4
$\begingroup$

Background: I run a product that compares sets of data (data matching and data reconciliation). To get the result we need to compare each row in a data set with every N rows on the opposing data set Now however we get sets of up to 300 000 rows of data in each set to compare and are getting 90 Billion computations to handle.

So my question is this: Even though we dont have the data volumes to use Hadoop, we have the computational need for something distributed. Is Hadoop a good choice for us?

$\endgroup$
  • 1
    $\begingroup$ How much memory one dataset takes? I.e. what is approximate size of one row? $\endgroup$ – ffriend Sep 4 '14 at 18:34
  • $\begingroup$ The size of rows differs, but on average about 30-50. Data sets are about 100Mb each. $\endgroup$ – papacostas Sep 6 '14 at 12:44
  • $\begingroup$ Meta-comment: N^2 algorithms are always bad news at scale. I would in any event investigate algorithms that do not require all-pairs computation. Cartesian joins destroy data locality optimization. $\endgroup$ – Sean Owen Sep 8 '14 at 11:51
  • $\begingroup$ You haven't specified the constraintd..eg response time, throughput etc $\endgroup$ – seanv507 Sep 9 '14 at 6:32
4
$\begingroup$

Your job seems like a map-reduce job and hence might be good for Hadoop. Hadoop has a zoo of an ecosystem though.

Hadoop is a distributed file system. It distributes data on a cluster and because this data is split up it can be analysed in parallel. Out of the box, Hadoop allows you to write map reduce jobs on the platform and this is why it might help with your problem.

The following technologies work on Hadoop:

  • If the data can be represented in a table format you might want to check out technologies like hive and impala. Impala uses all the distributed memory across a cluster and is very performant while it allows you to still work with a table structure.
  • A more new, but promising alternative might also be spark which allows for more iterative procedures to be run on the cluster.

Don't underestimate the amount of time setting up and the amount of time needed to understand Hadoop.

$\endgroup$
  • 2
    $\begingroup$ Few corrections. Firstly, Hadoop is a common name for a set of tools, file system is called HDFS. Secondly, data may be processed in parallel without distributing it on HDFS, e.g. sending data tuples to Storm or even RabbitMQ with a number of workers on a consumer side will do the trick as well. Thirdly, in this specific case you need to distribute not just 2 separate datasets, but instead all pairs from both (90 B tuples). Spark already has .cartesian() method which does exactly this, but custom lazy generator + RabbitMQ will work fine too. $\endgroup$ – ffriend Sep 5 '14 at 23:44
  • $\begingroup$ Splitting up using a queue and calculating in a distributed fashion is an option. just assume this will come with a price tag of handling a lot of complexity thats been solved in other distributed products. Spark seems like a good candidate on paper. $\endgroup$ – papacostas Sep 6 '14 at 12:46
1
$\begingroup$

If I understand your description correctly, hadoop seems a huge overhead, for the wrong problem. basically you just need a standard distributed architecture: don't you just have to pass pairs of rows - eg mpi.... ipython.parallel, ...

$\endgroup$
  • $\begingroup$ I do not understand the down vote. This is a perfectly reasonable answer. There are platforms other than Hadoop for computational grid computing. $\endgroup$ – Brent Worden Sep 12 '14 at 12:57
1
$\begingroup$

Data volume is not the only criterion for using Hadoop. Big Data is often characterized by the 3 V's:

  • volume,
  • velocity, and
  • variety.

More V's than these 3 have been invented since. I suppose the V's were a catchy way to characterize what is Big Data.

But as hinted, computational intensity is a perfect reason for using Hadoop (if your algorithm is computationally expensive). And, as hinted, the problem you describe is perfect for Hadoop, especially since it is embarrassingly parallel in nature.

Is Hadoop a good choice for you? I would argue, yes. Why? Because

  1. Hadoop is open source (compared with proprietary systems which may be expensive and black boxes),
  2. your problem lends itself well to the MapReduce paradigm (embarassingly parallel, shared-nothing),
  3. Hadoop is easily scalable with commodity hardware (as opposed to specialized hardware, and you should get linear speed-up in your performance with just throwing hardware at the problem, and you can just spin a cluster as needed on cloud service providers),
  4. Hadoop allows multiple client languages (Java is only one of many supported languages),
  5. there might be a library available already to do your cross-product operation, and
  6. you're shipping compute code, not data, around the network (which you should benefit from, and as opposed to other distributed platforms where you are shipping data to compute nodes which is the bottleneck).

Please note, Hadoop is not a distributed file system (as mentioned, and corrected already). Hadoop is distributed storage and processing platform. The distributed storage component of Hadoop is called the Hadoop Distributed File System (HDFS), and the distributed processing component is called MapReduce.

Hadoop has now evolved slightly. They keep the HDFS part for distributed storage. But they have a new component called YARN (Yet Another Resource Negotiator), which serves to appropriate resources (CPU, RAM) for any compute task (including MapReduce).

On the "overhead" part, there is noticeable overhead with starting/stopping a Java Virtual Machine (JVM) per tasks (map tasks, reduce tasks). You can specify for your MapReduce Jobs to reuse JVMs to mitigate this issue.

If "overhead" is really an issue, look into Apache Spark, which is part of the Hadoop ecosystem, and they are orders of magnitude faster than MapReduce, especially for iterative algorithms.

I have used Hadoop to compute pairwise comparisons (e.g. correlation matrix, similarity matrix) that are O(N^2) (n choose 2) in worst case running time complexity. Imagine computing the correlations between 16,000 variables (16,000 choose 2); Hadoop can easily process and store the results if you have the commodity resources to support the cluster. I did this using the preeminent cloud service provider (I won't name it, but you can surely guess who it is), and it cost me < $100 and under 18 hours.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.