You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@giraph.apache.org by "Eli Reisman (JIRA)" <ji...@apache.org> on 2012/07/12 19:41:33 UTC

[jira] [Created] (GIRAPH-250) Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.

Eli Reisman created GIRAPH-250:
----------------------------------

             Summary: Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.
                 Key: GIRAPH-250
                 URL: https://issues.apache.org/jira/browse/GIRAPH-250
             Project: Giraph
          Issue Type: Improvement
          Components: bsp, graph, zookeeper
    Affects Versions: 0.2.0
            Reporter: Eli Reisman
            Assignee: Eli Reisman
            Priority: Minor
             Fix For: 0.2.0
         Attachments: GIRAPH-250-1.patch

In the job logs it has become clear that workers trying to scan for master-created Znodes indicating an InputSplit is available to claim (and read) are starting very similar lists of znode names to scan (iterating from 0 through the list all at the same time)

what you see in the logs is lots of misses, followed by finally a hit somewhere. By using iterating the list, but starting from a different spot for each worker (see the patch its a simple change using the hash code of the worker hostname + index and mod that by the size of the list of possible splits to claim) we (mostly) iterate starting from different parts of the input split list each worker gets, thereby lowering contention dramatically and ensuring everyone will more quickly claim (at least their first) input split. This seems to work very well so far.

passes mvn verify etc.


--
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-250) Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.

Posted by "Eli Reisman (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/GIRAPH-250?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13413260#comment-13413260 ] 

Eli Reisman commented on GIRAPH-250:
------------------------------------

this one needs a quick fix or two now that I have tried it on the cluster. Will upload fixed patch momentarily...

                
> Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.
> -------------------------------------------------------------------------------------------
>
>                 Key: GIRAPH-250
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-250
>             Project: Giraph
>          Issue Type: Improvement
>          Components: bsp, graph, zookeeper
>    Affects Versions: 0.2.0
>            Reporter: Eli Reisman
>            Assignee: Eli Reisman
>            Priority: Minor
>             Fix For: 0.2.0
>
>         Attachments: GIRAPH-250-1.patch
>
>
> In the job logs it has become clear that workers trying to scan for master-created Znodes indicating an InputSplit is available to claim (and read) are starting very similar lists of znode names to scan (iterating from 0 through the list all at the same time)
> what you see in the logs is lots of misses, followed by finally a hit somewhere. By using iterating the list, but starting from a different spot for each worker (see the patch its a simple change using the hash code of the worker hostname + index and mod that by the size of the list of possible splits to claim) we (mostly) iterate starting from different parts of the input split list each worker gets, thereby lowering contention dramatically and ensuring everyone will more quickly claim (at least their first) input split. This seems to work very well so far.
> passes mvn verify etc.

--
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] [Updated] (GIRAPH-250) Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.

Posted by "Eli Reisman (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/GIRAPH-250?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Eli Reisman updated GIRAPH-250:
-------------------------------

    Attachment: GIRAPH-250-2.patch

Sorry, this is good to go now. Initial cluster tests suggest this + GIRAPH 246 + GIRAPH 247 patches dramatically speed up INPUT_SUPERSTEP!
                
> Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.
> -------------------------------------------------------------------------------------------
>
>                 Key: GIRAPH-250
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-250
>             Project: Giraph
>          Issue Type: Improvement
>          Components: bsp, graph, zookeeper
>    Affects Versions: 0.2.0
>            Reporter: Eli Reisman
>            Assignee: Eli Reisman
>            Priority: Minor
>             Fix For: 0.2.0
>
>         Attachments: GIRAPH-250-1.patch, GIRAPH-250-2.patch
>
>
> In the job logs it has become clear that workers trying to scan for master-created Znodes indicating an InputSplit is available to claim (and read) are starting very similar lists of znode names to scan (iterating from 0 through the list all at the same time)
> what you see in the logs is lots of misses, followed by finally a hit somewhere. By using iterating the list, but starting from a different spot for each worker (see the patch its a simple change using the hash code of the worker hostname + index and mod that by the size of the list of possible splits to claim) we (mostly) iterate starting from different parts of the input split list each worker gets, thereby lowering contention dramatically and ensuring everyone will more quickly claim (at least their first) input split. This seems to work very well so far.
> passes mvn verify etc.

--
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] [Updated] (GIRAPH-250) Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.

Posted by "Eli Reisman (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/GIRAPH-250?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Eli Reisman updated GIRAPH-250:
-------------------------------

    Attachment: GIRAPH-250-3.patch

Found a small potential loophole in the case that the Math.abs(hashCode()) part of this comes up Integer.MIN_VALUE, fixed it. Probably not an issue, but better safe than sorry.

As for port # etc. I looked into it, but the distribution is very good in the first loop, and anyone who waits or gets a 2nd input split, the "available split" list has gotten so small by then that they would all hash to similar indexes anyway. But thats an excellent idea, Jakob mentioned it too.

                
> Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.
> -------------------------------------------------------------------------------------------
>
>                 Key: GIRAPH-250
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-250
>             Project: Giraph
>          Issue Type: Improvement
>          Components: bsp, graph, zookeeper
>    Affects Versions: 0.2.0
>            Reporter: Eli Reisman
>            Assignee: Eli Reisman
>            Priority: Minor
>             Fix For: 0.2.0
>
>         Attachments: GIRAPH-250-1.patch, GIRAPH-250-2.patch, GIRAPH-250-3.patch
>
>
> In the job logs it has become clear that workers trying to scan for master-created Znodes indicating an InputSplit is available to claim (and read) are starting very similar lists of znode names to scan (iterating from 0 through the list all at the same time)
> what you see in the logs is lots of misses, followed by finally a hit somewhere. By using iterating the list, but starting from a different spot for each worker (see the patch its a simple change using the hash code of the worker hostname + index and mod that by the size of the list of possible splits to claim) we (mostly) iterate starting from different parts of the input split list each worker gets, thereby lowering contention dramatically and ensuring everyone will more quickly claim (at least their first) input split. This seems to work very well so far.
> passes mvn verify etc.

