Без темы
<<  «Два поколения в романе NOVOMETRY - НОВОМЕТРИЯ - Эффект, Эффективность и Ранг нововведений Москва  >>
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
Информации много
Информации много
Используем 1000 компьютеров
Используем 1000 компьютеров
Кластеры
Кластеры
Компьютеры
Компьютеры
Особенности вычислительной среды
Особенности вычислительной среды
Larry page (слева) и sergey brin (справа)
Larry page (слева) и sergey brin (справа)
google
google
google
google
Google Data Center (circa 2000)
Google Data Center (circa 2000)
google
google
google
google
MapReduce
MapReduce
Типичная задача, решаемая MapReduce
Типичная задача, решаемая MapReduce
На входе и на выходе пары ключ/значение Нужно написать две функции:
На входе и на выходе пары ключ/значение Нужно написать две функции:
Пример: подсчет слов в тексте
Пример: подсчет слов в тексте
Пример: подсчет слов в тексте
Пример: подсчет слов в тексте
Пример (псевдокод)
Пример (псевдокод)
MapReduce широко применяется в Гугле
MapReduce широко применяется в Гугле
Число программ, использующих MapReduce
Число программ, использующих MapReduce
Распределение задач
Распределение задач
Выполнение MapReduce
Выполнение MapReduce
Гранулярность
Гранулярность
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
MapReduce Простая, но мощная модель параллельных вычислений или о том
Отказоустойчивость
Отказоустойчивость
Улучшения
Улучшения
Улучшения
Улучшения
Улучшения
Улучшения
Другие улучшения (подробности в статье)
Другие улучшения (подробности в статье)
Пример: Построение индекса
Пример: Построение индекса
Сторонние реализации
Сторонние реализации
Заключение
Заключение
Google в России
Google в России
Спасибо за внимание
Спасибо за внимание

Презентация: «MapReduce Простая, но мощная модель параллельных вычислений или о том как обработать петабайты данных». Автор: Google Employee. Файл: «MapReduce Простая, но мощная модель параллельных вычислений или о том как обработать петабайты данных.ppt». Размер zip-архива: 3149 КБ.

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

содержание презентации «MapReduce Простая, но мощная модель параллельных вычислений или о том как обработать петабайты данных.ppt»
СлайдТекст
1 MapReduce Простая, но мощная модель параллельных вычислений или о том

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

как обработать петабайты данных.

2 Информации много

Информации много

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

3 Используем 1000 компьютеров

Используем 1000 компьютеров

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

4 Кластеры

Кластеры

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

5 Компьютеры

Компьютеры

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

6 Особенности вычислительной среды

Особенности вычислительной среды

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

7 Larry page (слева) и sergey brin (справа)

Larry page (слева) и sergey brin (справа)

8 google

google

stanford.edu (circa 1997)

9 google

google

com (1999)

10 Google Data Center (circa 2000)

Google Data Center (circa 2000)

11 google

google

com (new data center 2001)

12 google

google

com (3 days later)

13 MapReduce

MapReduce

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

14 Типичная задача, решаемая MapReduce

Типичная задача, решаемая MapReduce

Схема остается одинаковой. Меняются Map и Reduce

Прочитать много данных Map: извлечь из этих данных то, что нам нужно обработать Перетасовать и отсортировать Reduce: объединить, просуммировать, отфильтровать или изменить Записать результаты

15 На входе и на выходе пары ключ/значение Нужно написать две функции:

На входе и на выходе пары ключ/значение Нужно написать две функции:

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

Программируем MapReduce

16 Пример: подсчет слов в тексте

Пример: подсчет слов в тексте

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

“Document1”, “в лесу родилась елочка, в лесу она росла”

“В”, “1” “лесу”, “1” “родилась”, “1” …

17 Пример: подсчет слов в тексте

Пример: подсчет слов в тексте

“В”, “2” “лесу”, “2” “родилась”, “1” “елочка”, “1” “она”, “1” “росла”, “1”

Библиотека MapReduce собирает вместе все пары с одинаковым ключом (перетасовывание/сортировка) Функция reduce получает и обрабатывает все значения для одного ключа. В нашем случае она считает сумму значений.

18 Пример (псевдокод)

Пример (псевдокод)

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()

19 MapReduce широко применяется в Гугле

MapReduce широко применяется в Гугле

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

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

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

21 Распределение задач

Распределение задач

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

22 Выполнение MapReduce

Выполнение MapReduce

Входные данные

Map

Map

Map

Map

Master

Выходные данные

23 Гранулярность

Гранулярность

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

24 MapReduce Простая, но мощная модель параллельных вычислений или о том
25 MapReduce Простая, но мощная модель параллельных вычислений или о том
26 MapReduce Простая, но мощная модель параллельных вычислений или о том
27 MapReduce Простая, но мощная модель параллельных вычислений или о том
28 MapReduce Простая, но мощная модель параллельных вычислений или о том
29 MapReduce Простая, но мощная модель параллельных вычислений или о том
30 MapReduce Простая, но мощная модель параллельных вычислений или о том
31 MapReduce Простая, но мощная модель параллельных вычислений или о том
32 MapReduce Простая, но мощная модель параллельных вычислений или о том
33 MapReduce Простая, но мощная модель параллельных вычислений или о том
34 MapReduce Простая, но мощная модель параллельных вычислений или о том
35 Отказоустойчивость

Отказоустойчивость

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

36 Улучшения

Улучшения

Повторный запуск

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

37 Улучшения

Улучшения

Оптимизация локальности

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

38 Улучшения

Улучшения

Пропускаем плохие записи

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

39 Другие улучшения (подробности в статье)

Другие улучшения (подробности в статье)

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

40 Пример: Построение индекса

Пример: Построение индекса

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

41 Сторонние реализации

Сторонние реализации

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

42 Заключение

Заключение

Оказалось, что 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)

43 Google в России

Google в России

Центры разработки в Москве и Санкт-Петербурге Открыты вакансии для программистов и других специалистов http://google.ru/jobs - полный список вакансий (или просто поискать “работа в google”)

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

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

«MapReduce Простая, но мощная модель параллельных вычислений или о том как обработать петабайты данных»
http://900igr.net/prezentacija/geometrija/mapreduce-prostaja-no-moschnaja-model-parallelnykh-vychislenij-ili-o-tom-kak-obrabotat-petabajty-dannykh-177563.html
cсылка на страницу

Без темы

105 презентаций
Урок

Геометрия

40 тем
Слайды
900igr.net > Презентации по геометрии > Без темы > MapReduce Простая, но мощная модель параллельных вычислений или о том как обработать петабайты данных