Return-Path: X-Original-To: apmail-incubator-giraph-user-archive@minotaur.apache.org Delivered-To: apmail-incubator-giraph-user-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id D4F9372AA for ; Fri, 9 Dec 2011 18:04:22 +0000 (UTC) Received: (qmail 19717 invoked by uid 500); 9 Dec 2011 18:04:22 -0000 Delivered-To: apmail-incubator-giraph-user-archive@incubator.apache.org Received: (qmail 19675 invoked by uid 500); 9 Dec 2011 18:04:22 -0000 Mailing-List: contact giraph-user-help@incubator.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: giraph-user@incubator.apache.org Delivered-To: mailing list giraph-user@incubator.apache.org Received: (qmail 19568 invoked by uid 99); 9 Dec 2011 18:04:22 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 09 Dec 2011 18:04:22 +0000 X-ASF-Spam-Status: No, hits=1.5 required=5.0 tests=HTML_MESSAGE,RCVD_IN_DNSWL_LOW,SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (nike.apache.org: domain of jake.mannix@gmail.com designates 209.85.213.175 as permitted sender) Received: from [209.85.213.175] (HELO mail-yx0-f175.google.com) (209.85.213.175) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 09 Dec 2011 18:04:14 +0000 Received: by yenm12 with SMTP id m12so2568991yen.6 for ; Fri, 09 Dec 2011 10:03:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=wQ6SnJmvTKzMmt4yDCbteKGydW5yEmPgloKagGloBOY=; b=tZ2LG4daf+wFYMSvMVaLFm/OYmK3GDWu9FhtiYUNbJFHMfQ1XH0zCoTBTng4q5Qkci 2er/6zFuoTEtFMKCkAnGDlMWR5KGISdxYPyeeO1BeYuQ3K0LTO6yyJ6Krtv1M58AndS1 aoKcAYzUUsfdstpmsBLYNL4B+a/zufAlvsgfM= Received: by 10.236.75.230 with SMTP id z66mr13524615yhd.66.1323453833175; Fri, 09 Dec 2011 10:03:53 -0800 (PST) MIME-Version: 1.0 Received: by 10.147.25.9 with HTTP; Fri, 9 Dec 2011 10:03:32 -0800 (PST) In-Reply-To: References: <4EE1B704.2000600@apache.org> From: Jake Mannix Date: Fri, 9 Dec 2011 10:03:32 -0800 Message-ID: Subject: Re: Comparing BSP and MR To: giraph-user@incubator.apache.org Content-Type: multipart/alternative; boundary=20cf300fb09f9a623404b3ac9b6a X-Virus-Checked: Checked by ClamAV on apache.org --20cf300fb09f9a623404b3ac9b6a Content-Type: text/plain; charset=ISO-8859-1 [hama-user to bcc:] Let's not crosspost, please, it make the thread of conversation totally opaque as to who is talking about what. On Fri, Dec 9, 2011 at 1:42 AM, Praveen Sripati wrote: > Thanks to Thomas and Avery for the response. > > > For Giraph you are quite correct, all the stuff is submitted as a MR > job. But a full map stage is not a superstep, the whole computation is a > done in one mapping phase. > > So a map task in MR corresponds to a computation phase in a superstep. > Once the computation phase for a superstep is complete, the vertex output > is stored using the defined OutputFormat, the message sent (may be) to > another vertex and the map task is stopped. Once the barrier > synchronization phase is complete, another set of map tasks are invoked for > the vertices which have received a message. > In Giraph, each superstep does not lead to storage into an OutputFormat. The data lives all in memory from the time the first superstep starts to the time the final superstep stops (except that for tolerance of failures, checkpoints are stored to disk at user-specified intervals). There is only one set of map tasks for the Giraph job - those long-running map tasks run possibly many supersteps. > In a regular MR Job (not Giraph) the number of Map tasks equals to the > number of InputSplits. But, in case of Giraph the total number of maps to > be launched is usually more than the number of input vertices. > Number of maps > number of input vertices? Not at all. That would be insane. We want to be able to run over multi-billion vertex graphs. We're going to launch multiple billions of mappers? The splitting of the data in Giraph is very similar to in a regular MR job, divide up your input data among the number of mappers you have, and you're off and running. > > > Where are the incoming, outgoing messages and state stored > > Memory > > What happens if a particular node is lost in case of Hama and Giraph? Are > the messages not persisted somewhere to be fetched later. If nodes are lost, the system has to back up to the most recent checkpoint, where graph state has been persisted to HDFS. Messages are not currently persisted, but the state at which the graph was in to produce any messages was. > > In Giraph, vertices can move around workers between supersteps. A > vertex will run on the worker that it is assigned to. > > Is data locality considered while moving vertices around workers in Giraph? > Data is all in memory, and typical graph algorithms are basically sending roughly the size of the entire graph (number of total edges) out over distributed RPC in any given superstep, so shuffling the graph around by RPC is not much more to do. > > > As you can see, you could write a MapReduce Engine with BSP on top of > Apache Hama. > > It's being the done other way, BSP is implemented in Giraph using Hadoop. I'll let the Hama people explain to you about how one would implement MR on top of Hama. You are correct that in Giraph, the Hadoop JobTracker/TaskTracker and HDFS are used as substrate to help implement BSP (although I would not say that "MR" is being used to implement BSP, as there is no MR going on in Giraph). -jake > > > Praveen > > On Fri, Dec 9, 2011 at 12:51 PM, Avery Ching wrote: > >> Hi Praveen, >> >> Answers inline. Hope that helps! >> >> Avery >> >> On 12/8/11 10:16 PM, Praveen Sripati wrote: >> >> Hi, >> >> I know about MapReduce/Hadoop and trying to get myself around >> BSP/Hama-Giraph by comparing MR and BSP. >> >> - Map Phase in MR is similar to Computation Phase in BSP. BSP allows for >> process to exchange data in the communication phase, but there is no >> communication between the mappers in the Map Phase. Though the data flows >> from Map tasks to Reducer tasks. Please correct me if I am wrong. Any other >> significant differences? >> >> I suppose you can think of it that way. I like to compare a BSP >> superstep to a MapReduce job since it's computation and communication. >> >> - After going through the documentation for Hama and Giraph, noticed that >> they both use Hadoop as the underlying framework. In both Hama and Giraph >> an MR Job is submitted. Does each superstep in BSP correspond to a Job in >> MR? Where are the incoming, outgoing messages and state stored - HDFS or >> HBase or Local or pluggable? >> >> My understanding of Hama is that they have their own BSP framework. >> Giraph can be run on a Hadoop installation, it does not have its own >> computational framework. A Giraph job is submitted to a Hadoop >> installation as a Map-only job. Hama will have its own BSP lauching >> framework. >> >> In Giraph, the state is stored all in memory. Graphs are loaded/stored >> through VertexInputFormat/VertexOutputFormat (very similar to Hadoop). You >> could implement your own VertexInputFormat/VertexOutputFormat to use HDFS, >> HBase, etc. as your graph stable storage. >> >> - If a Vertex is deactivated and again activated after receiving a >> message, does is run on the same node or a different node in the cluster? >> >> In Giraph, vertices can move around workers between supersteps. A >> vertex will run on the worker that it is assigned to. >> >> Regards, >> Praveen >> >> >> > --20cf300fb09f9a623404b3ac9b6a Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable [hama-user to bcc:]

