Apache Giraph

logoApacheGiraph

O Apache Giraph é um framework para processamento iterativo de grafos em larga escala ele foi inspirado no framework Pregel criado por adivinha quem? Adivinha? Google é claro! no ano da graça de 2010.

Abaixo o documento que serviu de inspiração:pregel

O Giraph é open-source ele se tornou um projeto de alto nível da Apache em 2012, o release 1.0 foi lançado em 2013 e o 1.1 em 2014

Neste post abordaremos o Apache Giraph

  • Grafos
  • Processamento de grafos
  • Apache Giraph
    – Características
    – Componentes
    – Aplicações
  • Apache Giraph na prática

GrafoS

Representação abstrata de um conjunto de objetos (vértices), onde alguns pares desses objetos são conectados por links (arestas), que podem ser direcionados ou não-direcionados. G = (V, A)

Características:

graphos1

graphos2

graphos3

Utilização

O que podemos fazer ou quais problemas podemos solucionar com os grafos ?

Mapear distâncias entre cidades, como chegar do ponto A até o ponto B no menor caminho? ou traçar a melhor rota logística para as entregas de um comércio eletrônico.utiliza3

Mapear relacionamentos entre pessoas, o Facebook é o maior utilizador dos grafos seguido do Linkedin.utiliza2

Mapear acesso à uma rede de computadores, quais computadores estão ligados a quais roteadores, switches ou Wifi?, qual o tipo da rede?, qual ponto da rede é o mais vulnerável no caso de um problema técnico.

No exemplo abaixo temos uma rede estrela com conectadas pelo IPUtiliza1

Áreas de negócios

Em quais negócios a análise de Grafos se faz necessária

  1. Redes Sociais
  2. Logística
  3. Segurança da informação
  4. Sistemas de redes de médio e grande porte
  5. PLN
  6. Busca semântica

Grafos e a Internet

A World Wide Web pode ser vista como um enorme grafo web pois as Páginas são os vértices conectados por bilhões de arestas que representam bilhões de hiperlinks

Grande parte do sucesso do Google é baseado em sua habilidade de realizar rapidamente cálculos sobre esse gigantesco grafo

O PageRank é um bom exemplo de grafos pois seu algoritmo mede a importância de uma página contabilizando a quantidade e qualidade de links apontando para ela, com isto o Google sabe em qual posição um site deve ter no resultado de busca.

pagerank

Desafios

Desafios para processar grafos larga escala

  • Tamanho dos dados
  • Latência
  • Sincronização frequente
    • Vértices, arestas, peso

HADOOP

Sim, o Apache Giraph é executado no nosso amigo mastigador de dados Hadoop, abaixo uma representação do ecossistema Giraph.

Eco_giraph

Giraph fornece meios ideais para processamento dos grafos

meiosProcessGraphos,

PROCESSAMENTO

o processamento de grafos em MapReduce:

> Implementados como uma sequência de jobs (cada iteração, um job)
> Dados escritos muitas vezes no disco
> Overhead por execução de tarefas de shuffle/sor

Processamento de grafos em Giraph

> Giraph utiliza Mappers para executar tarefas mestre e escravas
> Não há tarefas reduce
> Os dados de entrada do grafo são carregados somente uma vez
> O processamento é feito em memória, com pouco acesso ao disco
> Coordenação feita via ZooKeeper
> Formatos de entrada e saída personalizado

Bem, e o que mais

No Giraph, somente as mensagens são passadas pela rede e não toda a estrutura do grafo, o Giraph facilita o desenvolvimento de algoritmos de processamento de grafos utilizando o modelo programação Bulk Syncronous Parallel (BSP)

Bulk Syncronous Parallel (BSP)

> Modelo para processamento paralelo
> Sequência de superpassos
> Passos
– Computação
– Comunicação
> Sincronização global após cada superpasso

BSP

Superpassos é a sequencia de iterações onde são realizados os processamentos, em cada superpasso cada vértice invoca o método computacional indicado pelo usuário

O método computacional, recebe mensagens enviadas ao vértice no superpasso anterior faz o processamento utilizando as mensagens e os valores do vértice, resultando em modificações nos valores dos vértices e envia mensagens a outros vértices

Abaixo temos os Vértices em preto as Arestas com linhas e setas em verde com seus respectivos valores e em azul as mensagens e as linhas em vermelho são os superpassos.

modeloAG

Abaixo um exemplo detalhando passo a passo

Passo 1:

passo1

Passo 2:

Passo2

Passo 3:

Passo3

Passo 4:

Passo4

Passo 5:

Passo5

VANTAGENS

O Giraph faz o processamento iterativo de dados ser mais prático para usuários Hadoop, ele pode evitar o custo do disco e operações da rede no MapReduce, não há o conceito de message parsing no MapReduce e permite integração com o ecossistema Hadoop HBase, Accumulo, Hive, HCatalog

> Sem locks – comunicação baseada em mensagens
> Sem semáforos – sincronização global
> Iteração isolada – massivamente paralela

Giraph oferece um conjunto de operações:

> Combiners
> Aggregators
> MasterCompute
> WorkerContext
> PartitionContex

Representações de grafos suportados

> Grafos direcionados
> Grafos não direcionados
> Grafos não valorados (NullWritable)
> Grafos valorados

API GIRAPHScreenshot from 2015-10-20 12:30:46

Tá, eu sei, é estranho, mas faça uma forcinha,
tente Pensar como um vértice!

> Eu sei meu estado local
> Eu conheço meus vizinhos
> Eu posso enviar mensagens aos vertices
> Eu posso declarer que finalizei o cálculo
> Eu posso mudar a topologia do grafo

JAVA

Estrutura

BasicComputation<IntWritable,   // Vértice ID
IntWritable,           // Dados do vértice
NullWritable,         // Dados da aresta
IntWritable>          // Tipo de mensagem

O código ou a imagem do código:

codigoJava

FORMATOS DE ENTRADA

> Giraph oferece uma API que converte o tipo de dado para as classes principais do Giraph (Vertex e Edge)
>  Classes devem implementar a interface VertexInputFormat

Exemplo:

JsonLongDoubleFloatDoubleVertexInputFormat – vértice ID long, valores do vértice double, peso das arestas float e mensagens double em formato JSON

Aceita outros formatos de dados de entreda:

>  LongDoubleDoubleAdjacencyListVertexInputFormat
>  LongLongNullTextInputFormat
>  TextDoubleDoubleAdjacencyListVertexInputFormat
>   GraphvizOutputFormat
>   IntIntNullTextInputFormat

INSTALAÇÃO

Vale lembrar que o Giraph roda sob a tutela do Hadoop, então temos de ter o danado instalado para executar o Giraph… mas dá para instalar o Giraph em ter o Hadoop instalado na máquina…o problema é que nada será executado, OK?

Para instalar o Giraph

>  Instale o Hadoop

>  Faça o download do Giraph pelo github
    – cd /usr/local/
    – sudo git clone https://github.com/apache/giraph.git
    – sudo chown -R giraphuser:giraphuser giraph

>  Instale os componentes do Giraph utilizando Maven
cd /usr/local/giraph
    – mvn package -DskipTests

MÃO NA MASSA!

Vamos criar um conjunto de arestas e vértices conforme a imagem abaixo

Pratica

Giraph

Acessar diretório do
     cd /usr/local/giraph

Lista o diretório
     ls

Conteúdo do diretório    ConteudoDiretorio

Hadoop

Acessar diretório
 cd /usr/local/hadoop

Iniciar processos do HDFS
 bin/start-dfs.sh

starting namenode, logging to /usr/local/hadoop/libexec/../logs/hadoop-giraphuser- namenode-vm-giraph.out
localhost: starting datanode, logging to usr/local/hadoop/libexec/../logs/hadoop – giraphuser-datanode-vm-giraph.out
localhost: starting secondarynamenode, logging to /usr/local/hadoop/libexec/../ logs/hadoop-giraphuser-secondarynamenode-vm-giraph.ou

Iniciar processos do MapReduce
   bin/start-mapred.sh
     starting jobtracker, logging to /usr/local/hadoop/libexec/../logs/hadoop-                      giraphuser- jobtracker-vm-giraph.out
     localhost: starting tasktracker, logging to /usr/local/hadoop/libexec/../                        logs/hadoop-giraphuser-tasktracker-vm-giraph.out

Verificar processos
jps
13931 JobTracker
14066 TaskTracker
13523 NameNode
13795 SecondaryNameNode
13658 DataNode
14181 Jps

Criaremos um arquivo chamado meugrafo.txt contendo 5 vértices e 12 arestas direcionadas

