MapReduce - Википедия - MapReduce

Уменьшение карты это модель программирования и связанная реализация для обработки и генерации большое количество данных наборы с параллельно, распределен алгоритм на кластер.[1][2][3]

Программа MapReduce состоит из карта процедура, который выполняет фильтрацию и сортировку (например, сортирует студентов по именам в очереди, по одной очереди для каждого имени), и уменьшать , который выполняет итоговую операцию (например, подсчет количества студентов в каждой очереди, получение частот имен). «Система MapReduce» (также называемая «инфраструктурой» или «структурой») управляет обработкой с помощью сортировка распределенные серверы, выполняющие различные задачи параллельно, управляющие всеми коммуникациями и передачей данных между различными частями системы и обеспечивающие избыточность и Отказоустойчивость.

Модель является специализацией разделить-применить-объединить стратегия анализа данных.[4]Он вдохновлен карта и уменьшать функции, обычно используемые в функциональное программирование,[5] хотя их назначение во фреймворке MapReduce отличается от их первоначальных форм.[6] Ключевой вклад фреймворка MapReduce - это не фактические функции map и reduce (которые, например, напоминают функции 1995 года Интерфейс передачи сообщений стандартные[7] уменьшать[8] и разбросать[9] операций), но масштабируемость и отказоустойчивость достигаются для множества приложений за счет оптимизации механизма выполнения.[нужна цитата ]. Таким образом, однопоточный реализация MapReduce обычно не быстрее традиционной (не-MapReduce) реализации; любые достижения обычно видны только с многопоточный реализации на многопроцессорном оборудовании.[10] Использование этой модели выгодно только тогда, когда в игру вступают оптимизированная операция распределенного перемешивания (которая снижает затраты на сетевое взаимодействие) и функции отказоустойчивости инфраструктуры MapReduce. Оптимизация стоимости связи важна для хорошего алгоритма MapReduce.[11]

Уменьшение карты библиотеки были написаны на многих языках программирования с разными уровнями оптимизации. Популярный Открытый исходный код реализация с поддержкой распределенного перемешивания является частью Apache Hadoop. Название MapReduce первоначально относилось к собственному Google технологии, но с тех пор обобщенный. К 2014 году Google больше не использовал MapReduce в качестве основного большое количество данных модель обработки,[12] и развитие на Apache Mahout перешел к более мощным и менее ориентированным на диски механизмам, которые включают полную карту и ограничивают возможности.[13]

Обзор

MapReduce - это фреймворк для обработки распараллеливаемый проблемы с большими наборами данных с использованием большого количества компьютеров (узлов), вместе называемые кластер (если все узлы находятся в одной локальной сети и используют одинаковое оборудование) или сетка (если узлы используются совместно географически и административно распределенными системами и используют более разнородное оборудование). Обработка может происходить с данными, хранящимися в файловая система (неструктурированный) или в база данных (структурированный). MapReduce может использовать локальность данных, обрабатывая их рядом с местом, где они хранятся, чтобы минимизировать накладные расходы на связь.

Фреймворк (или система) MapReduce обычно состоит из трех операций (или шагов):

  1. Карта: каждый рабочий узел применяет карта в локальные данные и записывает вывод во временное хранилище. Главный узел обеспечивает обработку только одной копии избыточных входных данных.
  2. Перемешать: рабочие узлы перераспределяют данные на основе выходных ключей (созданных карта function), так что все данные, принадлежащие одному ключу, находятся на одном рабочем узле.
  3. Уменьшать: рабочие узлы теперь обрабатывают каждую группу выходных данных для каждого ключа параллельно.

MapReduce позволяет выполнять распределенную обработку карты и операции сокращения. Карты могут выполняться параллельно при условии, что каждая операция сопоставления не зависит от других; на практике это ограничено количеством независимых источников данных и / или количеством процессоров рядом с каждым источником. Точно так же набор «редукторов» может выполнять фазу редукции при условии, что все выходные данные операции сопоставления, которые используют один и тот же ключ, представлены одному и тому же редуктору в одно и то же время, или что функция редукции ассоциативный. Хотя этот процесс часто кажется неэффективным по сравнению с более последовательными алгоритмами (поскольку необходимо запускать несколько экземпляров процесса сокращения), MapReduce может применяться к значительно большим наборам данных, чем один "товарный" сервер может справиться - большой ферма серверов можно использовать MapReduce для сортировки петабайт данных всего за несколько часов.[14] Параллелизм также предлагает некоторую возможность восстановления после частичного отказа серверов или хранилища во время операции: если один преобразователь или редуктор выйдет из строя, работу можно перенести, если входные данные все еще доступны.

Другой способ взглянуть на MapReduce - это 5-этапное параллельное и распределенное вычисление:

  1. Подготовьте ввод Map () - «Система MapReduce» обозначает процессоры карты, назначает клавишу ввода K1 что каждый процессор будет работать, и предоставляет этому процессору все входные данные, связанные с этим ключом.
  2. Запустите предоставленный пользователем код Map () - Map () запускается ровно один раз для каждого K1 ключ, генерирующий вывод, организованный по ключу K2.
  3. "Перемешать" вывод карты в процессоры Reduce - система MapReduce обозначает процессоры Reduce, назначает K2 key, с которым должен работать каждый процессор, и предоставляет этому процессору все сгенерированные Map данные, связанные с этим ключом.
  4. Запустите предоставленный пользователем код Reduce () - Reduce () запускается ровно один раз для каждого K2 ключ, созданный на шаге Map.
  5. Произвести окончательный результат - система MapReduce собирает все выходные данные Reduce и сортирует их по K2 чтобы произвести окончательный результат.

Эти пять шагов можно логически представить как выполняющиеся последовательно - каждый шаг начинается только после завершения предыдущего шага - хотя на практике их можно чередовать, если это не влияет на конечный результат.

Во многих ситуациях входные данные могли уже быть распределены ("сегментированный" ) среди множества различных серверов, и в этом случае шаг 1 иногда можно значительно упростить, назначив серверы карты, которые будут обрабатывать локально представленные входные данные. Точно так же шаг 3 иногда можно ускорить, назначив процессоры Reduce, которые максимально приближены к сгенерированным Map данным, которые им необходимо обработать.

Логический взгляд

В карта и Уменьшать функции Уменьшение карты оба определены в отношении данных, структурированных парами (ключ, значение). карта берет одну пару данных с типом в один область данных, и возвращает список пар в другом домене:

Карта (k1, v1) → список (k2, v2)

В карта функция применяется параллельно к каждой паре (с ключом k1) во входном наборе данных. Это создает список пар (с ключом k2) для каждого вызова, после чего фреймворк MapReduce собирает все пары с одним и тем же ключом (k2) из всех списков и группирует их вместе, создавая по одной группе для каждого ключа.

В Уменьшать Затем функция применяется параллельно к каждой группе, которая, в свою очередь, создает набор значений в том же домене:

Уменьшить (k2, list (v2)) → список ((k3, v3))[15]

Каждый Уменьшать вызов обычно производит либо одну пару значений ключа, либо пустой возврат, хотя один вызов может возвращать более одной пары значений ключа. Возвраты всех вызовов собираются в виде списка желаемых результатов.

Таким образом, инфраструктура MapReduce преобразует список пар (ключ, значение) в другой список пар (ключ, значение).[16] Это поведение отличается от типичной комбинации функционального программирования и сокращения, которая принимает список произвольных значений и возвращает одно значение, которое объединяет все значения, возвращаемые картой.

это необходимо, но недостаточно иметь реализации карты и уменьшить количество абстракций для реализации MapReduce. Для распределенных реализаций MapReduce требуются средства соединения процессов, выполняющих фазы Map и Reduce. Это может быть распределенная файловая система. Возможны и другие варианты, такие как прямая потоковая передача от модулей сопоставления к редукторам или для процессоров сопоставления передавать свои результаты редукторам, которые их запрашивают.

Примеры

В каноническом примере MapReduce подсчитывается появление каждого слова в наборе документов:[17]


функция карта(Имя строки, документ String): // name: название документа  // документ: содержание документа  для каждого слово w в документ: emit (w, 1)функция уменьшать(Строковое слово, Iterator partialCounts): // слово: слово  // partialCounts: список агрегированных частичных счетчиков  сумма = 0 для каждого ПК в partialCounts: sum + = pc emit (слово, сумма)

Здесь каждый документ разбит на слова, и каждое слово подсчитывается карта функция, используя слово в качестве ключа результата. Платформа объединяет все пары с одним и тем же ключом и передает их одному и тому же вызову уменьшать. Таким образом, этой функции просто нужно просуммировать все входные значения, чтобы найти общее количество появлений этого слова.

В качестве другого примера представьте, что для базы данных, содержащей 1,1 миллиарда человек, нужно вычислить среднее количество социальных контактов, которые имеет человек в зависимости от возраста. В SQL, такой запрос можно выразить как:

  ВЫБРАТЬ возраст, AVG(контакты)    ИЗ Социальное.человекГРУППА К возрастПОРЯДОК К возраст

Используя MapReduce, K1 ключевые значения могут быть целыми числами от 1 до 1100, каждое из которых представляет пакет из 1 миллиона записей, K2 ключевым значением может быть возраст человека в годах, и это вычисление может быть выполнено с помощью следующих функций:

функция карта является    Вход: целое число K1 от 1 до 1100, что представляет собой пакет из 1 миллиона записей соц.персоналов. для каждого запись соц.персона в партии K1 делать        позволять Y быть возрастом человека позволять N - количество контактов человека создать одну выходную запись (Д, (Н, 1)) повторениеконечная функцияфункция Уменьшать является    Вход: возраст (в годах) Y для каждого входная запись (Y, (N, C)) делать        Накопить в S сумму N * C Накопить в Cновый сумма C повторение    позволять A be S / Cновый    создать одну выходную запись (Y, (A, Cновый))конечная функция

Система MapReduce выстроит 1100 процессоров Map и предоставит каждому соответствующий 1 миллион входных записей. Шаг карты даст 1,1 миллиарда (Д, (Н, 1)) записи, с Y значений в диапазоне, скажем, от 8 до 103. Система MapReduce затем выстроит в ряд 96 процессоров Reduce, выполнив операцию перемешивания пар ключ / значение из-за того, что нам нужно среднее значение на возраст, и предоставит каждому свои миллионы соответствующих входные записи. Шаг Уменьшить приведет к значительно сокращенному набору всего из 96 выходных записей. (Y, A), который будет помещен в файл окончательного результата, отсортированный по Y.

Информация о количестве в записи важна, если обработка сокращается более одного раза. Если бы мы не добавляли количество записей, вычисленное среднее значение было бы неверным, например:

- вывод карты №1: возраст, количество контактов10, 910, 910, 9
- вывод карты # 2: возраст, количество контактов10, 910, 9
- вывод карты # 3: возраст, количество контактов10, 10

Если мы уменьшим файлы #1 и #2, у нас будет новый файл со средним числом контактов 9 для 10-летнего человека ((9 + 9 + 9 + 9 + 9) / 5):

- уменьшить шаг №1: возраст, среднее количество контактов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 МБ), и фреймворк назначает одно разбиение каждому карта функция. В читатель ввода читает данные из стабильного хранилища (обычно распределенная файловая система ) и генерирует пары ключ / значение.

Обычный пример будет читать каталог, полный текстовых файлов, и возвращать каждую строку как запись.

Функция карты

В карта Функция принимает серию пар ключ / значение, обрабатывает каждую и генерирует ноль или более выходных пар ключ / значение. Типы ввода и вывода карты могут отличаться (и часто отличаются) друг от друга.

Если приложение производит подсчет слов, функция карты разбивает строку на слова и выводит пару ключ / значение для каждого слова. Каждая выходная пара будет содержать слово в качестве ключа и количество экземпляров этого слова в строке в качестве значения.

Функция разделения

Каждый карта вывод функции привязан к конкретному редуктор по заявке раздел функция для шардинг целей. В раздел функция получает ключ и количество редукторов и возвращает индекс желаемого редуктор.

Типичное значение по умолчанию - хэш ключ и используйте хеш-значение по модулю количество редукторы. Важно выбрать функцию секционирования, которая дает приблизительно равномерное распределение данных на сегмент для Балансировка нагрузки В противном случае операция MapReduce может быть приостановлена ​​в ожидании завершения медленных редукторов (т. е. редукторы назначили более крупные доли неравномерно разделенных данных).

