MapReduce

MapReduce jest modelem programowania oraz platformą przetwarzania danych opracowaną w celu rozwiązywania problemów z zakresu big data na dużą skalę przy użyciu klastrów komputerów. Model ten rozdziela zadanie na dwie podstawowe fazy – Map oraz Reduce – a pomiędzy nimi odbywa się etap sortowania i przemieszczania danych, zwany Shuffle. Dzięki takiej strukturze MapReduce umożliwia równoległe przetwarzanie ogromnych zbiorów danych przy zachowaniu prostoty programistycznej.

Historia

Pomysł na MapReduce został przedstawiony w 2004 roku w artykule „MapReduce: Simplified Data Processing on Large Clusters” autorstwa Jeffreya Dean i Sanjaya Ghemawata z firmy Google. Wdrożenie tego modelu w praktyce nastąpiło w 2006 roku, kiedy Apache Hadoop – otwarto‑źródłowa implementacja MapReduce – został udostępniony społeczności open‑source. Od tego czasu technologia stała się fundamentem wielu systemów analitycznych i przetwarzania danych, m.in. Amazon EMR, Cloudera i Hortonworks.

Podstawowe pojęcia

• Map – funkcja przetwarzająca każdy rekord wejściowy i generująca zestaw par (klucz, wartość). Działa niezależnie na poszczególnych fragmentach danych, co umożliwia wysoką paralelność.
• Shuffle – etap pośredni, w którym wszystkie pary (klucz, wartość) są grupowane według klucza. Dane są przenoszone pomiędzy węzłami klastra, aby wszystkie wartości o tym samym kluczu trafiły do tego samego procesu Reduce.
• Reduce – funkcja agregująca wszystkie wartości powiązane z danym kluczem i produkująca ostateczny wynik (np. sumę, średnią, listę).

Architektura i komponenty

Typowa implementacja MapReduce składa się z następujących elementów:

• JobTracker (lub ApplicationMaster w nowszych wersjach YARN) – zarządza planowaniem zadań, ich monitorowaniem oraz alokacją zasobów.
• TaskTracker (lub NodeManager) – wykonuje przydzielone zadania Map i Reduce na poszczególnych węzłach.
• HDFS (Hadoop Distributed File System) – rozproszony system plików, w którym przechowywane są zarówno dane wejściowe, jak i wyniki pośrednie oraz końcowe.

Zastosowania

MapReduce znajduje zastosowanie w wielu dziedzinach, m.in.:

• Analiza logów internetowych (np. liczenie unikalnych odwiedzających).
• Indeksowanie dokumentów i wyszukiwanie pełnotekstowe.
• Przetwarzanie danych genomowych w bioinformatyce.
• Modelowanie i uczenie maszynowe w trybie wsadowym.
• Agregacja danych telemetrycznych w systemach IoT.

Korzyści

• Skalowalność – model pozwala na zwiększanie mocy obliczeniowej przez prostą dodawanie kolejnych węzłów do klastra.
• Odporność na awarie – w przypadku awarii pojedynczego węzła zadania są automatycznie przenoszone i ponownie uruchamiane na innych maszynach.
• Abstrakcja programistyczna – programiści muszą definiować jedynie funkcje Map i Reduce, a system zajmuje się rozdzielaniem pracy i komunikacją.

Ograniczenia

• Model wymaga, aby przetwarzanie mogło być wyrażone jako dwie fazy, co nie zawsze jest optymalne dla algorytmów iteracyjnych.
• Wysoki narzut związany z etapem Shuffle i zapisem/odczytem z HDFS, co ogranicza wydajność w zadaniach wymagających częstej wymiany danych.
• MapReduce nie jest odpowiedni do pracy w czasie rzeczywistym – do tego służą systemy takie jak Apache Spark czy Apache Flink.

Powiązane technologie

W ekosystemie przetwarzania dużych zbiorów danych MapReduce współistnieje z wieloma innymi narzędziami i koncepcjami:

• Apache Spark – platforma oferująca podobny model programowania, ale z pamięcią operacyjną (in‑memory) i wsparciem dla przetwarzania strumieniowego.
• Apache Flink – system do przetwarzania danych w trybie ciągłym i wsadowym.
• YARN (Yet Another Resource Negotiator) – menedżer zasobów w Hadoopzie, umożliwiający uruchamianie różnych typów zadań, w tym MapReduce.
• Rozproszone systemy – kontekst, w którym MapReduce funkcjonuje, zapewniając spójność i dostępność danych.

Przykład implementacji

Poniżej przedstawiono prosty przykład programu MapReduce napisanego w języku Java, którego celem jest zliczanie wystąpień słów w zbiorze tekstowym.

public class WordCount {

    public static class TokenizerMapper
            extends Mapper<Object, Text, Text, IntWritable> {

        private final static IntWritable one = new IntWritable(1);
        private Text word = new Text();

        public void map(Object key, Text value, Context context)
                throws IOException, InterruptedException {
            StringTokenizer itr = new StringTokenizer(value.toString());
            while (itr.hasMoreTokens()) {
                word.set(itr.nextToken());
                context.write(word, one);
            }
        }
    }

    public static class IntSumReducer
            extends Reducer<Text, IntWritable, Text, IntWritable> {

        private IntWritable result = new IntWritable();

        public void reduce(Text key, Iterable<IntWritable> values, Context context)
                throws IOException, InterruptedException {
            int sum = 0;
            for (IntWritable val : values) {
                sum += val.get();
            }
            result.set(sum);
            context.write(key, result);
        }
    }

    public static void main(String[] args) throws Exception {
        Configuration conf = new Configuration();
        Job job = Job.getInstance(conf, "word count");
        job.setJarByClass(WordCount.class);
        job.setMapperClass(TokenizerMapper.class);
        job.setCombinerClass(IntSumReducer.class);
        job.setReducerClass(IntSumReducer.class);
        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(IntWritable.class);
        FileInputFormat.addInputPath(job, new Path(args[0]));
        FileOutputFormat.setOutputPath(job, new Path(args[1]));
        System.exit(job.waitForCompletion(true) ? 0 : 1);
    }
}

W powyższym przykładzie TokenizerMapper emituje pary (słowo, 1), a IntSumReducer sumuje wszystkie wartości dla tego samego słowa, dając ostateczną liczbę wystąpień.

Patrzenie w przyszłość

Choć MapReduce w czystej formie traci na popularności na rzecz szybszych rozwiązań, nadal jest ważnym elementem zrozumienia przetwarzania rozproszonego i stanowi podstawę dla wielu współczesnych systemów analitycznych. Jego zasady wpływają na projektowanie algorytmów w Spark, Flink i innych platformach, które rozszerzają model o możliwości przetwarzania w pamięci, iteracyjne oraz strumieniowe.

Artykuł opracowany na podstawie dostępnych źródeł publicznych oraz dokumentacji projektów Apache Hadoop, Google i Apache Spark.