Retornar à página sobre a Google

4 Anatomia do Sistema
Inicialmente, apresentamos uma discussão superficial sobre a arquitetura. A seguir, descrevemos em profundidade algumas estruturas de dados importantes. Por fim, discutimos em profundidade as aplicações principais: rastreamento (crawling), indexação (indexing) e pesquisa (searching).

Figura 1. Arquitetura Geral da Google

4.1 Arquitetura Simplificada da Google
Nessa seção, nós dados uma visão geral de como o sistema funciona, conforme mostrado na Figura 1. Seções mais adiante discutirão as aplicações e estruturas de dados que não são mencionadas nessa seção. A maior parte da Google foi implementada em C ou C++, por razões de eficiência, e roda em Solaris ou Linux.
Na Google, o rastreamento da web  (web crawling - downloading de páginas da web) é feito por vários crawlers distribuídos. Existe um servidor de URL que envia aos cralers listas de URLs a serem recuperadas. As páginas recuperadas são enviadas ao storeserver. O storeserver comprime e armazena as páginas web em um repositório. Toda página web recebe um número de identificação chamado docID, que é assignado toda vez que uma nova URL é extraída de uma página. A indexação é realizada pelo indexador (indexer) e pelo ordenador (sorter). O indexer executa funções variadas; ele lê o repositório, descomprime os documentos, e interpreta a sintaxe (processo chamado "parse" ou "parsing"). Cada documento é convertido em um conjunto de ocorrências de palavras, denominado hits.
[Nota do Tradutor: o termo "hit" é largamente empregado nesse texto, em um sentido pouco usual aos que não estão familiarizados com Search Engines. Um hit, basicamente, é a ocorrência de uma palavra de interesse em um documento sendo pesquisado. Se estamos pesquisando a palavra "livro" e a mesma aparece no documento http://www.dominio.com/biblioteca.html", dizemos que ocorreu um hit; uma hit list (lista de hits) para a palavra "livros" registraria a ocorrência no documento http://www.dominio.com/biblioteca.html"]. Os hits gravam a palavra, a posição no documento, uma estimativa do tamanho da fonte, e a ocorrência de letras maiúsculas. O indexer distribui esses hits através de um conjunto de "barrels", criando um índice direto (forward index), parcialmente ordenado. O indexer exerce outra função importante: ele extrai todos os links de todas as páginas e armazena informações relevantes sobre eles em um arquivo de âncoras (anchor file). Esse arquivo contém informações suficientes para determinar onde o link se origina, para onde se destina, e qual o texto do link.
O resolvedor de URLs lê o arquivo de âncoras, converte URLs relativas em URLs absolutas, e a seguir em docIDs. Ele coloca o texto da âncora no índice direto, associado ao docID da página para a qual o link aponta. Ele também gera um banco de dados de links composto de pares de docIDs. O banco de dados de links é utilizado para calcular o PageRank de todos os documentos.
O sorter pega os barrels, que estão ordenados por docID (essa é uma simplificação, ver Seção 4.2.5), e os reordena por wordID, para criar o índice invertido (inverted index). Isso é feito no próprio local, de forma que pouco espaço temporário seja necessário para a operação. O sorter também produz uma lista de wordIDs e offsets no índice invertido. Um programa chamado Dump Lexicon pega essa lista, juntamente com o lexicon produzido pelo indexer, e gera um novo lexicon que será utilizado pelo searcher. O searcher é executado em um servidor web; para responder às pesquisas, ele utiliza o lexicon produzido pelo DumpLexicon, o índice invertido e os PageRanks.


4.2 Principais estruturas de dados
As estruturas de dados da Google são otimizadas de forma a permitir que grandes conjuntos de documentos sejam rastreados, indexados e pesquisados com um baixo custo. Embora CPUs e dispositivos de entrada e saída tenham melhorado dramaticamente ao longo dos últimos anos, uma pesquisa em disco ainda requer aproximadamente 10 ms para ser completada. Google foi projetada para evitar ao máximo pesquisas em disco, e isso teve uma influência considerável no projeto das estruturas de dados.
4.2.1 BigFiles
BigFiles são arquivos virtuais espalhados através de múltiplos sistemas de arquivos, que são endereçados por inteiros de 64 bits. A alocação entre os múltiplos sistemas de arquivos é feita automaticamente. O sistema de BigFiles também faz alocação e desalocação dos descritores de arquivos, já que os sistemas operacionais não suprem as nossas necessidades. BigFiles suportam também algumas opções básicas de compressão.
4.2.2 Repositório


Figura 2. Estrutura do Repositório de Dados
O repositório contém o HTML completo de cada página web. Cada página é comprimida utilizando-se zlib (ver RFC1950). A escolha da técnica de compressão foi baseada em  velocidade e taxa de compressão. Nós escolhemos zlib por ser a mais rápida, emb ora bzip oferecesse uma taxa de compressão significantemente maior. A taxa de compressão da bzip foi aproximadamente 4 para 1, enquanto a da zlib foi 3 para 1. No repositório, os documentos são armazenados um após o outro e são prefixados pelo docID, tamanho e URL, como ode ser visto na Figura 2. O repositório não requer que nenhuma outra parte da estrutura de dados seja usada para acessá-lo; esse fato é útil para se conseguir consistência de dados e torna o desenvolvimento muito mais fácil: podemos reconstruir todas as outras estruturas a partir de tão somente o repositório e um arquivo que liste erros reportados pelos crawlers.

4.2.3 Índice dos Documentos
O índice de documentos contém informações sobre cada documen to.  O índice é do tipo ISAM (Index sequencial access mode), de largura fixa, ordenado por docIDs. A informação armazenada em cada entry inclui o status atual do documento, um ponteiro para o depositório, um checksum para cada documento, e várias estatísticas. Se o documento foi crawled, o índice conterá também um ponteiro para um arquivo de tamanho variável chamado docinfo, que armazena o URL e título do documento;  caso contrário, o ponteiro aponta para a URLlist, que armazena apenas a URL. Essa decisão foi tomada com o intuito de se obter uma estrutura de dados razoavelmente compacta, e ainda permitir o acesso a um record com apenas uma pesquisa no disco.
Adicionalmente, existe um arquivo que é utilizado para converter URLs em docIDs. Trata-se de uma lista de  URLs, checksums e docIDs, ordenada por checksum. Para encontrar o docID de uma URL em particular, o checksum da URL é computado e uma busca binária é realizada nesse arquivo; batches de URLs podem ser convertidos em docIDs utilizando-se esse arquivo. Essa é a técnica utilizada pelo URLresolver para transformar URLs em docIDs. Esse modo de trabalho em batches é crucial, pois de outra forma teríamos que realizar uma busca para cada link, o que demandaria, para o nosso conjunto de 322 milhões de links, mais de um mês de processamento.

4.2.4 Lexicon
O lexicon tem diversas peculiaridades. Uma importante mudança em relação a sistemas anteriores é que o lexicon pode ser totalmente alocado em memória, por um preço razoável. Na implementação atual nós mantemos o lexicon na memória de uma máquina com 256MB de memória principal. O lexiconatual contém 14 milhões de palavras (algumas palavras raras não foram adicionadas ao lexicon). Ele é implementado em duas partes : uma lista de palavras (concatenadas juntas, mas separadas por nulls) e uma tabela de hash de ponteiros. A lista de palavras exerce algumas funções auxiliares, que estão além do escopo desse paper.
4.2.5
Hit Lists
Uma hit list corresponde a uma lista de ocorrências de uma determinada palavra em um determinado documento, incluindo posição, fonte e capitalização (uso de maiúsculas e minúsculas). As hit lists ocupam a maior parte do espaço utilizado tanto no índice direto como no índice invertido; por causa disso, é importante que sua representação seja a mais eficiente possível. [Nota do Tradutor: o conceito de hit list foi explicado de forma demasiadamente resumida pelos autores do documento. Um exemplo ajudará a esclarecer o que significa hit list. Suponhamos que, no documento http://www.meudominio.com.br/automoveis.html, a palavra "carro" apareça em várias partes: uma vez no título "Melhores carros usados do mercado", uma vez em letras maiúsculas no primeiro parágrafo (a décima palavra do texto) e outra vez no terceiro parágrafo (a centésima palavra do texto). Nesse exemplo, a hit list do documento http://www.meudominio.com.br/automoveis.html (que será identificado por um docID), para a palavra "carros" (que é identificada por um wordID), deverá de alguma maneira armazenar as informações: wordID aparece como 2a. palavra no título do docID; word ID aparece como 10a palavra do texto, e está em negrito; wordID aparece como 100a palavra do texto, fonte normal. A hit list assim formada é empregada, como se verá mais adiante, para a formação dos índices direto e invertido.]
Nós analisamos diversas alternativas para codificação da posição, fonte e capitalização: codificação simples (uma tripla de inteiros), codificação compacta (uma alocação otimizada de bits), e a codificação Huffman. Ao final, optamos pela segunda opção, pois essa exigia muito menos espaço que a primeira opção e muito menos manipulação de bits que a codificação Huffman. Os detalhes sobre os hits são mostrados na Figura 3.
Nossa codificação compacta utiliza dois bytes para cada hit. Existem dois tipos de hits: fancy hits (hits especiais) e plain hits (hits comuns). Fancy hits incluem hits que ocorrem na URL, no título, nos textos das âncoras e nos meta tags. Todos os outros hits são plain hits. Um plain hit é composto de um bit para indicar capitalização, um bit para tamanho de fonte, e 12 bits para a posição da palavra no documento (todas as posições acima de 4095 - o limite representável por doze bits - são consideradas como sendo posição 4096). O tamanho de fonte toma três bits (apenas 7 valores podem ser representados, pois 111 é um flag para indicar um fancy hit), e é representado levando-se em conta uma comparação com o restante do documento. Um fancy hit é composto por um bit de capitalização, três bits de tamanho que são sempre representados por 111, 4 bits para indicar a classe de fancy hit, e 8 bits para posição. Para hits de âncoras, os 8 bits de posição são divididos em 4 bits para posição dentro da âncora e 4 bits para um hash do docID do documento no qual a âncora aparece. Isso nos dá uma limitada capacidade de busca por frases, desde que não existam muitas âncoras contendo uma determinada palavra. Nós temos a expectativa de melhorar a maneira como os hits de âncoras são armazenadas, a fim de permitir maior resolução nos campos de posição e hashIDs. A comparação do tamanho da fonte com o restante do documento é feita porque não desejamos dar mais importância a um de dois documentos idênticos somente porque ele foi escrito com fontes maiores.


Figura 3. Indice Direto, Indice Invertido e o Lexicon
O tamanho de uma hit list é armazenada antes da relação de hits. Para economizar espaço, os bits que codificam o tamanho da hit list são combinados com os bits da wordID no índice direto e com os do docID no índice invertido. Isso limita a 8 e 5, respectivamente, o número de bits disponíveis para representar o tamanho da hit list (há alguns truques que permitem o empréstimo de 8 bits da wordID para uso no tamanho da hit list). Se o tamanho é maior do que o que pode ser descrito no número de bits disponível, um escape code é colocado nesses bits, e os próximos dois bytes passam a conter o tamanho da lista.


4.2.6. Indice direto
O índice direto já está, na realidade, parcialmente ordenado. Ele é armazenado em vários barris (nós usamos 64). Cada barril abriga uma faixa de wordIDs. Se um documento contém palavras que caiam na faixa de um determinado barril, o docID é gravado naquele barril, seguido por uma lista de wordIDs e hitlists correspondentes àquelas palavras. [Nota do Tradutor: novamente, um exemplo pode ajudar a clarificar a questão. Suponhamos que determinado docID contenha, entre várias outras, as palavras "comida" e "bebida", e que os wordIDs dessas duas palavras caiam numa mesma faixa de wordIDs (ou seja, devam ser armazenadas num mesmo barril). Então, para esse exemplo, esse barril armazenará, pela ordem: docID; wordID de "comida"; hitlist de "comida"; wordID de "bebida" (observe que não há necessidade de se repetir o docID); hitlist de "bebida"; null wordID (para separar esse docID do seguinte); próximo docID que contenha palavras que caiam nessa faixa de wordIDs; ....]
 Esse esquema requer um pouco a mais de espaço de armazenamento por causa dos docIDs duplicados, mas a diferença é pequena para um número razoável de buckets e economiza tempo e capacidade de processamento no estágio final de indexação, realizado pelo sorter. Além disso, em vez de armazenar os verdadeiros wordIDs, nós armazenamos cada wordID como a diferença em relação ao menor wordID que deva ser armazenado em um dado barril. Assim, podemos usar apenas 24 bits para as wordIDs nos barris não ordenados, deixando assim 8 bits para o comprimento da hit list.
[Nota do Tradutor: o índice direto permite recompor a totalidade de um documento HTML; para tal, faz-se o seguinte: a partir da URL, identifico o docID do documento que desejo recompor; vou ao primeiro barril, localizo aquele docID e recupero todas as palavras (wordIDs) e respectivas posições (hit list) que estejam armazenadas nesse barril; repito o procedimento para todos os barris; ao final do último barril, o texto estará inteiramente recomposto].


4.2.7. Indice invertido
O indice invertido compõe-se dos mesmos barris do indice direto, exceto que eles são processados pelo sorter. Para cada wordID válida, o lexicon contém um ponteiro para um barril que armazena aquela wordID, o qual por sua vez aponta para uma lista de docIDs, juntamente com as respectivas hit lists. Essa lista de docIDs, chamada doclist, representa todas as ocorrências daquela palavra em todos os documentos.
Uma questão importante é o critério de ordenamento de docIDs na doclist. Uma solução simples seria armazená-los por ordem crescente de docIDs; isso permitiria uma rápida mesclagem (merging) de diferentes doclists, para o caso de pesquisas com mais de uma palavra-chave. Uma outra opção é armazenar docIDs de acordo com o número de vezes que a palavra aparece em cada documento (ou seja, o primeiro docID seria aquele em que aparece o maior número de vezes, o segundo docID seria aquele em que a palavra aparece o segundo maior número de vezes, etc); essa opção tornaria mais simples as pesquisas com apenas uma palavra-chave, e provavelmente as páginas de respostas mais relevantes para pesquisas de múltiplas palavras apareceriam perto do topo. Entretanto, nessa opção, o merging é muito mais difícil; além disso, desenvolvimentos futuros tornam-se muito mais complicados, pois qualquer alteração na função de rankeamento requereria uma completa reconstrução do índice. Nós optamos por um compromisso entre essas duas opções: mantemos dois conjuntos de barris invertidos; um conjunto para hit lists que incluem hits no título ou nas âncoras, e outro conjunto para todos os demais hits. Dessa forma, nós checamos o primeiro conjunto de barris em primeiro lugar, e se não houver matches suficientes dentro desses barris, nós partimos para o outro conjunto.

4.3 Rastreando (crawling) a web
Operar um web crawler é uma tarefa desafiadora. Existem questões problemáticas relativas a desempenho e confiabilidade; mais importante, existem questões sociais. Crawling é a mais frágil das aplicações, pois envolve a interação com centenas de milhares de servidores web e vários servidores de nome (name servers) que estão além do nosso controle.
A fim de crescer ao nível de centenas de milhões de páginas web, Google desenvolveu um sistema de crawling distrubuído. Um único servidor de URL serve listas de URLs para vários crawlers (nós tipicamente operamos rodamos três). Ambos, servidor URL e crawlers, são implementados em Python. Cada crawler mantém aproximadamente 30 conexões abertas ao mesmo tempo; isso é necessário para recuperar web pages a um ritmo suficientemente rápido. Operando a velocidade máxima, o sistema pode rastrear mais de 100 páginas por segundo usando quatro crawlers; isso equivale a aproximadamente 600 K por segundo de dados.
Uma grande causa de preocupação é a consulta a DNS (DNS lookup). Cada crawler mantém seu próprio cache de DNS, a fim de evitar fazer um DNS lookup antes de recuperar cada documento. Cada uma das centenas de conexões pode estar em diversos estados: consultando DNS, conectando ao host, enviando requisições, e recebendo respostas. Esses fatores tornam o crawler um componente complexo do sistema.
O crawler utiliza IO assíncronos para gerenciar eventos, e um número de filas de controle que monitoram o estado de cada página pesquisada.

É fato que rodar um crawler que se conecta a mais de meio milhão de servidores, e gera dezenas de milhões de linhas de log, resulta em um número considerável de emails e telefonemas. Por causa do enorme contingente de pessoas que está se conectando online, sempre existem aquelas que não sabem o que um crawler faz (já que é o primeiro crawler que elas vêem). Quase que diariamente, nós recebemos uma mensagem do tipo "Legal, vocês visitaram um grande número de páginas do meu site. Vocês gostaram?". Muitas pessoas desconhecem também a existência de protocolos de exclusão de robots, e pensam que suas páginas estão protegidas apenas porque colocaram um aviso como "Esta página está protegida por direitos de autor e não deve ser indexada", o que, desnecessário dizer, não é entendido por crawlers. Ademais, por causa da enorme quantidade de dados em jogo, coisas inesperadas acontecem. Por exemplo, nosso sistema tentou rastrear um jogo online; isso resultou em várias mensagens estranhas para os jogadores, no meio da paretida. Esse problema específico foi fácil de se resolver, mas somente depois que nós já tínhamos baixado dezenas de milhões de páginas. Por causa da imensa variedade de páginas e servidores, é virtualmente impossível testar um crawler sem que o soltemos livremente em uma grande porção da internet. Invariavelmente, existem centenas de problemas obscuros que ocorrem em apenas uma página da internet inteira e causam um crash no crawler ou, pior ainda, causam um comportamento incorreto e imprevisível. Sistemas que acessam grandes porções da internet precisam ser projetados para ser muito robustos e devem ser cuidadosamente testados. Como é certo que sistemas complexos como crawlers causarão problemas, é necessário que uma parte dos recursos seja alocada para ler emails e resolver  problemas, à medida que surjam.

4.4 Indexando a Web
Interpretando a sintaxe de páginas (Parsing) - qualquer parser que seja projetado para rodar na Web deve ser capaz de tratar uma gama enorme de possíveis erros. Esses podem variar de pequenos erros de datilografia em tags HTML até kilobytes de zeros no meio de um tag, caracteres não-ASCII, aninhamentos de tags HTML em centenas de níveis, e uma grande variedade de outros erros que desafiam a imaginação de qualquer pessoa. Para máximo desempenho, em vez de utilizar YACC para gerar um parser CFG, nós utilizamos flex para gerar um analisador léxico, que a seguir nós aprimoramos. Desenvolver esse parser, que roda a velocidade razoável e é muito robusto, exigiu uma grande quantidade de trabalho.
Após cada documento ser interpretado, ele é armazenado em um número de barris. Cada palavra é convertida em uma wordID, com a ajuda de uma tabela hash que reside em meória - o lexicon. Novos termos que vão sendo adicionados à tabela hash do lexicon são registrados em um arquivo. Após a conversão das palavras em wordIDs, sua(s) ocorrência(s) é(são) registradas em hit lists e são armazenadas nos barris diretos (barris que armazenam o índice direto). A maior dificuldade para implementar a paralelização na fase de indexação é que o lexicon precisa ser compartilhado. Em vez de compartilhar o lexicon, nós adotamos o método de escrever um log com todas as palavras novas que não constavam do lexicon básico, que continha 14 milhões de palavras. Assim, múltiplos indexadores podem rodar em paralelo e, ao final, o pequeno arquivo de palavras novas pode ser processada, por um indexador final.
Ordenamento (sorting).  Para criar o índice invertido, o sorter visita cada um dos barris diretos e os ordena por wordID, cria um barril invertido apenas para palavras no título e nas âncoras, e um barril invertido para o texto completo.  Esse processo é feito em um barril de cada vez, e por isso requer pouco espaço de armazenamento temporário. Além disso, nós paralelizamos essa fase de ordenamento, usando todas as máquinas disponíveis para rodar a maior quantidade de sorters possível, os quais podem processar diferentes trechos de disco ao mesmo tempo. Como os barris não cabem na memória principal, o sorter os divide em cestas, baseadas em wordIDs e docIDs, que caibam na memória. O sorter, então, carrega cada cesta na memória, ordena-a e grava o arquivo ordenado nos dois barris invertidos.

4.5 Pesquisas (searching)
O objetivo das pesquisas é prover resultados com qualidade e eficiência. Muitas das grandes search engines comerciais parecem ter feito grande progresso em termos de eficiência. Por isso, nós nos focamos mais na qualidade das pesquisas, embora nós acreditemos que nossas soluções sejam aplicáveis a volumes comerciais com um pouco de esforço. O processo de pesquisa da Google funciona como mostrado na figura 4.
1. Interpretar os dados fornecidos pelo usuário (parse the query).
2. Converter palavras em wordIDs.
3. Ir ao início da doclist no barril curto (apenas títulos e âncoras) para cada uma das palavras.
4. Examinar as doclists até encontrar um documento que contenha todas as palavras.
5. Computar o rank para cada um dos documentos.
6. Se estiver no barril curto e atingir o final de alguma doclist, procurar o início da doclist no barril completo (todo o texto) para cada palavra e retornar ao passo 4.
7. Se não estiver no final de alguma doclist, voltar para o passo 4.
8. Ordenar os documentos por rank e retornar os que estejam entre os K primeiros.

Figura 4. Como a Google processa as pesquisas

Para limitar o tempo de resposta, quando um certo número (atualmente 40.000) de documentos é encontrado, o searcher automaticamente vai para o passo 8. Isso significa que é possível que resultados sub-ótimos sejam apresentados. Estamos atualmente investigando outras maneiras de resolver esse problema. No passado, nós ordenamos os hits por PageRank, o que nos pareceu melhorar a situação.

4.5.1. O sistema de rankeamento
A Google mantém muito mais informação sobre os documentos web do que outras search engines. Toda hitlist inclui informação sobre posição, font e capitalização. Além disso, levamos em consideração hits que ocorram nos textos das âncoras e o PageRank do documento. Combinar todas essas informações em um ranking é difícil. Nós projetamos nosso método de rankeamento de maneira tal que nenhum fator tivesse demasiada influência.
Primeiro, consideremos o caso mais simples - uma pesquisa com uma única palavra-chave. A fim de rankear um documento para tal pesquisa, Google olha para a hit list do documento para a palavra pesquisada. Google analisa cada hit separadamente, dividindo-os em tipos (título, âncoras, URLs, texto em fonte grande, texto em fonte pequena, etc), e atribui pesos diferentes a cada tipo. Os pesos formam um vetor, indexado por tipos. A seguir cada contagem (ou seja, cada ocorrência) é convertida em pesos de contagem. Os pesos de contagem aumentam linearmente com as primeiras ocorrências, mas rapidamente atingem um limite, de maneiras que ocorrências a partir de um certo número são descartadas. Nós tomamos então o produto escalar entre o vetor de pesos de contagens e o vetor de pesos de tipos para computar um score IR para o documento (Nota do tradutor: não há definição de o que seja IR nesse contexto; o termo IR usualmente significa Information Retrieval). Finalmente, o score IR é combinado com PageRank para dar um rank final ao documento.
Para uma pesquisa multi-palavras, o processo é mais complicado. Dessa feita, múltiplas hit lists devem ser consultadas, em busca de palavras que estejam próximas. Toda vez que um conjunto de hits é encontrado, um índice de proximidade entre eles é computado. O valor do índice depende da distância entre os hits no documento (ou âncoras), mas é classificado em apenas dez diferentes valores, variando desde um casamento perfeito até um "muito distantes entre si". As ocorrências são computadas levando-se em conta não apenas para todos os tipos de hit (título, âncora, etc), mas também a proximidade entre elas. Cada par tipo-proximidade tem um peso-tipo-proximidade. As ocorrências são convertidas em pesos de contagens e nós então tomamos o produto escalar entre os pesos de contagens e os pesos-tipo-proximidade para computar um score IR. [Nota do Tradutor: o documento original não menciona, mas é evidente que o PageRank é também levado em conta, para apresentação do resultado final].
Todos esses números e matrizes podem ser exibidos juntamente com os resultados das pesquisas, utilizando-se um modo de debug. Isso tem sido muito útil para aprimorar o sistema de ranking.
 
4.5.2. Feedback
A função de ranking tem muitos parâmetros, como os pesos-de-tipos e os pesos-tipo-proximidade. Estipular os melhores valores para esses parâmetros requer um pouco de magia negra. Para superar essa deficiência, nós nos baseamos em feedback dos usuários. Alguns usuários podem manifestar suas opiniões sobre os resultados que lhes são apresentados; essas opiniões são armazenadas. Quando qualquer modificação é introduzida no rankeamento, podemos comparar os resultados através da análise das opiniões dos usuários. Embora esteja longe da perfeição, esse método nos dá alguma idéia de como os usuários estão vendo as mudanças que introduzimos.