Web Crawler

When someone searches, the search engine does not go to the web at that moment. That would be too slow.

It answers from an index, a table that says which pages contain each word.

To build that index it needs a copy of every page, and the crawler is the program that downloads those copies and stores them.

Quando alguém faz uma pesquisa, o buscador não vai até a web naquele momento. Isso seria lento demais.

Ele responde a partir de um índice, uma tabela que diz quais páginas contêm cada palavra.

Para montar esse índice ele precisa de uma cópia de cada página, e o crawler é o programa que baixa essas cópias e as guarda.

A search engine downloads pages to build its index.

A web archive, such as the Internet Archive, downloads pages to keep a copy of how the web was.

Web mining downloads pages to take data out of them, such as the prices of a store.

Web monitoring downloads pages to find copies of protected content, such as a pirated book.

Um buscador baixa páginas para montar o seu índice.

Um acervo da web, como o Internet Archive, baixa páginas para guardar uma cópia de como a web era.

A mineração de dados baixa páginas para tirar informações de dentro delas, como os preços de uma loja.

O monitoramento baixa páginas para encontrar cópias de conteúdo protegido, como um livro pirateado.

The scope of this crawler is to collect one billion HTML pages per month for a search engine.

It has to find new pages and also notice the ones that changed, keep every page for up to five years, and skip a page whose content it already has.

O escopo deste crawler é coletar um bilhão de páginas HTML por mês para um buscador.

Ele precisa encontrar páginas novas e também perceber as que mudaram, guardar cada página por até cinco anos, e pular uma página cujo conteúdo ele já tem.

The crawler also needs four qualities.

Scalability, because the web has billions of pages.

Robustness, because the web is full of broken HTML, servers that do not answer and links that never end, and the crawler has to keep running.

Politeness, because each site can only take so many requests, so the crawler must not send too many to the same one.

Extensibility, because one day someone will want to collect another type of content, such as images.

O crawler também precisa de quatro qualidades.

Escalabilidade, porque a web tem bilhões de páginas.

Robustez, porque a web é cheia de HTML quebrado, servidores que não respondem e links que nunca acabam, e o crawler precisa continuar rodando.

Politeness, porque cada site aguenta um número limitado de requisições, então o crawler não pode mandar requisições demais para o mesmo site.

Extensibilidade, porque um dia alguém vai querer coletar outro tipo de conteúdo, como imagens.

One billion pages per month, divided by the seconds in a month, is about 400 pages per second. The peak is assumed to be twice that, 800.

With an average page of 500 kilobytes, one month of pages takes 500 terabytes.

Kept for five years, that is 30 petabytes.

Um bilhão de páginas por mês, dividido pelos segundos de um mês, dá cerca de 400 páginas por segundo. O pico é assumido como o dobro, 800.

Com uma página média de 500 kilobytes, um mês de páginas ocupa 500 terabytes.

Guardadas por cinco anos, são 30 petabytes.

The crawler has to start somewhere, so it receives a few URLs to begin with.

The seeds go into the URL Frontier, and every other page is found by following the links of the pages already downloaded.

O crawler precisa começar por algum lugar, então ele recebe algumas URLs iniciais.

As seeds entram na URL Frontier, e todas as outras páginas são encontradas seguindo os links das páginas já baixadas.

The first component is the URL Frontier. It holds the URLs the crawler has found and has not downloaded yet.

The frontier is a queue. The URL in pink is the next one to be downloaded, and new links enter at the other end.

It starts with the seed A. Downloading A adds B and C. Downloading B adds D and E after C. Downloading C adds F and G after E.

The last four pages have no links, so the frontier empties and the crawl ends.

Because the oldest URL always leaves first, the pages are visited level by level. This order is called breadth first.

O primeiro componente é a URL Frontier. Ela guarda as URLs que o crawler já encontrou e ainda não baixou.

A frontier é uma fila. A URL em rosa é a próxima a ser baixada, e os links novos entram na outra ponta.

Ela começa com a seed A. Baixar A acrescenta B e C. Baixar B acrescenta D e E depois de C. Baixar C acrescenta F e G depois de E.

As quatro últimas páginas não têm links, então a frontier esvazia e o crawl termina.

