O nosso papel: somos a Geonode e comercializamos proxies, que são um recurso utilizado no rastreamento e não na gestão de listas. A verdade é que uma lista de rastreamento mal gerida custa muito mais do que um plano de proxies mal escolhido. Um rastreador sem normalização de URLs visita a mesma página dezenas de vezes com diferentes ordens de parâmetros de consulta e, num modelo de preços por gigabyte, paga por cada uma dessas visitas. Um rastreador sem limites de orçamento segue um calendário até ao infinito e cobra-lhe por isso. Corrigir a lista é gratuito; corrigi-la depois da fatura já não é. Essa secção encontra-se abaixo e é a que vale a pena ler em primeiro lugar.
O que é, na verdade, uma lista de rastreamento
Três conceitos que são frequentemente confundidos.
A lista inicial — o ponto de partida. Um conjunto de URLs ou um mapa do site completo.
A fronteira — URLs descobertos e colocados na fila, mas ainda não recuperados. Esta é a estrutura de dados ativa e aquela que contém todas as decisões de design.
O conjunto de URLs visitados — URLs já recuperados, guardados para que não os recupere novamente.
O ciclo de vida é um ciclo: retira-se um URL da fronteira, obtém-se o conteúdo, extraem-se os links, normalizam-se, descartam-se os que já se encontram no conjunto de visitados ou já estão na fila, adiciona-se o restante à fronteira e marca-se o URL como visitado. Repete-se até a fronteira ficar vazia ou o orçamento se esgotar.
Simples no essencial. Cada passo tem um pormenor que lhe custará um dia se o fizer mal.
Semeadura: De onde vêm os primeiros URLs
Por ordem da poupança de trabalho que cada um proporciona.
O mapa do site. A melhor fonte de semeadura disponível, porque é o próprio inventário do site e inclui carimbos de data/hora lastmod que indicam o que mudou. Encontre-o através da diretiva Sitemap: em robots.txt e siga os ficheiros de índice do mapa do site de forma recursiva.
Um feed ou API de um parceiro. Se existir algum, talvez nem precise de fazer um rastreio.
Arquivos da Web. A API CDX do Internet Archive devolve URLs históricos de um domínio, incluindo páginas que já não têm ligações a partir de lado nenhum. Não tem qualquer custo para o alvo e encontra páginas órfãs que o rastreio não consegue detetar.
Operadores de pesquisa. As consultas do tipo «site:» revelam páginas indexadas e, o que é ainda mais útil, subdomínios que desconhecia.
Páginas de categorias e de índice. Para um rastreamento direcionado, partir das páginas de listagem específicas que lhe interessam é muito mais eficiente do que começar pela página inicial e deixar tudo ao acaso.
A página inicial. O último recurso, e o que as pessoas procuram por defeito em primeiro lugar. Começar a partir de um URL e descobrir tudo através da navegação por links é o caminho mais lento para a pior cobertura.
Analisámos toda a hierarquia de fontes em como encontrar todas as páginas de um site. A versão resumida: uma boa lista de sementes transforma um rastreio numa recuperação.
Normalização de URLs: o passo que toda a gente ignora
O elemento de engenharia de maior valor num rastreador e o que é mais frequentemente omitido.
Sem ele, estas são cinco URLs diferentes para o conjunto de páginas visitadas e uma única página para o servidor:
http://Example.com/Products
http://example.com/products
http://example.com/products/
http://example.com:80/products
http://example.com/products?utm_source=email
RFC 3986 define as normalizações que são sempre seguras.
Normalização de maiúsculas e minúsculas. «O esquema e o host não distinguem maiúsculas de minúsculas e, por isso, devem ser normalizados para minúsculas. Por exemplo, o URI <HTTP://www.EXAMPLE.com/>
é equivalente a <http://www.example.com/>."
. Tenha em atenção a restrição: «Presume-se que os outros componentes genéricos da sintaxe distinguem maiúsculas de minúsculas, a menos que o esquema defina especificamente o contrário.» Os caminhos distinguem maiúsculas de minúsculas — não os converta para minúsculas.
Além disso: «os dígitos hexadecimais dentro de um triplo de codificação percentual (por exemplo, %3a
versus %3A
) não distinguem maiúsculas de minúsculas e, por isso, devem ser normalizados para utilizar letras maiúsculas».
Normalização da codificação percentual. A RFC refere-se a isto como «uma fonte frequente de variação entre URIs que, de resto, são idênticas», uma vez que «alguns criadores de URIs utilizam a codificação por por cento em octetos que não requerem essa codificação». Estes «devem ser normalizados através da descodificação de qualquer octeto codificado por por cento que corresponda a um carácter não reservado».
Normalização de segmentos de caminho. Remova os segmentos .
e ..
aplicando o algoritmo remove_dot_segments
, porque «algumas implementações em uso assumem incorretamente que a resolução da referência não é necessária quando a referência já é um URI».
Normalização baseada no esquema. A RFC apresenta o exemplo canónico — estes quatro são equivalentes:
http://example.com
http://example.com/
http://example.com:/
http://example.com:80/
Assim, um caminho vazio «deve ser normalizado para um caminho do tipo /
», e uma porta predefinida ou vazia «deve ser removida por normalização baseada no esquema».
Para além da especificação, há três normalizações que são pragmáticas, em vez de estritamente seguras, e que vale a pena aplicar com cuidado:
Remover parâmetros de rastreamento. utm_*
, fbclid
, gclid
, identificadores de sessão. Estes quase nunca alteram o conteúdo e multiplicam enormemente o número de URLs. Mantenha uma lista em vez de adivinhar.
Classifique os parâmetros de consulta restantes. ?a=1&b=2
e ?b=2&a=1
são normalmente a mesma página. Normalmente — algumas aplicações são sensíveis à ordem, por isso teste numa amostra.
Remova fragmentos. #section
é do lado do cliente e nunca chega ao servidor. É sempre seguro ignorá-lo para efeitos de rastreamento.
**E respeite rel="canonical"
.** Se uma página declarar uma URL canónica, isso significa que o site está a indicar-lhe qual, de entre vários endereços, é o verdadeiro. Respeitá-la é uma forma gratuita de deduplicação, com a própria autoridade do site por trás disso.
A Fronteira: Conceção de Filas
Três propriedades determinam se o seu rastreador é escalável.
A deduplicação deve ser económica. Antes de adicionar um URL, verifica-se se este já é conhecido. Com um milhão de URLs, uma verificação linear torna-se impraticável. Um conjunto hash funciona até certo ponto; para além disso, um filtro de Bloom oferece verificação de pertença em tempo constante, utilizando apenas uma fração da memória, com uma baixa taxa de falsos positivos — o que significa que, ocasionalmente, se ignora um URL que ainda não foi visto. Para a maioria dos rastreamentos, essa troca é aceitável; nos casos em que a exaustividade é importante, complemente o filtro com um armazenamento exato.
A ordem deve ser controlável. Uma fila FIFO simples proporciona uma percussão em largura, que é normalmente o que se pretende — alcança uma ampla cobertura desde cedo e mantém-se superficial. Uma pilha LIFO proporciona uma percussão em profundidade, que penetra profundamente num ramo e raramente é útil para o rastreio de um site. Uma fila de prioridades permite ordenar por qualquer critério que desejar, como será abordado a seguir.
O estado por anfitrião deve ser monitorizado. Na prática, a «fronteira» não é uma única fila; trata-se de uma fila por anfitrião, de modo que os limites de cortesia se aplicam a cada uma de forma independente. Uma única fila global com um limite de taxa global significa que um site de grande dimensão priva todos os outros de recursos.
A estrutura que é escalável consiste num conjunto de filas por anfitrião, juntamente com um agendador que seleciona o próximo anfitrião elegível para ser consultado — sendo «elegível» o que significa que decorreu tempo suficiente desde o último pedido dirigido a esse anfitrião.
Priorização
Qual URL deve ser obtida a seguir, quando não é possível obter todas.
Por profundidade. As páginas mais superficiais são normalmente mais importantes. Uma opção predefinida simples e eficaz.
Por padrão de caminho. Se pretender páginas de produtos, dê prioridade às URLs que correspondam a /product/. Esta é a heurística com maior retorno para rastreamentos direcionados e é extremamente económica.
Por lastmod. A partir do mapa do site. Recupere o que foi alterado.
Por histórico de alterações. Para rastreamentos recorrentes, as páginas que mudaram frequentemente no passado voltarão a mudar com frequência.
Por número de links de entrada. As páginas com links provenientes de muitos locais são normalmente mais significativas. É dispendioso de calcular durante um rastreamento, mas compensa para trabalhos de grande dimensão.
Por valor estimado. Seja qual for o seu objetivo real. Se quiser preços, dê prioridade às páginas que provavelmente os contenham.
A organização prática consiste numa pequena pontuação inteira calculada no momento da enfileiramento a partir de alguns destes sinais, utilizada como chave numa fila de prioridade. Esquemas elaborados raramente justificam a sua complexidade; a profundidade, juntamente com um bónus de padrão de caminho, cobre a maioria das necessidades.
Limites: Orçamentos e Armadilhas
Sem limites, alguns rastreios não terminam. Isto não é um caso excecional.
Profundidade máxima. Links de links de links. Um limite de profundidade de cinco ou seis abrange praticamente qualquer estrutura real de um site.
Número máximo de páginas por host. Um número fixo. Quando for atingido, pare e comunique o facto, em vez de continuar.
Número máximo total de páginas. Para todo o trabalho.
Largura de banda máxima. Especialmente no tráfego de proxy medido, onde um rastreio ilimitado significa uma fatura ilimitada.
Exclusões por padrão. Os calendários são o clássico espaço infinito — um link do tipo next month
gera URLs infinitamente. A navegação facetada num catálogo extenso produz explosões combinatórias. Exclua-os por padrão:
/calendar/
/?filter=
/*?sort=
Detecção de conteúdo duplicado. Faça um hash do corpo. Se cem URLs devolverem conteúdo idêntico, encontrou um espaço gerado em vez de cem páginas.
E fique atento à taxa de descoberta. O alarme mais útil: acompanhe as URLs recém-descobertas por página obtida. Num site finito, este valor diminui de forma constante até zero. Se se mantiver estável ou aumentar, algo está a gerar URLs mais rapidamente do que consegue consumi-las — uma armadilha, um calendário ou uma explosão facetada. Abordámos as versões deliberadas em armadilhas honeypot.
Programação do novo rastreio
Para tudo o que é executado mais do que uma vez, a lista transforma-se num calendário.
Classifique por volatilidade. As páginas que mudam de hora a hora precisam de verificações de hora a hora; as páginas que mudam uma vez por ano não precisam. Rastrear tudo com a frequência exigida pelo item mais volátil é a forma mais comum de exceder o orçamento.
Utilize pedidos condicionais. If-Modified-Since e If-None-Match transformam um novo rastreamento numa série de respostas do tipo «304 Not Modified», com um custo de algumas centenas de bytes cada. Num novo rastreamento em que a maioria das páginas se mantém inalterada, isto reduz tanto a sua fatura como a carga do alvo numa ordem de magnitude.
Adapte-se com base na observação. Se uma página não tiver sofrido alterações em dez verificações, verifique-a com menos frequência. Se tiver sofrido alterações nas últimas três, verifique-a com mais frequência. Basta um simples recuo multiplicativo.
Deteta explicitamente a remoção. As páginas desaparecem e os sites raramente o anunciam. Fica atento aos erros 404 ou aplica uma política — um URL que não tenha sido encontrado em três rastreamentos consecutivos é marcado como inativo. Sem isto, o teu conjunto de dados enche-se de entradas que já não existem, o que corrói a confiança mais rapidamente do que as entradas em falta.
Armazenamento e Escalabilidade
Uma nota sobre quando a abordagem em memória deixa de funcionar.
Até cerca de cem mil URLs, os conjuntos e listas do Python são suficientes. Não complique demasiado.
Até alguns milhões, uma base de dados local — o SQLite funciona bem — com índices no hash da URL e no estado da recuperação. A persistência também significa que um rastreamento interrompido é retomado em vez de reiniciado, o que é mais importante do que o desempenho.
Para além disso, uma fila adequada e um armazenamento de chave-valor, com a fronteira particionada por anfitrião, para que os trabalhadores possam ser atribuídos a anfitriões inteiros e a «politeness» se mantenha correta sem necessidade de coordenação.
Duas decisões de design que compensam em qualquer escala:
Armazene o hash da URL, não apenas a URL. As comparações e os índices num hash de comprimento fixo são mais económicos e o armazenamento é menor.
Armazenar a resposta bruta, não apenas o resultado analisado. Quando um analisador falhar — e isso irá acontecer —, reanalisar o que se tem é gratuito, enquanto que a nova recuperação custa largura de banda e boa vontade.
Uma implementação mínima
O código completo tem cerca de quarenta linhas, para tornar os mecanismos em ação mais concretos.
import time
from collections import deque, defaultdict
from urllib.parse import urlsplit, urlunsplit, parse_qsl, urlencode
TRACKING = {"utm_source", "utm_medium", "utm_campaign", "fbclid", "gclid"}
def normalise(url):
p = urlsplit(url)
host = p.hostname or ""
port = "" if p.port in (None, 80, 443) else f":{p.port}"
query = urlencode(sorted(
(k, v) for k, v in parse_qsl(p.query, keep_blank_values=True)
if k.lower() not in TRACKING
))
return urlunsplit((p.scheme.lower(), host + port, p.path or "/", query, ""))
class Frontier:
def __init__(self, delay=1.5, max_per_host=5000):
self.queues = defaultdict(deque)
self.seen = set()
self.next_ok = defaultdict(float)
self.counts = defaultdict(int)
self.delay, self.max_per_host = delay, max_per_host
def add(self, url, depth=0):
url = normalise(url)
if url in self.seen or depth > 5:
return False
host = urlsplit(url).hostname
if self.counts[host] >= self.max_per_host:
return False
self.seen.add(url)
self.counts[host] += 1
self.queues[host].append((url, depth))
return True
def next(self):
now = time.monotonic()
for host, q in self.queues.items():
if q and self.next_ok[host] <= now:
self.next_ok[host] = now + self.delay
return q.popleft()
return None
Nesse código, são visíveis cinco decisões de conceção, e cada uma corresponde a uma secção acima.
A normalização ocorre em add(), e não no momento da recolha. A deduplicação só é correta se a forma canónica for a que entra no conjunto de páginas visitadas; por isso, normalizar mais tarde significa que já se armazenaram duplicados.
O conjunto de páginas visitadas é preenchido no momento da colocação na fila, e não após a conclusão. Caso contrário, um URL descoberto em vinte páginas é colocado na fila vinte vezes antes de a primeira recuperação terminar.
As filas são por anfitrião e a «politeness» é por anfitrião. next_ok regista quando cada anfitrião pode ser contactado a seguir, para que um site de grande dimensão não possa privar os outros de recursos e o atraso se aplique onde deve.
Os limites são aplicados no ponto de entrada. Os limites de profundidade e por anfitrião rejeitam URLs antes de estas consumirem memória, o que constitui a diferença entre um rastreio limitado e um que descobre o seu limite ao esgotar a RAM.
next() devolve None em vez de bloquear. Isso deixa o chamador livre para decidir se quer esperar, fazer outro trabalho ou terminar — um agendador que fica em espera dentro da estrutura de dados é algo que não se pode monitorizar.
O que falta deliberadamente aqui é a persistência, e essa é a primeira coisa a adicionar para qualquer aplicação real. Um rastreio que falha e tem de recomeçar a partir da lista inicial perdeu mais do que tempo; teve de voltar a obter tudo, o que custa largura de banda e boa vontade.
Instrumentação da lista
O que medir, porque um rastreio que apenas reporta «páginas obtidas» não diz praticamente nada.
Dimensão da fronteira ao longo do tempo. Deve tender para zero. Um aumento significa uma descoberta ilimitada.
Rácio de descoberta. Novas URLs por página obtida, tal como acima.
Resultados da recuperação por estado, por anfitrião. Os números agregados ocultam a falha total de um anfitrião.
Taxa de duplicados. Quantas URLs descobertas já eram conhecidas. Uma taxa elevada após a normalização significa que a sua normalização está a deixar escapar algo.
Bytes por página útil. O número que liga o rastreio à fatura e que revela um navegador sem interface a recuperar megabytes de imagens de que não precisava.
Verificações de conteúdo. Se as páginas contêm os marcadores que espera. Um rastreador que relata 100% de sucesso, mas devolve páginas bloqueadas de forma não definitiva, é uma falha dispendiosa, e só as verificações de conteúdo a detetam.
Perguntas frequentes
O que é uma lista de rastreamento?
O conjunto de URLs que um rastreador pretende visitar, geralmente composto por uma lista inicial, uma fronteira de URLs descobertas mas ainda não recolhidas e um conjunto de URLs já visitadas. A gestão da fronteira — ordem, deduplicação e orçamentos — é o que mais determina se um rastreio é concluído.
Como normalizo as URLs para o rastreio?
Coloque o esquema e o host em minúsculas, mas não o caminho; coloque em maiúsculas os dígitos hexadecimais com codificação percentual; descodifique a codificação percentual desnecessária; remova segmentos de ponto; elimine portas predefinidas; normalize um caminho vazio para /; remova fragmentos; e elimine parâmetros de rastreamento conhecidos. A RFC 3986 define todos estes passos, exceto os dois últimos.
O que é uma «fronteira de rastreamento»?
A fila de URLs descobertas que ainda não foram obtidas. Na prática, trata-se de um conjunto de filas por anfitrião, juntamente com um agendador que seleciona o próximo anfitrião elegível dentro dos limites de cortesia, uma vez que uma única fila global permite que um site de grande dimensão bloqueie todos os outros.
Como posso impedir que o meu rastreador funcione indefinidamente?
Limites rígidos: profundidade máxima, número máximo de páginas por anfitrião e no total, e um limite de largura de banda. Adicione exclusões de padrões para calendários e navegação facetada, e emita um alerta quando a proporção entre URLs recém-descobertos e páginas obtidas deixar de diminuir.
Como evito rastrear a mesma página duas vezes?
Normalize os URLs antes da deduplicação, uma vez que a mesma página tem muitos endereços válidos. Em seguida, verifique se a página pertence a um conjunto de páginas visitadas — um conjunto hash em pequena escala, um filtro de Bloom ou uma base de dados em grande escala. Respeite o atributo rel="canonical" quando as páginas o declararem.
Com que frequência devo voltar a rastrear?
Tão raramente quanto os seus requisitos permitirem, em função da frequência com que cada página muda efetivamente. Utilize o «lastmod» a partir do mapa do site e pedidos condicionais, para que as páginas inalteradas impliquem apenas um «304» em vez de uma obtenção completa. Rastrear tudo com a frequência das páginas voláteis é a fonte mais comum de desperdício.
O que é um filtro de Bloom e preciso de um?
Um conjunto probabilístico que determina a pertença a um conjunto em tempo constante, utilizando muito pouca memória, com uma pequena probabilidade de falsos positivos — o que significa que, ocasionalmente, pode ignorar um URL que ainda não tenha visto. Vale a pena a partir de alguns milhões de URLs; é desnecessário abaixo desse número, caso em que um conjunto simples é mais fácil de utilizar e exato.
Como deteto que as páginas foram removidas?
Esteja atento aos erros 404 e aplique uma política para as páginas que simplesmente deixam de aparecer — por exemplo, marque um URL como inativo se não tiver sido detetado em três rastreamentos consecutivos. Sem isto, um conjunto de dados acumula entradas que já não existem, o que prejudica a confiança mais rapidamente do que as lacunas.
Conclusão
O rastreamento é, na sua maioria, uma questão de gestão. A recuperação de dados é um problema já resolvido pelas bibliotecas; decidir o que recuperar, reconhecer que já o recuperou e saber quando parar é que constitui o verdadeiro desafio de engenharia.
Há três aspetos que merecem atenção desproporcional à sua dificuldade. A normalização, porque sem ela visita-se a mesma página através de uma dúzia de endereços e paga-se por cada um deles — e a RFC 3986 indica exatamente quais as transformações que são seguras. Orçamentos, porque alguns espaços de URL são genuinamente infinitos e um rastreador sem limites rígidos acabará por encontrar um. E a taxa de descoberta, porque é um único número que revela uma armadilha, um calendário ou uma explosão facetada muito antes de a fatura o fazer.
Depois, faça uma sementeção adequada. Um mapa do site transforma um rastreio numa recolha do que mudou, uma consulta ao arquivo revela páginas que a navegação por links nunca conseguirá alcançar, e ambas não custam nada ao alvo. Começar pela página inicial e ficar à espera é o caminho mais lento para o resultado menos completo, e continua a ser o padrão.