Let's not crosspost, please, it = make the thread of conversation totally opaque as to who is talking about w= hat.

On Fri, Dec 9, 2011 at 1:42 AM, Prav= een Sripati <praveensripati@gmail.com> wrote:
Thanks to Thomas and Avery for the response.

> For Giraph= you are quite correct, all the stuff is submitted as a MR job. But a full = map stage is not a superstep, the whole computation is a done in one mappin= g phase.

So a map task in MR corresponds to a computation phase in a superstep. = Once the computation phase for a superstep is complete, the vertex output i= s stored using the defined OutputFormat, the message sent (may be) to anoth= er vertex and the map task is stopped. Once the barrier synchronization pha= se is complete, another set of map tasks are invoked for the vertices which= have received a message.

In Giraph, each superstep do= es not lead to storage into an OutputFormat. =A0The data lives all in memor= y from the time the first superstep starts to the time the final superstep = stops (except that for tolerance of failures, checkpoints are stored to dis= k at user-specified intervals). =A0There is only one set of map tasks for t= he Giraph job - those long-running map tasks run possibly many supersteps.<= /div>
=A0
In a regular MR Job (not Giraph) the number of Map = tasks equals to the number of InputSplits. But, in case of Giraph the total= number of maps to be launched is usually more than the number of input ver= tices.

