View
699
Download
0
Category
Preview:
Citation preview
Busca na web para um planeta
A Arquitetura de Cluster do Google
Apresentado por:
• Alison Miazaki• Filipe Morgado Simões de Campos• Guilherme Fré• Rafael Barbolo Lopes• Rafael Ivan Garcia
Fonte de Dados
• Dados apresentados com base em um artigo publicado pelo Google em 2003
Web Search for a Planet: The Google Cluster Architecture
Luiz Barroso, Jeffrey Dean, and Urs Hoelzlehttp://research.google.com/archive/googlecluster.html
Resumo
“ Com extensivo uso de paralelização, a busca do Google permite que diferentes consultas sejam executadas em diferentes processadores, dividindo o índice de busca, também permitindo que uma única consulta seja executada por múltiplos processadores.Para lidar com esta carga de trabalho, a arquitetura do Google é implementada com clusters de mais de 15.000 PCs simples com software tolerante a falhas. Essa arquitetura atinge performance superior por uma fração do custo de um sistema com menos servidores de alto padrão, porém mais caros.
”
O Buscador Perfeito“Entende exatamente o que você quis dizer e devolve exatamente o que você queria”
Larry Page
<html><title>Corp. Info - Tech Overview</title> <body><h1>Corporate Information</h1><li><a href=“/home.htm”>Home</a></li><h2>Technology Overview</h2><p>We stand alone in our focus on developing the "perfect search engine,
PageRank Análise e classificação do conteúdo HTML
Ciclo de vida de uma consulta
Um ciclo leva cerca de 0,5 segundo
Requisitos de uma consulta
• Processamento de centenas de megabytes• Bilhões de ciclos de CPU• Executar em paralelo com milhares de outras
consultas
Google: Alcançando Alta performance
• Banco de Dados: BigTable• Sistema de Arquivos: Google File System• Arquitetura: Clusters de Multicomputadores
baratos
Clusters deMulticomputadores baratos
Rede local: comunicação por
passagem de mensagens
PMPMPMPM
P MP MP MP M
PM
PM
PM
PM
PM
PM
PM
PM
Memória Processador
Multicomputador
Clusters do Google
• Mais de 15.000 PCs básicos• Software tolerante a falhas de PCs• Custo efetivo total menor que o custo de usar
servidores de alto padrão• Alta eficiência no consumo de energia• Alta razão performance/preço• Máquinas geograficamente distribuídas (evita
falhas localizadas em data centers e diminui Round Trip Time de requisições)
Paralelização
• Diferentes consultas podem rodar em diferentes processadores
• Uma única consulta pode utilizar diversos processadores
• Desta forma, a performance máxima de um processador é menos relevante do que seu performance/preço (parecido com pipeline: importante é a vazão e não o tempo para executar uma única consulta)
O que é melhor para o Google?
1. Um processador de 3GHz que custa R$ 4.0002. Um processador de 1GHz que custa R$ 100
O que é melhor para o Google?
1. Razão performance/preço = 0,75MHz/R$
2. Razão performance/preço = 10MHz/R$
Princípios da Arquitetura
Princípios da Arquitetura
1.Confiabilidade no software– Evita utilização de fontes de energia redundantes,
discos redundantes (RAID) e componentes de alta qualidade
– Os clusters possuem muitas máquinas simples e baratas
– Máquinas podem falhar– A confiabilidade está focada no software
Princípios da Arquitetura
2.Replicação– Aumenta a vazão e disponibilidade dos serviços– Máquinas diferentes podem disponibilizar os
mesmos serviços– Como a quantidade de máquinas para fornecer
capacidade de processamento de dados é grande, o custo da replicação de serviços é baixo
Princípios da Arquitetura
3.Preço/performance é melhor que medidas de performance em pico– A escolha de qual máquina comprar depende da
performance que será obtida por unidade de preço
– CPUs que fornecem o melhor processamento de pico (clock nominal) são menos significantes se seu preço for alto.
Princípios da Arquitetura
4.Uso de PCs básicos– Aumenta o poder computacional para cada
consulta que é feita– Permite usar algoritmos de busca mais custosos– Permite aumentar o índice de documentos
buscados– Durabilidade de um PC básico é de 2 ou 3 anos
Tratamento de consultas
Servidor Web do Google
Correção ortográfica
Servidor de Anúncios
Servidores de ÍndiceServidores de
ÍndiceServidores de ÍndiceServidores de
Índice
Servidores de DocumentosServidores de
DocumentosServidores de DocumentosServidores de
DocumentosServidores de Documentos
Tratamento de consultas
Correção ortográfica
Servidor de Anúncios
Servidores de ÍndiceServidores de
ÍndiceServidores de ÍndiceServidores de
Índice
Servidores de DocumentosServidores de
DocumentosServidores de DocumentosServidores de
DocumentosServidores de Documentos
Servidor Web do Google
Recebe termos da consulta
Tratamento de consultas
Servidor Web do Google
Servidor de Anúncios
Servidores de ÍndiceServidores de
ÍndiceServidores de ÍndiceServidores de
Índice
Servidores de DocumentosServidores de
DocumentosServidores de DocumentosServidores de
DocumentosServidores de Documentos
Correção ortográfica
Você quis dizer:
Tratamento de consultas
Servidor Web do Google
Correção ortográfica
Servidores de ÍndiceServidores de
ÍndiceServidores de ÍndiceServidores de
Índice
Servidores de DocumentosServidores de
DocumentosServidores de DocumentosServidores de
DocumentosServidores de Documentos
Servidor de Anúncios
AdSense e links patrocinados
Tratamento de consultas
Servidor Web do Google
Correção ortográfica
Servidor de Anúncios
Servidores de DocumentosServidores de
DocumentosServidores de DocumentosServidores de
DocumentosServidores de Documentos
Servidores de ÍndiceServidores de
ÍndiceServidores de ÍndiceServidores de
Índice
Índice invertido:palavra1: doc1 - doc12 - doc32 - doc43 - doc100palavra2: doc12 - doc132 doc181
(cada máquina possui um pedaço do índice)
Tratamento de consultas
Servidor Web do Google
Correção ortográfica
Servidor de Anúncios
Servidores de ÍndiceServidores de
ÍndiceServidores de ÍndiceServidores de
Índice
Servidores de DocumentosServidores de
DocumentosServidores de DocumentosServidores de
DocumentosServidores de Documentos
Formatação do resultado:Extrai título e pequena descrição contendo termos da consulta de cada documento
(cada máquina possui um conjunto de documentos)
Tratamento de consultas
Correção ortográfica
Servidor de Anúncios
Servidores de ÍndiceServidores de
ÍndiceServidores de ÍndiceServidores de
Índice
Servidores de DocumentosServidores de
DocumentosServidores de DocumentosServidores de
DocumentosServidores de Documentos
Servidor Web do Google
Retorna HTML com resultados da busca
Tratamento de consultas
Servidor Web do Google
Correção ortográfica
Servidor de Anúncios
Servidores de ÍndiceServidores de
ÍndiceServidores de ÍndiceServidores de
Índice
Servidores de DocumentosServidores de
DocumentosServidores de DocumentosServidores de
DocumentosServidores de Documentos
Configuração das máquinas• Um rack do google possui cerca de 80 servidores x86 que
possuem componentes equivalentes ao de um PC desktop, mas com disco rígido de grande capacidade
• CPUs: de processadores com apenas um núcleo como o Intel-Celeron 533 MHz a processadores com dois núcleos como o Intel Pentium III 1.4GHz
• Servidores de Índice possuem menos espaço de disco porque possuem carga de trabalho definida por intenso uso de CPU
• Conexões entre servidores de um mesmo rack com switches 100Mbps Ethernet. Cada switch é conectado a um switch principal com link gigabit que faz a conexão entre os racks
Comparação entre máquinasRack do Google
Dados de 2002
•88 servidores dual-CPU Intel Xeon, cada um com:
•2GHz / CPU•2GB RAM•80GB HD
•Total:•176 CPUs de 2-GHz cada•176 GB RAM•7 TB HD
Custo: U$ 278.000
Rack de um servidor de alto padrão
•8 servidores Intel Xeon, cada um com:
•2GHz•8GB RAM•1TB HD
•Total:•8 CPUs de 2-GHz cada•64 GB RAM•8 TB HD
Custo: U$ 758.000
Servidor de Índice
Servidor de Índice
• Principal atividade: decodificar informações comprimidas no índice invertido e encontrar entradas com documentos que satisfazem a busca.
Servidor de Índice
Medidas de uso de instruções em um Pentium III de 1-GHz dual core:
Característica Valor
Ciclos por Instrução (CPI) 1.1
Falha de previsão de desvio 5.0 %
Falha de acesso a blocos de instrução no cache L1 0.4%
Falha de acesso a blocos de dados no cache L1 0.7%
Falha de acesso a blocos no cache L2 0.3%
Falha de acesso a blocos de instrução no TLB 0.04%
Falha de acesso a blocos de dados no TLB 0.7%
Análise: Sistema de Memória
• Ocorrem poucas falhas para acessar instruções porque o servidor de índice possui um pequeno código em loop.
• O acesso a blocos de dados não se aproveita de localidade temporal devido à imprevisibilidade de acesso a blocos de dados do índice, porém se aproveita de localidade espacial porque acessa conjuntos de blocos próximos para decodificar o índice e realizar buscas.
Arquitetura do GoogleClusters de PCs básicos
Quando usar
• Serviços que requerem milhares de servidores e petabytes de armazenamento
• Foco em performance/preço• Servidores que não guardam estado (permitindo
replicação)• Intenso uso computacional• Volume de requisições a serem atendidas muito
alto• Aplicações que exigem paralelismo
Referências
• Google – Corporate Information – Technology Overview:– http://www.google.com/corporate/tech.html
• Google Research Publication: Web Search for a Planet:– http://research.google.com/archive/googlecluster.html
Obrigado
Recommended