Programação Paralela em Arquiteturas Multi-Core/Aplicações Internet: diferenças entre revisões

Origem: Wikilivros, livros abertos por um mundo aberto.
[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição
Linha 24: Linha 24:
*Grid
*Grid
*P2P
*P2P

== Programação paralela na web ==
*Ambientes de programação
*Bibliotecas de programação
*Linguagens de programação
**PHP
**Java
*Tecnologias
**AJAX
**CGI

== Outras aplicações ==

=== Web Crawlers ===
=== Web Crawlers ===


Linha 95: Linha 81:


Web crawlers vem sendo utilizados com cada vez mais frequência para coletar dados da Web para máquinas de busca, caches e [[mineração de dados]]. Como o tamanho da Web aumenta a cada dia que passa, o uso de crawlers paralelos vem se tornando cada vez mais importante. Conforme observado nessa subseção, construir um crawler paralelo eficiente é muito mais complicado do que uma simples paralelização.
Web crawlers vem sendo utilizados com cada vez mais frequência para coletar dados da Web para máquinas de busca, caches e [[mineração de dados]]. Como o tamanho da Web aumenta a cada dia que passa, o uso de crawlers paralelos vem se tornando cada vez mais importante. Conforme observado nessa subseção, construir um crawler paralelo eficiente é muito mais complicado do que uma simples paralelização.

== Programação paralela na web ==
*Ambientes de programação
*Bibliotecas de programação
*Linguagens de programação
**PHP
**Java
*Tecnologias
**AJAX
**CGI


== Conclusão ==
== Conclusão ==

Revisão das 11h32min de 13 de dezembro de 2007


Este capítulo se encontra em construção    -   Previsão de Conclusão: 14/12   Progresso:


Introdução

Uma breve história e introdução sobre a necessidade de aplicações paralelas na internet e sobre o capítulo.

Aplicações para infra-estrutura

  • Servidores
  • Banco de Dados
  • Gerenciamento de tráfego
  • Protocolos paralelos

Aplicações distribuídas

  • Grid
  • P2P

Web Crawlers

Uma outra aplicação interessante do paralelismo na internet é na construção de Web crawlers, também conhecidos como robôs [1]. Um crawler é um programa que coleta e armazena páginas da Internet, sendo muito utilizados em máquinas de busca.

Definição

Um crawler geralmente começa a funcionar a partir de um conjunto inicial de URLs [2], , armazenadas numa fila. Partindo do conjunto inicial, o crawler pega alguma URL, em alguma ordem pré-definida, coleta a página, extrai novas URLs encontradas a partir da página coletada, e insere essas novas URLs na fila. O processo se repete até que o crawler decide parar. As páginas coletas podem ser utilizadas para aplicações como em máquinas de busca, em Web caches ou em estudos científicos, por exemplo.

Com a expansão diária do tamanho da Web, fica cada vez mais difícil coletar toda ou uma significante parte da Web em um só processo. Então, a paralelização dos Web crawlers se tornam uma medida essencial para maximizar a taxa de captura dos dados.

A construção de Web crawlers paralelos tem muitas vantagens mas trazem também alguns problemas e desafios interessantes. Entre eles, podemos citar:

    • Sobreposição: com muitos processos rodando em paralelo para coletar páginas, é possível que diferentes processos coletem uma mesma página múltiplas vezes.
    • Qualidade: geralmente é mais interessante coletar as páginas mais "importantes" primeiro, a fim de maximizar a "qualidade" dos dados coletados. Em crawlers paralelos, cada processo pode não ter conhecimento da imagem de toda a rede coletada, tomando decisões de acordo com a imagem local da parte que coletou.
    • Banda de Comunicação: periodicamente os processos precisam se comunicar para prevenir a sobreposição de dados ou melhorar a qualidade da coleta. Entretando, essa comunicação pode crescer bastante à medida em que o número de processos aumentam.

A paralelização dos web crawlers nos trazem importantes vantagens em relação aos crawlers não paralelizados, como:

    • Escalabilidade: devido ao enorme tamanho da Web, é quase que uma obrigação utilizar crawlers paralelos. Um crawler de um único processo simplesmente pode não atingir a taxa de coleta desejada em certos casos.
    • ```NETWORK-LOAD DISPERSION```: os múltiplos processos de um crawler paralelo podem rodar em lugares geograficamente distantes, cada um coletando dados de locais próximos geograficamente. Por exemplo, um processo no Brasil pode coletar páginas dos países da América do Sul, enquanto um outro processo na Alemanha coleta dados da Europa. Essa dispersão pode ser necessária quando um crawler serial não consegue lidar com uma carga pesada de uma coleta em larga escala.
    • ```NETWORD-LOAD REDUCTION```: um crawler paralelo pode também reduzir a carga na rede. Por exemplo, assuma que um crawler na América do Norte precise coletar uma página da Europa. Primeiramente, a página deve ir pela rede na Europa, passando pela rede inter-continental Europa-para-América do Norte, e finalmente passa pela rede na América do Norte. Se um processo de um crawler paralelo coleta todas as páginas européias, e outro processo coleta as páginas da América do Norte, então o tráfego total na rede será reduzido.

Note que as páginas coletadas devem ser transferidas para uma central de comando, a fim de se construir um indice geral. Essa transferência de dados pode ser bastante reduzida usando algum dos seguintes métodos:

    • Compressão: as páginas coletas e armazenadas podem ser comprimidas antes de serem enviadas a uma localização central.
    • Diferença: ao invés de mandar uma imagem inteira de todas as páginas coletadas por um processo, é possível mandar apenas a diferença entre a imagem corrente e a anterior. Isso pode reduzir o tráfego porque muitas páginas são estáticas e não costumam ser atualizadas com muita frequência.
    • Sumarização: em muitos casos é necessário apenas um indice central, e não as páginas originais. Nesses casos, apenas as informações relevantes precisam ser enviadas ao centro de comando.

Fica claro que para a construção de Web crawlers efetivos é necessário muito mais do que apenas uma simples paralelização.

Arquitetura de um crawler paralelo

A figura [[Image: | Arquitetura geral de um crawler paralelo]] nos mostra a arquitetura geral de um crawler paralelo, que consiste de múltiplos processos, referidos por . Cada é responsável por executar uma tarefa básica de um crawler não paralelo. Ele coleta páginas da Web, armazena as páginas localmente, extrai todas as URLs que encontrar e segue os links. Dependendo da forma com que as tarefas são divididas entre os , pode ser necessário a troca de dados entre os processos. A distribuição de tarefas entre os pode ser feita numa rede local (como uma LAN), ou em localizações geograficamente distantes (como uma WAN).

    • Intra-site crawler: quando todos os processos rodam em uma mesma rede local e se comunicam em alta velocidade. Na figura anterior, isso pode ser observado no caso onde todos os rodam na rede local da parte de cima.
    • Crawler distribuido: quando todos os processos rodam em localizações geograficamente distantes. Quando os processos nessas localizações distantes se conectam via Internet, se torna importante determinar a frequência e a quando os processos devem se comunicar.

Em um crawler que roda com múltiplos processos, é possível ocorrer o problema da sobreposição. Para evitar esse problema, os processos devem ser coordenados entre eles para saber quais páginas cada um deve coletar. Essa coordenação pode ser feita seguindo algum dos caminhos:

    • Independência: os podem coletar páginas de uma maneira completamente independente um dos outros sem qualquer coordenação. Cada processo começa com um conjunto de URLs e vai seguindo os links sem consultar outro processo. Neste cenário, o problema da sobreposição pode ocorrer.
    • Assinalamento Dinâmico: ocorre quando existe uma central de comando que divide a Web em partições pequenas, usando para isto alguma função pré-estabelecida, e dinamicamente assinala cada partição a um processo. Essas partições podem ser feitas em diferentes granularidades, o que afeta a comunicação entre os processos e a central de comando.
    • Assinalamento Estático: ocorre quando a Web é particionada e assinalada a cada antes de começar a coleta. Neste caso, cada sabe qual é responsável por qual página, não precisando de uma central de comando para isto.

Conclusão

Estudos mais detalhados sobre crawlers paralelos podem ser encontrados em diversas referências, como [] MAIS REFERENCIAS - PEGAR NO RELATED WORK DO PAPER.

Web crawlers vem sendo utilizados com cada vez mais frequência para coletar dados da Web para máquinas de busca, caches e mineração de dados. Como o tamanho da Web aumenta a cada dia que passa, o uso de crawlers paralelos vem se tornando cada vez mais importante. Conforme observado nessa subseção, construir um crawler paralelo eficiente é muito mais complicado do que uma simples paralelização.

Programação paralela na web

  • Ambientes de programação
  • Bibliotecas de programação
  • Linguagens de programação
    • PHP
    • Java
  • Tecnologias
    • AJAX
    • CGI

Conclusão

Referências