Spark: Unterschied der Semantik zwischen reduce und reduceByKey

Question

In der Dokumentation von Spark heißt es, dass die RDDs-Methode reduce eine assoziative UND-kommutative Binärfunktion benötigt.

Die Methode reduceByKey erfordert jedoch nur eine assoziative Binärfunktion.

sc.textFile("file4kB", 4) 

Ich habe einige Tests gemacht, und anscheinend ist es das Verhalten, das ich bekomme. Warum dieser Unterschied? Warum stellt reduceByKey sicher, dass die Binärfunktion immer in einer bestimmten Reihenfolge angewendet wird (um die fehlende Kommutativität auszugleichen), wenn reduce nicht funktioniert?

Beispiel, wenn eine Last einige (kleine) Text mit 4 Partitionen (Minimum):

val r = sc.textFile("file4k", 4) 

dann:

r.reduce(_ + _) 

einen String zurückgibt, wo Teile, die nicht immer in der gleichen Reihenfolge sind, während:

r.map(x => (1,x)).reduceByKey(_ + _).first 

gibt immer die gleiche Zeichenfolge (wo alles in der gleichen Reihenfolge als in der ursprünglichen ist l Datei).

(Ich überprüft mit r.glom und der Dateiinhalt ist in der Tat verteilt über 4 Partitionen, es gibt keine leere Partition).

Answer 1

Soweit es mich betrifft, ist dies ein Fehler in der Dokumentation und Ergebnisse, die Sie sehen, sind nur nebensächlich. Praxis, other resources und ein einfaches analysis of the code zeigen, dass die Funktion, die an reduceByKey übergeben wird, nicht nur assoziativ sondern auch kommutativ sein sollte.

• Praxis - während es wie die Reihenfolge sieht in einem lokalen Modus beibehalten wird, ist es nicht mehr der Fall, wenn Sie Funken auf einem Cluster ausgeführt werden, einschließlich Standalone-Modus.

• andere Ressourcen - zu zitieren Data Exploration Using Spark von AmpCamp 3:

  Es ist eine bequeme Methode reduceByKey Spark für genau dieses Muster genannt. Beachten Sie, dass das zweite Argument für reduceByKey die Anzahl der zu verwendenden Reduzierungen bestimmt. Standardmäßig geht Spark davon aus, dass die Reduzierungsfunktion kommutativ und assoziativ ist und Combiner auf der Mapper-Seite anwendet.

• Code - reduceByKey wird mit combineByKeyWithClassTag implementiert und schafft ShuffledRDD. Da Spark nicht garantiert, dass die Reihenfolge nach dem Mischen die einzige Möglichkeit zur Wiederherstellung bietet, würde es sein, einige Metadaten an die teilweise reduzierten Datensätze anzuhängen. Soweit ich das beurteilen kann, passiert nichts dergleichen.

Auf einer seitlichen Anmerkung reduce wie es in PySpark umgesetzt wird, wird mit einer Funktion gut funktionieren, die nur kommutativ ist. Es ist natürlich nur ein Detail einer Implementierung und kein Teil des Vertrages.

Answer 2

Gemäß der Codedokumentation, vor kurzem aktualisiert/korrigiert.(thanks @ zero323):

reduceByKey führt die Werte für jede Taste mit einer assoziativen und kommutativen Reduzierungsfunktion zusammen. Dies führt auch das Zusammenführen lokal auf jedem Mapper durch, bevor Ergebnisse an einen Reduzierer gesendet werden, ähnlich einem "Kombinierer" in MapReduce.

So war es in der Tat tatsächlich ein Dokumentationsfehler wie @ Zero323 in seiner Antwort darauf hingewiesen.

können Sie überprüfen die folgenden Links, um den Code, um sicherzustellen:

• https://github.com/apache/spark/blob/master/core/src/main/scala/org/apache/spark/rdd/PairRDDFunctions.scala#L304

• https://github.com/apache/spark/blob/master/python/pyspark/rdd.py#L1560