Между этапами отображения и сокращения данные перетасованный (параллельная сортировка / обмен между узлами), чтобы переместить данные из узла карты, который их создал, в шард, в котором они будут сокращены. Перемешивание иногда может занимать больше времени, чем время вычислений, в зависимости от пропускной способности сети, скорости ЦП, производимых данных и времени, затрачиваемого на отображение и сокращение вычислений.

Функция сравнения

Вход для каждого Уменьшать вытаскивается из машины, где карта запущен и отсортирован с помощью приложения сравнение функция.

Функция уменьшения

Фреймворк вызывает приложение Уменьшать функция один раз для каждого уникального ключа в отсортированном порядке. В Уменьшать может перебирать значения, связанные с этим ключом, и давать ноль или более выходных данных.

В примере с подсчетом слов Уменьшать функция принимает входные значения, суммирует их и генерирует единственный выход слова и окончательной суммы.

Выходной писатель

В Выходной писатель записывает вывод Уменьшать в стабильное хранилище.

Соображения производительности

Работа программ MapReduce не гарантируется. Основным преимуществом этой модели программирования является использование оптимизированной операции перемешивания платформы и необходимость только писать карта и Уменьшать части программы. Однако на практике автор программы MapReduce должен принимать во внимание этап перемешивания; в частности, функция секционирования и объем данных, записанных карта функция может иметь большое влияние на производительность и масштабируемость. Дополнительные модули, такие как Комбайнер Функция может помочь уменьшить объем данных, записываемых на диск и передаваемых по сети. Приложения MapReduce могут достигать сублинейного ускорения при определенных обстоятельствах.[18]

При разработке алгоритма MapReduce автору нужно выбрать хороший компромисс.[11] между вычислениями и коммуникационными затратами. Стоимость связи часто преобладает над стоимостью вычислений,[11][18] и многие реализации MapReduce предназначены для записи всех сообщений в распределенное хранилище для восстановления после сбоев.

При настройке производительности MapReduce необходимо учитывать сложность сопоставления, перемешивания, сортировки (группировки по ключу) и сокращения. Объем данных, производимых модулями сопоставления, является ключевым параметром, который перемещает основную часть вычислительных затрат между сопоставлением и сокращением. Редукция включает в себя сортировку (группировку ключей), имеющую нелинейную сложность. Следовательно, небольшие размеры разделов сокращают время сортировки, но есть компромисс, поскольку наличие большого количества редукторов может быть непрактичным. Влияние размера разделенного блока незначительно (если он не выбран особенно плохо, скажем <1 МБ). Выигрыш от некоторых картографов, читающих нагрузку с локальных дисков, в среднем незначительный.[19]

Для процессов, которые завершаются быстро и где данные помещаются в основную память одного компьютера или небольшого кластера, использование инфраструктуры MapReduce обычно неэффективно. Поскольку эти структуры предназначены для восстановления после потери целых узлов во время вычислений, они записывают промежуточные результаты в распределенное хранилище. Это восстановление после сбоя является дорогостоящим и окупается только в том случае, если в вычислениях участвует много компьютеров и выполняется длительное время выполнения вычислений. Задачу, которая завершается за секунды, можно просто перезапустить в случае ошибки, и вероятность отказа хотя бы одной машины быстро растет с увеличением размера кластера. При таких проблемах реализации, сохраняющие все данные в памяти и просто перезапускающие вычисления при сбоях узлов или - когда данные достаточно малы - нераспределенные решения часто оказываются быстрее, чем система MapReduce.

Распространение и надежность

MapReduce обеспечивает надежность, распределяя ряд операций с набором данных для каждого узла в сети. Ожидается, что каждый узел будет периодически отчитываться о выполненной работе и обновлениях статуса. Если узел молчит дольше этого интервала, главный узел (аналогичный главному серверу в Файловая система Google ) записывает узел как мертвый и отправляет назначенную ему работу другим узлам. Использование отдельных операций атомный операции для именования выходных файлов в качестве проверки, чтобы убедиться, что не работают параллельные конфликтующие потоки. Когда файлы переименовываются, их можно также скопировать под другое имя в дополнение к имени задачи (с учетом побочные эффекты ).

