GitHub user andrewor14 opened a pull request:
https://github.com/apache/incubator-spark/pull/624
External spilling - fix Int.MaxValue hash code collision bug
The original poster of this bug is @guojc, who opened a PR that preceded
this one at https://github.com/apache/incubator-spark/pull/612.
ExternalAppendOnlyMap uses key hash code to order the buffer streams from
which spilled files are read back into memory. When a buffer stream is empty,
the default hash code for that stream is equal to Int.MaxValue. This is,
however, a perfectly legitimate candidate for a key hash code. When reading
from a spilled map containing such a key, a hash collision may occur, in which
case we attempt to read from an empty stream and throw NoSuchElementException.
The fix is to maintain the invariant that empty buffer streams are never
added back to the queue to be considered. This guarantees that we never read
from an empty buffer stream, ever again.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/andrewor14/incubator-spark spilling-bug
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/incubator-spark/pull/624.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #624
----
commit 21c1a39ebe7d0f10519621f3ef54aa6e89c08441
Author: Andrew Or <andrewo...@gmail.com>
Date: 2014-02-21T02:04:27Z
Add hash collision tests to ExternalAppendOnlyMapSuite
As of now, the test "spilling with hash collisions using the Int.MaxValue
key" fails.
Fixing this behavior is the main goal of this PR.
commit c11f03b6e6e82617a826dc3acbd09a52760f143b
Author: Andrew Or <andrewo...@gmail.com>
Date: 2014-02-21T02:58:18Z
Fix Int.MaxValue hash collision bug in ExternalAppendOnlyMap
The solution is to maintain the invariant that mergeHeap contains only
non-empty
StreamBuffer's at the time next() is called.
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. To do so, please top-post your response.
If your project does not have this feature enabled and wishes so, or if the
feature is enabled but not working, please contact infrastructure at
infrastruct...@apache.org or file a JIRA ticket with INFRA.
---
