MapaReduce - MapReduce

MapReduce to model programowania i powiązana z nim implementacja do przetwarzania i generowania dużych zbiorów danych z równoległym , rozproszonym algorytmem w klastrze .

Program MapReduce składa się z procedury mapy , która wykonuje filtrowanie i sortowanie (np. sortowanie uczniów według imienia do kolejek, jedna kolejka dla każdego nazwiska) oraz metody zmniejszania , która wykonuje operację sumaryczną (np. liczenie liczby uczniów w każdej kolejce, z podaniem częstotliwości imion). W „MapReduce System” (zwany również „Infrastruktura” lub „ramy”) aranżuje przetwarzanie przez punkt etapowy rozproszonych serwerów, uruchamiając różne zadania równolegle, zarządzanie wszystkimi komunikację i transmisję danych pomiędzy różnymi częściami systemu oraz zapewniając nadmiarowość i odporność na uszkodzenia .

Model jest specjalizacją strategii split-apply-combine do analizy danych. Jest inspirowany mapie i zmniejszyć funkcje powszechnie stosowanych w programowaniu funkcjonalnym , choć ich przeznaczenie w ramach MapReduce nie jest taka sama jak w oryginalnych formach. Kluczowym wkładem struktury MapReduce nie jest faktyczna mapa i funkcje redukujące (które na przykład przypominają operacje redukujące i rozpraszające w standardzie Message Passing Interface z 1995 r. ), ale skalowalność i odporność na błędy osiągnięte dla różnych aplikacji poprzez optymalizację silnik wykonawczy. W związku z tym jednowątkowa implementacja MapReduce zwykle nie jest szybsza niż tradycyjna implementacja (bez MapReduce); wszelkie zyski są zwykle widoczne tylko w przypadku wielowątkowych implementacji na sprzęcie wieloprocesorowym. Korzystanie z tego modelu jest korzystne tylko wtedy, gdy w grę wchodzą zoptymalizowane działanie rozproszonego odtwarzania losowego (co zmniejsza koszty komunikacji sieciowej) i funkcje odporności na awarie platformy MapReduce. Optymalizacja kosztów komunikacji jest niezbędna dla dobrego algorytmu MapReduce.

Biblioteki MapReduce zostały napisane w wielu językach programowania, z różnymi poziomami optymalizacji. Popularna implementacja open-source , która obsługuje rozproszone shuffle, jest częścią Apache Hadoop . Nazwa MapReduce pierwotnie odnosiła się do zastrzeżonej technologii Google , ale od tego czasu została uogólniona . Do 2014 r. Google nie używał już MapReduce jako podstawowego modelu przetwarzania dużych zbiorów danych , a rozwój na Apache Mahout przeniósł się do bardziej wydajnych i mniej zorientowanych na dysk mechanizmów, które zawierały pełną mapę i zmniejszały możliwości.

Niektóre procesory Vector, takie jak NEC SX-Aurora TSUBASA, mają wbudowaną obszerną obsługę mapreduce w instrukcjach Vector, w tym w wektorach RISC-V

Przegląd

MapReduce to platforma do przetwarzania równoległych problemów w dużych zestawach danych przy użyciu dużej liczby komputerów (węzłów), określanych zbiorczo jako klaster (jeśli wszystkie węzły znajdują się w tej samej sieci lokalnej i używają podobnego sprzętu) lub siatkę (jeśli węzły są współużytkowane przez systemy rozproszone geograficznie i administracyjnie oraz wykorzystujące bardziej heterogeniczny sprzęt). Przetwarzanie może odbywać się na danych przechowywanych w systemie plików (nieustrukturyzowanym) lub w bazie danych (ustrukturyzowany). MapReduce może wykorzystać lokalizację danych, przetwarzając je w pobliżu miejsca ich przechowywania w celu zminimalizowania kosztów komunikacji.

