Шаблоны проектирования Hadoop MapReduce Сильвестров Алексей 26 апреля 2011 г. - презентация

1 Шаблоны проектирования Hadoop MapReduce Сильвестров Алексей 26 апреля 2011 г

2 Введение In-mapper combining Pairs and stripes Order inversion Value-to-key conversion Базы данных : map-side join, reduce-side join План доклада

3 Архитектура MapReduce

4 Задача Подсчитать количество вхождений всех слов в наборе документов {d1,d2,…}

5 Типичное решение

6 In-mapper combining

7 Недостатки паттерна: 1.Угроза масштабируемости: н адо хранить результаты промежуточных вычислений, пока mapper не обработает все поданные на него данные. 2.Наличие внутренних состояний внутри mapper создает возможность появления ошибок связанных с порядком выполнения. Одно из решений 1): делать emit после каждых n обработанных пар

8 In-mapper combining Combiner в MapReduce - оптимизационная опция, поэтому корректность выполнения алгоритма не должна от него зависеть. Reducer должен принимать на вход пары того же типа что и пары испускаемые mapperом.

9 Задача Рассмотрим пример, в котором обыграны два этих правила. Есть много.log документов, хранящих данные вида. Нужно посчитать среднее время пребывания на сайте. Учесть правило:

10 Простое решение

11 Неправильное решение

12

13 Правильное решение

14 Еще одно решение

15 Pairs и stripes Учебник Python 3 покупают вместе с K&R, но никогда наоборот. Учебник SICP не покупают вместе с Мечты роботов Азимова. Нужно построить матрицу совместных покупок с помощью паттерна pairs или с помощью паттерна stripes.

16 Pairs и stripes Pairs:

17 Pairs и stripes Stripes:

18 Pairs и stripes Очевидно, что pairs генерирует намного больше пар, чем stripes. Реализация stripes компактна, но сложна. Реализация stripes требует временного хранения данных. Combiner в stripes имеет больше возможностей для выполнения локальной агрегации.

19 Pairs и stripes

20

21 Order inversion Вернемся к построению матрицы совместных покупок: некоторые товары покупают гораздо чаще других. Следовательно абсолютные значения нерепрезентативны, поэтому перейдем к частотам:

22 Order inversion Возникает проблема: как подсчитать знаменатель? С помощью шаблона Stripes: в reducer попадают пары, поэтому можно вычислять знаменатель на месте.

23 Order inversion В случае Pairs нужно проявить изобретательность: идея этого шаблона состоит в сохранении масштабируемости. 1. Заведем специальные key-value: для подсчета знаменателя. 2. В reducer введем свой порядок сортировки, чтобы специальные пары суммировались до вычисления частот. 3. Определим свой partitioner который будет отправлять пары с одинаковым первым словом на один reducer. 4. Для правильного порядка сортировки(.2) заведем состояния в reducer.

24 Order inversion Пример:

25 Value-to-key conversion Рассмотрим пример: m сенсоров считывают некие данные, t – timestamp, Rx – данные. Выделим работу одного сенсора с помощью Map: Т.е. Reducer получит данные с конкретного сенсора, не отсортированные по timestampам.

26 Value-to-key conversion Очевидное решение: буферизовать данные и затем сортировать их по timestamp – потенциальная угроза масштабируемости. Value-to-key conversion : в паре часть значения переносится в ключ, проблемы сортировки возлагаются на MapReduce: Таким образом на reduce будут попадать отсортированные по обоим параметрам данные:

27 Базы данных: реляционные соединения Hadoop часто используется для хранения данных в форме реляционных баз данных. Рассмотрим три вида объединения отношений S и T: один к одному, один ко многим, много ко многим. k – ключ, s – идентификатор кортежа, S и T – остальные атрибуты.

28 Reduce-side join. Один к одному Идея Reduce-side join состоит в разбиении данных по ключу на map и объединении на Reduce. В качестве примера рассмотрим объединение один к одному: В map стадии k используется как временный ключ, остальное содержимое кортежа - как значение.

29 Reduce-side join. Один ко многим Рассмотрим объединение один ко многим: пусть в S k- уникальный ключ, в T – нет. Простейший выход- хранить оба отношения в памяти, вытаскивать кортеж из S и объединять с каждым кортежем из T - является угрозой масштабируемости. Здесь понадобится secondary sort и вытекающий из него value-to-key conversion - в mapper создается составной ключ: Когда бы reducer не получил пару гарантируется что ее кортеж S будет сохранен в памяти до появления T кортежа, после чего произойдет объединение.

30 Reduce-side join. Много ко многим Много ко многим: в S и T k не являются уникальными ключами: Для объединения каждого с каждым также используется Value-to-key conversion.

31 Map-side join Идея Map-side join состоит в объединении данных на map и и отправке на Reduce. Пример: S и T разделены на 10 файлов(5 для S и 5 для T), в каждом файле кортежи отсортированы по первичному ключу. Чтобы выполнить объединение, нужно параллельно обработать файлы S1 и T1, S2 и T2 и т.д. на map- стадии. Map-side join более эффективен чем Reduce-side, т.к. не требуется передача данных по сети на Reduce узлы. Однако Reduce-side более прост и потому популярен.

32 Вопросы?