Войти
MapReduce является моделью программирования и связанной с ним реализацией для обработки и генерации больших данных наборов с параллельно, распределенным алгоритмом на кластере.
Программа MapReduce состоит из процедуры сопоставления, которая выполняет фильтрацию и сортировку (например, сортировку студентов по имени в очереди, одна очередь для каждого имени), и метода сокращения, который выполняет сводную операцию (например, подсчет количества студентов в каждой очереди, с указанием частотности имен). «MapReduce System» (также называемая «инфраструктура» или «рамки») дирижирует обработка сортировочных распределенных серверов, запуск различных задач параллельно, управление все коммуникации и передачи данных между различными частями системы, и обеспечения избыточности и отказоустойчивость.
Модель представляет собой специализацию стратегии разделения-применения-объединения для анализа данных. Он основан на функциях map и reduce, обычно используемых в функциональном программировании, хотя их назначение в среде MapReduce отличается от их исходных форм. Ключевым вкладом инфраструктуры MapReduce являются не фактические функции сопоставления и сокращения (которые, например, напоминают операции сокращения и разброса стандарта интерфейса передачи сообщений 1995 года), а масштабируемость и отказоустойчивость, достигаемые для множества приложений за счет оптимизации двигатель исполнения. Таким образом, однопоточная реализация MapReduce обычно не быстрее традиционной (не-MapReduce) реализации; любой выигрыш обычно наблюдается только при многопоточной реализации на многопроцессорном оборудовании. Использование этой модели выгодно только тогда, когда в игру вступают оптимизированная операция распределенного перемешивания (которая снижает стоимость сетевой связи) и функции отказоустойчивости инфраструктуры MapReduce. Оптимизация стоимости связи важна для хорошего алгоритма MapReduce.
Библиотеки MapReduce написаны на многих языках программирования с разными уровнями оптимизации. Популярная реализация с открытым исходным кодом, которая поддерживает распределенное перемешивание, является частью Apache Hadoop. Название MapReduce первоначально относилось к частной технологии Google, но с тех пор было обобщено. К 2014 году Google больше не использовал MapReduce в качестве основной модели обработки больших данных, а разработка Apache Mahout перешла на более функциональные и менее ориентированные на диск механизмы, которые включали полную карту и ограничивали возможности.
Некоторые векторные процессоры, такие как NEC SX-Aurora TSUBASA, имеют обширную поддержку mapreduce, встроенную в их векторные инструкции, в том числе в RISC-V Vectors.
MapReduce - это платформа для обработки задач, которые можно распараллелить, в больших наборах данных с использованием большого количества компьютеров (узлов), вместе называемых кластером (если все узлы находятся в одной локальной сети и используют подобное оборудование) или сеткой (если узлы совместно используются географически и административно распределенными системами и используют более разнородное оборудование). Обработка может происходить с данными, хранящимися либо в файловой системе (неструктурированной), либо в базе данных (структурированной). MapReduce может использовать преимущества локальности данных, обрабатывая их рядом с местом, где они хранятся, чтобы минимизировать накладные расходы на связь.
Фреймворк (или система) MapReduce обычно состоит из трех операций (или шагов):
mapфункцию к локальным данным и записывает вывод во временное хранилище. Главный узел обеспечивает обработку только одной копии избыточных входных данных.mapфункцией), так что все данные, принадлежащие одному ключу, находятся на одном рабочем узле.MapReduce позволяет выполнять распределенную обработку карты и операции сокращения. Карты могут выполняться параллельно, при условии, что каждая операция сопоставления не зависит от других; на практике это ограничено количеством независимых источников данных и / или количеством процессоров рядом с каждым источником. Точно так же набор «редукторов» может выполнять фазу редукции при условии, что все выходные данные операции сопоставления, которые используют один и тот же ключ, представлены одному и тому же редуктору в одно и то же время, или что функция редукции является ассоциативной. Хотя этот процесс часто кажется неэффективным по сравнению с более последовательными алгоритмами (поскольку необходимо запускать несколько экземпляров процесса сокращения), MapReduce может применяться к значительно большим наборам данных, чем может обрабатывать один "стандартный" сервер - большая ферма серверов может использовать MapReduce позволяет отсортировать петабайт данных всего за несколько часов. Параллелизм также предлагает некоторую возможность восстановления после частичного отказа серверов или хранилища во время операции: если один преобразователь или редуктор выйдет из строя, работа может быть перепланирована - при условии, что входные данные все еще доступны.
Другой способ взглянуть на MapReduce - это 5-этапное параллельное и распределенное вычисление:
Эти пять шагов можно логически представить как выполняющиеся в последовательности - каждый шаг начинается только после завершения предыдущего шага - хотя на практике их можно чередовать, если это не влияет на конечный результат.
Во многих ситуациях входные данные могли уже быть распределены ( «сегментированы» ) между множеством разных серверов, и в этом случае шаг 1 иногда можно было значительно упростить, назначив серверы карт, которые будут обрабатывать локально присутствующие входные данные. Точно так же шаг 3 иногда можно ускорить, назначив процессоры Reduce, которые максимально приближены к данным, сгенерированным картой, которые им необходимо обработать.
Функции Map и Reduce в MapReduce определены относительно данных, структурированных парами (ключ, значение). Карта принимает одну пару данных с типом в одном домене данных и возвращает список пар в другом домене:
Map(k1,v1) → list(k2,v2)
Функция Map применяется параллельно к каждой паре (с ключом k1) во входном наборе данных. Это создает список пар (с ключом k2) для каждого вызова. После этого платформа MapReduce собирает все пары с одним и тем же ключом ( k2) из всех списков и группирует их вместе, создавая одну группу для каждого ключа.
Затем функция Reduce применяется параллельно к каждой группе, которая, в свою очередь, создает набор значений в том же домене:
Reduce(k2, list (v2)) → list((k3, v3))
Каждый вызов Reduce обычно производит либо одну пару значений ключа, либо пустой возврат, хотя один вызов может возвращать более одной пары значений ключа. Возвраты всех вызовов собираются в виде списка желаемых результатов.
Таким образом, инфраструктура MapReduce преобразует список пар (ключ, значение) в другой список пар (ключ, значение). Это поведение отличается от типичной комбинации функционального программирования map и reduce, которая принимает список произвольных значений и возвращает одно единственное значение, объединяющее все значения, возвращаемые map.
Это необходимо, но не достаточно, чтобы иметь реализации карты и уменьшить абстракции для реализации MapReduce. Для распределенных реализаций MapReduce требуются средства соединения процессов, выполняющих фазы Map и Reduce. Это может быть распределенная файловая система. Возможны и другие варианты, такие как прямая потоковая передача от сопоставителей к редукторам или для процессоров сопоставления, чтобы передать свои результаты редукторам, которые их запрашивают.
Канонический пример MapReduce подсчитывает появление каждого слова в наборе документов:
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)
Здесь каждый документ разбивается на слова, и каждое слово подсчитывается функцией карты, используя слово в качестве ключа результата. Фреймворк объединяет все пары с одним и тем же ключом и передает их одному и тому же вызову для сокращения. Таким образом, этой функции просто нужно просуммировать все входные значения, чтобы найти общее количество появлений этого слова.
В качестве другого примера представьте, что для базы данных, содержащей 1,1 миллиарда человек, нужно вычислить среднее количество социальных контактов, которые имеет человек в зависимости от возраста. В SQL такой запрос можно выразить как:
SELECT age, AVG(contacts) FROM social.person GROUP BY age ORDER BY age
Используя MapReduce, значения ключа K1 могут быть целыми числами от 1 до 1100, каждое из которых представляет пакет из 1 миллиона записей, значение ключа K2 может быть возрастом человека в годах, и это вычисление может быть выполнено с помощью следующих функций:
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
Система MapReduce выстроит 1100 процессоров Map и предоставит каждому соответствующий 1 миллион входных записей. На этапе Map будет создано 1,1 миллиарда (Y, (N, 1)) записей со значениями Y в диапазоне, скажем, от 8 до 103. Система MapReduce затем выстроит 96 процессоров Reduce, выполнив операцию перемешивания ключа / значения. пары из-за того, что нам нужно среднее значение по возрасту, и предоставить каждому миллионы соответствующих входных записей. Уменьшение шаг приведет к значительно сниженному набору только 96 выходных записей (Y, A), которые будут поставлены в конечном итоге файл, отсортированном по Y.
Информация о счетчике в записи важна, если обработка сокращается более одного раза. Если бы мы не добавляли количество записей, вычисленное среднее значение было бы неверным, например:
-- 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
Если мы уменьшим файлы №1 и №2, у нас будет новый файл со средним числом контактов 9 для 10-летнего человека ((9 + 9 + 9 + 9 + 9) / 5):
-- reduce step #1: age, average of contacts 10, 9
Если мы сократим его с помощью файла № 3, мы потеряем счет того, сколько записей мы уже видели, поэтому мы получаем в среднем 9,5 контактов для 10-летнего человека ((9 + 10) / 2), что неверно. Правильный ответ: 9,1 66 = 55/6 = (9 * 3 + 9 * 2 + 10 * 1) / (3 + 2 + 1).
Архитектура фреймворка программного обеспечения придерживается принципа открытого-закрытого, когда код эффективно разделяется на неизменяемые замороженные точки и расширяемые горячие точки. Замороженное место фреймворка MapReduce - это большой распределенный вид. Приложение определяет следующие горячие точки:
На входе считыватель делит вход в соответствующий размере «расколы» (на практике, как правило, 64 МБ до 128 МБ) и каркасные присваивает один сплит каждой карту функцию. Устройство чтения ввода считывает данные из стабильного хранилища (обычно распределенной файловой системы ) и генерирует пары ключ / значение.
Обычный пример будет читать каталог, полный текстовых файлов, и возвращать каждую строку как запись.
Функция Map принимает серию пар ключ / значение, обрабатывает каждую и генерирует ноль или более выходных пар ключ / значение. Типы ввода и вывода карты могут отличаться (и часто отличаются) друг от друга.
Если приложение выполняет подсчет слов, функция карты разбивает строку на слова и выводит пару ключ / значение для каждого слова. Каждая выходная пара будет содержать слово в качестве ключа и количество экземпляров этого слова в строке в качестве значения.
Каждая карта выходная функции выделяются для конкретного редуктора с помощью приложения разбиения функции для шардинге целей. Функция секционирования получает ключ и количество редукторов и возвращает индекс желаемого редуктора.
Типичное значение по умолчанию - хэширование ключа и использование значения хеш-функции по модулю количества редукторов. Важно выбрать функцию секционирования, которая дает приблизительно равномерное распределение данных по сегменту для целей балансировки нагрузки, в противном случае операция MapReduce может быть приостановлена в ожидании завершения медленных редукторов (т. Е. Редукторам назначены большие доли не- равномерно разделенные данные).
Между этапами сопоставления и сокращения данные перемешиваются (параллельная сортировка / обмен между узлами), чтобы переместить данные из узла карты, который их создал, в сегмент, в котором они будут сокращены. Перемешивание иногда может занимать больше времени, чем время вычислений, в зависимости от пропускной способности сети, скорости ЦП, производимых данных и времени, затрачиваемого на отображение и сокращение вычислений.
Входные данные для каждого Reduce берутся с компьютера, на котором выполнялась карта, и сортируются с помощью функции сравнения приложения.
Платформа вызывает функцию Reduce приложения один раз для каждого уникального ключа в отсортированном порядке. Уменьшение может перебирать значения, которые связаны с этим ключом и производить ноль или более выходов.
В примере с подсчетом слов функция Reduce принимает входные значения, суммирует их и генерирует единственный выходной сигнал слова и окончательной суммы.
Устройство записи вывода записывает вывод Reduce в стабильное хранилище.
Работа программ MapReduce не гарантируется. Основным преимуществом этой модели программирования является использование оптимизированной операции перемешивания платформы и необходимость писать только части программы Map и Reduce. Однако на практике автор программы MapReduce должен учитывать этап перемешивания; в частности, функция секционирования и объем данных, записываемых функцией Map, могут иметь большое влияние на производительность и масштабируемость. Дополнительные модули, такие как функция Combiner, могут помочь уменьшить объем данных, записываемых на диск и передаваемых по сети. Приложения MapReduce могут достигать сублинейного ускорения при определенных обстоятельствах.
При разработке алгоритма MapReduce автору необходимо выбрать хороший компромисс между вычислительными затратами и затратами на связь. Стоимость связи часто преобладает над стоимостью вычислений, и многие реализации MapReduce предназначены для записи всех сообщений в распределенное хранилище для восстановления после сбоя.
При настройке производительности MapReduce необходимо учитывать сложность сопоставления, перемешивания, сортировки (группировки по ключу) и сокращения. Объем данных, производимых модулями сопоставления, является ключевым параметром, который перемещает основную часть вычислительных затрат между сопоставлением и сокращением. Редукция включает в себя сортировку (группировку ключей), имеющую нелинейную сложность. Следовательно, небольшие размеры разделов сокращают время сортировки, но есть компромисс, потому что наличие большого количества редукторов может быть непрактичным. Влияние размера разделенного блока незначительно (если он не выбран особенно плохо, скажем lt;1 МБ). Выгоды от чтения нагрузки с локальных дисков некоторыми картографами в среднем незначительны.
Для процессов, которые завершаются быстро и где данные помещаются в основную память отдельного компьютера или небольшого кластера, использование инфраструктуры MapReduce обычно неэффективно. Поскольку эти структуры предназначены для восстановления после потери целых узлов во время вычислений, они записывают промежуточные результаты в распределенное хранилище. Это восстановление после сбоя является дорогостоящим и окупается только тогда, когда в вычислениях задействовано много компьютеров и выполняется длительное время выполнения вычислений. Задачу, которая завершается за секунды, можно просто перезапустить в случае ошибки, и вероятность отказа хотя бы одной машины быстро растет с увеличением размера кластера. При таких проблемах реализации, сохраняющие все данные в памяти и просто перезапускающие вычисления при сбоях узлов или - когда данные достаточно малы - нераспределенные решения часто оказываются быстрее, чем система MapReduce.
MapReduce обеспечивает надежность, распределяя ряд операций с набором данных для каждого узла в сети. Ожидается, что каждый узел будет периодически отчитываться о выполненной работе и обновлениях статуса. Если узел не работает дольше этого интервала, главный узел (аналогичный главному серверу в файловой системе Google ) записывает узел как неработающий и отправляет назначенную ему работу другим узлам. Отдельные операции используют атомарные операции для именования выходных файлов в качестве проверки, чтобы убедиться, что не запущены параллельные конфликтующие потоки. Когда файлы переименовываются, их можно также скопировать под другое имя в дополнение к имени задачи (с учетом побочных эффектов ).
Операции сокращения работают примерно так же. Из-за своих худших свойств в отношении параллельных операций главный узел пытается запланировать операции сокращения на том же узле или в той же стойке, что и узел, содержащий обрабатываемые данные. Это свойство желательно, поскольку оно сохраняет полосу пропускания в магистральной сети центра обработки данных.
Реализации не обязательно отличаются высокой надежностью. Например, в старых версиях Hadoop NameNode была единственной точкой отказа для распределенной файловой системы. Более поздние версии Hadoop обладают высокой доступностью с активным / пассивным переключением при отказе для «NameNode».
MapReduce полезен в широком спектре приложений, включая распределенный поиск на основе шаблонов, распределенную сортировку, обращение веб-ссылок и графов, разложение по сингулярным значениям, статистику журнала веб-доступа, построение инвертированного индекса, кластеризацию документов, машинное обучение и статистический машинный перевод. Более того, модель MapReduce была адаптирована к нескольким вычислительным средам, таким как многоядерные и многоядерные системы, настольные гриды, мульти-кластеры, добровольные вычислительные среды, динамические облачные среды, мобильные среды и высокопроизводительные вычислительные среды.
В Google MapReduce использовался для полной регенерации индекса всемирной паутины Google. Он заменил старые специальные программы, которые обновляли индекс и выполняли различные анализы. С тех пор разработка в Google перешла к таким технологиям, как Percolator, FlumeJava и MillWheel, которые предлагают операции потоковой передачи и обновления вместо пакетной обработки, что позволяет интегрировать «живые» результаты поиска без восстановления полного индекса.
Стабильные входные и выходные данные MapReduce обычно хранятся в распределенной файловой системе. Переходные данные обычно хранятся на локальном диске и извлекаются удаленно редукторами.
Дэвид ДеВитт и Майкл Стоунбрейкер, компьютерные ученые, специализирующиеся на параллельных базах данных и архитектурах без совместного использования ресурсов, критически оценивают широкий спектр проблем, для решения которых может использоваться MapReduce. Они назвали его интерфейс слишком низкоуровневым и задались вопросом, действительно ли он представляет собой сдвиг парадигмы, о котором заявляли его сторонники. Они оспорили утверждения сторонников MapReduce о новизне, сославшись на Teradata в качестве примера предшествующего уровня техники, существующего более двух десятилетий. Они также сравнили программистов MapReduce с программистами CODASYL, отметив, что оба они «пишут на низкоуровневом языке, выполняя низкоуровневые манипуляции с записями». Использование MapReduce входных файлов и отсутствие поддержки схемы не позволяет повысить производительность, обеспечиваемую общими функциями системы баз данных, такими как B-деревья и хеш-секционирование, хотя такие проекты, как Pig (или PigLatin), Sawzall, Apache Hive, HBase и Bigtable, обращаются к некоторым из них. этих проблем.
Грег Йоргенсен написал статью, отвергающую эти взгляды. Йоргенсен утверждает, что весь анализ ДеВитта и Стоунбрейкера беспочвенен, поскольку MapReduce никогда не разрабатывался и не предназначался для использования в качестве базы данных.
Впоследствии ДеВитт и Стоунбрейкер в 2009 году опубликовали подробное эталонное исследование, в котором сравнивается производительность подходов Hadoop MapReduce и СУБД по нескольким конкретным проблемам. Они пришли к выводу, что реляционные базы данных предлагают реальные преимущества для многих видов использования данных, особенно при сложной обработке или в тех случаях, когда данные используются в масштабах всего предприятия, но что MapReduce может быть проще для пользователей для решения простых или одноразовых задач обработки.
Парадигма программирования MapReduce также была описана в диссертации Дэнни Хиллиса 1985 года и широко использовалась в то время для программирования машины соединений, которая имела специальную аппаратную поддержку для ускорения как отображения, так и сокращения.
В 2010 году Google получил патент на MapReduce. Патент, поданный в 2004 году, может охватывать использование MapReduce программным обеспечением с открытым исходным кодом, таким как Hadoop, CouchDB и другими. В Ars Technica редактор признал роль Google в популяризации концепции MapReduce, но поставил под сомнение, был ли патент действительным или новым. В 2013 году в рамках своего «Обязательства о неприкрытии патента (OPN)» Google пообещал использовать патент только в целях защиты. Срок действия патента истекает 23 декабря 2026 года.
Задачи MapReduce должны быть написаны как программы с ациклическим потоком данных, то есть преобразователь без сохранения состояния, за которым следует редуктор без состояния, которые выполняются планировщиком пакетных заданий. Эта парадигма затрудняет повторные запросы наборов данных и накладывает ограничения, которые ощущаются в таких областях, как машинное обучение, где итерационные алгоритмы, многократно пересматривающие один рабочий набор, являются нормой.
