Tolleranza di errore

  • 14 minuti

L'obiettivo di MapReduce è dividere i processi in attività che sfruttino efficacemente il parallelismo e, di conseguenza, vengano completati più rapidamente. Anche se in teoria questo approccio è valido, in pratica presenta problematiche specifiche. Ad esempio, basta un'unica attività lenta o in errore perché l'intero processo richieda molto più tempo del previsto. In realtà, le attività di Hadoop MapReduce non riescono e rallentano a causa di problemi come la riduzione delle prestazioni dell'hardware, l'errata configurazione del software, l'eterogeneità e/o la località dei dati, solo per citare alcuni esempi. Non è facile applicare la tolleranza di errore per attività con errori e lente. In particolare, se i dati che passano attraverso un sistema di I/O sono in quantità elevata quanto quelli elaborati da Hadoop, la probabilità che alcuni risultino danneggiati aumenta. Inoltre, nel caso di diverse migliaia di attività e nodi operativi (uno scenario tipico di Hadoop), la probabilità di errore aumenta.

Hadoop MapReduce applica due meccanismi per la tolleranza di errori, ovvero la ridondanza dei dati e la resilienza delle attività. La ridondanza dei dati viene applicata a livello di archiviazione. In particolare, l'affidabilità di HDFS conserva i blocchi HDFS mantenendo più repliche (tre per impostazione predefinita) per ogni blocco in computer fisicamente separati. Ovviamente, in questo modo MapReduce può tollerare facilmente blocchi danneggiati e nodi in errore. Se un blocco va perso a causa di un errore hardware o software, è possibile individuare e leggere un'altra replica in un altro nodo in modo totalmente trasparente per i processi utente. HDFS calcola i checksum usando un controllo di ridondanza ciclico (CRC-32) per tutti i dati scritti e, per impostazione predefinita, verifica i checksum durante la lettura dei dati.2 Quando viene rilevato l'errore di un blocco o l'arresto di un nodo, HDFS ripristina in modo trasparente il livello predefinito tre del fattore di replica.

Anche se è possibile che tutti i blocchi HDFS del set di dati di un processo siano privi di errore, l'esecuzione delle attività del processo potrebbe comunque rallentare o semplicemente non riuscire. Ovviamente, un rallentamento o un errore di un'attività può causare il rallentamento o l'errore di un intero processo. Per evitare tali conseguenze e per ottenere resilienza, Hadoop MapReduce consente la replica delle attività e le monitora per rilevare e risolvere quelle lente o in errore. Per rilevare le attività lente o in errore, Hadoop MapReduce si basa sul meccanismo di heartbeat. Il JobTracker (JT) esegue un thread di scadenza che controlla gli heartbeat di ogni TaskTracker (TT) e decide se le rispettive attività sono inattive o attive. Se il thread di scadenza non riceve gli heartbeat che confermano l'integrità di un'attività entro 10 minuti (per impostazione predefinita), l'attività viene considerata inattiva. In caso contrario, l'attività viene contrassegnata come attiva.

Le attività attive possono essere lente (ossia in ritardo) o meno. Per misurare la lentezza, il JT stima l'avanzamento dell'attività usando un punteggio per attività compreso tra 0 e 1. I punteggi di mapping e riduzione vengono calcolati in modo diverso. Per un'attività di mapping, il punteggio di avanzamento è una funzione del blocco HDFS di input letto fino a quel momento. Per un'attività di riduzione, il punteggio di avanzamento è più complesso. Hadoop MapReduce presuppone che ogni stadio di riduzione (shuffling, unione e ordinamento e riduzione) totalizzi un terzo del punteggio di un'attività di riduzione e che, per ogni stadio, il punteggio corrisponda alla frazione dei dati elaborati fino a quel momento. Ad esempio, un'attività di riduzione a metà dello stadio di shuffling avrà un punteggio di avanzamento di $\frac{1}{3} \times \frac{1}{2} = \frac{1}{6}$. D'altra parte, un'attività di riduzione a metà dello stadio di unione e ordinamento avrà un punteggio di avanzamento di $\frac{1}{3} + (\frac{1}{2} \times \frac{1}{3}) = \frac{1}{2}$. Infine, un'attività di riduzione a metà dello stadio di riduzione avrà un punteggio di avanzamento di $\frac{1}{3} + \frac{1}{3} + (\frac{1}{3} \times \frac{1}{2}) = \frac{5}{6}$.

