MapReduce qualcosa di più di una semplice applicazione di divide et impera?

Se stai chiedendo dell'architettura MapReduce, allora è solo una tecnica divide and conquer . Tuttavia, qualsiasi utile architettura MapReduce avrà montagne di altre infrastrutture per "dividere", "conquistare" e infine "ridurre" il problema. Con una grande distribuzione MapReduce (migliaia di nodi di calcolo) questi passaggi per partizionare il lavoro, calcolare qualcosa e infine raccogliere tutti i risultati non sono banali. Cose come bilanciamento del carico, rilevamento di nodi morti, salvataggio dello stato intermedio (per problemi di lunga durata), sono di per sé problemi difficili.

MapReduce è un framework per implementare algoritmi di divisione e conquista in modo estremamente scalabile , distribuendo automaticamente unità di lavoro ai nodi in un cluster arbitrariamente grande di computer e gestisce automaticamente i guasti dei singoli nodi ridistribuendo l'unità di lavoro su un altro nodo.

Non è un concetto super sofisticato, ma un'infrastruttura molto utile.

MapReduce diverge dalla maggior parte dei sistemi di divisione e conquista in modo abbastanza fondamentale, ma è così semplice che quasi nessuno lo manca. Il vero genio di questo è nel tagging dei risultati intermedi.

In un tipico (precedente) sistema divide and conquer, dividi il lavoro in serie, esegui i pacchetti di lavoro in parallelo, quindi unisci di nuovo i risultati da quel lavoro in serie.

In MapReduce, dividi il lavoro in serie, esegui i pacchetti di lavoro in parallelo e tagga i risultati per indicare quali risultati vanno con quali altri risultati. La fusione è quindi seriale per tutti i risultati con lo stesso tag, ma può essere eseguita in parallelo per risultati con tag diversi.

Nella maggior parte dei sistemi precedenti, il passo di unione diventava un collo di bottiglia per tutti, tranne che per le attività più banali. Con MapReduce può essere ancora se la natura delle attività richiede che tutte le operazioni di fusione avvengano in serie. Se, tuttavia, l'attività consente un certo grado di fusione parallela dei risultati, MapReduce offre un modo semplice per sfruttare questa possibilità. La maggior parte degli altri sistemi fa una delle due cose: o esegue l'unione in serie solo perché potrebbe essere necessaria per alcune attività, o altrimenti definire staticamente la fusione parallela per una determinata attività. MapReduce ti dà abbastanza dati nella fase di fusione per pianificare automaticamente il più possibile in parallelo, assicurando comunque (presumendo che non hai commesso errori nella fase di mappatura) che la coerenza sia mantenuta.

Si noti inoltre che in MapReduce, è implicito che tutti i passaggi possono essere ricorsivi, quindi potrei avere una fase di mappatura iniziale che rompe una grande attività in 5 attività più piccole che possono essere eseguite in parallelo - ma ognuna di queste potrebbe (a sua volta) essere mappato su un numero di altre attività parallele più piccole, e così via.

Questo porta a una struttura ad albero sia sul lato di mappatura che su quello di riduzione per suddividere velocemente un grande compito in pezzi sufficienti per sfruttare molte macchine.

MapReduce è non semplicemente una tecnica divide et impera, anche se in questo modo appare in molti esempi.

Nella fase di mappatura puoi e spesso vuoi fare una relazione uno-a-molti. Quindi non stai semplicemente dividendo in casi.

Tra la mappa e la riduzione c'è o (a seconda dell'implementazione) un ordinamento o un passaggio di hashing. L'efficienza di questa operazione è estremamente importante per i requisiti generali delle risorse. I suoi dettagli sono invisibili al programmatore dell'applicazione, ma questo passaggio è il cuore del framework.

L'operazione di riduzione è un tipo di unione. Che può essere pensato come una conquista, ma in pratica tende ad essere, "emettere i dati per un utilizzo successivo" o "salva i dati in un archivio dati". (Nota: se hai grandi set di dati vuoi davvero che tutto sia distribuito, incluso l'input e il risultato finale. Quindi un archivio di chiavi / valori distribuiti ha senso sia come luogo per ottenere l'input che per archiviare l'output.)