[
https://issues.apache.org/jira/browse/SPARK-21782?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16131865#comment-16131865
]
Sergey Serebryakov commented on SPARK-21782:
--------------------------------------------
I played with Scala's `hashing.byteswap32()` and it seems to be working pretty
well. Not perfect, you can still see "patterns" in the size distribution, but
it's much better than before.
{code}
scala> new ShuffledRDD[Int, Int, Int](sc.parallelize(0 until 1000,
250).mapPartitionsWithIndex(distributePartition), new
HashPartitioner(64)).glom().map(_.length).collect()
res50: Array[Int] = Array(26, 25, 18, 15, 14, 11, 13, 16, 17, 19, 21, 19, 18,
18, 14, 13, 12, 8, 14, 15, 16, 17, 13, 13, 17, 22, 22, 20, 18, 14, 14, 15, 12,
14, 13, 14, 13, 10, 10, 10, 11, 12, 11, 10, 9, 13, 16, 19, 21, 19, 17, 14, 14,
13, 14, 16, 16, 15, 16, 16, 16, 20, 24, 25)
{code}
> Repartition creates skews when numPartitions is a power of 2
> ------------------------------------------------------------
>
> Key: SPARK-21782
> URL: https://issues.apache.org/jira/browse/SPARK-21782
> Project: Spark
> Issue Type: Bug
> Components: Spark Core
> Affects Versions: 2.2.0
> Reporter: Sergey Serebryakov
> Labels: repartition
> Attachments: Screen Shot 2017-08-16 at 3.40.01 PM.png
>
>
> *Problem:*
> When an RDD (particularly with a low item-per-partition ratio) is
> repartitioned to {{numPartitions}} = power of 2, the resulting partitions are
> very uneven-sized. This affects both {{repartition()}} and
> {{coalesce(shuffle=true)}}.
> *Steps to reproduce:*
> {code}
> $ spark-shell
> scala> sc.parallelize(0 until 1000,
> 250).repartition(64).glom().map(_.length).collect()
> res0: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> 0, 0, 0, 0, 144, 250, 250, 250, 106, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
> {code}
> *Explanation:*
> Currently, the [algorithm for
> repartition|https://github.com/apache/spark/blob/v2.2.0/core/src/main/scala/org/apache/spark/rdd/RDD.scala#L450]
> (shuffle-enabled coalesce) is as follows:
> - for each initial partition {{index}}, generate {{position}} as {{(new
> Random(index)).nextInt(numPartitions)}}
> - then, for element number {{k}} in initial partition {{index}}, put it in
> the new partition {{position + k}} (modulo {{numPartitions}}).
> So, essentially elements are smeared roughly equally over {{numPartitions}}
> buckets - starting from the one with number {{position+1}}.
> Note that a new instance of {{Random}} is created for every initial partition
> {{index}}, with a fixed seed {{index}}, and then discarded. So the
> {{position}} is deterministic for every {{index}} for any RDD in the world.
> Also, [{{nextInt(bound)}}
> implementation|http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/Random.java/#393]
> has a special case when {{bound}} is a power of 2, which is basically taking
> several highest bits from the initial seed, with only a minimal scrambling.
> Due to deterministic seed, using the generator only once, and lack of
> scrambling, the {{position}} values for power-of-two {{numPartitions}} always
> end up being almost the same regardless of the {{index}}, causing some
> buckets to be much more popular than others. So, {{repartition}} will in fact
> intentionally produce skewed partitions even when before the partition were
> roughly equal in size.
> The behavior seems to have been introduced in SPARK-1770 by
> https://github.com/apache/spark/pull/727/
> {quote}
> The load balancing is not perfect: a given output partition
> can have up to N more elements than the average if there are N input
> partitions. However, some randomization is used to minimize the
> probabiliy that this happens.
> {quote}
> Another related ticket: SPARK-17817 -
> https://github.com/apache/spark/pull/15445
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
