Jakie problemy rozwiązuje MapReduce?

Czytałem o MapReduce od jakiegoś czasu - ale nie rozumiem, w jaki sposób ktoś podejmie decyzję o użyciu (lub nie) użyciu MapReduce.

Mam na myśli, jakie są wzorce problemów, które sygnalizują, że można zastosować MapReduce.

Zasadniczo problemy są ogromne, ale nie trudne. Podróżujący sprzedawca zależy w dużej mierze od odległości między dowolną parą miast, więc chociaż można ją podzielić na wiele części, częściowych wyników nie można zrekombinować, tak aby pojawiło się optymalne globalnie rozwiązanie (cóż, prawdopodobnie nie; jeśli znasz sposób, zgłoś się teraz o medal Fields).

Z drugiej strony, liczenie częstotliwości słów w gigantycznym korpusie jest trywialnie podzielne i trywialnie rekombinowalne (po prostu dodajemy wektory obliczone dla segmentów korpusu), więc redukcja mapy jest oczywistym rozwiązaniem.

W praktyce więcej problemów można łatwo zrekombinować niż nie, więc decyzja, czy zadanie równoległe ma być równoległe, czy nie, ma więcej wspólnego z tym, jak duże jest to zadanie, a mniej z tym, jak trudne.

Czy problem można skutecznie rozwiązać za pomocą przetwarzania rozproszonego?

Jeśli odpowiedź na to pytanie brzmi „tak”, oznacza to, że masz problem z kandydatem na MapReduce. Wynika to z faktu, że wzór problemu dzieli się na mniejsze pojedyncze problemy.

Twoje zadanie: parsuj tę książkę

