Declarative Overlay Professor: Eduardo Almeida UFPR / Departamento de Informática Alunos: Ailton Sergio Bonifacio - Doutorando Caio Ruan Nichele - Mestrando

Declarative OverlayDeclarative Overlay

Professor:Eduardo Almeida

UFPR / Departamento de Informática

Alunos:Ailton Sergio Bonifacio - Doutorando

Caio Ruan Nichele - MestrandoDiogo Andrade - Graduando

E-mail: {ailtons, caio, da06}@c3sl.ufpr.br

Maio/2010


RoteiroRoteiro

• Linguagem Declarativa– Exemplo: PROLOG

• Rede Overlay

• Overlay Declarativa– P2

• Questões em Aberto

• Trabalhos Futuros

• Conclusão


Linguagem DeclarativaLinguagem Declarativa

• Um programa é “declarativo” se ele descreve como é algo, ao invés de como criá-lo.

• Uma abordagem diferente da tradicional linguagem de programação imperativa, tais como Fortran, C e Java, que exigem do programador um específico algoritmo para ser executado.

• A linguagem declarativa descreve ao computador um conjunto de condições específicas, deixando ao computador decidir como processar as informações de melhor modo.


Linguagem DeclarativaLinguagem Declarativa

• Um programa é “Declarativo” se está escrito em uma linguagem de programação funcional ou linguagem de programação lógica.

• A linguagem declarativa permite ao programador se concentrar na lógica do algoritmo, isto é, sua preocupação está em definir critérios, e não decidir ações.


Linguagem Declarativa – CaracterísticasLinguagem Declarativa – Características

• Modelo de computação baseado num sistema onde as relações são específicas em termos de características dos dados de entrada;

• Composta por conjuntos de definições ou equações que descrevem as relações que especificam o que deve ser computado, e não como ser computado;

• Não existe ordem específica para execução;

• Valores podem ser utilizados como expressões e definições.


PROLOGPROLOG

• Linguagem baseada em um conjunto de conceitos:– casamento de padrões;– estruturação em forma de árvore;– backtracking automático.

• Prolog é uma linguagem de programação que utiliza o modelo declarativo, com lógica matemática;

• É uma linguagem especialmente associada com a inteligência artificial e semântica computacional;

• Apresenta uma semântica declarativa inerente à lógica.


PROLOGPROLOG

• Conciliar o uso da lógica como uma linguagem declarativa de representação do conhecimento com a representação procedimental do conhecimento;

• Suporta código recursivo e iterativo para a descrição de processos e problemas;

• Permite associar o processo de especificação ao processo de codificação de programas;

• Utiliza uma base de dados de fatos e de relações lógicas (regras) que exprimem o domínio relacional do problema a resolver.


PROLOG PROLOG

• PROLOG é mais direcionada ao conhecimento, menos direcionada aos algoritmos;

• PROLOG não possui estruturas de controle como do-while, repeat-until, if-then-else, for, case ou switch como os encontrados em outras linguagens;

• Em PROLOG utiliza-se métodos lógicos para declarar como o programa atinge seu objetivo;

• A força do PROLOG reside em sua capacidade de Busca e Casamento de Padrões.


PROLOG PROLOG

• Permite a obtenção de respostas alternativas, uma vez que várias soluções diante da base de dados podem ser encontradas;


PROLOG: conceitosPROLOG: conceitos

• Átomos – As constantes de texto são introduzidas por meio de

átomos. Um átomo é uma seqüência constituída de letras e números, mas iniciando com uma letra minúscula.

– Ex. joaquim, 'quem é você?' , guarda-roupa

• Números– Um número é uma seqüência de dígitos, permitindo

também os sinais de . (para números reais), - (número negativo) e e (notação científica).

– Ex. 814, 54.876

• Variáveis– Variáveis são declaradas da mesma forma que átomos,

porém iniciando com uma letra maiúscula.– Ex. Minha-var, Teste