Операции сокращения работают примерно так же. Из-за своих худших свойств в отношении параллельных операций главный узел пытается запланировать операции сокращения на том же узле или в той же стойке, что и узел, содержащий обрабатываемые данные. Это свойство желательно, поскольку оно сохраняет полосу пропускания в магистральной сети центра обработки данных.

Реализации не обязательно отличаются высокой надежностью. Например, в старых версиях Hadoop то Имя Узел был единая точка отказа для распределенной файловой системы. Более поздние версии Hadoop обладают высокой доступностью с активным / пассивным переключением при отказе для «NameNode».

Использует

MapReduce полезен в широком спектре приложений, включая распределенный поиск на основе шаблонов, распределенную сортировку, обращение веб-ссылок и графов, разложение по сингулярным значениям,[20] статистика журнала веб-доступа, инвертированный индекс строительство, кластеризация документов, машинное обучение,[21] и статистический машинный перевод. Более того, модель MapReduce была адаптирована к нескольким вычислительным средам, таким как многоядерные и многоядерные системы,[22][23][24] настольные сетки,[25]мультикластер,[26] волонтерские вычислительные среды,[27] динамические облачные среды,[28] мобильные среды,[29] и высокопроизводительные вычислительные среды.[30]

В Google MapReduce использовался для полной регенерации индекса Google Всемирная паутина. Он заменил старый для этого случая программы, которые обновляли индекс и выполняли различные анализы.[31] С тех пор разработка в Google перешла на такие технологии, как Percolator, FlumeJava.[32] и Мельничное колесо которые предлагают операции потоковой передачи и обновления вместо пакетной обработки, что позволяет интегрировать «живые» результаты поиска без восстановления всего индекса.[33]

Стабильные входы и выходы MapReduce обычно хранятся в распределенная файловая система. Переходные данные обычно хранятся на локальном диске и извлекаются удаленно редукторами.

Критика

Отсутствие новизны

Дэвид ДеВитт и Майкл Стоунбрейкер, компьютерные ученые, специализирующиеся на параллельные базы данных и архитектуры без общего доступа, критически оценивали спектр проблем, для решения которых может использоваться MapReduce.[34] Они назвали его интерфейс слишком низкоуровневым и задались вопросом, действительно ли он представляет смена парадигмы его сторонники утверждали, что это так.[35] Они оспорили утверждения сторонников MapReduce о новизне, сославшись на Терадата как пример предшествующий уровень техники которая существует уже более двух десятилетий. Они также сравнили программистов MapReduce с КОДАСИЛ программисты, отметив, что оба «пишут в язык низкого уровня выполнение низкоуровневых манипуляций с записями ".[35] Использование MapReduce входных файлов и отсутствие схема поддержка предотвращает повышение производительности, обеспечиваемое общими функциями системы баз данных, такими как B-деревья и хеш-разделение, хотя такие проекты, как Свинья (или PigLatin), Sawzall, Apache Hive,[36] HBase[37] и Большой стол[37][38] решают некоторые из этих проблем.

Грег Йоргенсен написал статью, отвергающую эти взгляды.[39] Йоргенсен утверждает, что весь анализ ДеВитта и Стоунбрейкера беспочвенен, поскольку MapReduce никогда не проектировался и не предназначался для использования в качестве базы данных.

Впоследствии ДеВитт и Стоунбрейкер опубликовали подробное эталонное исследование в 2009 году, в котором сравнивались характеристики Hadoop's MapReduce и СУБД подходит к нескольким конкретным проблемам.[40] Они пришли к выводу, что реляционные базы данных предлагают реальные преимущества для многих видов использования данных, особенно при сложной обработке или в тех случаях, когда данные используются в масштабах всего предприятия, но что MapReduce может быть проще для пользователей для решения простых или одноразовых задач обработки.

Парадигма программирования MapReduce также описана в Дэнни Хиллис дипломная работа 1985 г. [41] и широко использовался в то время для программирования Соединительная машина, у которого была специальная аппаратная поддержка для ускорения как карты, так и уменьшения.

Google получил патент на MapReduce.[42] Однако были заявления о том, что этот патент нельзя было выдавать, потому что MapReduce слишком похож на существующие продукты. Например, функции сопоставления и сокращения могут быть очень легко реализованы в Oracle PL / SQL язык, ориентированный на базы данных[43] или прозрачно поддерживается разработчиками в архитектурах распределенных баз данных, таких как Clusterpoint База данных XML[44] или же MongoDB База данных NoSQL.[45]

Фреймворк ограниченного программирования

Задачи MapReduce должны быть написаны как программы с ациклическим потоком данных, то есть преобразователь без сохранения состояния, за которым следует редуктор без состояния, которые выполняются планировщиком пакетных заданий. Эта парадигма затрудняет повторные запросы наборов данных и накладывает ограничения, которые ощущаются в таких областях, как машинное обучение, где итерационные алгоритмы, которые пересматривают один рабочий набор несколько раз - это норма.[46]

Смотрите также

Реализации MapReduce

Рекомендации

  1. ^ «Учебное пособие по MapReduce». Apache Hadoop. Получено 3 июля 2019.
  2. ^ «Google освещает внутреннюю работу центра обработки данных». cnet.com. 30 мая 2008 г.
  3. ^ «MapReduce: упрощенная обработка данных в больших кластерах» (PDF). googleusercontent.com.
  4. ^ Уикхэм, Хэдли (2011). «Стратегия разделения-применения-объединения для анализа данных». Журнал статистического программного обеспечения. 40: 1–29. Дои:10.18637 / jss.v040.i01.
  5. ^ «Наша абстракция вдохновлена ​​картой и сокращает примитивы, присутствующие в Лиспе и многих других функциональных языках». -«MapReduce: упрощенная обработка данных в больших кластерах» Джеффри Дин и Санджай Гемават; из Google Research
  6. ^ Лэммель, Р. (2008). "Карта Google Уменьшать модель программирования - новый взгляд ". Наука компьютерного программирования. 70: 1–30. Дои:10.1016 / j.scico.2007.07.001.
  7. ^ http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/mpi2-report.htm Стандарт MPI 2
  8. ^ "MPI Reduce and Allreduce · Учебное пособие по MPI". mpitutorial.com.
  9. ^ «Выполнение параллельного ранжирования с помощью MPI · MPI Tutorial». mpitutorial.com.
  10. ^ «MongoDB: ужасная производительность MapReduce». Переполнение стека. 16 октября 2010 г. Реализация MapReduce в MongoDB явно не имеет ничего общего с уменьшением карты. Потому что из всего, что я читал, он однопоточный, в то время как map-reduce предназначена для высокопараллельного использования в кластере. ... MongoDB MapReduce является однопоточным на одном сервере ...
  11. ^ а б c Ульман, Дж. Д. (2012). «Разработка хороших алгоритмов MapReduce». XRDS: Crossroads, журнал ACM для студентов. 19: 30. Дои:10.1145/2331042.2331053.
  12. ^ Свердлик, Евгений (25.06.2014). «Google отказывается от MapReduce в пользу новой системы гипермасштабной аналитики». Знание центра обработки данных. Получено 2015-10-25. «Мы больше не используем MapReduce» [Урс Хёльзле, старший вице-президент по технической инфраструктуре Google]
  13. ^ Харрис, Деррик (27 марта 2014 г.). «Apache Mahout, оригинальный проект машинного обучения Hadoop, переходит на MapReduce». Гигаом. Получено 2015-09-24. Apache Mahout [...] присоединяется к исходу из MapReduce.
  14. ^ Чайковский, Гжегож; Мариан Дворски; Джерри Чжао; Майкл Конли. "Сортировка петабайт с помощью MapReduce - следующий эпизод". Получено 7 апреля 2014.
  15. ^ https://hadoop.apache.org/docs/r1.2.1/mapred_tutorial.html#Inputs+and+Outputs
  16. ^ https://github.com/apache/hadoop-mapreduce/blob/307cb5b316e10defdbbc228d8cdcdb627191ea15/src/java/org/apache/hadoop/mapreduce/Reducer.java#L148
  17. ^ "Пример: подсчет вхождений слов". Google Research. Получено 18 сентября, 2013.
  18. ^ а б Сенгер, Гермес; Хиль-Коста, Вероника; Арантес, Лучиана; Marcondes, Cesar A.C .; Марин, Маурисио; Sato, Liria M .; да Силва, Фабрисио А. (01.01.2015). «Анализ стоимости и масштабируемости BSP для операций MapReduce». Параллелизм и вычисления: практика и опыт. 28 (8): 2503–2527. Дои:10.1002 / cpe.3628. ISSN  1532-0634.
  19. ^ Берлинская, Иоанна; Дроздовский, Мацей (01.12.2010). «Планирование делимых вычислений MapReduce». Журнал параллельных и распределенных вычислений. 71 (3): 450–459. Дои:10.1016 / j.jpdc.2010.12.004.
  20. ^ Босах Заде, Реза; Карлссон, Гуннар (2013). «Квадрат матрицы, не зависящий от размеров с использованием MapReduce» (PDF). arXiv:1304.1467. Bibcode:2013arXiv1304.1467B. Получено 12 июля 2014. Цитировать журнал требует | журнал = (помощь)
  21. ^ Ng, Andrew Y .; Брадски, Гэри; Чу, Чэн-Тао; Олюкотун, Кунле; Ким, Сан Гюн; Линь И-Ань; Ю, ЮаньЮань (2006). «Map-Reduce для машинного обучения на многоядерных процессорах». НИПС 2006.
  22. ^ Рейнджер, C .; Raghuraman, R .; Пенметса, А .; Bradski, G .; Козыракис, К. (2007). «Оценка MapReduce для многоядерных и многопроцессорных систем». 2007 13-й Международный симпозиум IEEE по архитектуре высокопроизводительных компьютеров. п. 13. CiteSeerX  10.1.1.220.8210. Дои:10.1109 / HPCA.2007.346181. ISBN  978-1-4244-0804-7.
  23. ^ Он, Б .; Fang, W .; Luo, Q .; Govindaraju, N.K .; Ван, Т. (2008). «Марс: фреймворк MapReduce на графических процессорах» (PDF). Материалы 17-й международной конференции по параллельным архитектурам и методам компиляции - PACT '08. п. 260. Дои:10.1145/1454115.1454152. ISBN  9781605582825.
  24. ^ Chen, R .; Chen, H .; Занг, Б. (2010). «Tiled-MapReduce: оптимизация использования ресурсов приложений с параллельными данными в многоядерных системах с мозаичным использованием». Труды 19-й международной конференции по параллельным архитектурам и методам компиляции - PACT '10. п. 523. Дои:10.1145/1854273.1854337. ISBN  9781450301787.
  25. ^ Тан, Б .; Moca, M .; Chevalier, S .; Он, H .; Федак, Г. (2010). «На пути к MapReduce для настольных грид-вычислений» (PDF). 2010 Международная конференция по P2P, параллельным, сетевым, облачным и интернет-вычислениям. п. 193. CiteSeerX  10.1.1.671.2763. Дои:10.1109 / 3PGCIC.2010.33. ISBN  978-1-4244-8538-3.
  26. ^ Luo, Y .; Guo, Z .; Sun, Y .; Plale, B .; Qiu, J .; Ли, В. (2011). «Иерархическая структура для междоменного выполнения MapReduce» (PDF). Материалы второго международного семинара по новым вычислительным методам для наук о жизни (ECMLS '11). CiteSeerX  10.1.1.364.9898. Дои:10.1145/1996023.1996026. ISBN  978-1-4503-0702-4.
  27. ^ Lin, H .; Максимум.; Archuleta, J .; Feng, W. C .; Gardner, M .; Чжан, З. (2010). "MOON: MapReduce On Opportunistic eNvironments" (PDF). Материалы 19-го Международного симпозиума ACM по высокопроизводительным распределенным вычислениям - HPDC '10. п. 95. Дои:10.1145/1851476.1851489. ISBN  9781605589428.
  28. ^ Marozzo, F .; Талия, Д .; Трунфио, П. (2012). «P2P-MapReduce: параллельная обработка данных в динамических облачных средах» (PDF). Журнал компьютерных и системных наук. 78 (5): 1382–1402. Дои:10.1016 / j.jcss.2011.12.021. Архивировано из оригинал (PDF) на 2016-03-03. Получено 2015-09-04.
  29. ^ Dou, A .; Калогераки, В .; Gunopulos, D .; Mielikainen, T .; Туулос, В. Х. (2010). «Misco: платформа MapReduce для мобильных систем». Материалы 3-й Международной конференции по ресурсным технологиям, связанным с вспомогательными средами - PETRA '10. п. 1. Дои:10.1145/1839294.1839332. ISBN  9781450300711.
  30. ^ Ван, Яньдун; Голдстоун, Робин; Ю, Вэйкуань; Ван, Тэн (май 2014 г.). «Характеристика и оптимизация резидентного MapReduce в системах HPC». 28-й Международный симпозиум по параллельной и распределенной обработке, 2014 г., IEEE. IEEE. С. 799–808. Дои:10.1109 / IPDPS.2014.87. ISBN  978-1-4799-3800-1.
  31. ^ "Как работает Google". baselinemag.com. По состоянию на октябрь, согласно презентации Дина, Google выполнял около 3000 вычислительных задач в день через MapReduce, что составляет тысячи машинно-дней. Среди прочего, эти пакетные процедуры анализируют последние веб-страницы и обновляют индексы Google.
  32. ^ Чемберс, Крейг; Ранивала, Ашиш; Перри, Фрэнсис; Адамс, Стивен; Генри, Роберт Р .; Брэдшоу, Роберт; Вайценбаум, Натан (1 января 2010 г.). FlumeJava: простые и эффективные конвейеры с параллельными данными (PDF). Материалы 31-й конференции ACM SIGPLAN по проектированию и реализации языков программирования. С. 363–375. Дои:10.1145/1806596.1806638. ISBN  9781450300193. Архивировано из оригинал (PDF) 23 сентября 2016 г.. Получено 4 августа 2016.
  33. ^ Пэн Д. и Дабек Ф. (октябрь 2010 г.). Масштабная инкрементная обработка с использованием распределенных транзакций и уведомлений. В OSDI (Том 10, стр. 1-15).
  34. ^ "Эксперты по базам данных прыгают через MapReduce Shark".
  35. ^ а б Дэвид ДеВитт; Майкл Стоунбрейкер. «MapReduce: большой шаг назад». craig-henderson.blogspot.com. Получено 2008-08-27.
  36. ^ «Apache Hive - Индекс - Apache Software Foundation».
  37. ^ а б «HBase - HBase Home - Фонд программного обеспечения Apache».
  38. ^ «Bigtable: распределенная система хранения структурированных данных» (PDF).
  39. ^ Грег Йоргенсен. "Эксперты по реляционным базам данных прыгают через акулу MapReduce". Typicalprogrammer.com. Получено 2009-11-11.
  40. ^ Павел, Андрей; Полсон, Эрик; Расин, Александр; Abadi, Daniel J .; DeWitt, Deavid J .; Мэдден, Сэмюэл; Стоунбрейкер, Майкл. «Сравнение подходов к анализу крупномасштабных данных». Брауновский университет. Получено 2010-01-11.
  41. ^ Хиллис, В. Дэнни (1986). Машина связи. MIT Press. ISBN  0262081571.
  42. ^ «Патент США: 7650331 - Система и метод для эффективной крупномасштабной обработки данных». uspto.gov.
  43. ^ Курт Монаш. "Еще одна патентная чепуха - Google MapReduce". dbms2.com. Получено 2010-03-07.
  44. ^ «База данных Clusterpoint XML». clusterpoint.com. Архивировано из оригинал на 2014-03-28.
  45. ^ «База данных MongoDB NoSQL». 10gen.com.
  46. ^ Захария, Матей; Чоудхури, Мошараф; Франклин, Майкл; Шенкер, Скотт; Стойка, Ион (июнь 2010 г.). Spark: кластерные вычисления с рабочими наборами. HotCloud 2010.

внешняя ссылка