Вчера я задал вопрос в своем ХабраБлоге — интересно ли людям узнать, что такое Hadoop с точки зрения его реального применения? Оказалось, интересно. Дело недолгое — статью я написал довольно быстро (по крайней мере, ее первую часть) — как минимум, потому, что уже давно знал, о чем собираюсь написать (потому как еще неплохо помню как я сам тыкался в поиске информации, когда начинал пользоваться Hadoop). В первой статье речь пойдет об основах — но совсем не о тех, про которые обычно рассказывают :-)
Перед прочтением статьи я настоятельно рекомендую изучить как минимум первый и последний источники из списка для чтения — их понимание или хотя бы прочтение практически гарантирует, что статья будет понята без проблем. Ну что, поехали?
Ну скажите, какой смысл об этом писать? Уже не раз это проговаривалось, неоднократно начинали писаться посты на тему Hadoop, HDFS и прочая. К сожалению, обычно все заканчивалось на довольно пространном введении и фразе “Продолжение следует”. Так вот: это — продолжение. Кому-то тема, затрагиваемая в этой статье может показаться совершенно тривиальной и неинтересной, однако же лиха беда начало — любые сложные задачи надо решать по частям. Это утверждение, в частности, мы и реализуем в ходе статьи. Сразу замечу, что я постараюсь избежать написания кода в рамках этой конкретной статьи — это может подождать, а понять принципы построения программ, работающих с Map/Reduce можно и “на кошках” (к тому же с текущей частотой кардинального изменения API Hadoop любой код становится obsolete примерно через месяц).
Когда я начинал разбираться с Хадупом, очень большой сложностью лично для меня стало первоначальное понимание идеологии Map/Reduce (я предпочитаю писать это словосочетание именно так, чтобы подчеркнуть, что речь идет не о продукте, а о принципе). Суть и ценность метода станет понятна в самом конце — после того, как мы решим несложную задачу.
Для начала сделаем допущение (для упрощения, а позже мы рассмотрим как решать эту задачу в более общем случае) что наши входные данные представлены в формате текстового файла с очень простой структурой:
Иными словами, каждый документ — это набор слов, которые возможно (и вполне вероятно) повторяются, и каждый такой набор слов расположен на одной строке текстового файла. Допущение это небольшое — практически каждый документ может быть представлен в таком виде.
Подсчет количества слов в корпусе — задача простая, и решается в линейное время, однако, возможно, ее даже не придется решать отдельно. То же самое касается и количества терминов — они посчитаются сами. Самая интересная задача на этом этапе — посчитать, сколько раз каждый термин встречается в корпусе текста.
Да-да, вы не ошибаетесь, это именно она — самая популярная и замученная уже всеми задача, первый пример в каждом руководстве по Hadoop — программа WordCount. Она настолько популярна, насколько же и проста — я даже не буду приводить ее здесь, ее можно посмотреть в официальном tutorial’е Хадупа. Если очень кратко, то на map-шаге программа формирует следующие пары:
На reduce-шаге каждый reduce-task получает ключ (то есть <term1>, <term2> и так далее) и список всех значений ассоциированных с этим ключем, полученных из всех map-задач (в данном случае — просто список единиц). Это будет выглядеть как:
Суммируя эти единицы (а по факту — просто считая количество элементов в списке) мы получаем количество вхождений каждого термина в корпус:
Это уже что-то, хотя ценность этих данных неочевидна. Однако простой подсчет количества строк в результирующем файле дает нам количество уникальных терминов. А суммируя все значения из второй колонки мы получаем общее количество токенов. Вроде бы ничего и не сделали — а уже получили несколько фундаментальных характеристик корпуса.
Дальше начинается классика 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?
Ну скажите, какой смысл об этом писать? Уже не раз это проговаривалось, неоднократно начинали писаться посты на тему 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
Суммируя эти единицы (а по факту — просто считая количество элементов в списке) мы получаем количество вхождений каждого термина в корпус:
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: я же сказал, что продолжение следует? Ну так вот оно — это самое продолжение — читайте и комментируйте!
