Jaka jest nowość w MapReduce?

67

Kilka lat temu MapReduce został okrzyknięty rewolucją programowania rozproszonego. Byli też krytycy, ale ogólnie był entuzjastyczny szum. Zostało nawet opatentowane! [1]

Nazwa nawiązuje mapi reduceprogramowania funkcjonalnego, ale kiedy czytam (Wikipedia)

Krok mapy: węzeł główny pobiera dane wejściowe, dzieli je na mniejsze podproblemy i rozdziela je na węzły robocze. Węzeł roboczy może to po kolei zrobić ponownie, prowadząc do wielopoziomowej struktury drzewa. Węzeł roboczy przetwarza mniejszy problem i przekazuje odpowiedź z powrotem do swojego węzła głównego.

Zmniejsz krok: węzeł główny zbiera następnie odpowiedzi na wszystkie podproblemy i łączy je w jakiś sposób, aby uzyskać wynik - odpowiedź na problem, który pierwotnie próbował rozwiązać.

lub [2]

Elementy wewnętrzne MAP: [...] MAP dzieli wartość wejściową na słowa. [...] MAP ma na celu powiązanie każdej podanej pary klucz / wartość wejścia z potencjalnie wieloma pośrednimi parami klucz / wartość.

Wartości wewnętrzne REDUCE: [...] [REDUCE] wykonuje agregację imperatywną (powiedzmy redukcję): weź wiele wartości i zredukuj je do jednej wartości.

Nie mogę przestać myśleć: to podział i podbój (w znaczeniu Mergesort), prosty i prosty! Czy jest więc gdzieś (konceptualna) nowość w MapReduce, czy jest to tylko nowa implementacja starych pomysłów przydatnych w niektórych scenariuszach?

Patent USA 7650331: „System i metoda wydajnego przetwarzania danych na dużą skalę” (2010)
Model programowania MapReduce firmy Google - ponownie odwiedził R. Lämmel (2007)

algorithms distributed-systems parallel-computing algorithm-design Raphael
źródło

7

Nie ma nowości. Nie udzielę odpowiedzi, ale jestem głęboko przekonany, że MapReduce nie odkrył niczego nowego w obliczeniach, a nawet obliczeniach rozproszonych.

edA-qa mort-ora-y

@Aryabhata: Jeśli jest nowość, to pytanie ma dobrą, konstruktywną odpowiedź. Jeśli tak nie jest, niewiele można udowodnić (poza wyraźnym sprowadzeniem MapReduce do starszej techniki), to prawda. Ale jeśli tak się czujesz, głosuj!

Raphael

@ edA-qamort-ora-y: W takim przypadku powinniśmy być w stanie wyrazić MapReduce starszymi terminami, a to byłaby dobra odpowiedź!

Raphael

1

@Raphael, zgadzam się, ale nie jestem pewien, czy dam radę. Widzę jednak, że jak opisano tutaj (pierwszy cytat), sortowanie według scalania używa dokładnej metody mapowania / zmniejszania. Można go rzeczywiście rozdzielić z zerową zmianą.

edA-qa mort-ora-y

47

Nie mogę przestać myśleć: to jest podział i podbój, jasne i proste!

M / R nie dzieli i podbija. Nie wymaga wielokrotnego zastosowania algorytmu do mniejszego podzbioru poprzedniego wejścia. Jest to potok (funkcja określona jako kompozycja prostszych funkcji), w którym etapy potoku zmieniają mapę i zmniejszają operacje. Różne etapy mogą wykonywać różne operacje.

Czy jest więc gdzieś (konceptualna) nowość w MapReduce, czy to tylko nowa implementacja starych pomysłów przydatnych w niektórych scenariuszach?

MapReduce nie stanowi przełomu w teorii obliczeń - nie pokazuje nowego sposobu rozkładania problemu na prostsze operacje. To pokazuje, że szczególne prostsze operacje są praktyczne dla określonej klasy problemu.

Wkład papieru MapReduce był

ocena potoku dwóch dobrze zrozumiałych operatorów ortogonalnych, które mogą być wydajnie i odporne na uszkodzenia w przypadku konkretnego problemu: tworzenie indeksu tekstowego o dużym korpusie
analiza porównawcza zmniejsz mapę tego problemu, aby pokazać, ile danych jest przesyłanych między węzłami i jak różnice latencji na etapach wpływają na ogólne opóźnienie
pokazując, jak uczynić system odpornym na awarie, aby awarie maszyny podczas obliczeń mogły być automatycznie kompensowane
określanie konkretnych przydatnych opcji i optymalizacji wdrażania

