В последнее время набирает популярность семейство подходов и методологий обработки данных, объединенных общими названиями 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. Вот они:
- Тип возвращаемого значения функции reduce должен совпадать с типом значения, которое выдается функцией map (второй параметр функции emit)
- Должно выполняться равенство: reduce(key, [ A, reduce(key, [ B, C ]) ] ) == reduce( key, [ A, B, C ] )
- Повторное применение операции Reduce к полученной паре <ключ, значение> не должно влиять на результат (идемпотентность)
- Порядок значений, передаваемых функции 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
Автор: Digwener
