Створення власного додатка для обробки графів у Giraph


Be my friend by oosDesign

Перед великими інтернет-компаніями часто постають такі складні завдання, як обробка великих даних і аналіз графів соціальних мереж. Допомагають у їх вирішенні фреймворки, але спершу необхідно проаналізувати можливі варіанти і вибрати підходящий. В лабораторії при Техносфери Mail.Ru ми вивчаємо ці питання на реальних прикладах з проектів Mail.Ru Group (myTarget, Пошук Mail.Ru, Антиспам). Завдання можуть бути як суто практичні, так і з дослідницької складової. За мотивами однієї з таких завдань і з'явилася ця стаття.

Під час складання і запуску свого першого проекту на Giraph співробітники лабораторії аналізу даних Техносфери Mail.Ru зіткнулися з низкою проблем, у зв'язку з чим народилася ідея написати короткий туторіал, як зібрати і запустити свій перший Giraph-проект.

У цій статті ми розповімо, як створювати свої додатки під фреймворк Giraph, який є надбудовою над популярною системою обробки даних Hadoop.

0. Що таке Giraph
Giraph — це фреймворк для ітеративної обробки великих графів, який працює поверх вельми популярної системи розподіленої обробки даних Hadoop. Подібно до того як поштовхом для появи Hadoop і HDFS послужила стаття Google про концепцію MapReduce і GFS (Google File System), Giraph з'явився як open source версія гугловой Pregel, стаття про яку була опублікована у 2010 році. Giraph використовується такими великими корпораціями, як Facebookдля обробки графів.

У чому полягає особливість Giraph? Основна його «фішка» — так звана vertex-centric-модель. Як написано в Practical Graph Analytics with Apache Giraph:
Ця модель вимагає від розробника, щоб він побував у шкурі вершини, яка може обмінюватися повідомленнями з іншими вершинами між ітераціями. Під час розробки вам не доведеться замислюватися про проблеми паралелізації і масштабування — цим займається сам Giraph.
Обробка графа в Giraph виглядає наступним чином: процес розбитий на ітерації, які називаються суперстепами (supersteps). На кожному суперстепе вершина виконує необхідну програму і, якщо треба, може надсилати повідомлення іншим вершин. На наступній ітерації вершина отримує повідомлення, виконує програму, розсилає повідомлення і т. д. Після завершення всіх суперстепов ви отримаєте результуючий граф.

Giraph підтримує велику кількість можливостей взаємодії з графом, у тому числі створення/видалення вершин, створення/видалення ребер, можливість зміни формату, в якому заданий граф або вибір із існуючих, управління завантаженням з диска і вивантаженням частин графа на диск під час роботи з ним і багато іншого. З подробицями можна ознайомитися в книзі Practical Graph Analytics with Apache Giraph.

1. Необхідне
Для початку вам знадобиться сам Hadoop. Якщо у вас немає доступу до кластеру з Hadoop, можна розгорнути його single-node-версію. Вона не дуже вимоглива до ресурсів, на ноутбуці запрацює спокійно. Для цього, наприклад, можна використовувати дистрибутив Hadoop під назвою Cloudera. Мануал по установці Cloudera ви можете знайти на тут. При розробці та тестуванні в цій статті був використаний Cloudera 5.5 (Hadoop 2.6.0).

Giraph реалізований на Java. При складанні проектів використовується білд-менеджер Maven. Вихідний код Giraph можна скачати з офіційного сайту. Інструкція по компіляції самого Giraph і прикладів, які поставляються з ним, перебуває тут і Quick Start Guide.

Будь-яка IDE, така як Eclipse або IntelliJ IDEA, вміє працювати з Maven в проектах, що дуже зручно при розробці. Ми в своїх експериментах використовували IntelliJ IDEA.

2. Компіляція Giraph
Давайте для початку скомпилируем вміст исходников Giraph і спробуємо що-небудь запустити. Як було сказано в інструкції, в папці з проектом Giraph виконуємо команду:

mvn -Phadoop_2 -fae -DskipTests install clean

