Jak działa algorytm sortowania MapReduce?

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.

Oto kilka szczegółów na temat implementacji Hadoop dla Terasort :

TeraSort to standardowe sortowanie według mapowania / redukowania, z wyjątkiem niestandardowego programu do partycjonowania, który używa posortowanej listy N-1 próbkowanych kluczy, które definiują zakres kluczy dla każdego ograniczenia. W szczególności wszystkie klucze takie, że sample [i - 1] <= key <sample [i] są wysyłane w celu zmniejszenia i. Gwarantuje to, że wynik funkcji redukuj i jest mniejszy niż wynik funkcji zmniejszaj i + 1. "

Więc ich sztuczka polega na sposobie, w jaki określają klucze podczas fazy mapy. Zasadniczo zapewniają one, że każda wartość w pojedynczym reduktorze jest „wstępnie posortowana” względem wszystkich innych reduktorów.

Odniesienie do papieru znalazłem w blogu Jamesa Hamiltona .

Odnośnik Google: MapReduce: Uproszczone przetwarzanie danych w dużych klastrach

Opublikowano w :
OSDI'04: Sixth Symposium on Operating System Design and Implementation,
San Francisco, CA, grudzień 2004.

To łącze zawiera odnośnik do slajdów w formacie PDF i HTML.

Istnieje również strona Wikipedii z opisem z odniesieniami do implementacji.

Także krytyka,

David DeWitt i Michael Stonebraker, pionierzy w dziedzinie równoległych baz danych i nie dzielący się żadnymi architekturami, sformułowali kilka kontrowersyjnych twierdzeń na temat zakresu problemów, do których można wykorzystać MapReduce. Nazwali jego interfejs zbyt niskim poziomem i zastanawiali się, czy naprawdę reprezentuje zmianę paradygmatu, jak twierdzili jego zwolennicy. Podważają twierdzenia zwolenników MapReduce o nowości, cytując Teradatę jako przykład wcześniejszej sztuki istniejącej od ponad dwóch dekad; porównali programistów MapReduce z programistami Codasyl, zauważając, że obaj „piszą w języku niskiego poziomu, wykonując manipulację rekordami niskiego poziomu”. Wykorzystanie przez MapReduce plików wejściowych i brak obsługi schematów uniemożliwia poprawę wydajności, którą zapewniają wspólne funkcje systemu baz danych, takie jak B-drzewa i partycjonowanie hashów,

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 Rprzedstawiono 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.

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.