[jira] [Commented] (GIRAPH-155) Allow creation of graph by adding edges that span multiple workers

["Alessandro Presta (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/GIRAPH-155?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13487380#comment-13487380 ] 

Alessandro Presta commented on GIRAPH-155:
------------------------------------------

Results from a PageRank run with 1M vertices, 100 edges per vertex, 10 workers.

I created both vertex-centric and edge-centric input files and uploaded them to the cluster's DFS.
Size of vertex-centric input: 696 MB
Size of edge-centric input: 1.37 GB

I set an input split size between 1 MB and 2 MB.
The vertex-input job created 349 input splits for 10 workers
The edge-input job created 689 input splits for 10 workers

Vertex-input job:

{code}
Total (milliseconds)	37,271	0	37,271
Setup (milliseconds)	7,030	0	7,030
Shutdown (milliseconds)	48	0	48
Superstep 0 (milliseconds)	7,362	0	7,362
Input superstep (milliseconds)	16,434	0	16,434
Superstep 2 (milliseconds)	586	0	586
Superstep 1 (milliseconds)	5,808	0	5,808
Giraph Stats	Aggregate edges	100,000,000	0	100,000,000
Superstep	3	0	3
Last checkpointed superstep	0	0	0
Current workers	10	0	10
Current master task partition	0	0	0
Sent messages	0	0	0
Aggregate finished vertices	1,000,000	0	1,000,000
Aggregate vertices	1,000,000	0	1,000,000
{code}

Edge-input job:

{code}
Total (milliseconds)	60,214	0	60,214
Setup (milliseconds)	12,073	0	12,073
Shutdown (milliseconds)	55	0	55
Superstep 0 (milliseconds)	6,999	0	6,999
Input superstep (milliseconds)	34,748	0	34,748
Superstep 2 (milliseconds)	637	0	637
Superstep 1 (milliseconds)	5,700	0	5,700
Giraph Stats	Aggregate edges	100,000,000	0	100,000,000
Superstep	3	0	3
Last checkpointed superstep	0	0	0
Current workers	10	0	10
Current master task partition	0	0	0
Sent messages	0	0	0
Aggregate finished vertices	1,000,000	0	1,000,000
Aggregate vertices	1,000,000	0	1,000,000
{code}

Overall results look good: a 2x performance hit for an aggregation operation that would otherwise need to be done in advance (with the database of choice, a MapReduce job, you name it).

These results can probably be improved by optimizing the VertexResolver and mutation code in general (maybe some of the ideas from messaging and vertex requests can be reused).
                
> Allow creation of graph by adding edges that span multiple workers
> ------------------------------------------------------------------
>
>                 Key: GIRAPH-155
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-155
>             Project: Giraph
>          Issue Type: New Feature
>          Components: graph, lib
>    Affects Versions: 0.2.0
>            Reporter: Dionysios Logothetis
>            Assignee: Alessandro Presta
>         Attachments: GIRAPH-155.patch
>
>
> Currently a graph is created only be adding vertices. The typical way is to read input text files line-by-line with each line describing a vertex (its value, its edges etc). The current API allows for the creation of a vertex only if all the information for the vertex is available in a single line.
> However, it's common to have graphs described in the form of edges. Edges might span multiple lines in an input file or even span multiple workers. The current API doesn't allow this. In the input superstep, a vertex must be created by a single worker.
> Instead, it should be possible for multiple workers to mutate the graph during the input superstep.
> This has the following implications:
> 1) Instead of just instantiating a vertex, a vertex reader should be able to do vertex addition and edge addition requests.
> 2) Multiple workers might try to create the same vertex. Any conflicts should be handled with a VertexResolver. So the resolver has to be instantiated before load time.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira