html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

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.
Читать дальше
Twitter
Одноклассники
Мой Мир

материал с habrahabr.ru

0

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • habrahabr.ru
          • домен habrahabr.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

            Ваш профиль на рассмотрении, обновите страницу через несколько секунд

            Facebook

            К сожалению, вы не попадаете под условия акции