Dzielenie problemu na mniejsze, aż poszczególne problemy można rozwiązać samodzielnie, a następnie łączenie ich w celu odpowiedzi na pierwotne pytanie jest znane jako technika projektowania algorytmu dziel i zwyciężaj . [Zobacz: Wprowadzenie do algorytmów CLR]
Ostatnio takie podejście do rozwiązywania problemów obliczeniowych, szczególnie w dziedzinie bardzo dużych zestawów danych, nazwano MapReduce, a nie dzieleniem i podbijaniem.
Moje pytanie brzmi: czy MapReduce jest czymś więcej niż zastrzeżoną ramą, która opiera się na podejściu dziel i zwyciężaj, czy też są jakieś szczegóły, które czynią go wyjątkowym pod jakimś względem?
algorithms
otto
źródło
źródło
Odpowiedzi:
Jeśli pytasz o architekturę MapReduce, to jest to po prostu technika dzielenia i podbijania . Jednak każda użyteczna architektura MapReduce będzie dysponować górami innej infrastruktury, aby skutecznie „dzielić”, „podbijać”, a na koniec „redukować” zestaw problemów. Przy dużym wdrożeniu MapReduce (1000 węzłów obliczeniowych) te kroki do podziału pracy na partycje, obliczenia czegoś, a następnie zebrania wszystkich wyników nie są trywialne. Rzeczy takie jak równoważenie obciążenia, wykrywanie martwych węzłów, zapisywanie stanu przejściowego (w przypadku problemów długotrwałych), same w sobie są trudnymi problemami.
źródło
MapReduce to platforma do implementacji algorytmów dziel i zwyciężaj w niezwykle skalowalny sposób , automatycznie dystrybuując jednostki pracy do węzłów w dowolnie dużym klastrze komputerów i automatycznie obsługując awarie poszczególnych węzłów poprzez redystrybucję jednostki pracy do innego węzła.
To nie jest bardzo wyrafinowana koncepcja, ale bardzo przydatny element infrastruktury.
źródło
MapReduce odbiega od większości systemów dzielenia i podbijania w dość fundamentalny sposób, ale taki, który jest tak prosty, że wiele osób prawie za nim tęskni. Prawdziwy geniusz polega na oznaczaniu wyników pośrednich.
W typowym (poprzednim) systemie dzielenia i podbijania dzielisz pracę szeregowo, równolegle wykonujesz pakiety robocze, a następnie ponownie scalasz wyniki z pracy.
W MapReduce dzielisz pracę szeregowo, równolegle wykonujesz pakiety robocze i otagujesz wyniki, aby wskazać, które wyniki towarzyszą innym wynikom. Scalanie jest następnie szeregowe dla wszystkich wyników z tym samym znacznikiem, ale może być wykonane równolegle dla wyników, które mają różne znaczniki.
W większości poprzednich systemów krok scalania stał się wąskim gardłem w przypadku wszystkich zadań oprócz najbardziej trywialnych. Dzięki MapReduce nadal może tak być, jeśli charakter zadań wymaga, aby wszystkie połączenia były wykonywane szeregowo. Jeśli jednak zadanie pozwala na pewien stopień równoległego łączenia wyników, MapReduce daje prosty sposób na skorzystanie z tej możliwości. Większość innych systemów wykonuje jedną z dwóch czynności: albo wykonuje wszystkie scalenia szeregowo tylko dlatego, że może być konieczne do niektórych zadań, albo statycznie definiuje równoległe scalanie dla konkretnego zadania. MapReduce zapewnia wystarczającą ilość danych na etapie łączenia, aby automatycznie zaplanować jak najwięcej równolegle, jak to możliwe, przy jednoczesnym zapewnieniu (zakładając, że nie popełniłeś błędów w etapie mapowania), że zachowana jest spójność.
Zauważ też, że w MapReduce domyślnie zakłada się, że wszystkie kroki mogą być rekurencyjne, więc mogę mieć początkowy krok mapowania, który dzieli duże zadanie na 5 mniejszych zadań, które można wykonać równolegle - ale każdy z nich może (w kolei) zostaną przypisane do szeregu innych mniejszych równoległych zadań i tak dalej.
Prowadzi to do struktury drzewa zarówno po stronie mapowania, jak i strony redukującej, aby szybko rozbić duże zadanie na wystarczającą liczbę części, aby skorzystać z wielu maszyn.
źródło
MapReduce to nie tylko technika dzielenia i podbijania, choć tak wygląda na wielu przykładach.
Na etapie mapowania możesz i często chcesz nawiązać relację jeden do wielu. Zatem nie dzielisz się po prostu na przypadki.
Pomiędzy mapą a redukcją jest (w zależności od implementacji) krok sortowania lub mieszania. Wydajność tej operacji jest niezwykle ważna dla ogólnych wymagań dotyczących zasobów. Jego szczegóły są niewidoczne dla programisty aplikacji, ale ten krok jest sercem frameworka.
Operacja redukcji jest rodzajem scalania. Co można uznać za podbój, ale w praktyce zwykle albo „emituje dane do późniejszego wykorzystania”, albo „zapisuje dane w magazynie danych”. (Uwaga: jeśli masz duże zestawy danych, naprawdę chcesz, aby wszystko było dystrybuowane, w tym dane wejściowe i końcowe. Tak więc rozproszony magazyn kluczy / wartości ma sens zarówno jako miejsce do uzyskania danych wejściowych, jak i do przechowywania danych wyjściowych.)
źródło