Sortowanie dużych danych za pomocą MapReduce / Hadoop

Jak już wspomnieli inni, scalanie jest o wiele prostsze niż sortowanie, więc jest tam duża wygrana.

Jednak wykonywanie operacji szeregowej O(N) na gigantycznym zbiorze danych może być również zaporowe. Jak słusznie zauważyłeś, lepiej jest znaleźć sposób na równoległe połączenie.

Jednym ze sposobów, aby to zrobić, jest zastąpienie funkcji partycjonowania z losowego partycjonera (który jest zwykle używany) na coś nieco mądrzejszego. Co Świnia robi dla tego, na przykład, jest próbka zestaw danych, aby uzyskać przybliżenie rozkładu wartości, a następnie przypisać zakresy wartości do różnych reduktorów. Reduktor 0 pobiera wszystkie elementy = 1000 i

Więc najprostszym sposobem sortowania za pomocą Map-reduce (choć nie najskuteczniejszym) jest wykonanie następujących czynności

Podczas fazy Mapy (Input_Key,Input_value) emit out (Input_value, Input Key)

Reduktor jest reduktorem tożsamości

Więc na przykład, jeśli nasze dane są studentami, bazą wiekową, to Twoje dane mapera będą ("A", 1) ("B", 2) ("C", 10) ... A wyjście będzie (1, A) (2, B) (10, C)

Nie próbowałem tej logiki, ale to krok w odrabianiu lekcji problem, nad którym pracuję. Umieści link do kodu źródłowego/ logiki aktualizacji.

Przepraszam za spóźnienie, ale dla przyszłych czytelników,tak chandler, mylisz się

Logika jest taka, że reduktor może obsłużyć tasowane, a następnie sortowane dane swojego węzła tylko na którym jest uruchomiony. Mam na myśli reduktor, który działa na jednym węźle nie można spojrzeć na dane innego węzła, stosuje redukować algo tylko na swoich danych. Tak więc procedura łączenia rodzaju połączenia nie może być stosowana.

Więc dla big data używamy Tera sort, który jest niczym innym jak identity mapper i reducer z niestandardowym partycjonerem. Czytaj więcej o tym tutaj powinieneś przeczytać więcej o tym tutaj implementacja Hadoop dla Terasort . Stwierdza:

"terasort jest standardowym sortowaniem map/reduce, z wyjątkiem niestandardowego partycjonera, który używa posortowanej listy N - 1 próbkowanych kluczy, które definiują zakres kluczy dla każdego reduce. W szczególności, wszystkie klucze takie, że próbka[i - 1]

Myślę, że łączenie wielu posortowanych elementów jest wydajne niż łączenie wielu niesortowanych elementów. Tak więc maperzy wykonują zadanie sortowania kawałków, a reduktor łączy je. Gdyby maperzy nie robili sortowania, reduktor będzie miał trudny czas na sortowanie.

Sortowanie może być efektywnie zaimplementowane przy użyciu MapReduce. Ale wydaje się, że myślisz o zaimplementowaniu sortowania scalonego za pomocą mapreduce, aby osiągnąć ten cel. To może nie być idealny kandydat.

Jak wspomniałeś, połączenie (z Map-reduce) obejmowałoby następujące kroki:

1. Podziel elementy na małe grupy i przypisz każdą grupę do maperów w sposób round robin
2. Każdy maper posortuje podzbiór i zwróci {K, {subset}}, gdzie K jest takie samo dla all the mappers
3. ponieważ to samo K jest używane we wszystkich maperach, tylko jeden reduktor i stąd tylko jeden reduktor. Reduktor może scalić Dane i zwrócić sortowany wynik

Problem polega na tym, że jak pan wspomniał, może być tylko jeden reduktor, który wyklucza równoległość w fazie redukcji. Tak jak wspomniano w innych odpowiedziach, mapreduce konkretne implementacje, takie jak terasort, mogą być brane pod uwagę w tym celu.

Znalazłem Wyjaśnienie na http://www.chinacloud.cn/upload/2014-01/14010410467139.pdf

Wracając do merge-sort, byłoby to możliwe, gdyby narzędzie hadoop (lub równoważne) dostarczyło hierarchię reduktorów, gdzie wyjście jednego poziomu reduktorów przechodzi do następnego poziomu reduktorów lub zapętla go z powrotem do tego samego zestawu reduktorów