Zawsze zakładałem, że jest to konieczne, ponieważ dane wyjściowe z programu odwzorowującego są danymi wejściowymi dla reduktora, więc zostały posortowane na podstawie przestrzeni kluczy, a następnie podzielone na segmenty dla każdego wejścia reduktora.
BasicHorizon
Odpowiedzi:
171
Przede wszystkim shufflingjest to proces przesyłania danych z mapperów do reduktorów, więc myślę, że jest oczywiste, że jest to konieczne dla reduktorów, ponieważ w przeciwnym razie nie byłyby w stanie mieć żadnego wejścia (lub wejścia z każdego mapera) . Tasowanie można rozpocząć jeszcze przed zakończeniem fazy mapy, aby zaoszczędzić trochę czasu. Dlatego możesz zobaczyć stan redukcji większy niż 0% (ale mniej niż 33%), gdy stan mapy nie wynosi jeszcze 100%.
Sortingoszczędza czas dla reduktora, pomagając mu łatwo odróżnić, kiedy powinno rozpocząć się nowe zadanie redukcji. Po prostu uruchamia nowe zadanie redukcji, gdy następny klucz w posortowanych danych wejściowych jest inny niż poprzedni, mówiąc prosto. Każde zadanie redukujące pobiera listę par klucz-wartość, ale musi wywołać metodę redukuj (), która pobiera dane wejściowe z listy kluczy (wartość), więc musi grupować wartości według klucza. Jest to łatwe do zrobienia, jeśli dane wejściowe są wstępnie posortowane (lokalnie) w fazie mapy i po prostu scalone posortowane w fazie redukcji (ponieważ reduktory pobierają dane od wielu maperów).
Partitioning, o którym wspomniałeś w jednej z odpowiedzi, to inny proces. Określa, w którym reduktorze zostanie wysłana para (klucz, wartość), wyjście fazy mapy. Domyślny program Partitioner używa skrótu na kluczach, aby rozesłać je do zadań redukcji, ale możesz go zastąpić i użyć własnego niestandardowego Partitionera.
Doskonałym źródłem informacji na temat tych kroków jest ten samouczek Yahoo .
Ładne graficzne przedstawienie tego jest następujące (odtwarzanie losowe na tym rysunku nazywa się „kopiowaniem”):
Należy zauważyć, że shufflingi sortingnie są wykonywane w ogóle, jeśli określisz zero redukcji (setNumReduceTasks (0)). Następnie zadanie MapReduce zatrzymuje się w fazie mapy, a faza mapy nie obejmuje żadnego rodzaju sortowania (więc nawet faza mapy jest szybsza).
AKTUALIZACJA: Ponieważ szukasz czegoś bardziej oficjalnego, możesz również przeczytać książkę Toma White'a „Hadoop: The Definitive Guide”. Oto interesująca część Twojego pytania.
Tom White jest zwolennikiem Apache Hadoop od lutego 2007 roku i jest członkiem Apache Software Foundation, więc myślę, że jest to całkiem wiarygodne i oficjalne ...
„Sortowanie oszczędza czas reduktorowi, pomagając w łatwym rozróżnieniu, kiedy powinno rozpocząć się nowe zadanie redukcji. Po prostu uruchamia nowe zadanie redukcji, gdy następny klucz w posortowanych danych wejściowych jest inny niż poprzedni, mówiąc prosto.” Nie rozumiem tej części. Mapper używa partycjonera do lokalnego dzielenia wycieków na partycje, a każda partycja jest następnie wysyłana do redukcji. Jak pomaga tutaj sortowanie?
MaxNevermind
1
@MaxNevermind Jeśli masz x redukuj zadania (partycje), nie oznacza to, że w końcu będziesz wywoływał metodę edit () x razy. Zostanie wywołany raz dla każdego oddzielnego klucza. Zatem jedno zadanie redukujące może wywołać metodę redukuj () kilka razy.
vefthym
„Zostanie wywołany raz dla każdego oddzielnego klucza”. Dlaczego? Mapper tworzy partycje w dowolny sposób (nie jest potrzebna jedna partycja dla każdego oddzielnego klucza), a następnie każda partycja przechodzi do redukcji, czy to źle?
MaxNevermind
1
@MaxNevermind Mapper wyprowadza klucze i wartości, nie tworzy partycji. Partycje są definiowane przez liczbę zadań redukcji zdefiniowanych przez użytkownika i implementację Partitionera. Dane wyjściowe wszystkich mapperów, które mają ten sam klucz, są kierowane do tej samej metody redukcji (). Nie można tego zmienić. Ale można zmienić to, jakie inne klucze (jeśli w ogóle) zostaną umieszczone w tej samej partycji, a zatem będą obsługiwane przez to samo zadanie. Zadanie redukcji może wywołać funkcję redukuj () więcej niż raz, ale tylko raz dla każdego klawisza.
vefthym
2
ok, myślę, że mam to. Mój problem polegał na tym, że zapomniałem, że redukcja przyjmuje jako argument listę wartości, a nie tylko jedną parę klucz-wartość. Myślę, że powinieneś rozwinąć to w swojej odpowiedzi: „Każde zadanie redukujące pobiera listę par klucz-wartość, ale musi wywołać metodę redukcji, która przyjmuje klucz-List <wartość>, więc musi grupować wartości według klucza, jest to łatwe do zrobienia, jeśli dane wejściowe są wstępnie posortowane na etapie mapowania ”
MaxNevermind
42
Wróćmy do kluczowych faz programu Mapreduce.
Faza mapy jest wykonywana przez twórców map . Mapery działają na nieposortowanych wejściowych parach klucz / wartość. Każdy element mapujący emituje zero, jedną lub wiele wyjściowych par klucz / wartość dla każdej wejściowej pary klucz / wartość.
Faza kombajnu jest wykonywana przez kombinatory. Sumator powinny łączyć pary klucz / wartość z tego samego klucza. Każdy sumator może działać zero, raz lub wiele razy.
Faza tasowania i sortowania jest wykonywana przez framework. Dane ze wszystkich mapowań są grupowane według klucza, dzielone między reduktory i sortowane według klucza. Każdy reduktor uzyskuje wszystkie wartości skojarzone z tym samym kluczem. Programista może dostarczyć niestandardowe funkcje porównujące do sortowania i partycjonera do podziału danych.
Partycjonujący decyduje, które reduktor dostanie szczególną parę kluczową wartością.
W reduktor uzyskiwanych przez klasyfikowane klucz /] [listy wartości par posortowane według klucza. Lista wartości zawiera wszystkie wartości z tym samym kluczem wygenerowanym przez twórców map. Każdy reduktor emituje zero, jedną lub wiele wyjściowych par klucz / wartość dla każdej wejściowej pary klucz / wartość .
Spójrz na ten artykuł javacodegeeks autorstwa Marii Jurcovicovej i artykuł mssqltips autorstwa Datta dla lepszego zrozumienia
Myślę, że na obrazie jest literówka (co, jak zdaję sobie sprawę, zostało tutaj skopiowane). Uważam, że iełańcuchy w sekcji Reducers and Output powinny być is.
Jeff Evans
32
Pomyślałem o dodaniu kilku brakujących punktów w powyższych odpowiedziach. Ten diagram zaczerpnięty stąd jasno pokazuje, co się naprawdę dzieje.
Jeśli ponownie przedstawię prawdziwy cel
Podziel: Poprawia przetwarzanie równoległe, rozkładając obciążenie przetwarzania na różne węzły (mapery), co pozwoliłoby zaoszczędzić całkowity czas przetwarzania.
Połącz: zmniejsza wydajność każdego Mappera. Pozwoliłoby to zaoszczędzić czas poświęcany na przenoszenie danych z jednego węzła do drugiego.
Sortowanie (Shuffle & Sort): Ułatwia planowanie czasu wykonywania (spawn / start) nowych reduktorów, gdzie podczas przeglądania posortowanej listy przedmiotów, za każdym razem, gdy bieżący klucz różni się od poprzedniego, może odrodzić nowy reduktor .
Gdzie krok podziału pojawiłby się na tym wykresie? Po mapie i przed połączeniem?
Joel
@Joel Mam nadzieję, że odnosisz się do kroku „podziału”?
Supun Wijerathne
Nie mam na myśli kroku partycjonowania, który decyduje, do jakiego reduktora wysłać dane, używając domyślnie prostego modulo z hashem, po kilku dalszych badaniach, które wydaje mi się, że następuje po kroku łączenia, przed shuffle & sort.
Joel
1
@Joel Nie jestem pewien, co zamierzasz opisać. Krótko mówiąc, dokładna sekwencja kroków może być w dużym stopniu związana z problemem. Mogę powiedzieć, że w niektórych sytuacjach nawet sortowanie nie jest konieczne. Wracając do twojego wkładu, jeśli mówię konkretnie o powyższym prostym przykładzie zliczania słów, tak naprawdę nie widzę potrzeby, aby takie partycjonowanie decydowało o reduktorach. Tutaj jest całkiem prosto odradzanie zmniejsza się na klucz. Ale domyślam się, że twój punkt widzenia może być ważny w niektórych scenariuszach. Szczerze mówiąc, nie mam o tym dokładnego jasnego pojęcia.
Supun Wijerathne
4
Niektóre wymagania dotyczące przetwarzania danych w ogóle nie wymagają sortowania. Syncsort sprawił, że sortowanie w Hadoop było podłączane. Oto fajny blog od nich na temat sortowania. Proces przenoszenia danych z elementów odwzorowujących do reduktorów nazywa się tasowaniem. Więcej informacji na ten temat można znaleźć w tym artykule.
Zawsze zakładałem, że jest to konieczne, ponieważ dane wyjściowe z programu odwzorowującego są danymi wejściowymi dla reduktora, więc zostały posortowane na podstawie przestrzeni kluczy, a następnie podzielone na segmenty dla każdego wejścia reduktora. Chcesz mieć pewność, że wszystkie te same wartości klucza trafią do tego samego segmentu i trafią do reduktora, więc zostaną razem zredukowane. Nie ma sensu wysyłanie K1, V2 i K1, V4 do różnych reduktorów, ponieważ muszą one być razem, aby zostały zredukowane.
Jeśli chcemy wysłać k1, v1 i k1, v4 do tego samego reduktora, możemy zrobić tasowanie. więc jaki jest cel sortowania?
Nithin K Anil
Sortuje z wielu powodów jednym z powodów jest to, że zadanie MapReduce wysyła wszystkie pary KV do reduktora, jeśli dane wejściowe nie są posortowane.Musiałby przeskanować wszystkie wyjścia Mappera, aby odebrać każdą instancję K1, VX . mając na uwadze, że jeśli wyjście Mappera jest sortowane zaraz po K2, VX jest odbierane, wiesz, że wszystkie K1, VX zostały odebrane i ten zestaw może zostać wysłany do reduktora w celu przetworzenia, korzyść z tego jest taka, że nie trzeba poczekać, aż każdy reduktor będzie gotowy, aby każdy z nich zaczął redukować.
BasicHorizon
Również jeśli chodzi o agregację, jeśli określisz, że chcesz agregować wszystkie K1, V1, jeśli dane wejściowe do reduktora są sortowane, gdy tylko reduktor odbierze K2, V2, wie, że nie ma więcej wystąpień K1, V1, więc może zakończyć agregację, podczas gdy jeśli wejście reduktora nie jest posortowane, będzie musiał przeskanować całe wejście pod kątem K1, V1
BasicHorizon
2
Tasowanie to proces, w którym pośrednie dane z maperów są przenoszone do 0,1 lub więcej reduktorów. Każdy reduktor otrzymuje 1 lub więcej kluczy i skojarzone z nimi wartości w zależności od liczby reduktorów (dla zrównoważonego obciążenia). Ponadto wartości skojarzone z każdym kluczem są sortowane lokalnie.
To dobra lektura. Mam nadzieję, że to pomoże. Jeśli chodzi o sortowanie, które dotyczy, myślę, że dotyczy to operacji scalania w ostatnim kroku mapy. Po zakończeniu operacji na mapie i konieczności zapisania wyniku na dysku lokalnym, na podziałach wygenerowanych z bufora zostanie przeprowadzone wielokrotne scalanie. W przypadku operacji scalania pomocne jest sortowanie każdej partycji w trybie zaawansowanym.
Cóż, w Mapreduce są dwie ważne frazy zwane Mapper i reduktor, oba są zbyt ważne, ale Reducer jest obowiązkowy. W niektórych programach reduktory są opcjonalne. A teraz przejdź do twojego pytania. Tasowanie i sortowanie to dwie ważne operacje w Mapreduce. Pierwsza platforma Hadoop pobiera dane strukturalne / nieustrukturyzowane i dzieli je na klucz, wartość.
Teraz program Mapper oddziela i porządkuje dane w klucze i wartości do przetworzenia. Wygeneruj wartości klucza 2 i wartości 2. Wartości te powinny zostać przetworzone i uporządkowane w odpowiedniej kolejności, aby uzyskać pożądane rozwiązanie. Teraz to tasowanie i sortowanie wykonane w systemie lokalnym (Framework zajmie się tym) i proces w systemie lokalnym po frameworku procesu wyczyści dane w systemie lokalnym. Dobrze
Tutaj używamy łącznika i partycji, aby zoptymalizować ten proces tasowania i sortowania. Po odpowiednim ułożeniu te kluczowe wartości są przekazywane do Reduktora w celu uzyskania pożądanego wyniku Klienta. Wreszcie reduktor uzyskuje pożądaną wydajność.
K1, V1 -> K2, V2 (napiszemy program Mapper), -> K2, V '(tutaj przetasuj i zmiękcz dane) -> K3, V3 Wygeneruj wyjście. K4, V4.
Należy pamiętać, że wszystkie te kroki są tylko operacjami logicznymi, nie powodują zmiany oryginalnych danych.
Twoje pytanie: Jaki jest cel tasowania i sortowania fazy w reduktorze w Map Reduce Programming?
Krótka odpowiedź: Przetwarzanie danych w celu uzyskania pożądanego wyniku. Tasowanie to agregacja danych, redukcja to oczekiwany wynik.
Odpowiedzi:
Przede wszystkim
shufflingjest to proces przesyłania danych z mapperów do reduktorów, więc myślę, że jest oczywiste, że jest to konieczne dla reduktorów, ponieważ w przeciwnym razie nie byłyby w stanie mieć żadnego wejścia (lub wejścia z każdego mapera) . Tasowanie można rozpocząć jeszcze przed zakończeniem fazy mapy, aby zaoszczędzić trochę czasu. Dlatego możesz zobaczyć stan redukcji większy niż 0% (ale mniej niż 33%), gdy stan mapy nie wynosi jeszcze 100%.Sortingoszczędza czas dla reduktora, pomagając mu łatwo odróżnić, kiedy powinno rozpocząć się nowe zadanie redukcji. Po prostu uruchamia nowe zadanie redukcji, gdy następny klucz w posortowanych danych wejściowych jest inny niż poprzedni, mówiąc prosto. Każde zadanie redukujące pobiera listę par klucz-wartość, ale musi wywołać metodę redukuj (), która pobiera dane wejściowe z listy kluczy (wartość), więc musi grupować wartości według klucza. Jest to łatwe do zrobienia, jeśli dane wejściowe są wstępnie posortowane (lokalnie) w fazie mapy i po prostu scalone posortowane w fazie redukcji (ponieważ reduktory pobierają dane od wielu maperów).Partitioning, o którym wspomniałeś w jednej z odpowiedzi, to inny proces. Określa, w którym reduktorze zostanie wysłana para (klucz, wartość), wyjście fazy mapy. Domyślny program Partitioner używa skrótu na kluczach, aby rozesłać je do zadań redukcji, ale możesz go zastąpić i użyć własnego niestandardowego Partitionera.Doskonałym źródłem informacji na temat tych kroków jest ten samouczek Yahoo .
Ładne graficzne przedstawienie tego jest następujące (odtwarzanie losowe na tym rysunku nazywa się „kopiowaniem”):
Należy zauważyć, że
shufflingisortingnie są wykonywane w ogóle, jeśli określisz zero redukcji (setNumReduceTasks (0)). Następnie zadanie MapReduce zatrzymuje się w fazie mapy, a faza mapy nie obejmuje żadnego rodzaju sortowania (więc nawet faza mapy jest szybsza).AKTUALIZACJA: Ponieważ szukasz czegoś bardziej oficjalnego, możesz również przeczytać książkę Toma White'a „Hadoop: The Definitive Guide”. Oto interesująca część Twojego pytania.
Tom White jest zwolennikiem Apache Hadoop od lutego 2007 roku i jest członkiem Apache Software Foundation, więc myślę, że jest to całkiem wiarygodne i oficjalne ...
źródło
Wróćmy do kluczowych faz programu Mapreduce.
Faza mapy jest wykonywana przez twórców map . Mapery działają na nieposortowanych wejściowych parach klucz / wartość. Każdy element mapujący emituje zero, jedną lub wiele wyjściowych par klucz / wartość dla każdej wejściowej pary klucz / wartość.
Faza kombajnu jest wykonywana przez kombinatory. Sumator powinny łączyć pary klucz / wartość z tego samego klucza. Każdy sumator może działać zero, raz lub wiele razy.
Faza tasowania i sortowania jest wykonywana przez framework. Dane ze wszystkich mapowań są grupowane według klucza, dzielone między reduktory i sortowane według klucza. Każdy reduktor uzyskuje wszystkie wartości skojarzone z tym samym kluczem. Programista może dostarczyć niestandardowe funkcje porównujące do sortowania i partycjonera do podziału danych.
Partycjonujący decyduje, które reduktor dostanie szczególną parę kluczową wartością.
W reduktor uzyskiwanych przez klasyfikowane klucz /] [listy wartości par posortowane według klucza. Lista wartości zawiera wszystkie wartości z tym samym kluczem wygenerowanym przez twórców map. Każdy reduktor emituje zero, jedną lub wiele wyjściowych par klucz / wartość dla każdej wejściowej pary klucz / wartość .
Spójrz na ten artykuł javacodegeeks autorstwa Marii Jurcovicovej i artykuł mssqltips autorstwa Datta dla lepszego zrozumienia
Poniżej znajduje się zdjęcie z artykułu safaribooksonline
źródło
iełańcuchy w sekcji Reducers and Output powinny byćis.Pomyślałem o dodaniu kilku brakujących punktów w powyższych odpowiedziach. Ten diagram zaczerpnięty stąd jasno pokazuje, co się naprawdę dzieje.
Jeśli ponownie przedstawię prawdziwy cel
Podziel: Poprawia przetwarzanie równoległe, rozkładając obciążenie przetwarzania na różne węzły (mapery), co pozwoliłoby zaoszczędzić całkowity czas przetwarzania.
Połącz: zmniejsza wydajność każdego Mappera. Pozwoliłoby to zaoszczędzić czas poświęcany na przenoszenie danych z jednego węzła do drugiego.
Sortowanie (Shuffle & Sort): Ułatwia planowanie czasu wykonywania (spawn / start) nowych reduktorów, gdzie podczas przeglądania posortowanej listy przedmiotów, za każdym razem, gdy bieżący klucz różni się od poprzedniego, może odrodzić nowy reduktor .
źródło
Niektóre wymagania dotyczące przetwarzania danych w ogóle nie wymagają sortowania. Syncsort sprawił, że sortowanie w Hadoop było podłączane. Oto fajny blog od nich na temat sortowania. Proces przenoszenia danych z elementów odwzorowujących do reduktorów nazywa się tasowaniem. Więcej informacji na ten temat można znaleźć w tym artykule.
źródło
Zawsze zakładałem, że jest to konieczne, ponieważ dane wyjściowe z programu odwzorowującego są danymi wejściowymi dla reduktora, więc zostały posortowane na podstawie przestrzeni kluczy, a następnie podzielone na segmenty dla każdego wejścia reduktora. Chcesz mieć pewność, że wszystkie te same wartości klucza trafią do tego samego segmentu i trafią do reduktora, więc zostaną razem zredukowane. Nie ma sensu wysyłanie K1, V2 i K1, V4 do różnych reduktorów, ponieważ muszą one być razem, aby zostały zredukowane.
Próbowałem wyjaśnić to tak prosto, jak to możliwe
źródło
Tasowanie to proces, w którym pośrednie dane z maperów są przenoszone do 0,1 lub więcej reduktorów. Każdy reduktor otrzymuje 1 lub więcej kluczy i skojarzone z nimi wartości w zależności od liczby reduktorów (dla zrównoważonego obciążenia). Ponadto wartości skojarzone z każdym kluczem są sortowane lokalnie.
źródło
Są tylko dwie rzeczy, które MapReduce robi NATYWNIE: Sortuj i (implementowane przez sortowanie) skalowalne GroupBy.
Większość aplikacji i wzorców projektowych w MapReduce jest zbudowanych na podstawie tych dwóch operacji, które są dostarczane przez shuffle i sort.
źródło
To dobra lektura. Mam nadzieję, że to pomoże. Jeśli chodzi o sortowanie, które dotyczy, myślę, że dotyczy to operacji scalania w ostatnim kroku mapy. Po zakończeniu operacji na mapie i konieczności zapisania wyniku na dysku lokalnym, na podziałach wygenerowanych z bufora zostanie przeprowadzone wielokrotne scalanie. W przypadku operacji scalania pomocne jest sortowanie każdej partycji w trybie zaawansowanym.
źródło
Cóż, w Mapreduce są dwie ważne frazy zwane Mapper i reduktor, oba są zbyt ważne, ale Reducer jest obowiązkowy. W niektórych programach reduktory są opcjonalne. A teraz przejdź do twojego pytania. Tasowanie i sortowanie to dwie ważne operacje w Mapreduce. Pierwsza platforma Hadoop pobiera dane strukturalne / nieustrukturyzowane i dzieli je na klucz, wartość.
Teraz program Mapper oddziela i porządkuje dane w klucze i wartości do przetworzenia. Wygeneruj wartości klucza 2 i wartości 2. Wartości te powinny zostać przetworzone i uporządkowane w odpowiedniej kolejności, aby uzyskać pożądane rozwiązanie. Teraz to tasowanie i sortowanie wykonane w systemie lokalnym (Framework zajmie się tym) i proces w systemie lokalnym po frameworku procesu wyczyści dane w systemie lokalnym. Dobrze
Tutaj używamy łącznika i partycji, aby zoptymalizować ten proces tasowania i sortowania. Po odpowiednim ułożeniu te kluczowe wartości są przekazywane do Reduktora w celu uzyskania pożądanego wyniku Klienta. Wreszcie reduktor uzyskuje pożądaną wydajność.
K1, V1 -> K2, V2 (napiszemy program Mapper), -> K2, V '(tutaj przetasuj i zmiękcz dane) -> K3, V3 Wygeneruj wyjście. K4, V4.
Należy pamiętać, że wszystkie te kroki są tylko operacjami logicznymi, nie powodują zmiany oryginalnych danych.
Twoje pytanie: Jaki jest cel tasowania i sortowania fazy w reduktorze w Map Reduce Programming?
Krótka odpowiedź: Przetwarzanie danych w celu uzyskania pożądanego wyniku. Tasowanie to agregacja danych, redukcja to oczekiwany wynik.
źródło