Nie mogłem wymyślić żadnych dobrych przykładów oprócz zadania „jak liczyć słowa w długim tekście za pomocą MapReduce”. Odkryłem, że nie był to najlepszy przykład, aby dać innym wrażenie, jak potężne może być to narzędzie.

Nie szukam fragmentów kodu, tak naprawdę tylko „tekstowych” przykładów.

Redukcja map to ramy opracowane w celu wydajnego przetwarzania ogromnych ilości danych. Na przykład, jeśli mamy 1 milion rekordów w zbiorze danych i jest on przechowywany w reprezentacji relacyjnej - wyprowadzenie wartości i wykonanie na nich wszelkiego rodzaju transformacji jest bardzo drogie.

Na przykład w SQL, biorąc pod uwagę datę urodzenia, aby dowiedzieć się, ile osób jest w wieku> 30 lat na milion rekordów, zajęłoby to trochę czasu, a to wzrosłoby tylko w kolejności magnitetycznej, gdy złożoność zapytania wzrosła. Map Reduce zapewnia implementację opartą na klastrze, w której dane przetwarzane są w sposób rozproszony

Oto artykuł w Wikipedii wyjaśniający, o co w tym map-reducewszystkim chodzi

Innym dobrym przykładem jest znalezienie przyjaciół poprzez redukcję mapy. Może to być dobry przykład zrozumienia tej koncepcji oraz dobrze wykorzystany przypadek użycia.

Osobiście uznałem ten link za bardzo przydatny do zrozumienia tej koncepcji

Kopiowanie objaśnienia zamieszczonego na blogu (w przypadku linku przestarzałego)

Znajdowanie przyjaciół

MapReduce to platforma opracowana pierwotnie w Google, która umożliwia łatwe przetwarzanie rozproszone na dużą skalę w wielu domenach. Apache Hadoop to implementacja typu open source.

Omówię szczegóły, ale sprowadza się to do zdefiniowania dwóch funkcji: funkcji mapy i funkcji redukcji. Funkcja mapy przyjmuje klucz wartości i wyników: pary wartości. Na przykład, jeśli zdefiniujemy funkcję mapy, która pobiera ciąg znaków i podaje długość słowa jako klucz, a samo słowo jako wartość, wówczas mapa (steve) zwróci 5: steve, a mapa (sawanna) zwróci 8: sawanna . Być może zauważyłeś, że funkcja mapy jest bezstanowa i wymaga jedynie wartości wejściowej do obliczenia jej wartości wyjściowej. To pozwala nam równolegle uruchamiać funkcję mapy względem wartości i zapewnia ogromną przewagę. Zanim przejdziemy do funkcji redukcji, framework mapreduce grupuje wszystkie wartości razem według klucza, więc jeśli funkcje mapy generują następujący klucz: pary wartości:

3 : the
3 : and
3 : you
4 : then
4 : what
4 : when
5 : steve
5 : where
8 : savannah
8 : research

Są one pogrupowane jako:

3 : [the, and, you]
4 : [then, what, when]
5 : [steve, where]
8 : [savannah, research]

Każdy z tych wierszy byłby następnie przekazywany jako argument funkcji zmniejszającej, która akceptuje klucz i listę wartości. W tym przypadku możemy próbować dowiedzieć się, ile istnieje słów o określonej długości, więc nasza funkcja zmniejszania policzy tylko liczbę elementów na liście i wyśle ​​klucz o rozmiarze listy, na przykład:

3 : 3
4 : 3
5 : 2
8 : 2

Redukcji można również dokonać równolegle, co ponownie zapewnia ogromną przewagę. Następnie możemy spojrzeć na te końcowe wyniki i zobaczyć, że w naszym korpusie były tylko dwa słowa o długości 5 itd.

Najczęstszym przykładem mapreduce jest zliczanie liczby wystąpień słów w korpusie. Załóżmy, że masz kopię Internetu (miałem szczęście, że mogłem pracować w takiej sytuacji) i chciałeś mieć listę każdego słowa w Internecie, a także liczbę razy.

Sposób, w jaki do tego podejdziesz, to tokenizowanie posiadanych dokumentów (rozbicie ich na słowa) i przekazywanie każdego słowa twórcy map. Następnie program mapujący wypluł słowo z powrotem wraz z wartością 1. Faza grupowania zajmie wszystkie klucze (w tym przypadku słowa) i utworzy listę 1. Faza redukcji pobiera następnie klucz (słowo) i listę (listę 1 za każdym razem, gdy klucz pojawia się w Internecie) i sumuje listę. Reduktor następnie wypisuje słowo wraz z jego liczbą. Kiedy wszystko zostanie powiedziane i zrobione, będziesz mieć listę każdego słowa w Internecie, wraz z tym, ile razy się pojawiło.

Łatwe, prawda? Jeśli kiedykolwiek czytałeś o mapreduce, powyższy scenariusz nie jest niczym nowym ... to „Hello, World” mapreduce. Oto przypadek użycia w świecie rzeczywistym (Facebook może, ale nie musi, wykonać następujące czynności, to tylko przykład):