Como a URL mais antiga sempre sai primeiro, as páginas são visitadas nível por nível. Essa ordem se chama busca em largura.

The URL that leaves the frontier goes to the HTML Downloader, whose job is to fetch the page.

A URL has the name of a site, and the network works with numeric addresses. So the downloader first asks the DNS Resolver for the address of example.com.

With the address, it sends a GET request for the page, and the server answers 200 OK followed by the HTML.

A URL que sai da frontier vai para o HTML Downloader, que tem o trabalho de buscar a página.

Uma URL tem o nome de um site, e a rede trabalha com endereços numéricos. Então o downloader primeiro pergunta ao DNS Resolver qual é o endereço de example.com.

Com o endereço, ele envia uma requisição GET pedindo a página, e o servidor responde 200 OK seguido do HTML.

The Content Parser reads the HTML and separates two things.

The first is the text, such as the title and the paragraphs. This is what the search engine will index, so the page goes to Content Storage.

The second is the links, which are the addresses of other pages. They go to the URL Extractor.

O Content Parser lê o HTML e separa duas coisas.

A primeira é o texto, como o título e os parágrafos. É isso que o buscador vai indexar, então a página vai para o Content Storage.

A segunda são os links, que são os endereços de outras páginas. Eles vão para o URL Extractor.

A link in a page is usually written in a short form, relative to the page it is in.

The URL Extractor turns each one into a complete URL, using the address of the page as the base.

For example, /about found on this page becomes https://example.com/about.

The complete URLs go back to the URL Frontier.

Um link dentro de uma página costuma ser escrito de forma curta, relativa à página em que ele está.

O URL Extractor transforma cada um em uma URL completa, usando o endereço da página como base.

Por exemplo, /about encontrado nesta página vira https://example.com/about.

As URLs completas voltam para a URL Frontier.

Content Storage keeps each downloaded page together with its URL, so the search engine can build its index from them later.

O Content Storage guarda cada página baixada junto com a sua URL, para o buscador montar o índice a partir delas depois.

The seeds enter the URL Frontier, the HTML Downloader downloads each page, the Content Parser reads it, the page goes to Content Storage, and the URL Extractor sends the links back to the frontier.

As seeds entram na URL Frontier, o HTML Downloader baixa cada página, o Content Parser a lê, a página vai para o Content Storage, e o URL Extractor manda os links de volta para a frontier.

Version one has a problem: it can run forever.

For example, page A has a link to page B, and B has a link back to A. The crawler downloads A, then B, then A again, and it never ends.

A versão um tem um problema: ela pode rodar para sempre.

Por exemplo, a página A tem um link para a página B, e B tem um link de volta para A. O crawler baixa A, depois B, depois A de novo, e nunca termina.

The solution is to remember what was already found. URL Seen? is a set with every URL found so far.

A link only enters the frontier if it is not in the set.

On the same three pages, when B links back to A, A is already in the set, so that link is discarded.

After three downloads the frontier is empty and the crawl ends.

A solução é lembrar o que já foi encontrado. O URL Seen? é um conjunto com todas as URLs encontradas até agora.

Um link só entra na frontier se não estiver no conjunto.

Nas mesmas três páginas, quando B aponta de volta para A, A já está no conjunto, então esse link é descartado.

Depois de três downloads a frontier está vazia e o crawl termina.

However, URL Seen? alone still lets the same page through when its URL is written in a different way.

For example, example.com/about and EXAMPLE.com/about#team lead to the same page. For URL Seen? they are two different URLs, so the page is downloaded twice.

Porém, o URL Seen? sozinho ainda deixa passar a mesma página quando a URL dela vem escrita de outra forma.

Por exemplo, example.com/about e EXAMPLE.com/about#team levam à mesma página. Para o URL Seen? são duas URLs diferentes, então a página é baixada duas vezes.

So before URL Seen?, every URL should be normalized with the rules of this table.

After that, the two URLs of the example both become example.com/about, and the page is downloaded once.

Por isso, antes do URL Seen?, toda URL deve ser normalizada com as regras desta tabela.

Depois disso, as duas URLs do exemplo viram example.com/about, e a página é baixada uma vez só.

The URLs that pass URL Seen? should be kept somewhere: URL Storage, a table with one URL per row, always already normalized.

For example, a link to Wiki.net/dns is normalized and is not in URL Storage, so it is added there and enters the frontier.

Then a link to EXAMPLE.com/about#team becomes example.com/about, which is already in URL Storage, so it is discarded.

As URLs que passam pelo URL Seen? devem ser guardadas em algum lugar: o URL Storage, uma tabela com uma URL por linha, sempre já normalizada.

Por exemplo, um link para Wiki.net/dns é normalizado e não está no URL Storage, então é acrescentado nele e entra na frontier.

Depois, um link para EXAMPLE.com/about#team vira example.com/about, que já está no URL Storage, então é descartado.

Yet normalization lets through two different URLs that return the same content.

For example, example.com/articles/crawler and example.com/print/crawler are the same article, one of them in its print version. The URLs are different, so the crawler downloads and stores the same text twice.

Entretanto, a normalização deixa passar duas URLs diferentes que devolvem o mesmo conteúdo.

Por exemplo, example.com/articles/crawler e example.com/print/crawler são o mesmo artigo, um deles na versão para impressão. As URLs são diferentes, então o crawler baixa e guarda o mesmo texto duas vezes.

So after the download, the crawler should compute a hash of the page. A hash is a short code calculated from the content, and the same content always gives the same code.

Content Seen? should keep the hashes of the pages already stored. If the hash of a new page is already there, the page is discarded.

Por isso, depois do download, o crawler deve calcular um hash da página. Um hash é um código curto calculado a partir do conteúdo, e o mesmo conteúdo sempre dá o mesmo código.

O Content Seen? deve guardar os hashes das páginas já armazenadas. Se o hash de uma página nova já está lá, a página é descartada.

Still, URL Seen? and Content Seen? let through the sites that generate links without end.

For example, a calendar always has a link to the next month. Each month is a new URL and a different page, so the frontier never gets empty.

Ainda assim, o URL Seen? e o Content Seen? deixam passar os sites que geram links sem fim.

Por exemplo, um calendário sempre tem um link para o mês seguinte. Cada mês é uma URL nova e uma página diferente, então a frontier nunca esvazia.

A site like this cannot be detected with certainty, so the crawler should limit the damage.

It should limit the depth, the length of a URL and the number of pages per host, and keep a blocklist written by hand.

Não há como detectar um site assim com certeza, então o crawler deve limitar o estrago.

Ele deve limitar a profundidade, o tamanho da URL e o número de páginas por host, e ter uma lista de bloqueio escrita à mão.

Even so, nothing so far stops the crawler from downloading what is not HTML.

For example, a page has links to a photo, a PDF and a mail address. All of them enter the frontier and become downloads the search engine does not use.

Mesmo assim, nada até aqui impede o crawler de baixar o que não é HTML.

Por exemplo, uma página tem links para uma foto, um PDF e um endereço de e-mail. Todos entram na frontier e viram downloads que o buscador não usa.

So the URL Filter should discard those links before they enter the frontier, by the extension, by the scheme and by a list of blocked hosts.

Por isso o URL Filter deve descartar esses links antes de entrarem na frontier, olhando a extensão, o scheme e uma lista de hosts bloqueados.

After the Content Parser, the page follows two paths.

On the first, Content Seen? decides if the page is stored or discarded as a duplicate.

On the second, the links go through the URL Extractor, the URL Filter, normalization and URL Seen? before they reach the frontier. URL Storage keeps the URLs already seen.

Depois do Content Parser, a página segue dois caminhos.

No primeiro, o Content Seen? decide se a página é guardada ou descartada como duplicata.

No segundo, os links passam pelo URL Extractor, pelo URL Filter, pela normalização e pelo URL Seen? antes de chegarem à frontier. O URL Storage guarda as URLs já vistas.

Version two has a problem: it sends many requests in a row to the same site.

For example, a page of example.com has several links to example.com itself. They enter the frontier together and leave together, and example.com receives four requests in the same second.

A site treated like this refuses the requests, blocks the crawler or goes down.

A versão dois tem um problema: ela manda muitas requisições seguidas para o mesmo site.

Por exemplo, uma página de example.com tem vários links para o próprio example.com. Eles entram juntos na frontier e saem juntos, e example.com recebe quatro requisições no mesmo segundo.

Um site tratado assim recusa as requisições, bloqueia o crawler ou cai.

So the crawler should have a Scheduler between the URL Frontier and the HTML Downloader. It lets each host receive one request at a time, with a delay before the next.

During that delay the Scheduler sends URLs of the other hosts, so the crawler does not stand still.

Por isso o crawler deve ter um Scheduler entre a URL Frontier e o HTML Downloader. Ele deixa cada host receber uma requisição por vez, com um intervalo antes da próxima.

Durante esse intervalo o Scheduler manda URLs dos outros hosts, então o crawler não fica parado.

For that, the URL Frontier should have one queue for each host, and the Scheduler takes from each queue at the pace of that host.

A single limit for the whole crawler would not be enough, because every request could still go to the same site.

Para isso a URL Frontier deve ter uma fila para cada host, e o Scheduler tira de cada fila no ritmo daquele host.

Um limite único para o crawler inteiro não bastaria, porque todas as requisições ainda poderiam ir para o mesmo site.

Nevertheless, the delay per host does not keep the crawler out of the parts of a site that its owner closed to crawlers.

For example, example.com closed its search page, /search, and each search is a different URL. The crawler asks for thousands of them, and the server still answers, because the closing is only a request. The site gets the load, and the index gets pages with nothing in them.

When the owner notices, the owner blocks the crawler, and from then on even the open pages are refused.

No entanto, o intervalo por host não impede o crawler de entrar nas partes de um site que o dono fechou para crawlers.

Por exemplo, example.com fechou a sua página de busca, /search, e cada pesquisa é uma URL diferente. O crawler pede milhares delas, e o servidor responde mesmo assim, porque o fechamento é só um pedido. O site recebe a carga, e o índice recebe páginas sem nada.

Quando o dono percebe, bloqueia o crawler, e a partir daí até as páginas abertas são recusadas.

So the crawler should read robots.txt, a file at the root of the site where the owner says what crawlers may visit.

User-agent says which crawlers the rules apply to, and the asterisk means all of them. Disallow closes a path, Allow opens an exception inside a closed path, and Sitemap points to the list of pages of the site.

When two rules match the same URL, the longest one wins. Here /search is closed, but /search/help is open, because Allow: /search/help is longer than Disallow: /search.

The crawler should download this file before the first page of each host and keep it in the robots.txt cache, so it is not asked for again on every request. Before each download, the Scheduler checks the URL against these rules.

Por isso o crawler deve ler o robots.txt, um arquivo na raiz do site em que o dono diz o que os crawlers podem visitar.

User-agent diz a quais crawlers as regras valem, e o asterisco quer dizer todos. Disallow fecha um caminho, Allow abre uma exceção dentro de um caminho fechado, e Sitemap aponta para a lista de páginas do site.

Quando duas regras valem para a mesma URL, vence a mais longa. Aqui /search está fechado, mas /search/help está aberto, porque Allow: /search/help é mais longa que Disallow: /search.

O crawler deve baixar esse arquivo antes da primeira página de cada host e guardá-lo no robots.txt cache, para não pedi-lo de novo a cada requisição. Antes de cada download, o Scheduler confere a URL com essas regras.

Even then, the crawler still loses the page when a request fails.

For example, the server is overloaded for a moment and the request fails. The crawler gives up and the page is lost, even if it would work a minute later.

And if the server never answers, the crawler waits forever.

Contudo, o crawler ainda perde a página quando uma requisição falha.

Por exemplo, o servidor está sobrecarregado por um momento e a requisição falha. O crawler desiste e a página se perde, mesmo que ela funcionasse um minuto depois.

E se o servidor nunca responder, o crawler fica esperando para sempre.

So the crawler should try again, waiting longer before each new attempt to give the server time to recover. For example, one second, two seconds, four seconds.

Every request should also have a timeout, so a server that does not answer cannot hold the crawler.

