MapReduce. Основы

MapReduce - модель программирования для параллельной обработки данных. Про MapReduce уже написано и сказано много. Самые лучшие материалы я прикладываю ниже.
Видеолекция посвященная MapReduce и распределенной файловой системе HDFS:


Cloudera Hadoop Training: MapReduce and HDFS from Cloudera on Vimeo.

Документ от Google, в котором впервые был описан MapReduce:




Код ниже описывает простейшую MapReduce программу, которая подсчитывает количество вхождений определенного слова в документах. На вход map подается название документа и его содержание. Map разбивает содержание документа на список слов и пересылает каждое слово на reduce вместе с 1. MapReduce фреймворк производит группировку всех получаемых данных по ключу и формирует список значений. Ключ и данный список передается на нашу reduce функцию, которая производит суммирование полученного списка и пересылает результат.

map(String input_key, String input_value):

  // input_key: название документа

  // input_value: содержание документа

  for each word w in input_value:

    Emit(w, 1);

reduce(String output_key, Iterator intermediate_values):

  // output_key: слово

  // output_values: список кол-ва вхождений слова

  int result = 0;

  for each v in intermediate_values:

    result += v;

  Emit(result);

Ниже представлена схема процесса обработки данных.

Самый интересный момент в данной программе состоит в том, почему она пересылает единичку с каждым словом, а не строит например HashMap, подсчитывает общее количество слов и уже потом отсылает свой список. MapReduce фреймворк избавляет нас от необходимости создавать какие-то структуры в оперативной памяти и делать предварительные группировки. Ведь объем данных, пересылаемых на map шаг может составлять более сотни мегабайт. На одном вычислительном узле, как правило запускается одновременно map и reduce задачи (map задач значительно больше). Поэтому использование например 64 Мб на каждую из map задач может вести к падению общей производительности. 

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

Например, по закону Зипфа слова "the" в английском языке будут встречаться чаще других слов и какому-то узлу будет приходить значительно больше данных, чем другим узлам. Если мы предварительно сольем все одинаковые ключи, то пересылаемых данных может стать меньше.

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