Facebook ma listę przyjaciół (pamiętaj, że przyjaciele są dwukierunkową rzeczą na Facebooku. Jeśli jestem twoim przyjacielem, jesteś mój). Mają też dużo miejsca na dysku i codziennie obsługują setki milionów żądań. Zdecydowali się na wstępne obliczenia, kiedy mogą skrócić czas przetwarzania żądań. Jednym z typowych żądań przetwarzania jest funkcja „Ty i Joe mają 230 wspólnych znajomych”. Gdy odwiedzasz czyjś profil, widzisz listę znajomych, których masz wspólnego. Ta lista nie zmienia się często, więc niepotrzebne byłoby jej ponowne obliczanie za każdym razem, gdy odwiedzasz profil (na pewno możesz użyć przyzwoitej strategii buforowania, ale wtedy nie byłbym w stanie kontynuować pisania o zmniejszeniu map dla tego problemu). Użyjemy mapreduce, abyśmy mogli obliczyć wszystkich ” wspólnych znajomych raz dziennie i przechowuj te wyniki. Później jest to tylko szybki przegląd. Mamy dużo dysku, jest tani.

Załóżmy, że znajomi są zapisywani jako Osoba -> [Lista znajomych], nasza lista znajomych to:

A -> B C D
B -> A C D E
C -> A B D E
D -> A B C E
E -> B C D

Każda linia będzie argumentem dla twórcy map. Dla każdego znajomego na liście znajomych mapujący wyświetli parę klucz-wartość. Kluczem będzie przyjaciel wraz z osobą. Wartością będzie lista przyjaciół. Klucz zostanie posortowany tak, aby przyjaciele byli w porządku, co spowoduje, że wszystkie pary znajomych przejdą do tego samego reduktora. Trudno to wytłumaczyć tekstem, więc zróbmy to i sprawdźmy, czy widać wzór. Po zakończeniu działania wszystkich twórców map pojawi się następująca lista:

For map(A -> B C D) :

(A B) -> B C D
(A C) -> B C D
(A D) -> B C D

For map(B -> A C D E) : (Note that A comes before B in the key)

(A B) -> A C D E
(B C) -> A C D E
(B D) -> A C D E
(B E) -> A C D E
For map(C -> A B D E) :

(A C) -> A B D E
(B C) -> A B D E
(C D) -> A B D E
(C E) -> A B D E
For map(D -> A B C E) :

(A D) -> A B C E
(B D) -> A B C E
(C D) -> A B C E
(D E) -> A B C E
And finally for map(E -> B C D):

(B E) -> B C D
(C E) -> B C D
(D E) -> B C D
Before we send these key-value pairs to the reducers, we group them by their keys and get:

(A B) -> (A C D E) (B C D)
(A C) -> (A B D E) (B C D)
(A D) -> (A B C E) (B C D)
(B C) -> (A B D E) (A C D E)
(B D) -> (A B C E) (A C D E)
(B E) -> (A C D E) (B C D)
(C D) -> (A B C E) (A B D E)
(C E) -> (A B D E) (B C D)
(D E) -> (A B C E) (B C D)

Każda linia zostanie przekazana jako argument do reduktora. Funkcja zmniejszania po prostu przecina listy wartości i wyprowadza ten sam klucz z wynikiem przecięcia. Na przykład, zmniejsz ((AB) -> (ACDE) (BCD)) wyświetli (AB): (CD) i oznacza, że ​​przyjaciele A i B mają C i D jako wspólnych znajomych.

Wynik po redukcji wynosi:

(A B) -> (C D)
(A C) -> (B D)
(A D) -> (B C)
(B C) -> (A D E)
(B D) -> (A C E)
(B E) -> (C D)
(C D) -> (A B E)
(C E) -> (B D)
(D E) -> (B C)

Teraz, gdy profil wizyt D B, możemy szybko sprawdzić (B D)i zobaczyć, że mają trzy wspólnych przyjaciół, (A C E).

Jeden z najlepszych przykładów implementacji MapReduce w stylu Hadoop .

Należy jednak pamiętać, że ograniczają się one do implementacji idei MapReduce opartej na kluczowej wartości (więc mają one ograniczone zastosowanie).

Jeden zestaw znanych operacji, które można wykonać w MapReduce, to zestaw normalnych operacji SQL: WYBIERZ, WYBIERZ GDZIE, GRUPUJ WG itd.

Innym dobrym przykładem jest mnożenie macierzy, w którym przekazujesz jeden wiersz M i cały wektor x i obliczasz jeden element M * x.

Od czasu do czasu prezentuję ludziom koncepcje MR. Uważam, że zadania przetwarzania są znane ludziom, a następnie mapuję je na paradygmat MR.

Zwykle biorę dwie rzeczy:

1. Grupuj według / agregacje. Tutaj przewaga etapu tasowania jest oczywista. Wyjaśnienie, że tasowanie jest również sortowaniem rozproszonym + wyjaśnienie algorytmu sortowania rozproszonego również pomaga.

2. Połącz dwa stoliki. Osoby pracujące z DB znają tę koncepcję i jej problem ze skalowalnością. Pokaż, jak można to zrobić w MR.