Por isso o crawler deve tentar de novo, esperando mais antes de cada nova tentativa, para dar tempo ao servidor de se recuperar. Por exemplo, um segundo, dois segundos, quatro segundos.

Toda requisição também deve ter um timeout, para um servidor que não responde não prender o crawler.

Then again, trying again only handles the requests that fail. A request can succeed and bring something the crawler cannot use.

For example, the server answers 200 OK, but the HTML stops halfway. The Content Parser receives it and fails, and that failure can stop the crawl.

Todavia, tentar de novo só cuida das requisições que falham. Uma requisição pode dar certo e trazer algo que o crawler não consegue usar.

Por exemplo, o servidor responde 200 OK, mas o HTML vem cortado pela metade. O Content Parser recebe isso e falha, e essa falha pode parar o crawl.

So the crawler should check what arrived before sending it to the Content Parser.

If it is wrong, the crawler records the error and moves on to the next URL, so one bad page never stops the crawl.

Por isso o crawler deve conferir o que chegou antes de mandar para o Content Parser.

Se estiver errado, o crawler registra o erro e segue para a próxima URL, e uma página ruim nunca para o crawl.

Version three adds two boxes. The Scheduler sits between the URL Frontier and the HTML Downloader: it lets each host receive one request at a time, with a delay before the next, and it checks every URL against robots.txt.

The robots.txt cache keeps the rules of each site, so the file is not downloaded again for every request.

The URL Frontier now has one queue per host, and the HTML Downloader has a timeout, tries again and checks what it received.

A versão três acrescenta duas caixas. O Scheduler fica entre a URL Frontier e o HTML Downloader: ele deixa cada host receber uma requisição por vez, com um intervalo antes da próxima, e confere cada URL com o robots.txt.

O robots.txt cache guarda as regras de cada site, para o arquivo não ser baixado de novo a cada requisição.

A URL Frontier passa a ter uma fila por host, e o HTML Downloader passa a ter timeout, nova tentativa e conferência do que recebeu.

Version three has a problem: it is slow.

It makes one request at a time, and each one takes about half a second, almost all of it waiting for the network. That is two pages per second, and the estimate asks for 400.

A versão três tem um problema: ela é lenta.

Ela faz uma requisição por vez, e cada uma leva cerca de meio segundo, quase todo esperando a rede. Isso dá duas páginas por segundo, e a estimativa pede 400.

So the crawler should not wait for one request to finish before starting the next. While one waits, it sends another.

To reach 400 pages per second with half a second per request, it needs 200 requests open at the same time.

Politeness still holds, because those 200 requests go to different hosts.

Por isso o crawler não deve esperar uma requisição terminar para começar a próxima. Enquanto uma espera, ele envia outra.

Para chegar a 400 páginas por segundo com meio segundo por requisição, ele precisa de 200 requisições abertas ao mesmo tempo.

A politeness continua valendo, porque essas 200 requisições vão para hosts diferentes.

That said, downloading faster does not decide what is downloaded first.

For example, the front page of a news site enters the queue behind forgotten pages, like one from 2009, and waits for all of them.

Só que baixar mais rápido não decide o que é baixado primeiro.

Por exemplo, a capa de um site de notícias entra na fila atrás de páginas esquecidas, como uma de 2009, e espera a vez de todas elas.

So each URL should receive a priority, calculated from three signals: how many pages link to it, how much traffic the site has, and how often the page changes.

The prioritizer puts the URL in a high, medium or low queue. The selector takes more from the high queue, but also from the others, otherwise a low priority page would wait forever.

Por isso cada URL deve receber uma prioridade, calculada por três sinais: quantas páginas têm link para ela, quanto tráfego o site tem e com que frequência a página muda.

O prioritizer coloca a URL em uma fila alta, média ou baixa. O seletor tira mais da fila alta, mas também das outras, senão uma página de prioridade baixa esperaria para sempre.

But priority conflicts with politeness.

For example, here the five most important pages are from the same host, portal.com. Priority says to download the five now, and politeness says one at a time.

One queue cannot obey both rules, so the frontier should be divided in two parts.

Mas a prioridade entra em conflito com a politeness.