Przykład dobrze to ilustruje. Masz duży dokument ( Moby Dick autorstwa Hermana Melville'a ), a Twoim zadaniem jest przeprowadzenie analizy częstotliwości wszystkich użytych w nim słów.

Podejście sekwencyjne

Możesz to zrobić sekwencyjnie, zdobywając najszybszą maszynę (masz dużo leżenia) i przeglądając tekst od początku do końca, utrzymując mapę skrótów dla każdego znalezionego słowa (klucz) i zwiększając częstotliwość (wartość) za każdym razem parsujesz słowo. Prosty, bezpośredni i wolny.

Podejście MapReduce

Podchodząc do tego z innej perspektywy, zauważasz, że masz wszystkie te zapasowe maszyny i możesz rozdzielić to zadanie na części. Daj każdej maszynie blok tekstu 1Mb do przetworzenia na mapę skrótu, a następnie zestaw wszystkie mapy skrótów z każdego w jeden wynik. To jest warstwowe rozwiązanie MapReduce.

Proces odczytywania wiersza tekstu i zbierania słów to faza mapy (tworzona jest prosta mapa przedstawiająca słowa w linii z ich częstotliwością 1,2,3 itd.), A następnie faza zmniejszania ma miejsce, gdy każda maszyna zbiera swoją linię mapy w jedną mapę zbiorczą.

Ogólne rozwiązanie pochodzi z kolejnej fazy redukcji, w której wszystkie mapy zbiorcze są agregowane (ponownie to słowo) w ostateczną mapę. Nieco bardziej skomplikowane, masywnie równoległe i szybkie.

Podsumowanie

Podsumowując, jeśli twój problem może być reprezentowany przez klucze, wartości, agreguj operacje na tych wartościach osobno, to masz problem z kandydatem na MapReduce.

Wzorzec MapReduce pochodzi ze świata programowania funkcjonalnego. Jest to proces nakładania równolegle na strukturę danych czegoś zwanego katamorfizmem. Funkcjonalni programiści używają katamorfizmów do prawie każdej prostej transformacji lub podsumowania.

Zakładając, że twoje dane są drzewem, decydującym czynnikiem jest to, czy możesz obliczyć wartość dla węzła, używając tylko danych zawartych w tym węźle i obliczonych wartości dla jego dzieci.

Na przykład możesz obliczyć rozmiar drzewa za pomocą katamorfizmu; obliczyłbyś sumę obliczonych wartości dla wszystkich dzieci plus jedno.

Ten WPI - Aplikacje Map Reduce (ppt) może Cię zainteresować. Omawia różne zastosowania MR, a jako jeden z omawianych przypadków pokazuje, w jaki sposób używając 100 instancji EC2 i 24 godzin, New York Times był w stanie przekonwertować 4 TB zeskanowanych artykułów na 1,5 TB dokumentów PDF.

Kolejny zestaw przykładów, w których MR pomógł w zwiększeniu wydajności, znajduje się w: Aster - SQL Map Reduce pokazuje niektóre studia przypadków technologii SQL-Map Reduce, w tym wykrywanie oszustw, transformacje i inne.

Map / Reduce to specyficzna forma określonego rodzaju algorytmu. Za jego pomocą przekształcasz jeden ogromny zestaw danych w inny zestaw danych. (Wynikowy zestaw danych może, ale nie musi być ogromny.) Jeśli nie chcesz, aby statyczny zestaw danych wyjściowych był wynikiem statycznego wprowadzania danych, wówczas opcja Map / Reduce nie jest odpowiednia. Map / Reduce może łatwo powiedzieć, ile osób John Smiths znajduje się w książce telefonicznej na Manhattanie, ale nie nadaje się do zbudowania serwera internetowego.

Sposób działania funkcji Map / Reduce to:

• Mapa bierze pary kluczy (k1) i wartości (v1) i mapuje je na nowy zestaw kluczy (k2) i wartości (v2).
• Zmniejsz pobiera wszystkie wartości v2 z tym samym kluczem k2 i tworzy nową wartość (v3).

W wyniku tego lista par (k1, v1) jest przekształcana w listę (v3) s. (Oczywiście, wartość „v3” może być kompozycją zawierającą k2, którą można zdefiniować jako równą k1.)

Więc używasz go:

1. Jeśli masz tak dużo danych, aby uruchomić je wszystkie po kolei przez jeden lub dwa serwery, zajęłoby to zbyt długo, a

2. Możesz wyobrazić sobie, że dane wyjściowe są listą wartości lub par klucz-wartość (ogólnie niezbyt trudne, gdy pamiętasz, że „klucz” oznacza tylko „unikalną etykietę”), i

3. Niezależnie od relacji masz pewność, że każdy element danych wejściowych wpływa tylko na wartość wyjściową dla jednego klucza wyjściowego.

Jeśli wszystkie Twoje dane mogą być przetwarzane sekwencyjnie przez jeden serwer, to ponieważ jest to dominujący paradygmat obliczeniowy (te, na których budowane są serwery i na których szkoleni są programiści), użyj jednego serwera.

Etap mapy musi podzielić wszystkie dane wejściowe na partycje według klucza wyjściowego. Nie musi generować wartości wyjściowej powiązanej z kluczem wyjściowym (co jest wykonywane przez etap redukcji), ale musi jednoznacznie przypisywać każdą parę wartości klucza wejściowego, aby przyczynić się do co najwyżej jednej wartości klucza wyjściowego. Jeśli dane są zbyt powiązane, zmniejszenie mapy może nie być w stanie poradzić sobie z problemem. Z drugiej strony może być konieczne użycie wielu rund mapy / zmniejszenia.

Jeśli nie możesz dowiedzieć się, jak przekształcić transformację danych w mapę / zmniejszyć, to oczywiście nie jest to rozwiązanie.

Jest prawdziwą sztuką zastanawianie się, czy problem można rozłożyć na coś, co poradzi sobie Map / Reduce. Na przykład wersje v1 i v2 mogą w ogóle nie znajdować się w zestawach danych wejściowych lub wyjściowych. Jeśli chcesz policzyć unikalne pozycje w danych wejściowych, to k1 = k2 = pozycja, a v1 = v2 = 1 lub 0 lub naprawdę cokolwiek. Zredukuj tylko produkuje v3 jako sumę podanej liczby k2.

Trudno więc powiedzieć na pewno, że transformacji danych nie można dokonać za pomocą funkcji Map / Reduce, ale powyższe informacje zawierają wskazówki.

MapReduce działa na każdy problem, który składa się dokładnie z 2 funkcji na pewnym poziomie abstrakcji. Pierwsza funkcja jest stosowana do każdej pozycji w zestawie danych wejściowych, a druga funkcja agreguje wyniki.

Tak więc, za każdym razem, gdy chcesz uzyskać (1) wynik z (n) danych wejściowych, a wszystkie dane wejściowe mogą być sprawdzone / wykorzystane przez funkcję (1), możesz użyć MapReduce. Ponownie jest to na pewnym określonym poziomie abstrakcji. Funkcja (1) może być funkcją grupującą, która sprawdza dane wejściowe i decyduje, której z kilku innych funkcji użyć.

Jest to przydatne, gdy nie wiesz z góry, ile będziesz miał wkładu, gdy musisz podzielić się dyskretnymi „jednostkami” pracy lub gdy chcesz, aby pojedynczy zwrot reprezentował cały wynik (IE przeprowadzający pięć tysięcy testów jednostkowych , a jeśli mniej niż x% nie powiedzie się, zwróć sukces).

Większość odpowiedzi tutaj wydaje się być pewną odmianą wyjaśniania, co robi redukcja mapy, co jest poprawne. Ale odpowiedź na pytanie, który wzór wskazywałby, gdzie można użyć mapy, nie jest tak naprawdę uwzględniona.

Jeśli naiwna, niefunkcjonalna implementacja problemu, na który patrzysz, polega na zapętlaniu czegoś, a następnie aktualizowaniu czegoś poza pętlą z pewnym stanem z wnętrza pętli, istnieje szansa, że ​​masz coś, co można dobrze odwzorować na mapie. Zwłaszcza jeśli możesz uogólnić aktualizację stanu centralnego do funkcji, która działa tylko z dwoma parametrami i może zagwarantować, że ta funkcja jest przemienna i asocjacyjna.

Powodem, dla którego możesz chcieć użyć map redukowania, jeśli jest to prawda, jest dwojaki: 1) może być nieco czystszy i łatwiejszy do przetestowania i debugowania, jeśli włamiesz rzeczy na mapę i zmniejszysz funkcje. 2) funkcje zmniejszania mapy są bezstanowe i mogą być uruchamiane jednocześnie, co przyspiesza działanie, jeśli masz wiele dostępnych procesorów i coś takiego jak hadoop lub spark, który wykorzystuje to do uruchamiania rzeczy w klastrze.

