Universidade Federal do Rio Grande do NorteCentro de Cincias
Exatas e da Terra
Departmento de Informtica e Matemtica AplicadaPrograma de
Ps-Graduao em Sistemas e Computao
Mestrado Acadmico em Sistemas e Computao
Uma Mquina de Reduo de GrafosExtensvel para a Implementao de
Fluxos de
Trabalho
Mrcio Alves de Macdo
Natal-RN
Fevereiro de 2015
Mrcio Alves de Macdo
Uma Mquina de Reduo de Grafos Extensvel para aImplementao de
Fluxos de Trabalho
Dissertao de Mestrado apresentada ao Pro-grama de Ps-Graduao em
Sistemas eComputao do Departamento de Inform-tica e Matemtica
Aplicada da UniversidadeFederal do Rio Grande do Norte como
re-quisito parcial para a obteno do grau deMestre em Sistemas e
Computao.
Linha de pesquisa:Linguagens de Programao e Mtodos For-mais
Orientador
Martin Alejandro Musicante
Co-Orientador
Alberto Pardo
PPgSC Programa de Ps-Graduao em Sistemas e ComputaoDIMAp
Departamento de Informtica e Matemtica Aplicada
CCET Centro de Cincias Exatas e da TerraUFRN Universidade
Federal do Rio Grande do Norte
Natal-RN
Fevereiro de 2015
Catalogao da Publicao na Fonte. UFRN / SISBI / Biblioteca
Setorial Centro de Cincias Exatas e da Terra CCET.
Macdo, Mrcio Alves de.Uma mquina de reduo de grafos extensvel
para a implementao de fluxos
de trabalho / Mrcio Alves de Macdo. - Natal, 2015.121 f.:
il.
Orientador: Prof. Dr. Martin Alejandro Musicante.Coorientador:
Prof. Dr. Alberto Pardo.
Dissertao (Mestrado) Universidade Federal do Rio Grande do
Norte. Centro de Cincias Exatas e da Terra. Programa de Ps-Graduao
em Sistemas e Computao.
1. Linguagens de mquina Dissertao. 2. Servios web Dissertao. 3.
Composio de servios Dissertao. 4. Mquina de reduo de grafos
Dissertao. 5. Big data Dissertao. 6. Linguagem BPEL Dissertao. I.
Musicante, Martin Alejandro. II. Pardo, Alberto. III. Ttulo.
RN/UF/BSE-CCET CDU: 004.431.2
uirakuleszaStamp
Agradecimentos
Agradeo inicialmente a Deus por me dar, alm dos obstculos, foras
para enfrent-
los.
Agradeo minha me Maria da Assuno, meu porto seguro, pelo
incentivo cons-
tante, que me ajudou a nunca desistir dos desafios.
Obrigado a Martin e Alberto, pela orientao nesses dois anos de
trabalho.
Obrigado aos meus amigos, pelo apoio nas horas difceis. Em
especial, agradeo aos
meus amigos talo e Simone, pelo suporte e ajuda nos momentos de
dificuldade.
Obrigado a minha amiga e companheira, Helona, pelo apoio, ajuda
e compreenso
em todos os momentos.
A todos que contriburam de alguma forma para essa realizao, o
meu muito obrigado.
Uma Mquina de Reduo de Grafos Extensvel para aImplementao de
Fluxos de Trabalho
Autor: Mrcio Alves de Macdo
Orientador(a): Martin Alejandro Musicante
Co-Orientador (a): Alberto Pardo
Resumo
Mquinas de reduo de grafos, so tradicionalmente utilizadas na
implementao de lin-
guagens de programao. Elas permitem executar programas
(representados como grafos),
atravs da aplicao sucessiva de regras de reduo. A composio de
servios web per-
mite a criao de novos servios web a partir de servios web j
existentes. BPEL a
linguagem padro para criar composies de servios web como fluxos
de trabalho. No
entanto, o uso de BPEL para definir composies que usem outras
tecnologias, alm dos
servios web no imediato. Na maioria dos casos, quando operaes
que no fazem parte
do domnio dos servios web precisam ser executadas nas regras de
negcio de uma em-
presa, parte do trabalho realizado de forma ad-hoc. Permitir que
operaes oriundas de
diferentes tecnologias possam fazer parte de um mesmo fluxo de
trabalho auxilia a criao
de fluxos de trabalho mais adequados s necessidades das
organizaes. Esta dissertao
define uma variante da linguagem BPEL para a criao de composies
com operaes
de servios web, tarefas de big data ou operaes definidas pelo
usurio. O suporte a esta
linguagem dado mediante a definio de uma mquina de reduo de
grafos extensvel,
a qual permite a execuo de programas definidos na linguagem
proposta. Esta mquina
implementada como prova de conceito. A proposta deste trabalho
avaliada mediante
a apresentao de resultados experimentais.
Palavras-chave: Servios web, Composio de servios, Mquina de
reduo de grafos, Big
data, BPEL.
An Extensible Graph Reduction Machine for
WorkflowImplementation
Author: Mrcio Alves de Macdo
Supervisor: Martin Alejandro Musicante
Co-Supervisor (a): Alberto Pardo
Abstract
Graph Reduction Machines, are a traditional technique for
implementing functional pro-
gramming languages. They allow to run programs by transforming
graphs by the suc-
cessive application of reduction rules. Web service composition
enables the creation of
new web services from existing ones. BPEL is a workflow-based
language for creating
web service compositions. It is also the industrial and academic
standard for this kind of
languages. As it is designed to compose web services, the use of
BPEL in a scenario where
multiple technologies need to be used is problematic: when
operations other than web
services need to be performed to implement the business logic of
a company, part of the
work is done on an ad hoc basis. To allow heterogeneous
operations to be part of the same
workflow, may help to improve the implementation of business
processes in a principled
way. This work uses a simple variation of the BPEL language for
creating compositions
containing not only web service operations but also big data
tasks or user-defined operati-
ons. We define an extensible graph reduction machine that allows
the evaluation of BPEL
programs and implement this machine as proof of concept. We
present some experimental
results.
Keywords : Web Services, Service Composition, Graph Reduction
Machines, Big data,
BPEL.
Lista de abreviaturas e siglas
UDDI (Universal Description, Discovery, and Integration)
W3C (Word Wide Web Consortium)
WSDL (Web Services Description Language)
SOAP (Simple Object Access Protocol)
HTML (Hypertext Markup Language)
XML (Extensible Markup Language)
BPEL (Business Process Execution Language)
PEWS (Path Expressions for Web Services)
BPML (Business Process Modeling Language)
WSCI (Web Service Choreography Interface)
WSFL (Web Services Flow Language)
PRAM (Parallel Random Access Machine)
BSP (Bulk Synchronous Parallel)
HDFS (Hadoop Distributed Filesystem)
YARN (Yet Another Resource Negotiator)
STG (Spineless Tagless G-machine)
GHC (Haskell Glasgow Compiler)
FIFO (First In First Out)
PLY (Python Lex-Yacc)
Yacc (Yet Another Compiler - Compiler)
SQL (Structured Query Language)
Sumrio
1 Introduo p. 11
1.1 Motivao . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . p. 12
1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . p. 12
1.3 Organizao do trabalho . . . . . . . . . . . . . . . . . . .
. . . . . . . p. 13
2 Fundamentao p. 14
2.1 Servios Web . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . p. 14
2.1.1 Composio de Servios Web . . . . . . . . . . . . . . . . .
. . p. 15
2.1.2 Linguagens de Composio . . . . . . . . . . . . . . . . . .
. . . p. 16
2.2 Big Data: Processamento de Grandes Volumes de Dados . . . .
. . . . p. 16
2.2.1 Modelos Paralelos . . . . . . . . . . . . . . . . . . . .
. . . . . . p. 17
2.2.2 MapReduce . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . p. 18
2.2.3 Hadoop . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . p. 19
2.2.4 Composio de Tarefas do Hadoop . . . . . . . . . . . . . .
. . p. 21
2.2.5 Apache Oozie . . . . . . . . . . . . . . . . . . . . . . .
. . . . . p. 23
2.3 Mquinas de Reduo de Grafos . . . . . . . . . . . . . . . . .
. . . . . p. 23
2.4 Concluses do Captulo . . . . . . . . . . . . . . . . . . . .
. . . . . . . p. 29
3 Trabalhos Relacionados p. 30
3.1 Mquina de Reduo de Grafos PEWS-AM . . . . . . . . . . . . .
. . . p. 30
3.1.1 Construtores da Linguagem . . . . . . . . . . . . . . . .
. . . . p. 31
3.1.2 Mquina de Reduo de Grafos PEWS-AM . . . . . . . . . . . p.
32
3.1.3 Regras de Traduo . . . . . . . . . . . . . . . . . . . . .
. . . . p. 34
3.1.3.1 Chamada de Operao . . . . . . . . . . . . . . . . . . p.
34
3.1.3.2 Composio em Paralelo . . . . . . . . . . . . . . . . .
p. 35
3.1.3.3 Composio Seqencial . . . . . . . . . . . . . . . . . .
p. 36
3.1.3.4 Escolha No Determinstica . . . . . . . . . . . . . . .
p. 36
3.1.3.5 Condicional . . . . . . . . . . . . . . . . . . . . . .
. . p. 38
3.1.3.6 Unfolding . . . . . . . . . . . . . . . . . . . . . . .
. . p. 39
3.1.3.7 Unfold . . . . . . . . . . . . . . . . . . . . . . . . .
. . p. 40
3.1.4 Regras de Reduo . . . . . . . . . . . . . . . . . . . . .
. . . . p. 41
3.1.4.1 Chamada de Operao . . . . . . . . . . . . . . . . . . p.
41
3.1.4.2 Retorno de Operao . . . . . . . . . . . . . . . . . . .
p. 42
3.1.4.3 Escolha No Determinstica . . . . . . . . . . . . . . .
p. 43
3.1.4.4 Unfolding . . . . . . . . . . . . . . . . . . . . . . .
. . p. 45
3.2 Pony . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . p. 46
3.3 Concluses do Captulo . . . . . . . . . . . . . . . . . . . .
. . . . . . . p. 47
4 A Mquina de Reduo de Grafos MiniBPEL-AM p. 49
4.1 Construtores da Linguagem . . . . . . . . . . . . . . . . .
. . . . . . . p. 50
4.2 Mquina de Reduo de Grafos . . . . . . . . . . . . . . . . .
. . . . . p. 51
4.3 Regras de Traduo . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . p. 54
4.3.1 Chamada de Operao . . . . . . . . . . . . . . . . . . . .
. . . p. 54
4.3.2 Composio em Paralelo . . . . . . . . . . . . . . . . . . .
. . . p. 55
4.3.3 Composio Seqencial . . . . . . . . . . . . . . . . . . . .
. . . p. 56
4.3.4 Escolha No Determinstica . . . . . . . . . . . . . . . . .
. . . p. 57
4.3.5 Condicional . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . p. 58
4.3.6 While . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . p. 59
4.4 Regras de Reduo . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . p. 60
4.4.1 Chamada de Operao . . . . . . . . . . . . . . . . . . . .
. . . p. 61
4.4.2 Retorno de Operao . . . . . . . . . . . . . . . . . . . .
. . . . p. 62
4.4.3 Escolha No Determinstica . . . . . . . . . . . . . . . . .
. . . p. 62
4.4.4 While . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . p. 65
4.5 Exemplo de Composio . . . . . . . . . . . . . . . . . . . .
. . . . . . p. 66
4.6 Concluses do Captulo . . . . . . . . . . . . . . . . . . . .
. . . . . . . p. 69
5 Implementao p. 71
6 Estudos de Casos p. 79
6.1 Estudo de Caso 1 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . p. 79
6.2 Estudo de Caso 2 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . p. 82
6.3 Estudo de Caso 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . p. 86
6.4 Anlise dos Estudos de Caso . . . . . . . . . . . . . . . . .
. . . . . . . p. 89
6.4.1 Estudo de Caso 1 . . . . . . . . . . . . . . . . . . . . .
. . . . . p. 90
6.4.2 Estudo de Caso 2 . . . . . . . . . . . . . . . . . . . . .
. . . . . p. 95
6.4.3 Estudo de Caso 3 . . . . . . . . . . . . . . . . . . . . .
. . . . . p. 97
6.5 Concluses do Captulo . . . . . . . . . . . . . . . . . . . .
. . . . . . . p. 101
7 Concluses p. 102
7.1 Principais contribuies . . . . . . . . . . . . . . . . . . .
. . . . . . . p. 103
7.2 Limitaes . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . p. 104
7.3 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . p. 105
Referncias p. 106
Apndice A -- Cdigos fonte utilizados nos estudos de caso p.
112
A.1 Estudo de caso 1 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . p. 112
A.2 Estudo de caso 2 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . p. 114
A.3 Estudo de caso 3 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . p. 117
11
1 Introduo
Desenvolvimento baseado em componentes (caixas pretas) que se
comunicam entre si
hoje uma realidade [1]. Servios web [2] so uma implementao deste
tipo de compo-
nentes.
A composio de servios web [3] responde a muitas das exigncias
das novas formas
de desenvolvimento. Principalmente, no que toca descrio dos
sistemas (ou, como era
chamado na dcada de 80 e 90, Programming in the large).
No entanto, as linguagens de composio de servios tem sido
desenvolvidas para dar
suporte direto apenas a servios web [4]. O uso de componentes
heterogneos (para a
formulao de composies hbridas) requer conhecimentos que
extrapolam aqueles do
programador usual.
Outras propostas (como MapReduce [5], BSP [6], Pig Latin [7],
RPC/RMI [8]) ofere-
cem primitivas que so complementares quelas dos servios web e
que podem ser combi-
nadas/usadas no desenvolvimento de aplicaes de composio.
Isto motiva este trabalho: a proposta de uma ferramenta que
integre, da forma mais
transparente possvel, as vantagens de se construir composies de
mdulos que no sejam
apenas servios web, mas oriundos de outras tecnologias.
Existem diversas ferramentas para facilitar a anlise de grandes
volumes de dados.
Destas ferramentas, Hadoop [9] a que atrai mais ateno por ser
utilizada por gran-
des empresas, porque permite que os dados sejam processados por
diversos modelos de
programao e pode funcionar em clusters compostos de mquinas no
to potentes.
O Hadoop permite a execuo de diversos modelos de programao para
processa-
mento dos dados, possuindo modelos que realizam processamento em
lotes (MapReduce),
processamento de grafos (Giraph [10]), consultas relacionais no
estilo SQL (Hive [11]),
dentre outros.
Assim como na composio de servios, existem ferramentas que
permitem a criao
12
de composies de tarefas de big data [12, 13]. No entanto, no
existem ferramentas que
permitam realizar composies mistas com operaes de diferentes
domnios, tais como
servios web, tarefas do Hadoop ou operaes definidas pelo
usurio.
1.1 Motivao
Este trabalho tem como motivao propor uma linguagem que permita
a criao de
fluxos de trabalho mistos, isto , composies que possuam operaes
de chamadas de
servios web, tarefas de big data, funes definidas pelo usurio ou
qualquer outro tipo
de operao que o usurio queira utilizar. A linguagem proposta ser
uma abstrao que
representar linguagens baseadas em fluxos de trabalho, como BPEL
[14] e PEWS [15]. O
propsito principal expandir linguagens de composio baseadas em
fluxos de trabalho
para que elas possam realizar composies com operaes de
diferentes domnios.
Acreditamos que, graas ferramenta proposta nesta dissertao,
pessoas que j tem
conhecimento prvio de ferramentas de composio de servios web,
tais como BPEL e
PEWS enfrentariam menos problemas para criar composies mistas,
podendo combi-
nar numa mesma composio tarefas de big data, servios web,
operaes definidas pelo
usurio ou operaes de qualquer outro domnio.
1.2 Objetivos
O objetivo geral deste trabalho propor uma mquina de reduo de
grafos extensvel,
de forma a permitir a criao de fluxos de trabalho envolvendo
servios web, tarefas de
big data, funes definidas pelo usurio, bem como qualquer outro
tipo de operao que
o usurio queira utilizar.
Este trabalho possui os seguintes objetivos especficos:
Propor uma linguagem que permita a criao de fluxos de trabalho
com operaesde diferentes domnios;
Propor as regras de traduo e reduo para compor uma mquina de
reduode grafos extensvel. As regras de traduo iro transformar
programas escritos na
linguagem proposta em grafos. As regras de reduo transformaro
estes grafos em
novos grafos e a extensibilidade permitir que novas operaes
possam ser utilizadas
pela mquina utilizando pouco esforo;
13
Implementar a mquina de reduo de grafos proposta;
Propor estudos de caso para demonstrar o funcionamento da mquina
de reduoimplementada.
1.3 Organizao do trabalho
Este trabalho est organizado em captulos, divididos da seguinte
forma: no captulo
2 so apresentados os principais conceitos relacionados a servios
web, composio de
servios, big data e mquinas de reduo. O captulo 3 apresenta dois
trabalhos relacio-
nados: PEWS-AM e Pony. O captulo 4 apresenta a mquina proposta
MiniBPEL-AM. A
implementao da mquina MiniBPEL-AM mostrada no captulo 5. Estudos
de caso e
anlises so apresentados no captulo 6, demonstrando o
funcionamento da mquina para
diferentes domnios. Por fim no captulo 7 so apresentadas as
concluses do trabalho,
principais contribuies, limitaes e trabalhos a serem
desenvolvidos.
14
2 Fundamentao
Este captulo descreve os conceitos relacionados a servios web,
composio de ser-
vios e linguagens de composio de servios web. Sero apresentados
conceitos de big
data, a ferramenta Hadoop, composio de tarefas do Hadoop e ser
feita uma listagem
das ferramentas que podem ser usadas para construir composies de
tarefas do Hadoop,
mostrando as vantagens e desvantagens de cada ferramenta. Por
fim ser mostrado o con-
ceito de mquinas de reduo de grafos, seu surgimento e onde so
utilizadas atualmente.
2.1 Servios Web
Servios web so aplicaes que podem ser executadas remotamente
(via Internet)
e possuem uma interface bem definida que descreve como as
operaes do servio web
devem ser acessadas, bem como os parmetros de entrada e sada que
cada operao
utiliza.
Com o crescimento da Internet uma onda de inovao mudou o modo
como os negcios
so conduzidos nas organizaes. Para acompanhar este crescimento
as empresas tiveram
de se adaptar. Visando uma melhor automao, processos de negcio
mais eficientes e
visibilidade global, as organizaes e governos procuravam por uma
soluo de negcios
mais robusta e integrada, que pudesse ser utilizada em suas
aplicaes j existentes,
adaptar-se rapidamente s suas necessidades e evoluir junto com
os os requisitos do modelo
de negcios da organizao [16].
Assim os servios web comearam a se popularizar como soluo para
empresas que
desejavam implementar modelos de negcio mais dinmicos. Os
servios web promoveram
a implementao de aplicaes fracamente acopladas em detrimento das
antigas aplica-
es fortemente acopladas, que eram utilizadas pelas empresas nos
modelos de negcio
anteriores.
Servios web representam um meio de implementar componentes para
aplicaes com
15
acesso Internet. So componentes de software modulares, auto
contidos e auto descritos.
Estes componentes so disponibilizados na Internet podendo ser
acessados diretamente ou
com o auxlio de diretrios de servios web. A principal tecnologia
utilizada para descrever
estes diretrios a UDDI (Universal Description, Discovery, and
Integration) [17].
Com o auxlio de diretrios UDDI, servios web podem ser facilmente
publicados e
buscados. Desta forma uma organizao pode publicar um dos seus
servios na Internet,
fazendo uso de diretrios UDDI, enquanto um cliente pode realizar
uma busca no mesmo
diretrio UDDI, encontrar o servio publicado pela empresa e fazer
uso do servio sem a
necessidade de um contato direto com a empresa que publicou o
servio.
De acordo com o W3C (Word Wide Web Consortium) [18] os servios
web so siste-
mas de software desenhados para dar suporte a interaes entre
computadores utilizando
uma rede. Servios web possuem interfaces que so descritas por um
documento em um
formato que possa ser lido pelas mquinas, chamado WSDL (Web
Services Description
Language) [19]. Eles Interagem com outros servios atravs de
trocas de mensagens
SOAP (Simple Object Access Protocol) [20], que normalmente so
transportadas utili-
zando HTML (Hypertext Markup Language) [21] e XML (Extensible
Markup Language)
[22].
2.1.1 Composio de Servios Web
A composio de servios web cria um novo servio a partir da
combinao de outros
servios pr existentes, respeitando algumas regras e restries
definidas pela linguagem
de composio utilizada [23].
Existem dois paradigmas de composio de servios web: orquestrao e
coreogra-
fia [3]. Na orquestrao existe a figura do servio orquestrador,
que fica responsvel por
coordenar os demais servios da composio. J a coreografia define
uma forma no cen-
tralizada de colaborao entre os servios que participam da
composio.
Este trabalho ter foco na composio de servios web por
orquestrao, desta forma,
de agora em diante quando o termo composio de servios web for
utilizado, ficar
implcito que se trata de uma composio de servios web por
orquestrao.
Servios web so descritos usando WSDL. Esta descrio declara
apenas o nome e
os tipos das operaes do servio web, definindo somente a
especificao da interface do
servio. Ela no descreve o comportamento observvel do servio web.
Alm disto, WSDL
no possui meios de descrever composies de servios web. A
necessidade por interfaces
16
de comportamento melhor definidas, motivou a definio de novas
linguagens e tcnicas
de descrio para estas interfaces [24].
2.1.2 Linguagens de Composio
A literatura dispe de uma srie de linguagens para a especificao
de composies,
cada uma com suas regras, restries e modos de montar a
composio.
A linguagem BPEL (Business Process Execution Language) [14] o
padro usado
hoje na maioria das aplicaes de servios web compostos. Outras
linguagens incluem
PEWS (Path Expressions for Web Services) [15] que utiliza
predicate path expressions
para criar composies; BPML (Business Process Modeling Language)
[25] que define
um modelo abstrato e uma gramtica para expressar processos
executaveis, no limitado
apenas a servios web; WSCI (Web Service Choreography Interface)
[26] uma exteno
do WSDL que define como os servios web pertencentes a uma
coreografia devem se
comunicar [3]; WSFL (Web Services Flow Language) [27] uma
linguagem de composio
de servios web que define como os servios devem trocar mensagens
e como o fluxo de
execuo deve ser executado [3]; e XLANG [28] que tem foco na
criao de processos de
negcio e no comportamento da troca de mensagens entre servios
participantes de uma
composio [3].
Neste trabalho ser utilizada uma notao de composio de servios
web definida
de forma abstrata, a qual contm os principais construtores
presentes em linguagens de
orquestrao como BPEL e PEWS. Escolheu-se BPEL por ser a
linguagem para criao de
composies mais utilizada atualmente e PEWS por ter sido criada
no grupo de pesquisa
ao qual este trabalho est inserido.
Com o surgimento de novas tecnologias, se faz necessrio utilizar
novas operaes, tais
como operaes de big data, em um fluxo de trabalho para realizao
de uma tarefa. A
prxima sub-seo detalhar o que big data e ir mostrar ferramentas
e operaes que
podem ser utilizadas em um fluxo de trabalho em conjunto com
servios web.
2.2 Big Data: Processamento de Grandes Volumes deDados
Big data refere-se ao conjunto de dados que to grande que os
sistemas de banco de
dados tradicionais falham em suas tarefas de captura,
armazenamento, gerenciamento e
17
anlise destes dados [13].
Esta definio no impe o tamanho que big data pode ter. Com o
avano da tecnolo-
gia o tamanho do conjunto de dados que define big data tambm
cresce. O tamanho de big
data tambm varia dentro de diferentes setores da indstria,
dependendo das ferramen-
tas disponveis para o tratamento tradicional de dados e do
tamanho dos dados usados
normalmente.
Considerando estes fatos, big data pode ter diferentes tamanhos
dentro de diferentes
setores da indstria, variando de alguns terabytes1 a milhares de
petabytes2.
Para realizar o processamento de conjuntos de dados to grandes e
complexos novas
tecnologias e ferramentas foram propostas. Dentre elas Hadoop a
que vem atraindo mais
ateno, por ser de cdigo livre e conseguir realizar o
processamento de dados, reduzindo
problemas com escalabilidade, falhas e tempo de
processamento.
2.2.1 Modelos Paralelos
O tradicional modelo de Von Neumann serviu de base para a
implementao e com-
preenso de algoritmos seqenciais por muito tempo. Servindo at
mesmo como modelo
de referncia para a criao de hardware. No entanto este modelo no
apresenta bons
resultados para algoritmos paralelos, de forma que novos modelos
de mquinas foram
propostos, tais como os modelos PRAM (Parallel Random Access
Machine) [29] e BSP
(Bulk Synchronous Parallel) [6].
Um dos primeiros modelos que permitia a implementao de
algoritmos para progra-
mao paralela foi o modelo PRAM. Este modelo permitia um melhor
raciocnio terico
sobre a implementao de algoritmos paralelos, porm possua uma
srie de premissas que
no podiam ser cumpridas pelo hardware, principalmente porque o
custo de comunicao
maior que o custo computacional e o nmero de processadores
limitado [30].
Para refletir melhor as caractersticas de hardware, Valiant
props o modelo BSP.
Um computador BSP pode ser definido como um conjunto de p
processadores, cada um
com memria local e conectados por algum meio de ligao ponto a
ponto. Algoritmos
BSP realizam aes em supersteps, onde cada processador recebe uma
entrada de dados
no incio do superstep, realiza processamento de forma assncrona,
e comunica qualquer
dado de sada ao final do superstep. Uma barreira de sincronizao
utilizada ao final de11012 bytes ou 1000 gigabytes21015 bytes ou
1000 terabytes
18
casa superstep com o propsito de sincronizar cada um dos p
processadores do sistema.
Cada processador pode se comunicar diretamente com os demais
processadores provendo
controle total de como os dados so distribudos em cada
superstep.
Mesmo bem especificados, nenhum destes modelos atraiu tanta
ateno quanto o mo-
delo MapReduce [5], por permitir que algoritmos paralelos possam
ser facilmente imple-
mentados e executados. Este modelo vem atraindo cada vez mais
adeptos e sendo aplicado
por grandes empresas, processando uma quantidade de dados nunca
antes vista.
2.2.2 MapReduce
MapReduce um modelo de programao com uma implementao associada
utilizado
para processar e gerar grandes conjuntos de dados. Este modelo
disponibiliza uma interface
que facilita a implementao por parte do programador de
algoritmos que processam
eficientemente uma grande quantidade de dados.
Desenvolvido e largamente utilizado pelo Google [5], MapReduce
tambm faz parte
do projeto de open source Apache Hadoop, sendo utilizado por
grandes empresas como
Yahoo!, IBM, The New York Times, Facebook, Twitter e um grande
nmero de universi-
dades [31]. Empresas como Amazon e Microsoft permitem at que
seus usurios executem
programas MapReduce em suas nuvens [32, 33]. MapReduce vem sendo
utilizado para
resolver problemas complexos de diversas reas, incluindo
processamento de dados, mine-
rao de dados e anlise de grafos [30].
No framework 3 MapReduce, uma computao definida como a seqncia
de passos
map, shuffle e reduce que operam sobre o conjunto de valores X =
{x1, x2, . . . , xn}:
No passo map uma funo aplicada a cada valor xi para produzir um
conjuntode chaves/valor (k, v). Para permitir o paralelismo o
processamento da funo (xi)
deve depender apenas de xi.
O passo shuffle combina todos os conjuntos chave/valor gerados
no passo map quepossuem uma mesma chave, produzindo um conjunto
chave/valor intermedirio
Pk = (k, Lk), onde Lk = {v1, v2, . . . } uma lista com os
valores dos pares quepossuem a mesma chave k.
3Um framework uma arquitetura codificada para resolver problemas
de um domnio e que podeser utilizado para resolver problemas
especficos [34]. Trazendo como principais benefcios
modularidade,reusabilidade, extensibilidade e inverso de controle
[35].
19
No passo reduce uma funo aplicada a cada uma dos Pk pares de
chave/va-lor intermedirios criados no passo shuffle, para produzir
um conjunto de valores,
y1, y2, . . . . A funo pode ser definida seqencialmente em Pk,
porm seu proces-
samento deve ser independente de outras listas Pk com k 6=
k.
O paralelismo do MapReduce vem do fato de cada funo e pode ser
executada em
um processador independentemente dos demais. O usurio deve
definir apenas as funes
e e o framework se encarrega de executar os passos
map-shuffle-reduce e enviar dados
para os processadores disponveis [31].
2.2.3 Hadoop
O conjunto de bibliotecas Hadoop4 [37] um framework gratuito
para programao,
que d suporte ao processamento de grandes conjuntos de dados em
um ambiente de
computao distribuda, utilizando modelos de programao simples.
Atualmente ele faz
parte do projeto Apache e financiado pela fundao Apache
[38].
O framework adequado ao processamento em clusters de milhares de
ns e analisa
milhares de terabytes de dados, permitindo que desenvolvedores
possam criar aplicaes
simples sem se preocuparem com os problemas comuns de aplicaes
distribudas, tais
como: concorrncia, controle de falhas, gerenciamento de
recursos, dentre outros.
O Hadoop tenta preservar a localidade dos dados enviando as
aplicaes para prximo
dos dados, diminuindo assim o trfego de dados pela rede, uma vez
que as aplicaes so
bem menores que os conjuntos de dados em que se trabalha.
O HDFS (Hadoop Distributed Filesystem) [39] um sistema de
arquivos distribudo
que permite o acesso em larga escala dos dados armazenados.
Possui uma interface limi-
tada que permite o gerenciamento de arquivos e possibilita a
escalabilidade do sistema.
O HDFS utiliza blocos de tamanho definido para armazenamento de
dados. Estes blocos
so replicados pelo cluster para permitir acesso rpido e
confivel.
O Hadoop foi inspirado no framework MapReduce5 do Google [5].
Por conta disto,
as verses iniciais do Hadoop (Figura 1, lado esquerdo) possuam
forte ligao com o
framework MapReduce. Este modelo antigo trazia problemas
manipulao de arquivos,4O criador do Hadoop, Doug Cutting, usou o
nome do elefante de pelcia de seu filho para dar nome
ao framework [36]5Este framework quebra aplicaes em pedaos
menores que podem ser executados em diferentes ns
de um cluster de forma concorrente.
20
pois o gerenciamento de recursos (HDFS) estava diretamente
ligado ao modelo de pro-
gramao MapReduce. Esta ligao dificultava a realizao de certos
tipos de operaes
com os dados armazenados, pois forava o uso do MapReduce para
que houvesse acesso
aos dados. [40].
O framework YARN (Yet Another Resource Negotiator) [40] foi
criado para diminuir
o acoplamento entre o gerenciamento de recursos e o framework de
programao. Neste
contexto, MapReduce apenas uma das aplicaes que ser executada
utilizando o YARN
como interface, como mostram as Figuras 1 e 2. Outros frameworks
como Tez [41], Spark
[42], Storm [43], Giraph [10], e outros, foram adaptados e
passaram a ser executados
pelo YARN. Desta forma, existe uma maior flexibilidade na
escolha dos frameworks que
acessaro os dados armazenados no sistema de arquivos
distribudo.
Figura 1: Desacoplamento do gerenciamento de recursos [44].
Como mostrado na Figura 1, MapReduce passa a realizar apenas o
processamento de
dados, deixando o gerenciamento de recursos a cargo do YARN.
Figura 2: YARN gerencia recursos para mltiplos modelos de
programao [44].
O Hadoop, em sua verso 2.2.0 (Figura 2), formado pelo sistema de
arquivos distri-
budos do Hadoop (HDFS), framework YARN, framework MapReduce
baseado no YARN
21
e um conjunto de utilitrios comuns que do suporte aos outros
mdulos do Hadoop.
Segue a lista de alguns dos projetos que podem ser utilizados em
um cluster Hadoop:
MapReduce permite o processamento em paralelo de grandes
conjuntos de dados.Quebra o conjunto de dados em dados menores que
so processados por cdigos
fornecidos pelos usurios dentro das funes Map e Reduce;
Hive facilita a utilizao do Hadoop por profissionais que esto
mais familiariza-dos com SQL, permitindo-lhes consultar dados
armazenados no Hadoop como nos
bancos de dados relacionais tradicionais. Pesquisas podem ser
feitas nestes dados
utilizando um dialeto SQL chamado HiveQL, que por sua vez so
traduzidas para
tarefas MapReduce [12].
Pig assim como Hive possibilita a criao de scripts que permitem
que usuriospossam trabalhar com dados armazenados no Hadoop sem a
necessidade de im-
plementar tarefas MapReduce diretamente. Pig utiliza uma
linguagem de script de
alto nvel chamada Pig Latin. Primitivas desta linguagem so
traduzidas para ta-
refas MapReduce. Caso a linguagem no possua alguma funo, o
usurio pode
estender a linguagem criando suas prprias funes [45].
O interesse pela utilizao do Hadoop vem crescendo tanto no meio
acadmico quanto
no meio empresarial. Dentre as empresas que utilizam o Hadoop
esto: Google, Yahoo,
IBM, Amazon, Facebook, dentre muitas outras [9].
2.2.4 Composio de Tarefas do Hadoop
Assim como nos servios web, existem ferramentas para realizao de
composies
de tarefas para o Hadoop. As seguintes ferramentas so algumas
das opes que se pode
utilizar para criar composies:
Cascading [46] uma camada de abstrao para o MapReduce. Permite a
criao eexecuo de composies, escondendo a complexidade de tarefas
MapReduce [36];
Hamake [47] foi desenvolvido para resolver problemas de
processamento incrementalde grandes conjuntos de dados. Permite a
formulao de solues em forma de fluxos
de dados, ao invs de composio de tarefas;
22
Azkaban [48] um framework de execuo de propsito geral que
permite a execuode tarefas de vrios tipos, como tarefas MapReduce,
Pig, Hive, shell scripts, dentre
outras [49];
CloudWF [50] um sistema de composio escalvel executado pelo
Hadoop. Suascomposies so formadas por tarefas MapReduce ou
programas legados (aplicaes
que no dependem da API do MapReduce);
Apache Oozie [51] um sistema de composio de tarefas que busca
implementarescalabilidade, concorrncia, segurana e operabilidade
[52];
Estas ferramentas de composio possuem um conjunto limitado de
primitivas para
o processamento da composio. Em geral existem apenas os
construtores: fork, join e
decision, os quais fornecem, respectivamente, a capacidade de
iniciar uma nova linha
(thread) de processamento, juntar threads e fazer escolhas entre
vrias alternativas [53].
Cada uma destas abordagens adota um conjunto de prticas e mtodos
para reali-
zao de composies, o que dificulta a integrao de tais ferramentas
com o processo
de negcio das empresas. H um perodo de aprendizado, treinamento
e adaptao para
utilizao destas ferramentas em conjunto com as ferramentas que
gerenciam os processos
de negcios das empresas. Empresas que j utilizam BPEL acabam
tendo que gastar mais
recursos para que seus sistemas possam trabalhar em conjunto com
o Hadoop.
O objetivo deste trabalho propor uma ferramenta que facilite a
integrao de tec-
nologias de composio. Permitindo que empresas que j utilizam
alguma linguagem de
composio de servios web, como BPEL, PEWS, WSFL, dentre outras,
possam utilizar o
conhecimento adquirido nestas linguagens para criao de composies
de servios web em
conjunto com outros tipos de operaes, como por exemplo, tarefas
do Hadoop, funes
definidas pelo usurio ou outras.
A mquina proposta trar os benefcios de linguagens como BPEL para
o mbito
do big data. Um conjunto maior de diretivas lgicas podem ser
utilizadas, facilitando a
adaptao de empresas que j usam linguagens de composio de servios
para resoluo
de problemas mais complexos. Possibilita ainda que tarefas do
Hadoop possam trocar
informaes com operaes de outros domnios dentro de uma mesma
composio.
23
2.2.5 Apache Oozie
Oozie um sistema de fluxos de trabalho desenhado especialmente
para trabalhar
com Hadoop [45]. Este sistema foi desenhado como uma aplicao web
feita em Java [52].
Os fluxos de trabalho do Oozie so representados como sequencias
de aes escritas
em um arquivo xml, com cada ao apontando para a prxima ao a ser
executada.
Uma ao inicial e final devem ser informadas para que o Oozie
possa saber onde iniciar
e finalizar a execuo do fluxo de trabalho. As aes fork e join do
Oozie so utilizadas
com o mesmo propsito da primitiva || (paralelo) da mquina
MiniBPEL-AM, ou seja,permitir a execuo de aes em paralelo.
Coordinators so utilizados para disparar fluxos de trabalho
quando determinados
eventos ocorrem, como a chegada de um arquivo em um diretrio ou
a verificao de uma
determinada data. Oozie permite a execuo de diversos tipos de
tarefas Hadoop, tais
como: mapreduce, pig, hdfs, hive e scoop. Porem o sub-conjunto
de operaes hdfs que
pode ser executado reduzido, no permitindo por exemplo que copia
de arquivos possam
ser realizadas.
2.3 Mquinas de Reduo de Grafos
Uma mquina de reduo de grafos representa um programa na forma de
grafo e
aplica sucessivas regras de reduo at que o grafo seja reduzido a
um grafo irredutvel
ou um valor. Este processo de reduo representa a execuo do
programa.
O termo reduo de grafos foi descrito pela primeira vez por
Wadsworth [54] como
parte de um processo que descreve uma soluo para avaliao de
expresses. Este processo
permitia o compartilhamento de expresses avaliadas, desta forma
uma expresso era
avaliada zero ou no mximo uma vez. O processo ficou conhecido
posteriormente como
avaliao preguiosa ou lazy evaluation [55, 56].
Em uma reduo de grafos, programas e suas expresses so
representados como grafos
direcionados. Um conjunto de regras definido para realizar
transformaes nestes grafos.
A reduo de grafos permite que uma expresso representada como um
grafo possa ser
reduzida, atravs de uma transformao, para um outro grafo que
representa a avaliao
da expresso. As regras de transformao so aplicadas
sucessivamente at que no seja
mais possvel aplicar regras.
Uma das vantagens de se utilizar reduo de grafos a possibilidade
de se compartilhar
24
o resultado de expresses j avaliadas, isto , caso uma expresso
E1 tenha sido avaliada
e uma outra expresso E2 necessite do resultado de E1, E1 no ser
avaliada novamente
para que E2 possa usar seu resultado.
O Exemplo 1 a seguir descreve o processo de avaliao de um
pequeno programa,
mostrando como a reduo de grafos pode ajudar na avaliao de
expresses. Porm
antes se faz necessrio revisar alguns conceitos relacionados a
linguagens de programao
usados neste exemplo.
No contexto de linguagens de programao a estratgia de avaliao
dos argumentos de
uma funo um importante aspecto que deve ser observado. A
estratgia de avaliao
determina onde e quando a chamada das funes e a avaliao dos
argumentos devem
ocorrer. A avaliao pode ser estrita ou no estrita. Na avaliao
estrita os parmetros de
uma funo so sempre avaliados antes da chamada da funo. Enquanto
que na avaliao
no estrita os argumentos de uma funo s so avaliados caso estes
sejam utilizados no
corpo da funo.
A ordem normal de avaliao na avaliao no estrita uma estratgia de
avaliao
onde o redex 6 mais a esquerda sempre reduzido, aplicando as
funes antes de avaliar
seus argumentos. No Exemplo 1 ser feita a comparao entre as
avaliaes chamada por
nome (call-by-name) e chamada por necessidade (call-by-need) da
avaliao no estrita.
Na estratgia de avaliao chamada por nome as expresses s so
avaliadas quando
chamadas e so avaliadas todas as vezes que elas forem utilizadas
[57]. J na estratgia
de avaliao chamada por necessidade as expresses so avaliadas
quando so chamadas e
as expresses so avaliadas apenas uma vez, guardando o resultado
da avaliao de uma
expresso para uso posterior [58].
Exemplo 1:
O cdigo mostrado na Figura 3 o de um programa que calcula o
quadrado do
quadrado de sete. So definidas as funes: sqr que calcula o
quadrado de um nmero e
retorna o resultado atravs da aplicao da funo multi; a funo main
realiza o clculo
do quadrado do quadrado de sete; e a funo multi que realiza a
multiplicao algbrica
de dois nmeros.
Realizando a execuo deste programa pela ordem normal de avaliao
e utilizando a
estratgia de avaliao chamada por nome, tem-se a ordem de avaliao
apresentada pela
Figura 4.6A palavra redex uma abreviao para reducible expression
e representa uma expresso que pode ser
reduzida.
25
sqr x = multi x xmain = sqr ( sqr 7 )
Figura 3: Programa que calcula o quadrado do quadrado de
sete.
1 main -> sqr ( sqr 7 )2 -> multi ( sqr 7 ) ( sqr 7 )3
-> multi ( multi 7 7 ) ( sqr 7 )4 -> multi ( 49 ) ( sqr 7 )5
-> multi ( 49 ) ( multi 7 7 )6 -> multi ( 49 ) ( 49 )7 ->
2401
Figura 4: Avaliao chamada por nome.
As funes sublinhadas indicam quando cada uma das expresses foi
avaliada. Para o
cdigo acima, a primeira funo a ser avaliada, na linha 1, foi a
funo main resultando na
expresso sqr ( sqr 7 ). Neste ponto a primeira funo sqr
avaliada. Substituindo a
ocorrncia da primeira funo sqr pela funo multi tem-se como
resultado a expresso
da linha 2. Segue-se deste modo avaliando todas as funes quando
necessrio at obter
como o resultado final da computao o valor 2401.
Neste exemplo pode-se notar que a avaliao chamada por nome
realiza computao
em expresses que j haviam sido calculadas antes. Como pode ser
notado pela avaliao
de sqr 7 nas linhas 2 e 4, e de multi 7 7 nas linhas 3 e 5. Este
comportamento faz com
que a avaliao de chamada por nome, no tenha um bom desempenho
quando expresses
aparecem mais de uma vez no corpo de uma funo.
Utilizando a estratgia de avaliao chamada por nome, no h a
possibilidade de
se compartilhar o resultado de avaliaes j computadas. Porm
quando a expresso
representada em forma de grafo, h a possibilidade de se
compartilhar o resultado das
avaliaes atravs da utilizao de ponteiros. Esta estratgia foi
proposta inicialmente por
Wadsworth [54] e serviu de inspirao para a implementao da
avaliao chamada por
necessidade, ou lazy evaluation [55, 56].
A representao de uma expresso em forma de grafo descrita na
Figura 5, onde
as aplicaes de funes(@) so ns binrios. Para a reduo, procura-se
o redex mais
exterior e mais a esquerda(ordem normal). E ao reduzir um
sub-termo atualiza-se o grafo
com o resultado.
Os passos para reduo de uma expresso so apresentado pelo
Algoritmo 1. O al-
goritmo entra em um loop, se houver algum redex que no tenha
sido avaliado ainda, o
26
@
Fun Arg
Figura 5: Grafo de uma chamada de mtodo.
algoritmo seleciona o redex mais externo ao grafo, realiza sua
reduo, substitui o redex
pelo resultado da reduo e verifica novamente se existe mais
algum redex que no foi
avaliado. Caso exista redex que ainda no tenha sido avaliado o
processo se repete, caso
contrrio o algoritmo encerrado.
Algoritmo 1 Reduo de grafos.enquanto existe redex que no foi
avaliado faaselecione o redex mais externo;reduza-o;substitua o
redex pelo resultado de sua reduo;
fim enquanto
(a)
@
sqr
(b)@
@2
multi
(c)
@
@2
multi
(d)
Figura 6: Regras utilizadas na reduo de grafos.
Na Figura 6 so ilustradas as regras utilizadas para a reduo do
grafo da Figura 7.
Neste exemplo s h duas regras: (i) a regra que transforma uma
chamada da funo sqr
(6a) em uma chamada da funo multi (6b); e (ii) a regra que
transforma a chamada da
funo multi (6c) em um valor (6d) atravs da multiplicao dos
valores de @ e @2.
A Figura 7 mostra o processo de avaliao chamada por necessidade
do programa
mostrado na Figura 3. As expresses sublinhadas nos grafos so as
expresses que sero
27
avaliadas (reescritas) utilizando as regras mostradas na Figura
6 e iro gerar o prximo
grafo.
(a)
@1
sqr @2
sqr 7
(b)
@1
@3 @2
sqr 7multi
(c)
@1
@3 @2
@4 7multi
multi
(d)
@1
@3 49
multi
(e)
2401
Figura 7: Avaliao chamada por necessidade(Reduo de Grafos).
Na Figura 7a visualizado o grafo que representa a chamada da
funo main. A raiz
do grafo, @1 representa a aplicao da funo main, que possui
arestas apontando para
seus dois ns filhos, a chamada da funo sqr a esquerda e a
direita do argumento desta
funo, que representado pelo subgrafo @2. Por sua vez o subgrafo
@2 possui dois ns
filhos, com arestas apontando para a chamada da funo sqr a sua
esquerda e a sua
direita um n com o valor 7.
A prxima expresso a ser avaliada neste grafo da Figura 7a a
expresso sqr a
esquerda de @1, que aps sua reescrita, utilizando a regra 6a,
ser substituda no grafo
original(Figura 7b) por um n @3 representando a aplicao da funo
sqr. So adicio-
nados um n multi representando a chamada da funo multi, uma
aresta de @3 para
multi e uma aresta de @3 para o resultado da aplicao da expresso
sqr 7(@2). Nesta
ltima aresta adicionada ao grafo pode-se perceber que o
resultado da avaliao de @2ser utilizado por @1 e @3, ou seja, @2
ser avaliado apenas uma vez e o resultado de sua
avaliao ser compartilhado com os ns @1 e @3 evitando reavaliaes
desnecessrias.
No grafo da Figura 7b procura-se o prximo redex que pode ser
avaliado, no caso a
chamada da funo sqr. Como foi feito no grafo anterior,
substitui-se a ocorrncia de sqr
pela aplicao da funo sqr (Regra 6a) com uma aresta apontando
para um novo n com
a chamada da funo multi e outra aresta apontando para o n de
valor 7. Percebe-se
aqui novamente o compartilhamento do valor 7 pelos ns @2 e
@4.
28
O prximo redex a ser avaliado no grafo da Figura 7c a chamada da
funo multi,
que aps ser avaliado utilizando a regra 6c, retorna o valor 49.
O n @2 ento substitudo
por um n de valor 49, como pode ser visto na Figura 7d.
Finalmente, a funo multi no grafo da Figura 7d avaliada (Regra
6c) obtendo
como resultado o valor 2401. O n @1 substitudo pelo resultado da
avaliao, ficando
apenas com um n de valor 2401. Como no h mais nenhum redex que
pode ser reduzido
o algoritmo encerrado.
Neste exemplo nota-se que a avaliao chamada por necessidade
realiza menos ava-
liaes que a estratgia chamada por nome, quando uma expresso
ocorre mais de uma
vez no corpo de uma funo. Porm necessrio um trabalho extra para
representar cada
expresso na forma de grafos, realizar o gerenciamento correto
das redues e se tomar
um cuidado especial para a coleta de lixo.
Normalmente linguagens imperativas adotam a avaliao chamada por
valor, que rea-
liza apenas uma avaliao de todas as expresses existentes no
programa. Evitando assim
o problema de duplicao de computaes. O problema desta avaliao
que mesmo que
uma expresso no seja utilizada no programa ela ainda ser
avaliada.
O processo reduo de grafos se tornou uma ferramenta importante,
utilizado pelas
linguagens funcionais para implementao do lambda clculo [59].
Permitindo a imple-
mentao de mquinas de reduo tanto seqenciais quanto paralelas.
Vrias mquinas
abstratas foram propostas, trazendo melhorias a cada
implementao.
Turner foi o primeiro a implementar uma mquina de reduo de
grafos, utilizando
combinadores SKI [60]. Sua mquina executava com maior eficincia
programas que ex-
ploravam funes de alta ordem7, quando comparada com
interpretadores convencionais
da poca [61].
Com o tempo, vrias melhorias foram propostas para implementaes
de mquinas
mais eficientes. Surgiram implementaes com base no lambda
clculo, reduo de com-
binadores ou reduo de strings. Estas mquinas ficaram conhecidas
como puras por
selecionarem o prximo passo de reduo dinamicamente [62].
Como alternativa s mquinas de reduo puras, surgiram as mquinas
de reduo
programada. Onde a escolha do prximo passo da reduo definido
atravs da anlise
esttica (compilao) da expresso original [63]. Por exemplo, em
uma expresso condici-7Funes de alta ordem so funes que utilizam
outras funes como argumento de entrada, ou
retorna uma funo como sada.
29
onal, a condio testada primeiro e depois um ou outro ramo do
grafo escolhido para
ser avaliado, ao invs de se construir o grafo da expresso
condicional e avaliar todo o
grafo e depois se escolher o prximo ramo.
Este processo de reduo programada trouxe novas possibilidades na
busca de me-
lhor eficincia para a implementao de mquinas de reduo de grafos.
Implementada
utilizando reduo programada, a mquina G criada por Johnsson e
Augustsson [64, 65]
tinha como objetivo a melhoria de performance das avaliaes de
aplicao de expresses.
Posteriormente foi melhorada por Peyton Jones, em sua mquina STG
(Spineless Tagless
G-machine) [66]. Sendo que esta ltima utilizada no GHC (Haskell
Glasgow Compiler)
que provavelmente o compilador Haskell mais utilizado atualmente
[67].
Outras mquinas de reduo que podem ser citadas: GRIP [68], ALICE
[69], mquina
(v, G) [70], NORMA [71], dentre muitas outras [60,63,72]
2.4 Concluses do Captulo
Neste captulo foi feita uma reviso da literatura e foram
apresentados os principais
conceitos relacionados a servios web, tais como, composies de
servios, linguagens de
composio e a definio da linguagem MiniBPEL proposta.
Um resumo sobre big data e suas principais ferramentas foi
apresentado, demonstrando
conceitos como o surgimento dos modelos paralelos, MapReduce,
Hadoop e as ferramentas
de composio existentes.
Por fim, foram expostos os conceitos por traz das mquinas de
reduo de grafos,
detalhando seu funcionamento e mostrando onde so utilizadas hoje
em dia. O prximo
captulo mostrar alguns trabalhos relacionados proposta.
30
3 Trabalhos Relacionados
Neste captulo sero apresentados alguns trabalhos relacionados.
Na seo 3.1 ser
apresentada a mquina PEWS-AM que permite a criao de fluxos de
trabalho para
servios web utilizando a linguagem PEWS. O sistema para criao de
fluxos de trabalho
para o Hadoop chamado Pony ser apresentado na seo 3.2.
3.1 Mquina de Reduo de Grafos PEWS-AM
Na tese de mestrado de Aguiar [73] foi proposta uma variante de
PEWS, uma lingua-
gem semelhante a BPEL, que permite a criao de fluxos de trabalho
para composio de
servios web utilizando grafos. Uma mquina de reduo de grafos foi
proposta e imple-
mentada como prova de conceito. A esta mquina foi dado o nome de
PEWS-AM.
A mquina implementada por Aguiar foi utilizada como modelo base
para a criao
da mquina MiniBPEL-AM proposta neste trabalho. Esta seo tratar
de explicar o
funcionamento da mquina PEWS-AM e no prximo captulo (4) a mquina
MiniBPEL-
AM ser detalhada.
A mquina PEWS-AM transforma uma composio escrita na linguagem
PEWS em
um grafo e permite a interpretao direta deste grafo, utilizando
um conjunto de regras
de reduo propostas no trabalho.
A mquina PEWS-AM utiliza dois conjuntos de regras:
regras de traduo T , que traduzem programas escritos em PEWS
para a sua re-presentao na forma de grafos;
regras de reduo, que realizam transformaes/redues nos
grafos.
A execuo de um programa PEWS corresponde a aplicaes sucessivas
de regras
de reduo, a partir do grafo gerado pela funo T , at que o grafo
no possa ser maisreduzido por nenhuma das regras de reduo.
31
As regras de traduo e reduo apresentadas nesta seo so baseadas
no draft [74],
onde as regras propostas foram revisadas e passaram por um
refinamento em comparao
com o trabalho original de Aguiar [73].
3.1.1 Construtores da Linguagem
O conjunto de regras a seguir define PEWS, uma linguagem que
contm operaes
mais comuns para tratar composies de servios web. A linguagem
definida como:
P ::= S(E,X) | P1||P2 | P1;P2 | [E1]P1 + [E2]P2 | if [E1] P1 |
unfolding P1 | unfold
E ::= id | n | t | E1 + E2 | E1 E2 | E1 E2 | E1/E2 | E1 | E1 and
E2 | E1 or E2| not E1 | E1 == E2 | E1 < E2 | E1 E2 | E1 > E2
| E1 E2 | ( E1)
As regras de E descrevem a sintaxe de expresses aritmticas e
booleanas. Permitindo
o uso de identificadores, literais, operadores lgicos,
aritmticos e relacionais mais comuns.
Enquanto as regras de P definem a chamada de servios web e
regras de composio
utilizadas pela linguagem, como:
S(E,X): corresponde a chamada de um servio web, onde S o
identificador doservio, E uma lista de expresses E que serviro como
parmetros de entrada
para o servio e X uma lista de identificadores id que guardaro
valores resultantes
da execuo do servio;
P1||P2: uma composio em paralelo, onde os dois programas so
executados con-correntemente e a composio s se encerra quando os
dois programas terminarem
suas execues;
P1;P2: define uma composio seqencial, onde um programa P2 s pode
comeara executar depois do trmino de P1;
[E1]P1 + [E2]P2: define escolhas no determinsticas, onde E1 e E2
so expressesbooleanas (guardas) que devem ser satisfeitas para a
execuo dos programas P1 e
P2 respectivamente.
if [E1] P1: um condicional, onde a guarda E1 deve ser satisfeita
para a execuodo programa P1
32
unfolding P1 e unfold: regras para repetio. Quando unfolding P1
avaliado,uma cpia P 1 criada a partir de P1 onde todas as
ocorrncias de unfold dentro de
P1 so substitudas por unfolding P1.
Para a implementao destas regras dois tipos de restries so
impostas: restries
de fluxo de controle e restries de fluxo de dados.
As restries de fluxo de controle so impostas diretamente pelos
construtores da
linguagem. Por exemplo, em comandos seqenciais, h uma restrio de
fluxo de controle
entre um programa P1 e P2 indicando que o programa P1 deve ser
executado e concludo
antes do incio da execuo de P2.
Restries de fluxo de dados garantem que cada varivel vai estar
associada a um
valor antes de ser utilizada por alguma regra da linguagem, como
uma expresso ou uma
chamada de um servio web. Por exemplo, dada a seguinte
composio:
S1(X, Y )||S2(X,Z)||S3(Y, Z,W )
onde X a entrada dos servios web S1 e S2; Y e Z so sadas de S1 e
S2 (respecti-
vamente) e so entradas de S3, o qual produz W . Restries de
fluxo de dados entre os
servios S1 e S3 e entre os servios S2 e S3, indicariam que S3 s
pode ser executado
uma vez que, os servios S1 e S2 j tenham sido executados, e suas
variveis de sada
Y e Z foram guardadas em memria para uso do servio S3. Isto ,
mesmo com os trs
servios em paralelo, o servio S3 s ser executado depois da
concluso dos servios S1
e S2 graas as restries de fluxo de dados.
3.1.2 Mquina de Reduo de Grafos PEWS-AM
A mquina permite a transformao de programas PEWS em grafos e a
reduo
destes grafos atravs da aplicao de sucessivas regras de reduo. A
aplicao de regras
de reduo corresponde avaliao do fluxo de trabalho de servios
web.
O processo de execuo da mquina consiste de duas etapas: (i) a
transformao de
um programa PEWS em um grafo G utilizando regras de traduo T ; e
(ii) avaliao,onde o grafo G reduzido atravs da aplicao de
sucessivas regras de reduo.
No processo de traduo, os grafos gerados so representados por
triplas V,Ac, Ad,onde V representa o conjunto de vrtices; Ac so
arestas de controle, representando as
33
restries de fluxo de controle e Ad so arestas de dependncia de
dados que representam
as restries de fluxo de dados.
Durante o processo de avaliao a mquina abstrata utiliza uma
4-tupla G, , I, O,onde G o grafo; o ambiente de variveis, que
possui como funo mapear nomes
de variveis para valores durante a execuo de uma composio de
servios; I e O so
buffers de entrada e sada. Cada buffer uma lista de triplas (o,
v, l) onde o o nome de
uma operao, v o nome de um vrtice e l uma lista de valores. No
buffer de sada
O, l uma lista de valores que devem ser utilizados como
parmetros para a chamada da
operao o, e a chamada da operao deve retornar seu valor para
vrtice de retorno de
operao v. J No buffer de entrada I, l uma lista de valores
retornados pela execuo
de uma operao o, que deve ser repassada para o vrtice v do
grafo.
Os buffers de entrada e sada so manipulados por um componente
externo mquina
de reduo, que ser chamado de gerenciador de servios. Este
componente tem como
responsabilidade realizar as chamadas das operaes por meio da
utilizao de informaes
do buffer de sada O da mquina de reduo e preencher o buffer de
entrada I da mquina
com o resultado da execuo das operaes, como ilustrado na Figura
8.
Figura 8: Comunicao da mquina de reduo com o gerenciador de
servios.
No processo de avaliao a mquina de reduo utiliza como configurao
inicial uma
4-tupla T [[P ]], , , , onde T [[P ]] o grafo gerado a partir da
transformao do programaP , utilizando as regras apresentadas na seo
3.1.3; indicando que o ambiente de variveiscomea sem variveis; e
com os buffers de entrada e sada vazios ().
As regras de traduo sero descritas na seo 3.1.3 e as regras de
reduo sero
descritas na seo 3.1.4.
34
3.1.3 Regras de Traduo
As regras de traduo utilizadas pela mquina PEWS-AM sero
definidas nesta sub-
seo. A funo T definida para transformar programas P em
grafos.
Como foi dito no final da seo 3.1.2 um grafo G representado como
uma tripla
V,Ac, Ad. A funo T atribui um nome nico a cada vrtice do
conjunto V . O conjuntode arestas de controle Ac representa as
restries de fluxo de controle impostas pelos cons-
trutores da linguagem. Arestas de dependncia Ad representam
dependncias de dados,
onde um n do grafo precisa utilizar o valor atribudo a uma
varivel por outro n do
grafo.
Informaes como o nmero de arestas que chegam a um n do grafo so
utilizadas
pelas regras de traduo. Estas informaes so disponibilizadas
pelas 3 funes definidas
a seguir:
indegreec(v) que informa o nmero de arestas de controle que
chegam ao n v;
indegreed(v) que informa o nmero de arestas de dependncia de
dados que chegamao n v;
indegree(v) que retorna o nmero total de arestas que chega ao n
v, isto ,indegree(v) = indegreec(v) + indegreed(v).
3.1.3.1 Chamada de Operao
Dada uma chamada de operao S(E,X), na qual S representa o nome
da operao
de um servio web, E representa uma lista de expresses de entrada
e X uma lista de
identificadores de sada, a regra de traduo T [[S(E,X]]) definida
a seguir:
T [[S(E,X)]] = {w : S!E,w : S?X}, {w 7 w},
A aplicao da regra da chamada de operao cria um grafo com 2
nodos w, w e uma
aresta de controle ligando os nodos. O n w representa a chamada
do servio S utilizando
a lista E de expresses como parmetros de entrada. Enquanto o n w
representa o
retorno da operao. Quando a operao S terminar sua execuo os
valores de retorno
sero associados lista de variveis de X no n w. A aresta de
controle ligando os ns
w e w define que a chamada do servio (w) deve ocorrer antes do
retorno (w), como
ilustrado na Figura 9.
35
w : S!E
w : S?X
S(E,X)
Figura 9: Grafo da chamada de operao.
3.1.3.2 Composio em Paralelo
Dados dois programas P1 e P2, em que cada um destes programas
representa um
programa PEWS vlido, a regra de traduo T [[P1||P2]] definida
por:
T [[P1P2]] = V V , Ac Ac , Ad Ad d dwhere
V , Ac, Ad = T [[P1]], V , Ac , Ad = T [[P2]],d = crossDD(V
, V ), d = crossDD(V, V )
onde a traduo de uma composio em paralelo definida como a unio
dos vrtices,
arestas de controle e dependncia de dados dos grafos que
representam os programas P1e P2.
O conjunto de arestas de dependncia de dados formado pela unio
das arestas de
dependncia de dados dos dois programas junto com os conjuntos d
e d provenientes
da funo crossDD. Esta funo retorna arestas de dependncia de
dados entre dois
conjuntos de vrtices, quando um n de um conjunto de vrtices
precisar utilizar algum
valor que vai ser resolvido por outro n que ainda precisa ser
avaliado. A definio desta
funo dada a seguir:
crossDD(V1, V2) = { v1 7 v2 | v1 : S1?X V1 (v2 : S2!E V2 x
Vars(E). x X v2 : E V2 x Vars(E). x X) }
36
Na Figura 10 mostrado um exemplo do grafo resultante da traduo
de dois progra-
mas P1 e P2. As arestas de dependncia de dados so representadas
como setas pontilhadas.
S!E
S?X
P1
T !F
T?X
P2
Figura 10: Grafo de uma composio em paralelo.
3.1.3.3 Composio Seqencial
Dados dois programas PEWS vlidos P1 e P2. A aplicao da regra de
traduo
T [[P1;P2]] definida por:
T [[P1;P2]] = V V , Ac Ac c, Ad Ad dwhere
V , Ac, Ad = T [[P1]], V , Ac , Ad = T [[P2]],c = {v1 7 v2 | v1
V , v2 V , indegreec(v2) = 0 },d = crossDD(V
, V )
onde a traduo de uma composio sequencial representada pela unio
dos vrtices dos
grafos dos dois programas. O conjunto de arestas de controle
resultantes (Ac) formado
pela unio das arestas de controle Ac e Ac mais c, onde c o
conjunto de arestas que
partem de todos os vrtices de P1 com destino a todos os vrtices
de P2 que possuem
indegreec = 0.
O conjunto de arestas de dependncia de dados Ad definido pela
unio das arestas
Ad, Ad e d, onde d representa o conjunto de arestas de
dependncia das variveis que
foi resolvido no programa P1 e utilizado em P2. Um exemplo disto
dado na Figura 11.
3.1.3.4 Escolha No Determinstica
O trecho de cdigo PEWS [E1]P1+[E2]P2, no qual P1 e P2 so
programas PEWS
e as expresses E1 e E2 so guardas dos respectivos programas,
representa uma escolha
37
S!E
S?X
P1
T !F
T?X
P2
Figura 11: Grafo de uma composio seqencial.
no determinstica.
O grafo resultante da aplicao da regra de traduo de uma escolha
no determi-
nstica possui um vrtice adicional + que contm arestas de
controle para as expresses
a serem avaliadas. Cada expresso contida em um nodo que possui
arestas de controle
apontando para seus respectivos programas.
A regra para traduo da escolha no determinstica T
[[[E1]P1+[E2]P2]] define que oconjunto de vrtices do grafo gerado
composto pela unio dos vrtices V , V e V , ondeV representa os
vrtices + e um vrtice para cada guarda.
T [[[E1]P1+[E2]P2]] = V V V , Ac Ac c, Ad Adwhere
V , Ac, Ad = T [[P1]], V , Ac , Ad = T [[P2]],V = {v : +, v1 :
E1, v2 : E2},c = {v 7 v1, v 7 v2} c c ,c = {v1 7 w | w V ,
indegreec(w) = 0},c = {v2 7 w | w V , indegreec(w) = 0}
O conjunto de arestas de controle formado pelas arestas de
controle de Ac, Ac e c,
onde c o conjunto de arestas que partem do vrtice + a cada uma
das expresses em
unio com o conjunto de arestas que partem de cada uma das
expresses para os vrtices
com indegreec = 0 de seus respectivos programas.
Como esta regra no cria arestas de dependncia de dados, fora as
criadas por P1 e
P2, o conjunto Ad fica definido como a unio das arestas de
dependncia de dados Ad e
Ad.
A Figura 12 mostra o grafo resultante da execuo da regra de
traduo para escolha
38
no determinstica T [[[E1]((A;B)||(C;D))+[E2]((E;F
)||(G;H))]].
+
E1 E2
A
B
C
D
P1
E
F
G
H
P2
Figura 12: Grafo de uma escolha no determinstica.
3.1.3.5 Condicional
A regra de traduo de expresso condicional definida de forma
similar escolha
no determinstica, com a diferena de que na regra de traduo
condicional h apenas
uma expresso a ser avaliada. A segunda expresso, por no existir
definida como um
nodo false sem nodos filhos.
Esta regra define que o conjunto de vrtices do grafo gerado
formado pelos vrtices
V do programa P em unio com um vrtice +, um vrtice representando
a expresso e
um vrtice representando o valor false.
T [[if E then P ]] = V V , Ac c, Adwhere
V, Ac, Ad = T [[P ]],V = {v : +, v1 : E, v2 : false},c = {v 7
v1, v 7 v2} c,c = {v1 7 w | w V, indegreec(w) = 0}
As arestas de controle so formadas pelas arestas Ac do programa
P em unio com
c, onde c o conjunto com as arestas de controle que ligam o
vrtice + aos vrtices
que representam a expresso a ser avaliada e o valor false em
unio com as arestas que
partem da expresso com destino a todos os ns com indegreec = 0
do programa P .
39
Assim como a regra para escolha no determinstica, esta regra no
cria arestas de
dependncia de dados, portanto estas arestas so representadas
apenas pelas arestas Adprovenientes de P .
O grafo da Figura 13 o resultado da aplicao da regra de traduo
para o condicional
T [[if E then ((A;B)||(C;D))]].
+
E false
A
B
C
D
P
Figura 13: Grafo de um condicional.
3.1.3.6 Unfolding
O trecho de cdigo unfolding P , no qual P um programa PEWS,
representa uma
estrutura de repetio Unfolding.
Um nodo criado e um conjunto de arestas ligando este nodo aos
vrtices raizes do
programa P .
O conjunto de vrtices do grafo gerado pela aplicao da regra de
traduo T [[unfolding P ]] formado pelos vrtices V vindos da traduo
de P em unio com o vrtice . Uma cpia
do programa P anotada no vrtice para ser utilizada
posteriormente no processo de
reduo para criar novas iteraes. Para indicar esta anotao o
vrtice ser escrito
como .P .
T [[unfolding P ]] = V {v : .P}, Ac c, Adwhere
V, Ac, Ad = T [[P ]],c = {v 7 w | w V, indegreec(w) = 0}
40
As arestas de controle so formadas pela unio das arestas Ac e as
arestas que ligam
o n aos ns que possuem indegreec = 0 em P . As arestas de
dependncia de dados so
formadas apenas pelas arestas Ad vindas de P .
A regra de traduo T [[unfolding ((A;B)||(C;D))]] cria o grafo
apresentado na Figura14.
.Pv
A
B
C
D
P
Figura 14: Grafo do unfolding.
3.1.3.7 Unfold
A regra de traduo T [[unfold]] a mais simples, criando um grafo
com apenas umnodo unfold. Este tipo de nodo faz parte de estruturas
de repetio unfolding. Assumindo
que para cada vrtice unfolding sempre existir pelo menos um
vrtice unfold associado.
T [[unfold]] = {v : unfold}, ,
O grafo gerado pela aplicao da regra unfold possui apenas um
vrtice unfold. Arestas
de controle ou de dependncia de dados no so geradas, deixando os
respectivos conjuntos
com valor vazio(). A Figura 15 representa o grafo gerado pela
aplicao da regra detraduo T [[unfold]].
unfold
Figura 15: Grafo do unfold.
41
3.1.4 Regras de Reduo
Nesta subseo as regras de reduo utilizadas pela mquina de reduo
so descritas.
O processo de avaliao ocorre sempre que algum determinado vrtice
se torna candidato
a avaliao. Para que um vrtice se torne candidato a avaliao ele
precisa atender as
restries de cada regra e ser um dos seguintes vrtices: S!E
(chamada de operaes),
S?X (retorno de operaes), + (usado em escolhas no determinsticas
e em condicionais)
e (usado pelo unfolding).
O processo de execuo da mquina PEWS definido pela relao de
avaliao:
G, , I, O G, , I , O
onde a partir de um estado inicial G, , I, O, aps um passo na
avaliao, utilizando asregras desta seo chega-se ao estado G, , I ,
O. Para um conjunto H, escreve-se H[x]com o significado H {x}.
As regras de reduo so apresentadas a seguir:
3.1.4.1 Chamada de Operao
indegree(w) = 0, a = Eval(E),
Ac = Ac {w 7 v | v V },G = V [w : S!E, w : S?X], Ac[w 7 w],
Ad
G, , I, O V [w : S?X], Ac, Ad, , I, O[(S,w, a)]
A regra de reduo para a chamada de operaes pode ser executada
quando existe
no grafo um vrtice w do tipo S!E com indegree = 0, um vrtice w
do tipo S?X e uma
aresta de controle partindo de w com destino a w. Isto , existe
um vrtice w pronto para
ser avaliado que representa uma chamada de operao, como
ilustrado no lado esquerdo
da Figura 16.
O processo de avaliao consiste nos seguintes passos: a) escrever
no buffer de sada
O uma tripla (S,w, a) com o nome do servio S a ser chamado, o
vrtice w ao qual a
mquina deve retornar o resultado e uma lista a de valores
avaliados a partir da lista de
expresses E que sero utilizados como parmetros de entrada do
servio S; b) remover
todas as arestas de controle que partem de w e c) remover o
vrtice w do grafo.
42
O resultado da avaliao desta regra mostrado na Figura 16,
ficando o vrtice w e
uma entrada no buffer de sada.
S!Ew
S?Xw S?Xw
O[(S,w, a)]
Figura 16: Grafo da chamada de uma operao.
Com a entrada no buffer de sada O um componente externo ir fazer
uma chamada
ao servio S usando a lista a como parmetro. Quando o servio
chamado retornar seu
resultado, o componente externo ir apagar a tripla do buffer de
sada O e escrever uma
tripla no buffer de entrada I da mquina.
Uma tripla (S,w, r) escrita no buffer de entrada formada
utilizando o nome do
servio S que foi chamado, o vrtice w ao qual o resultado deve
ser retornado e uma lista
r com os valores retornados pela chamada do servio.
3.1.4.2 Retorno de Operao
indegree(w) = 0, r = (v1, . . . , vk), X = (x1, . . . , xk),
= {(xi, vi) | 1 i k},Ac = Ac {w 7 v | v V }, Ad = Ad {w 7 v | w
V }V [w : S?X], Ac, Ad, , I[(S,w, r)], O V,Ac, Ad, , I, O
A regra para retorno de operao espera que o grafo possua um
vrtice w do tipo S?X,
que possua indegree = 0 e uma entrada no buffer de entrada
I[(S,w, r)] que indique que
existe um resultado de chamada de operao para o vrtice w. Ou
seja, existe um vrtice
de retorno de operao pronto para ser avaliado.
A avaliao associa cada um dos valores retornados r com cada uma
das variveis
X no ambiente . A tripla (S,w, r) removida do buffer de entrada
I. O vrtice w
removido do grafo, bem como todas as arestas de controle e de
dependncia de dados que
partem de w. O resultado da avaliao desta regra pode ser visto
na Figura 17.
43
S?Xw
I[(S,w, r)]
[{(xi, vi)|1 i k}]
Figura 17: Grafo do retorno de uma operao.
3.1.4.3 Escolha No Determinstica
Quando o prximo vrtice a ser avaliado um vrtice +, sabe-se que
uma escolha no
determinstica ser tratada.
Durante a fase de aplicao das regras de traduo as escolhas no
determinsticas
e os condicionais criam grafos semelhantes. Escolhas no
determinsticas utilizam duas
expresses guardas (Figura 18 esquerda), enquanto que
condicionais utilizam apenas uma
expresso guarda (Figura 18 direita), deixando a segunda expresso
com valor false e sem
vrtices filhos.
+
E1 E2
A
B
C
D
E
F
G
H
+
E1 false
A
B
C
D
Figura 18: Grafo de uma escolha no determinstica (esquerda) e de
um condicional (di-reita).
Para o caso de escolha no determinstica so utilizadas duas
regras de avaliao: (i)
uma para quando uma das expresses avaliadas possui valor true; e
(ii) as duas expresses
avaliadas possuem valor false. Quando existem duas expresses com
valor verdadeiro a
primeira regra utilizada e seleciona-se uma das expresses. Sendo
que esta escolha no
determinstica, isto , a especificao no define qual das opes ser
adotada. A escolha
fica, ento, a cargo da implementao.
44
A regra a seguir usada quando uma das expresses da escolha no
determinstica
avaliada possui valor true. Neste caso no necessrio verificar as
outras expresses da
escolha no determinstica, removendo assim: o subgrafo filho da
outra expresso; o vrtice
+; e os vrtices das expresses, como ilustrado na Figura 19.
indegreec(v) = 0, indegreed(w) = 0, Eval(E) = true,
V = {u V | w 7c u w 67c u}, G = V,Ac, Ad \ (V {v, w})V [v : +, w
: E,w : E ], Ac[v 7 w, v 7 w], Ad, , I, O G, , I, O
Para a remoo do subgrafo filho da outra expresso seleciona-se
para remoo o
conjunto de vrtices atingveis a partir do vrtice w e que no so
alcanveis a partir
de w. Na Figura 19 os vrtices V selecionados para remoo da
expresso no escolhida
seriam E,F,G,H e o prprio vrtice w : E2.
+v
truew E w
A
B
C
D
E
F
G
H
A
B
C
D
Figura 19: Grafo de uma escolha no determinstica com uma
expresso verdadeira.
A regra da escolha no determinstica para o caso das duas
expresses terem sido
avaliadas para false apresentada a seguir. Neste caso remove-se
do grafo: o vrtice +;
os vrtices das expresses falsas e os subgrafos filhos de cada
uma das expresses.
indegreec(v) = 0, indegreed(w) = 0, indegreed(w) = 0,
Eval(E) = false, Eval(E) = false,
V = {u V | w 7c u w 67c u}, V = {u V | w 7c u w 67c u},G = V,Ac,
Ad \ (V V {v})
V [v : +, w : E,w : E ], Ac[v 7 w, v 7 w], Ad, , I, O G, , I,
O
45
Para a remoo dos subgrafos filhos de cada expresso remove-se do
grafo o conjunto
de vrtices V e V , onde V possui os vrtices atingveis a partir
de w que no so
alcanveis pelo vrtice w correspondendo ao subgrafo com raiz em w
e o conjunto de
vrtices V que possui os vrtices atingveis a partir de w mas que
no so alcanveis
pelo vrtice w, correspondendo ao subgrafo com raiz em w.
A Figura 20 ilustra a aplicao desta regra em um grafo com duas
expresses falsas.
+v
falsew falsew
A
B
C
D
E
F
G
H
Figura 20: Grafo de uma escolha no determinstica com todas as
expresses falsas.
3.1.4.4 Unfolding
Esta regra deve ser aplicada quando o prximo vrtice a ser
avaliado um vrtice
.P , indicando que trata-se de uma estrutura de repetio
unfolding. Quando esta regra
aplicada, todas as ocorrncias do vrtice unfold so expandidas
para uma cpia do
subgrafo com raiz em .P .
Nesta regra W o conjunto de vrtices w representando todos os
vrtices unfold
atingveis a partir do vrtice v (.P ) utilizando as arestas de
controle que no so atingveis
por outros vrtices .P dentro de T [[P ]]. Gw uma cpia do grafo
v, com novos vrticese novas arestas de controle e dependncia, como
demonstrado a seguir.
Dado T [[P ]] = V P , APc , APd , Gw definido como:
Gw = V P {w : .P}, APc {w 7 r|r roots(V P )}, APd
onde roots(G) representa a funo que retorna o conjunto de
vrtices razes de um
grafo G = V,Ac, Ad e definida como roots(G) = {v V |indegreec(v)
= 0}.
46
O novo grafo G formado pela substituio de todos os vrtices
unfold do conjunto
W por cpias Gw do grafo com raiz em .P . Esta substituio
corresponde a criao de
uma nova iterao do loop unfolding, como ilustra a Figura 21.
indegreec(v) = 0
W = {w | w : unfold V v 7c w 6 u : .P . v 7c u u 7c w}
G = V W,Ac, Ad wW G
w
V [v : .P ], Ac, Ad, , I, O G, , I, O
.Pv
A
B
C
unfoldw
A
B
C
.P 2 Gw
A2
B2
C2
unfold2
Figura 21: Grafo de unfolding.
3.2 Pony
Pony [53] um sistema para gerenciamento de fluxos de trabalho
para Hadoop baseado
em BPEL. Este sistema se destaca por utilizar um agendador de
fluxos de trabalho. O
agendador utilizado por Pony permite priorizar a execuo de
operaes pertencentes a
fluxos de trabalho dentro do Hadoop.
Os fluxos de trabalho utilizados por Pony so modelados como
grafos direcionados (ou
seja, grafos de fluxos de trabalho) e so posteriormente mapeados
para processos BPEL.
Como BPEL realiza orquestraes utilizando apenas servios web, um
servio wrapper
(utilizado para encapsular tarefas Hadoop) foi proposto para
converter tarefas do Hadoop
47
para servios web. Para cada tipo de tarefa do Hadoop h um servio
wrapper correspon-
dente que fica responsvel por realizar envio de dados, execuo e
obteno de resposta
da tarefa do Hadoop.
O agendador de tarefas do Hadoop tem como funo alocar recursos
(containers1)
para tarefas em execuo. Por padro, Hadoop utiliza o agendador de
tarefas FIFO (First
In First Out) , que aloca recursos para tarefas na ordem em que
elas chegam ao cluster.
Dois outros agendadores de tarefa que podem ser utilizados so
Capacity e Fair [75].
No entanto, estes agendadores no tem condies de determinar se
uma tarefa pertence
ou no a um fluxo de trabalho. Desta forma, quando fluxos de
trabalho so enviados para
execuo, suas tarefas concorrem por recursos junto com tarefas
que no fazem parte do
fluxo de trabalho, fazendo com que tarefas pertencentes a um
fluxo de trabalho esperem
por recursos para que possam ser executadas. A espera por
recursos acaba retardando a
execuo dos fluxos de trabalho.
Para resolver este problema, Pony props a criao de um agendador
de tarefas Ha-
doop que trabalha de forma colaborativa com BPEL para permitir a
execuo de fluxos
de trabalho de forma eficiente. Desta forma, o Hadoop pode dar
prioridade execuo de
tarefas pertencentes fluxos de trabalho, acelerando assim sua
execuo.
Como pode ser visto na Figura 22, Pony composto por um Hadoop
Workflow De-
signer que fica responsvel por criar fluxos de trabalho de forma
visual e converter estes
grafos para BPEL para que o fluxo de trabalho possa ser
executado pelo Hadoop Work-
flow Execution Engine. O Execution Engine cuidar de executar o
fluxo de trabalho
BPEL e quando uma tarefa Hadoop for executada, o servio wrapper
correspondente ir
realizar comunicao com o cluster Hadoop, executar sua tarefa e
retornar resultados
para o Execution Engine. Os servios wrapper se comunicam com o
Pony Job Schedu-
ler (o agendador de tarefas), e este ltimo trata de dar
prioridades s tarefas Hadoop que
pertencem a fluxos de trabalho, permitindo que o fluxo seja
executado mais rapidamente.
- permitir a chamada de operaes de multiplos dominios a partir
do cluster hadoop -
3.3 Concluses do Captulo
Neste captulo foram mostrados trabalhos relacionados proposta
desta dissertao.
Na seo 3.1 foi apresentada a mquina de reduo de grafos PEWS-AM
que permite a cri-1Container a unidade computacional mnima dentro
do Hadoop, que equivale aos recursos, tais como
CPU e memria, necessrios para executar uma tarefa em um nodo do
cluster.
48
Figura 22: Arquitetura de Pony [53].
ao de composies de servios web utilizando a linguagem PEWS.
Foram apresentados
os construtores da linguagem; a arquitetura utilizada pela
mquina; o conjunto de regras
de traduo que transforma cdigo PEWS em grafos e o conjunto de
regras de reduo
que atravs de sucessivas aplicaes transformam os grafos e
executam as chamadas de
servios web da composio.
A experincia obtida na definio e implementao da mquina PEWS-AM
foi utili-
zada neste trabalho, permitindo propor uma mquina de reduo de
grafos extensvel e
com uma estrutura de grafos mais simplificada.
A seo 3.2 tratou de comentar sobre a ferramenta Pony, que
realiza fluxos de traba-
lho Hadoop, utilizando BPEL para executar os fluxos de trabalho
em conjunto com um
agendador de tarefas. Sendo este o trabalho mais prximo
relacionado proposta.
No prximo captulo sero apresentados os principais conceitos
relacionados mquina
MiniBPEL-AM.
49
4 A Mquina de Reduo de GrafosMiniBPEL-AM
Este captulo apresenta de forma geral a mquina MiniBPEL-AM. Esta
mquina
permite a execuo de fluxos de trabalho com operaes mistas, isto
, operaes como
chamadas de servios web, tarefas do hadoop, funes definidas pelo
usurio ou qualquer
outra operao que o usurio queira chamar, utilizando para isto
construtores similares
aos utilizados em linguagens que permitem composies de servios
web baseadas em
workflows (fluxos de trabalho), tais como BPEL e PEWS.
A mquina PEWS-AM foi utilizada como base para a criao da mquina
MiniBPEL-
AM. A presente proposta representa uma evoluo da mquina PEWS-AM.
A nossa
proposta se diferencia de PEWS-AM em dois aspectos principais:
(1) O grafo gerado pela
funo de traduo foi redefinido e simplificado e (2) foram
adicionadas caractersticas
de extensibilidade que permitem o uso da mquina em conjunto com
outras tecnologias.
Em particular, nosso trabalho demonstra essa extensibilidade
mediante a adio de uma
interface para o processamento de grandes volumes de dados
usando Hadoop.
A mquina MiniBPEL-AM permite a execuo de fluxos de trabalho,
assim como o
sistema de gerenciamento de fluxos de trabalho Pony apresentado
na seo 3.2 do captulo
de trabalhos relacionados 3. O que diferencia as duas
ferramentas o foco: Pony tem como
foco executar mltiplos fluxos de trabalho de forma eficiente,
enquanto MiniBPEL-AM
procura permitir que o usurio possa criar novas operaes para
executar em um mesmo
fluxo de trabalho.
A sintaxe da linguagem MiniBPEL detalhada na seo 4.1; a
arquitetura da mquina
que ser vista na seo 4.2; o conjunto de regras de traduo e
reduo, que so utilizados
pela mquina sero vistos nas sees 4.3 e 4.4 respectivamente. Ser
apresentado na seo
4.5 um exemplo de composio utilizando a linguagem MiniBPEL e por
fim as concluses
so apresentadas na seo 4.6.
50
4.1 Construtores da Linguagem
Os construtores da linguagem MiniBPEL so quase todos os mesmos
utilizados pela
mquina PEWS-AM, com exceo do construtor de repetio, onde foi
removido o unfol-
ding/unfold e foi inserido while.
As regras da gramtica a seguir definem a linguagem MiniBPEL:
E ::= id | n | t | s | E1 + E2 | E1 E2 | E1 E2 | E1/E2 | E1 | E1
and E2 | E1 or E2| not E1 | E1 == E2 | E1 < E2 | E1 E2 | E1 >
E2 | E1 E2 | ( E1)
P ::= S(E;X) | P1||P2 | P1;P2 | [E1]P1 + [E2]P2 | if E then P |
while E do P
Assim como na mquina PEWS-AM o smbolo no terminal E descreve
expresses
aritmticas e booleanas, permitindo o uso de identificadores,
literais, strings, operadores
lgicos, aritmticos e relacionais mais comuns. Da mesma forma o
smbolo no terminal P
define as chamadas de servios web, chamadas de tarefas de big
data ou outras operaes
e regras de composio utilizadas na linguagem. A maioria das
regras P se comporta de
forma similar ao que foi definido para a mquina PEWS-AM, com
exceo das seguintes
regras:
S(E;X): corresponde a chamada de uma operao, onde S o
identificador da ope-rao, E uma lista de expresses E que serviro
como parmetros de entrada para
a operao e X uma lista de identificadores id que guardaro
valores resultantes
da execuo da operao. A operao pode ser um servio web, uma tarefa
de big
data ou uma operao definida pelo usurio. A diferena em relao a
PEWS-AM
que as chamadas podem, agora, alm de invocar servios web,
invocar operaes
de big data ou operaes definidas pelo usurio. Esta regra separa
as listas E e X
utilizando ponto e virgula (;), o que difere da regra PEWS que
utiliza uma virgula
para separar estas listas. Esta mudana torna mais claro onde a
lista de parametros
termina e onde a lista de identificadores inicia;
while E do P : regra para repetio. Quando esta regra avaliada o
trecho deprograma reescrito como if E then (P ; while E do P ),
correspondendo a um
novo loop de repetio do while.
Na mquina MiniBPEL-AM so utilizadas apenas restries de fluxo de
controle.
Estas restries so impostas pelos construtores da linguagem. Por
exemplo, caso exista
51
uma restrio de controle de um programa P1 at um programa P2 isto
indica que o
programa P1 deve ser executado antes do programa P2.
As operaes de big data que sero implementadas neste trabalho
so:
mapReduce(e;x), que espera como parmetro de entrada e, um
arquivo do tipo .jar,que possua as funes Map e Reduce
implementadas;
hdfs(e;x), que recebe como parmetro de entrada um conjunto de
caracteres cor-respondendo a um comando hdfs;
pig(e;x), que espera como parmetro de entrada um script pig;
hive(e;x), que aceita como parmetro de entrada um script
hive.
Todas estas operaes de big data retornam uma varivel x que
indica se a operao
foi bem sucedida ou no.
4.2 Mquina de Reduo de Grafos
Um programa ao ser executado pela mquina de reduo de grafos
MiniBPEL-AM
inicialmente traduzido para um grafo. Esta tarefa feita
utilizando um Parser que
aplica um conjunto de regras de traduo T [[P ]]. De posse do
grafo, a mquina de reduoaplica sucessivas regras de reduo, at que
no seja mais possvel aplicar outras regras.
A arquitetura da mquina pode ser observada na Figura 23.
Quando h a necessidade de se realizar uma chamada de operao, uma
tupla (o, v, l)
escrita no buffer de sada O da mquina, fazendo com que o
gerenciador de operaes
realize a operao o e retorne o resultado da chamada no buffer de
entrada I.
Durante o perodo em que o gerenciador de operaes est
trabalhando, a mquina de
reduo pode executar novas redues em vrtices candidatos ou apenas
esperar o retorno
do gerenciador de operaes, caso no existam regras para serem
aplicadas no momento.
A mquina de reduo de grafos proposta uma extenso da arquitetura
da mquina
de reduo apresentada na seo 3.1.2. As modificaes que sero feitas
iro alterar prin-
cipalmente o componente Gerenciador de Servios de PEWS-AM (
Figura 8), o qual ser
substitudo por um componente extensvel chamado de gerenciador de
operaes (Figura
23). O gerenciador de operaes tem a funo de ler o buffer de sada
da mquina de
52
Cdigo
Parser
MiniBPEL-AM
G
I
O
Gerenciadorde
Operaes
Gerencidorde FunesDefinidas
peloUsurio
FunesDefinidas
peloUsurio
Gerenciadordo HadoopHadoop
Gerenciadorde Servios
Web
ServiosWeb
G(o, v, l)
(o, v, l)
Figura 23: Arquitetura da mquina de reduo MiniBPEL-AM.
reduo de grafos, realizar uma operao e escrever no buffer de
entrada da mquina o
resultado da operao chamada.
Na mquina proposta o gerenciador de operaes possuir
sub-gerenciadores para
poder tratar cada tipo de operao que seja chamada pela mquina de
reduo de grafos.
Por exemplo, um sub-gerenciador permitir tratar chamadas a
servios web. Outro sub-
gerenciador ir gerenciar a chamada de operaes de big data mais
especficas, como o
caso de operaes de tarefas do Hadoop, ou outro sistema que
possua operaes de big
data, como ilustra a Figura 24.
Desta forma o
![GRAFOS CLIQUE DE ARESTAS Márcia Rosana CerioliCERIOLI, MÁRCIA ROSANA Grafos Clique de Arestas [Rio de Janeiro] 1999 VI, 68 p.29,7cm (COPPE/UFRJ, D.Sc., Engenharia de Sistemas e Computação,](https://img.document.onl/doc/110x75/5f4bd7d9416a2e69e11ec287/grafos-clique-de-arestas-mrcia-rosana-cerioli-cerioli-mrcia-rosana-grafos-clique.jpg)
