incubator-giraph-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "jiraposter@reviews.apache.org (Commented) (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (GIRAPH-11) Improve the graph distribution of Giraph
Date Mon, 14 Nov 2011 20:54:53 GMT

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

jiraposter@reviews.apache.org commented on GIRAPH-11:
-----------------------------------------------------


-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/2788/#review3211
-----------------------------------------------------------


Overall I like it.  Please avoid non-essential format changes in large patches; when reviewing
it's like trying to run a marathon with a pebble in your shoe.  There needs to be quite a
bit of unit test coverage on the new classes.  Most of them should be amenable to straight-up
unit tests rather than ZK-involved integration tests.


http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/bsp/CentralizedServiceWorker.java
<https://reviews.apache.org/r/2788/#comment7131>

    return type has changed. javadoc needs updated.



http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/SimpleMutateGraphVertex.java
<https://reviews.apache.org/r/2788/#comment7152>

    switch statement?



http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/SuperstepHashPartitioner.java
<https://reviews.apache.org/r/2788/#comment7156>

    This seems like a dangerous thing to leave lying around, even for example purposes.  Is
there another example that we can generate which might be more useful?



http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/VerifyMessage.java
<https://reviews.apache.org/r/2788/#comment7158>

    indent +4



http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/VerifyMessage.java
<https://reviews.apache.org/r/2788/#comment7159>

    need debugging guards here and +2 lines



http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/VerifyMessage.java
<https://reviews.apache.org/r/2788/#comment7161>

    log guard



http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/VerifyMessage.java
<https://reviews.apache.org/r/2788/#comment7162>

    ditto



http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BspServiceWorker.java
<https://reviews.apache.org/r/2788/#comment7168>

    typo. send -> sent



http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BspServiceWorker.java
<https://reviews.apache.org/r/2788/#comment7173>

    typo. sent -> send



http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/GraphPartitioner.java
<https://reviews.apache.org/r/2788/#comment7178>

    Better to call it a factory?



http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/HashWorkerPartitioner.java
<https://reviews.apache.org/r/2788/#comment7180>

    typo: dependant -> dependent



http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/PartitionBalancer.java
<https://reviews.apache.org/r/2788/#comment7182>

    rename: value -> totalValue, to be consistent with usage.



http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/RangeWorkerPartitioner.java
<https://reviews.apache.org/r/2788/#comment7185>

    I'm unclear on this.


- Jakob


On 2011-11-14 06:56:19, Avery Ching wrote:
bq.  
bq.  -----------------------------------------------------------
bq.  This is an automatically generated e-mail. To reply, visit:
bq.  https://reviews.apache.org/r/2788/
bq.  -----------------------------------------------------------
bq.  
bq.  (Updated 2011-11-14 06:56:19)
bq.  
bq.  
bq.  Review request for giraph.
bq.  
bq.  
bq.  Summary
bq.  -------
bq.  
bq.  Warning: This is a very large change!
bq.  
bq.  Vertex ranges no longer exist.  A generic partitioner handles the
bq.  division of vertex ids to partitions.  As a default, there is a
bq.  HashPartitioner and a HashRangePartitioner that will use the hashCode
bq.  of a Java object to decide which partition to place the vertex.
bq.  Developers can write their own algorithm to determine how to change
bq.  the partitioning as well as implement the assignment of partitions to
bq.  workers.  All vertices loaded from the input split are sent to the
bq.  owner of the partition rather than loaded locally.  This eliminates the
bq.  constraint that the vertices must be ordered in the input split.
bq.  
bq.  The checkpoint format has been changed to suit the new partition
bq.  style.  Checkpoints are now a lot simpler.  The master will assign
bq.  partitions and the workers will only load their own partitions from
bq.  the checkpoint.
bq.  
bq.  Unfortunately, the vertex range implementation was baked into almost
bq.  every aspect of the code (hence the ridiculous size of this diff).
bq.  But now it should be flexible to support several different graph
bq.  partitioning schemes (i.e. hash-based, hash-ranged-based, and for
bq.  special cases, fully ranged-based).
bq.  
bq.  Sorry for the long delay, but this way pretty involved.
bq.  
bq.  
bq.  This addresses bug GIRAPH-11.
bq.      https://issues.apache.org/jira/browse/GIRAPH-11
bq.  
bq.  
bq.  Diffs
bq.  -----
bq.  
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/pom.xml 1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/benchmark/PseudoRandomVertexInputFormat.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/bsp/CentralizedServiceWorker.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/comm/BasicRPCCommunications.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/comm/CommunicationsInterface.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/comm/RPCCommunications.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/comm/ServerInterface.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/comm/WorkerCommunications.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/GeneratedVertexInputFormat.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/GeneratedVertexReader.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/MaxAggregator.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/MinAggregator.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/SimpleMutateGraphVertex.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/SimpleSuperstepVertex.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/SuperstepBalancer.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/SuperstepHashPartitioner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/VerifyMessage.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/AutoBalancer.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BasicVertex.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BasicVertexRangeBalancer.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BspService.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BspServiceMaster.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BspServiceWorker.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BspUtils.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/GiraphJob.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/GlobalStats.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/GraphMapper.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/GraphState.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/LongDoubleFloatDoubleVertex.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/MutableVertex.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/StaticBalancer.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/Vertex.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/VertexEdgeCount.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/VertexRange.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/VertexRangeBalancer.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/WorkerInfo.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/BasicPartitionOwner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/GraphPartitioner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/HashMasterPartitioner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/HashPartitioner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/HashRangePartitioner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/HashRangeWorkerPartitioner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/HashWorkerPartitioner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/MasterGraphPartitioner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/Partition.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/PartitionBalancer.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/PartitionExchange.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/PartitionOwner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/PartitionStats.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/PartitionUtils.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/RangeMasterPartitioner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/RangePartitionOwner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/RangePartitionStats.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/RangePartitioner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/RangeSplitHint.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/RangeWorkerPartitioner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/WorkerGraphPartitioner.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/utils/WritableUtils.java
PRE-CREATION 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/zk/ZooKeeperExt.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/test/java/org/apache/giraph/TestMutateGraphVertex.java
1201607 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/test/java/org/apache/giraph/TestVertexRangeBalancer.java
1186590 
bq.    http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/test/java/org/apache/giraph/TestVertexRangeBalancer.java
1201607 
bq.  
bq.  Diff: https://reviews.apache.org/r/2788/diff
bq.  
bq.  
bq.  Testing
bq.  -------
bq.  
bq.  local and MR unittests.  Added some simple unittests for testing the out-of-order input
splits and other balancing algorithms.
bq.  
bq.  
bq.  Thanks,
bq.  
bq.  Avery
bq.  
bq.


                
> Improve the graph distribution of Giraph
> ----------------------------------------
>
>                 Key: GIRAPH-11
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-11
>             Project: Giraph
>          Issue Type: Improvement
>    Affects Versions: 0.70.0
>            Reporter: Avery Ching
>            Assignee: Avery Ching
>         Attachments: GIRAPH-11.2.diff, GIRAPH-11.3.diff, GIRAPH-11.diff
>
>
> Currently, Giraph assumes that the data from the VertexInputFormat is sorted.  If the
user data is not sorted by the vertex id, they must first run a MapReduce or Pig job to generate
a sorted dataset.  This is often a bit inconvenient.
> Giraph graph partitioning is currently range based and there are some advantages and
disadvantages of this approach.  The proposal of this JIRA would be to allow for both range
and hash based partitioning and provide more flexibility to the user.
> Design goals for the graph distribution:
> * Allow vertices to be unordered or unordered
> * Ability to repartition
> * Select the partitioning scheme based on user needs (i.e. hash or range based)
> * Ability to provide user-specific hints about partitions
> Hash-based partitioning
> * Good vertex balancing across ranges for random data
> * Bad at vertex id locality
> Range-based partitioning
> * Good at vertex id locality
> * Ability to split ranges easily
> * Can cause hotspots for hot ranges

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

Mime
View raw message