--
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-250) Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.

Posted by "Eli Reisman (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/GIRAPH-250?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13428536#comment-13428536 ] 

Eli Reisman commented on GIRAPH-250:
------------------------------------

if we end up committing GIRAPH-275 then this is no longer needed, we can resolve this as 'won't fix.'
                
> Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.
> -------------------------------------------------------------------------------------------
>
>                 Key: GIRAPH-250
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-250
>             Project: Giraph
>          Issue Type: Improvement
>          Components: bsp, graph, zookeeper
>    Affects Versions: 0.2.0
>            Reporter: Eli Reisman
>            Assignee: Eli Reisman
>            Priority: Minor
>             Fix For: 0.2.0
>
>         Attachments: GIRAPH-250-1.patch, GIRAPH-250-2.patch, GIRAPH-250-3.patch
>
>
> In the job logs it has become clear that workers trying to scan for master-created Znodes indicating an InputSplit is available to claim (and read) are starting very similar lists of znode names to scan (iterating from 0 through the list all at the same time)
> what you see in the logs is lots of misses, followed by finally a hit somewhere. By using iterating the list, but starting from a different spot for each worker (see the patch its a simple change using the hash code of the worker hostname + index and mod that by the size of the list of possible splits to claim) we (mostly) iterate starting from different parts of the input split list each worker gets, thereby lowering contention dramatically and ensuring everyone will more quickly claim (at least their first) input split. This seems to work very well so far.
> passes mvn verify etc.

--
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] [Updated] (GIRAPH-250) Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.

Posted by "Eli Reisman (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/GIRAPH-250?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Eli Reisman updated GIRAPH-250:
-------------------------------

    Attachment: GIRAPH-250-1.patch
    
> Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.
> -------------------------------------------------------------------------------------------
>
>                 Key: GIRAPH-250
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-250
>             Project: Giraph
>          Issue Type: Improvement
>          Components: bsp, graph, zookeeper
>    Affects Versions: 0.2.0
>            Reporter: Eli Reisman
>            Assignee: Eli Reisman
>            Priority: Minor
>             Fix For: 0.2.0
>
>         Attachments: GIRAPH-250-1.patch
>
>
> In the job logs it has become clear that workers trying to scan for master-created Znodes indicating an InputSplit is available to claim (and read) are starting very similar lists of znode names to scan (iterating from 0 through the list all at the same time)
> what you see in the logs is lots of misses, followed by finally a hit somewhere. By using iterating the list, but starting from a different spot for each worker (see the patch its a simple change using the hash code of the worker hostname + index and mod that by the size of the list of possible splits to claim) we (mostly) iterate starting from different parts of the input split list each worker gets, thereby lowering contention dramatically and ensuring everyone will more quickly claim (at least their first) input split. This seems to work very well so far.
> passes mvn verify etc.

--
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-250) Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.

Posted by "Alessandro Presta (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/GIRAPH-250?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13416999#comment-13416999 ] 

Alessandro Presta commented on GIRAPH-250:
------------------------------------------

Good idea to use hashing here. Are you getting a good distribution across the whole list or mainly avoiding collisions on the first split?

If you use the number of workers and some sort of incremental worker id (I'm not familiar, but maybe WorkerInfo#getPartitionId()?), you may even be deterministic and assign equally-spaced starting points to the workers, and see how it performs.

Either way, this already sounds like a good improvement!

Can't comment on the wait interval, if 10 seconds gives you better results on a few different scenarios, then it's probably sensible.
                
> Let workers contending for InputSplits during INPUT_SUPERSTEP guess better, choose quicker.
> -------------------------------------------------------------------------------------------
>
>                 Key: GIRAPH-250
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-250
>             Project: Giraph
>          Issue Type: Improvement
>          Components: bsp, graph, zookeeper
>    Affects Versions: 0.2.0
>            Reporter: Eli Reisman
>            Assignee: Eli Reisman
>            Priority: Minor
>             Fix For: 0.2.0
>
>         Attachments: GIRAPH-250-1.patch, GIRAPH-250-2.patch
>
>
> In the job logs it has become clear that workers trying to scan for master-created Znodes indicating an InputSplit is available to claim (and read) are starting very similar lists of znode names to scan (iterating from 0 through the list all at the same time)
> what you see in the logs is lots of misses, followed by finally a hit somewhere. By using iterating the list, but starting from a different spot for each worker (see the patch its a simple change using the hash code of the worker hostname + index and mod that by the size of the list of possible splits to claim) we (mostly) iterate starting from different parts of the input split list each worker gets, thereby lowering contention dramatically and ensuring everyone will more quickly claim (at least their first) input split. This seems to work very well so far.
> passes mvn verify etc.

--
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