Struktura (lub system) MapReduce składa się zwykle z trzech operacji (lub kroków):

  1. Mapa: każdy węzeł roboczy stosuje mapfunkcję do danych lokalnych i zapisuje dane wyjściowe w magazynie tymczasowym. Węzeł główny zapewnia przetwarzanie tylko jednej kopii nadmiarowych danych wejściowych.
  2. Shuffle: węzły robocze redystrybuują dane na podstawie kluczy wyjściowych (wytworzonych przez mapfunkcję), tak że wszystkie dane należące do jednego klucza znajdują się w tym samym węźle roboczym.
  3. Zmniejszenie: węzły robocze przetwarzają teraz równolegle każdą grupę danych wyjściowych według klucza.

MapReduce pozwala na rozproszone przetwarzanie mapy i operacje redukcji. Mapy mogą być wykonywane równolegle, pod warunkiem, że każda operacja mapowania jest niezależna od pozostałych; w praktyce jest to ograniczone liczbą niezależnych źródeł danych i/lub liczbą procesorów w pobliżu każdego źródła. Podobnie, zestaw „reduktorów” może przeprowadzić fazę redukcji, pod warunkiem, że wszystkie wyjścia operacji mapy, które mają ten sam klucz, są prezentowane w tym samym czasie temu samemu reduktorowi lub że funkcja redukcji jest asocjacyjna . Chociaż proces ten często wydaje się nieefektywny w porównaniu z algorytmami, które są bardziej sekwencyjne (ponieważ musi być uruchomionych wiele wystąpień procesu redukcji), MapReduce można zastosować do znacznie większych zestawów danych niż może obsłużyć pojedynczy serwer „towarowy” – może użyć dużej farmy serwerów MapReduce do sortowania petabajta danych w zaledwie kilka godzin. Równoległość daje również pewną możliwość odzyskania częściowej awarii serwerów lub pamięci masowej podczas operacji: jeśli jeden mapper lub reduktor ulegnie awarii, pracę można przełożyć – zakładając, że dane wejściowe są nadal dostępne.

Innym sposobem spojrzenia na MapReduce jest 5-etapowe obliczenia równoległe i rozproszone:

  1. Przygotuj dane wejściowe Map() – „System MapReduce” wyznacza procesory map, przypisuje klucz wejściowy K1, na którym będzie pracował każdy procesor, i dostarcza temu procesorowi wszystkie dane wejściowe powiązane z tym kluczem.
  2. Uruchom podany przez użytkownika kod Map() – Map() jest uruchamiany dokładnie raz dla każdego klawisza K1 , generując dane wyjściowe zorganizowane według klucza K2 .
  3. „Przetasuj” dane wyjściowe Mapy do procesorów Reduce – system MapReduce wyznacza procesory Reduce, przypisuje klucz K2 , na którym każdy procesor powinien pracować, i dostarcza temu procesorowi wszystkie dane wygenerowane przez Mapy skojarzone z tym kluczem.
  4. Uruchom dostarczony przez użytkownika kod Reduce() — Reduce() jest uruchamiane dokładnie raz dla każdego klucza K2 utworzonego w kroku Map.
  5. Wygeneruj ostateczny wynik — system MapReduce zbiera wszystkie dane wyjściowe Reduce i sortuje je według K2, aby uzyskać ostateczny wynik.

Te pięć kroków można logicznie myśleć jako przebiegających w sekwencji – każdy krok rozpoczyna się dopiero po zakończeniu poprzedniego – chociaż w praktyce można je przeplatać, o ile nie ma to wpływu na końcowy wynik.

W wielu sytuacjach dane wejściowe mogły być już rozłożone ( „sharded” ) na wiele różnych serwerów, w którym to przypadku krok 1 można czasem znacznie uprościć, przypisując serwery Map, które przetwarzałyby lokalnie obecne dane wejściowe. Podobnie krok 3 można czasami przyspieszyć, przypisując procesory Reduce, które są jak najbliżej danych wygenerowanych przez Mapy, które muszą przetworzyć.

