Jednym z głównych przykładów wykorzystywanych do zademonstrowania możliwości MapReduce jest test porównawczy Terasort . Mam problem ze zrozumieniem podstaw algorytmu sortowania używanego w środowisku MapReduce.
Dla mnie sortowanie polega po prostu na określeniu względnego położenia elementu w stosunku do wszystkich innych elementów. Tak więc sortowanie polega na porównywaniu „wszystkiego” ze „wszystkim”. Twój przeciętny algorytm sortowania (szybki, bąbelkowy, ...) robi to po prostu w inteligentny sposób.
Moim zdaniem podzielenie zbioru danych na wiele części oznacza, że możesz posortować pojedynczy element, a następnie nadal musisz zintegrować te elementy w „kompletnym”, w pełni posortowanym zbiorze danych. Biorąc pod uwagę zestaw danych terabajtów rozproszonych w tysiącach systemów, spodziewam się, że będzie to ogromne zadanie.
Więc jak to się naprawdę robi? Jak działa ten algorytm sortowania MapReduce?
Dzięki za pomoc w zrozumieniu.
Miałem to samo pytanie, czytając artykuł Google MapReduce. @Yuval F „s odpowiedź prawie rozwiązał zagadkę.
Jedną rzeczą, którą zauważyłem podczas czytania pracy, jest to, że magia dzieje się podczas partycjonowania (po mapie, przed redukcją).
W artykule
hash(key) mod R
przedstawiono przykład partycjonowania, ale nie jest to jedyny sposób podziału danych pośrednich na różne zadania redukcji.Wystarczy dodać warunki brzegowe do @Yuval F „s odpowiedzi , aby to kompletna: Załóżmy min (S) i max (S) jest kluczem minimalna i maksymalna klucz między próbą kluczy; wszystkie klucze <min (S) są partycjonowane do jednego zadania redukcji; odwrotnie, wszystkie klucze> = max (S) są podzielone na partycje do jednego zadania redukcji.
Nie ma sztywnych ograniczeń dotyczących próbkowanych klawiszy, takich jak min lub max. Po prostu, bardziej równomiernie te klucze R są rozdzielone między wszystkie klucze, bardziej „równoległy” jest ten system rozproszony i mniej prawdopodobne jest, że operator redukujący ma problem z przepełnieniem pamięci.
źródło
Tylko zgaduję...
Biorąc pod uwagę ogromny zestaw danych, można podzielić dane na kilka fragmentów, które mają być przetwarzane równolegle (być może według numeru rekordu, tj. Rekord 1 - 1000 = partycja 1 itd.).
Przypisz / zaplanuj każdą partycję do określonego węzła w klastrze.
Każdy węzeł klastra dalej dzieli (mapuje) partycję na własną mini partycję, być może według kolejności alfabetycznej kluczy. Więc w partycji 1 pobierz wszystkie rzeczy, które zaczynają się od A i wyślij je do mini partycji A z x. Utwórz nowe A (x), jeśli obecnie istnieje już A (x). Zastąp x kolejnym numerem (być może jest to zadanie harmonogramu). To znaczy podaj kolejny unikalny identyfikator A (x).
Przekaż (zaplanuj) zadania wykonane przez program odwzorowujący (poprzedni krok) do „zredukowania” węzłów klastra. Zmniejszenie klastra węzłów spowoduje dalsze udoskonalenie rodzaju każdej części A (x), które wystąpią tylko wtedy, gdy zostaną wykonane wszystkie zadania programu mapującego (nie można faktycznie rozpocząć sortowania wszystkich słów zaczynających się w / A, gdy nadal istnieje możliwość będzie kolejna mini partycja w trakcie tworzenia). Wyświetl wynik w ostatecznej posortowanej części (tj. Sorted-A, Sorted-B itp.)
Po zakończeniu ponownie połącz posortowaną partycję w jeden zestaw danych. W tym momencie jest to po prostu zwykła konkatenacja n plików (gdzie n może wynosić 26, jeśli robisz tylko A - Z) itd.
Między ... nie jestem pewien :). To znaczy dalej mapuj i zmniejszaj po początkowym kroku redukcji.
źródło