Number of maps > number o= f input vertices? =A0Not at all. =A0That would be insane. =A0We want to be = able to run over multi-billion vertex graphs. =A0We're going to launch = multiple billions of mappers? =A0 The splitting of the data in Giraph is ve= ry similar to in a regular MR job, divide up your input data among the numb= er of mappers you have, and you're off and running.
=A0

> Where are the incoming, outgoing messages and state stored
> Memory

What happens if a particular node is lost in case of H= ama and Giraph? Are the messages not persisted somewhere to be fetched late= r.

If nodes are lost, the system has to back up to the mos= t recent checkpoint, where graph state has been persisted to HDFS. =A0Messa= ges are not currently persisted, but the state at which the graph was in to= produce any messages was.
=A0
> In Giraph, vertices can move= around workers between supersteps.=A0 A vertex will run on the worker that= it is assigned to.

Is data locality considered while moving vertices around workers = in Giraph?

Data is all in= memory, and typical graph algorithms are basically sending roughly the siz= e of the entire graph (number of total edges) out over distributed RPC in a= ny given superstep, so shuffling the graph around by RPC is not much more t= o do.
=A0

> As you can see, you could write a MapReduc= e Engine with BSP on top of Apache Hama.

It's being the done other way, BSP is implemented in Giraph using H= adoop.

I'll let the Hama = people explain to you about how one would implement MR on top of Hama. =A0Y= ou are correct that in Giraph, the Hadoop JobTracker/TaskTracker and HDFS a= re used as substrate to help implement BSP (although I would not say that &= quot;MR" is being used to implement BSP, as there is no MR going on in= Giraph).

=A0 -jake
=A0


Praveen

On Fri, Dec 9, 2011 at 12:51 PM, Ave= ry Ching <aching@apache.org> wrote:
=20 =20 =20
Hi Praveen,

Answers inline.=A0 Hope that helps!

Avery

On 12/8/11 10:16 PM, Praveen Sripati wrote:
Hi,<= br style=3D"font-family:verdana,sans-serif">
I know about MapReduce/Hadoop and trying to get myself around BSP/Hama-Giraph by comparing MR and BSP.

- Map Phase in MR is similar to Computation Phase in BSP. BSP allows for process to exchange data in the communication phase, but there is no communication between the mappers in the Map Phase. Though the data flows from Map tasks to Reducer tasks. Please correct me if I am wrong. Any other significant differences?
I suppose you can think of it that way.=A0 I like to compare a BSP superstep to a MapReduce job since it's computation and communication.
- After going through the documentation for Hama and Giraph, noticed that they both use Hadoop as the underlying framework. In both Hama and Giraph an MR Job is submitted. Does each superstep in BSP correspond to a Job in MR? Where are the incoming, outgoing messages and state stored - HDFS or HBase or Local or pluggable?

My understanding of Hama is that they have their own BSP framework.=A0 Giraph can be run on a Hadoop installation, it does not have its own computational framework.=A0 A Giraph job is submitted to a Hadoop installation as a Map-only job.=A0 Hama will have its own BSP lauching framework.=A0

In Giraph, the state is stored all in memory.=A0 Graphs are loaded/stored through VertexInputFormat/VertexOutputFormat (very similar to Hadoop).=A0 You could implement your own VertexInputFormat/VertexOutputFormat to use HDFS, HBase, etc. as your graph stable storage.

- If a Vert= ex is deactivated and again activated after receiving a message, does is run on the same node or a different node in the cluster?

In Giraph, vertices can move around workers between supersteps.=A0 A vertex will run on the worker that it is assigned to.

Regards,
Praveen



--20cf300fb09f9a623404b3ac9b6a--