Was macht Reduce bei MapReduce?

[burli]

Ich lese mich derzeit in CouchDB ein und bin mir noch nicht so ganz sicher, wofür die Reduce Funktion so alles zu gebrauchen ist. Bisher beschränken sich die Funktionen, die ich gesehen habe, auf das Zählen von irgendwelchen Werten oder das Zusammenrechnen von Werten.

Ist das so in etwa die Funktion von Reduce? Oder kann man damit noch mehr machen? Es mangelt mir noch ein wenig an praktischen Beispielen.

[cofi]

Ja. Map ist so ziemlich identisch zur Pythonfunktion `map` und dasselbe gilt fuer Reduce und `reduce`. Das Konzept ist Jahrzehnte alt.

[BlackJack]

@burli: Damit kann man die Daten durch "zusammenrechnen" reduzieren. Also so in etwa wie die Aggregatfunktionen in SQL. Das sind in SQL ja im wesentlichen auch so Sachen wie ``COUNT()``, ``SUM()``, oder ``AVG()``.

Ergänzend zu cofi: Das Map in MapReduce ist ähnlich einer Kombination aus `map()` und `filter()` in Python.

[Hyperion]

Wobei der Sinn dahinter doch darin besteht, Daten nach bestimmten Regeln zu aggregieren oder auszusortieren, oder? Also ersetzt das reduce das "where", "group by" und "having" bei SQL in solchen schemalosen DBs. Zumindest habe ich das bisher so verstanden. So wie das "map" eben das "select ... from" ersetzt. Natürlich sind die Entsprechungen nicht identisch.

[burli]

Ja. Map ist so ziemlich identisch zur Pythonfunktion `map` und dasselbe gilt fuer Reduce und `reduce`. Das Konzept ist Jahrzehnte alt.

Ich muss zu meiner Schande gestehen, dass ich mit Map und Reduce in Python noch überhaupt nichts gemacht habe.

Das es Reduce in Python gibt wusste ich noch nicht einmal. :K Map kannte ich zumindest von Namen.
Ok, also hab ich Reduce zumindest richtig verstanden. Die Funktion soll nur einen Wert als Ergebnis liefern. Entweder wird irgendwas gezählt, irgend ein Mittelwert berechnet, irgendwas zusammenaddiert usw. Aber das Ergebnis ist immer ein Numerischer Wert?

[Hyperion]

Aber das Ergebnis ist immer ein Numerischer Wert?

Naja, Du hast doch in Python nicht nur Funktionen, die numerische Werte liefern! Insofern kann reduce auch irgend ein beliebiges Objekt liefern.

[burli]

Also ersetzt das reduce das "where", "group by" und "having" bei SQL in solchen schemalosen DBs.

Wenn das so sein sollte vermisse ich irgendwie die Möglichkeit, der Funktion einen Wert zu übergeben. group by ist es definitiv schonmal nicht, da die Sortierung bereits durch die Map Funktion des View gemacht wird. Möchte man nach einem anderen Wert sortieren muss man einen neuen View erstellen. Sortiert wird nämlich immer nach dem Key, der der Funktion emit() in der Map Funktion übergeben wird. So weit mein Kenntnisstand.

Auch irgendwelche Filterfunktionen werden eigentlich in der Map Funktion gemacht. Man übergibt dem View zum Beispiel startkey="f" und einen endkey="w", wenn man alle Buchstaben von "f" bis "w" aus einem Alphabet haben will.

Ich habe auch noch kein einziges Beispiel gesehen, in der eine Reduce Funktion (bei CouchDB) etwas anderes geliefert hat als einen numerischen Wert. Die einzige Funktion, die etwas anderes macht, hat als Untertitel "Don’t use this, it’s an example broken on purpose"

Also entweder hat sich mir der Sinn der Reduce Funktion in CouchDB damit erschlossen oder es gibt noch mehr Möglichkeiten, auf die aber bisher noch an keiner Stelle eingegangen wurde, die ich gelesen habe.