І чекаємо якийсь час, поки всі збирається… В течці giraph-examples/target з'являться зібрані jar-файли, нам знадобиться giraph-examples-1.2.0-SNAPSHOT-for-hadoop-2.5.1-jar-with-dependencies.jar.

Давайте запустимо, наприклад, SimpleShortestPathsComputation. Для початку нам потрібен файл з вхідними даними. Візьмемо приклад з Quick Start Guide:

[0,0,[[1,1],[3,3]]]
[1,0,[[0,1],[2,2],[3,1]]]
[2,0,[[1,2],[4,4]]]
[3,0,[[0,3],[1,1],[4,4]]]
[4,0,[[3,4],[2,4]]]

Збережемо це в файл tiny_graph.txt і покладемо в HDFS в нашу локальну папку:

hdfs dfs -put ./tiny_graph.txt ./

При такій команді файл потрапить у вашу локальну директорію. Перевірити це можна, вивівши на екран вміст файлу:

hdfs dfs -text tiny_graph.txt

Ок, все круто, а тепер запустили:

hadoop jar \
giraph-examples-1.2.0-SNAPSHOT-for-hadoop-2.5.1-jar-with-dependencies.jar \
org.apache.giraph.GiraphRunner \
org.apache.giraph.examples.SimpleShortestPathsComputation \
-vif org.apache.giraph.io.formats.JsonLongDoubleFloatDoubleVertexInputformat \
-vip tiny_graph.txt \
-vof org.apache.giraph.io.formats.IdWithValueTextOutputFormat \
-op shortestpaths \
-w 1 

Давайте розберемося, що тут написано:

  • hadoop jar giraph-examples-1.2.0-SNAPSHOT-for-hadoop-2.5.1-jar-with-dependencies.jar
    — ця частина команди говорить Хадупу запустити jar-файл;
  • org.apache.giraph.GiraphRunner
    — ім'я ранера. Тут використовується дефолтний. Ранер можна перевизначити. Щоб він, наприклад, при старті видаляв старі дані або здійснював ще якісь підготовчі дії. Детальніше про це можна прочитати в книжці Practical Graph Analytics with Apache Giraph;
  • org.apache.giraph.examples.SimpleShortestPathsComputation
    — клас, що містить compute-метод, який буде виконано;
  • vif
    визначає клас, який буде читати вхідний файл з вершинами. Цей клас обирається в залежності від формату вхідного файлу і може бути різним, при необхідності його навіть можна перевизначити (див. в Practical Graph Analytics with Apache Giraph). Опис стандартних класів можна подивитися тут;
  • vip
    — шлях до вхідного файлу, який містить описи вершин;
  • vof
    — в якому форматі буде збережений результат роботи. При бажанні змінюється, описи стандартних класів дивись тут;
  • m
    — куди зберегти;
  • w
    — кількість воркеров (процесів, які обробляють повершинно граф).
Більш детально про параметри запуску можна дізнатися, набравши в консолі:

hadoop jar \
giraph-examples-1.2.0-SNAPSHOT-for-hadoop-2.5.1-jar-with-dependencies.jar \
org.apache.giraph.GiraphRunner \
org.apache.giraph.examples.SimpleShortestPathsComputation -h

Після запуску ми можемо прочитати результат в shortestpaths, виконавши

