КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Общая модель программирования 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 можно было бы объединить с производительностью параллельных систем баз данных. В следующих разделах мы опишем свою попытку построить такую гибридную систему.
Дата добавления: 2015-01-03; Просмотров: 365; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |