hadoop lab 2: łączenie faz map-reduce

W niektórych przypadkach chcielibyśmy policzyć pewne globalne wartości (np. statystyki) w programach MapReduce. W tym celu architektura MapReduce została wzbogacona o objekty Counter. Aby użyć tych obiektów, należy najpierw zadeklarować swój własny counter:

public static enum MY_COUNTER {
      LONG_WORDS_NUM,
      SHORT_WORDS_NUM
    };

A następnie można go modyfikować w metodach map i reduce:

reporter.getCounter(MY_COUNTER.LONG_WORDS_NUM).increment(1);
reporter.getCounter(MY_COUNTER.SHORT_WORDS_NUM).increment(1);

W trakcie trwania zadania i po jego zakończeniu do wartości liczników można dostać się za pomocą obiektu klasy RunningJob:

RunningJob runningJob = JobClient.runJob(job);
long longWordsNum = runningJob.getCounters().getCounter(MY_COUNTER.LONG_WORDS_NUM);

Uwaga: w hadoopie 1.2.x combinery nie widzą counterów!

Wyjście z reduce może stanowić wejście do kolejnej fazy map. Pozwala to na zaimplementowanie algorytmów iteracyjnych.

Przydatne fragmenty API hadoopa:

• blokowanie się do zakończenia obliczeń:

JobClient.runJob(pageJob);

• czyszczenie katalogu wyjściowego:

FileSystem fs = FileSystem.get(conf);
fs.delete(new Path(outputDirectory), true);

(inspirowane problemem zaproponowanym przez Piotra Skowrona)

Zaimplementuj przeszukiwanie grafu wszerz. Najprostsze podejście zakłada kolorowanie wierzchołków. Zaczynamy od pokolorowania wierzchołka wejściowego na szaro (reszta grafu jest biała). Fazy map i reduce wykonywane są dla każdego wierzchołka. W fazie map wierzchołki białe i czarne emitowane są bez zmian; wierzchołki szare zmieniają kolor na czarny (odwiedzony), ale każdy sąsiad takiego wierzchołka zmienia kolor na szary (jest emitowany jako szary). W fazie reduce wierzchołki, które były białe a zostały pokolorowane na szaro stają się szare; wierzchołki białe i czarne emitowane są bez zmian.

Przykład: dla grafu 1->2, 1->3, 2->4, 3->4 wejście do pierwszego map wygląda następująco:

1 GRAY 2,3
2 WHITE 4
3 WHITE 4
4 WHITE

Po wykonaniu map, wejście dla reduce można przedstawić następująco:

1 BLACK 2,3
2 GRAY 
2 WHITE 4
3 GRAY 
3 WHITE 4
4 WHITE

Zaimplementuj algorytm BFS, który, po końcu każdej fazy reduce, dla wierzchołków czarnych i szarych zapisuje odległość (najmniejszą liczbę krawędzi) od węzła początkowego. Algorytm powinien zatrzymać się po przejściu całego grafu (podpowiedź: użyj liczników liczących szare węzły w fazie reduce). Na przykład po 3 iteracjach map-reduce, rezultatem powinno być:

1 BLACK 2,3 0
2 BLACK 4 1
3 BLACK 4 1
4 BLACK 2