Widok logiczny

Funkcje Map i Reduce w MapReduce są zdefiniowane w odniesieniu do danych ustrukturyzowanych w pary (klucz, wartość). Map pobiera jedną parę danych z typem w jednej domenie danych i zwraca listę par w innej domenie:

Map(k1,v1)list(k2,v2)

Funkcja Map jest stosowana równolegle do każdej pary (wpisanej przez k1) w wejściowym zestawie danych. Daje to listę par (zakodowanych przez k2) dla każdego połączenia. Następnie platforma MapReduce zbiera wszystkie pary z tym samym kluczem ( k2) ze wszystkich list i grupuje je razem, tworząc jedną grupę dla każdego klucza.

Funkcja Reduce jest następnie stosowana równolegle do każdej grupy, co z kolei tworzy zbiór wartości w tej samej domenie:

Reduce(k2, list (v2))list((k3, v3))

Każde wywołanie redukcji zwykle generuje jedną parę klucz-wartość lub pustą wartość zwrotu, chociaż jedno wywołanie może zwrócić więcej niż jedną parę klucz-wartość. Zwroty wszystkich połączeń są zbierane jako lista pożądanych wyników.

W ten sposób struktura MapReduce przekształca listę par (klucz, wartość) w inną listę par (klucz, wartość). To zachowanie różni się od typowej mapy programowania funkcjonalnego i kombinacji redukcji, która akceptuje listę dowolnych wartości i zwraca jedną pojedynczą wartość, która łączy wszystkie wartości zwracane przez mapę.

Jest konieczne, ale niewystarczające, aby mieć implementacje mapy i zmniejszyć abstrakcje w celu zaimplementowania MapReduce. Rozproszone implementacje MapReduce wymagają połączenia procesów realizujących fazy Map i Reduce. Może to być rozproszony system plików . Możliwe są inne opcje, takie jak bezpośrednie przesyłanie strumieniowe z programów mapujących do reduktorów lub aby procesory mapowania udostępniały swoje wyniki reduktorom, które je wysyłają.

Przykłady

Kanoniczny przykład MapReduce zlicza pojawienie się każdego słowa w zestawie dokumentów:


function map(String name, String document):
  // name: document name
  // document: document contents
  for each word w in document:
    emit (w, 1)

function reduce(String word, Iterator partialCounts):
  // word: a word
  // partialCounts: a list of aggregated partial counts
  sum = 0
  for each pc in partialCounts:
    sum += pc
  emit (word, sum)

Tutaj każdy dokument jest podzielony na słowa, a każde słowo jest liczone przez funkcję mapy , używając słowa jako klucza wyniku. Struktura łączy wszystkie pary z tym samym kluczem i przekazuje je do tego samego wywołania w celu zmniejszenia . Tak więc funkcja ta musi po prostu zsumować wszystkie swoje wartości wejściowe, aby znaleźć łączne wystąpienia tego słowa.

Jako inny przykład wyobraź sobie, że dla bazy danych liczącej 1,1 miliarda ludzi, chciałoby się obliczyć średnią liczbę kontaktów towarzyskich danej osoby w zależności od wieku. W SQL takie zapytanie może być wyrażone jako:

  SELECT age, AVG(contacts)
    FROM social.person
GROUP BY age
ORDER BY age

Używając MapReduce, wartości klucza K1 mogą być liczbami całkowitymi od 1 do 1100, z których każda reprezentuje partię 1 miliona rekordów, wartość klucza K2 może być wiekiem osoby w latach, a to obliczenie można uzyskać za pomocą następujących funkcji:

function Map is
    input: integer K1 between 1 and 1100, representing a batch of 1 million social.person records
    for each social.person record in the K1 batch do
        let Y be the person's age
        let N be the number of contacts the person has
        produce one output record (Y,(N,1))
    repeat
