Upload
alexandre-duarte
View
302
Download
0
Embed Size (px)
Citation preview
Aula 13: Índices e rastejamento (crawling) web
Alexandre [email protected]
1 111
Ordenação e Recuperação de Dados
Revisão da última aula Pesquisa na Web Spam Tamanho da Web Deteção de duplicatas
Usar o Coeficiente de Jaccard para calcular a similaridade entre dois documentos
2
Aula de Hoje Rastejamento
3
Operação básica de um crawler Começar com um conjunto conhecidos
de URLs (“raiz”) Recuperar e fazer parsing
Extrair as URLs referenciadas Colocar as URLs em uma fila
Recuperar cada URL da fila e repetir
Sec. 20.2
4
Retrado do crawling
Web
URLs na Fronteira
Web desconhecida
Páginasraíz
URLs recuperadase processadas
Sec. 20.2
5
Algumas complicações desse retrato Crawling na web não pode ser feito com uma única máquina
Todos os passos descritos são distribuídos
Páginas maliciosas Spam Armadilhas– incluído páginas geradas dinamicamente
Mesmo páginas não maliciosas podem ser desafiadoras Latência/largura de banda de servidores remotos varia Profundidade
Quão “profundo” deve-se ir numa hierarquia de URLs? Espelhos e duplicatas de sites Educação – não borbardear um servidor muito frequentemente
Sec. 20.1.1
6
O que todo crawler precisa fazer
Ser Educado: Respeitar considerações implícitas e explicitas Só processar páginas permitidas Respeitar o robots.txt (mais sobre isso jajá)
Ser Robusto: Ser imune a armadilhas e comportamento malicioso de servidores web
Sec. 20.1.1
7
O que todo crawler deve fazer Se capaz de operar de forma distribuída:
projetado para rodar em várias máquinas distribuídas
Ser escalável: projetado para aumentar a taxa de processamento com a adição de mais máquinas
Desempenho/eficiência: permitir uso total dos recursos de processamento e rede disponíveis
Sec. 20.1.1
8
O que todo crawler deve fazer
Recuperar as páginas de “maior qualidade” primeiro
Operação Contínua: Continuar a recuperar cópias atualizadas de páginas previamente recuperadas
Extensibilidade: Adaptação a novos formatos de dados, protocolos, etc
Sec. 20.1.1
9
Retrato do crawling atualizado
URLs recuperadase processadas
Web desconhecida
Páginas Raiz
URLs na Fronteira
Crawling thread
Sec. 20.1.1
10
URLs na fronteira
Podem incluir várias páginas de um mesmo servidor
Precisa evitar tentar recuperar todas elas ao mesmo tempo
Precisa tentar manter todos os crawling threads ocupados
Sec. 20.2
11
Educação Explicita e Implícita
Educação explicita: especificações dos webmasters sobre que porções do site podem ser recuperadas robots.txt
Educação implícita: mesmo sem especificação, evitar visitar um site muito frequentemente
Sec. 20.2
12
Robots.txt Protocolo criado em 1994 para dar aos crawlers
(“robôs”) acesso limitado a um website www.robotstxt.org/wc/norobots.html
Website anunciam seus requisitos sobre o que pode e não pode ser recuperado
Para um servidor, criar um arquivo /robots.txt Este arquivo especifica as restrições de acesso
Sec. 20.2.1
13
Exemplo de Robots.txt Nenhum robô deve visitar URLs começando com
"/yoursite/temp/", exceto o robô chamado “searchengine":
User-agent: *
Disallow: /yoursite/temp/
User-agent: searchengine
Disallow:
Sec. 20.2.1
14
Etapas de processamento durante o crawling Escolher uma URL da fronteira Recuperar o documento correspondente Fazer parse do documento
Extrair links para outros documentos (URLs)
Checar se a URL tem conteúdo já visto Se não, adicionar ao índices
Para cada URL extraída Garantir que ela passa em alguns filtros de teste para URLs Checar se ela já está na fronteira (eliminação de URLs
duplicadas)
Ex., só processar .edu, obedecer robots.txt, etc.
Qual?
Sec. 20.2.1
15
Arquitetura básica
WWW
DNS
Parse
Contentseen?
DocFP’s
DupURLelim
URLset
URL Frontier
URLfilter
robotsfilters
Fetch
Sec. 20.2.1
16
DNS (Domain Name Server) Um serviço de consulta na Web
Dada uma URL, recuperar seu endereço IP Serviço oferecido por um conjunto distribuído de
servidores, portanto, latências de consulta podem ser altas (mesmo de segundos)
Implementações comuns de consultas a DNS nos Sistemas Operacionais são bloqueantes: apenas uma consulta aberta por vez
Soluções Cache de DNS Batch DNS resolver – coleta as requisições e envia as
consultas de uma só vez
Sec. 20.2.2
17
Parsing: normalização de URL
Quando um documento recuperado é processado, alguns dos links são URLs relativas
Ex., http://en.wikipedia.org/wiki/Main_Page tem um link relativo para /wiki/Wikipedia:General_disclaimer que aponta para a URL absoluta http://en.wikipedia.org/wiki/Wikipedia:General_disclaimer
Durante o parsing é preciso normalizar (expandir) URLs relativas
Sec. 20.2.1
18
Conteúdo já visto?
Duplicação está em todo lugar na web Se a página recuperada já está no
índice, deve ser ignorada Isso é verificado utilizando assinaturas
de documentos
Sec. 20.2.1
19
Filtros e robots.txt
Filtros – expressões regulares para URLs a serem (ou não) recuperadas
Uma vez que o arquivo robots.txt de um site é recuperado, ele não precisa ser recuperado repetivas vezes Fazer isso consume largura de banda e
afeta os servidores web Fazer cache dos arquivos robots.txt
Sec. 20.2.1
20
Eliminação de URL duplicadas
Para uma recuperação não-contínua, testar para ver se a URL extraída+filtrada já está na fronteira
Para uma recuperação contínua, ver detalhes sobre a implementação da fronteira
Sec. 20.2.1
21
Distribuíndo o crawler Executar vários threads do crawler, dentro de
diferentes processos, potencialmente em diferentes nós Nós distribuídos geograficamente
Particionar os servidores sendo processados entre os nós Partição baseada em hash
Como esses nós se comunicam e compartilham URLs?
Sec. 20.2.1
22
Comunicação entre os nós Saída do filtro de URLs em cada nó é enviada para um
Eliminador de URLs Duplicadas do nó apropriado
WWW
Fetch
DNS
ParseContentseen?
URLfilter
DupURLelim
DocFP’s
URLset
URL Frontier
robotsfilters
Hostsplitter
Para outrosnós
Deoutrosnós
Sec. 20.2.1
23
URLs na fronteira: duas principais considerações
Educação: não visitar um servidor web muito frequentemente
Atualização: recuperar algumas páginas mais frequentemente que outras Ex., páginas (como sites de notícias) cujos
conteúdos mudam frequentementeEstes objetivos estão em conflitos.(Ex., Filas de prioridade não são suficientes –
muitos dos links de uma página vão para o mesmo servidor, criando uma rajada de acessos a este servidor.)
Sec. 20.2.3
24
Educação – desafios
Mesmo que restrinjamos a um único thread por host, ele ainda poderá ser visitado repetidas vezes
Heurística comum: inserir um intervalo entre duas consultas sucessivas a um mesmo servidor que seja >> que o tempo necessário para recuperar o documento da última vez
Sec. 20.2.3
25
Back queue selector
B back queuesSingle host on each
Crawl thread requesting URL
URL na fronteira: Esquema de Mercator
Biased front queue selectorBack queue router
Prioritizer
K front queues
URLs
Sec. 20.2.3
26
Fronteira de URLs de Mercator As URLs fluem do topo até a fronteira As filas da frente gerenciam a priorização As filas de trás garantem educação Cada fila é FIFO
Sec. 20.2.3
27
Filas da Frente
Prioritizer
1 K
Biased front queue selectorBack queue router
Sec. 20.2.3
28
Filas da Frente Prioritizer atribui uma prioridade de 1 a K para
cada URL Adiciona a URL à fila correspondente
Heurística para atribuição de prioridade Taxa de atualização observada nas recuperações
anteriores Específica da Aplicação (ex., “checar sites de
notícias mais frequentemente”)
Sec. 20.2.3
29
Biased front queue selector Quando uma fila de trás solicita uma URL:
escolhe uma fila da frente de onde remover a URL
Esta escolha pode ser feita utilizando round robin ou utilizando alguma variante mais sofisticada Também pode ser aleatória
Sec. 20.2.3
30
Filas de trás
Biased front queue selectorBack queue router
Back queue selector
1 B
Heap
Sec. 20.2.3
31
Filas de trás
Cada fila é mantida não-vazia enquanto o processamento é realizado
Cada fila contém URLs de um único servidor Manter uma tabela mapeando servidores em
filas
Host name Back queue
… 3
1
B
Sec. 20.2.3
32
Heap das filas de trás Uma entrada para cada fila de trás A entrada é o menor tempo te no qual o servidor
correspondente pode ser visitado novamente O menor tempo é determinado a partir do
Último acesso ao servidor Alguma outra heurística desejada
33
Processamento das filas de trás
Um crawler thread a procura de uma URL para recuperar: Extrair a raiz do heap Recuperar a URL na cabeça da fila correspondente q (olhar a
tabela) Checar se a fila q esta vazia – em caso afirmativo obter uma
URL v das filas da frente se já existe uma fila de trás para o servidor de v, adicionar v à esta fila
e pegar outra URL das filas da frente, repetir Caso contrário, adicionar v a q
Quando q é não-vazia, criar uma entrada no heap para q
Sec. 20.2.3
34
Número de filas de trás B Manter todos os threads ocupados mas
mantendo a educação Recomendação de Mercator: ter três vezes mais
filas que crawler threads
Sec. 20.2.3
35