Apache Giraph

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:25, 16 января 2019.
Apache Giraph
Apache Giraph.jpg
Gephi visualization of a correlation network.png
Разработчики: ASF (Apache Software Foundation)
Постоянный выпуск: 1.1.0 / 2014/11/19
Состояние разработки: активный
Написана на: Java
Операционная система: Кросс-платформенное программное обеспечение
Тип ПО: графовый процессор
Лицензия: Apache 2.0 Licence
Веб-сайт giraph.apache.org

Apache Giraph - это проект Apache с отрытым исходным кодом, созданный для итеративной обработки больших графов, который использует реализацию MapReduce от Apache Hadoop.

Что такое Giraph?

Данная система возникла как аналог открытого программного обеспечения для Pregel (архитектуры обработки графиков, разработанной в Google), но Giraph добавляет несколько функций помимо базовой модели Pregel, включая основные вычислительные мощности. Характерная черта Apache Giraph – высокая масштабируемость. Основная его особенность данной системы – это так называемая vertex-centric-модель. Как написано в книге "Practical Graph Analytics with Apache Giraph": «Эта модель требует от разработчика, чтобы он побывал в шкуре вершины, которая может обмениваться сообщениями с другими вершинами между итерациями. Во время разработки вам не придется задумываться о проблемах параллелизации и масштабирования — этим занимается сам Giraph».

Общее строение Giraph

Координация вычислений

Для управления вычислениями существует специальный механизм — MasterCompute (DefaultMaster - класс по умолчанию, наследованный от абстрактного класса MasterCompute). Есть возможность создать свой мастер, который так же будет унаследован от MasterCompute с реализацией метода compute, который выполняется перед каждым суперстепом. Мастер позволяет выбирать класс для вершин, агрегировать некоторые данные из вершин и завершать вычисления. Обработка графа ведётся на нескольких воркерах (workers), число которых не изменяется во время выполнения. Каждый воркер последовательно обрабатывает несколько частей графа (Partition). Граф разбивается на части, которые могут меняться в процессе обработки. Всё это делается автоматически и не требует вмешательства пользователя.

Принцип функционирования

Сам алгоритм обратботки графа в Giraph выглядит следующим образом. Процесс разбит на итерации, которые называются «supersteps». На каждой итерации вершина выполняет необходимую программу и может, при необходимости, разослать сообщения другим вершинам. То есть на каждом суперстепе для вершин вызывается метод compute. На следующей шаге вершина получает сообщения, выполняет программу, рассылает сообщения «соседям» и т.д. Сообщения имеют свой тип, который не обязан совпадать с типами вершин или рёбер. После завершения программ всех суперстепов в итоге получается результирующий граф.

Внутренняя структура

Giraph поддерживает большое количество способов взаимодействия с графом, например, создание и удаление вершин, ребер. Так же присутствует возможность переопределения формата, в котором задан граф или выбор из существующих, управление загрузкой с диска и выгрузкой частей графа на диск во время работы. Каждая вершина и ребро имеют своё значение, которое может быть разных типов. Вершины содержат класс, который реализует интерфейс Computation, где описан метод compute. Каждая вершина может находиться в двух состояниях: активном и неактивном. Если внутри compute вызывается метод voteToHalt(), то по окончании суперстепа вершина «засыпает» — становится неактивной на следующем суперстепе. Между суперстепами вершинам доставляются сообщения, отправленные другими вершинами в ходе суперстепа. Все вершины, которые не заснули на предыдущем суперстепе или получили сообщения перед следующим, являются активными и участвуют в новом суперстепе, выполняя свой метод compute. Если все вершины неактивны, то вычисления заканчиваются. По окончании суперстепа текущее состояние графа сохраняется на диск. Теперь рассмотрим работу с ребрами. В Giraph рёбра по умолчанию хранятся в виде массива байтов и при каждом обращении заново десериализуются. Это помогает сэкономить память, пренебрегая временем работы. Для ускорения программы можно хранить рёбра в виде списка и словаря, ключами в котором являются конечные вершины рёбер. Список позволяет оперативно производить итерацию по рёбрам, в тот момент пока словарь находит ребро по его вершине назначения.

