Map-Reduce на примере MongoDB

В последнее время набирает популярность семейство подходов и методологий обработки данных, объединенных общими названиями Big Data и NoSQL. Одной из моделей вычислений, применяемых к большим объемам данных, является технология Map-Reduce, разработанная в недрах компании Google. В этом посте я постараюсь рассказать о том, как эта модель реализована в нереляционной СУБД MongoDB.

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

Нереляционная СУБД MongoDB представляет данные в виде коллекций из документов в формате JSON и предоставляет разные способы обработки этих данных. В том числе, присутствует собственная реализация модели Map-Reduce. О том, насколько целесообразно применять именно эту реализацию в практических целях, будет сказано ниже, а пока ограничимся тем, что для ознакомления с самой парадигмой Map-Reduce эта реализация подходит как нельзя лучше.

Итак, что же такого особенного в Map-Reduce?

Предположим, что мы разрабатываем крупное онлайн-приложение, данные которого хранятся распределенным образом на нескольких серверах во всех уголках земного шара. Помимо всего прочего у пользователя указаны его интересы. Мы решили вычислить популярность каждого интереса путем простого определения числа пользователей, разделяющих этот интерес. Если бы мы использовали реляционную СУБД и хранили всех пользователей на одном сервере, то простой запрос с использованием операции group by помог бы нам получить ответ. В случае разных узлов мы бы хотели, чтобы эта группировка выполнялась параллельно, загружая все сервера равномерно. В мире реляционных СУБД и SQL-запросов представить такое довольно сложно, а вот с помощью Map-Reduce эта задача вполне решаема.

Пусть в нашей базе есть коллекция users, элементы которой имеют вид:

{
	name : "John",
	age : 23,
	interests : ["football", "IT", "women"]
}

На выходе мы хотим получить коллекцию такого типа:

{
	key: "football",
	value: 1349
},
{
	key: "MongoDB",
	value: 58
},
//...

В ходе выполнения система выполняет над данными операции Map и Reduce, которые определяются программистом. В MongoDB эти операции имеют вид функций, написанных на Javascript. То есть сами функции пишет программист, а Mongo управляет их вызовом.

В начале к каждому документу коллекции применяется операция Map, которая формирует пары <ключ, значение>. Эти пары затем передаются функции reduce в сгруппированном по ключу виде. Операция Reduce формирует одну пару <ключ, значение>. Как в качестве ключа, так и в качестве значения могут выступать любые переменные, включая объекты.

Рассмотрим функцию map для нашего примера:

function map(){
	for(var i in this.interests) {
		emit(this.interests[i], 1);
	}
}

Как можно заметить, документ, к которому применена операция Map, доступен по указателю this. Функция emit служит для передачи очередной пары <ключ, значение> для дальнейшей обработки. Как видно, операция Map для одного документа может выдать несколько пар <ключ, значение>. В данном примере всё просто — мы передаем в качестве ключа интерес, а в качестве значения единицу — так как в данном случае интерес встретился ровно один раз.

Сформированные пары группируются по ключу и передаются функции reduce в виде <ключ, список значений>. Функция reduce для нашего примера выглядит так:

function reduce(key, values) {
	var sum = 0;
	for(var i in values) {
		sum += values[i];
	}
	return sum;
}

Для получения итогового значения мы суммируем все значения, которые имеем в массиве values. Изменение ключа операцией Reduce не предусмотрено, поэтому функция просто возвращает полученное значение в виде своего результата.

Сообразительный читатель может задаться следующим вопросом — а зачем пробегать по всему массиву values и складывать его элементы, если мы знаем что они равны единице? Не проще ли вернуть длину массива? Ответ на этот вопрос является отрицательным, а пояснение прольет свет на ключевую особенность работы Map-Reduce.

Дело в том, что MongoDB запускает операцию Reduce для выполнения промежуточных агрегаций. Как только сформировано несколько пар с одинаковым ключом, MongoDB может выполнить для них Reduce, получив тем самым одну пару <ключ, значение>, которая потом обрабатывается наравне с остальными, как если бы она была получена с помощью операции Map.

Это накладывает определенные требования на реализацию функции reduce. Вот они:

  1. Тип возвращаемого значения функции reduce должен совпадать с типом значения, которое выдается функцией map (второй параметр функции emit)
  2. Должно выполняться равенство: reduce(key, [ A, reduce(key, [ B, C ]) ] ) == reduce( key, [ A, B, C ] )
  3. Повторное применение операции Reduce к полученной паре <ключ, значение> не должно влиять на результат (идемпотентность)
  4. Порядок значений, передаваемых функции reduce, не должен влиять на результат

Второе требование является еще и иллюстрацией того, что может произойти. Если пары <key, B> и <key, C> были получены на одном узле, а <key, A> на другом, то предварительное выполнение операции Reduce на первом из узлов уменьшит сетевой трафик и повысит параллелизм. Но платой за это являются существенные ограничения на функцию reduce, вызванные необходимостью поддерживать вышеуказанное тождество.