Jest to miłe, jeśli przeglądasz wiele rzeczy, ale twój przebieg może się różnić w zależności od stopnia skomplikowania mapy / redukcji. Często zdarza się, że kończy się sekwencyjnym łańcuchem lub drzewem redukcji map, w których ostatecznie wszystko jest wąskie gardło na złożonym kroku redukcji na końcu łańcucha. Na przykład wiele algorytmów graficznych trudno jest skutecznie skalować za pomocą tylko zmniejszenia mapy.

Najprostszym przykładem, który działa dobrze z redukcją mapy, jest zliczanie rzeczy, co jest bardzo tanią redukcją. Właśnie dlatego liczba słów jest często stosowanym przykładem redukcji mapy. Przy takim zastosowaniu można prawie oczekiwać liniowej skalowalności pod względem wydajności: każde dodane procesor przyspiesza.

Jeśli wykonujesz dużo programowania funkcjonalnego, zaczynasz napotykać sytuacje wymagające ogólnej mapy i zmniejszenia. Prawdopodobnie widzisz je nawet w programowaniu imperatywnym, ale nie rozpoznajesz ich za maską pętli i akumulatorów.

Jako przykład tego, który ostatnio mi przyszedł, pracowałem nad parserem w Haskell. Aby przetestować analizator składni, przepompowuję listę fragmentów ciągów przez analizator składni, a następnie chcę uzyskać pojedynczy ciąg, który mogę wypisać z moich wyników, aby sprawdzić, czy został poprawnie przeanalizowany. Wygląda to tak:

--my initial set of test data, a list
tests = ["string1", "string2", "string3", ...]

--Map Step: turn strings into parsed results
--note the type, which demonstrates the map
applyParser :: [String] -> [Token]
--The actual function
applyParser input = map parser input

--Second map, turn tokens into output
showTokens :: [Token] -> [String]
showTokens t = map show t

--Reduce step, concat the results
combineResults :: [String] -> String
--In haskell, reduce is the foldl function, which takes an operation to fold with, a starting element, and a list to fold on
combineResults strings = foldl concat "" strings

--Finished program
testParser = print (combineResults(showTokens(applyParser tests)))

Oczywiście jest to po prostu pedagogiczne. Mój rzeczywisty kod wygląda nieco inaczej i używa więcej funkcji wewnętrznych (jak fold concatnie jest potrzebna, ponieważ Haskell zawiera już unlinesto robi [String]->String). Moim głównym celem było to, że nie spodziewałem się użycia mapy / zmniejszenia, kiedy zaczynałem, po prostu dostosowałem się do moich potrzeb. Chciałem zrobić kilka rzeczy z listami, a następnie zamienić moją listę w pojedynczy element wyniku. Użycie map / zmniejsz pojawiło się naturalnie.

Przetwarzanie łańcucha znaków (jak parsowanie) jest jednym z bardzo oczywistych zastosowań redukcji mapy, mapowanie polega na zastosowaniu różnych transformacji tekstu wejściowego i zmniejszeniu go, łącząc tekst wynikowy z powrotem jako wynik. Podobnie, kompilator może być podobny, używając foldów, aby zmienić strumień elementów abstrakcyjnego drzewa składni w lepszą formę (optymalizację).

Czy jest to równoległe?

Każdy problem, który można zrównoważyć, polega zasadniczo na mapowaniu i składaniu; i odwrotnie, krok mapy jest z natury równoległy (a krok składania może być, w zależności od struktury, na której się składa), więc jest to właściwość dwukierunkowa.

Załóżmy, że przeszukujesz klaster serwerów i nie można w tej chwili odpowiedzieć. MapReduce zrobi to, ponieważ nie będzie mógł uzyskać dostępu do tego węzła drzewa na większej mapie, ponieważ przełoży go na później i wykona albo Mapę, albo Zmniejsz. Zasadniczo stara się zagwarantować, że wszystkie informacje są dostępne z nieprzewidywalnością oprogramowania i sprzętu w środowiskach.

Oto główne pytania, które zadaję, by zbadać decyzję o użyciu (lub nie) użycia MapReduce.

• Czy osiągnięcie rozsądnej wydajności wykonywania równoległego przy minimalnym wysiłku programisty jest ważne dla danego problemu?
• Czy mam dostępną dużą liczbę (setki) równoległych elementów wykonawczych?
• Czy istnieje doskonała przepustowość / przepustowość komunikacji między równoległymi elementami wykonawczymi?
• Czy muszę przetwarzać ogromną ilość (TB) danych?

• Czy problem, który próbuję rozwiązać, rozkłada się na mapę i zmniejsza działanie?

  • Mapa: Wykonaj tę samą operację na wszystkich danych.
  • Zmniejsz: Wykonaj tę samą operację na każdej grupie danych wygenerowanych przez Mapę.

w efekcie jest to ogólny wzorzec „dziel i rządź”, dzięki czemu rozwiązania dotyczące dystrybucji obliczeń można pisać ogólnie.

prosty przykład jest jak duży dokument. Problem polega na tym, że chcesz policzyć liczbę liter w tym dokumencie. zamiast uruchamiać na jednym komputerze, możesz podzielić go na tablicę wszystkich słów w dokumencie. następnie możesz przetworzyć każde słowo osobno, a wyniki ponownie połączyć.

wzorzec jest użyteczny, ponieważ po otrzymaniu ogólnej mapy / zmniejszeniu implementacji możesz rozwiązać każdy problem za pomocą tej samej warstwy oprogramowania, wystarczy wyrazić swój problem w odniesieniu do niego.