end function

function Reduce is
    input: age (in years) Y
    for each input record (Y,(N,C)) do
        Accumulate in S the sum of N*C
        Accumulate in Cnew the sum of C
    repeat
    let A be S/Cnew
    produce one output record (Y,(A,Cnew))
end function

System MapReduce połączyłby 1100 procesorów Map i zapewniłby każdemu z nich odpowiedni 1 milion rekordów wejściowych. Krok Map wytworzyłby 1,1 miliarda (Y, (N, 1)) rekordów, z wartościami Y w zakresie, powiedzmy, od 8 do 103. System MapReduce następnie wyrównałby 96 procesorów Reduce, wykonując operację tasowania klucza/wartości par ze względu na fakt, że potrzebujemy średniej na wiek i dostarczamy każdemu z jej milionów odpowiednich rekordów wejściowych. Krok Zmniejszenia spowodowałby znacznie zmniejszony zestaw tylko 96 rekordów wyjściowych (Y,A) , które zostałyby umieszczone w końcowym pliku wynikowym, posortowanym według Y .

Informacje o liczbie w rekordzie są ważne, jeśli przetwarzanie jest redukowane więcej niż jeden raz. Gdybyśmy nie dodali liczby rekordów, wyliczona średnia byłaby błędna, na przykład:

-- map output #1: age, quantity of contacts
10, 9
10, 9
10, 9
-- map output #2: age, quantity of contacts
10, 9
10, 9
-- map output #3: age, quantity of contacts
10, 10

Jeśli zmniejszymy pliki #1 i #2 , otrzymamy nowy plik ze średnią 9 kontaktami dla osoby 10-letniej ((9+9+9+9+9)/5):

-- reduce step #1: age, average of contacts
10, 9

Jeśli zmniejszymy go o plik nr 3 , stracimy liczbę rekordów, które już widzieliśmy, więc otrzymujemy średnio 9,5 kontaktów dla osoby w wieku 10 lat ((9+10)/2) , co jest złe. Prawidłowa odpowiedź to 9,1 66 = 55 / 6 = (9*3+9*2+10*1)/(3+2+1).

Przepływ danych

Architektura szkieletu oprogramowania jest zgodna z zasadą open-closed, w której kod jest efektywnie podzielony na niemodyfikowalne zamrożone punkty i rozszerzalne punkty aktywne . Zamrożony punkt struktury MapReduce jest dużym sortowaniem rozproszonym. Hot spoty, które definiuje aplikacja, to:

  • wejście czytnika
  • Mapa funkcja
  • podział funkcji
  • porównać funkcja
  • Zmniejszenie funkcji
  • pisarz wyjście

Czytnik wejściowy

Do czytnika wejście dzieli sygnał wejściowy na odpowiednie wielkości „pęknięć” (w praktyce zwykle do 64 MB 128 MB) i wyznacza ramowe jednego rozdzielonego każdej Mapa funkcji. Wejście czytnika odczytuje dane z pamięci trwałej (typowo około Rozproszony system plików ) i generuje pary kluczy / wartość.

Typowy przykład odczyta katalog pełen plików tekstowych i zwróci każdy wiersz jako rekord.

Funkcja mapy

Funkcja Map pobiera serię par klucz/wartość, przetwarza każdą z nich i generuje zero lub więcej wyjściowych par klucz/wartość. Typy wejścia i wyjścia mapy mogą być (i często się różnią) od siebie.

Jeśli aplikacja wykonuje zliczanie słów, funkcja map podzieli wiersz na słowa i wypisze parę klucz/wartość dla każdego słowa. Każda para wyjściowa zawierałaby słowo jako klucz i liczbę wystąpień tego słowa w wierszu jako wartość.

Funkcja partycji