Графическая демонстрация функционирования

Как уже говорилось выше, программы обработки графов в Giraph представлены в виде последовательностей итераций, которые называются супершагами. При выполнении супершага для каждой вершины графа запускается определенная пользователем функция, выполняющаяся относительно других - параллельно. Пользовательская функция определяет поведение для отдельной вершины V и отдельного супершага S. Функция может считывать сообщения, отправляемые вершине V на супершаге S-1, посылать сообщения другим вершинам (они будут получены на супершаге S+1), а также изменять состояние вершины V и исходящих из нее ребер. Обычно сообщения посылаются вдоль исходящих ребер, но можно отправить сообщение любой вершине с известным идентификатором. Каждый супершаг представляет собой атомную единицу параллельных вычислений. На рисунке 1 изображен механизм выполнения модели программирования BSP.

Рисунок 1 - Модель программирования BSP

В этой модели программирования на супершаге 1 выполняемой программы всем вершинам присвоен статус активных. На каждом супершаге все активные вершины выполняют пользовательскую функцию compute(). Каждая вершина может деактивировать себя путем запроса на останов в процессе голосования и перейти в неактивное состояние на любом супершаге при получении сообщения. Вершина может возвратиться в активное состояние при получении сообщения в процессе выполнения любого последующего супершага. Этот процесс, изображенный на рисунке 2, продолжается до тех пор, пока все вершины не отправят все свои сообщения и не перейдут в неактивное состояние. Таким образом, выполнение программы завершается, когда на каком-то этапе все вершины становятся неактивными.

Рисунок 2 - Голосование вершин

На рисунке 3 изображен пример обмена сообщениями между набором вершин графа для определения максимального значения вершины.

Рисунок 3 - Пример BSP – вычисление максимального значения вершины

На супершаге 1 рисунка 3 каждая вершина сообщает свое значение своему соседу. На супершаге 2 каждая вершина сравнивает свое значение с полученным от соседа. Если полученное значение выше, то вершина меняет свое значение на полученное и сообщает это новое значение своему соседу. Если полученное значение ниже, чем собственное значение, то вершина сохраняет свое текущее значение и посылает запрос в голосование на останов. Таким образом, на супершаге 2 только вершина 1 обновляет свое значение на более высокое (5) и передает его соседу. Этот процесс снова повторяется на супершаге 3 для вершины со значением 2, а на супершаге 4 все вершины участвуют в голосовании на останов, и выполнение программы завершается. Так же, как и инфраструктура Hadoop, Giraph является эффективной, масштабируемой и отказоустойчивой реализацией, работающей в кластерах из тысяч рядовых компьютеров; при этом все специфические детали, относящиеся к продукту, спрятаны за абстракциями. На компьютере, выполняющем вычисления, все вершины и ребра хранятся в памяти, а сеть используется только для передачи сообщений. Эта модель хорошо подходит для распределенных реализаций благодаря тому, что она не использует каких-либо механизмов для определения порядка выполнения внутри супершага, и все взаимодействия выполняются только между супершагом S и супершагом S+1. Во время выполнения программы вершины графа разделяются на секции, которые назначаются отдельным обработчикам. По умолчанию используется механизм хеш-секционирования (hash-partitioning), но можно использовать и собственные алгоритмы секционирования. В Giraph реализована архитектура главного узла и узлов-обработчиков, как показано на рисунке 4.

Рисунок 4 - Шаги обработки графа на главном узле и узлах-обработчиках

Главный узел распределяет секции по узлам-разработчикам, координирует синхронизацию, опрашивает контрольные точки и отслеживает статусы состояния. Как и в Hadoop, для синхронизации в Giraph используется Apache ZooKeeper. Обработчики отвечают за вершины. Узел-обработчик запускает функцию compute() для активных вершин, а также отправляет, получает и присваивает сообщения другим вершинам. Если во время выполнения обработчик получает входные данные, не предназначенные для его вершин, он передает их дальше. Разберем еще один рисунок, на котором изображено выполнение алгоритма кратчайших путей.

