[SPARK-1113] External Spilling Bug - hash collision causes NoSuchElementException

• Type: Bug
• Status: Resolved
• Priority: Blocker
• Resolution: Fixed
• Affects Version/s: 0.9.0
• Fix Version/s: 0.9.1, 1.0.0
• Component/s: Shuffle, Spark Core
• Assignee: Andrew Or
• Reporter: Andrew Or
• Created: 20/Feb/14 15:53
• Updated: 09/Mar/14 17:43
• Resolved: 22/Feb/14 17:00

Description

When reading KV pairs back from disk, ExternalAppendOnlyMap maintains a StreamBuffer for each spilled file. These StreamBuffers are ordered by key hash code, and a hash of Int.MAX_VALUE signifies that the corresponding StreamBuffer is empty.

However, Int.MAX_VALUE is a perfectly legitimate hash value. If there exists a key with this value, then ExternalAppendOnlyMap does not differentiate between empty StreamBuffers and StreamBuffers that contain only this key. As a result, a NoSuchElementException is thrown - https://github.com/apache/incubator-spark/blob/95d28ff3d0d20d9c583e184f9e2c5ae842d8a4d9/core/src/main/scala/org/apache/spark/util/collection/ExternalAppendOnlyMap.scala#L304.

java.util.NoSuchElementException (java.util.NoSuchElementException)
org.apache.spark.util.collection.ExternalAppendOnlyMap$ExternalIterator.next(ExternalAppendOnlyMap.scala:277)
org.apache.spark.util.collection.ExternalAppendOnlyMap$ExternalIterator.next(ExternalAppendOnlyMap.scala:212)
org.apache.spark.InterruptibleIterator.next(InterruptibleIterator.scala:29)

Issue Links

• is duplicated by: SPARK-1045 ExternalAppendOnlyMap Iterator throw no such element on joining two large rdd