Każde dane wyjściowe funkcji Map są przydzielane do określonego reduktora przez funkcję partycji aplikacji na potrzeby fragmentowania . Funkcja partycji otrzymuje klucz i liczbę reduktorów i zwraca indeks żądanego reduktora .

Typowym ustawieniem domyślnym jest mieszanie klucza i używanie wartości mieszania modulo liczba reduktorów . Ważne jest, aby wybrać funkcję partycji, która zapewnia w przybliżeniu równomierną dystrybucję danych na fragment dla celów równoważenia obciążenia , w przeciwnym razie operacja MapReduce może zostać wstrzymana w oczekiwaniu na zakończenie powolnych reduktorów (tj. reduktorom przypisano większe udziały nie- dane podzielone na partycje).

Między mapą a etapami redukcji dane są tasowane (sortowane równolegle / wymieniane między węzłami) w celu przeniesienia danych z węzła mapy, który je utworzył, do fragmentu, w którym zostaną zredukowane. Tasowanie może czasami trwać dłużej niż czas obliczeń, w zależności od przepustowości sieci, szybkości procesora, generowanych danych i czasu zajmowanego przez mapę i zmniejszania obliczeń.

Funkcja porównawcza

Dane wejściowe dla każdej redukcji są pobierane z maszyny, na której uruchomiona była mapa, i sortowane za pomocą funkcji porównania aplikacji .

Zmniejsz funkcję

Struktura wywołuje funkcję Reduce aplikacji raz dla każdego unikalnego klucza w posortowanej kolejności. Redukcja może iterację wartości, które są związane z kluczem i wytwarzają zero lub więcej wyjść.

W przykładzie liczenia słów funkcja Reduce pobiera wartości wejściowe, sumuje je i generuje jedno wyjście słowa oraz sumę końcową.

Zapis wyjścia

Output Writer zapisuje wyjście Zmniejsz do magazynowania stabilny.

Rozważania dotyczące wydajności

Nie ma gwarancji, że programy MapReduce będą szybkie. Główną zaletą tego modelu programowania jest wykorzystanie zoptymalizowanej operacji odtwarzania losowego platformy i konieczność napisania tylko części programu Map i Reduce . W praktyce autor programu MapReduce musi jednak wziąć pod uwagę krok przetasowania; w szczególności funkcja partycji i ilość danych zapisanych przez funkcję Map może mieć duży wpływ na wydajność i skalowalność. Dodatkowe moduły, takie jak funkcja Combiner, mogą pomóc w zmniejszeniu ilości danych zapisywanych na dysku i przesyłanych przez sieć. Aplikacje MapReduce mogą w określonych okolicznościach osiągnąć podliniowe przyspieszenie.

Projektując algorytm MapReduce, autor musi wybrać dobry kompromis między kosztami obliczeń a kosztami komunikacji. Koszt komunikacji często dominuje nad kosztem obliczeń, a wiele implementacji MapReduce jest zaprojektowanych do zapisywania całej komunikacji w rozproszonej pamięci masowej w celu odzyskiwania po awarii.

Przy dostrajaniu wydajności MapReduce należy wziąć pod uwagę złożoność mapowania, tasowania, sortowania (grupowania według klucza) i redukcji. Ilość danych generowanych przez programy mapujące jest kluczowym parametrem, który przenosi większość kosztów obliczeń między mapowaniem a redukcją. Redukcja obejmuje sortowanie (grupowanie kluczy), które ma nieliniową złożoność. W związku z tym małe rozmiary partycji skracają czas sortowania, ale istnieje kompromis, ponieważ posiadanie dużej liczby reduktorów może być niepraktyczne. Wpływ wielkości jednostki podzielonej jest marginalny (chyba, że ​​wybrano szczególnie źle, powiedzmy <1MB). Zyski z niektórych maperów odczytujących obciążenie z dysków lokalnych są średnio niewielkie.