hdfs dfs -text shortestpaths/*

3. Створення власного проекту
А тепер давайте напишемо програму, яка буде вважати ступінь вершин у ненаправленном графі. Я створюю новий Maven-проект. Як це зробити, написано, наприклад, тут. В корені проекту лежить pom.xml, заповнюємо його наступним чином:

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>

<groupId>ru.simple.giraph.project.org</groupId>
<artifactId>simple-giraph-project</artifactId>
<version>1.0-SNAPSHOT</version>

<repositories>
<repository>
<id>cloudera</id>
<url>
https://repository.cloudera.com/artifactory/cloudera-repos/
</url>
</repository>
</repositories>

<properties>
<org.apache.hadoop.version>2.6.0-cdh5.5.1</org.apache.hadoop.version>
</properties>

<build>
<plugins>
<plugin>
<artifactId>maven-assembly-plugin</artifactId>
<version>2.4</version>
<configuration>
<finalName>simple-giraph-project</finalName>
<descriptor>
${project.basedir}/src/main/assembly/single-jar.xml
</descriptor>
</configuration>
<executions>
<execution>
<goals>
<goal>single</goal>
</goals>
<phase>package</phase>
</execution>
</executions>
</plugin>
</plugins>
</build>
<dependencies>
<dependency>
<groupId>org.apache.hadoop</groupId>
<artifactId>hadoop-client</artifactId>
<version>${org.apache.hadoop.version}</version>
</dependency>
<dependency>
<groupId>org.apache.hadoop</groupId>
<artifactId>hadoop-common</artifactId>
<version>${org.apache.hadoop.version}</version>
</dependency>
<dependency>
<groupId>org.apache.giraph</groupId>
<artifactId>giraph-core</artifactId>
<version>1.1.0-hadoop2</version>
</dependency>
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>19.0</version>
</dependency>
</dependencies>
</project>

Про те, як створювати pom-файли і працювати з Maven, ви можете прочитати в офіційному гайде тут. Після цього у src я створюю новий файл ComputationDegree.java. Це буде наш клас, який буде вважати ступеня вершин:

/**
* This is a simple implementation of vertex degree computation.
*/
package ru.simple.giraph.project.org;

import com.google.common.collect.Iterables;
import org.apache.giraph.graph.BasicComputation;
import org.apache.giraph.graph.Vertex;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.NullWritable;
import org.apache.hadoop.io.Text;

import java.io.IOException;

public class ComputeDegree extends
BasicComputation<IntWritable, IntWritable,
NullWritable, Text> {
public void compute(Vertex<IntWritable, IntWritable,
NullWritable> vertex, Iterable<Text> iterable) throws IOException {
if (getSuperstep() == 0){
sendMessageToAllEdges(vertex, new Text());
} else if (getSuperstep() == 1){
Integer degree = Iterables.size(vertex.getEdges());
vertex.setValue(new IntWritable(degree));
}else{
vertex.voteToHalt();
}
}
}

Працює це так:

  1. На першому кроці кожна вершина шле своїм сусідам повідомлення.
  2. Кожна вершина підраховує кількість вхідних повідомлень і зберігає їх у значенні вершини.
  3. Всі вершини голосують за зупинку обчислень.
На виході ми маємо граф, який у значенні вершини зберігає ступінь вершини. Компилируемся командою:

mvn package -fae -DskipTests install clean

Зазвичай після компіляції створюється татко target, в якій лежить файл giraph-test-fatjar.jar. Цей файл ми і будемо запускати. Візьмемо який-небудь дуже простий граф, наприклад ось такий:



В якості вхідного формату даних будемо використовувати org.apache.giraph.io.formats.IntIntNullTextVertexInputFormat, так що файл, що описує наш граф, буде виглядати ось так:

0 0 1 2 3
1 0 0 2
2 0 0 1
3 0 0

Зберігаємо його у файл example_graph.txt, кладемо на HDFS і запускаємо нашу програму:

hadoop jar ./target/giraph-test-fatjar.jar org.apache.giraph.GiraphRunner \
ru.giraph.test.org.ComputeDegree \
-vif org.apache.giraph.io.formats.IntIntNullTextVertexInputFormat \
-vip example_graph.txt \
-vof org.apache.giraph.io.formats.IdWithValueTextOutputFormat \
-op degrees \
-w 1

Дивимося результат:

hdfs dfs -text degrees/*

І бачимо приблизно таку відповідь:

0 3
2 2
1 2
3 1

Отже, в даній статті ми навчилися компілювати Giraph і написали своє маленьке додаток. А весь проект можна скачати тут.

У наступній статті поговоримо про роботу з Giraph на прикладі алгоритму навчання Restricted Boltzmann Machine. Ми спробуємо максимально прискорити алгоритм, щоб зрозуміти тонкощі налаштування Giraph і оцінити, наскільки ця система зручна/продуктивна/стабільна.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.