Общая модель программирования MapReduce

В этой модели вычисления производятся над множествами входных пар "ключ-значение", и в результате каждого вычисления также производится некоторое множество результирующих пар "ключ-значение". Для представления вычислений в среде MapReduce используются две основные функции: Map и Reduce. Обе функции явно кодируются разрабочиками приложений в среде MapReduce.

Функция Map в цикле обрабатывает каждую пару из множества входных пар и производит множество промежуточных пар "ключ-значение". Среда MapReduce групирует все промежуточные значения с одним и тем же ключом I и передает их функции Reduce.

Функция Reduce получает значение ключа I и множество значений, связанных с этим ключом. В типичных ситуациях каждая группа обрабатывается (в цикле) таким образом, что в результате одного вызова функции образуется не более одного результирующего значения.

Инвертированный индекс (англ. inverted index) — структура данных, в которой для каждого слова коллекции документов в соответствующем списке перечислены все документы в коллекции, в которых оно встретилось. Инвертированный индекс используется для поиска по текстам.

Есть два варианта инвертированного индекса:

· индекс, содержащий только список документов для каждого слова,

· индекс, дополнительно включающий позицию слова в каждом документе

Пусть у нас есть корпус из трех текстов T0="it is what it is", T1="what is it" и T2="it is a banana", тогда инвертированный индекс будет выглядеть следующим образом:

"a": {2}

"banana": {2}

"is": {0, 1, 2}

"it": {0, 1, 2}

"what": {0, 1}

десь цифры обозначают номера текстов, в которых встретилось соответствующее слово.

Задача: составить список документов, в котором встречается заданное слово

Функция Map: читает документы и для каждого слова генерирует пары:

Ключ: слово

Значение: идентификатор документа

Функция Reduce объединяет данные для каждого слова и выдает пары:

Ключ: слово

Значение: список идентификаторов документов

Исходные данные: [(docid, content)...]

Требуемый результат: [(term, [<docid,tf>...])...]

Этап 1 - Параллельная обработка документов

(docid, content) → (term, [<docid1,tf1>,<docid2,tf2>...])

Этап 2 - Параллельная агрегация промежуточных

результатов для каждого терма

(term, [<docid1,tf1>,<docid2,tf2>...]) → (term, [<docid,tf>...])

Partition Определяет распределение промежуточных данных между reduce-процессами. Простейший случай: hash(k2) % num_reducers.

Сombine Осуществляет локальную агрегацию промежуточных данных после map() в рамках одного map-процесса. Для ассоциативных и коммутативных операций может использоваться reduce().

Сompare Определяет отношение порядка между промежуточными ключами.

+/- map reduce:

Модель программирования

Высокий уровень абстракции за счет скрытия деталей организации вычислений внутри библиотеки.

Позволяет разработчику сконцентрироваться на решаемой задаче.

Легкость добавления новых стадий обработки

Реализация

Автоматическое распараллеливание, распределение заданий и балансирование нагрузки

Устойчивость к отказам

Масштабируемость

Самой большой проблемой MapReduce является производительность. Поскольку от пользователей не требуется моделирование и загрузка данных до их обработки, использование многих упомянутых выше средств повышения производительности, применяемых в системах баз данных, в данном случае оказывается невозможным.

В идеальном случае отказоустойчивость и возможность функционировать в неоднородных средах MapReduce можно было бы объединить с производительностью параллельных систем баз данных. В следующих разделах мы опишем свою попытку построить такую гибридную систему.