• Termo Composto– É a única forma de se expressar estruturas de dados

complexas em Prolog;– Consiste de uma cabeça e parâmetros listados entre

parênteses e separados por vírgulas.– Ex. suc(suc(suc(0)))

• Predicado– É a construção usada para declarar algo a respeito de

objetos. Em Prolog, a declaração é representada por um átomo e é seguida pelos objetos, que devem ser colocados entre parênteses e estar separados uns dos outros por vírgulas.

– Ex. robô(joão) , homem(silvestre)



• Frases– Consultas à base de dados de fatos

• casado(pedro,maria).• casado(carlos,ana).• ?- casado(carlos,maria).• ?- casado(carlos,ana).

• Fatos– gosta (josé, maria)



• Regras– São utilizadas para construir relações entre fatos,

explicitando as dependências entre eles. Ao contrário dos fatos, que são incondicionais, as regras especificam coisas que podem ser verdadeiras se algumas condições forem satisfeitas.

– Ex. gosta (joão, X) :- gosta (X, cachaça).



• Dizemos que dois fatos (ou um fato e uma questão) se unificam (são iguais) se:– seus predicados são os mesmos,– eles possuem o mesmo número de argumentos e,– os argumentos são iguais.– o PROLOG encontra um fato que se iguala a questão, ele

retorna "YES", indicando que a questão tem resposta verdadeira; caso contrário, ele retorna "NO".


PROLOG - exemploPROLOG - exemplo

•Programa:factorial (0,1). factorial (N,F) :-

N>0,N1 is N-1,Factorial (N1,F1),F is N*F1.

•Consulta:?- factorial(3,W).


Estrutura de Árvores

PROLOG - exemploPROLOG - exemplo


Exemplo: Concatenando listas Exemplo: Concatenando listas aa e e bb

list procedure cat(list a, list b){ list t = list u = copylist(a); while (t.tail != nil) t = t.tail; t.tail = b; return u;}

Em uma Linguagem Imperativa

Em uma Linguagem Declarativa

Em uma Linguagem Funcionalcat(a,b) if b = nil then aelse cons(head(a), cat(tail(a),b))

cat([], Z, Z).cat([H|T], L, [H|Z]) :- cat(T, L, Z).


Overlays: Visão GeralOverlays: Visão Geral

• “Overlay”: componente de roteamento e encaminhamento de mensagens de qualquer

sistema distribuído não trivial

Internet

Overlay


Overlays - Exemplos e AplicaçõesOverlays - Exemplos e Aplicações

• Redes Overlay são amplamente utilizadas atualmente:– Roteamento e encaminhamento em sistemas distribuídos de

larga escala;– Fornecer novas funcionalidades sobre infra-estruturas

existentes.

• Alguns exemplos:– Entrega de pacotes: Multicast, RON;– Entrega de conteúdo: CDNs, P2P file sharing, DHTs;– Sistemas empresarias: MS Exchange.

Rede Overlay é uma parte integrante de muitos sistemas distribuídos de larga escala.

Rede Overlay é uma parte integrante de muitos sistemas distribuídos de larga escala.


Overlay: ProblemaOverlay: Problema

• Não é trivial projetar, construir e implantar uma rede overlay:

– Processo Iterativo de Projeto:• Propriedades desejáveis Protocolos e algoritmos distribuídos

Simulação Implementação Implantação Repita…

– Cada iteração toma muito tempo e utiliza uma diversidade de conhecimento.


Esforços para inovação da internetEsforços para inovação da internet

• Evolução: Redes Overlay– Comercial (Akamai, VPN, servidores MS Exchange)– P2P (compartilhamento de arquivos, telefonia)– Pesquisas (PlanetLab)

• Revolução:– Programa 1NSF Future Internet Design (FIND)– Iniciativa 2NSF Global Environment for Network

Investigations (GENI)

1 http://www.nets-find.net/2 http://www.geni.net/

Faltam: ferramentas de software que podem acelerar significativamente a inovação da

Internet

Faltam: ferramentas de software que podem acelerar significativamente a inovação da

Internet


Overlay DeclarativaOverlay Declarativa

• Tornar o desenvolvimento de redes mais acessível para os desenvolvedores de aplicações distribuídas– Ferramenta para prototipagem rápida de novas redes

overlay– Especificar redes overlay em alto nível– Tradução automática para especificação executável– Ocultar tudo que não se quer tocar

• Visa uma performance de bom desempenho– Foca na aceleração do processo iterativo de design– Permite ajuste tardio da implementação

• Fazer para os sistemas de redes o que o SQL fez para os modelos de bancos de dados relacionais


Overlay Declarativa: A razãoOverlay Declarativa: A razão

• O conjunto de tabelas de roteamento em uma rede representa uma estrutura distribuída de dados

• A estrutura de dados é caracterizada por um conjunto de propriedades ideais que definem a rede– Pensando em termos de estrutura e não de protocolo

• Roteamento é o processo de manutenção destas propriedades a despeito de mudança dos fatos fundamentais– Falhas, mudanças de topologia, carga, políticas...


Duas direções:Duas direções:

• Expressão declarativa de protocolos de roteamento da internet– Loo et. al., ACM SIGCOMM 2005

• Implementação Declarativa de Redes Overlay– Loo et. al., ACM SOSP 2005– O foco deste seminário


Overlay Declarativa: P2Overlay Declarativa: P2

• Utiliza uma linguagem lógica declarativa - Overlog– Baseada em Datalog– O foco é sobre modelos de algoritmos e protocolos, e não a

implementação.

• Analisa e executa as especificações utilizando uma arquitetura de fluxo de dados para a construção e manutenção de redes overlay

• Objetivo: Expressar redes overlay de uma forma altamente compacta e reusável


P2: Roteamento como Processamento de ConsultasP2: Roteamento como Processamento de Consultas

• Em termos de banco de dados, a tabela de roteamento é uma visão sobre as mudanças de estado e condições da rede;

• Implementação de uma engine genérica de protocolo de roteamento como um processador de consultas;

• Utilização de um framework de fluxo de dados em tempo de execução para a manutenção das overlays;

• Elementos de Fluxo de Dados fornecem um modelo de implementação para consultas.


Nodo Tradicional de uma rede OverlayNodo Tradicional de uma rede Overlay

node

Network State

route ...

Traditional Overlay Node

node

Network State

route ...

Overlay ProgramPackets OutPackets In

Fonte: Implementing Declarative Overlays - Boon Thau Loo - SOSP2005


node

Local Tables

route ...

Nodo de uma rede Overlay P2Nodo de uma rede Overlay P2

...

Netw

ork In Dataflow

...

...

Netw

ork Out D

ataflow

Overlay description: dataflow scripting language

Runtime dataflows maintain network state

Overlay description: declarative query language

Planner

P2 Query Processor

Packets OutPackets InOverlay Program

Fonte: Implementing Declarative Overlays -

Boon Thau Loo - SOSP2005


Vantagens da Abordagem P2Vantagens da Abordagem P2

• Linguagem de consulta declarativa– Expressão concisa e de alto nível– Estaticamente verificável (terminações, corretude)

• Facilidade de modificação

• Framework unificador para implementação

• Otimizações automáticas– Nível de consulta e fluxo de dados (dataflows)


Modelo de DadosModelo de Dados

• Dados Relacionais: tuplas e tabelas relacionais

• Dois tipos de tabelas:– Armazenadas:

• E.g. neighbor(Src,Dst), forward(Src,Dst,NxtHop)

– Fluxos (streams) transientes:

• Mensagens da rede: message (Rcvr, Dst)

• Eventos baseados em tempo: periodic (NodeID,10)

...

Netw

ork In Dataflow

...

...

Netw

ork Out D

ataflow

node

Local Tables

route ...


FrameworkFramework do do DataflowDataflow

• Gráficos do Fluxo de Dados– Em C++

• Similar ao Click1:– Elementos de fluxo (mux,

demux, queues)– Elementos da rede (cc, retry,

rate limitation)

• Além disso:– Operadores relacionais

(junções, seleções, projeções e agregação)

...

Netw

ork In Dataflow

...

...

Netw

ork Out D

ataflow

node

Local Tables

route ...

1 Click Modular Router Project - http://read.cs.ucla.edu/click/faq


P2 Declarative Networking SystemP2 Declarative Networking System

P2 Declarative Networking SystemNetwork Specifications as Queries

Query Planner Dataflow Engine

Network Protocols

Fonte: http://p2.cs.berkeley.edu

lookup

lookup

Dem

ux

link

Local Tables

path ...

UD

P

Tx

Round

Robin

Queue

CC

T

x

Queue

UD

P

Rx

CC

R

x

Dataflow


Exemplo: Roteamento do AnelExemplo: Roteamento do Anel

• Cada nó tem um endereço (i.e. endereço IP) e um identificador (randômico)

• Cada objeto tem um identificador

• Nodos e objetos são ordenados dentro do anel por seus identificadores

• Objetos são “servidos” por seu nodo sucessor

• Cada nodo conhece seu sucessor no anel

• Para encontrar o objeto K, caminha-se ao redor do anel até localizar o nodo sucessor imediato K’s

3

28

15

1840

60

58 13

37

0

56

42

222433


• Como encontrar o nodo responsável pela chave k?

• n.lookup(k)if k in (n, n.successor)

return n.successor

elsereturn n.successor. lookup(k)

3

28

15

1840

60

58 13

37

Exemplo: Roteamento do AnelExemplo: Roteamento do Anel


Estado do AnelEstado do Anel

3

28

15

1840

60

58 13

37

n.lookup(k)

if k in (n, n.successor)

return n.successor

else

return n.successor. lookup(k)

Tuplas do estado do Nodo

node(NAddr, N)

successor(NAddr, Succ, SAddr)

Tuplas dos eventos transientes

lookup ( Addr, Req, K )

response( Addr, K, Owner )


send response( Req, K, SAddr ) to Reqwhere lookup( NAddr, Req, K ) @

NAddrand node ( NAddr, N ),and succ ( NAddr, Succ, SAddr ),and K in ( N, Succ ],

n.lookup(k)


return n.successor

else


Node state tuples

node(NAddr, N)


Transient event tuples



Pseudocódigo como uma Pseudocódigo como uma QueryQuery


Pseudocódigo como uma Pseudocódigo como uma QueryQuery

send response( Req, K, SAddr ) to Reqwhere lookup( NAddr, Req, K ) @

NAddrand node ( NAddr, N ),and succ ( NAddr, Succ, SAddr ),and K in ( N, Succ ],

send lookup( Req, K, SAddr ) to SAddrwhere lookup( NAddr, Req, K ) @

Naddrand node ( NAddr, N ),and succ ( NAddr, Succ, SAddr ),and K not in ( N, Succ ],

n.lookup(k)


return n.successor

else


Node state tuples

node(NAddr, N)


Transient event tuples




Implementação:Implementação:Do modelo de consultas (query) para o DataflowDo modelo de consultas (query) para o Dataflow

• Problema tradicional em bancos de dados

• Transformar a lógica em álgebra relacional– Junções, projeções, seleções, agregações, etc

• Implementar os elementos como gráfico de dataflow– C.f. Click, PIER, etc. – Fluxo de tuplas através de graphb

• Executar este gráfico para manter a rede overlay


send response( Req, K, SAddr ) to Reqwhere lookup( NAddr, Req, K ) @ NAddr & node ( NAddr, N )& succ ( NAddr, Succ, SAddr ) & K in ( N, Succ ]

send lookup( Req, K, SAddr ) to SAddrwhere lookup( NAddr, Req, K ) @ Naddr & node ( NAddr, N )& succ ( NAddr, Succ, SAddr ) & K not in ( N, Succ ]

lookup

Da Query para o DataflowDa Query para o Dataflow




node

Joinlookup.NI ==

node.NINI, R, K, N

lookup





node succ

Joinlookup.NI ==

node.NI

Joinlookup.NI ==

succ.NINI, R, K, N, S, SI

lookup





node succ

Joinlookup.NI ==

node.NI

Joinlookup.NI ==

succ.NI

SelectK in (N, S]

NI, R, K, N, S, SIK in (N, S]

lookup





node succ

Joinlookup.NI ==

node.NI

Joinlookup.NI ==

succ.NI

SelectK in (N, S]

Projectresponse@R

(R, K, SI)

lookup





node succ

Joinlookup.NI ==

node.NI

Joinlookup.NI ==

succ.NI

SelectK in (N, S]

Projectresponse@R

(R, K, SI)

Joinlookup.NI ==

node.NI

Joinlookup.NI ==

succ.NINI, R, K, N, S, SI

lookup

lookup






node succ

Joinlookup.NI ==

node.NI

Joinlookup.NI ==

succ.NI

SelectK in (N, S]

Projectresponse@R

(R, K, SI)

Joinlookup.NI ==

node.NI

Joinlookup.NI ==

succ.NI

SelectK not in (N, S]

NI, R, K, N, S, SIK in (S, N]

lookup

lookup




node succ

Joinlookup.NI ==

node.NI

Joinlookup.NI ==

succ.NI

SelectK in (N, S]

Projectresponse@R

(R, K, SI)

Joinlookup.NI ==

node.NI

Joinlookup.NI ==

succ.NI

SelectK not in (N, S]

Projectlookup@SI(SI, R, K)

lookup

lookup



• Um strand por subconsulta• A ordem do Strand é indiferente• Strands podem ser executados em paralelo

node succ

Strand 1lookup

lookup

response

Strand 2 lookup



node succ

Strand 1lookup

lookup Strand 2

...

...

De m

uxQ

ue u

e

UD

P

Tx

UD

P

Rx

CC

R

x

Sched

Qu

e ue

...

...

CC

T

x



P2P2

node succ

Strand 1lookup

lookup Strand 2

...

...

De m

u xQ

ueue

UD

PTx

UD

PR

xC

CR

x

Sch

ed

Queu

e

...

...

CCTx

node succ

Strand 1lookup

lookup Strand 2

...

...

De m

u xQ

ueue

UD

PTx

UD

PR

xC

CR

x

Sch

ed

Queu

e

...

...

CCTx

Descrição da Rede

Overlay

Packets outPackets in

1. Sistema Distribuído especificado em uma linguagem de consulta

2. Compilado dentro de gráfico otimizado de elementos dataflow

3. Gráfico executado diretamente para manter as tabelas de roteamento e o estado da rede overlay


P2 - Estado atualP2 - Estado atual

• Implementação do Chord em P2– DHT popular– Complexa rede overlay– Manutenção dinâmica

• Como se sabe que funciona?– Mesmas propriedades de alto nível

• Logarítmica de diâmetro e estado• Roteamento consistente• Restrições de propriedades como consultas

adicionais– Desempenho comparável as implementações tradicionais


RM1Generate

pingEvent(local)TimedPullPush ping_interval

Slot

RM3 ProjectpingResp

(Y,X)Slot

RM4 Join pingResp.XpingNodes.X

Select pingResp.Y = pingNodes.Y

Project lastPing

(X, Y, now)

RM2 Join pingEvent.XpingNodes.X

ProjectpingReq(X,Y)

Materializations

Insert

