[jira] [Commented] (GIRAPH-11) Improve the graph distribution of Giraph
[ https://issues.apache.org/jira/browse/GIRAPH-11?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13150869#comment-13150869 ] Hudson commented on GIRAPH-11: -- Integrated in Giraph-trunk-Commit #34 (See [https://builds.apache.org/job/Giraph-trunk-Commit/34/]) GIRAPH-88: Message count not updated properly after GIRAPH-11. (aching) aching : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVNview=revrev=1202455 Files : * /incubator/giraph/trunk/CHANGELOG * /incubator/giraph/trunk/src/main/java/org/apache/giraph/bsp/CentralizedServiceWorker.java * /incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BspServiceWorker.java * /incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/GraphMapper.java * /incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/partition/RangeWorkerPartitioner.java 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.4.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
[jira] [Commented] (GIRAPH-11) Improve the graph distribution of Giraph
[ https://issues.apache.org/jira/browse/GIRAPH-11?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13150095#comment-13150095 ] Jakob Homan commented on GIRAPH-11: --- I think this is ready to go. Avery, just out of curiosity, beyond the MR unittests, have you run any test vertices on this? 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.4.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
[jira] [Commented] (GIRAPH-11) Improve the graph distribution of Giraph
[ https://issues.apache.org/jira/browse/GIRAPH-11?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13150099#comment-13150099 ] Jakob Homan commented on GIRAPH-11: --- +1 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.4.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
[jira] [Commented] (GIRAPH-11) Improve the graph distribution of Giraph
[ https://issues.apache.org/jira/browse/GIRAPH-11?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13149412#comment-13149412 ] Hyunsik Choi commented on GIRAPH-11: Avery, I'm sorry for delaying the review. Now, I'm digging your patch. That looks great! Based on this work, we can consider some advanced graph partitioner based on the number of edge-cuts on graph partitions. I need about one more day for more investigation because the patch is somewhat complicated for me :) Besides, for the deeper review, I would like to execute the some tests and trace them. Your patch needs the rebase. Could you rebase the patch? Thank you :) 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.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
[jira] [Commented] (GIRAPH-11) Improve the graph distribution of Giraph
[ https://issues.apache.org/jira/browse/GIRAPH-11?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13149471#comment-13149471 ] Hyunsik Choi commented on GIRAPH-11: Thank you for rebase. 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.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
[jira] [Commented] (GIRAPH-11) Improve the graph distribution of Giraph
[ https://issues.apache.org/jira/browse/GIRAPH-11?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13148187#comment-13148187 ] Hyunsik Choi commented on GIRAPH-11: That's a huge patch :) I have just started to explore your patch. I will leave some comments (maybe tomorrow). 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.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
[jira] [Commented] (GIRAPH-11) Improve the graph distribution of Giraph
[ https://issues.apache.org/jira/browse/GIRAPH-11?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13146944#comment-13146944 ] jirapos...@reviews.apache.org commented on GIRAPH-11: - --- This is an automatically generated e-mail. To reply, visit: https://reviews.apache.org/r/2788/ --- Review request for giraph. Summary --- Warning: This is a very large change! Vertex ranges no longer exist. A generic partitioner handles the division of vertex ids to partitions. As a default, there is a HashPartitioner and a HashRangePartitioner that will use the hashCode of a Java object to decide which partition to place the vertex. Developers can write their own algorithm to determine how to change the partitioning as well as implement the assignment of partitions to workers. All vertices loaded from the input split are sent to the owner of the partition rather than loaded locally. This eliminates the constraint that the vertices must be ordered in the input split. The checkpoint format has been changed to suit the new partition style. Checkpoints are now a lot simpler. The master will assign partitions and the workers will only load their own partitions from the checkpoint. Unfortunately, the vertex range implementation was baked into almost every aspect of the code (hence the ridiculous size of this diff). But now it should be flexible to support several different graph partitioning schemes (i.e. hash-based, hash-ranged-based, and for special cases, fully ranged-based). Sorry for the long delay, but this way pretty involved. This addresses bug GIRAPH-11. https://issues.apache.org/jira/browse/GIRAPH-11 Diffs - http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/bsp/CentralizedServiceWorker.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/comm/BasicRPCCommunications.java 1196639 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/comm/CommunicationsInterface.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/comm/RPCCommunications.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/comm/ServerInterface.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/comm/WorkerCommunications.java 1196639 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/GeneratedVertexInputFormat.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/GeneratedVertexReader.java 1196639 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/MaxAggregator.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/MinAggregator.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/SimpleMutateGraphVertex.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/SimpleSuperstepVertex.java 1196639 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/SuperstepBalancer.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/SuperstepHashPartitioner.java PRE-CREATION http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/examples/VerifyMessage.java PRE-CREATION http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/AutoBalancer.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BasicVertex.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BasicVertexRangeBalancer.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BspService.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BspServiceMaster.java 1196639 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BspServiceWorker.java 1198972 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/BspUtils.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/GiraphJob.java 1199643 http://svn.apache.org/repos/asf/incubator/giraph/trunk/src/main/java/org/apache/giraph/graph/GlobalStats.java PRE-CREATION
[jira] [Commented] (GIRAPH-11) Improve the graph distribution of Giraph
[ https://issues.apache.org/jira/browse/GIRAPH-11?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13147194#comment-13147194 ] Jake Mannix commented on GIRAPH-11: --- wow, there's a monster diff! I'm glad I don't have any outstanding patches to get clobbered! 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.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
[jira] [Commented] (GIRAPH-11) Improve the graph distribution of Giraph
[ https://issues.apache.org/jira/browse/GIRAPH-11?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13147226#comment-13147226 ] Avery Ching commented on GIRAPH-11: --- I started it so long ago that the merge was brutal for me. =) 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.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
[jira] [Commented] (GIRAPH-11) Improve the graph distribution of Giraph
[ https://issues.apache.org/jira/browse/GIRAPH-11?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13106839#comment-13106839 ] Avery Ching commented on GIRAPH-11: --- Hi Severin, as far as getting started, feel free to take a look at any of the open issues (https://issues.apache.org/jira/secure/IssueNavigator.jspa?reset=truejqlQuery=project+%3D+GIRAPH+AND+status+%3D+Open+ORDER+BY+priority+DESCmode=hide) that are unassigned. Also, if you think of any interesting features to add, file a JIRA. We'd be happy to have you contribute =). Improve the graph distribution of Giraph Key: GIRAPH-11 URL: https://issues.apache.org/jira/browse/GIRAPH-11 Project: Giraph Issue Type: Improvement Reporter: Avery Ching Assignee: Avery Ching 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. For more information on JIRA, see: http://www.atlassian.com/software/jira
