MapReduce является моделью программирования и связанной с ним реализацией для обработки и генерации больших данных наборов с параллельно , распределенным алгоритмом на кластере . [1] [2] [3]
Программа MapReduce состоит из процедуры сопоставления , которая выполняет фильтрацию и сортировку (например, сортирует студентов по имени в очереди, одна очередь для каждого имени), и метода сокращения , который выполняет сводную операцию (например, подсчет количества студентов в каждой очереди, с указанием частотности имен). «Система MapReduce» (также называемая «инфраструктурой» или «структурой») управляет обработкой путем упорядочивания распределенных серверов, параллельного выполнения различных задач, управления всеми коммуникациями и передачей данных между различными частями системы и обеспечения избыточности. и отказоустойчивость .
Модель представляет собой специализацию стратегии разделения-применения-объединения для анализа данных. [4] Он основан на функциях map и reduce, обычно используемых в функциональном программировании , [5] хотя их назначение в среде MapReduce отличается от их исходных форм. [6] Основные вклады рамок MapReduce не фактические карты и уменьшить функции (которые, например, напоминающей 1995 Message Passing Interface стандарта [7] уменьшить [8] и Разброс [9] операция), но масштабируемость и отказоустойчивость, достигаемая для множества приложений за счет оптимизации механизма выполнения [ необходима цитата ] . Таким образом, однопоточная реализация MapReduce обычно не быстрее традиционной (не-MapReduce) реализации; любой выигрыш обычно наблюдается только при многопоточной реализации на многопроцессорном оборудовании. [10] Использование этой модели выгодно только тогда, когда в игру вступают оптимизированная операция распределенного перемешивания (которая снижает стоимость сетевой связи) и функции отказоустойчивости инфраструктуры MapReduce. Оптимизация стоимости связи важна для хорошего алгоритма MapReduce. [11]
Библиотеки MapReduce написаны на многих языках программирования с разными уровнями оптимизации. Популярная реализация с открытым исходным кодом , которая поддерживает распределенное перемешивание, является частью Apache Hadoop . Название MapReduce первоначально относилось к частной технологии Google , но с тех пор было обобщено . К 2014 году Google больше не использовал MapReduce в качестве основной модели обработки больших данных [12], а разработка Apache Mahout перешла на более функциональные и менее ориентированные на диск механизмы, которые включали полную карту и ограничивали возможности. [13]
Обзор
MapReduce - это платформа для обработки распараллеливаемых задач в больших наборах данных с использованием большого количества компьютеров (узлов), вместе называемых кластером (если все узлы находятся в одной локальной сети и используют подобное оборудование) или сеткой (если узлы совместно используются географически и административно распределенными системами и используют более разнородное оборудование). Обработка может происходить с данными, хранящимися либо в файловой системе (неструктурированной), либо в базе данных (структурированной). MapReduce может использовать преимущества локальности данных, обрабатывая их рядом с местом, где они хранятся, чтобы минимизировать накладные расходы на связь.
Фреймворк (или система) MapReduce обычно состоит из трех операций (или шагов):
- Карта: каждый рабочий узел применяет
map
функцию к локальным данным и записывает вывод во временное хранилище. Главный узел обеспечивает обработку только одной копии избыточных входных данных. - Перемешать: рабочие узлы перераспределяют данные на основе выходных ключей (созданных
map
функцией), так что все данные, принадлежащие одному ключу, находятся на одном рабочем узле. - Уменьшение: рабочие узлы теперь обрабатывают каждую группу выходных данных для каждого ключа параллельно.
MapReduce позволяет выполнять распределенную обработку карты и операции сокращения. Карты могут выполняться параллельно, при условии, что каждая операция сопоставления не зависит от других; на практике это ограничено количеством независимых источников данных и / или количеством процессоров рядом с каждым источником. Точно так же набор «редукторов» может выполнять фазу редукции, при условии, что все выходные данные операции сопоставления, которые используют один и тот же ключ, представлены одному и тому же редуктору в одно и то же время, или что функция редукции является ассоциативной . Хотя этот процесс часто кажется неэффективным по сравнению с более последовательными алгоритмами (поскольку необходимо запускать несколько экземпляров процесса сокращения), MapReduce может применяться к значительно большим наборам данных, чем может обрабатывать один "стандартный" сервер - большая ферма серверов может использовать MapReduce позволяет отсортировать петабайт данных всего за несколько часов. [14] Параллелизм также предлагает некоторую возможность восстановления после частичного отказа серверов или хранилища во время операции: если один преобразователь или редуктор выйдет из строя, работа может быть перепланирована - при условии, что входные данные все еще доступны.
Другой способ взглянуть на MapReduce - это 5-этапное параллельное и распределенное вычисление:
- Подготовьте ввод Map () - «система MapReduce» назначает процессоры Map, назначает ключ ввода K1, с которым будет работать каждый процессор, и предоставляет этому процессору все входные данные, связанные с этим ключом.
- Запустите предоставленный пользователем код Map () - Map () запускается ровно один раз для каждого ключа K1 , генерируя выходные данные, организованные по ключу K2 .
- «Перемешайте» вывод Map процессорам Reduce - система MapReduce назначает процессоры Reduce, назначает ключ K2 , с которым должен работать каждый процессор, и предоставляет этому процессору все сгенерированные Map данные, связанные с этим ключом.
- Запустите предоставленный пользователем код Reduce () - Reduce () запускается ровно один раз для каждого ключа K2, созданного на этапе Map.
- Произвести окончательный результат - система MapReduce собирает все выходные данные Reduce и сортирует их по K2 для получения окончательного результата.
Эти пять шагов можно логически представить как выполняющиеся в последовательности - каждый шаг начинается только после завершения предыдущего шага - хотя на практике их можно чередовать, если это не влияет на конечный результат.
Во многих ситуациях входные данные могли уже быть распределены ( «сегментированы» ) между множеством разных серверов, и в этом случае шаг 1 иногда можно было значительно упростить, назначив серверы карт, которые будут обрабатывать локально присутствующие входные данные. Точно так же шаг 3 иногда можно ускорить, назначив процессоры Reduce, которые максимально приближены к сгенерированным Map данным, которые им необходимо обработать.
Логический взгляд
Функции Map и Reduce в MapReduce определены относительно данных, структурированных парами (ключ, значение). Карта принимает одну пару данных с типом в одном домене данных и возвращает список пар в другом домене:
Map(k1,v1)
→ list(k2,v2)
Функция Map применяется параллельно к каждой паре (с ключом k1
) во входном наборе данных. Это создает список пар (с ключом k2
) для каждого вызова. После этого платформа MapReduce собирает все пары с одним и тем же ключом ( k2
) из всех списков и группирует их вместе, создавая одну группу для каждого ключа.
Затем функция Reduce применяется параллельно к каждой группе, которая, в свою очередь, создает набор значений в том же домене:
Reduce(k2, list (v2))
→ list((k3, v3))
[15]
Каждый вызов Reduce обычно производит либо одну пару значений ключа, либо пустой возврат, хотя один вызов может возвращать более одной пары значений ключа. Возвраты всех вызовов собираются в виде списка желаемых результатов.
Таким образом, инфраструктура MapReduce преобразует список пар (ключ, значение) в другой список пар (ключ, значение). [16] Это поведение отличается от типичной комбинации функционального программирования map и reduce, которая принимает список произвольных значений и возвращает одно единственное значение, которое объединяет все значения, возвращаемые map.
Это необходимо , но не достаточно , чтобы иметь реализации карты и уменьшить абстракции для реализации MapReduce. Для распределенных реализаций MapReduce требуются средства соединения процессов, выполняющих фазы Map и Reduce. Это может быть распределенная файловая система . Возможны и другие варианты, такие как прямая потоковая передача от сопоставителей к редукторам или для процессоров сопоставления, чтобы передать свои результаты редукторам, которые их запрашивают.
Примеры
Канонический пример MapReduce подсчитывает появление каждого слова в наборе документов: [17]
function map (String name, String document): // name: document name // document: содержимое документа для каждого слова w в документе: испускать (ш, 1)function reduce (String word, Iterator partialCounts): // word: a word // partialCounts: список агрегированных частичных подсчетов сумма = 0 для каждого ПК в partialCounts: сумма + = шт испускать (слово, сумма)
Здесь каждый документ разбивается на слова, и каждое слово подсчитывается функцией карты , используя слово в качестве ключа результата. Фреймворк объединяет все пары с одним и тем же ключом и передает их одному и тому же вызову для сокращения . Таким образом, этой функции просто нужно просуммировать все входные значения, чтобы найти общее количество появлений этого слова.
В качестве другого примера представьте, что для базы данных, содержащей 1,1 миллиарда человек, нужно вычислить среднее количество социальных контактов, которые имеет человек в зависимости от возраста. В SQL такой запрос можно выразить как:
ВЫБЕРИТЕ возраст , СРЕДНЕЕ ( контакты ) ИЗ соц . человек ГРУППА ПО возрасту ПОКАЗАТЬ ПО возрасту
Используя MapReduce, значения ключа K1 могут быть целыми числами от 1 до 1100, каждое из которых представляет пакет из 1 миллиона записей, значение ключа K2 может быть возрастом человека в годах, и это вычисление может быть выполнено с помощью следующих функций:
Функция Карта является входом: целым числом K1 от 1 до 1100, представляющий партию 1 млн social.person записей для каждой записи social.person в K1 партии делать пусть Y будет возраст человека пусть N будет количеством контактов у человека продуктов одна выходная запись (Y, (N, 1)) функция конца повторенияФункция Уменьшения является ввод: возраст (в годах) Y для каждой входной записи (Y, (N, С)) делает Накопите в S сумму N * C Накопите в C new сумму повторений C, пусть A будет S / C new, создайте одну выходную запись (Y, (A, C new )) end function
Система MapReduce выстроит 1100 процессоров Map и предоставит каждому соответствующий 1 миллион входных записей. На этапе Map будет создано 1,1 миллиарда (Y, (N, 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 МБ) и каркасные присваивает один сплит каждой карту функцию. Устройство чтения ввода считывает данные из стабильного хранилища (обычно распределенной файловой системы ) и генерирует пары ключ / значение.
Обычный пример будет читать каталог, полный текстовых файлов, и возвращать каждую строку как запись.
Функция карты
Функция Map принимает серию пар ключ / значение, обрабатывает каждую и генерирует ноль или более выходных пар ключ / значение. Типы ввода и вывода карты могут отличаться (и часто отличаются) друг от друга.
Если приложение выполняет подсчет слов, функция карты разбивает строку на слова и выводит пару ключ / значение для каждого слова. Каждая выходная пара будет содержать слово в качестве ключа и количество экземпляров этого слова в строке в качестве значения.
Функция разделения
Каждая карта выходная функции выделяются для конкретного редуктора с помощью приложения разбиения функции для шардинге целей. Функция секционирования получает ключ и количество редукторов и возвращает индекс желаемого редуктора .
Типичное значение по умолчанию - хэширование ключа и использование значения хеш-функции по модулю количества редукторов . Важно выбрать функцию секционирования, которая дает приблизительно равномерное распределение данных по сегменту для целей балансировки нагрузки , в противном случае операция MapReduce может быть приостановлена в ожидании завершения медленных редукторов (т. Е. Редукторы назначили большие доли не- равномерно разделенные данные).
Между этапами сопоставления и сокращения данные перемешиваются (параллельная сортировка / обмен между узлами), чтобы переместить данные из узла карты, который их создал, в сегмент, в котором они будут сокращены. Перемешивание иногда может занимать больше времени, чем время вычислений, в зависимости от пропускной способности сети, скорости ЦП, производимых данных и времени, затрачиваемого на отображение и сокращение вычислений.
Функция сравнения
Входные данные для каждого Reduce берутся с компьютера, на котором выполнялась карта, и сортируются с помощью функции сравнения приложения .
Функция уменьшения
Платформа вызывает функцию Reduce приложения один раз для каждого уникального ключа в отсортированном порядке. Уменьшение может перебирать значения, которые связаны с этим ключом и производить ноль или более выходов.
В примере с подсчетом слов функция Reduce принимает входные значения, суммирует их и генерирует единственный выходной сигнал слова и окончательной суммы.
Выходной писатель
Устройство записи вывода записывает вывод Reduce в стабильное хранилище.
Соображения производительности
Работа программ MapReduce не гарантируется. Основное преимущество этой модели программирования заключается в использовании оптимизированной операции перемешивания платформы и необходимости писать только части программы Map и Reduce . Однако на практике автор программы MapReduce должен учитывать этап перемешивания; в частности, функция секционирования и объем данных, записываемых функцией Map, могут иметь большое влияние на производительность и масштабируемость. Дополнительные модули, такие как функция Combiner, могут помочь уменьшить объем данных, записываемых на диск и передаваемых по сети. Приложения MapReduce могут достигать сублинейного ускорения при определенных обстоятельствах. [18]
При разработке алгоритма MapReduce автору необходимо выбрать хороший компромисс [11] между затратами на вычисления и коммуникацию. Стоимость связи часто преобладает над стоимостью вычислений [11] [18], и многие реализации MapReduce предназначены для записи всего обмена данными в распределенное хранилище для восстановления после сбоя.
При настройке производительности MapReduce необходимо учитывать сложность сопоставления, перемешивания, сортировки (группировки по ключу) и сокращения. Объем данных, производимых модулями сопоставления, является ключевым параметром, который перемещает основную часть вычислительных затрат между сопоставлением и сокращением. Редукция включает в себя сортировку (группировку ключей), имеющую нелинейную сложность. Следовательно, небольшие размеры разделов сокращают время сортировки, но есть компромисс, потому что наличие большого количества редукторов может быть непрактичным. Влияние размера разделенного блока незначительно (если он не выбран особенно плохо, скажем <1 МБ). Выигрыш от некоторых картографов, читающих нагрузку с локальных дисков, в среднем незначительный. [19]
Для процессов, которые завершаются быстро и где данные помещаются в основную память отдельной машины или небольшого кластера, использование инфраструктуры MapReduce обычно неэффективно. Поскольку эти структуры предназначены для восстановления после потери целых узлов во время вычислений, они записывают промежуточные результаты в распределенное хранилище. Это восстановление после сбоя является дорогостоящим и окупается только тогда, когда в вычислениях задействовано много компьютеров и выполняется длительное время выполнения вычислений. Задачу, которая завершается за секунды, можно просто перезапустить в случае ошибки, и вероятность отказа хотя бы одной машины быстро растет с увеличением размера кластера. При таких проблемах реализации, сохраняющие все данные в памяти и просто перезапускающие вычисления при сбоях узлов или - когда данные достаточно малы - нераспределенные решения часто оказываются быстрее, чем система MapReduce.
Распространение и надежность
MapReduce обеспечивает надежность, распределяя ряд операций с набором данных для каждого узла в сети. Ожидается, что каждый узел будет периодически отчитываться с завершенной работой и обновлениями статуса. Если узел не работает дольше этого интервала, главный узел (аналогичный главному серверу в файловой системе Google ) записывает узел как неработающий и отправляет назначенную ему работу другим узлам. Отдельные операции используют атомарные операции для именования выходных файлов в качестве проверки, чтобы убедиться, что не запущены параллельные конфликтующие потоки. Когда файлы переименовываются, их можно также скопировать под другое имя в дополнение к имени задачи (с учетом побочных эффектов ).
Операции сокращения работают примерно так же. Из-за своих худших свойств в отношении параллельных операций главный узел пытается запланировать операции сокращения на том же узле или в той же стойке, что и узел, содержащий обрабатываемые данные. Это свойство желательно, поскольку оно сохраняет полосу пропускания в магистральной сети центра обработки данных.
Реализации не обязательно отличаются высокой надежностью. Например, в старых версиях Hadoop NameNode была единственной точкой отказа для распределенной файловой системы. Более поздние версии Hadoop обладают высокой доступностью с активным / пассивным переключением при отказе для «NameNode».
Использует
MapReduce полезен в широком спектре приложений, включая распределенный поиск на основе шаблонов, распределенную сортировку, обращение веб-ссылок и графов, разложение по сингулярным значениям, [20] статистику журнала веб-доступа, построение инвертированного индекса , кластеризацию документов , машинное обучение , [21] ] и статистический машинный перевод . Более того, модель MapReduce была адаптирована к нескольким вычислительным средам, таким как многоядерные и многоядерные системы, [22] [23] [24] настольные сети, [25] мульти-кластеры, [26] добровольные вычислительные среды, [27] ] динамические облачные среды [28] мобильные среды [29] и высокопроизводительные вычислительные среды. [30]
В Google MapReduce использовался для полной регенерации индекса всемирной паутины Google . Он заменил старые специальные программы, которые обновляли индекс и выполняли различные анализы. [31] С тех пор разработка в Google перешла к таким технологиям, как Percolator, FlumeJava [32] и MillWheel, которые предлагают операции потоковой передачи и обновления вместо пакетной обработки, что позволяет интегрировать «живые» результаты поиска без перестройки всего индекса. [33]
Стабильные входные и выходные данные MapReduce обычно хранятся в распределенной файловой системе . Переходные данные обычно хранятся на локальном диске и извлекаются удаленно редукторами.
Критика
Отсутствие новизны
Дэвид ДеВитт и Майкл Стоунбрейкер , компьютерные ученые, специализирующиеся на параллельных базах данных и архитектурах без совместного использования ресурсов , критически оценивают широкий спектр проблем, для решения которых может использоваться MapReduce. [34] Они назвали его интерфейс слишком низкоуровневым и задались вопросом, действительно ли он представляет собой сдвиг парадигмы, о котором заявляли его сторонники. [35] Они оспорили утверждения сторонников MapReduce о новизне, сославшись на Teradata в качестве примера предшествующего уровня техники , существующего более двух десятилетий. Они также сравнили программистов MapReduce с программистами CODASYL , отметив, что оба они «пишут на низкоуровневом языке, выполняя низкоуровневые манипуляции с записями». [35] Использование в MapReduce входных файлов и отсутствие поддержки схем не позволяет повысить производительность, обеспечиваемую общими функциями системы баз данных, такими как B-деревья и хеш-секционирование , хотя такие проекты, как Pig (или PigLatin) , Sawzall , Apache Hive , [36] HBase [37] и Bigtable [37] [38] решают некоторые из этих проблем.
Грег Йоргенсен написал статью, отвергающую эти взгляды. [39] Йоргенсен утверждает, что весь анализ ДеВитта и Стоунбрейкера беспочвенен, поскольку MapReduce никогда не разрабатывался и не предназначался для использования в качестве базы данных.
Впоследствии ДеВитт и Стоунбрейкер в 2009 году опубликовали подробное эталонное исследование, в котором сравнивается производительность подходов Hadoop MapReduce и СУБД по нескольким конкретным проблемам. [40] Они пришли к выводу, что реляционные базы данных предлагают реальные преимущества для многих видов использования данных, особенно при сложной обработке или в тех случаях, когда данные используются в масштабах всего предприятия, но что MapReduce может быть проще для пользователей для решения простых или одноразовых задач обработки. .
Парадигма программирования MapReduce также была описана в диссертации 1985 года Дэнни Хиллиса [41] и широко использовалась в то время для программирования машины соединений , которая имела специальную аппаратную поддержку для ускорения как отображения, так и сокращения.
В 2010 году Google получил патент на MapReduce. Патент, поданный в 2004 году, может охватывать использование MapReduce программным обеспечением с открытым исходным кодом, таким как Hadoop , CouchDB и другими. В Ars Technica редактор признал роль Google в популяризации концепции MapReduce, но поставил под сомнение, был ли патент действительным или новым. [42] [43] В 2013 году в рамках своего «Открытого обязательства по непринятию патентных заявлений (OPN)» Google пообещал использовать патент только в целях защиты. [44] [45] Срок действия патента истекает 23 декабря 2026 года. [46]
Фреймворк ограниченного программирования
Задачи MapReduce должны быть написаны как программы с ациклическим потоком данных, то есть преобразователь без сохранения состояния, за которым следует редуктор без состояния, которые выполняются планировщиком пакетных заданий. Эта парадигма затрудняет повторные запросы наборов данных и накладывает ограничения, которые ощущаются в таких областях, как машинное обучение , где итерационные алгоритмы, многократно пересматривающие один рабочий набор, являются нормой. [47]
Смотрите также
- Формализм Берда – Меертенса
Реализации MapReduce
- Apache CouchDB
- Apache Hadoop
- Infinispan
- Риак
Рекомендации
- ^ "Учебное пособие по MapReduce" . Apache Hadoop . Дата обращения 3 июля 2019 .
- ^ «Google освещает внутреннюю работу центра обработки данных» . cnet.com . 30 мая 2008 г.
- ^ «MapReduce: упрощенная обработка данных в больших кластерах» (PDF) . googleusercontent.com .
- ^ Уикхэм, Хэдли (2011). «Стратегия разделения-применения-объединения для анализа данных» . Журнал статистического программного обеспечения . 40 : 1–29. DOI : 10,18637 / jss.v040.i01 .
- ^ «Наша абстракция вдохновлена картой и сокращает примитивы, присутствующие в Лиспе и многих других функциональных языках». - «MapReduce: упрощенная обработка данных в больших кластерах» Джеффри Дина и Санджая Гемавата; из Google Research
- ^ Лэммель, Р. (2008). « Модель программирования Google Map Reduce - еще раз» . Наука компьютерного программирования . 70 : 1–30. DOI : 10.1016 / j.scico.2007.07.001 .
- ^ http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/mpi2-report.htm Стандарт MPI 2
- ^ «MPI Reduce и Allreduce · Учебное пособие по MPI» . mpitutorial.com .
- ^ «Выполнение параллельного ранжирования с помощью MPI · MPI Tutorial» . mpitutorial.com .
- ^ «MongoDB: ужасная производительность MapReduce» . Переполнение стека. 16 октября 2010 г.
Реализация MapReduce в MongoDB явно не имеет ничего общего с уменьшением карты. Потому что из всего, что я читал, он однопоточный, а map-reduce предназначен для высокопараллельного использования в кластере. ... MongoDB MapReduce является однопоточным на одном сервере ...
- ^ а б в Ульман, JD (2012). «Разработка хороших алгоритмов MapReduce» . XRDS: Crossroads, журнал ACM для студентов . 19 : 30. DOI : 10,1145 / 2331042,2331053 .
- ^ Свердлик, Евгений (25.06.2014). «Google отказывается от MapReduce в пользу новой системы гипермасштабной аналитики» . Знание центра обработки данных . Проверено 25 октября 2015 .
«Мы больше не используем MapReduce» [Урс Хёльзле, старший вице-президент по технической инфраструктуре Google]
- ^ Харрис, Деррик (27 марта 2014 г.). «Apache Mahout, оригинальный проект машинного обучения Hadoop, переходит на MapReduce» . Гигаом . Проверено 24 сентября 2015 .
Apache Mahout [...] присоединяется к исходу из MapReduce.
- ^ Чайковский, Гжегож; Мариан Дворски; Джерри Чжао; Майкл Конли. «Сортировка петабайт с помощью MapReduce - следующий эпизод» . Проверено 7 апреля 2014 года .
- ^ https://hadoop.apache.org/docs/r1.2.1/mapred_tutorial.html#Inputs+and+Outputs
- ^ https://github.com/apache/hadoop-mapreduce/blob/307cb5b316e10defdbbc228d8cdcdb627191ea15/src/java/org/apache/hadoop/mapreduce/Reducer.java#L148
- ^ «Пример: подсчет вхождений слов» . Google Research . Проверено 18 сентября 2013 года .
- ^ а б Сенгер, Гермес; Хиль-Коста, Вероника; Арантес, Лучиана; Marcondes, Cesar AC; Марин, Маурисио; Sato, Liria M .; да Силва, Фабрисио А.Б. (01.01.2015). «Анализ стоимости и масштабируемости BSP для операций MapReduce». Параллелизм и вычисления: практика и опыт . 28 (8): 2503–2527. DOI : 10.1002 / cpe.3628 . hdl : 10533/147670 . ISSN 1532-0634 .
- ^ Берлинская, Иоанна; Дроздовский, Мацей (01.12.2010). «Планирование делимых вычислений MapReduce». Журнал параллельных и распределенных вычислений . 71 (3): 450–459. DOI : 10.1016 / j.jpdc.2010.12.004 .
- ^ Босах Заде, Реза; Карлссон, Гуннар (2013). «Квадрат матрицы, не зависящий от размеров с использованием MapReduce» (PDF) . arXiv : 1304,1467 . Bibcode : 2013arXiv1304.1467B . Проверено 12 июля 2014 . Цитировать журнал требует
|journal=
( помощь ) - ^ Ng, Andrew Y .; Брадски, Гэри; Чу, Чэн-Тао; Олюкотун, Кунле; Ким, Сан Гюн; Линь И-Ань; Ю, ЮаньЮань (2006). «Map-Reduce для машинного обучения на многоядерных процессорах» . НИПС 2006.
- ^ Рейнджер, C .; Raghuraman, R .; Пенметса, А .; Брадски, G .; Козыракис, К. (2007). «Оценка MapReduce для многоядерных и многопроцессорных систем». 2007 13-й международный симпозиум IEEE по архитектуре высокопроизводительных компьютеров . п. 13. CiteSeerX 10.1.1.220.8210 . DOI : 10.1109 / HPCA.2007.346181 . ISBN 978-1-4244-0804-7.
- ^ Он, Б .; Fang, W .; Luo, Q .; Говиндараджу, НК; Ван, Т. (2008). «Марс: фреймворк MapReduce на графических процессорах» (PDF) . Материалы 17-й международной конференции по параллельным архитектурам и методам компиляции - PACT '08 . п. 260. DOI : 10,1145 / 1454115,1454152 . ISBN 9781605582825.
- ^ Chen, R .; Chen, H .; Занг, Б. (2010). «Tiled-MapReduce: оптимизация использования ресурсов приложений с параллельными данными в многоядерных системах с мозаичным использованием». Материалы 19-й международной конференции по параллельным архитектурам и методам компиляции - PACT '10 . п. 523. DOI : 10,1145 / 1854273,1854337 . ISBN 9781450301787.
- ^ Тан, Б .; Moca, M .; Chevalier, S .; Он, H .; Федак, Г. (2010). «На пути к MapReduce для настольных грид-вычислений» (PDF) . 2010 Международная конференция по P2P, параллельным, сетевым, облачным и Интернет-вычислениям . п. 193. CiteSeerX 10.1.1.671.2763 . DOI : 10.1109 / 3PGCIC.2010.33 . ISBN 978-1-4244-8538-3.
- ^ Luo, Y .; Guo, Z .; Sun, Y .; Plale, B .; Qiu, J .; Ли, В. (2011). «Иерархическая структура для междоменного выполнения MapReduce» (PDF) . Труды второго международного семинара по новым вычислительным методам для наук о жизни (ECMLS '11) . CiteSeerX 10.1.1.364.9898 . DOI : 10.1145 / 1996023.1996026 . ISBN 978-1-4503-0702-4.
- ^ Lin, H .; Максимум.; Archuleta, J .; Фен, туалет; Gardner, M .; Чжан, З. (2010). «ЛУНА: MapReduce в оппортунистических электронных средах» (PDF) . Материалы 19-го Международного симпозиума ACM по высокопроизводительным распределенным вычислениям - HPDC '10 . п. 95. DOI : 10,1145 / 1851476,1851489 . ISBN 9781605589428.
- ^ Marozzo, F .; Талия, Д .; Трунфио, П. (2012). «P2P-MapReduce: параллельная обработка данных в динамических облачных средах» (PDF) . Журнал компьютерных и системных наук . 78 (5): 1382–1402. DOI : 10.1016 / j.jcss.2011.12.021 . Архивировано из оригинального (PDF) 03 марта 2016 года . Проверено 4 сентября 2015 .
- ^ Dou, A .; Калогераки, В .; Gunopulos, D .; Mielikainen, T .; Туулос, В.Х. (2010). «Misco: платформа MapReduce для мобильных систем». Материалы 3-й Международной конференции по ресурсным технологиям, связанным с вспомогательными средами - PETRA '10 . п. 1. дои : 10,1145 / 1839294,1839332 . ISBN 9781450300711.
- ^ Ван, Яньдун; Голдстоун, Робин; Ю, Вэйкуань; Ван, Тэн (май 2014 г.). «Характеристика и оптимизация резидентного MapReduce в системах HPC». 28-й Международный симпозиум по параллельной и распределенной обработке, 2014 г., IEEE . IEEE. С. 799–808. DOI : 10.1109 / IPDPS.2014.87 . ISBN 978-1-4799-3800-1.
- ^ «Как работает Google» . baselinemag.com.
По состоянию на октябрь, согласно презентации Дина, Google выполнял около 3000 вычислительных задач в день через MapReduce, что составляет тысячи машинно-дней. Среди прочего, эти пакетные процедуры анализируют последние веб-страницы и обновляют индексы Google.
- ^ Чемберс, Крейг; Ранивала, Ашиш; Перри, Фрэнсис; Адамс, Стивен; Генри, Роберт Р .; Брэдшоу, Роберт; Вайценбаум, Натан (1 января 2010 г.). FlumeJava: простые и эффективные конвейеры с параллельными данными (PDF) . Труды 31-й конференции ACM SIGPLAN по проектированию и реализации языков программирования . С. 363–375. DOI : 10.1145 / 1806596.1806638 . ISBN 9781450300193. Архивировано из оригинального (PDF) 23 сентября 2016 года . Дата обращения 4 августа 2016 .
- ^ Пэн, Д., и Dabek, F. (2010, октябрь). Масштабная инкрементная обработка с использованием распределенных транзакций и уведомлений. В OSDI (Том 10, стр. 1-15).
- ^ «Эксперты баз данных прыгают через акулу MapReduce» .
- ^ а б Дэвид ДеВитт ; Майкл Стоунбрейкер . «MapReduce: большой шаг назад» . craig-henderson.blogspot.com . Проверено 27 августа 2008 .
- ^ «Apache Hive - Индекс - Apache Software Foundation» .
- ^ а б «HBase - HBase Home - Фонд программного обеспечения Apache» .
- ^ «Bigtable: распределенная система хранения структурированных данных» (PDF) .
- ^ Грег Йоргенсен . «Эксперты по реляционным базам данных прыгают через акулу MapReduce» . Typicalprogrammer.com . Проверено 11 ноября 2009 .
- ^ Павел, Андрей; Полсон, Эрик; Расин, Александр; Abadi, Daniel J .; DeWitt, Deavid J .; Мэдден, Сэмюэл; Стоунбрейкер, Майкл. «Сравнение подходов к анализу крупномасштабных данных» . Брауновский университет . Проверено 11 января 2010 .
- ^ Хиллис, В. Дэнни (1986). Машина связи . MIT Press . ISBN 0262081571.
- ^ Пол, Райан (20 января 2010 г.). «Патент Google MapReduce: что это значит для Hadoop?» . Ars Technica . Проверено 21 марта 2021 года .
- ^ «Патент США: 7650331 - Система и метод для эффективной крупномасштабной обработки данных» . uspto.gov .
- ^ Назер, Даниэль (28 марта 2013 г.). «Google дает открытое обязательство о непринятии патентных прав и предлагает новые модели лицензирования» . Electronic Frontier Foundation . Проверено 21 марта 2021 года .
- ^ Король, Рэйчел (2013). «Google расширяет открытое патентное обязательство еще на 79 вопросов об управлении центрами обработки данных» . ZDNet . Проверено 21 марта 2021 года .
- ^ «Система и метод эффективной крупномасштабной обработки данных» . Поиск патентов Google. 18 июня 2004 . Проверено 21 марта 2021 года .
- ^ Захария, Матей; Чоудхури, Мошараф; Франклин, Майкл; Шенкер, Скотт; Стойка, Ион (июнь 2010 г.). Spark: кластерные вычисления с рабочими наборами . HotCloud 2010.