Por exemplo, aqui as cinco páginas mais importantes são do mesmo host, portal.com. A prioridade manda baixar as cinco agora, e a politeness manda baixar uma por vez.

Uma fila só não obedece às duas regras, então a frontier deve ser dividida em duas partes.

The front part deals with priority. For example, the prioritizer puts the URL wiki.net/dns in the high queue, and the selector takes it from there.

The back part deals with politeness. The router finds the queue of wiki.net, and the URL waits there behind the other URLs of that host.

A worker downloads it when its turn comes, and then waits the delay of that host.

A parte da frente cuida da prioridade. Por exemplo, o prioritizer coloca a URL wiki.net/dns na fila alta, e o seletor a tira de lá.

A parte de trás cuida da politeness. O router encontra a fila de wiki.net, e a URL espera ali atrás das outras URLs desse host.

Um worker a baixa quando chega a vez dela, e depois espera o intervalo desse host.

So far each page is downloaded once, and pages change.

For example, the front page of a news site changes several times a day, and the stored copy is still the one from the first visit. The search engine shows old news.

Até aqui cada página é baixada uma única vez, e as páginas mudam.

Por exemplo, a capa de um site de notícias muda várias vezes por dia, e a cópia guardada continua a da primeira visita. O buscador mostra notícias velhas.

So the crawler should visit pages again, at a frequency that depends on the page.

The front page of a news site every hour, an active blog once a day, and a ten-year-old article once a month.

The frequency comes from how often the page changed in the past and from its priority.

Por isso o crawler deve visitar as páginas de novo, com uma frequência que depende da página.

A capa de um site de notícias a cada hora, um blog ativo uma vez por dia, e um artigo de dez anos atrás uma vez por mês.

A frequência vem de quantas vezes a página mudou no passado e da sua prioridade.

Despite that, with 200 requests open another wait shows up.

For example, the crawler downloads three pages of example.com and asks the DNS Resolver for the same address three times. Each question takes from 10 to 200 milliseconds, and the download waits for the answer.

Apesar disso, com 200 requisições abertas aparece outra espera.

Por exemplo, o crawler baixa três páginas de example.com e pergunta três vezes ao DNS Resolver o mesmo endereço. Cada pergunta leva de 10 a 200 milissegundos, e o download espera a resposta.

A host has thousands of pages, and the address is the same for all of them.

So the crawler should keep the addresses it already asked for, and only ask again when the host is new or when the answer expires.

Um host tem milhares de páginas, e o endereço é o mesmo para todas elas.

Por isso o crawler deve guardar os endereços que já perguntou e só perguntar de novo quando o host é novo ou quando o prazo de validade da resposta acaba.

The frontier now holds hundreds of millions of URLs.

That does not fit in the memory of the machine, and if the machine restarts, everything that was in memory is lost.

A frontier agora guarda centenas de milhões de URLs.

Isso não cabe na memória da máquina, e se a máquina reiniciar, tudo o que estava na memória se perde.

So the frontier should be kept on disk.

Since the disk is slow, it uses two buffers in memory. New URLs collect in the first one and are written to disk in batches, and the URLs about to leave are read in batches into the second one.

Por isso a frontier deve ficar em disco.

Como o disco é lento, ela usa dois buffers na memória. As URLs novas se acumulam no primeiro e são gravadas no disco em lotes, e as URLs que vão sair são lidas em lotes para o segundo.

In version four three boxes change.

The URL Frontier has priority queues in front and host queues behind, schedules the revisits and is kept on disk.

The HTML Downloader keeps 200 requests open at the same time.

The DNS Resolver has a cache.

Na versão quatro mudam três caixas.

A URL Frontier tem filas de prioridade na frente e filas por host atrás, agenda as revisitas e fica em disco.

O HTML Downloader mantém 200 requisições abertas ao mesmo tempo.

O DNS Resolver tem um cache.

Version four has a problem: it depends on one machine.

The estimate asks for 400 megabytes per second of network and 500 terabytes of disk per month, more than one machine has. And if that machine stops, the whole crawl stops.

A versão quatro tem um problema: ela depende de uma máquina só.

A estimativa pede 400 megabytes por segundo de rede e 500 terabytes de disco por mês, mais do que uma máquina tem. E se essa máquina parar, o crawl inteiro para.