Рисунок 5 - Метод кратчайших путей

Входными данными является цепной граф с тремя черными вершинами и двумя зелеными ребрами, значения которых равно 1 и 3 соответственно. Алгоритм вычисляет расстояние начиная от крайней левой вершины. Начальные значения вершин в первой строке: 0, ∞ и ∞. Верхние границы расстояния отправляются в виде сообщений (стрелки синего цвета), что приводит к последующему обновлению значений вершин (последовательно сверху вниз по строкам). Как видно на данном рисунке выполнение алгоритма длится три супершага, каждый из которых разделен краной линией.

Необходимое ПО для работы с Giraph

Для работы с Giraph, в первую очередь, нам понадобится Hadoop. При сборке проектов можно использовать билд-менеджер Maven. Любая IDE, такая как Eclipse IDE или IntelliJ IDEA, умеет работать с Maven в проектах, что достаточно практично при разработке. Сам исходный код Giraph, который так же необходим, можно скачать с официального сайта разработчика. Инструкция по компиляции самого Giraph и множество примеров, которые поставляются с ним, находится в Quick Start Guide.

Практические применение системы

В целом, благодаря устойчивому циклу разработки и растущему сообществу пользователей по всему миру, Giraph является естественным выбором для массового использования потенциала системы в обработке структурированных наборов данных. Система является весьма многофункциональным инструментом, который может быть адаптирован под множество различных задач, например обучение RBM (Ограниченная машина Больцмана). В нём есть множество настраиваемых параметров, начиная от способа хранения данных и форматов ввода или вывода графа и заканчивая разбиением графа на части для хранения и количеством воркеров. С другой стороны, эффективное использование этих параметров требует понимания устройства Giraph. Таким образом, Giraph активно используется такими крупными корпорациями, как Facebook и Google. Свое применение он нашел в работе осуществления анализа социального графа, сформированного пользователями связями и связями компаний. Данная аналитика необходима, например, в социальных сетях для извлечения ценности бизнеса из огромного количества взаимосвязанных точек данных. Рассматриваемый подход позволяет создавать приложения для интеллектуального анализа данных и машинного обучения с использованием инфраструктуры Giraph Apache Foundation. Насколько реально эффективен данный продукт, можно судить, исходя из конкретных показателей его производительности. Так Facebook использовал Giraph с некоторыми улучшениями системы, чтобы проанализировать один триллион ребер, используя 200 машин за 4 минуты.

Установка

В представленном ролике можно найти пример, демонстрирующий процесс от скачивания, до полной утановки системы Giraph и требующегося для ее работы утилит и программ. Для полной работоспособности, как и написано выше, необходимо установить и настроить Hadoop, а для сборки проектов можно использовать, как на видео, билд-менеджер Maven. Все действия по установке, настройке и запуску систем производятся посредством использования виртуальной машиины Ubuntu на Oracle VM VirtualBox (все необходимые настройки машины также подробно и детально демонстрируются).

Исчточники

  • Apache Giraph [Электронный ресурс]/ Дата обращения: 10.12.2018. — Режим доступа: https://en.wikipedia.org/wiki/Apache_Giraph/.
  • Apache Giraph [Электронный ресурс]: Apache Giraph official website / Дата обращения: 10.12.2018. — Режим доступа: http://giraph.apache.org/.
  • Работа с фреймворком итеративной обработки графов Giraph на примере RBM[Электронный ресурс]/ Дата обращения: 10.12.2018. — Режим доступа: https://habr.com/company/mailru/blog/306362/#7/.
  • Создание собственного приложения для обработки графов в Giraph[Электронный ресурс]/ Дата обращения: 10.12.2018. — Режим доступа: https://habr.com/company/mailru/blog/305924/.