MapReduce Простая, но мощная модель параллельных вычислений или о том как обработать петабайты данных.

Информации много 20+ миллиардов веб-страниц × 20KB = 400+ TB Скорость чтения с диска 30–35 MB/sec ~4 месяца, чтобы прочитать весь интернет с диска ~1000 дисков, чтобы хранить весь интернет Еще больше времени нужно, чтобы сделать что-нибудь полезное с этими данными Что делать?

Используем 1000 компьютеров Можно посчитать все за 3 часа Но много возни –Координация и коммуникация между машинами –Восстановление при сбоях –Отображение состояния –Отладка –Оптимизация –Локальность Каждый раз нужно делать заново

Кластеры Много стоек с компьютерами Тысячи машин в кластере Ограниченная пропускная способность между стойками

Компьютеры 2 процессора Обычно hyperthreaded или dual-core В будущем будет больше ядер Несколько дисков От 1 TB до 4TB дискового пространства на машине 4–16GB оперативной памяти Обычно на машине запущены: Google File System (GFS) chunkserver Планировщик для запуска задач Одна или несколько задач

Особенности вычислительной среды Производительность одной машины не имеет значения Для больших задач соотношение пропускная способность/цена более важно, чем пиковая производительность Все ломается Один сервер может работать без сбоев три года (~1000 дней) Если у вас таких серверов, то они будут ломаться по 10 штук в день Супернадежное оборудование не помогает При больших масштабах даже самое надежние оборудование ломается, конечно реже чем обычное Программы все равно должны быть рассчитаны на сбои оборудования Обычные компьютеры обеспечивают лучшее соотношение производительность/цена Как же нам упростить написание распределенных программ?

Larry Page (слева) и Sergey Brin (справа)

google.stanford.edu (circa 1997)

google.com (1999)

Google Data Center (circa 2000)

google.com (new data center 2001)

google.com (3 days later)

MapReduce Простая модель вычислений, которая применима ко многим вычислительным задачам большого размера MapReduce обеспечивает: Автоматическое распараллеливание Балансировку нагрузки Оптимизацию загрузки сети и дисков Решение проблем с поломками машин Отказоустойчивость Улучшения базовой библиотеки помогают всем ее пользователям!

Типичная задача, решаемая MapReduce Прочитать много данных Map: извлечь из этих данных то, что нам нужно обработать Перетасовать и отсортировать Reduce: объединить, просуммировать, отфильтровать или изменить Записать результаты Схема остается одинаковой. Меняются Map и Reduce

Программируем MapReduce На входе и на выходе пары ключ/значение Нужно написать две функции: –map(in_key, in_value) -> list(out_key, intermediate_value) Обрабатывает поступившую на вход пару ключ/значение Выдает множество промежуточных пар –reduce(out_key, list(intermediate_value)) -> list(out_value) Комбинирует все промежуточные значения для данного ключа Выдает множество окончательных значений для данного ключа (обычно всего одно)

Пример: подсчет слов в тексте Обычно новички пишут такую программу в качестве упражнения в первую неделю работы На входе набор файлов с текстами Напишем функцию map, которая берет пары ключ/значение, где ключ = имя файла значение = содержание документа Функция выдает множество пар ключ/значение. В нашем случае, они имеют вид (слово, 1) для каждого слова из документа document1, в лесу родилась елочка, в лесу она росла в, 1 лесу, 1 родилась, 1 …

Пример: подсчет слов в тексте Библиотека MapReduce собирает вместе все пары с одинаковым ключом (перетасовывание/сортировка) Функция reduce получает и обрабатывает все значения для одного ключа. В нашем случае она считает сумму значений. в, 2 лесу, 2 родилась, 1 елочка, 1 она, 1 росла, 1 key = в values = 1, 1 2 key = лесу values = 1, 1 2 key = родилась values = 1 1 key = елочка values = 1 1 key = она values = 1 1 key = росла values = 1 1

Пример (псевдокод) Map(String input_key, String input_value): // input_key: document name // input_value: document contents for each word w in input_values: EmitIntermediate(w, "1"); Reduce(String key, Iterator intermediate_values): // key: a word, same for input and output // intermediate_values: a list of counts int result = 0; for each v in intermediate_values: result += ParseInt(v); Emit(AsString(result)); На C++ получится 80 строк с комментариями и функцией main()

MapReduce широко применяется в Гугле Существуют реализации для C++, Java, Python Поддерживается множество форматов для входных и выходных данных Примеры использования: распределенный grep распределенная сортировка построение графа гиперссылок Did you mean? анализ статистики посещений построение инвертированного индекса кластеризация документов машинное обучение статистический машинный перевод

Число программ, использующих MapReduce

Распределение задач Много машин, один мастер Входные данные разделяются на M заданий типа map (обычно по 64MB) Стадия reduce разделяется на R заданий Задания распределяются динамически Часто: M = ; R = 4 000; число машин = Мастер назначает задания типа map свободным машинам Принимает во внимание близость данных к обрабатывающей их машине Машина, получившая задание, читает данные с диска (часто с локального) И создает R локальных файлов, сожержащих промежуточные пары Мастер назначает задания типа reduce свободным машинам Reducer читает нужные ему промежуточные пары с mapperов Reducer сортирует пары и применяет операцию Reduce

Выполнение MapReduce Map Входные данные Reduce Shuffle Reduce Shuffle Reduce Shuffle Выходные данные Master

Гранулярность Мелкие задачи – задач гораздо больше чем машин Это минимизирует время восстановления после ошибки Лучшее динамическое распределение нагрузки задач типа map / задач типа reduce на машин

MapReduce status: MR_Indexer-beta6-large-2003_10_28_00_03

Отказоустойчивость При падении одной из машин: – Оно определяется используя периодические проверки (heartbeats) – Перезапускаем задания типа map, которые были назначены упавшей машине – Перезапускаем незавершенные задания типа reduce – Завершение задачи подтверждается мастером При падении мастера: –Можно его перезапустить, но пока в этом не было необходимости

Улучшения. Повторный запуск Медленные машины существенно увеличивают общее время работы Другие задачи отъедают ресурсы на этой машине Диски замедляют передачу данных при ошибках Странные вещи: отключен кеш процессора Решение - ближе к концу работы запускаем копии незавершенных задач Первый завершивший задачу выигрывает В результате существенно сокращается общее время работы

Улучшения. Оптимизация локальности При распределении заданий мастер Запрашивает GFS о том, где расположены копии блоков данных Обычно задания map обрабатывают 64MB (размер блока GFS) Задания типа map назначаются на те машины, на которых хранятся соответствующие блоки GFS или на машины из той же стойки

Улучшения. Пропускаем плохие записи Иногда функции Map или Reduce падают при некоторых значениях на входе Лучше всего их отладить и исправить, но это не всегда возможно При ошибке посылаем мастеру UDP-пакет, содержащий порядковый номер записи, при обработке которой произошла ошибка Если мастер замечает несколько ошибок для одной записи, то в следующий раз мы ее пропустим Можно обойти баги внешних библиотек

Другие улучшения (подробности в статье) Sorting guarantees within each reduce partition Compression of intermediate data Combiner: useful for saving network bandwidth Local execution for debugging/testing User-defined counters Optional secondary keys for ordering

Пример: Построение индекса Построение индекса Google использует MapReduce Состоит из нескольких десятков фаз MapReduce Код стал гораздо проще после перевода на MapReduce MapReduce заботится об ошибках и медленных машинах Просто ускорить построение индекса, добавив больше машин

Сторонние реализации Hadoop – реализация на Java от Apache Foundation IBM MapReduce Tools for Eclipse Qt Concurrent (since 4.3) – реализация MapReduce для систем с общей памятью Есть реализация для Ruby

Заключение Оказалось, что MapReduce – довольно полезная абстракция Существенно упрощает крупномасштабные вычисления в Google Можно сфокусироваться только на задаче, которую необходимо решить и не заботиться о куче вещей За несколько лет были написаны тысячи эффективных параллельных программ Среди пользователей MapReduce многие не имели опыта написания параллельных и распределенных программ Подробнее о MapReduce можно прочитать в статье MapReduce: Simplified Data Processing on Large Clusters Jeffrey Dean and Sanjay Ghemawat OSDI'04: Sixth Symposium on Operating System Design and Implementation (просто поищите MapReduce в Google)

Google в России Центры разработки в Москве и Санкт-Петербурге Открыты вакансии для программистов и других специалистов - полный список вакансий (или просто поискать работа в google)

Спасибо за внимание!