Jak działa algorytm sortowania MapReduce?

Google Reference: MapReduce: uproszczone przetwarzanie danych na dużych klastrach

Pojawił się w :
OSDI'04: szóste Sympozjum na temat projektowania i wdrażania systemów operacyjnych,
San Francisco, CA, Grudzień 2004.

Ten link ma odniesienie PDF i HTML-Slide.

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

Również krytyka,

David DeWitt i Michael Stonebraker, pionierski ekspert w dziedzinie równoległych baz danych i architektur shared nothing, wysunął kilka kontrowersyjnych twierdzeń na temat zakresu problemów, do których MapReduce może być używany. Nazwali jego interfejs zbyt niskim poziomem i zapytali, Czy naprawdę reprezentuje zmianę paradygmatu, którą twierdzą jego zwolennicy. Kwestionują twierdzenia zwolenników MapReduce o nowości, powołując się na Teradatę jako przykład sztuki wcześniejszej, która istnieje od ponad dwóch dekad; porównali MapReduce programistów do programistów Codasyl, zauważając, że obaj "piszą w języku niskiego poziomu, wykonując niskopoziomową manipulację rekordami". Wykorzystanie plików wejściowych MapReduce i brak wsparcia dla schematów uniemożliwia ulepszenia wydajności włączone przez wspólne funkcje systemu bazodanowego, takie jak B-trees i partycjonowanie hash, chociaż projekty takie jak PigLatin i Sawzall zaczynają rozwiązywać te problemy.

Miałem to samo pytanie podczas czytania papieru MapReduce Google. @Yuval F 's ODPOWIEDŹ prawie rozwiązała moją zagadkę.

Jedną z rzeczy, które zauważyłem podczas czytania gazety, jest to, że magia dzieje się w partycjonowaniu(po mapie, przed redukcją).

Artykuł używa hash(key) mod R jako przykład partycjonowania, ale nie jest to jedyny sposób na partycjonowanie danych pośrednich w różnych zadaniach redukcji.

Wystarczy dodać warunki brzegowe do @Yuval F 's answer to make it complete: przypuśćmy, że min(s) i max(S) są minimalnymi i maksymalnymi kluczami wśród włączonych klawiszy; wszystkie klawisze = max(s) Są podzielone na jedno zadanie redukcji.

Nie ma twardych ograniczeń na próbkowanych klawiszach, takich jak min lub max. Po prostu bardziej równomiernie te klucze r rozmieszczone między wszystkimi kluczami, bardziej "równoległy" ten rozproszony system jest i mniej prawdopodobne, że operator reduce ma problem z przepełnieniem pamięci.

Tylko zgaduję...

Biorąc pod uwagę ogromny zestaw danych, można podzielić dane na kilka kawałków, które mają być przetwarzane równolegle(być może przez numer rekordu, np. rekord 1-1000 = partycja 1, i tak dalej).

Przypisz / zaplanuj każdą partycję do konkretnego węzła w klastrze.

Każdy węzeł klastra będzie dalej łamał (mapował) partycję na własną mini partycję, być może według kolejności alfabetycznej klucza. Więc, w partycji 1, daj mi wszystkie rzeczy, które zaczynają się od A i wyjście to do mini partycji a z X. Utwórz nową A (x), Jeśli obecnie istnieje już A (x). Zastąp x numerem sekwencyjnym(być może jest to zadanie schedulera, aby to zrobić). Czyli podaj mi NASTĘPNY A (X) unikalny identyfikator.

Przekaż (zaplanuj) zadania zakończone przez mapera (poprzedni krok) do" zmniejsz " węzły klastra. Reduce node cluster będzie następnie dalej udoskonalać sortowanie poszczególnych części A (x), które będą się dziać, gdy wszystkie zadania mapera zostaną wykonane (nie można faktycznie rozpocząć sortowania wszystkich słów start w / a, gdy nadal istnieje możliwość, że nadal będzie kolejna mini partycja w tworzeniu). Wypisuje wynik w końcowej części posortowanej (np. posortowane-A, posortowane-B, itd.)

Po zakończeniu ponownie połącz posortowaną partycję w pojedynczy zestaw danych. W tym momencie jest to tylko prosta konkatenacja n plików (gdzie n może być 26 jeśli robisz tylko A-Z), itp.

Mogą istnieć pośrednie kroki pomiędzy nimi... Nie jestem pewien :). Tj. dalsza mapa i redukcja po początkowym kroku redukcji.