Технология построения защищенных распределенных приложений
жүктеу/скачать 0.74 Mb. Pdf көрінісі
|
| Рисунок 1 — Упрощенная схема потоков данных в парадигме MapReduce
// Функция, используемая исполнителями на Reduce-фазе // для обрабоки пар ключ-значение, полученных на Map-шаге void reduce(String word, Iterator partialCounts): // Входные данные: // word - слово // partialCounts - список группированных промежуточных результатов. // Количество записей в partialCounts и есть требуемое значение int result = 0; for each v in partialCounts: result += parseInt(v); Emit(AsString(result)); В этом коде на map-фазе каждый документ разбивается на слова, и возвращаются пары, где ключом является само слово, а значением — «1». Если в документе одно и то же слово встречается несколько раз, то в результате предварительной обработки этого документа будет столько же этих пар, сколько раз встретилось это слово. Далее выполняется объединение всех пар с одинаковым ключом, и они передаются на вход функции reduce, которой остается сложить их, чтобы получить общее количество вхождений данного слова во все документы. Созданная в Google конструкция MapReduce делает примерно то же, но по отношению к гигантским объемам данных. В этом случае map – это функция запроса от пользователя, помещенная в библиотеку MapReduce. Ее работа сводится к выбору входной пары, ее обработке и формированию результата в виде значения и некоторого промежуточного ключа, служащего указателем для reduce. Конструкция MapReduce собирает вместе все значения с одинаковыми промежуточными ключами и передает их в функцию reduce, также написанную пользователем. Эта функция воспринимает промежуточные значения, каким-то образом их собирает и воспроизводит результат, скорее всего выраженный меньшим количеством значений, чем входное множество. Теперь свяжем функциональную идею MapReduce со схемой SPMD. Вызовы map распределяются между множеством машин путем деления входного потока данных на М срезов (splits или shard), каждый срез 10 обрабатывается на отдельной машине. Вызовы reduce распределены на R частей, количество которых определяется пользователем. При вызове функции из библиотеки MapReduce выполняется примерно такая последовательность операций (рисунок 2): 1) входные файлы разбиваются на срезы размером от 16 до 64 Мбайт каждый, и на кластере запускаются копии программы. Одна из них менеджер, а остальные – исполнители. Всего создается M задач map и R задач reduce. Поиском свободных узлов и назначением на них задач занимается менеджер; 2) в процессе исполнения исполнители, назначенные на выполнение задачи map, считывают содержимое соответствующих срезов, осуществляют их грамматический разбор, выделяют отдельные пары «ключ и соответствующее ему значение», а потом передают эти пары в обрабатывающую их функцию map. Промежуточное значение в виде идентификатора и значения буферизуется в памяти; 3) периодически буферизованные пары сбрасываются на локальный диск, разделенный на R областей. Расположение этих пар передается менеджеру, который отвечает за дальнейшую передачу этих адресов исполнителям, выполняющим reduce; 4) исполнители, выполняющие задачу reduce, ждут сообщения от менеджера о местоположении промежуточных пар. По его получении они, используя процедуры удаленного вызова, считывают буферизованные данные с локальных дисков тех исполнителей, которые выполняют map. Загрузив все промежуточные данные, исполнитель сортирует их по промежуточным ключам и, если есть необходимость, группирует; Пользовательская программа Менеджер Исполнитель Исполнитель (4) локальная запись Исполнитель Исполнитель Исполнитель Срез 0 Срез 1 Срез 2 Срез 3 Срез 4 (5) удаленное чтение (3) чтение Выход 0 Выход 1 (6) запись (2) назначение reduce (2) назначение map (1) ветвление (1) ветвление (1) ветвление Входные файлы Фаза Map Промежуточные файлы локальных дисках Фаза Reduce Выходные файлы Рисунок 2 — Ход выполнения вызова MapReduce 11 5) исполнитель обрабатывает данные по промежуточным ключам и передает их в соответствующую функцию reduce для вывода результатов; 6) когда все задачи map и reduce завершаются, конструкция MapReduce возобновляет работу вызывающей программы и та продолжает выполнять пользовательский код. Одно из важнейших преимуществ этой, замысловатой на первый взгляд, конструкции состоит в том, что она позволяет надежно работать на платформах с низкими показателями надежности. Для обнаружения потенциальных сбоев менеджер периодически опрашивает исполнителей, и, если какой-то из них задерживается с ответом сверх заданного норматива, менеджер считает его дефектным и передает исполнение на свободные узлы. Различие между задачами map и reduce в данном случае состоит в том, что map хранит промежуточные результаты на своем диске, и выход из строя такого узла приводит к их потере и требует повторного запуска, а reduce хранит свои данные в глобальном хранилище. жүктеу/скачать 0.74 Mb. Достарыңызбен бөлісу:
|