Niektóre krytyki należą do tych klas:

„Mapa / redukcja nie otwiera nowych gruntów w teorii obliczeń”. Prawdziwe. Pierwotny wkład artykułu polegał na tym, że tych dobrze rozumianych operatorów ze specyficznym zestawem optymalizacji wykorzystano z powodzeniem do rozwiązywania rzeczywistych problemów łatwiej i bardziej odpornych na uszkodzenia niż rozwiązania jednorazowe.
„To rozproszone obliczenia nie rozkładają się łatwo na mapę i nie ograniczają operacji”. W porządku, ale wielu tak.
„Potok n etapów mapy / redukcji wymaga opóźnienia proporcjonalnego do liczby kroków redukcji rurociągu przed uzyskaniem jakichkolwiek wyników.” Prawdopodobnie prawdziwe. Operator redukcji musi otrzymać cały swój wkład, zanim będzie w stanie uzyskać pełną moc wyjściową.
„Mapowanie / zmniejszanie to przesada w tym przypadku użycia”. Może. Kiedy inżynierowie znajdują nowy błyszczący młotek, zwykle szukają czegoś, co wygląda jak gwóźdź. To nie znaczy, że młot nie jest dobrze wykonanym narzędziem dla pewnej niszy.
„Mapuj / zmniejsz to kiepski zamiennik relacyjnej bazy danych”. Prawdziwe. Jeśli relacyjna baza danych skaluje się do zestawu danych, to jest to dla Ciebie wspaniałe - masz opcje.

Mike Samuel
źródło

Nazywają oryginalny artykuł „przełomowym”, więc oczekuję czegoś nowego. Nie rozumiem twojego pierwszego akapitu: wyraźnie jest wiele technik algorytmicznych, które nie dzielą i nie podbijają . Jeśli MapReduce jest „tylko” wydajną implementacją d & c dla określonego zestawu problemów, z pewnością nie ma nic znaczącego ani patentowego w zakresie algorytmiki (imho). To nie znaczy, że to nie jest dobry system. Zauważ, że moja krytyka nie dotyczy samego MapReduce (wydaje mi się, że jest dobry do tego, do czego został stworzony) niż jego odbioru przez społeczność.

Raphael

1

@ Rafael, nie sądzę, że M / R jest dzieleniem i podbijaniem w sensie, do którego linkujesz. Nie wymaga wielokrotnego stosowania algorytmu do mniejszego podzbioru oryginalnego wejścia. Jest to rurociąg, w którym etapy rurociągu zmieniają mapę i ograniczają operacje.

Mike Samuel,

Prawda. Zinterpretowałem: „Węzeł roboczy może to po kolei zrobić ponownie, prowadząc do wielopoziomowej struktury drzewa”. w ten sposób, ale to oczywiście nie oznacza, że to samo dzieje się na każdym poziomie.

Raphael

1

@ ex0du5, myślę, że potępiasz go za roszczenia, których nie czyni. „Wiele systemów zapewniło ograniczone modele programowania i zastosowało ograniczenia do automatycznego zrównoleglenia obliczeń. ... MapReduce można uznać za uproszczenie i destylację niektórych z tych modeli w oparciu o nasze doświadczenia z dużymi obliczeniami w świecie rzeczywistym. W przeciwieństwie do tego , większość systemów przetwarzania równoległego została zaimplementowana tylko w mniejszych skalach i pozostawia programistom szczegółowe informacje o awariach obsługi ”. Przytacza na ten temat papiery Rabina i Valianta, ale nie gazetę Liskowa.

Mike Samuel,

1

@ ex0du5, wystarczy. Myślałem, że „Mapuj / zmniejszaj nie otwiera nowych gruntów w teorii obliczeń.” Prawda ”. było wystarczająco jasne, ale przepisałem listę wpisów.

Mike Samuel,

21

EDIT (marzec 2014) Powinienem powiedzieć, że od tego czasu pracowałem więcej nad algorytmami modeli obliczeniowych typu MapReduce i czuję, że byłem zbyt negatywny. Technika Divide-Compress-Conquer, o której mówię poniżej, jest zaskakująco wszechstronna i może być podstawą algorytmów, które moim zdaniem są nietrywialne i interesujące.

Pozwól, że dam odpowiedź, która będzie znacznie gorsza od Mike'a pod względem kompleksowości, ale z modelu obliczeniowego / teorii algorytmów.

Dlaczego jest podniecenie : MapReduce przeplata obliczenia równoległe i sekwencyjne; każdy procesor ma dostęp do nietrywialnego fragmentu (np. ) wejścia i może na nim wykonywać nietrywialne operacje; to bardzo różni się od modeli PRAM i wydaje się interesującym pomysłem, który może prowadzić do nowych technik algorytmicznych. W szczególności niektóre problemy można rozwiązać w kilku rundach obliczeń (o stałej wielkości wejściowej), natomiast w pamięci PRAM w nie można rozwiązać żadnych niebanalnych problemów . $O(n^\epsilon)$ $o(\log n)$

Dlaczego model jest dla mnie trochę frustrujący : Jedyną techniką algorytmiczną, która wydaje się działać, aby uzyskać algorytmy i jest nieco nowa, są następujące $O(1)$

Podziel wystąpienie problemu na partycje (często losowo)
Czy jakieś obliczenia na każdej partycji równolegle i reprezentują wynik obliczeń kompaktowo
Połącz wszystkie kompaktowo reprezentowane rozwiązania podproblemów na jednym procesorze i zakończ tam obliczenia

Bardzo prosty przykład techniki: oblicz sumę liczb. Każdy procesor ma tablicy i oblicza sumę tej części. Następnie wszystkie sumy można połączyć na jednym procesorze, aby obliczyć całkowitą sumę. Nieco ciekawszym ćwiczeniem jest obliczenie wszystkich sum prefiksów w ten sposób (oczywiście w takim przypadku dane wyjściowe muszą być reprezentowane w sposób rozproszony). Lub obliczyć rozciągające się drzewo gęstego wykresu. $n$ $O(\sqrt{n})$ $\sqrt{n}$

Teraz myślę, że to naprawdę interesujący zwrot akcji dziel i zwyciężaj, przy czym po etapie podziału musisz skompresować rozwiązania podproblemowe, aby pojedynczy procesor mógł zwyciężyć. Wydaje się jednak, że jest to jedyna technika, jaką do tej pory wymyśliliśmy. Nie działa w przypadku problemów z rzadkimi grafami, takich jak na przykład rzadka łączność. Porównaj to z modelem przesyłania strumieniowego, który doprowadził do wielu nowych pomysłów, takich jak genialny algorytm próbkowania Flajoleta i Martina, algorytm deterministycznego parowania Misry i Griesa, moc prostych technik szkicowania itp.

Jako paradygmat programowania redukcja mapy okazała się bardzo udana. Moje komentarze traktują redukcję mapy jako interesujący model obliczeń. Dobre modele teoretyczne są trochę dziwne. Jeśli zbyt blisko podążają za rzeczywistością, są nieporęczne, ale co ważniejsze (aby pożyczyć termin od uczenia maszynowego) twierdzenia udowodnione dla modeli, które są zbyt specyficzne, nie uogólniają, tj. Nie trzymają się innych modeli. Dlatego chcemy wyodrębnić jak najwięcej szczegółów, jednocześnie pozostawiając wystarczająco dużo, aby rzucić nam wyzwanie, aby wymyślić nowe algorytmy. Wreszcie, te nowe pomysły powinny ostatecznie znaleźć drogę do prawdziwego świata. PRAM to jeden nierealistyczny model, który doprowadził do interesujących pomysłów, ale te pomysły rzadko okazały się przydatne do obliczeń równoległych w świecie rzeczywistym. Z drugiej strony streaming jest również nierealny, ale zainspirowało idee algorytmiczne, które są faktycznie stosowane w prawdziwym świecie. Widziećszkic odliczający min . Techniki szkicowania są w rzeczywistości również stosowane w systemach opartych na redukcji map.

Sasho Nikolov
źródło

Prawdopodobnie M / R jest bardziej realistycznym (użytecznym) modelem niż PRAM lub strumienie. (Przynajmniej z powodu dość dużego zestawu problemów.)

Xodarap

„musisz skompresować rozwiązania podproblemów, aby pojedynczy procesor mógł pokonać” - Wydaje się, że mówisz, że zestaw problemów, które można rozwiązać za pomocą M / R, jest podzbiorem tych, dla których istnieje możliwa do rozpoznania pamięć podręczna lub pamięć podręczna -oczywiste rozwiązania. Jeśli to prawda, wydaje mi się, że to stwierdzenie stosuje się równie dobrze do większości rozproszonych schematów obliczeniowych.

Mike Samuel,

1

@ Xodarap, który może być. tutaj używam czysto teoretycznego punktu widzenia algorytmów: model jest użyteczny, jeśli prowadzi do nowych perspektyw algorytmicznych. w ten sposób streaming nie jest całkowicie realistyczny, ale doprowadził do powstania wielu nowych technik, które faktycznie są przydatne w praktyce. chodzi o to, jaka jest właściwa abstrakcja, która prowadzi do nowego myślenia. obecne abstrakcje MR mają mieszany sukces (ale chyba pewien sukces)

Sasho Nikolov

1

@MikeSamuel „potrzeba” w tym zdaniu oznacza, że technika wymaga pracy, a nie jedyna możliwa rzecz do zrobienia. nie ma teoretycznych negatywnych wyników dla MR, które znam. moja skarga nie polega na tym, że MR jest znacznie mniej wydajny niż CO. jest to, że nie widzieliśmy wiele nowych myślenia algorytmicznego zainspirowanych modelem (co jest dobre dla systemu, ale rozczarowujące dla modelu obliczeń). z drugiej strony sama pamięć o pamięci podręcznej jest niesamowitym pomysłem imo

Sasho Nikolov

@SashoNikolov, Zrozumiano. Dziękuję za wyjaśnienie.

Mike Samuel,

6

Całkowicie się z Tobą zgadzam. Z perspektywy konceptualnej nie ma nic naprawdę nowego: Map / Reduce był pierwotnie znany w Parallel Computing jako model programowania przepływu danych. Jednak z praktycznego punktu widzenia Map / Reduce zaproponowany przez Google i wraz z kolejnymi implementacjami typu open source również zasilił Cloud Computing i jest teraz dość popularny w przypadku bardzo prostych równoległych rozkładów i przetwarzania. Oczywiście nie nadaje się do niczego, co wymaga złożonej domeny lub rozkładów funkcjonalnych.

Massimo Cafaro
źródło

3

Myślę, że trafiłeś w sedno swoim komentarzem.

Nie jest prawdą, że w funkcjonalnych mapach językowych można równolegle łączyć - język musi być czysty . (Uważam, że Haskell to jedyny niejasny język funkcjonalny w mainstreamie. Lisp, OCaml i Scala nie są czyste).

O zaletach czystego kodu wiemy już od czasów dzielenia czasu, kiedy inżynierowie po raz pierwszy potokowali swoje procesory. Dlaczego więc nikt nie używa czystego języka?

To jest naprawdę bardzo trudne. Programowanie w czystym języku często przypomina programowanie obiema rękami za plecami.

MR łagodzi nieco ograniczenie czystości i zapewnia ramy dla innych elementów (takich jak faza losowania), dzięki czemu dość łatwo jest napisać kod dystrybucyjny dla dużej części problemów.

$NC=P$

Xodarap
źródło

Nie jestem zaznajomiony z MapReduce, ale twoja prezentacja tego nie wygląda inaczej niż to, co pamiętam, że zostało przedstawione jako idealny przypadek w Parallelism 101 w poprzednim stuleciu.

Gilles,

@Gilles: Moim zamiarem było po prostu pokazać, że „dziel i rządź” = „ dystrybuowana dziel i rządź.” M / R jest mniej trywialny, choć zapewne wciąż nieoryginalny.

Xodarap,

W programowaniu funkcjonalnym wszystkie mapy można sparaliżować (żenująco), więc dlaczego nie trzymać się tego paradygmatu? Nie widzę, jak countzmienna współdzielona jest w twoim pseudo-kodzie; po prostu przekazanie bieżącej wartości do do_somethingpowinno działać. Czy możesz podać przykład „prawdziwego” algorytmu D&C (Mergesort, Quicksort, ...), dla którego wywołania rekurencyjne zależą od siebie (po wysłaniu połączenia)?

Raphael

@Raphael: Przepisałem odpowiedź, aby lepiej odpowiedzieć na Twój komentarz. Mogę dodać przykład, kiedy czystość jest denerwująca, jeśli nadal chcesz.

Xodarap,

1

@Raphael: Zgadzam się, że moja odpowiedź byłaby znacznie lepsza, gdybym mógł zacytować artykuł wskazujący, że czas programowania skraca się z X godzin do Y przy użyciu M / R lub zwiększa się z A do B poprzez wymuszanie czystości, ale myślę, że wszystko, co mogę robi macha wściekle rękami i nalega, aby różnice nie były trywialne.

Xodarap,

Jaka jest nowość w MapReduce?

Odpowiedzi: