VII Международная студенческая научная конференция Студенческий научный форум - 2015

Об актуальности

За последние годы проблема обработки больших массивов данных (Big Data) для мировых гигантов информационного пространства (Google, Fb, Alibaba etc.) вышла на передний план. Сервисы, предоставляемые крупными «поисковиками», социальными сетями, e-ритейлерами и другими обработчиками больших потоков информации перестали удовлетворять совершенствующимся стандартам качества (скорости обработки и хранения данных). Более того, проблема усугубляется ростом объемов, представленных к обработке, роста скорости обработки, требуемой рынком и увеличения информационного разнообразия, затрудняющего провайдерам использовать стандартные методы в алгоритмах обработки.

Согласно отчету McKinsey Institute «Большие данные – новый рубеж для инноваций, конкуренции и производительности», а аналитики TadInvest’a оценили CAPEX на разработку технологий работы с BigData в 34 млрд долл. за 2013 год. Все это подчеркивает актуальность методов и средств обработки больших массивов данных не только для списка 10-ти наиболее ликвидных мировых компаний TMT-сектора, но и для рядовых компаний-разработчиков программного обеспечения, «стремящихся на свет «голубого океана».

Ликбез

«Большие данные» или BigData можно представить в виде набора структурированной и не структурированной информации, «пакетно» организованной, размер которой превосходит возможности типичных БД (баз данных) по занесению, хранению, управлению и анализу информации. Другими словами, Big Data – это проблема для компаний, связанных с большими объемами данных. Проблему можно рассмотреть в трех проекциях: Volume – нестандартный объем данных, Velocity – высокие минимальные показатели скорости обработки информации и Variety – многообразие информации и отсутствие структурированности. От года к году BigData «растет» в каждой из этих проекций, что заставляет провайдеров уделять больше внимания на разработку технологий работы с данными.

Быстрая обработка петабайтов неструктурированных данных недоступна стандартным программным инструментам и средствам, с которыми рядовые пользователи сталкиваются в повседневной жизни, поэтому также под BigData понимают комплекс подходов и технологий (в том числе MapReduce), призванных оптимизировать результаты функционирования больших данных в каждой проекции. В основе таких подходов лежит система распределенных вычислений, в которой большие данные параллельно обрабатываются на высокопроизводительных ЭВМ, объединенных в кластер.

О том, как Google начал «бороздить просторы голубого океана»

Выход на новый рынок для «поисковика» был необходимостью, чтобы сохранить конкурентное преимущество своего основного сервиса. Скорость выполнения запросов при вводе «куплю машину Москва» или «курсовая работа скачать» в поисковой строке – одно из основных конкурентных преимуществ (недостатков в случае Bing), которые обеспечивается технологиями обработки больших данных.

Не дифференцируя пул проблем, с которым столкнулись разработчики нового программного обеспечения, стоит сосредоточиться на 2х из них: «Как хранить данные для поисковых запросов и обращаться к ним через допустимый временной лаг?». Так на рынке была запущена технология MapReduce.

О том, как Google «поедает бифштексы»

Парадигма новой «гугловской» технологии обработки больших массивов данных строится на основном правиле управления временем «поедания слонов»: разрежь и съешь. Стоит представить большой информационных поток, выделить из него некоторый сегмент. Он более чем «большой» и не может быть обработан на стандартном ПК. Далее дробим этот сегмент на «более мелкие кусочки» и приемлемые, для обработки на стандартном ПК. В книге Глеба Архангельского «Тайм-Драйв» этот процесс относится к решению сложных задач-слонов. Разделив на части-бифштексы, можно последовательно избавиться от большой задачи.

Google MapReduce также делит поток на бифштексы, съедает кусочек за кусочком, используя стандартные кластеры (ни чем не отличающиеся по мощности от ноутбука, на котором я пишу эту статью), далее собирает результаты обработки воедино и отправляет пользователю как результат на запрос. К сожалению, «велосипед не был изобретен» компанией Google, тем не менее, компания решила основную задачу, оптимизировав поисковую машину.

Внедренная архитектура MapReduce смогла обеспечить:

• автоматическую параллельную обработку данных из огромного массива по множеству узлов обработки (кластеров)

• эффективную балансировку загрузки этих вычислительных узлов, не дающую им простаивать или быть перегруженными сверх меры (мастер-узел)

• технологию отказоустойчивой работы (резервные серверы и фантомные мастера)

О том, как правильно резать и есть бифштексы

При проектировании MapReduce разработчики «гугла» преследовали цель размещения модулей, которые реализуют процедуры «map» и «reduce» на чанк-серверах – базовых элементах системы GFS.

Историческая справка

Вышеупомянутая система GFS – распределенная кластерная файловая система гугл. Применимо к данной статье – это аппаратный «бэкграунд» для реализации MapReduce. Основные принципы системы заключаются в перекрестном хранении дублированной информации на кластерах с «повышенной» защитой от сбоев. По большому счету, вся защита осуществляется посредством «фантомов» и образов (у любого объекта есть пара, готовая заменить его в случае поломки).

Чанк-сервер или CSS – базовая единица хранилища информации для GFS.

Возвращаясь к поеданию бифштексов

Как и GFS, технология MapReduce построена по принципу «главный (мастер) — подчиненные (исполнители)». Мастер управляет/координирует множество исполнителей/работников, находящихся на разных чанк-серверах. Все исполнители делятся на два типа по исполняемым функциям: mappers или «мапперы», выполняющие функцию map, и «редьюсеры», отвечающие, соответственно, за функцию reduce.

Рис. 1 Верхний уровень матрешки устройства MapReduce

На вход технология MapReduce подается массив «на обработку», который предварительно разделяется на количество частей (N), соответствующее количеству мапперов. Размеры каждой от 16 до 64 мегабайт. Стоит оговориться, есть несколько версий и методологий работы данной технологии. От версии к версии некоторые численные значения (в частности по «весу» единицы обработки) могут меняться. Целью данной статьи служит показать общую концепцию работы технологии.

Получив адреса M частей массива, мастер MapReduce формирует частные задания для N функций мапперов и отправляет их в соответствующие мапперам чанки. Далее каждое задание обрабатывается функцией map (работа мапперов). Поскольку мапперы работают параллельно и независимо друг от друга, требуется в N раз меньше времени, чем при линейной обработке.

Финальная стадия работы мапперов – разделённый на части массив промежуточных данных, содержащих неупорядоченные списки пар «ключ – значение». Количество таких частей должно быть эквивалентно количеству редьюсеров, но в реальности массив пар, содержащих один и тот же ключ, значительно больше. Для сокращения размера до требуемого, MapReduce использует процедуру (combine) – процедуру предварительного сбора данных. Эта процедура присваивает популярным/часто встречаемым парам новое промежуточное значение. Идеальная функция для накопления данных о частоте использования «слова» внутри переменных, однако коммутативностью и ассоциативностью данных для обработки редьюсеров.

Рис. 2 Второй уровень матрешки устройства MapReduce - Линия

Агрегированный массив промежуточных данных отправляется к редьюсерам (логистика также осуществляется посредством мастера). На каждого «работника» желательно подать пары с одинаковым ключом (в силу алгоритма обработки). Вопрос: как это сделать, если пары разбросаны по разным частям списка, сформированного мапперами?

Тут MapReduce использует процедуру (partioning), перераспределяя и отправляя пакеты к «нужным» работникам, в соответствии с парами «ключ-значение». Процесс времяемкий и энергозатратный (требуется большое количество итераций на проверку), но скорость выполнения работниками сборки готовых к сборке входных данных компенсирует время на процедуру распределения.

Каждый работник (редьюсер) по завершению работы создает файл, куда сохраняет отсортированный список ключей с соответствующими значениями. R «работников» создают R результирующих файлов, на что мастер дает команду об отправке адресов конечных файлов к клиентскому приложению. Таким образом сгеренированный обработанный массив «уже небольших» данных появляется на экране пользователя, сделавшего запрос.

Через перспективу

Разработчики Google увидели потенциал системы и стали использовать ее не только для оптимизации поисковых запросов - Google Translate, Google Docs, Google Voice (что является вторичным рынком, частично покрывающим стартовые капиталовложения).

Концепт MapReduce был опубликован разработчиками, что дало возможность GNU создать планировщик распределения задач – симулятор MapReduce.

Private Companies, такие как Fb или Alibaba, последовали примеру Google и создали свои системы обработки больших объемов данных, тем самым объявив «гонку вооружения».

Литература

1. Официальный сайт компании Cloudera http://www.cloudera.com/

2. Агрегатор статей в области программирования http://docs.mongodb.org/

3. Информационный портал «о новых технологиях» http://www.computerra.ru/

4. Новостной агрегатор http://venturebeat.com/

5. Официальный сайт компании IBMhttp://www.ibm.com/

6. Портал для IT-специалистов http://habrahabr.ru/

7. Аналитическое агентство http://www.tadviser.ru/

8. Официальный сайт консалтинговой компании McKinsey http://www.mckinsey.com

Код для цитирования: Скопировать