Подход mapreduce сейчас, с ростом объемов вычислений, стал очень популярен, но все упоминания какие то туманные, надо разложить все по полочкам. Начну с того что напомню о такой штуке как «закон Амдала». Он описывает ограничение роста производительности вычислительной системы с увеличением количества вычислителей, т.е. как мы можем ускорить вычисление увеличивая количество компьютеров в кластере. В общем то тут все интуитивно понятно. Математически он выражается в формуле:

где:
α — доля вычислений которые могут быть произведены только последовательно,
p — размер кластера (ну или количество процессоров/вычислителей).

И чем меньше α тем ближе масштабируемость к линейной. При 10% последовательного кода, к примеру, выходит что больше чем 100 компьютеров использовать не имеет никакого смысла, никакого серьезного прироста не будет, хоть на 1000 запускай. И добиться этих 10% не всегда просто.

Понятно что для того чтобы мы могли ускорять программу добавляя процессоры она должна иметь минимум таких обязательно последовательных участков. Это, кстати, один из стопоров увеличения количества ядер, так как сейчас очень мало программ которые используют параллельное вычисление, α у большинства в районе единицы, и тут как не добавляй ядра, программа не заработает быстрее.

Так вот MapReduce это такой подход построения архитектуры при котором просто не получится написать не параллельное приложение, α будет близко к 0. Алгоритм разбивается на 2 слоя параллельных операций и, в итоге, очень хорошо масштабируется. Надо заметить что алгоритм в виде функции map+reduce может быть гораздо медленней чем он же в стандартном (имеющим последовательные участки) виде, но стандартный алгоритм будет иметь предел после которого добавляя процессоры мы не выигрываем в производительности, с map+reduce вариантом этот предел почти недостижим. Дополнительным плюсом здесь является независимость, и при сбое отдельного участка его можно вычислить заново, не перезапуская весь процесс.

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

Один из классических примеров использования mapreduce - подсчитать распределение слов. В этом случае map обрабатывает входной текст, как независимые блоки. На выходе получаем пары «слово — кол-во употреблений» . В простейшем случае map не анализирует текст, а лишь разбивает по пробелам, в итоге из текста 5 раз содержащего слово «hello» на выходе будет не пара «hello — 5», а 5 пар по «hello — 1». Вот этот выхлоп уже связан друг с другом, и reduce обрабатывает эту связь. Ему на вход приходят блоки с одинаковым ключем пары, он в свою очередь суммирует цифровые значения этих пар. Поэтому обоих случаев наших «hello — x» он выдаст «hello — 5». Основную работу тут выполняет reduce. Такой, не совсем простой, способ подсчета количества слов полезен когда объем анализируемого текста измеряется гигабайтами (и более). Map выдаст огромный файл отсортированных пар «слово — количество» Так как он отсортирован то пробегая по нему достаточно просто вызвать reduce для всех групп с одним ключом, и получить суммарное количество для каждого из слов.

Хочу заметить что mapreduce, конечно, не панацея, часто он совсем не оптимален, и для малых объемов вообще не имеет смысла, но это самое простое и универсальное решение для масштабируемых алгоритмов, хорошо подходящий для различных data mining решений.