MapReduce
Концепция MapReduce была введена Дином (Jeffrey Dean) и Гемаватом (Sanjay Ghemawat) в 2004 г. . Для понимания нашей статьи не требуется знание всех деталей работы MapReduce. Коротко говоря, MapReduce обрабатывает данные, распределенные (и реплицированные) между узлами кластера без общих ресурсов на основе трех базовых операций. Во-первых, параллельно выполняется некоторый набор задач Map (по одной задаче на узел) без каких-либо коммуникаций между узлами. Далее данные заново разделяются между узлами кластера. Наконец, параллельно выполняется некоторый набор задач Reduce (по одной задаче в каждом узле, получившем раздел данных). За этим может следовать произвольное число циклов Map-repartition-Reduce, если это требуется. В системе MapReduce не создается какой-либо детальный план выполнения запроса, в котором заранее указывалось бы, какие узлы должны выполнять соответствующие задачи; это определяется во время выполнения. Такой подход позволяет системам MapReduce "на лету" подстраиваться к отказам узлов и медленным узлам путем назначения большего числа задач более быстрым узлам и переназначения задач, которые были назначены для отказавших узлов. Кроме того, в MapReduce на локальный диск сбрасываются результаты каждой задачи Map, чтобы минимизировать объем работы, которую придется повторно выполнить после возникновения отказа.
Что касается требуемых свойств рабочих нагрузок крупномасштабного анализа данных, то MapReduce наилучшим образом поддерживает свойства отказоустойчивости и возможности функционировать в разнородных средах. Отказоустойчивость достигается за счет выявления и переназначения другим узлам задач отказавших узлов (предпочтение отдается узлам, содержащим реплики входных данных Map). Возможность функционирования в неоднородных средах обеспечивается за счет выполнения избыточных задач. Задачи, выполнение которых занимает долгое время в медленных узлах, избыточным образом выполняются на узлах, завершивших выполнение назначенных им задач. Время выполнения подобной задачи становится равным времени выполнения в самом быстром узле назначенной ему избыточной задачи. Если делать задачи достаточно мелкими, то можно минимизировать влияние отказов и "отстающих" узлов.
В MapReduce имеется гибкий интерфейс запросов; функции Map и Reduce представляют собой всего лишь произвольные вычисления, закодированные на некотором языке общего назначения. Поэтому каждая задача может делать со своими входными данными все, что угодно, лишь бы только она производила результирующие данные в соответствии с соглашениями модели. В большинстве систем, основанных на MapReduce, (в том числе, и в системе Hadoop, в которой напрямую реализованы детали системного уровня, описанные в статье про MapReduce) не поддерживается декларативный SQL. Однако имеются некоторые исключения (например, Hive).
Как было показано в предыдущем исследовании, самой большой проблемой MapReduce является производительность . Поскольку от пользователей не требуется моделирование и загрузка данных до их обработки, использование многих упомянутых выше средств повышения производительности, применяемых в системах баз данных, в данном случае оказывается невозможным.
В идеальном случае отказоустойчивость и возможность функционировать в неоднородных средах MapReduce можно было бы объединить с производительностью параллельных систем баз данных. В следующих разделах мы опишем свою попытку построить такую гибридную систему.
