Реализация парадигмы MapReduce на языке Си с использованием возможностей многозадачности UNIX-подобных ОС.
cmapreduce состоит из следующих базовых модулей:
- split - распределяет входные данные по узлам Map
- map - обеспечивает функционирование узлов Map (запуск узлов, передача входных данных)
- shuffle - распределяет полученные от узлов Map пары "ключ-значение" по узлам Reduce
- reduce - обеспечивает функционирование узлов Reduce
- merge - слияние данных, полученных от узлов Reduce
Для map также реализована внутренняя подключаемая "обёртка", позволяющая использовать утилиты UNIX в качестве обработчиков.
./cmapreduce -M "программа-mapper" -R "программа-reducer" [аргументы] <список входных файлов>
- -h, --help - вывод справочного сообщения и выход из программы
- -m, --num_map=n - желаемое число узлов Map
- -r, --num_reduce=n - желаемое число узлов Reduce
- -S. --split="программа-сплиттер" - внешний сплиттер
Управление UNIX-обёрткой для map
- --unix-mapper - подключение обёртки для map
- --unix-mapper-delim="delims" - установка набора символов-разделителей
- --unix-mapper-value="value" - установка значения по умолчанию для ключей
Модуль split распределяет входные данные между узлами Map. Есть два варианта запуска процедуры split:
- внутренний - входные данные разбиваются по простейшему алгоритму: один файл делится по строкам поровну между map-нодами, несколько файлов - в расчёте по одному на каждую ноду.
- внешний - запускается внешняя программа split, которой в качестве последних N аргументов передаётся N имён входных файлов, переданных через интерфейс cmapreduce
В результате процедуры split формируется набор структур, описывающих фрагменты (chunks) файлов для раздачи узлам Map.
Внешняя программа split получает список входных файлов через последние аргументы командной строки и должна в качестве выхода вернуть набор строк следующего формата:
имя_файла старт длина
- старт - начальная позиция в файле (в байтах)
- длина - длина фрагмента файла (в байтах)
Модуль map создаёт узлы Map, UNIX-обёртки (при необходимости) и пересылает этим узлам соответствующие входные данные.
Входные данные каждого узла - "сырые" данные из файлов согласно разбивке (split)
Выходные данные - пары "ключ-значение", записанные в следующем формате:
w[длина_пакета] [длина_ключа] [ключ][значение]
Первый символ необходим для синхронизации и не должен быть пропущен. Сразу за этим символом следуют два числа в текстовом представлении, разделённые между собой пробелом. За последним числом следует один пробел, затем без разелителя подряд передаются ключ и значение.
Длина пакета - сумма длин ключа и значения (длина чисел и начальный символ не включаются).
При подключении UNIX-обёртки, выходные данные узла - поток слов, разделённых любыми из настроенных разделителей. Обёрткой к ним будут прикреплены значения по умолчанию, и так будут сформированы пакеты.
Модуль shuffle группирует полученные от узлов Map пакеты по ключу и раздаёт полученные пары "ключ-значения" узлам Reduce.
Группировка данных происходит в хэш-таблице в оперативной памяти.
Передача пар "ключ-значения" к узлам Reduce происходит в следующем формате:
w[длина_ключа] [ключ] [число_значений] [длина_1] [значение_1] [[длина_2] [значение_2] ... ]
Между всеми значениями по 1 разделительному пробелу.
Модуль reduce создаёт узлы Reduce и настраивает потоки ввода-вывода для них. Далее эти потоки используются для передачи данных от shuffle и приёма данных в merge. Узлы Reduce принимают на вход пары "ключ-значения" и выдают на выходе строки результата.
Модуль merge принимает строки от узлов Reduce и выводит их по одной в стандартный поток вывода.