Вчера я задал вопрос в своем ХабраБлоге — интересно ли людям узнать, что такое Hadoop с точки зрения его реального применения? Оказалось, интересно. Дело недолгое — статью я написал довольно быстро (по крайней мере, ее первую часть) — как минимум, потому, что уже давно знал, о чем собираюсь написать (потому как еще неплохо помню как я сам тыкался в поиске информации, когда начинал пользоваться Hadoop). В первой статье речь пойдет об основах — но совсем не о тех, про которые обычно рассказывают :-)
Перед прочтением статьи я настоятельно рекомендую изучить как минимум первый и последний источники из списка для чтения — их понимание или хотя бы прочтение практически гарантирует, что статья будет понята без проблем. Ну что, поехали?
![](http://romankirillov.info/images/hadoop-elephant-small-rgb.png)
Ну скажите, какой смысл об этом писать? Уже не раз это проговаривалось, неоднократно начинали писаться посты на тему Hadoop, HDFS и прочая. К сожалению, обычно все заканчивалось на довольно пространном введении и фразе “Продолжение следует”. Так вот: это — продолжение. Кому-то тема, затрагиваемая в этой статье может показаться совершенно тривиальной и неинтересной, однако же лиха беда начало — любые сложные задачи надо решать по частям. Это утверждение, в частности, мы и реализуем в ходе статьи. Сразу замечу, что я постараюсь избежать написания кода в рамках этой конкретной статьи — это может подождать, а понять принципы построения программ, работающих с Map/Reduce можно и “на кошках” (к тому же с текущей частотой кардинального изменения API Hadoop любой код становится obsolete примерно через месяц).
Когда я начинал разбираться с Хадупом, очень большой сложностью лично для меня стало первоначальное понимание идеологии Map/Reduce (я предпочитаю писать это словосочетание именно так, чтобы подчеркнуть, что речь идет не о продукте, а о принципе). Суть и ценность метода станет понятна в самом конце — после того, как мы решим несложную задачу.
Для начала сделаем допущение (для упрощения, а позже мы рассмотрим как решать эту задачу в более общем случае) что наши входные данные представлены в формате текстового файла с очень простой структурой:
Иными словами, каждый документ — это набор слов, которые возможно (и вполне вероятно) повторяются, и каждый такой набор слов расположен на одной строке текстового файла. Допущение это небольшое — практически каждый документ может быть представлен в таком виде.
Подсчет количества слов в корпусе — задача простая, и решается в линейное время, однако, возможно, ее даже не придется решать отдельно. То же самое касается и количества терминов — они посчитаются сами. Самая интересная задача на этом этапе — посчитать, сколько раз каждый термин встречается в корпусе текста.
Да-да, вы не ошибаетесь, это именно она — самая популярная и замученная уже всеми задача, первый пример в каждом руководстве по Hadoop — программа WordCount. Она настолько популярна, насколько же и проста — я даже не буду приводить ее здесь, ее можно посмотреть в официальном tutorial’е Хадупа. Если очень кратко, то на map-шаге программа формирует следующие пары:
На reduce-шаге каждый reduce-task получает ключ (то есть <term1>, <term2> и так далее) и список всех значений ассоциированных с этим ключем, полученных из всех map-задач (в данном случае — просто список единиц). Это будет выглядеть как:
![](http://romankirillov.info/images/mr_whiteboard.jpg)
Суммируя эти единицы (а по факту — просто считая количество элементов в списке) мы получаем количество вхождений каждого термина в корпус:
Это уже что-то, хотя ценность этих данных неочевидна. Однако простой подсчет количества строк в результирующем файле дает нам количество уникальных терминов. А суммируя все значения из второй колонки мы получаем общее количество токенов. Вроде бы ничего и не сделали — а уже получили несколько фундаментальных характеристик корпуса.
Дальше начинается классика information retrieval. Для начала на основе результатов работы
Reduce для этой задачи будет идентичен классическому
Так что же у нас получилось? А получилась у нас так называемая частота терминов — которую гораздо лучше знают как term frequency, сокращенно — tf(t,d) (здесь t и d означают, что значение считается применимо к конкретному документу и конкретному термину). К примеру, в статье про Лондон значение tf для слова
В рамках нашего примера мы разработали алгоритм вычисления одной из наиболее популярных статистических характеристик в information retrieval. Ценность данного метода в том, что он может быть расширен на корпус практически любого размера — и это можно будет посчитать даже на одной машине (а можно без дополнительных усилий распараллелить на кластер в полторы-две тысячи нодов). Таким образом, ответ на вопрос, сформулированный в самом начале статьи звучит так: идеология Map/Reduce позволяет разбить вычислительно сложную задачу на маленькие блоки, которые можно посчитать отдельно, после чего объединить результаты. Эти блоки могут считаться параллельно, могут — последовательно и это не имеет никакого значения: суть в том, что мы превратили одну крайне ресурсоемкую задачу в большое количество задач, каждая из которых может быть решена на вашем домашнем компьютере.
Пожалуй, здесь мне все-таки следует произнести сакральную фразу — “Продолжение следует”. В следующем посте мы рассмотрим расчет второй части tf-idf — а именно, inverse document frequency, после чего плавно перейдем к решению этой задачи для реального большого (никому мало не покажется) набора данных.
P.S. Маленькое примечание, которое мне показалось важным: при написании русской версии статьи (а она изначально писалась практически параллельно на двух языках) я старался писать настолько по-русски, насколько это только возможно, однако я не переводил многие устойчивые сочетания (такие как Map/Reduce) и даже не пытался перевести названия фаз этого процесса, оттуда появились map-таски и reduce-таски. К сожалению, русская терминология не вполне устоялась применимо к этому предмету, но великий и могучий настолько велик и могуч, что любой школьник может просклонять слово “таск” по падежам — не говоря уж о программистах, которые и представляют собой целевую аудиторию этого поста.
Если вам показалось что-то непонятным — пожалуйста, пишите. После того, как долго работаешь в какой-то сфере, мозги до какой-то степени “замыливаются” и многие вещи воспринимаешь как само собой разумеющееся. Если где-то это имело место быть — напишите, и я исправлюсь.
_________________________________________________________________
Список литературы для домашнего чтения:
Оригинал фотографии был опубликован по лицензии Creative Commons: www.flickr.com/photos/antichrist/3427853501
Update: поскольку НЛО временно отключило возможность создавать новые блоги, опубликовал в алгоритмах — в конце концов, Hadoop это далеко не единственная реализация Map/Reduce, а ни одной строчки кода здесь нет. Когда НЛО смилостивится, создам блог Hadoop и перенесу туда вместе с новыми статьями, которые сейчас пишутся.
Update 2: я же сказал, что продолжение следует? Ну так вот оно — это самое продолжение — читайте и комментируйте!
Перед прочтением статьи я настоятельно рекомендую изучить как минимум первый и последний источники из списка для чтения — их понимание или хотя бы прочтение практически гарантирует, что статья будет понята без проблем. Ну что, поехали?
Что такое Hadoop?
![](http://romankirillov.info/images/hadoop-elephant-small-rgb.png)
Ну скажите, какой смысл об этом писать? Уже не раз это проговаривалось, неоднократно начинали писаться посты на тему Hadoop, HDFS и прочая. К сожалению, обычно все заканчивалось на довольно пространном введении и фразе “Продолжение следует”. Так вот: это — продолжение. Кому-то тема, затрагиваемая в этой статье может показаться совершенно тривиальной и неинтересной, однако же лиха беда начало — любые сложные задачи надо решать по частям. Это утверждение, в частности, мы и реализуем в ходе статьи. Сразу замечу, что я постараюсь избежать написания кода в рамках этой конкретной статьи — это может подождать, а понять принципы построения программ, работающих с Map/Reduce можно и “на кошках” (к тому же с текущей частотой кардинального изменения API Hadoop любой код становится obsolete примерно через месяц).
Когда я начинал разбираться с Хадупом, очень большой сложностью лично для меня стало первоначальное понимание идеологии Map/Reduce (я предпочитаю писать это словосочетание именно так, чтобы подчеркнуть, что речь идет не о продукте, а о принципе). Суть и ценность метода станет понятна в самом конце — после того, как мы решим несложную задачу.
- Количество слов в корпусе
- Количество терминов в корпусе (под термином здесь и далее я буду понимать уникальное слово-токен)
- Количество документов в корпусе
- Сколько раз каждый термин встречается в каждом документе
- Сколько документов содержит каждый термин.
Для начала сделаем допущение (для упрощения, а позже мы рассмотрим как решать эту задачу в более общем случае) что наши входные данные представлены в формате текстового файла с очень простой структурой:
<w11> <w12> <w13> ... <w1N> <w21> <w22> <w23> ... <w2M> ...
Иными словами, каждый документ — это набор слов, которые возможно (и вполне вероятно) повторяются, и каждый такой набор слов расположен на одной строке текстового файла. Допущение это небольшое — практически каждый документ может быть представлен в таком виде.
Подсчет количества слов в корпусе — задача простая, и решается в линейное время, однако, возможно, ее даже не придется решать отдельно. То же самое касается и количества терминов — они посчитаются сами. Самая интересная задача на этом этапе — посчитать, сколько раз каждый термин встречается в корпусе текста.
Да-да, вы не ошибаетесь, это именно она — самая популярная и замученная уже всеми задача, первый пример в каждом руководстве по Hadoop — программа WordCount. Она настолько популярна, насколько же и проста — я даже не буду приводить ее здесь, ее можно посмотреть в официальном tutorial’е Хадупа. Если очень кратко, то на map-шаге программа формирует следующие пары:
map1: <term1> 1 <term2> 1 <term3> 1 map2: <term2> 1 <term3> 1 <term3> 1 map3: <term1> 1 ...
На reduce-шаге каждый reduce-task получает ключ (то есть <term1>, <term2> и так далее) и список всех значений ассоциированных с этим ключем, полученных из всех map-задач (в данном случае — просто список единиц). Это будет выглядеть как:
<term1> 1,1 <term2> 1,1 <term3> 1,1,1
![](http://romankirillov.info/images/mr_whiteboard.jpg)
Суммируя эти единицы (а по факту — просто считая количество элементов в списке) мы получаем количество вхождений каждого термина в корпус:
the 19283 to 3432 from 343 ... ... london 14
Это уже что-то, хотя ценность этих данных неочевидна. Однако простой подсчет количества строк в результирующем файле дает нам количество уникальных терминов. А суммируя все значения из второй колонки мы получаем общее количество токенов. Вроде бы ничего и не сделали — а уже получили несколько фундаментальных характеристик корпуса.
Дальше начинается классика information retrieval. Для начала на основе результатов работы
WordCount
мы строим словарь — то есть общий список терминов корпуса. Наша следующая задача — установить, как часто и какие именно термины словаря встречаются в каждом из документов. Для этого мы реализуем уже немного модифицированный вариант WordCount
, который считает количество терминов применимо к конкретному документу. Наверное, самый простой способ добиться этого — это использовать в результатах map-задач ключ, состоящий из идентификатора документа (входной ключ mapper’а) и термина:map1: 1_the 1 1_the 1 1_the 1 1_to 1 ... map2: 2_the 1 2_the 1 2_from 1 ... map3: 37_london 1 ...
Reduce для этой задачи будет идентичен классическому
WordCount
— он будет просто суммировать значения с одинаковым ключем. В результате мы получим:1_the 3 1_to 1 ... 2_the 2 2_from 1 ... 37_london 1
Так что же у нас получилось? А получилась у нас так называемая частота терминов — которую гораздо лучше знают как term frequency, сокращенно — tf(t,d) (здесь t и d означают, что значение считается применимо к конкретному документу и конкретному термину). К примеру, в статье про Лондон значение tf для слова
london
будет, вероятно, выше, чем в статье про свиноводство (а возможно, будет равным нулю — нулевая частота это тоже частота). Вероятно, надо заметить, что у нас получился ненормализованный вариант этой характеристики, для нормализации полученные значения следует разделить на общее количество токенов в корпусе.В рамках нашего примера мы разработали алгоритм вычисления одной из наиболее популярных статистических характеристик в information retrieval. Ценность данного метода в том, что он может быть расширен на корпус практически любого размера — и это можно будет посчитать даже на одной машине (а можно без дополнительных усилий распараллелить на кластер в полторы-две тысячи нодов). Таким образом, ответ на вопрос, сформулированный в самом начале статьи звучит так: идеология Map/Reduce позволяет разбить вычислительно сложную задачу на маленькие блоки, которые можно посчитать отдельно, после чего объединить результаты. Эти блоки могут считаться параллельно, могут — последовательно и это не имеет никакого значения: суть в том, что мы превратили одну крайне ресурсоемкую задачу в большое количество задач, каждая из которых может быть решена на вашем домашнем компьютере.
Пожалуй, здесь мне все-таки следует произнести сакральную фразу — “Продолжение следует”. В следующем посте мы рассмотрим расчет второй части tf-idf — а именно, inverse document frequency, после чего плавно перейдем к решению этой задачи для реального большого (никому мало не покажется) набора данных.
P.S. Маленькое примечание, которое мне показалось важным: при написании русской версии статьи (а она изначально писалась практически параллельно на двух языках) я старался писать настолько по-русски, насколько это только возможно, однако я не переводил многие устойчивые сочетания (такие как Map/Reduce) и даже не пытался перевести названия фаз этого процесса, оттуда появились map-таски и reduce-таски. К сожалению, русская терминология не вполне устоялась применимо к этому предмету, но великий и могучий настолько велик и могуч, что любой школьник может просклонять слово “таск” по падежам — не говоря уж о программистах, которые и представляют собой целевую аудиторию этого поста.
Если вам показалось что-то непонятным — пожалуйста, пишите. После того, как долго работаешь в какой-то сфере, мозги до какой-то степени “замыливаются” и многие вещи воспринимаешь как само собой разумеющееся. Если где-то это имело место быть — напишите, и я исправлюсь.
_________________________________________________________________
Список литературы для домашнего чтения:
- Yahoo! Hadoop Tutorial — рекомендую прочитать первым, потому что лучше документации на данный момент просто нет, включая официальный сайт.
- Hadoop QuickStart Guide
- Hadoop Map/Reduce Tutorial
- Hadoop and Distributed Computing at Yahoo!
- Term frequency-inverse document frequency — статья в Wikipedia.
Оригинал фотографии был опубликован по лицензии Creative Commons: www.flickr.com/photos/antichrist/3427853501
Update: поскольку НЛО временно отключило возможность создавать новые блоги, опубликовал в алгоритмах — в конце концов, Hadoop это далеко не единственная реализация Map/Reduce, а ни одной строчки кода здесь нет. Когда НЛО смилостивится, создам блог Hadoop и перенесу туда вместе с новыми статьями, которые сейчас пишутся.
Update 2: я же сказал, что продолжение следует? Ну так вот оно — это самое продолжение — читайте и комментируйте!