Arquitectura de um motor de busca: exemplo do Google

Mestrado em Informática e Sistemas
SEMINÁRIO 1
ARQUITECTURA DE UM MOTOR DE
BUSCA:
EXEMPLO DO GOOGLE
por Vasco Nuno Sousa Simões Pereira
[email protected]
Sumário. Este artigo explica em modos gerais a arquitectura de um dos motores de busca mais populares
actualmente, o Google. Pretende-se mostrar como uma aplicação que lida com um volume de dados gigantesco pode
beneficiar de uma abordagem que envolve computação paralela e de bases de dados distribuídas. No fim são feitas
algumas considerações sobre aplicações desta arquitectura a outros cenários.
Palavras chave. Internet, bases de dados distribuídas, computação paralela, motores de busca
1. Introdução
No início a Internet era um meio de comunicação
acedido por apenas uma comunidade restrita. Com o
aparecimento da WWW (World Wide Web) com base
no protocolo HTTP (Hyper Text Transfer Protocol),
essa comunidade teve um crescimento exponencial,
permitindo o acesso generalizado de uma vasta faixa
de população. Os novos utilizadores não só passaram
a poder aceder a um conjunto de informação de uma
maneira rápida como puderam também participar no
aumento dessa mesma informação criando sites
acerca dos mais variados temas e conteúdos. Isto
gerou uma dinâmica nunca antes vista com milhares
de novos sites a aparecerem num curto espaço de
tempo. Começou então a surgir a questão de como
catalogar esses sites, como fazer para que fossem do
conhecimento do resto da comunidade. As
abordagens tradicionais, como a lista telefónica,
tiveram um êxito limitado pois a dinâmica da Internet
não se compadecia com um meio de divulgação tão
estático. Na data de saída de cada lista já esta estava
completamente desactualizada, com uma grande parte
dos sites a ficar irremediavelmente de fora. Era então
necessária outra forma de catalogar a Internet. Essa
solução foi encontrada com motores de busca,
aplicações que permitiam pesquisas pela Internet com
base em uma ou mais palavras-chave. Neste pequeno
artigo vai-se apresentar a arquitectura de um dos mais
populares motores de busca do momento, o Google.
O artigo não pretende ser exaustivo nem demasiado
profundo, apenas dar a conhecer uma aplicação
prática, de grande relevância, do uso massivo de
computação paralela e de bases de dados distribuídas.
Este trabalho insere-se no mestrado em Informática e
Sistemas do Departamento de Engenharia Informática
da Universidade de Coimbra, e foca dois dos temas
abordados na disciplina de Seminário 1, computação
paralela e bases de dados distribuídas.
2. Solução Google
Criado por dois investigadores da Universidade de
Stanford em 1998, o Google é um dos mais populares
motores de busca da Internet, existindo em várias
línguas e distribuído por vários continentes. Nas suas
bases de dados constam cerca de 6 biliões de itens,
maioritariamente páginas web [1], os quais têm
actualmente cerca de 200 milhões de acessos por dia.
De modo a suportar esta performance foi criado um
cluster de cerca de 15000 servidores Linux de baixo
custo que, num tempo médio próximo do meio
segundo, devolve os resultados pretendidos pelo
utilizador. Na génese da arquitectura do Google um
factor foi essencial: a relação preço/performance [2].
2.1 Enquadramento do problema
Os motores de busca para a Internet são programas
que, dadas determinadas palavras-chave ou
expressões, por um qualquer utilizador, devolvem
uma lista de hiper-ligações para documentos onde
essas palavras existem. De modo a poderem realizar
essa tarefa os motores de busca têm armazenadas na
sua base de dados um vasto conjunto de informação
extraída da Internet, que previamente indexaram e
catalogaram. Para criar essas bases de dados existem
programas auxiliares (webcrawlers ou spiders) que
percorrem constantemente a Internet à procura de
sites novos, os quais são posteriormente tratados e
adicionados às bases de dados. Cada motor de busca
usa um algoritmo específico de indexação das
palavras existentes nos documentos encontrados, de
modo a poder depois devolver resultados por ordem
de relevância.
Cada pedido a um motor de busca gera uma sequência
de operações que necessita de uma grande capacidade
de computação, bem como de um grande número de
acessos a disco. É necessário pesquisar Terabytes de
informação constantes das bases de dados, agregar e
ordenar resultados e, por fim, devolver os dados
Departamento de Engenharia Informática, Universidade de Coimbra
2003/2004
Mestrado em Informática e Sistemas
obtidos ao utilizador. Além disso, tem de se ter em
conta que o número de pedidos de pesquisas, por
segundo, está na ordem dos milhares. Para que o
sistema tenha um tempo de resposta aceitável é então
necessário uma grande velocidade de processamento
e de acesso a disco. Uma das formas de tornar real
este cenário era recorrer a alguns dos mais rápidos
super-computadores do mundo. O uso de supercomputadores tem no entanto vários problemas. O
primeiro é o custo. Além de um elevado custo inicial
há ainda o custo de se usar um sistema proprietário,
onde qualquer alteração ou operação de manutenção
implica ainda mais elevados custos. Outro factor
importante é a escalabilidade. Com o aumento
previsível do número de páginas nos próximos anos,
bem como a indexação de outro tipo de conteúdos
(ex. imagens), existirá uma inevitável diminuição da
performance do sistema, requerendo alterações que se
traduzirão num novo aumento exponencial de custos.
Outro problema ainda é a fiabilidade desse sistema
quando o que se pretende é um serviço contínuo sem
falhas nem períodos de manutenção perceptíveis.
SEMINÁRIO 1
que distribui equitativamente os pedidos pelos vários
servidores. Estes GWS vão ser responsáveis por gerir
a execução da pesquisa do utilizador e por formatar
no fim os resultados em HTML (Hyper Text Markup
Language).
Pesquisa do
utilizador
Escolha do
cluster no DNS
Cluster A
...
GWS 2
Verificador de
sintaxe
O que a Google descobriu foi que as operações
realizadas por um motor de busca eram altamente
paralelizáveis, i.e., várias operações poderiam ser
realizadas em paralelo devido ao facto de não
dependerem umas das outras [2]. Esse foi o factor
chave para a solução que viriam a adoptar. Essa
solução passou pela criação de um cluster (conjunto
de máquinas que trabalham com um mesmo
objectivo, portando-se como uma única) de máquinas
vulgares que, aproveitando a possibilidade de
processamento paralelo, tinham a performance de um
super-computador por uma fracção do custo. Esta
arquitectura trazia ainda mais uma vantagem
essencial, tornava o processo escalável. Em seguida
será apresentada a arquitectura geral e alguns
componentes de um cluster Google.
O inicio de qualquer pesquisa no Google começa pela
introdução de palavras-chave, ou expressões, por um
utilizador, usando um vulgar browser. Após o
utilizador introduzir os termos a pesquisar, o primeiro
passo é saber a qual dos clusters distribuídos por
vários locais do mundo é que o utilizador se vai ligar.
Essa selecção é feita por um balanceador de carga a
nível do DNS (Domain Name Server), o qual devolve
o endereço do cluster mais próximo do utilizador.
Deste modo, é proporcionado um menor trajecto dos
dados entre o utilizador e os servidores Google, ao
mesmo tempo que se distribui a carga por vários
locais do mundo. Em seguida, depois de escolhido o
cluster, o pedido é redireccionado para um servidor
web da Google (Google Web Server - GWS). Esta
operação também é feita por um balanceador de carga
...
GWS 1
2.2. Arquitectura do Google
Pesquisa. O objectivo do Google é responder às
pesquisas dos vários utilizadores. Um esquema
simplificado de todo o processo de pesquisa e
devolução de resultados é apresentado na Figura 1.
Cluster B
Servidor de
publicidade
Servidor de Indíces 1
Servidor de docs 1
Servidor de Indíces 2
Servidor de docs 2
...
...
Servidor de Índices 1
Sub-Índice 1
PC 1
PC 2
Sub-Índice 2
...
PC 1
...
...
Agregar resultados e calcular
relevância dos documentos
Lista de Documentos por ordem
Figura 1 – Esquema simplificado da arquitectura
do Google
Quando a expressão de pesquisa chega ao GWS, e
depois de verificada a sua sintaxe, vai começar a
pesquisa às bases de dados. O primeiro acesso é feito
pelos servidores de índices. Estes servidores acedem
aos índices com base nas palavras-chave pedidas e
retornam identificadores das páginas onde os termos
foram encontrados. Devido ao seu grande tamanho, o
índice é subdividido em várias partes, cada uma tendo
um conjunto específico de máquinas associadas. Cada
máquina destas replica as outras permitindo assim
várias pesquisas simultâneas a essa parte do índice
geral. Para que o trabalho
seja dividido
equitativamente, também aqui é usado um
balanceador de carga. Os resultados finais da pesquisa
Departamento de Engenharia Informática, Universidade de Coimbra
2003/2004
Mestrado em Informática e Sistemas
são então agregados e intersectados de modo a obter
uma lista ordenada por relevância. O critério usado
para calcular a relevância de uma página é
proprietário da Google e é designado por PageRank
[3]. Após saber quais os identificadores dos
documentos, um processo análogo à pesquisa nos
índices é realizado sobre os servidores de
documentos. Pretende-se agora obter o título dos
documentos, o seu URL e a parte do texto onde a
palavra-chave é referida. Para que isto seja possível
os servidores de documentos armazenam várias
cópias da web! Em paralelo, é também feita uma
pesquisa a um servidor de publicidade que determina
se existe algum anúncio relevante tendo como base as
palavras-chave inseridas pelo utilizador. Por fim a
página é devolvida ao utilizador, depois de formatada
em HTML.
População das bases de dados. Devido à grande
dinâmica da Internet as bases de dados têm de ser
actualizadas com bastante regularidade, o que implica
uma constante pesquisa de páginas na Internet. Isso é
feito por vários spiders que, a partir de um URL
(Uniform Resource Locator) inicial percorrem as
várias páginas disponíveis. Essas páginas são depois
indexadas por um programa indexador que faz o
parsing do documento convertendo-o numa lista de
palavras. De tempos a tempos as bases de dados de
índices presentes nos vários milhares de máquinas,
são actualizadas [4].
Paralelismo. Devido ao facto da maioria das
operações poder ser realizada em paralelo, é possível
ter pesquisas diferentes a usar diferentes
processadores e ter uma mesma pesquisa dividida por
vários processadores. Pode-se por exemplo dividir
uma pesquisa nos seu vários termos (palavras-chave)
e usar máquinas diferentes para pesquisar resultados.
No final, após encontrados os resultados parcelares, é
apenas necessária uma operação de agregação dos
resultados que, comparativamente, é bastante mais
rápida. Ao mesmo tempo, não há problemas
relevantes de coerência de dados visto que a grande
maioria de operações são apenas de leitura.
Escalabilidade. A solução apresentada pela Google
apresenta-se bastante escalável. Conforme os índices
e o número de documentos vão crescendo apenas é
necessário juntar à estrutura mais um conjunto de PCs
que pesquisem o novo pedaço do índice ou o novo
conjunto de documentos. Ao mesmo tempo, se o
problema for o tempo médio de resposta, basta
acrescentar máquinas a cada grupo para que cada uma
trate de menos pedidos de cada vez.
Fiabilidade. Uma das grandes vantagens desta
arquitectura é a sua inerente tolerância a falhas, que é
assegurada por software. Não são feitos investimentos
em hardware redundante como várias fontes de
alimentação ou soluções RAID (Redundant Array of
Inexpensive Disks), mas assegura-se por software que
caso uma das máquinas tenha algum problema, outra
tome o seu lugar. Embora esta solução possa implicar
SEMINÁRIO 1
uma perda de performance temporária, manterá
sempre o sistema completamente funcional. Deste
modo, aproveita-se a replicação natural inerente à
arquitectura usada, diminuindo ao mesmo tempo os
custos. Como resultado final, consegue-se obter uma
estrutura fiável a partir de máquinas individualmente
não fiáveis.
Hardware. Na Google grande parte dos
computadores usados são vulgares PCs, correndo
Linux, apenas se distinguindo por terem bastante
capacidade de disco. As máquinas usadas não são
escolhidas em termos de performance máxima mas
sim pela relação performance/custo. A arquitectura é
orientada para uma lógica de alto débito de respostas
do cluster, em detrimento de uma lógica de
performance pura de uma máquina. Todas as
máquinas estão ligadas por uma rede Ethernet a 100
Mbps com as ligações principais entre grupos de
máquinas a chegarem aos 2Gbps. Não são usados
esquemas complexos para redundância visto que esta
é assegurada pela replicação intrínseca à própria
arquitectura.
PageRank. O PageRank é usado pelo Google para
permitir ordenar por relevância os resultados de uma
pesquisa. O algoritmo usado algoritmo interpreta “um
link de uma Página A para a Página B como um voto
da Página A para a Página B”[5], avaliando a
importância de uma página pelos votos que ela
recebe.[3][6]
3. Conclusões
A solução apresentada pela Google, idealizada para o
universo específico dos motores de busca, permite
obter escalabilidade, fiabilidade e um elevado
desempenho, tendo como base um cluster de
máquinas comuns. No entanto, esta solução só é
possível devido ao facto do problema dos motores de
busca ter algumas propriedades especiais. Entre estas
propriedades podemos destacar o facto de a maior
parte das operações serem de leitura e de poderem
ocorrer em paralelo. Em cenários que impliquem uma
constante actualização ou inserção de dados, o
software de controle e os processos de replicação dos
dados pelas várias máquinas, teriam de ser bastante
mais complexos. Apesar disso, há uma série de
aplicações que podem beneficiar desta abordagem,
como é o caso de servidores web que guardem
grandes quantidades de informação e em que as
escritas não sejam frequentes. Também repositórios
de informação como bases de dados de artigos
científicos, catálogos on-line de equipamentos,
bibliotecas digitais on-line, podem beneficiar desta
abordagem. Outras aplicações que não partilhem das
características enunciadas podem beneficiar de
soluções mistas. Para isso será necessário criar uma
nova arquitectura, complementada com um software
de gestão que permita a manutenção da coerência dos
dados
dentro
do
cluster,
sem
diminuir
significativamente a performance.
Departamento de Engenharia Informática, Universidade de Coimbra
2003/2004
Mestrado em Informática e Sistemas
SEMINÁRIO 1
Referências
1.
Google Press Release (2004), Google Achieves
Search Milestone With Immediate Access To
More Than 6 Billion Items,
http://www.google.com/intl/pt/press/pressrel/6bil
lion.html
2.
Barroso, L., Dean, J., Hölzle, U. (2003) Web
Search For a Planet: The Google Cluster
Architecture, IEEE Micro, March-April 2003, pp.
22-28
http://www.computer.org/micro/mi2003/m2022.p
df
3.
Brin, S., Page L. (1998) The Anatomy of a LargeScale Hypertextual Web Search Engine, Proc.
Seventh World Wide Web Conference
http://wwwdb.stanford.edu/pub/papers/google.pdf
4.
Sobek, M. Google Dance - The Index Update of
the Google Search Engine
http://dance.efactory.de/
5.
Google Inc. Technology Overview
http://www.google.com/press/overview_tech.htm
l
6.
Rogers, I. (2002) The Google Pagerank
Algorithm and How it Works,
http://www.iprcom.com/papers/pagerank/Pageran
k Explained Correctly with Examples.htm
Departamento de Engenharia Informática, Universidade de Coimbra
2003/2004
Mestrado em Informática e Sistemas
SEMINÁRIO 1
Ficha de Caracterização de Trabalho
Título: Arquitectura de um motor de busca: exemplo do Google
Resumo: Este artigo explica em modos gerais a arquitectura de um dos motores de busca mais
populares actualmente, o Google. Pretende-se mostrar como uma aplicação que lida com um
volume de dados gigantesco pode beneficiar de uma abordagem que envolve computação
paralela e de bases de dados distribuídas. No fim são feitas algumas considerações sobre
aplicações desta arquitectura a outros cenários.
URL: www.dei.uc.pt/~vasco/portfolio/Google_v1.pdf
Data: 19-Fev-2004
Esforço:
Motivação: Conhecer o funcionamento de uma aplicação que trabalha com um volume de
dados gigantesco e que, através de um cluster constituído por PCs normais consegue alcançar
performances muito elevadas.
Aprendizagem: Clusters, computação paralela, bases de dados distribuídas
Conteúdos:
Processos: (que procedimentos e comportamentos aprendeu)
Futuro:
Departamento de Engenharia Informática, Universidade de Coimbra
2003/2004