In questo breve articolo introduciamo un algoritmo per Hadoop Map/Reduce, per estrarre i valori distinti di un dataset.

Iniziamo subito vedendo lo pseudocodice:

def map(key, value):
    emit(value, null)
def reduce(key, null[]):
    emit(key)

Tutto abbastanza semplice: il mapper riceve in input dei dati, ed emette il valore su cui eseguire la distinct come nuova chiave.

Come funziona

In breve, Hadoop M/R è diviso in due macro fasi:

  1. Map: Fase in cui vengono caricati i dati dal disco, e viene effettuata una operazione su ogni elemento. I risultati vengono poi passati ad uno o più reducers
  2. Reduce: Fase in cui si ricevono i dati dai vari mappers, e si esegue una “sintesi” di qualche tipo.

Entrambe queste funzioni, lavorano per chiave-valore. Il mapper emetterà ogni record usando il valore da distinguere come chiave e null come valore. I reducers quindi, riceveranno dai mappers delle coppie <chiave : null>.

La proprietà delle chiavi è che sono univoche: per ogni chiave distinta, verrà chiamato un solo reducer.

Se nel map infatti avessimo fatto l’emit di key : intero (o comunque qualcosa diverso da null), il reducer avrebbe ricevuto la coppia <key : lista di interi>.

E sostanzialmente è tutto qua! Le distinct su Map/Reduce sono possibili senza molto sforzo, l’unico consiglio è quello di stare attenti nel parsing dell’input del primo mapper per essere sicuri di emettere effettivamente chiavi della stessa forma.

Di seguito posto un esempio di codice, che prende input un file ed esegue la distinct di tutte le parole che trova.
Il primo argomento è il file su cui eseguire la distinct, e il secondo argomento è la directory di output.