[BlackJack]

@burli: Du hast "alle" Möglichkeiten bei Reduce. Da kann mehr oder weniger beliebiger JavaScript-Code drin stehen, der auch alle möglichen Datentypen inklusive komplexer Objekt-Strukturen liefern kann und nicht nur numerische Werte.

Man könnte sich zum Beispiel vorstellen, dass die Dokumente ein Attribut haben was einen Pfad beschreibt und die Reduce-Funktion die mit Map selektierten Dokumente anhand dieses Pfades in eine verschachteltes Objekt aggregiert und die Rereduce-Funktion solche baumartigen Objektstrukturen "merge"t.

[burli]

@burli: Du hast "alle" Möglichkeiten bei Reduce. Da kann mehr oder weniger beliebiger JavaScript-Code drin stehen, der auch alle möglichen Datentypen inklusive komplexer Objekt-Strukturen liefern kann und nicht nur numerische Werte.

Dann verstehe ich diesen Satz nicht

If you don’t reduce your values to a single scalar value or a small fixed-sized object or array with a fixed number of scalar values of small sizes, you are probably doing it wrong.

Das widerspricht deiner Aussage von "komplexen Objekt-Strukturen", oder liege ich mal wieder falsch?

[BlackJack]

@burli: Da steht "probably". Bei meinem Baumstruktur-Beispiel bin ich natürlich davon ausgegangen, dass Map schon soweit vor gefiltert hat, dass man am Ende nicht den Inhalt der ganzen Datenbank in dem aggregierten Objekt stehen hat.

Ein anderes Beispiel für ein Objekt was kein einzelner Zahlenwert ist, wären vielleicht Dokumente die Personen mit einem Geburtsdatum speichern und man möchte wissen wieviele davon jeweils in eine bestimmte Altersgruppe fallen, so dass man am Ende nicht *eine* Zahl heraus bekommt, sondern so etwas wie:

Code: Alles auswählen

{
    'kinder': 10,
    'jugendliche': 62,
    'erwachsene': 177,
    'durchscnittsAlter': 42.23
}

Hier sieht man auch ganz gut, dass Reduce etwas macht, was man in einer SQL-Datenbank mit ``GROUP BY`` und Aggregatsfunktionen lösen würde.

[cofi]

Nein, nach meiner Lesart, hast du ihn da missverstanden. Map erzeugt in seinem Beispiel z.B. eine Liste von Bäumen und Reduce baut merge't sie zu einem Baum zusammen.
Nach meiner Auslegung passt das durchaus zu deinem Zitat, allerdings ist das auch nur eine Daumenregel. Ich wuerde es lieber so formulieren: "Wenn man Reduce so nutzt, dass sich die Objektmenge, die aus Map rausfaellt, nicht reduziert oder vereinfacht, benutzt man Reduce wahrscheinlich falsch".

Um das jetzt wieder auf dein Zitat von Blackjack zurueckzubeziehen: Nur weil man alle Moeglichkeiten hat, ist es nicht zwangslaeufig sinnvoll alle auszuschoepfen.

Verdammt, BlackJack war schneller, aber ich will das jetzt nicht wegschmeissen.

[burli]

Ok, das Beispiel von BlackJack würde ich jetzt auch noch als "array with a fixed number of scalar values of small sizes" bezeichnen. Von daher würde das noch in die Aussage passen.

Zugegeben, es ist etwas mehr als ein einzelner numerischer Wert, aber letzten Endes auch nur sum() und average()

Ich will es mal so formulieren. Vielleicht liege ich damit ja halbwegs richtig.

"Reduce dient dazu, eine Zusammenfassung bestimmter Informationen der Dokumente zu ermitteln und nicht, um bestimmte Dokumente zu erhalten"

Die SQL Funktionen Group By und Distict liefern im Prinzip ja auch nur eine Zusammenfassung. Aus einer Tabelle von Namen erhält man eine Liste, in der jeder Name nur einmal vorkommt.