W przypadku procesów, które kończą się szybko i gdy dane mieszczą się w pamięci głównej pojedynczego komputera lub małego klastra, korzystanie z platformy MapReduce zwykle nie jest skuteczne. Ponieważ te frameworki są zaprojektowane do odzyskiwania po utracie całych węzłów podczas obliczeń, wyniki pośrednie zapisują w rozproszonej pamięci masowej. Odzyskiwanie po awarii jest kosztowne i opłaca się tylko wtedy, gdy obliczenia obejmują wiele komputerów i długi czas działania obliczeń. Zadanie, które kończy się w kilka sekund, można po prostu ponownie uruchomić w przypadku błędu, a prawdopodobieństwo awarii co najmniej jednej maszyny rośnie szybko wraz z rozmiarem klastra. W przypadku takich problemów implementacje utrzymujące wszystkie dane w pamięci i po prostu ponownie uruchamiające obliczenia w przypadku awarii węzła lub — gdy dane są wystarczająco małe — rozwiązania nierozproszone będą często szybsze niż system MapReduce.

Dystrybucja i niezawodność

MapReduce osiąga niezawodność, rozdzielając szereg operacji na zestawie danych do każdego węzła w sieci. Oczekuje się, że każdy węzeł będzie okresowo raportował z ukończoną pracą i aktualizacjami statusu. Jeśli węzeł zamilknie na dłużej niż ten interwał, węzeł główny (podobnie jak serwer główny w systemie plików Google ) rejestruje go jako martwy i wysyła przypisaną pracę węzła do innych węzłów. Poszczególne operacje używać atomowych operacji nazywania plików wyjścia jak sprawdzić, czy nie są sprzeczne wątki działające równolegle. W przypadku zmiany nazwy plików możliwe jest również skopiowanie ich na inną nazwę oprócz nazwy zadania (zezwalając na efekty uboczne ).

Operacje redukcji działają w bardzo podobny sposób. Z powodu ich gorszych właściwości w odniesieniu do operacji równoległych, węzeł nadrzędny próbuje zaplanować operacje redukcji na tym samym węźle lub w tej samej szafie, co węzeł przechowujący dane, na których są operowane. Ta właściwość jest pożądana, ponieważ pozwala zachować przepustowość w sieci szkieletowej centrum danych.

Implementacje niekoniecznie są wysoce niezawodne. Na przykład, w starszych wersjach Hadoop NameNode był pojedynczy punkt awarii dla rozproszonego systemu plików. Nowsze wersje Hadoop mają wysoką dostępność z aktywnym/pasywnym przełączaniem awaryjnym dla „NameNode”.

Zastosowania

MapReduce jest przydatny w szerokim zakresie zastosowań, w tym w rozproszonym wyszukiwaniu opartym na wzorcach, rozproszonym sortowaniu, odwracaniu wykresów łączy internetowych, dekompozycji na wartości osobliwe, statystykach dzienników dostępu do stron internetowych, konstrukcji indeksów odwróconych , grupowaniu dokumentów , uczeniu maszynowym i statystycznym tłumaczeniu maszynowym . Co więcej, model MapReduce został dostosowany do kilku środowisk obliczeniowych, takich jak systemy wielordzeniowe i wielordzeniowe, sieci komputerów stacjonarnych, wieloklastrowe środowiska komputerowe ochotników, dynamiczne środowiska chmurowe, środowiska mobilne i środowiska obliczeniowe o wysokiej wydajności.

W Google narzędzie MapReduce zostało wykorzystane do całkowitego zregenerowania indeksu Google dla sieci WWW . Zastąpił on stare programy ad hoc , które aktualizowały indeks i przeprowadzały różne analizy. Rozwój w Google przeszedł od tego czasu do technologii, takich jak Percolator, FlumeJava i MillWheel, które oferują operacje przesyłania strumieniowego i aktualizacji zamiast przetwarzania wsadowego, aby umożliwić integrację wyników wyszukiwania „na żywo” bez przebudowy całego indeksu.

