MapReduce to architektoniczny wzorzec z rozwojem oprogramowania , wymyślone przez Google , w której wykonane są z obliczeń równoległych , a często dystrybuowane do potencjalnie bardzo dużych danych, zwykle większym rozmiarze do 1 terabajta .
Terminy „ mapa ” i „ redukcja ” oraz podstawowe koncepcje są zapożyczone z funkcjonalnych języków programowania używanych do ich budowy (mapa i redukcja programowania funkcyjnego i języków programowania tablicowego).
MapReduce umożliwia manipulowanie dużymi ilościami danych poprzez dystrybucję ich w klastrze maszyn do przetwarzania. Model ten jest bardzo popularny wśród firm posiadających duże centra danych, takich jak Amazon.com czy Facebook . Zaczyna być również używany w ramach przetwarzania w chmurze . Pojawiło się wiele frameworków do implementacji MapReduce. Najbardziej znanym jest Hadoop, który został opracowany przez Apache Software Foundation . Jednak ten framework ma wady, które znacznie zmniejszają jego wydajność, szczególnie w środowiskach heterogenicznych. Z ram dla poprawy wydajności Hadoop lub ogólną wydajność MapReduce, zarówno pod względem szybkości przetwarzania niż zużycie energii, zaczynają się pojawiać.
MapReduce to model programowania spopularyzowany przez Google . Służy głównie do manipulacji i przetwarzania dużej ilości danych w klastrze węzłów.
MapReduce składa się z dwóch funkcji map() i Reduce().
Klaster MapReduce używa architektury typu Master-Slave, w której węzeł główny kieruje wszystkimi węzłami podrzędnymi.
MapReduce ma kilka funkcji:
Gdy węzeł zakończy zadanie, zostanie mu przydzielony nowy blok danych. Dzięki temu szybki węzeł wykona o wiele więcej obliczeń niż wolniejszy. Liczba zadań Map nie zależy od liczby węzłów, ale od liczby bloków danych wejściowych. Do każdego bloku przypisane jest jedno zadanie Mapy. Ponadto nie wszystkie zadania Map muszą być wykonywane w tym samym czasie równolegle. Zadania Redukcja działają zgodnie z tą samą logiką. Na przykład, jeśli dane wejściowe są podzielone na 400 bloków i w klastrze jest 40 węzłów, liczba zadań Map wyniesie 400. Wtedy do wykonania mapowania danych będzie potrzebnych 10 fal Map.
MapReduce pojawił się w 2004 roku. Technologia jest wciąż młoda. Ma kilka słabych punktów:
MapReduce czerpie swoją wiarygodność z rozkładu, w każdym węźle sieci, operacji, które mają być zastosowane do zbioru danych ; deweloper oczekuje, że każdy węzeł będzie okresowo zwracał ukończoną pracę i zmiany statusu . Jeśli węzeł nic nie zwraca w tym przedziale, węzeł główny (o nazwie NameNode w Hadoop) (podobnie jak serwer główny systemu plików Google ) uznaje węzeł za martwy i wysyła dane przypisane do tego węzła do innych węzłów . Poszczególne operacje używają operacji niepodzielnych dla nazw plików wyjściowych jako podwójnego sprawdzenia, aby upewnić się, że nie ma konfliktu równoległego z uruchomionym wątkiem ; przy zmianie nazwy plików możliwe jest również skopiowanie ich pod inną nazwą oprócz nazwy zadania (dopuszcza się skutki uboczne ) .
Operacje zmniejszania działają w bardzo podobny sposób, ale ze względu na ich gorsze właściwości dotyczące operacji współbieżnych , węzeł główny próbuje zaplanować operacje zmniejszania na tym samym węźle lub jak najbliżej węzła, który je przechowuje. obrobiony. Ta właściwość jest preferowana przez Google, ponieważ nie wymaga dodatkowej przepustowości. Jest to zaletą, ponieważ przepustowość jest często ograniczona w wewnętrznych sieciach firmowych .
Według badania przeprowadzonego przez National University of Singapore w 2010 roku na wydajność MapReduce wpływa pięć czynników.
Model programowania MapReduce został zaprojektowany tak, aby był niezależny od systemu przechowywania danych. Odczytuje pary <klucz, wartość> za pomocą czytnika. Czytnik pobiera każdy rekord z systemu pamięci masowej, a następnie umieszcza je w parze <klucz, wartość>, aby można je było przetwarzać podczas MapReduce. Chociaż MapReduce nie jest zależny od konkretnego systemu pamięci masowej, ma trudności, gdy system pamięci masowej jest bazą danych. Komercyjne systemy równoległych baz danych wykorzystują silnik do wykonywania zapytań i silnik pamięci masowej. Aby uruchomić zapytanie, aparat zapytań odczytuje dane bezpośrednio z aparatu magazynu. MapReduce musi najpierw odczytać wartość, a następnie zapisać ją w parze za pomocą czytnika, dlatego MapReduce działa gorzej w bazach danych. Porównując MapReduce i równoległe systemy baz danych, wyróżniono trzy czynniki, które mogą wpływać na wydajność MapReduce:
MapReduce używa systemu planowania do przydzielania bloków danych do dostępnych węzłów w klastrze. Ten system generuje koszty wykonania i może spowolnić wykonanie MapReduce. Na wydajność MapReduce mogą mieć wpływ dwa czynniki:
Czytnik może wykorzystać dwa tryby odczytu do odczytu danych przechowywanych w systemie pamięci masowej.
Według testów przeprowadzonych w tym badaniu różnica w wydajności między tymi dwoma trybami jest niewielka (około 10%).
Parsowanie danychGdy dysk pobiera dane z systemu pamięci masowej, musi je przekonwertować na parę <klucz, wartość>, aby kontynuować wykonywanie (ten proces nazywa się analizą danych). Analiza polega na dekodowaniu danych z ich natywnego formatu przechowywania w celu przekształcenia ich do formatu, który może być używany przez język programowania. Istnieją dwa rodzaje dekodowania, dekodowanie niezmienne i dekodowanie mutowalne. Niezmienne dekodowanie to proces przekształcania danych w niezmienne obiekty. Obiekty niezmienne w programowaniu obiektowym to obiekty, których stan nie może zostać zmieniony po ich utworzeniu, w przeciwieństwie do obiektów zmiennych.
Używając dekodowania niezmiennego, każda z danych zostanie umieszczona w obiekcie niezmiennym. Dlatego jeśli zdekodujemy 4 miliony fragmentów danych, powstanie 4 miliony niezmiennych obiektów. Domyślnie MapReduce Google używa niezmiennych obiektów.
Inną metodą jest użycie dekodowania mutowalnego. Dzięki temu dekodowaniu obiekt mutowalny jest ponownie używany do dekodowania wszystkich danych. Tym samym liczba danych nie jest już istotna, ponieważ zostanie utworzony tylko jeden obiekt.
Według badań słaba wydajność analizowania wynika z niezmiennego dekodowania. Dekodowanie niezmienne jest wolniejsze niż dekodowanie mutowalne, ponieważ podczas procesu dekodowania wytwarza dużą liczbę niezmiennych obiektów. Tworzenie wszystkich tych niezmiennych obiektów zwiększa obciążenie procesorów.
IndeksacjaPonieważ MapReduce jest niezależny od systemu pamięci masowej, nie może uwzględniać wszystkich danych wejściowych, aby mieć dostępny indeks. Wygląda na to, że MapReduce nie może korzystać z indeksów. Stwierdzono jednak, że trzy metody wykorzystania indeksów przyspieszają proces przetwarzania danych.
Aby skrócić czas planowania, można zmodyfikować rozmiar bloków danych, które mają być dystrybuowane do węzłów klastra. Jeśli zwiększymy rozmiar bloków danych, planowanie będzie szybsze, ponieważ będzie wymagało mniej zadań mapowych. Jeśli jednak rozmiar bloków zostanie zbytnio zwiększony, ryzyko awarii jest większe.
MapReduce może być używany do różnych aplikacji, w tym rozproszonego grep, rozproszonego sortowania, odwracania wykresów linków internetowych, wektorów terminów według hosta, statystyk dostępu do stron internetowych, konstrukcji odwróconych indeksów, automatycznej klasyfikacji dokumentów , uczenia maszynowego , statystycznego tłumaczenia maszynowego (rozproszony grep, rozproszony los, odwrócenie wykresu łączy internetowych, wektor terminów na hosta, statystyki dziennika dostępu do sieci, budowanie indeksu odwróconego, grupowanie papieru , uczenie maszynowe , statystyczne tłumaczenie maszynowe ). Co ważniejsze, kiedy ukończono MapReduce, wykorzystano go do całkowitego przebudowania indeksów internetowych Google i zastąpił stare programy ad hoc używane do aktualizacji tych indeksów i do różnych indeksów ich przeszukiwania.
MapReduce generuje dużą liczbę pośredników i pliki tymczasowe, które są zarządzane i ogólnie dostępnych za pośrednictwem tej systemie plików dla lepszej wydajności.
Hadoop to implementacja open source MapReduce w Javie dystrybuowana przez Fundację Apache . Został on zaproponowany przez głównych graczy internetowych, takich jak Yahoo! i Facebooka . Dwie główne funkcje platformy Hadoop to platforma MapReduce i rozproszony system plików Hadoop (inspirowany systemem plików Google ). W HDFS może rozpowszechniać dane i skutecznych metod leczenia na tych danych z MapReduce dystrybucją operacji na wielu węzłach w celu parallelize.
W Hadoop węzeł główny nazywa się JobTracker, a węzły podrzędne nazywają się TaskTracker. Każdy węzeł podrzędny będzie zawierał bloki danych poprzez ich replikację. Węzeł główny zna lokalizacje różnych replik. Wtórny węzeł główny jest używany do tworzenia regularnych kopii zapasowych węzła głównego, aby można było go ponownie wykorzystać w przypadku wystąpienia problemu.
Hadoop wykonuje zadanie typu MapReduce, najpierw dzieląc dane wejściowe na blok danych o tym samym rozmiarze. Następnie każdy blok jest planowany do wykonania przez TaskTracker. Proces przydzielania zadań realizowany jest jako protokół typu „heartbeat”. Oznacza to, że TaskTracker powiadamia JobTrackera, że jego zadanie zostało zakończone, aby ten przypisał mu nowe zadanie do wykonania. Gdy funkcja mapy zostanie zakończona, system przegrupuje wszystkie pary pośrednie i zainicjuje serię redukcji, aby uzyskać ostateczny wynik.
Wdrożenie Hadoop z 2010 r. zakłada, że przetwarzanie odbywa się na klastrze jednorodnych maszyn (tj. wszystkie mają te same cechy sprzętowe). Nie uwzględnia również lokalizacji danych, uważa, że wszystkie dane są lokalne. Niestety te dwa czynniki mogą znacząco wpłynąć na wydajność MapReduce.
W jednorodnym środowisku wszystkie węzły mają takie samo obciążenie pracą, co oznacza, że żadne dane nie powinny być przesyłane z jednego węzła do drugiego. W środowisku heterogenicznym węzeł o wysokiej wydajności może zakończyć przetwarzanie lokalne szybciej niż węzeł o niższej wydajności. Gdy szybki węzeł zakończy przetwarzanie, będzie musiał pobrać nieprzetworzone dane z jednego lub większej liczby wolniejszych węzłów. Transfer danych z wolnego węzła do szybkiego węzła wiąże się z wysokimi kosztami.
W chmurze PrezentacjaMapReduce pojawił się w 2004 roku jako ważny model programowania dla aplikacji wykorzystujących ogromne ilości danych dzięki wydajnemu rozmieszczeniu pracy na różnych węzłach obliczeniowych. W szczególności zaczyna być stosowany w Cloud Computing, ponieważ liczba przechowywanych i obsługiwanych danych stale rośnie. Dlatego konieczne jest posiadanie sposobu na usprawnienie przetwarzania danych w Chmurze.
Pod względem zasobów chmurę można scharakteryzować w trzech punktach: duża pojemność przechowywania danych, moc obliczeniowa na żądanie, niewielkie wykorzystanie przepustowości. Rozmiar danych przechowywanych w Chmurze stale rośnie, w szczególności plików graficznych, wideo, audio czy instrumentów naukowych do przeprowadzania symulacji. Przetwarzanie tych danych stało się jednym z głównych wyzwań Cloud Computing.
Chmura wykorzystuje głównie maszyny wirtualne (VM) do uruchamiania aplikacji. Maszyny wirtualne umożliwiają pełne wykorzystanie zasobów systemowych, poprawiają niezawodność systemu poprzez tworzenie kopii zapasowych stanu systemu przy użyciu funkcji zawartych w maszynach wirtualnych oraz zmniejszają zużycie energii poprzez zmniejszenie liczby węzłów wykorzystywanych do wykonywania zadań.
Połączenie Cloud Computing, które wykorzystuje maszyny wirtualne i MapReduce, może być interesujące. Głównie dlatego, że technologie wirtualizacji osiągnęły pełnoletność. Wykorzystano je już w sieciach obliczeniowych, aby w pełni wykorzystać zasoby węzłów obliczeniowych i aplikacji HPC (High-Performance computing). Ponadto, z jednej strony rośnie popularność chmury (która wykorzystuje maszyny wirtualne), z drugiej strony MapReduce zaczyna być szeroko stosowany dzięki wielu jego mocnym stronom, szczególnie ze względu na skalowalność i tolerancję na błędy. Dlatego połączenie tych dwóch technologii stworzyłoby wydajny sposób przetwarzania dużych ilości danych w chmurze. Do tego dochodzi fakt, że MapReduce wykorzystuje zadania spekulacyjne. Są to zadania, które można ponownie uruchomić na innym węźle, jeśli zostaną wykryte jako zbyt wolne. Problem polega na tym, że ponowne uruchomienie zadania może zmniejszyć wydajność przez wydłużenie czasu wykonania, ponieważ zadanie musi wznowić całe przetwarzanie. Dzięki nowym technologiom maszyn wirtualnych, takim jak tworzenie kopii zapasowych i migracja, poprawiono wydajność i niezawodność MapReduce. Funkcjonalność backupu polega na zapisywaniu stanu systemu, aby mógł powrócić do tego stanu w przypadku wystąpienia poważnego błędu uniemożliwiającego jego prawidłowe działanie. Funkcjonalność migracji polega na dystrybucji maszyny wirtualnej lub aplikacji na kilku węzłach fizycznych bez zatrzymywania aplikacji.
WystępAby przetestować MapReduce, różne pomiary są wykonywane na platformie Hadoop. Testy wydajności są wykonywane na HDFS, ponieważ odgrywa on dużą rolę w wykonywaniu MapReduce. Rzeczywiście, to w szczególności HDFS zajmuje się dystrybucją zadań na różne węzły, decyduje również o wielkości danych, które mają być przetwarzane przez węzeł. Przeprowadzone zostaną dalsze testy wykonalności wykorzystania maszyn wirtualnych w celu poprawy wydajności MapReduce poprzez zwiększenie wykorzystania zasobów (poprzez zwiększenie liczby maszyn wirtualnych na węzeł). Wydajność mierzy się za pomocą dwóch znanych wzorców, wzorca sortowania słów i wzorca liczenia.
wzorzec sortowania Ten test porównawczy wykorzystuje strukturę map/reduce do sortowania danych wejściowych. Test porównawczy „Liczenia słów” ten test porównawczy zlicza liczbę wystąpień każdego słowa w pliku i zapisuje wynik na dysku lokalnym. HDFSOcena wydajności HDFS jest wykonywana w klastrze fizycznym (PH-HDFS) oraz w klastrze wirtualnym (VM-HDFS podczas zapisu i odczytu danych w celu wykazania różnic wydajności między klastrem fizycznym a klastrem wirtualnym.
W tej ocenie wykonywanych jest kilka transferów danych o różnych rozmiarach. PH-HDFS osiąga lepsze czasy, luki powiększają się wraz ze wzrostem rozmiaru danych.
W tej ocenie jedno lub więcej żądań jest uruchamianych jednocześnie i mierzony jest czas potrzebny do zakończenia przesyłania danych. Wydajność PH-HDFS jest lepsza niż VM-HDFS.
Wykonalność maszyn wirtualnychWraz z pojawieniem się procesorów wielordzeniowych ważne jest, aby używać procesorów wielordzeniowych w klastrze do instalowania wielu maszyn wirtualnych na procesor, aby w pełni wykorzystać możliwości węzła. Na potrzeby testów utworzono kilka klastrów, aby ocenić wpływ wzrostu liczby maszyn wirtualnych na węzeł:
Jak pokazano na tym rysunku, benchmark „liczba słów” z klastrem Ph jest szybszy niż klaster V. Gdy dane mają rozmiar 1 Gb, różnica jest niewielka. Ale gdy dane są znacznie większe (tutaj 8 Gb), pojawia się znacząca różnica. Jest to spowodowane wzrostem zadań spekulacyjnych, co powoduje nieefektywne wykorzystanie zasobów. Z drugiej strony klastry V2 i V4 są znacznie wydajniejsze niż klaster Ph, ponieważ jest o wiele więcej obliczeń na cykl.
Po uruchomieniu testu porównawczego sortowania czas wykonywania dla tej samej dystrybucji danych zwiększa się wraz ze wzrostem liczby maszyn wirtualnych wdrożonych w węźle fizycznym. Ponadto luki powiększają się wraz ze wzrostem rozmiaru rozproszonych danych. Jest to spowodowane 3 przyczynami: słabą wydajnością HDFS na maszynach wirtualnych podczas operacji odczytu/zapisu (jak widać wcześniej), wzrostem liczby zadań spekulacyjnych (Rysunek 6) oraz dużą ilością danych przesyłanych podczas etapów pośrednich.
Przypomnijmy, że Hadoop to framework oparty na modelu programowania MapReduce. Będąc szeroko stosowanym w obliczeniach bardzo dużych mas danych, pojawiło się kilka ulepszeń tego frameworka. Te rozszerzenia to struktury: „BlobSeer” modyfikuje system plików, aby poprawić dostęp do danych, „Phoenix” rozdziela zadania na procesory za pomocą MapReduce, a „Mars” poprawia obliczenia danych na procesorach graficznych.
Jak wspomniano wcześniej, problem wydajności Hadoopa w heterogenicznym środowisku wynika z przesyłania danych między szybkimi i wolnymi węzłami. Gdy przesyłana jest duża ilość danych, ma to znaczny wpływ.
Aby poprawić wydajność Hadoop, konieczne jest zminimalizowanie transferu danych między szybkimi i wolnymi węzłami. W tym celu zaimplementowano mechanizm umieszczania danych; dystrybuuje i przechowuje dane w wielu heterogenicznych węzłach zgodnie z ich możliwościami. Dzięki temu transfer danych może zostać zmniejszony, jeśli liczba danych umieszczonych na dysku każdego węzła jest proporcjonalna do szybkości przetwarzania węzłów.
Replikacja danych ma wiele ograniczeń. Po pierwsze, oznacza to znaczny koszt stworzenia każdej repliki danych wewnątrz klastra posiadającego dużą liczbę węzłów. Po drugie, dystrybucja dużej liczby replik może przeciążyć przepustowość klastra. Po trzecie, przechowywanie replik wymaga dysków o ogromnej pojemności.
PoprawaBadacze skupili się na tym problemie, aby stworzyć mechanizm rozmieszczania danych. Aby rozwiązać ten problem, szukali najlepszego sposobu na umieszczenie danych w miejscu, w którym pliki byłyby dzielone i dystrybuowane na wiele węzłów bez ich duplikowania .
Mechanizm ten opiera się na 2 algorytmach wbudowanych w Hadoop HDFS:
Pierwszy algorytm działa tak:
Jeśli weźmiemy pod uwagę aplikację, korzystającą z MapReduce i plik wejściowy w heterogenicznym klastrze Hadoop. Początkowe rozmieszczenie danych nie uwzględnia wydajności węzła, ponieważ usługa Hadoop szacuje, że wszystkie węzły będą działać i wykonywać swoje zadanie w mniej więcej takim samym czasie. Eksperymenty wykazały, że z reguły czas przetwarzania każdego węzła był stabilny, ponieważ czas odpowiedzi każdego węzła jest liniowo proporcjonalny do rozmiaru danych. Dzięki temu można określić ilościowo szybkość przetwarzania każdego węzła w heterogenicznym środowisku. Termin określający wydajność każdego węzła to „Ratio Performance”.
Wydajność współczynnika każdego węzła jest określana za pomocą tej procedury:
Weźmy przykład, aby pokazać, jak obliczana jest wydajność współczynnika. Rozważ 3 heterogeniczne węzły A, B i C w klastrze Hadoop. Po uruchomieniu aplikacji osobno na każdym węźle otrzymujemy czas odpowiedzi każdego węzła A, B i C (odpowiednio 10 s, 20 s i 30 s). Czas odpowiedzi węzła A jest najkrótszy, dlatego współczynnik wydajności A wynosi 1. Współczynnik wydajności B i C wynosi odpowiednio 2 i 3. Oznacza to, że Węzeł A będzie w stanie zarządzać 30 fragmentami pliku wejściowego, podczas gdy Węzeł C będzie zarządzać tylko 10.
Po uruchomieniu algorytmu dystrybucji fragmentów w celu osiągnięcia początkowego położenia fragmenty mogą ulec uszkodzeniu z kilku powodów:
Aby uniknąć tych problemów, zaimplementowano drugi algorytm, który reorganizuje fragmenty pliku na podstawie współczynnika wydajności węzłów.
Ten algorytm działa tak:
W procesie migracji danych pomiędzy 2 węzłami (jeden przeciążony, drugi z miejscem na dysku) serwer przenosi fragmenty pliku z węzła źródłowego listy węzłów przeciążonych do węzła, który nadal ma miejsce z listy węzłów nieużywanych . Ten proces jest powtarzany, aż liczba fragmentów w każdym węźle będzie odpowiadać jego współczynnikowi wydajności.
PrzedstawieniaAby pokazać wyniki tych algorytmów tego badania, przeprowadzono dwa testy, Grep i WordCount. Te 2 aplikacje działają w klastrach Hadoop. Grep to narzędzie do wyszukiwania wyrażeń regularnych w tekście. WordCount to program służący do liczenia słów w tekście.
Wyniki pokazały, że algorytmy te poprawiły wydajność Grepa średnio o 17% i WordCounta średnio o 7%.
Hadoop to framework oparty na modelu programowania Map/Reduce. A do tego Hadoop musi polegać na „potężnym narzędziu”: systemie plików HDFS. System plików HDFS (zwany Hadoop Distributed File System) jest ważnym parametrem wydajności obliczeniowej Hadoop, ponieważ jest dla niego specyficzny. Oznacza to, że został zaprojektowany tak, aby zmaksymalizować dostęp do danych.
Tylko błędy pozostają, gdy kilka procesów uzyskuje dostęp do tego samego pliku. To framework Blobseer oferuje rozwiązanie tego problemu. Rzeczywiście, ten framework proponuje zmodyfikowanie HDFS w celu zastąpienia go własnym systemem plików BSFS (Blobseer File System).
Nowy system plikówPrzyczyny zmiany tego systemu plików są związane z równoczesnymi problemami z dostępem do tego samego pliku. System HDFS został zaprojektowany, aby zapewnić najlepszą wydajność obliczeniową Hadoop, jednak ta implementacja nie wystarczy. System plików HDFS nie pozwala na utrzymanie wysokiej szybkości przy równoczesnym dostępie do tego samego pliku, ponadto obecny system plików nie pozwala na pewne funkcje, takie jak „wersjonowanie” lub różne jednoczesne aktualizacje tego samego pliku.
Jedną z mocnych stron Hadoopa jest to, że przemierza petabajty w ciągu zaledwie kilku godzin, ponieważ pliki mają rozmiar kilkuset gigabajtów. W rezultacie możliwy jest równoczesny dostęp do małych części tego samego pliku. Należy pamiętać, że praca z milionami małych plików zamiast jednego nie byłaby możliwa, a nawet jeśli system plików na to pozwala, utrzymanie bardzo dużej szybkości nie jest możliwe.
Dlatego Blobseer oferuje system plików, który umożliwia dostęp do małych części dużego pliku, pozwalając tysiącom „klientów” modyfikować ten sam plik bez problemów z konfliktami. BSFS pozwala więc również na „wersjonowanie”, co pozwala na usuwanie niechcianych zmian i tworzenie niezależnych gałęzi, które nie powinny zmniejszać wydajności obliczeń ani przeciążenia przestrzeni dyskowej, która byłaby spowodowana tysiącami małych plików.
PrzedstawieniaWydajność frameworka została przetestowana na grid5000. Blobseer został porównany z Hadoopem. W tym celu wykorzystano frameworki na mikrozadania:
Rekordy wydajności wykazały, że przepustowość (dostęp do danych) była nawet dwukrotnie większa niż Hadoop. Wyniki te ujawniły również, że platforma BlobSeer może obsługiwać nawet dwa razy więcej klientów (tj. liczbę trafień na pojedynczy plik). Stosunek wydajności między BlobSeer i Hadoop wynosi nie więcej niż dwa. Rzeczywiście, BlobSeer wykorzystuje te same możliwości obliczeniowe co Hadoop, z wyjątkiem tego, że system plików został zmodyfikowany.
Phoenix to API oparte na modelu MapReduce, oferowane przez google. Różnica polega na tym, że Phoenix jest używany na komputerach wielordzeniowych i dlatego nie używa serwerów, ale wątków, aby móc korzystać z MapReduce. Phoenix opiera się na języku funkcjonalnym, aby równoległość była całkowicie przejrzysta dla użytkownika. Phoenix jest używany w C i C++.
StrukturaJest to API opracowane do użytku z kodem C/C++, ale można je łatwo wyeksportować do java/C#. Wskaźniki, bufor, wątki P służą do zwiększenia wydajności interfejsu API. Bufory umożliwiają dostęp do danych w pamięci współdzielonej. Istnieją dwa rodzaje buforów: wejście/wyjście to bufory zawierające dane wejściowe oraz dane wyjściowe, czyli dane, których potrzebuje użytkownik, oraz inne bufory. Są to te używane do tworzenia MapReduce, więc są "niewidocznymi" buforami dla użytkownika. Wskaźniki służą do unikania w jak największym stopniu braku duplikacji danych, co znacznie poprawia szybkość obliczeń danych. Korzystanie z P-Threads pozwala interfejsowi API na dystrybucję pracy na wiele procesorów zgodnie z modelem programowania MapReduce.
PrzedstawieniaPrzedstawienia zostały obliczone na podstawie podstawowych zadań, takich jak:
jako punkt odniesienia, wydajność p-wątków bez modelu MapReduce.
Wyniki Phoenix pokazują, że przy 4-rdzeniowym procesorze można przyspieszyć obliczenia o 40%, a przy 8 rdzeniach nawet o 50%. Jednakże, chociaż szybkość obliczeń jest zwiększona, na prostych maszynach pozostaje ona jednak równoważna z szybkością wątków p. Rzeczywiście, chociaż model MapReduce jest bardzo wydajny w klastrach o skali milionów danych, wdrożenie modelu nie jest wystarczająco ogólne, aby objąć wszystkie programy.
Zachęcony sukcesem modelu programowania MapReduce narodził się framework Mars, który umożliwia implementację modelu MapReduce na procesorach graficznych. Procesory graficzne ( GPU ) mają dziesięciokrotnie większą przepustowość pamięci niż procesory , a także są do dziesięciu razy szybsze.
PrzedstawieniaAby ocenić tę wydajność, Marsa porównano z Phoenixem, wykonując te same zadania. Okazało się, że osiągi Marsa są 1,5 raza lepsze niż Feniksa.
OptymalizacjaMars jest nadal badany, jednak istnieją trzy istotne punkty przyszłej ewolucji:
PQL to język zaimplementowany jako rozszerzenie java. Został zaprojektowany w celu zwiększenia jego wyrazistości i modułowości, dokonano porównania jego implementacji z java w podobnych równoległych zadaniach. Równoległość jest aktualnym problemem w informatyce, dlatego ważne jest tworzenie języków lub bibliotek ułatwiających zrównoleglenie. Nie należy jednak zapominać o programowaniu sekwencyjnym, dlatego implementacja języka odpowiedniego do programowania równoległego i sekwencyjnego jest niezbędna. Wszystkie programy realizowane za pomocą PQL są zrównoleglone dzięki programowaniu deklaratywnemu .
Programowanie deklaratywnePQL jest językiem opartym na programowaniu deklaratywnym , co oznacza, że programista może określić co chce zrobić bez faktycznego określania „jak” to zrobić. PQL został wdrożony, aby znaleźć najszybszą metodę do wykonania. Rzeczywiście, będzie wiedział, który fragment kodu powinien być zrównoleglony, czy nie. Nie jest zadaniem programisty dowiedzieć się, jak zoptymalizować swój kod. PQL rozdziela obciążenie na dostępne procesory przy użyciu MapReduce. PQL został zoptymalizowany pod kątem zadań równoległych, dzięki czemu użytkownik ma najmniejszą ilość manipulacji w porównaniu do kodu równoległego napisanego przez użytkownika.
Ilustracja językowaPQL używa wartości logicznych &&, ||, XAND, XOR oraz słów kluczowych, takich jak Reduce, forall, query, exist. Liczba słów kluczowych PQL jest wyraźnie zmniejszona, aby maksymalnie poprawić równoległość.
Zapytanie może być zaimplementowane za pomocą: Quantify Expression (zwraca ilość, używa forall, istnieje ...), Java Expression (kod Java), id (zmienna, z typem lub bez), QExpr (łączy przypadki poprzednie ).
Przykład:
int[] array = query(Array[x]==y):range(1,1000).contains(x) && y=x*x;Zapytanie zwróci tablicę liczb całkowitych zawierającą kwadraty x od 1 do 1000.
Wyrażenie kwantyfikatora można zapisać w postaci: QUANT-EXPR :: = <QUANT> <ID> ':' <QUERY> zapytanie '(' <MATCH> ')' ':' <QUERY> (zapytania kontenerowe) zmniejszyć ' (' id ')' <ID> [ponad <ID-SEQ>]: <QUERY> (Redukcji)
Przykład: forall int x: x == x zawsze prawda (Quantify) (ID) (x == x zapytanie)
Zapytania kontenerowe: zapytanie (Map.get (x) == y): zakres (1, 10) .contains (x) && y == x * x zapytanie '(' <MATCH> ')' ':' <QUERY> Zbuduje mapę zawierającą kwadraty od 1 do 10 (możemy uzyskać dostęp do elementu 0, ale zwróci null)
Operacja redukcji:
reduce (sumInt) x : myset.contains(x) cette expression va additionner tous les x contenus dans myset reduce (sumDouble) x over y : set.contains(y) && x == 1.0 / y Additionne les inverses des éléments contenus dans la mapTypy mogą być deklarowane niejawnie (użytkownik nie musi deklarować typu) lub jawnie (użytkownik musi zadeklarować typ zmiennej). PQL zgłasza wyjątki, ale nie mamy gwarancji zamówienia. PQL używa == lub = dla równości (z wyjątkiem ciągów i obiektów .equals ()).
Użytkownik może tworzyć własne rabaty. Muszą respektować kilka właściwości (metoda statyczna, asocjacyjna, przemienna…). Nieprzestrzeganie tych właściwości prowadziłoby do błędów.
PrzedstawieniaDo oceny PQL zaimplementowano różne zadania (obliczanie premii dla dużej liczby pracowników, znalezienie podciągu w ciągu znaków, listę dokumentów, które można ze sobą powiązać, celem jest znalezienie cykli, obliczyć liczbę wystąpień wszystkich słów w kilku tekstach).
Wdrażanie rozwiązań na różne sposoby:
Przy implementacji z jednowątkowymi i PQL zmienne wejściowe są używane, ale bez zmiennych tymczasowych, podczas gdy w innych implementacjach użycie zmiennych i tablic pośrednich było konieczne albo do komunikacji, albo do optymalizacji. Implementacja SQL jest prosta, ale szybko staje się skomplikowana, jeśli połączysz ją z javą.
Implementacja PQL jest łatwa do napisania, ponieważ zawiera niewiele linijek. Rzeczywiście, rozwiązaniem, które zawiera minimalną liczbę wierszy jest zawsze to z PQL . Drugi to pojedynczy wątek (ale nie zoptymalizowany). Inne metody zawierają od 5 do 20 razy więcej rzędów.
W 4 zadaniach tylko pierwsze nie działa dobrze, ponieważ czas wykonania operacji scalania wyników jest bardzo długi. W przypadku innych zadań PQL może działać od 2 do 6 razy szybciej niż inne implementacje. Wszystkie te testy pokazują, że PQL działa znacznie lepiej i zużywa mniej linii kodu. Należy jednak pamiętać, że SQL i Hadoop korzystają z tabeli danych i dlatego dostęp do tej bazy spowalnia czas ich wykonania. Ponadto platforma Hadoop jest zoptymalizowana pod kątem obliczeń na klastrach, a nie na pojedynczej maszynie.
MapReduce został nagrodzony przede wszystkim za elastyczność i wydajność. Jednak w czasach, gdy ekologia zajmuje ważniejsze miejsce w nowych technologiach, ważne jest zbadanie zużycia energii przez MapReduce i dowiedzenie się, jak je zmniejszyć.
Większość frameworków implementujących MapReduce, takich jak Hadoop, uważa, że przetwarzanie odbywa się w jednorodnym środowisku. W rzeczywistości bardzo rzadko klaster zawiera te same maszyny. Maszyny różnią się w zależności od różnych kryteriów w oparciu o zużycie energii: ilość pasty termicznej, prędkość wentylatora, wielkość wentylatora, umiejscowienie mniej więcej blisko jednostki chłodzącej, ilość kurzu. Oznacza to, że niektóre maszyny będą zużywać więcej energii niż inne, aby wykonać ten sam zabieg.
Dlatego zaprojektowano ramy umożliwiające dynamiczne planowanie zadań zgodnie z indywidualnym zużyciem każdego węzła klastra.
RealizacjaAby móc planować dynamicznie, najpierw musieliśmy opracować sposób na poznanie zużycia każdego węzła. W tym artykule ustalono korelację między temperaturą procesora a zużyciem energii, jednak ta zależność jest niedokładna. Dzieje się tak, ponieważ maszyna może zużywać dużą ilość energii przy niskiej temperaturze, jeśli znajduje się w pobliżu jednostki chłodzącej. Ogólnie rzecz biorąc, ta korelacja pozostaje prawidłowa.
Gdy węzeł główny HDFS rozprowadzi dane, uruchamia wątek, który będzie mierzył temperaturę każdego węzła. Gdy węzeł zakończy przetwarzanie, a jego temperatura jest niższa niż maksymalna temperatura zdefiniowana przez użytkownika, to do węzła zostaje przypisane nowe zadanie, w przeciwnym razie węzeł zostanie wstrzymany do czasu spadku temperatury lub do zakończenia przetwarzania. Jednak po rozdzieleniu wszystkich zadań moduł odporności na awarie rozpocznie pracę niezależnie od temperatury. Rzeczywiście, jeśli wszystkie węzły się ochładzają, zadanie zostanie zablokowane.
Aby zmniejszyć zużycie, zostaną wprowadzone dwa parametry: maksymalna temperatura węzła i liczba zadań do wykonania zabiegu. W kolejnych ewolucjach tego frameworka każdy węzeł będzie miał własną, zdefiniowaną temperaturę, ponieważ niektóre procesory mają wyższą temperaturę podczas pracy.
PrzedstawieniaPomiary przeprowadzono na algorytmie WordCount (oblicza wszystkie iteracje wszystkich słów dokumentu) w niejednorodnym medium.
Przeanalizujemy różnice w wydajności zgodnie z dwoma parametrami wymienionymi w poprzednim rozdziale.
Maksymalna temperaturaLimit temperatury, decydujący o tym, czy węzeł jest w stanie wykonać przetwarzanie, może ograniczyć wydajność. Testy przeprowadzono w trzech różnych temperaturach (80°, 110°, 120°).
Z rysunku widać, że im niższa temperatura maksymalna, tym dłuższy czas pracy. Jeśli maksymalna temperatura jest zbyt zbliżona do temperatury bezczynnych procesorów, bardzo niewiele węzłów otrzyma nowe zadanie po ukończeniu pierwszego. Problem polega na tym, że może to spowodować zawieszenie bieżącego zadania, dopóki węzeł nie osiągnie temperatury poniżej limitu. Pobierając informacje z klastra, w którym wdrożony jest framework, moglibyśmy uniknąć takiego ryzyka. Jedną z najważniejszych informacji byłaby temperatura każdego procesora w spoczynku.
Ponadto zauważamy, że im większa liczba zadań na węzeł i im niższa maksymalna temperatura, tym bardziej wydłuża się czas wykonania. Wynika to z czasu potrzebnego na schłodzenie węzłów, aby powrócić poniżej limitu.
Widzimy ten sam trend w zużyciu energii przez każdy węzeł. Dzięki tym ramom, jeśli prawidłowo dobierzemy temperaturę maksymalną, możliwe jest uzyskanie znacznych oszczędności w zużyciu energii przy jednoczesnym ograniczeniu spadku wydajności.
Dystrybucja danychDystrybucja danych w każdym węźle może również wpływać na wydajność i zużycie MapReduce. Do pomiarów mamy przykład z plikiem 500 MB i jednym z 1 GB.
Na 2 wykresach widzimy 2 punkty przecięcia, pierwszy występuje, gdy stosunek zadania do węzła wynosi 1 (oznacza to, że jest tyle zadań, ile jest węzłów). Drugi występuje, gdy stosunek wynosi 2. Można to wyjaśnić tym, że czas wykonania między najszybszym węzłem a najwolniejszym węzłem jest krótszy niż czas wykonania zadania. Oznacza to, że każdy węzeł otrzymał dwa zadania. Jednak gdy stosunek wynosi 3, zadania są znacznie krótsze, co oznacza, że czas wykonania między najszybszym węzłem a najwolniejszym węzłem jest większy niż czas wykonania zadania. W dalszej części pracy nad tym frameworkiem zostanie zaimplementowana metoda, aby wiedzieć, jak wydajnie rozdzielać zadania. Możemy zauważyć, że maksymalna temperatura nadal odgrywa bardzo ważną rolę w szybkości wykonania.
Aby udowodnić, że maksymalna temperatura i rozkład danych wpływa na zużycie energii. Dokonano pomiarów zużycia energii przez węzeł w klastrze.
Widzimy, że przy maksymalnej temperaturze 80 °C występują dwa szczyty zużycia dla pliku 2 GB. Dzieje się tak, gdy węzeł zostanie przełożony. Gdy węzeł nie jest przesunięty, a zadania stają się krótsze, zwiększa się podział zadań i zmniejsza się zużycie energii.
Dzięki temu frameworkowi zużycie energii przez węzeł spadło o 36%. Ramy te są wciąż w fazie rozwoju, ale już przynoszą bardzo ciekawe rezultaty.
Google uzyskał patent na funkcję MapReduce, ale ważność tego patentu jest kwestionowana.
| Język | współczynnik szybkości klastra | współczynnik szybkości procesora | Oszczędzanie energii | Środowisko | |
|---|---|---|---|---|---|
| Hadoop | Jawa | 1 | NC | NC | Grupa |
| BlobSeer | Jawa | 1,35 | NC | NC | Grupa |
| Marsz | Programowanie GPU | NC | 1,1 ~ 4 | NC | Procesor graficzny |
| Feniks | C / C++ | NC | 1 | NC | Procesor wielordzeniowy |
| Ramy ekologiczne | Jawa | NC | NC | 36% | Grupa |