[noisefloor]

Hallo,

@burli: lies' mal den Link auf FreiesMagazin, den ich im uu.de Forum gepostet habe. Da ist ziemlich am Ende ein ziemliches simples Beispiel, wie man Reduce anwendent.

Falls deine Frage dahin abzielt, ob man Reduce in CouchDB oft braucht bzw. du dir "Sorgen" machst, dass du nur Map und kein Reduce hast: Bei meiner Anwendungen und meinen "Spielereien" mit CouchDB habe ich sehr oft nur Map gebraucht, ohne Reduce.

Das ganze Ding heißt zwar "Map-Reduce" in den Views, aber man muss halt nicht immer 'reducen'.

Reduce kann in der Tat so was sein wie "summerieren" (z.B. zählt Map die Wörter in einen bestimmten Feld in allen Dokumenten, Reduce summiert dann die Einzelergebnisse zur Gesamtwortzahl auf), aber, wie oben ja schin gesagt wird, es kann beliebig komplex werden.

Gruß, noisefloor

[burli]

Hi Noisefloor,
ich hab den Artikel gelesen, danke. Hat auch etwas geholfen. Aber am meisten geholfen hat mir das View Cookbook for SQL Jockeys, obwohl ich mich eigentlich nicht als SQL Jockey bezeichnen kann. Im Gegenteil, mehr als einfache Selects bekomme ich kaum zusammen.

Aber da gibt es mal ein paar kleine praktische Beispiele. Sowas hilft mir mehr als seitenweise Text, der aber nur um den heißen Brei redet.

Ich denke, ich habe Map und Reduce jetzt einigermaßen verstanden. Das Reduce optional ist war mir schon vorher klar. Aber mir hat irgendwie noch der Zugang zum Sinn der Funktion gefehlt. Zumindest zu allem, was über einfache Berechnungen hinaus geht.

Ach ja, einen Punkt habe ich noch immer nicht ganz verstanden. Den Unterschied zwischen Reduce und Rereduce. Ich weiß, dass es irgendwas mit den B-Trees zu tun hat und davon abhängt, bei welchem Index man sich gerade befindet. Aber was das jetzt genau für eine Bedeutung und Auswirkung hat ist mir noch nicht ganz klar geworden.

[BlackJack]

@burli: Reduce bekommt eine Menge von Datensätze die zu einem Ergebnis zusammengefasst werden müssen, und Rereduce bekommt eine Menge zusammengefasste Ergebnisse von Reduce-Aufrufen, welche wiederum zu einem einzelnen Ergebnis zusammengefasst werden müssen. Du musst beides zur Verfügung stellen, weil die Datenbank nicht garantiert, dass nur einmal Reduce mit allen Datensätzen aufgerufen wird, die zusammengefasst werden sollen.

Das kann allgemein gesprochen die verschiedensten Gründe haben. Zum Beispiel dass die Datenmenge so gross ist, dass man sie nicht auf einmal an *einen* Reduce-Aufruf übergeben kann. Das es sinnvoll sein kann mehrere Reduce-Aufrufe parallel laufen zu haben, zum Beispiel um mehrere Prozessoren oder Prozessorkerne zu beschäftigen; oder weil die Daten vielleicht sogar physikalisch auf mehrere Rechner verteilt sind und jeder lokal ein Reduce auf seinem angeforderten Datenteil macht und nur noch das akkumulierte Ergebnis zu einem Rereduce zu dem Rechner schickt, der die Anfrage koordiniert. Oder eben weil die Daten in einem B-Baum organisiert sind, und es sich anbietet die Daten von den einzelnen Blättern zu zusammen zu fassen und am Ende dann diese Zwischenergebnisse zu einem Endergebnis zusammen zu fassen. *Oder* auch eine wilde Mischung aus all diesen Möglichkeiten.

[burli]

So, danke für die Erläuterungen. Ich denke, so langsam komme ich klar.

Ich habe auch noch was schönes zum Spielen gefunden