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