Quando rileva un'attività lenta, il JT esegue contemporaneamente un'attività di backup (speculativa) corrispondente. Hadoop consente l'esecuzione di un'attività speculativa per ogni attività lenta originale e le due vanno in competizione. La versione che viene completata per prima viene sottoposta a commit, mentre l'altra viene terminata. Questa tattica di resilienza delle attività è nota in Hadoop MapReduce come esecuzione speculativa ed è attivata per impostazione predefinita, anche se può essere abilitata o disabilitata in modo indipendente per le attività di mapping e di riduzione, a livello di cluster o per ogni processo.

Hadoop MapReduce calcola il punteggio di avanzamento medio tra tutte le attività in ogni categoria, ad esempio tutte le attività di mapping. Qualsiasi attività di una categoria con un punteggio inferiore al 80% della media (detta soglia del 20% di differenza nell'avanzamento) viene contrassegnata come attività in ritardo. Purché tutte le attività originali di mapping e di riduzione siano già state pianificate,9 il JT avvia un'attività speculativa equivalente. Tutte le attività in ritardo vengono considerate ugualmente lente e il collegamento tra loro viene interrotto in base alla località dei dati. Più in particolare, se uno slot di mapping diventa libero in uno specifico TT e vengono rilevate due attività di mapping in ritardo, quella che usa un blocco HDFS archiviato nel TT verrà selezionata per l'esecuzione speculativa. Se le due attività in ritardo richiedono entrambe i blocchi HDFS archiviati nel TT, è possibile sceglierne una in modo casuale. Le attività inattive ottengono sempre la massima priorità e quelle speculative la minima. In particolare, quando il JT riceve un heartbeat del TT che include una richiesta di attività di mapping o di riduzione, il JT risponde con un'attività nell'ordine seguente:

  1. Un'attività che compensa un'attività inattiva o arrestata.
  2. Un'attività originale, non ancora pianificata.
  3. Un'attività speculativa.

L'approccio di Hadoop MapReduce alla resilienza delle attività è efficace negli ambienti omogenei ma non altrettanto in quelli eterogenei, per diversi motivi:1, 3

  • L'eterogeneità può derivare dal conflitto delle risorse nei cloud virtualizzati, in cui la congestione potrebbe essere solo temporanea. In questi casi, il JT può avviare troppe attività speculative per quelle originali che risultano lente al momento ma che poco dopo vengono identificate come non lente. Le attività speculative tolgono risorse a quelle originali e un numero eccessivo di esecuzioni speculative può rallentare l'intero cluster, soprattutto se la rete è sovraccaricata da una quantità elevata di traffico di shuffling non necessario.
  • Hadoop MapReduce avvia inoltre le attività speculative nei TT senza considerare i carichi/velocità correnti rispetto a quelli dei TT che ospitano le attività originali. In teoria, il JT potrebbe pianificare un'attività speculativa in un TT lento che successivamente diventa più lento anche rispetto all'attività originale corrispondente.
  • Poiché il pianificatore di Hadoop usa la località dei dati per interrompere i collegamenti tra attività di mapping in ritardo, è possibile che per la speculazione vengano selezionate attività in ritardo errate. Se il JT rileva due attività in ritardo, $S_{1}$ e $S_{2}$, per cui il punteggio di $S_{1}$ è il 70% della media e il punteggio di $S_{2}$ è il 20%, e se un TT che ospita il blocco di input $S_{1}$ diventa inattivo, l'attività $S_{1}$ potrebbe essere resa speculativa prima di $S_{2}$.
  • La soglia del 20% di differenza nell'avanzamento implica che le attività con un punteggio superiore all'80% della media non verranno mai rese speculative, nonostante la necessità o il potenziale di una maggiore efficienza.
  • Infine, Hadoop MapReduce divide equamente il punteggio della fase di riduzione tra i tre stadi costitutivi. Questo compromesso non è realistico in un tipico processo MapReduce, in cui lo stadio di shuffling è in genere il più lento perché coinvolge tutte le coppie che comunicano tramite la rete. In realtà, è altamente probabile che, dopo lo stadio di shuffling, i processi MapReduce completino rapidamente lo stadio di unione e ordinamento e lo stadio di riduzione. Quindi, non appena le prime attività di riduzione completano gli stadi di shuffling, i relativi punteggi di avanzamento passeranno da $\frac{1}{3}$ a $1 $. Quindi, il punteggio medio complessivo aumenterà significativamente, con un possibile degrado dell'accuratezza della speculazione. Infatti, non appena viene eseguito il commit del 30% delle attività di riduzione, il punteggio medio diventa $0,3 \times 1 + 0,7 \times \frac{1}{3} = 53%$. Successivamente, tutte le attività di riduzione ancora nello stadio di shuffling si troveranno il 20% indietro rispetto al punteggio medio. Di conseguenza, un set arbitrario di attività in ritardo false diventerà speculativo, occupando rapidamente gli slot di riduzione e possibilmente sovraccaricando la rete del cloud con traffico non necessario.

Ovviamente, l'approccio standard di MapReduce all'esecuzione speculativa presenta seri limiti. Per questo motivo, Facebook ha disabilitato l'esecuzione speculativa per le attività di riduzione.1 Anche Yahoo! ha disabilitato completamente l'esecuzione speculativa, anche se solo per determinati processi.1 Per risolvere il problema sottostante, Zahria e associati1 propongono una strategia "greedy" denominata LATE (Longest Approximate Time to End), che suggerisce di rendere speculative solo le attività che si prevede vengano completate in un futuro più lontano. Con la strategia LATE è molto più probabile che le attività speculative superino quelle originali e, di conseguenza, che tendano a ridurre i tempi di risposta dei processi. Tuttavia, il problema consiste nell'identificare le attività candidate appropriate. A tale scopo, LATE propone di calcolare la velocità di avanzamento di ogni attività con la formula $\frac{score}{T}$, dove $T $ è il tempo impiegato finora dall'attività, e quindi di prevedere il tempo di completamento dell'attività con la formula $\frac{(1 - progress\ score)}{progress\ rate}$. Inoltre, LATE supporta la pianificazione di attività speculative solo nei TT veloci, ossia quelli superiori a una determinata soglia. Inoltre, per tenere conto del fatto che la speculazione consuma risorse, LATE specifica un limite per il numero di attività speculative che è possibile avviare contemporaneamente. Infine, LATE ignora la località dei dati per la pianificazione di attività di mapping speculative, presupponendo che la maggior parte delle attività di mapping originali continui a essere eseguita con i blocchi HDFS di input locali e che ne venga eseguito correttamente il commit. I risultati della sperimentazione dimostrano che la strategia LATE può migliorare di due volte i tempi di risposta di Hadoop negli ambienti cloud eterogenei.

9 Ogni attività originale deve essere eseguita per almeno 1 minuto (per impostazione predefinita) prima che ne venga calcolato il punteggio di avanzamento. In seguito, il JT decide se pianificare o meno la corrispondente attività speculativa.

Riferimenti

  1. M. Zaharia, A. Konwinski, A. Joseph, R. Katz e I. Stoica (2008). Improving MapReduce Performance in Heterogeneous Environments OSDI
  2. T. White (2011). Hadoop: The Definitive Guide, O'Reilly, seconda edizione
  3. Z. Guo e G. Fox (2012). Improving MapReduce Performance in Heterogeneous Network Environments and Resource Utilization Documentazione del 12° simposio internazionale IEEE/ACM su cluster, cloud e grid computing del 2012

Verificare le conoscenze

1.

Come viene gestita la ridondanza dei dati in Hadoop MapReduce?

2.

Come vengono replicate le attività in Hadoop MapReduce?

3.

Di seguito è riportato un elenco di alcuni presupposti che Hadoop effettua in modo implicito nell'esecuzione speculativa:

  • R. Non è previsto alcun costo per la pianificazione di un'attività speculativa in un TT che espone uno slot inattivo.
  • B. I TT eseguono le attività approssimativamente alla stessa velocità.
  • C. Le attività di un processo avanzano a una velocità costante nel tempo.
  • D. In un'attività di riduzione gli stadi di shuffling, di unione e ordinamento e di riduzione richiedono lo stesso tempo, ovvero ognuno richiede un terzo del tempo totale dell'attività di riduzione.
  • E. Un'attività con un punteggio di avanzamento basso è probabilmente un'attività in ritardo, perché le attività tendono a essere completate in tempi simili.
Quale dei presupposti precedenti è più probabile che risulti infondato nei cloud eterogenei ma non in quelli omogenei?

4.

Ecco tre presupposti che Hadoop effettua in modo implicito nell'esecuzione speculativa:

  • R. I TaskTracker eseguono le attività approssimativamente alla stessa velocità.
  • B. In un'attività di riduzione gli stadi di shuffling, di unione e ordinamento e di riduzione richiedono lo stesso tempo, ovvero ognuno richiede un terzo del tempo totale dell'attività di riduzione.
  • C. L'attività con un punteggio di avanzamento basso è probabilmente un'attività in ritardo, perché le attività tendono a essere completate in tempi simili.
Si supponga di avere un cluster Hadoop C con una larghezza di banda di rete molto limitata e un processo Hadoop J con una velocità di shuffling molto elevata. Quale dei presupposti precedenti è più probabile che risulti infondato quando si esegue J in C?