Поиск в MapReduce позволил найти различные отдельные посты в блогах, страницы некоторых курсов университетов и одну книгу, в которой, как представляется, содержится почти все, что делали другие источники.
Этот пост содержит вопросы и ответы MapReduce на основе книги. По сути, если бы я был студентом, это то, что я бы сделал в качестве заметок к экзамену. Если бы я был учителем, это то, что я бы спросил на экзамене.
Первая глава посвящена теме кредита, а остальная часть содержит вопросы. Последняя глава содержит практические упражнения по кодированию.
Книга
Книга называется Интенсивная обработка текста с помощью MapReduce . Если вы не уверены, хотите ли вы купить его или нет, предварительная версия рукописи доступна бесплатно.
Не обманывайтесь названием. Книга больше о самом MapReduce и меньше об обработке текста. Первая половина книги описывает приемы общего назначения (шаблоны проектирования), полезные для любой задачи. Вторая половина содержит главы по обработке текста, алгоритмам графиков и максимизации ожиданий.
Книга содержит почти все, что я нашел в различных блогах, на страницах университетских курсов и многое другое.
Вопросы
Вопросы разбиты по главам книг. За одним небольшим исключением (счетчики) вопросы в основном основаны на первой половине книги. Вторая половина содержит конкретные алгоритмы, и я хотел сосредоточиться на знаниях общего назначения.
Это не значит, что их изучение бесполезно. В частности, глава Graph Algorithms содержит легко обобщаемые идеи.
2 MapReduce Основы
2.2 Картографы и редукторы
Опишите общий алгоритм MapReduce. Разделите это на фазы. Для каждого этапа включают в себя:
- кто отвечает (фреймворк / программист / настраиваемый),
- что оно делает,
- фазовый ввод,
- фазовый выход.
MapReduce имеет четыре фазы:
- карта,
- комбайн,
- челнок и сортировка,
- уменьшить.
Фаза карты выполняется картографами. Мапперы работают на несортированных парах ключ / значение. Те же физические узлы, которые хранят входные данные, также работают с мапперами. Каждый преобразователь генерирует ноль, одну или несколько выходных пар ключ / значение для каждой пары входной ключ / значение. Выходные пары ключ / значение называются промежуточными парами ключ / значение. Их тип обычно отличается от типа пары ключ / значение. Картограф должен быть предоставлен программистами.
Фаза объединения осуществляется объединителями. Комбинатор должен объединять пары ключ / значение с одним и тем же ключом. Каждый объединитель может работать ноль, один или несколько раз. Framework решает, запускать ли комбинатор и сколько раз, программист не может его контролировать. Тип пары ключ / значение выходных данных комбинаторов должен совпадать с типом пары «ключ / значение» ввода.
Фаза челнока и сортировки выполняется рамкой. Данные всех картографов сгруппированы по ключу, распределены по редукторам и отсортированы по ключу. Каждый редуктор получает все значения, связанные с одним и тем же ключом. Программист может предоставить пользовательскую функцию сравнения для сортировки и разделителя для разделения данных. Все пары ключ / значение, идущие к одному и тому же редуктору, сортируются по ключу, но глобальная сортировка отсутствует.
Редуктор получает отсортированные пары ключ / [список значений], отсортированные по ключу. Список значений содержит все значения с одним и тем же ключом, созданным картографами. Каждый редуктор генерирует ноль, одну или несколько пар ключ / значение для каждой пары ключ / значение. Тип выходной ключ / пара значений обычно отличается от типа входной ключ / пара значений. Редуктор должен поставляться программистами.
Если алгоритм требует нескольких итераций MapReduce, каждый объединитель может увеличивать глобальный счетчик. Программа драйвера считывает счетчик после фазы уменьшения. Затем он решает, нужна ли следующая итерация или нет.
Примечание: глава 2 не упоминает счетчики. Они объяснены позже, в главе 5. Решите, является ли утверждение истинным или ложным: все реализации MapReduce реализуют точно такой же алгоритм.
Ложь. Например, реализация Google не позволяет менять ключ в редукторе, но обеспечивает сортировку значений. Hadoop не обеспечивает сортировку значений, но редуктор может изменить ключ.
Истина или ложь: каждый маппер должен генерировать такое же количество пар ключ / значение, которое имел его вход.
Ложь. Mapper может генерировать любое количество пар ключ / значение (включая ноль).
Истина или ложь: пары ключ-значение ввода карт сопоставляются по ключу.
Ложь. Вход Mapper никак не сортируется.
True или false: выходной ключ / значение Mappers должен быть того же типа, что и его ввод.
Ложь. Mapper может создавать пары ключ / значение любого типа.
Истина или ложь: Редуктор применяется ко всем значениям, связанным с одним и тем же ключом.
Правда. Редуктор применяется ко всем значениям, связанным с одним и тем же ключом.
Истина или ложь: пары ключ / значение редуктора сортируются по ключу.
Правда. Пары ключ / значение ввода редукторов сортируются по ключу.
реализация.
Истина или ложь: каждый редуктор должен генерировать такое же количество пар ключ / значение, которое имел его вход.
Ложь. Редуктор может генерировать любое количество пар ключ / значение (включая ноль).
Истина или ложь: пара ключ / значение выходного редуктора должна быть того же типа, что и ее вход.
Ложь. Утверждение ложно в Hadoop и верно в реализации Google.
2.3 Структура исполнения
Что происходит в случае аппаратного / программного сбоя?
Каркас MapReduce должен быть способен восстанавливаться как от аппаратных (сбои диска, ошибки ОЗУ), так и от программных (ошибки, неожиданные исключения) ошибок. Оба распространены и ожидаемы.
Можно ли запустить редукторы, пока некоторые мапперы еще работают? Зачем?
Нет. Вход редуктора сгруппирован по ключу. Последний маппер теоретически может произвести ключ, уже использованный при работе редуктора.
Определить отставшего.
Straggler — это либо карта, либо задача сокращения, выполнение которой занимает необычно много времени.
Что такое спекулятивное выполнение (также называемое задачами резервного копирования)? Какую проблему это решает?
Идентичная копия одной и той же задачи выполняется на нескольких узлах. Вывод самой быстрой задачи.
Спекулятивное выполнение помогает, если задача медленная из-за проблем с оборудованием. Это не помогает, если распределение значений по ключам искажено.
2.4 Разделители и объединители
Что делает разделитель?
Секционер разделяет пары ключ / значение, созданные задачами карты, между редукторами.
Что делает комбинатор?
Combiner выполняет локальную агрегацию пар ключ / значение, созданных картографом до или во время фазы челнока и сортировки. В целом, это уменьшает объем данных, передаваемых между узлами.
Каркас решает, сколько раз его запустить. Комбинатор может работать ноль, один или несколько раз на одном входе.
Решите, является ли утверждение истинным или ложным: каждый объединитель запускается ровно один раз.
Ложь. Каркас решает, работает ли объединитель ноль, один раз или несколько раз.
2.5 Распределенная файловая система
Кратко опишите архитектуру HDFS.
HDFS имеет один наменод и множество датододов. Namenode является главным и координирует файловые операции, обеспечивает целостность системы и сохраняет пространство имен (метаданные, структуру каталогов, отображение файлов в блоки и т. Д.).
Данные хранятся в больших блоках на узлах данных. Каждый блок хранится на нескольких, по умолчанию трех, узлах данных. Имя узла проверяет, правильно ли работают узлы данных и управляет репликацией данных.
Клиентский узел имени контакта, который отвечает с идентификатором блока данных и идентификатором узла данных. Затем узел данных отправляет данные непосредственно клиенту.
Решите, является ли утверждение истинным или ложным: HDFS хороша для управления большим количеством маленьких файлов.
Ложь. HDFS хорош в управлении большими файлами.
2.6 Кластерная архитектура Hadoop
Объясните разницу между JobTracker и TaskTracker?
Клиент выполняет задания на трекере. Jobtracker работает на мастера. Jobtracker отслеживает рабочие места MapReduce. Он также координирует картографы и редукторы.
Tasktracker запускает как пользовательский код, так и демон данных на подчиненных узлах. Это никогда не связывается с клиентом.
Объясните жизненный цикл картографа.
Метод инициализации вызывается до вызова любого другого метода. У него нет параметров и нет вывода.
Метод карты вызывается отдельно для каждой пары ключ / значение. Он обрабатывает пары ключ / значение и выдает промежуточные пары ключ / значение.
Метод Close запускается после обработки всего входного ключа / значения. Метод должен закрыть все открытые ресурсы. Он также может испускать пары ключ / значение.
Объясните жизненный цикл редуктора.
Метод инициализации вызывается до вызова любого другого метода. У него нет параметров и нет вывода.
Метод Reduce вызывается отдельно для каждой пары ключ / [список значений]. Он обрабатывает промежуточные пары ключ / значение и испускает окончательные пары ключ / значение. Его ввод является ключом и итератором для всех промежуточных значений, связанных с одним и тем же ключом.
Метод Close запускается после обработки всего входного ключа / значения. Метод должен закрыть все открытые ресурсы. Он также может испускать пары ключ / значение.
3 Разработка алгоритма MapReduce
3.1 Локальная агрегация
Что такое локальная агрегация и почему она используется?
Объединитель или преобразователь объединяет пары ключ / значение с одним и тем же ключом. Они могут также выполнять дополнительную предварительную обработку комбинированных значений. Объединяются только пары ключ / значение, созданные одним и тем же сопоставителем.
Пары «ключ / значение», создаваемые задачами карты, передаются между узлами на этапах перемешивания и сортировки. Локальная агрегация уменьшает объем передаваемых данных.
Если распределение значений по ключам искажено, предварительная обработка данных в объединителе помогает устранить количество отставших.
Что такое комбинирование в Mapper? Назовите преимущества и недостатки по сравнению с написанием пользовательского объединителя.
Локальная агрегация (объединение пар ключ / значение) выполняется внутри картографа.
Метод map не генерирует пары ключ / значение, он только обновляет внутреннюю структуру данных. Метод Close объединяет и предварительно обрабатывает все сохраненные данные и генерирует окончательные пары ключ / значение. Внутренняя структура данных инициализируется в методе init.
Преимущества:
- Это будет работать ровно один раз. Комбинатор может работать несколько раз или не работать вообще.
- Мы уверены, что он будет работать во время фазы карты. Комбинатор может работать либо после фазы карты, либо перед фазой уменьшения. Последний случай не обеспечивает сокращения передаваемых данных.
- Комбинирование в картографе обычно более эффективно. Combiner не уменьшает объем данных, создаваемых сопоставителями, он только группирует сгенерированные данные вместе. Это вызывает ненужное создание, уничтожение, сериализацию и десериализацию объектов.
Недостатки:
- Узкое место масштабируемости: метод зависит от наличия достаточного количества памяти для хранения всех частичных результатов. Мы должны регулярно сбрасывать частичные результаты, чтобы избежать этого. Использование Combiner не создает узких мест для масштабируемости.
3.2 Пары и полосы
Объясните шаблон дизайна пар на примере совместного вхождения. Включите преимущества / недостатки по сравнению с подходом Stripes, возможные оптимизации и их эффективность.
Mapper генерирует ключи, составленные из пар слов, которые произошли вместе. Значение содержит число 1. Каркас группирует пары ключ / значение с одинаковыми рабочими парами, а редуктор просто подсчитывает числовые значения для каждой входящей пары ключ / значение.
Каждая последняя пара кодирует ячейку в матрице совместного использования. Можно использовать локальное агрегирование, например, объединение в объединении или объединении в преобразователе.
Преимущества:
- Простые значения, меньше издержек сериализации / десериализации.
- Упрощенное управление памятью. Нет узких мест в масштабируемости (только если будет использоваться оптимизация в картографе).
Недостатки:
- Огромное количество промежуточных пар ключ / значение. Фаза перемешивания и сортировки медленнее.
- Локальная агрегация менее эффективна — слишком много разных ключей.
Объясните шаблон дизайна Stripes на примере совместного вхождения. Включите преимущества / недостатки по сравнению с подходом Pairs, возможные оптимизации и их эффективность.
Mapper генерирует отдельный ключ от каждого встреченного слова. Связанное значение содержит карту всех совместно встречающихся слов в качестве ключей карты и количество совпадений в качестве значений карты. Каркас объединяет одни и те же слова, а редуктор объединяет карты значений.
Каждая последняя пара кодирует строку в матрице совместного использования. Можно использовать комбинирование или комбинирование в картографе.
Преимущества:
- Небольшое количество промежуточных пар ключ / значение. Фаза перемешивания и сортировки выполняется быстрее.
- Промежуточные ключи меньше.
- Эффективная локальная агрегация — меньшее количество различных ключей.
Недостатки:
- Сложные значения, дополнительные издержки сериализации / десериализации.
- Более сложное управление памятью. Поскольку карты значений могут стать слишком большими, этот подход может стать узким местом для масштабируемости.
Объясните узкое место масштабируемости, вызванное полосным подходом.
Решение Stripes хранит карту совмещенных слов в памяти. Так как количество встречающихся слов не ограничено, размер карты тоже не ограничен. Огромная карта не помещается в память и вызывает ошибки подкачки или нехватки памяти.
3.3 Вычисление относительных частот
Относительные частоты проблемы совпадений:
Input: text documents
key: document id
value: text document Output: key/value pairs where
key: pair(word1, word2)
value: #co-occurrences(word1, word2)/#co-occurrences(word1, any word)
Input: text documents
key: document id
value: text document Output: key/value pairs where
key: pair(word1, word2)
value: #co-occurrences(word1, word2)/#co-occurrences(word1, any word)
Исправьте следующее решение для относительной частоты проблемы совпадений:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class MAPPER method INITIALIZE H = new hash map method MAP(docid a, doc d) for all term w in doc d do for all term u patri neighbors(w) do H(w) = H(w) + 1 emit(pair(u, w), count 1) method CLOSE for all term w in H emit(pair(w, *), H(w)) class REDUCER variable total_occurrences = 0 method REDUCE(pair (p, u), counts[c1, c2, ..., cn]) s = 0 for all c in counts[c1, c2, ..., cn] do s = s + c if u = * total_occurrences = s else emit(pair p, s/total_occurrences)class SORTING_COMPARATOR method compare(key (p1, u1), key (p2, u2)) if p1 = p2 AND u1 = * return key1 is lower if p1 = p2 AND u2 = * return key2 is lower return compare(p1, p2) |
Секционер отсутствует, фреймворк может отправлять пары ключ / значение с итогами в другой редуктор, чем ключ / пары с парами слов.
|
1
2
3
4
5
6
|
class PARTITIONING_COMPARATOR method compare(key (p1, u1), key (p2, u2)) if p1 = p2 return keys are equal return keys are different |
Опишите порядок проектирования инверсии заказа .
Инверсия порядка используется, если алгоритм требует двух проходов через сгенерированные маппером пары ключ / значение с одним и тем же ключом. Первый проход генерирует некоторую общую статистику, которая затем применяется к данным во время второго прохода. Редуктор должен будет буферизовать данные в памяти, чтобы иметь возможность дважды проходить через них.
Результат первого прохода вычисляется картографами и сохраняется в некоторой внутренней структуре данных. Преобразователь генерирует результат в методе закрытия после всех обычных промежуточных пар ключ / значение.
Шаблон требует пользовательского разбиения и сортировки. Результат первого прохода должен прийти к редуктору раньше, чем обычные пары ключ / значение. Конечно, это должно прийти к тому же редуктору.
3.4 Вторичная сортировка
Опишите шаблон проектирования «значение к ключу».
Реализация Hadoop не обеспечивает сортировку сгруппированных значений во входных данных редукторов. Значение для ключа используется в качестве обходного пути.
Часть значения добавляется к ключу. Затем пользовательская сортировка сортирует первичную по ключу и вторичную по добавленной стоимости. Пользовательский разделитель должен переместить все данные с одинаковым исходным ключом в один и тот же редуктор.
3.5 реляционные соединения
Опишите сокращение бокового соединения между таблицами с отношением один на один.
Mapper создает пары ключ / значение с идентификаторами соединений в качестве ключей и значениями строк в качестве значений. Соответствующие строки из обеих таблиц сгруппированы по каркасу во время перемешивания и сортировки.
Метод Reduce в Reducer получает идентификатор соединения и два значения, каждое из которых представляет строку из одной таблицы. Редуктор соединяет данные.
Опишите сокращение бокового соединения между таблицами с отношением один-ко-многим.
Мы предполагаем, что ключ соединения является первичным ключом в таблице с именем S. Вторая таблица называется T. Другими словами, таблица S находится на стороне «one» отношения, а таблица T — на стороне «many» отношения.
Мы должны реализовать mapper, пользовательский сортировщик, разделитель и редуктор.
Mapper создает ключ, состоящий из идентификатора соединения и флага таблицы. Partitioner разделяет данные таким образом, что все пары ключ / значение с одинаковым идентификатором соединения переходят в один и тот же редуктор. Пользовательская сортировка помещает пару ключ / значение, сгенерированную из таблицы S, прямо перед парой ключ / значение с тем же идентификатором соединения из таблицы T.
Вход редуктора выглядит так:
((JoinId1, s)-> row)
((JoinId1, t)-> [rows])
((JoinId2, s)-> row)
((JoinId2, t)-> [rows])
...
((JoinIdn, s), row)
((JoinIdn, t), [rows])
Редуктор соединяет все строки из пары s со всеми строками из следующей пары t .
Опишите сокращенное боковое соединение между таблицами с отношением «многие ко многим».
Мы предполагаем, что данные хранятся в таблицах, называемых S и T. Таблица S меньше. Мы должны реализовать mapper, пользовательский сортировщик, разделитель и редуктор.
Mapper создает ключ, состоящий из идентификатора соединения и флага таблицы. Partitioner разделяет данные таким образом, что все пары ключ / значение с одинаковым идентификатором соединения переходят в один и тот же редуктор. Пользовательская сортировка помещает пары ключ / значение, сгенерированные из таблицы S, прямо перед всеми парами ключ / значение с данными из таблицы T.
Вход редуктора выглядит так:
((JoinId1, s)-> [rows])
((JoinId1, t)-> [rows])
((JoinId2, s)-> [rows])
((JoinId2, t)-> [rows])
...
((JoinIdn, s), [rows])
((JoinIdn, t), [rows])
Редуктор буферизует все строки с одинаковым JoinId из таблицы S в память и объединяет их со следующими T-строками таблицы.
Все данные из таблицы меньшего размера должны помещаться в память — алгоритм имеет проблему узкого места масштабируемости.
Опишите соединение на стороне карты между двумя таблицами базы данных.
Объединение на стороне карты работает, только если выполняются следующие допущения:
- оба набора данных отсортированы по ключу соединения,
- оба набора данных разделены одинаково.
Mapper отображает более большой набор данных и считывает соответствующую часть меньшего набора данных в Mapper. Поскольку меньший набор разделен так же, как и больший, только одна задача карты получает доступ к одним и тем же данным. Поскольку данные сортируются по ключу соединения, мы можем выполнить объединение O(n) .
Опишите объединение с поддержкой памяти.
Меньший набор данных загружается в память каждого преобразователя. Мапперы перебирают больший набор данных и соединяют его с данными в памяти. Если меньший набор слишком велик для размещения в памяти, набор данных загружается в memcached или какое-либо другое решение для кэширования.
Какой из них быстрее? Соединение на стороне карты или уменьшение на стороне?
Соединение со стороной карты быстрее.
Ссылка: MapReduce Вопросы и ответы от нашего партнера по JCG Марии Юрковичовой в блоге This Is Stuff .