So the crawler should run on many machines, and the first decision is how to divide the URLs between them.

If each URL can go to any machine, two machines receive URLs of the same host without knowing about each other, and politeness is lost.

So the URLs should be divided by host: every URL of a host goes to the same machine.

Por isso o crawler deve rodar em várias máquinas, e a primeira decisão é como dividir as URLs entre elas.

Se cada URL pode ir para qualquer máquina, duas máquinas recebem URLs do mesmo host sem saber uma da outra, e a politeness se perde.

Então as URLs devem ser divididas por host: todas as URLs de um host vão para a mesma máquina.

What is missing is the rule that says which machine takes care of each host.

The simple rule is the hash of the host name divided by the number of machines, taking the remainder. Here there are three machines.

The problem appears when a machine is added. With four, the remainder changes for four of the six hosts, and their queues have to move with them.

Falta a regra que diz qual máquina cuida de cada host.

A regra simples é o hash do nome do host dividido pelo número de máquinas, usando o resto. Aqui são três máquinas.

O problema aparece quando uma máquina é acrescentada. Com quatro, o resto muda para quatro dos seis hosts, e as filas deles precisam se mudar junto.

So the crawler should use consistent hashing. Machines and hosts sit on a ring, and each host belongs to the next machine clockwise.

When machine D enters the ring, only the two hosts between A and D change machine.

Por isso o crawler deve usar consistent hashing. Máquinas e hosts ficam em um anel, e cada host pertence à próxima máquina no sentido horário.

Quando a máquina D entra no anel, só os dois hosts entre A e D mudam de máquina.

URL Seen? has to remember every URL already found.

With one billion URLs of 100 bytes each, that is 100 gigabytes, and the set is checked for every link found. It costs too much memory.

O URL Seen? precisa lembrar todas as URLs já encontradas.

Com um bilhão de URLs de 100 bytes cada, são 100 gigabytes, e o conjunto é consultado a cada link encontrado. Isso custa memória demais.

So URL Seen? should use a Bloom filter, which keeps the same information in a row of bits, in a little more than one gigabyte.

To add a URL, three hash functions give three positions, and those three bits are set to one.

To look up a URL, the filter checks its three positions. If any of them is zero, the URL was never added, and that answer is always right.

If all three are one, the filter answers that the URL was seen. Those bits may have been set by other URLs, as in the last step, so this answer is sometimes wrong.

Por isso o URL Seen? deve usar um Bloom filter, que guarda a mesma informação em uma fileira de bits, em pouco mais de um gigabyte.

Para acrescentar uma URL, três funções de hash dão três posições, e esses três bits passam a valer um.

Para consultar uma URL, o filtro olha as três posições dela. Se alguma está em zero, a URL nunca foi acrescentada, e essa resposta está sempre certa.

Se as três estão em um, o filtro responde que a URL já foi vista. Esses bits podem ter sido ligados por outras URLs, como no último passo, então essa resposta às vezes está errada.

When the filter is wrong, the crawler treats a new URL as already seen and that page is never downloaded.

So the crawler should use the filter only as a first check.

If the filter answers not seen, the URL goes straight to the frontier. If it answers maybe seen, the crawler confirms in URL Storage, which has the exact list.

Each machine does this for its own hosts, so two machines never decide about the same URL.

Quando o filtro erra, o crawler trata uma URL nova como já vista e essa página nunca é baixada.

Por isso o crawler deve usar o filtro só como primeira verificação.

Se o filtro responde não vista, a URL vai direto para a frontier. Se responde talvez vista, o crawler confirma no URL Storage, que tem a lista exata.

Cada máquina faz isso para os seus próprios hosts, então duas máquinas nunca decidem sobre a mesma URL.

With many machines, one of them stopping is common.

When a machine stops, it takes with it thousands of URLs waiting in its frontier and hundreds of downloads in progress.

Com várias máquinas, uma delas parar é comum.

Quando uma máquina para, ela leva junto milhares de URLs esperando na sua frontier e centenas de downloads em andamento.

So the crawler should save its state to disk from time to time: the queues of the frontier, the URLs already seen and the URLs being downloaded.