Criando o arquivo, pode ser nano, vi, gedit o sabor que lhe convier

nano meugrafo.txt

//inserir o conteúdo abaixo no arquivo
//source_id, source_value, [[dest_id, edge_value],…]
[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]]]

Criar diretório de entrada no HDFS
bin/hadoop fs -mkdir input

Enviar arquivo para o HDFS
bin/hadoop fs -put meugrafo.txt input/

Verificar se o arquivo foi enviado com sucesso
bin/hadoop fs -ls input

Found 1 items
-rw-r–r– 1 giraphuser supergroup 112
/user/giraphuser/input/meugrafo.txt

Uma parte já foi, agora Iremos executar o exemplo SimpleShortestPathsComputation

Objetivo: ler um arquivo de entrada de um grafo em um dos formatos suportados pelo Giraph e calcular o tamanho do menor caminho de um nó até os outros nós.

Importante: O nó raíz é sempre o primeiro nó do arquivo de entrada

Visualizar os parâmetros parâmetros para execução
bin/hadoop jar /usr/local/giraph/giraph-examples/target/giraph-examples-1.2.0-SNAPSHOT-for- hadoop-1.2.1-jar-with-dependencies.jar org.apache.giraph.GiraphRunner -h

Utilizaremos os seguintes parâmetros

-vif    –vertexInputFormat <arg>        Vertex input format
-vip    –vertexInputPath <arg>           Vertex input path
-vof    –vertexOutputFormat <arg>    Vertex output format
-op     –outputPath <arg>                   Output path
-w     –workers <arg>                         Output path

Agora vamos executar a aplicação de busca do menor caminho, tuuudo isso é o comando e pode ser digitado na mesma linha

bin/hadoop jar
/usr/local/giraph/giraph-examples/target/giraph-examples-1.2.0-SNAPSHOT-for-hadoop-1.2.1-jar-with-dependencies.jar org.apache.giraph.GiraphRunner
org.apache.giraph.examples.SimpleShortestPathsComputation
-vif org.apache.giraph.io.formats.JsonLongDoubleFloatDoubleVertexInputFormat
-vip input/meugrafo.txt
-vof org.apache.giraph.io.formats.IdWithValueTextOutputFormat
-op output
-w 1

Aplicação em execução

15/10/18 20:41:21 INFO utils.ConfigurationUtils: No edge input format specified. Ensure your InputFormat does not require one.
15/10/18 20:41:25 INFO job.GiraphJob: run: Since checkpointing is disabled (default), do not allow any task retries (setting mapred.map.max.attempts = 1, old value = 4)
15/10/18 20:41:33 INFO job.GiraphJob: Tracking URL:
http://localhost:50030/jobdetails.jsp?jobid=job_201510181954_0002
15/10/18 20:41:33 INFO job.GiraphJob: Waiting for resources… Job will start only when it gets all 2 mappers
15/10/18 20:42:50 INFO job.HaltApplicationUtils$DefaultHaltInstructionsWriter: writeHaltInstructions: To halt
after next superstep execute: ‘bin/halt-application –zkServer vm-giraph:22181 –zkNode
/_hadoopBsp/job_201510181954_0002/_haltComputation’
15/10/18 20:42:50 INFO mapred.JobClient: Running job: job_201510181954_0002
15/10/18 20:42:51 INFO mapred.JobClient: map 100% reduce 0%

Listar diretório do resultado

bin/hadoop fs -ls output
Found 3 items
-rw-r–r– 1 giraphuser supergroup 0 2015-10-18 20:43 /user/giraphuser/output/_SUCCESS
drwxr-xr-x – giraphuser supergroup 0 2015-10-18 20:41 /user/giraphuser/output/_logs
-rw-r–r– 1 giraphuser supergroup 30 2015-10-18 20:42 /user/giraphuser/output/part-m-00001

O Resultado

bin/hadoop fs -text output/part-m-00001

//vérticeID soma dos pesos para o menor caminho

0          1.0
2          2.0
1          0.0
3          1.0
4          5.0

Links:

http://socilab.com – Ferramenta para criação de um grafo da sua rede do Linkedin

http://giraph.apache.org/ – Página oficial do projeto Giraph

http://maven.apache.org/ – Maven, é uma ferramenta de automação de compilação utilizada primariamente em projetos Java

Dúvidas, Perguntas e pedidos de música para:
alexandredvolpi@gmail.com

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s