title: Avoid Shuffling with ReduceByKey in Spark
body: <p>I am taking the <em>coursera Course on Scala Spark</em>, and I am trying to optimize this snippet:</p>
  
  <pre><code>val indexedMeansG = vectors.                                                                                                                                                                 
         map(v =&gt; findClosest(v, means) -&gt; v).                                                                                                                                                      
         groupByKey.mapValues(averageVectors)
  </code></pre>
  
  <p><code>vectors</code> is a <code>RDD[(Int, Int)]</code>, in order to see the list of dependencies and the lineage of the RDD I've used:</p>
  
  <pre><code>println(s"""GroupBy:                                                                                                                                                                         
               | Deps: ${indexedMeansG.dependencies.size}                                                                                                                                           
               | Deps: ${indexedMeansG.dependencies}                                                                                                                                                
               | Lineage: ${indexedMeansG.toDebugString}""".stripMargin)
  </code></pre>
  
  <p>Which shows this:</p>
  
  <pre><code>/* GroupBy:                                                                                                                                                                                  
     * Deps: 1                                                                                                                                                                                      
     * Deps: List(org.apache.spark.OneToOneDependency@44d1924)                                                                                                                                      
     * Lineage: (6) MapPartitionsRDD[18] at mapValues at StackOverflow.scala:207 []                                                                                                                 
     *  ShuffledRDD[17] at groupByKey at StackOverflow.scala:207 []                                                                                                                                 
     * +-(6) MapPartitionsRDD[16] at map at StackOverflow.scala:206 []                                                                                                                              
     *  MapPartitionsRDD[13] at map at StackOverflow.scala:139 []                                                                                                                                   
     *      CachedPartitions: 6; MemorySize: 84.0 MB; ExternalBlockStoreSize: 0.0 B; DiskSize: 0.0 B                                                                                                
     *  MapPartitionsRDD[12] at values at StackOverflow.scala:116 []                                                                                                                                
     *  MapPartitionsRDD[11] at mapValues at StackOverflow.scala:115 []                                                                                                                             
     *  MapPartitionsRDD[10] at groupByKey at StackOverflow.scala:92 []                                                                                                                             
     *  MapPartitionsRDD[9] at join at StackOverflow.scala:91 []                                                                                                                                    
     *  MapPartitionsRDD[8] at join at StackOverflow.scala:91 []                                                                                                                                    
     *  CoGroupedRDD[7] at join at StackOverflow.scala:91 []                                                                                                                                        
     *    +-(6) MapPartitionsRDD[4] at map at StackOverflow.scala:88 []                                                                                                                             
     *  |  MapPartitionsRDD[3] at filter at StackOverflow.scala:88 []                                                                                                                               
     *  |  MapPartitionsRDD[2] at map at StackOverflow.scala:69 []                                                                                                                                  
     *  |  src/main/resources/stackoverflow/stackoverflow.csv MapPartitionsRDD[1] at textFile at StackOverflow.scala:23 []                                                                          
     *  |  src/main/resources/stackoverflow/stackoverflow.csv HadoopRDD[0] at textFile at StackOverflow.scala:23 []                                                                                 
     *    +-(6) MapPartitionsRDD[6] at map at StackOverflow.scala:89 []                                                                                                                             
     *  MapPartitionsRDD[5] at filter at StackOverflow.scala:89 []                                                                                                                                  
     *  MapPartitionsRDD[2] at map at StackOverflow.scala:69 []                                                                                                                                     
     *  src/main/resources/stackoverflow/stackoverflow.csv MapPartitionsRDD[1] at textFile at StackOverflow.scala:23 []                                                                             
     *  src/main/resources/stackoverflow/stackoverflow.csv HadoopRDD[0] at textFile at StackOverflow.scala:23 [] */
  </code></pre>
  
  <p>From this <code>List(org.apache.spark.OneToOneDependency@44d1924)</code> I deduced no shuffling is being done, Am I right? However, below <code>ShuffledRDD[17]</code> is printed, which means in fact there is shuffling. </p>
  
  <p>I've tried to replace that <code>groupByKey</code> call with a <code>reduceByKey</code>, like this:</p>
  
  <pre><code>val indexedMeansR = vectors.                                                                                                                                                              
        map(v =&gt; findClosest(v, means) -&gt; v).                                                                                                                                                   
        reduceByKey((a, b) =&gt; (a._1 + b._1) / 2 -&gt; (a._2 + b._2) / 2)
  </code></pre>
  
  <p>And its dependencies and lineage are:</p>
  
  <pre><code>/* ReduceBy:                                                                                                                                                                                 
     * Deps: 1                                                                                                                                                                                      
     * Deps: List(org.apache.spark.ShuffleDependency@4d5e813f)                                                                                                                                      
     * Lineage: (6) ShuffledRDD[17] at reduceByKey at StackOverflow.scala:211 []                                                                                                                    
     * +-(6) MapPartitionsRDD[16] at map at StackOverflow.scala:210 []                                                                                                                              
     *  MapPartitionsRDD[13] at map at StackOverflow.scala:139 []                                                                                                                                   
     *      CachedPartitions: 6; MemorySize: 84.0 MB; ExternalBlockStoreSize: 0.0 B; DiskSize: 0.0 B                                                                                                
     *  MapPartitionsRDD[12] at values at StackOverflow.scala:116 []                                                                                                                                
     *  MapPartitionsRDD[11] at mapValues at StackOverflow.scala:115 []                                                                                                                             
     *  MapPartitionsRDD[10] at groupByKey at StackOverflow.scala:92 []                                                                                                                             
     *  MapPartitionsRDD[9] at join at StackOverflow.scala:91 []                                                                                                                                    
     *  MapPartitionsRDD[8] at join at StackOverflow.scala:91 []                                                                                                                                    
     *  CoGroupedRDD[7] at join at StackOverflow.scala:91 []                                                                                                                                        
     *    +-(6) MapPartitionsRDD[4] at map at StackOverflow.scala:88 []                                                                                                                             
     *  |  MapPartitionsRDD[3] at filter at StackOverflow.scala:88 []                                                                                                                               
     *  |  MapPartitionsRDD[2] at map at StackOverflow.scala:69 []                                                                                                                                  
     *  |  src/main/resources/stackoverflow/stackoverflow.csv MapPartitionsRDD[1] at textFile at StackOverflow.scala:23 []                                                                          
     *  |  src/main/resources/stackoverflow/stackoverflow.csv HadoopRDD[0] at textFile at StackOverflow.scala:23 []                                                                                 
     *    +-(6) MapPartitionsRDD[6] at map at StackOverflow.scala:89 []                                                                                                                             
     *  MapPartitionsRDD[5] at filter at StackOverflow.scala:89 []                                                                                                                                  
     *  MapPartitionsRDD[2] at map at StackOverflow.scala:69 []                                                                                                                                     
     *  src/main/resources/stackoverflow/stackoverflow.csv MapPartitionsRDD[1] at textFile at StackOverflow.scala:23 []                                                                             
     *  src/main/resources/stackoverflow/stackoverflow.csv HadoopRDD[0] at textFile at StackOverflow.scala:23 [] */
  </code></pre>
  
  <p>This time, the dependency is <code>ShuffleDependency</code> and I am not able to understand why.</p>
  
  <p>Since the RDD is a pair which <strong>keys are Ints</strong>, and therefore have an ordering,  I've also tried to modified the partitioner and use a <code>RangePartitioner</code>, but it doesn't improve either</p>