After a crash, the work resumes from the last saved state, and what was done after it is done again. Storing the same page twice has to give the same result as storing it once.

Since the state is saved outside the workers, a worker that stops is replaced by another.

Por isso o crawler deve salvar o seu estado em disco de tempos em tempos: as filas da frontier, as URLs já vistas e as URLs que estão sendo baixadas.

Depois de uma queda, o trabalho continua do último estado salvo, e o que foi feito depois dele é feito de novo. Guardar a mesma página duas vezes precisa dar o mesmo resultado que guardá-la uma vez.

Como o estado fica salvo fora dos workers, um worker que para é substituído por outro.

The crawler keeps two kinds of data, used in different ways, so it should have two storages.

Content Storage keeps the HTML of the pages. These are large items, 500 terabytes per month, written once and read later by the indexer.

URL Storage keeps one small row per URL, with its state, the last visit and the next visit, and it is read and updated all the time.

O crawler guarda dois tipos de dados, usados de formas diferentes, e por isso deve ter dois armazenamentos.

O Content Storage guarda o HTML das páginas. São itens grandes, 500 terabytes por mês, gravados uma vez e lidos depois pelo indexador.

O URL Storage guarda uma linha pequena por URL, com o estado, a última visita e a próxima visita, e é lido e atualizado o tempo todo.

Neither Content Storage nor URL Storage fits on one machine. Content Storage alone grows 500 terabytes every month.

And if the only disk that holds a page fails, the page is lost.

Nem o Content Storage nem o URL Storage cabem em uma máquina. Só o Content Storage cresce 500 terabytes por mês.

E se o único disco que guarda uma página falhar, a página se perde.

So Content Storage and URL Storage should use sharding: the data is divided in parts, and each part goes to a different machine.

And they should use replication: each part has a copy on a second machine, so a disk that fails takes no page with it.

Por isso o Content Storage e o URL Storage devem usar sharding: os dados são divididos em partes, e cada parte fica em uma máquina diferente.

E devem usar replicação: cada parte tem uma cópia em uma segunda máquina, então um disco que falha não leva nenhuma página.

Even with many machines, if all of them are in one region, a page hosted on another continent takes longer to download, because each request travels further.

Mesmo com várias máquinas, se todas ficam na mesma região, uma página hospedada em outro continente demora mais para baixar, porque cada requisição viaja mais longe.

So the machines should be spread over regions, and each region downloads from the hosts that are near it.

Inside each region, consistent hashing still decides which machine takes care of each host.

Por isso as máquinas devem ser espalhadas por regiões, e cada região baixa dos hosts que estão perto dela.

Dentro de cada região, o consistent hashing continua decidindo qual máquina cuida de cada host.

What is left is extensibility, the fourth quality asked at the start.

For example, the search engine now wants to index PNG images, and the crawler only handles HTML. The URL Filter discards every link to an image.

Falta a extensibilidade, a quarta qualidade pedida no início.

Por exemplo, o buscador passa a querer indexar imagens PNG, e o crawler só sabe tratar HTML. O URL Filter descarta todo link para uma imagem.

So everything that comes after the Content Parser should work as a module, and the URL Extractor is one of them.

To collect PNG images, a PNG Downloader is added next to it, and the rest of the crawler stays the same.

Por isso tudo o que vem depois do Content Parser deve funcionar como um módulo, e o URL Extractor é um deles.

Para coletar imagens PNG, basta acrescentar um PNG Downloader ao lado dele, e o resto do crawler continua igual.

The boxes and the flow are the same since version two.

Every box now runs on many machines, spread over regions, and each host belongs to one of them.

URL Seen? is a Bloom filter in front of URL Storage, and Content Storage and URL Storage are sharded and replicated.

And the PNG Downloader is a new module next to the URL Extractor.

As caixas e o fluxo são os mesmos desde a versão dois.

Cada caixa agora roda em várias máquinas, espalhadas por regiões, e cada host pertence a uma delas.

O URL Seen? é um Bloom filter na frente do URL Storage, e o Content Storage e o URL Storage têm sharding e replicação.

E o PNG Downloader é um módulo novo, ao lado do URL Extractor.