'

Шаблоны проектирования Hadoop MapReduce

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

In-mapper combining


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

“Pairs” и “stripes” Pairs:


Слайд 16

“Pairs” и “stripes” Stripes:


Слайд 17

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


Слайд 18

“Pairs” и “stripes”


Слайд 19

“Pairs” и “stripes”


Слайд 20

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


Слайд 21

Order inversion Возникает проблема: как подсчитать знаменатель? С помощью шаблона “Stripes”: в reducer попадают пары <term, Stripe[term1,term2,…]>, поэтому можно вычислять знаменатель на месте.


Слайд 22

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


Слайд 23

Order inversion Пример:


Слайд 24

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


Слайд 25

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


Слайд 26

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


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30

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 более прост и потому популярен.


Слайд 31

Вопросы?


×

HTML:





Ссылка: