Ho letto MapReduce da un po 'di tempo - ma quello che non riesco a capire è come qualcuno prenderebbe una decisione per usare (o non usare) MapReduce.
Voglio dire, quali sono i pattern di problema che segnalano che MapReduce potrebbe essere usato.
In pratica sono problemi enormi, ma non difficili. Il venditore ambulante dipende in modo cruciale dalla distanza tra una data coppia di città, quindi mentre può essere scomposto in più parti, i risultati parziali non possono essere ricombinati in modo che la soluzione ottimale globale emerga (beh, probabilmente no ; se conosci un modo, per favore richiedi la medaglia Fields ora).
D'altra parte, il conteggio delle frequenze di parole in un corpus gigantesco è banalmente partizionabile, e ricombinabile banalmente (si sommano solo i vettori calcolati per i segmenti del corpus), quindi riduci la mappa è la soluzione più ovvia.
In pratica, più problemi tendono ad essere facilmente ricombinabili rispetto a no, quindi la decisione se parallelizzare un'attività o meno ha più a che fare con quanto sia enorme il compito, e meno con quanto sia difficile.
Il problema può essere risolto in modo efficiente utilizzando il calcolo distribuito?
Se la risposta a questa domanda è sì, allora hai un problema con il candidato per MapReduce. Questo perché il modello del problema si presta a essere suddiviso in problemi isolati più piccoli.
La tua attività: analizza questo libro
Un esempio funziona bene per illustrarlo. Hai un documento di grandi dimensioni ( Moby Dick di Herman Melville ) e il tuo compito è eseguire un'analisi di frequenza di tutte le parole usate in esso.
L'approccio sequenziale
Puoi farlo in sequenza ottenendo la tua macchina più veloce (ne hai abbastanza in giro) e passando il testo dall'inizio alla fine mantenendo una mappa hash di ogni parola che trovi (la chiave) e incrementando la frequenza (valore ) ogni volta che analizzi una parola. Semplice, diretto e lento.
L'approccio MapReduce
Avvicinandoti da una prospettiva diversa, noti che hai tutte queste macchine di riserva in giro e potresti dividere questo compito in blocchi. Assegna ad ogni macchina un blocco di testo da 1 Mb per analizzare in una mappa hash e quindi raggruppare tutte le mappe hash da ognuna in un singolo risultato. Questa è una soluzione MapReduce a strati.
Il processo di lettura di una riga di testo e di raccolta delle parole è la fase Map (si crea una mappa semplice che rappresenta le parole nella linea con la loro frequenza 1,2,3 ecc.), quindi la fase Reduce è quando ciascuna macchina raccoglie le loro mappe di linee in una singola mappa aggregata.
La soluzione generale proviene da un'ulteriore fase di riduzione in cui tutte le mappe aggregate sono aggregate (quella parola di nuovo) in una mappa finale. Leggermente più complesso, massicciamente parallelo e veloce.
Riepilogo
Quindi, per riassumere, se il tuo problema si presta a essere rappresentato da chiavi, valori, operazioni di aggregazione su quei valori in isolamento, allora hai un problema candidato per MapReduce.
Il pattern MapReduce è preso dal mondo della programmazione funzionale. È un processo per applicare qualcosa chiamato un catamorfismo su una struttura dati in parallelo. I programmatori funzionali usano i catamorfismi praticamente per ogni semplice trasformazione o riepilogo.
Supponendo che i tuoi dati siano un albero, il fattore decisivo è se puoi calcolare un valore per un nodo usando solo i dati contenuti in quel nodo e i valori calcolati per i suoi figli.
Ad esempio puoi calcolare la dimensione di un albero usando un catamorfismo; calcoli la somma dei valori calcolati per tutti i bambini più uno.
Questo WPI - Applicazioni di Riduzione della mappa (ppt) potrebbe essere di interesse per te. Descrive diverse applicazioni di MR e, come uno dei casi discussi, mostra come utilizzando 100 istanze EC2 e 24 ore, il New York Times è stato in grado di convertire da 4 TB di articoli scansionati a 1,5 TB di documenti PDF.
Un'altra serie di esempi in cui MR ha aiutato a velocizzare le prestazioni è in: Aster - SQL Map Reduce mostra alcuni casi di studio della tecnologia SQL-Map Reduce tra cui rilevamento di frodi, trasformazioni e altri.
Mappa / Riduci è una forma specifica di un tipo specifico di algoritmo. Lo usi per trasformare un enorme set di dati in un altro set di dati. (Il set di risultati può essere o non essere enorme.) Se non si desidera impostare un output di dati statici come risultato dell'input statico, quindi Map / Reduce non è appropriato. Map / Reduce può facilmente dirti quanti John Smith sono nella rubrica di Manhattan, ma non è adatto per costruire un server web.
Il modo in cui Map / Reduce funziona è:
Il risultato è che una lista di coppie (k1, v1) viene trasformata in una lista di (v3) s. (Naturalmente, il valore "v3" può essere un composto che include k2, che potrebbe essere definito uguale a k1.)
Quindi lo usi:
Se hai così tanti dati per iniziare che eseguirli tutti in sequenza attraverso uno o due server richiederebbe troppo tempo e
Puoi immaginare i dati di output di essere un elenco di valori o coppie di valori chiave (generalmente non troppo difficile quando ricordi "chiave" significa solo "etichetta univoca"), e
Qualunque sia la relazione, sei sicuro che ogni parte dei dati di input influisce solo sul valore di output per una chiave di uscita.
Se i tuoi dati possono essere elaborati in sequenza da un singolo server, poiché questo è il paradigma di elaborazione dominante (quelli per cui i server sono stati progettati e i programmatori sono addestrati), utilizza un singolo server.
Lo stage della mappa deve partizionare tutti i dati di input per chiave di output. Non deve produrre il valore di uscita associato alla chiave di output (operazione eseguita dalla fase di riduzione), ma deve assegnare in modo univoco ciascuna coppia di valori della chiave di input per contribuire al massimo al valore di una chiave di uscita. Se i dati sono troppo interconnessi, la riduzione della mappa potrebbe non essere in grado di gestire il problema. D'altra parte, potrebbe essere solo che è necessario utilizzare più turni di mappa / ridurre.
Se non riesci a capire come trasformare la trasformazione dei dati in una mappa / riduci, ovviamente non è una soluzione.
Esiste una vera arte per capire se un problema può essere scomposto in qualcosa che Map / Reduce può gestire. Ad esempio, v1 e v2 potrebbero non essere presenti nei set di dati di input o di output. Se si desidera contare solo elementi unici nei dati di input, quindi k1 = k2 = un elemento e v1 = v2 = 1 o 0 o qualsiasi altra cosa. Riduci produce appena v3 come somma del numero di k2 che è stato dato.
Quindi è difficile dire con certezza che una trasformazione dei dati non può essere eseguita usando Map / Reduce, ma quanto sopra ti dà alcune indicazioni.
MapReduce funziona su qualsiasi problema costituito da esattamente 2 funzioni con un certo livello di astrazione. La prima funzione è applicata a ciascuno degli elementi nel set di input e la seconda funzione aggrega i risultati.
Quindi, ogni volta che vuoi ottenere (1) risultato da (n) input e tutti gli input possono essere esaminati / usati dalla (1) funzione, puoi usare MapReduce. Di nuovo, questo è a un livello specifico di astrazione. La (1) funzione potrebbe essere una funzione di raggruppamento che controlla l'input e decide quale delle diverse altre funzioni utilizzare.
Questo è utile quando non si conosce in anticipo quanto input si avrà, quando è necessario condividere "unità" di lavoro discrete o quando si desidera che un singolo ritorno rappresenti l'intero risultato (IE che esegue cinque migliaia di unit test, e se meno di x% fallisce, restituire successo).
La maggior parte delle risposte qui sembrano essere una variante di spiegare cosa fa la mappa di riduzione, che è valida. Ma per rispondere alla domanda, quale sarebbe stato il pattern che segnalerebbe dove potresti essere in grado di utilizzare la riduzione della mappa, non viene realmente affrontato da questo.
Se l'implementazione ingenua e non funzionale del problema che stai osservando implica il looping su qualcosa e quindi l'aggiornamento di qualcosa al di fuori del ciclo con uno stato all'interno del ciclo, è probabile che tu abbia qualcosa che porti bene a ridurre la mappa. Soprattutto se è possibile generalizzare l'aggiornamento dello stato centrale a una funzione che funziona con solo due parametri e può garantire che questa funzione sia commutativa e associativa.
Il motivo per cui potresti voler utilizzare la mappa riduci se è vero è duplice: 1) potrebbe essere un po 'più pulito e più facile da testare e correggere se rompi le cose nella mappa e riduci le funzioni. 2) le funzioni di riduzione della mappa sono stateless e possono essere eseguite contemporaneamente, il che accelera le cose se si hanno più cpu disponibili e qualcosa come hadoop o spark che fa uso di ciò per eseguire le cose in un cluster.
Questo è bello se stai facendo un sacco di roba, ma il tuo chilometraggio può variare a seconda della complessità della tua mappa / riduzione. È abbastanza comune finire con una catena sequenziale o un albero di riduzioni di mappe, dove alla fine tutto è ancora confinato in una fase di riduzione complessa alla fine della catena. Ad esempio, molti algoritmi di grafi sono difficili da scalare in modo efficiente con la sola riduzione della mappa.
L'esempio più semplice che funziona bene con la riduzione della mappa, è il conteggio delle cose, che è una riduzione molto economica. Questo è il motivo per cui il conteggio delle parole è un esempio spesso usato per la riduzione delle mappe. Puoi aspettarti una scalabilità lineare per le prestazioni con quel tuo usecase: ogni CPU che aggiungi lo rende più veloce.
Se fai molta programmazione funzionale, inizi a correre in situazioni che richiedono una mappa generale e riducono. Probabilmente li vedi anche nella programmazione imperativa, ma non li riconosci dietro la maschera di anelli e accumulatori.
Come esempio di quello che mi è venuto in mente di recente, ho lavorato su un parser in Haskell. Per testare il mio parser, io pompo un elenco di frammenti di stringhe attraverso il parser, e poi voglio ottenere una singola stringa che possa produrre dei miei risultati per vedere se ha analizzato correttamente. In questo modo:
--my initial set of test data, a list
tests = ["string1", "string2", "string3", ...]
--Map Step: turn strings into parsed results
--note the type, which demonstrates the map
applyParser :: [String] -> [Token]
--The actual function
applyParser input = map parser input
--Second map, turn tokens into output
showTokens :: [Token] -> [String]
showTokens t = map show t
--Reduce step, concat the results
combineResults :: [String] -> String
--In haskell, reduce is the foldl function, which takes an operation to fold with, a starting element, and a list to fold on
combineResults strings = foldl concat "" strings
--Finished program
testParser = print (combineResults(showTokens(applyParser tests)))
Naturalmente, questo è solo pedagogico. Il mio codice attuale sembra un po 'diverso e utilizza più funzioni interne (come fold concat non è necessario poiché Haskell include già unlines che fa [String]->String ). Il mio punto principale era che non mi aspettavo di usare una mappa / ridurre quando ho iniziato, era semplicemente in linea con le mie esigenze. Volevo fare qualcosa con le liste, quindi trasformare la mia lista in un singolo elemento di output. L'uso della mappa / riduzione è emerso naturalmente.
L'elaborazione di stringhe (come l'analisi) è un uso molto ovvio della riduzione della mappa, la mappatura è l'applicazione di varie trasformazioni sul testo di input e la riduce mettendo il testo risultante di nuovo insieme come output. Allo stesso modo, un compilatore potrebbe essere simile, usando le pieghe per trasformare un flusso di elementi Abstract Syntax Tree in una forma migliore (ottimizzazione).
È parallelizzabile?
Qualsiasi problema parallelizzabile è essenzialmente mappa e piega; viceversa, il passo della mappa è intrinsecamente parallelizzabile (e la fase di piega potrebbe essere, a seconda della struttura su cui si piega), quindi questa è una proprietà bidirezionale.
Dire che stai cercando un gruppo di server e uno non è in grado di rispondere in quel momento. Ciò che mapReduce farà è che, poiché non è in grado di accedere a quel nodo ad albero nella mappa più grande, lo ripianificherà per un momento successivo ed eseguirà la mappa o il riduttore. In sostanza cerca di garantire che tutte le informazioni siano disponibili con l'imprevedibilità del software e dell'hardware negli ambienti.
Ecco le principali domande che uso per sondare la decisione di utilizzare (o non utilizzare) MapReduce.
Il problema che sto cercando di risolvere si scompone in Map e riduce l'operazione?
in effetti, è un modello generico di "divide et impera", in modo che le soluzioni per distribuire il calcolo possano essere scritte genericamente.
un semplice esempio è come un grande documento. il problema è che vuoi contare il numero di lettere in quel documento. invece di girare su una singola macchina, puoi scomporla in una matrice di tutte le parole del documento. quindi puoi elaborare ogni parola singolarmente e i risultati di nuovo insieme.
il pattern è utile, perché una volta che ottieni una mappa generica / riduci l'implementazione funzionante puoi risolvere qualsiasi problema usando lo stesso livello software, devi solo esprimere il tuo problema in termini di esso.
Leggi altre domande sui tag programming-practices parallel-programming