Принцип работы MapReduce (кратко): - Map: входные данные разбиваются на независимые фрагменты; каждая map‑задача читает фрагмент и для каждого исходного элемента испускает пары ключ–значение \((k, v)\). - Shuffle/Sort: промежуточные пары перемещаются по сети и сортируются так, чтобы все записи с одинаковым ключом попали к одному reduce‑задачнику. - Reduce: каждая reduce‑задача получает ключ \(k\) и поток значений \([v_1, v_2, \dots]\) и агрегирует их в итоговый результат (например, суммирует, объединяет, сортирует). - Важные оптимизации и свойства: локальность данных (задачи назначаются туда, где хранится блок), комбинирующие функции (combiners) для уменьшения объёма shuffle, повторное выполнение упавших задач для отказоустойчивости, масштабирование за счёт простого распараллеливания map/reduce задач. Пример задачи (не подсчёт слов): построение матрицы со‑встречаемости товаров (item–item co‑occurrence) для рекомендательной системы. Задача: по логам покупок/корзин много пользователей, у каждого — набор купленных товаров; нужно посчитать, сколько раз каждая пара товаров встречалась вместе (это затем используется для вычисления схожести). Как MapReduce решает задачу: - Map: для каждого пользователя с набором товаров \(S=\{i_1,i_2,\dots,i_k\}\) эмитировать для каждой пары \((i_a,i_b)\) запись \(((i_a,i_b),1)\). Для одного пользователя при размере корзины \(k\) получается \(\binom{k}{2}\) пар. - Combiner: локально агрегировать пары по ключу, превратив многие единицы в локальные суммы, чтобы сократить сетевой трафик. - Shuffle: сгруппировать все записи по парам товаров. - Reduce: для каждой пары \((i_a,i_b)\) суммировать все поступившие счётчики — получаем количество совместных покупок. Преимущества MapReduce для этой задачи: - Масштабируемость: параллельно обрабатываются миллионы пользователей и корзин; общая сложность по памяти/CPU делится между узлами. - Снижение сетевого трафика за счёт combiners (локальная агрегация) — критично, потому что число промежуточных пар может быть очень большим (итоговый объём промежуточных данных примерно \(\sum_u \binom{k_u}{2}\), где \(k_u\) — размер корзины пользователя \(u\)). - Отказоустойчивость и простота распределения работы по кластеру. - Подходит для одноразовой/пакетной агрегации больших объёмов данных, где распределённая группировка по ключу — естественная операция. Эта схема даёт существенное преимущество по сравнению с однопроходной обработкой на одной машине, когда объём данных и число пар делают задачу неприемлемо дорогой по времени и памяти.
- Map: входные данные разбиваются на независимые фрагменты; каждая map‑задача читает фрагмент и для каждого исходного элемента испускает пары ключ–значение \((k, v)\).
- Shuffle/Sort: промежуточные пары перемещаются по сети и сортируются так, чтобы все записи с одинаковым ключом попали к одному reduce‑задачнику.
- Reduce: каждая reduce‑задача получает ключ \(k\) и поток значений \([v_1, v_2, \dots]\) и агрегирует их в итоговый результат (например, суммирует, объединяет, сортирует).
- Важные оптимизации и свойства: локальность данных (задачи назначаются туда, где хранится блок), комбинирующие функции (combiners) для уменьшения объёма shuffle, повторное выполнение упавших задач для отказоустойчивости, масштабирование за счёт простого распараллеливания map/reduce задач.
Пример задачи (не подсчёт слов): построение матрицы со‑встречаемости товаров (item–item co‑occurrence) для рекомендательной системы.
Задача: по логам покупок/корзин много пользователей, у каждого — набор купленных товаров; нужно посчитать, сколько раз каждая пара товаров встречалась вместе (это затем используется для вычисления схожести).
Как MapReduce решает задачу:
- Map: для каждого пользователя с набором товаров \(S=\{i_1,i_2,\dots,i_k\}\) эмитировать для каждой пары \((i_a,i_b)\) запись \(((i_a,i_b),1)\). Для одного пользователя при размере корзины \(k\) получается \(\binom{k}{2}\) пар.
- Combiner: локально агрегировать пары по ключу, превратив многие единицы в локальные суммы, чтобы сократить сетевой трафик.
- Shuffle: сгруппировать все записи по парам товаров.
- Reduce: для каждой пары \((i_a,i_b)\) суммировать все поступившие счётчики — получаем количество совместных покупок.
Преимущества MapReduce для этой задачи:
- Масштабируемость: параллельно обрабатываются миллионы пользователей и корзин; общая сложность по памяти/CPU делится между узлами.
- Снижение сетевого трафика за счёт combiners (локальная агрегация) — критично, потому что число промежуточных пар может быть очень большим (итоговый объём промежуточных данных примерно \(\sum_u \binom{k_u}{2}\), где \(k_u\) — размер корзины пользователя \(u\)).
- Отказоустойчивость и простота распределения работы по кластеру.
- Подходит для одноразовой/пакетной агрегации больших объёмов данных, где распределённая группировка по ключу — естественная операция.
Эта схема даёт существенное преимущество по сравнению с однопроходной обработкой на одной машине, когда объём данных и число пар делают задачу неприемлемо дорогой по времени и памяти.