Map and Reduce

Всё началось с доклада компании Google на конференции OSGI (текст доклада прикреплён к странице). А может быть и гораздо раньше (еще во временя языка Lisp), но после доклада все вокруг стали обсуждать эту модель параллельного программирования. Эта модель хорошо подходит для обработки огромных массивов данных на большом количестве компьютеров. Модель является крайне простой, и при этом очень эффективна. Она позволяет программисту отвлечься от проблем параллельного выполнения и сконцентрироваться на алгоритмах. О всём остальном позаботиться реализация MapReduce.

"Вычисление принимает на вход набор пар ключ/значение и вычисляет набор выходных пар ключ/значение. Пользователь библиотеки MapReduce выражает вычисление в виде двух функций: map и reduce (отобразить и сократить).

Отображение (функция map), задаваемое пользователем, получает пару входных значений и производит набор промежуточных пар ключ/значение. Библиотека MapReduce группирует вместе все промежуточные пары, ассоциированные с одинаковыми промежуточными ключами и передаёт их функции reduce.

Функция сокращения (reduce), также определяемая пользователем, принимает промежуточный ключ и множество значений, связанных с этим ключом. Она объединяет эти значения и формирует небольшой набор значений, обычно ноль или одно выходное значение за вызов функции. Промежуточные значения передаются функции через итератор, что позволяет обрабатывать даже большие списки значений, не влезающие в память"

Шаги работы MapReduce

• Итерирование по входным данным
• Вычисление пар ключ/значение по входным данным
• Группировка всех промежуточных значений по ключу
• Итерирование по полученным группам
• Сокращение (reduction) в каждой группе

Ruby и MapReduce

Достаточно легко реализуется на Ruby, поэтому существует несколько реализаций, самая известная из который StarFish.

Ссылки

http://multipart-mixed.com/software/simple_mapreduce_in_ruby.html - MapReduce на простом Ruby

http://romeda.org/blog/labels/mapreduce%20ruby%20code.html - MapReduce с использованием ruby2ruby и RingyDingy (1st of arpil)

http://labs.google.com/papers/mapreduce.html - аннотация доклада Google про MapReduce

Текст доклада (Авторы Jeffrey Dean and Sanjay Ghemawat, прочитано на OSDI'04: Sixth Symposium on Operating System Design and Implementation, San Francisco, CA, December, 2004. ):

• mapreduce-osdi04.pdf: MapReduce: Simplified Data Processing on Large Clu

http://tech.rufy.com/2006/08/mapreduce-for-ruby-ridiculously-easy.html - пример реального использования MapReduce на C++

http://www.cs.vu.nl/~ralf/MapReduce/ - Google's MapReduce Revised - обширный доклад по технологии.

http://rufy.com/distributed-programming/ - презентация по MapReduce на основе Rinda

-- AlexBreger - 29 Apr 2007

---