После того как все операции Map и Reduce выполнены, на выходе формируется коллекция из элементов вида

{
	key:"football",
	value: 1349
},

Чтобы запустить такую операцию, нужно объявить эти две функции в консоли mongo shell, а затем выполнить команду:

db.users.mapReduce(map, reduce,{out:"interests"})

Рассмотрим другую задачу. Предположим, мы хотим узнать среднее количество интересов у людей разных возрастов. Функция map в данном случае может иметь вид:

function map(){
	emit(this.age, {interests_count: this.interests.length, count: 1});
}

Ключом здесь является возраст, а в качестве значения передается объект — количество интересов и количество людей данного возраста, эти интересы разделяющих (для одного документа является единицей).

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

function reduce(key, values) {
	var sum = 0;
	var count = 0;
	for(var i in values){
		count += values[i].count;
		sum += values[i].interests_count;
	}
	return {interests_count: sum, count: count};
}

Чтобы в итоговой коллекции получить искомое среднее арифметическое, можно воспользоваться операцией Finalize — она применяется к финальной паре <key, value>, полученной после выполнения всех операций Reduce с ключом key:

	function finalize(key, reducedValue) {
		return reducedValue.interests_count / reducedValue.count;
	}

Команда для вызова:

 db.users.mapReduce(map, reduce, {finalize: finalize, out:"interests_by_age"})

Необходимо отметить, что в других реализациях Map-Reduce, включая Apache Hadoop, подобных ограничений на работу Reduce нет. Там на вход функции reduce всегда будет подаваться полный список значений, относящихся к ключу. А промежуточную агрегацию можно осуществить посредством другой операции, Combine, семантически схожей с Reduce.

Теперь несколько слов о целесообразности практического применения нативной реализации MapReduce в Mongo. Для выполнения агрегаций в этой СУБД существует мощный инструмент под названием Aggregation Framework, который выполняет те же самые агрегации приблизительно в 5-10 раз быстрее Map-Reduce. Но параллелизм в данном случае заканчивается там, где начинаются сортировки и группировки. Также есть определенные ограничения на оперативную память, потребляемую операцией.

Вообще, Aggregation Framework следует применять там, где требуется быстрый отклик, в то время как Map-Reduce предназначен для предварительной обработки сырой информации. Mongo предоставляет возможности для взаимодействия с Hadoop, чья реализация Map-Reduce работает более эффективно, чем нативная. Так или иначе, MongoDB позволяет ознакомиться с моделью Map-Reduce без необходимости устанавливать и настраивать такой сравнительно тяжеловесный инструмент как Apache Hadoop.
  • +54
  • 44,4k
  • 8
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 8
  • +1
    Спасибо большое за статью. Очень просто и очень понятно!
    • +2
      Вообще, Aggregation Framework следует применять там, где требуется быстрый отклик, в то время как Map-Reduce предназначен для предварительной обработки сырой информации

      Я бы раскрыл тему, а то не особо понятно, что это значит.
      А именно
      а) Aggregation framework умеет утилизировать индексы(иногда). MR, очевидно всегда делает перебор.
      Отсюда следует что AF работает не во сколько-то там раз быстрее, а имеет лучшую асимптотику(опять же, иногда, в монго на эту тему есть хорошая документация).
      б) AF работает с нативными функциями, так что есть и другая составляющая скорости.
      в) AF имеет весьма стремный синтаксис, в отличие от MR
      • 0
        Как по мне, для 90% повседневных нужд написать запрос для AF гораздо проще и быстрее, чем функции MR, а благодаря конвеерной обработке еще и очень привычно для пользователей *nix систем.
        • +2
          Aggregation framework умеет утилизировать индексы(иногда). MR, очевидно всегда делает перебор.

          Поправлю: MapReduce тоже может использовать индексы — в функции mapReduce есть query параметр который позволяет сузить первоначальную выборку.
        • +1
          У меня, почему-то, функция mapReduce каждый раз выводит объект со статистикой, но не выдает мне результатов. Что может быть не так?

          {
          «result»: «interests_by_age»,
          «timeMillis»: 4,
          «counts»: {
          «input»: 3,
          «emit»: 3,
          «reduce»: 1,
          «output»: 2
          },
          «ok»: 1,
          }
          • +1
            docs.mongodb.org/manual/reference/command/mapReduce/#dbcmd.mapReduce

            out –
            New in version 1.8.
            Specifies the location of the result of the map-reduce operation. You can output to a collection, output to a collection with an action, or output inline. You may output to a collection when performing map reduce operations on the primary members of the set; on secondary members you may only use the inline output.

            Вы очевидно указали out:«interests», как в примерах.
            • 0
              В качестве результата («result»: «interests_by_age»), Вы указали название коллекции, в которую и будет записан результат — «interests_by_age».
              Если коллекция с таким именем существует, все данные в ней буду перезаписаны.
            • 0
              Отличная статья!

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.