Stabilne dane wejściowe i wyjściowe MapReduce są zwykle przechowywane w rozproszonym systemie plików . Dane przejściowe są zwykle przechowywane na dysku lokalnym i pobierane zdalnie przez reduktory.

Krytyka

Brak nowości

David DeWitt i Michael Stonebraker , informatycy specjalizujący się w równoległych bazach danych i architekturach typu „shared-nic” , krytycznie oceniali zakres problemów, do których można wykorzystać MapReduce. Nazwali jego interfejs zbyt niskim poziomem i zakwestionowali, czy naprawdę reprezentuje zmianę paradygmatu , jak twierdzą jego zwolennicy. Zakwestionowali twierdzenia zwolenników MapReduce dotyczące nowości, przytaczając Teradata jako przykład stanu techniki , który istnieje od ponad dwóch dekad. Porównali także programistów MapReduce z programistami CODASYL , zauważając, że obaj „piszą w języku niskiego poziomu, dokonując manipulacji rekordami niskiego poziomu”. Zastosowanie mapreduce za plików wejściowych i brak schematu zapobiega wspierać poprawę skuteczności włączona wspólnego systemu bazy danych cech, takich jak B-drzew i partycjonowanie hash , choć projekty takie jak Pig (lub PigLatin) , Sawzall , Apache Hive , HBase i Bigtable są adresowania niektórych tych problemów.

Greg Jorgensen napisał artykuł odrzucający te poglądy. Jorgensen twierdzi, że cała analiza DeWitt i Stonebrakera jest bezpodstawna, ponieważ MapReduce nigdy nie został zaprojektowany ani przeznaczony do wykorzystania jako baza danych.

DeWitt i Stonebraker opublikowali następnie w 2009 r. szczegółowe badanie porównawcze porównujące wydajność podejść MapReduce i RDBMS firmy Hadoop w odniesieniu do kilku konkretnych problemów. Doszli do wniosku, że relacyjne bazy danych oferują realne korzyści w przypadku wielu rodzajów wykorzystania danych, zwłaszcza w przypadku złożonego przetwarzania lub gdy dane są wykorzystywane w całym przedsiębiorstwie, ale MapReduce może być łatwiejszy do zastosowania przez użytkowników do prostych lub jednorazowych zadań przetwarzania.

Paradygmat programowania MapReduce został również opisany w tezie Danny'ego Hillisa z 1985 r. i był wówczas szeroko stosowany do programowania maszyny połączeń , która miała specjalne wsparcie sprzętowe do przyspieszania zarówno mapowania, jak i redukcji.

W 2010 roku Google otrzymało patent na MapReduce. Patent, zgłoszony w 2004 r., może obejmować korzystanie z MapReduce przez oprogramowanie typu open source, takie jak Hadoop , CouchDB i inne. W Ars Technica redaktor uznał rolę Google w popularyzacji koncepcji MapReduce, ale zakwestionował ważność patentu, czy nowość. W 2013 r. w ramach zobowiązania „Open Patent Non-Assertion (OPN) Pledge” Google zobowiązał się do korzystania z patentu wyłącznie w sposób defensywny. Oczekuje się, że patent wygaśnie 23 grudnia 2026 r.

Ograniczone ramy programowania

Zadania MapReduce muszą być napisane jako programy acyklicznego przepływu danych, tj. bezstanowy program odwzorowujący, po którym następuje bezstanowy reduktor, które są wykonywane przez harmonogram zadań wsadowych. Ten paradygmat utrudnia powtarzanie zapytań o zestawy danych i nakłada ograniczenia, które są odczuwalne w takich dziedzinach, jak uczenie maszynowe , gdzie normą są algorytmy iteracyjne, które wielokrotnie odwiedzają pojedynczy zestaw roboczy .

Zobacz też

Implementacje MapReduce

Bibliografia