pingNodesDemux

(@local?)

TimedPullPush0

Network OutQueueremote

local

Netw

ork In

pingNodes

pingEvent

pingReq

pingResp

lastPing

Insert lastPing

RoundRobin

Mux

Tim

edPullPush 0

Queue

Dem

ux(tuple nam

e)

P2 - Estado atualP2 - Estado atual


Ponto-chave: especificação “notavelmente” concisa da rede Ponto-chave: especificação “notavelmente” concisa da rede overlayoverlay

• Especificação completa do Chord, incluindo– Recuperação de Falhas– Múltiplos sucessores– Estabilização– Manutenção otimizada

• 44 regras OverLog• ...e Roda!

Fonte 10 pt


Comparação: Chord in C++Comparação: Chord in C++


Questões em abertoQuestões em aberto

• Qual o papel da prototipagem rápida?

• Quão bom é performance “boa o suficiente” para prototipagem rápida?

• ... e o tempo de resposta em sistemas críticos?

• Quando os desenvolvedores devem utilizar a prototipagem rápida ou códigos “feitos à mão”?

• Pode-se realmente alcançar a “qualidade de produção” de redes overlay proposta por P2?


Questões em abertoQuestões em aberto

• Onde é o fim da rede e o início da aplicação?– Pode executar consultas para monitorar a rede com

parâmetros– Integração da descoberta de recursos, gerenciamento e

roteamento– Chance para a remodelação dos fundamentos em rede


Trabalhos FuturosTrabalhos Futuros

• Linguagem “adequada”– Expressividade da linguagem

• Dados formais e consulta semântica

• Análise estática – Otimizações, Terminação e Corretude

• Restrições Declarativas e Transações Declarativas não tem sido totalmente exploradas


Trabalhos FuturosTrabalhos Futuros

• Demanda esforços interdisciplinares, incluindo:– Banco de Dados– Redes– Sistemas– Linguagens de programação– Engenharia de software

• Tirar proveito de:– paralelismo implícito para a arquitetura multi-core– Metaprogramação 1 (Para embutir algoritmos de planning

para criar visões virtuais especializadas)

1 T. Condie, D. Chu, J. M. Hellerstein, and P. Maniatis. Evita Raced: Metacompilation for Declarative Networks. In Proceedings of Conference on Very Large Data Bases (VLDB), 2008.


ConclusãoConclusão

• Uma abstração e infra-estrutura para repensar radicalmente redes

• P2: Overlay Declarativa– Ferramenta para prototipagem rápida de novas redes

overlay

• Redes Declarativas– Research agenda: Specify and construct networks

declaratively– Declarative Routing : Extensible Routing with Declarative

Queries (SIGCOMM 2005)


Referências BibliográficasReferências Bibliográficas

1. Boon Thau Loo , Tyson Condie , Joseph M. Hellerstein , Petros Maniatis , Timothy Roscoe , Ion Stoica, Implementing declarative overlays, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom

2. Yun Mao, On the declarativity of declarative networking, ACM SIGOPS Operating Systems Review, v.43 n.4, January 2010

3. B. T. Loo, T. Condie, M. Garofalakis, D. E. Gay, J. M. Hellerstein, P. Maniatis, R. Ramakrishnan, T. Roscoe, and I. Stoica. Declarative Networking: Language, Execution and Optimization. In Proceedings of ACM SIGMOD International Conference on Management of Data, June 2006.

4. X. Chen, Y. Mao, Z. M. Mao, and J. E. V. der Merwe. DÉCOR: DEClarative network management and OpeRation. In Proceedings of the ACM SIGCOMM Workshop on Programmable Routers for Extensible Services of TOmorrow (PRESTO), 2009.

Documents

Declarative Overlay Professor: Eduardo Almeida UFPR / Departamento de Informática Alunos: Ailton Sergio Bonifacio - Doutorando Caio Ruan Nichele - Mestrando