Grupo 1

The Google Cluster Architecture

Frederico Paiva Quintao fred@dcc.ufmg.br

Anisio Mendes Lacerda anisio@dcc.ufmg.br

Vanessa Cristina Sabino vsabino@dcc.ufmg.br

:cursos:arquitetura:2007-1:grupo1:ArtigoGrupo1.pdf

Autores: Barroso, L.A.; Dean, J.; Holzle, U.

Publicado em: Micro, IEEE, Volume 23, Issue 2, March-April 2003 Pages: 22-28

Neste artigo, escrito por três engenheiros do Google, é apresentada a arquitetura de hardware usada pela empresa para atender às requisições da máquina de busca Google, que chega a processar milhares de buscas por segundo, em que cada uma lê centenas de megabytes de dados e consome bilhões de ciclos de CPU.

São discutidos os principais fatores que influenciam o design da arquitetura do cluster Google, que são eficiência de energia e razão preço/performance. Em conseqüência desta ser uma aplicação orientada a throughput e facilmente paralelizável, o que significa que a performance máxima do processador é menos importante, são utilizados mais de 15000 PCs, ao invés de um menor número de servidores de alta performance mais caros. O controle da tolerância a falhas é realizado por software ao invés de hardware. Ou seja, eles constroem uma infraestrutura de computação confiável utilizando clusters de PCs de baixa confiabilidade e software para replicar os serviços em diferentes máquinas e automaticamente detectar e tratar as falhas.

É explicado em alto nível todo o processo do funcionamento da máquina de busca, desde o momento em que o usuário submete sua requisição até o retorno do resultado, que além da lista de documentos ordenados por relevância pode incluir sugestões de ortografia e anúncios. A cada etapa, ressalta algumas decisões de arquitetura, tais como um sistema de balanceamento de carga baseado em DNS para escolher qual cluster irá atender à requisição e divisão do índice para permitir maior paralelização. Esta paralelização é um dos aspectos mais importantes, pois reduz a latência média da resposta através da divisão da computação em diversas CPUs e discos, resultando em um speedup praticamente linear.

São fornecidos detalhes bastante específicos sobre as configurações dos computadores utilizados e custos associados, porém os dados apresentados neste artigo provavelmente já estão ultrapassados. É mencionado que em geral os servidores não duram mais do que dois ou três anos, pois é dificil fazer a distribuição de carga em clusters que contém máquinas com muita diferença de performance. O critério de seleção das máquinas é o cost per query, medido como a soma do custo de capital (incluindo depreciação) e custo de operação (hospedagem, administração de sistema e reparos) dividido pela performance.

Uma seção do artigo é dedicada inteiramente à questão da energia, que é um dos grandes desafios. É necessário conseguir economizar energia, porém isso deve ser balanceado para não impactar a performance e nem causar um grande aumento de custo das máquinas.

Por fim, são explicadas algumas outras considerações sobre o hardware utilizando como base os servidores de índice. Vários assuntos estudados durante o curso são vistos aqui, tais como CPI, IPC, branch prediction, ILP, hierarquia de memória, localidade temporal e espacial, etc.

Este artigo servirá como a principal fonte para o nosso seminário, pois é bastante informativo e coeso. Seu único problema é a possível desatualização dos dados.

Autores: Badue, C.S.; Baeza-Yates, R.; Ribeiro-Neto, B.; Ziviani, A.; Ziviani, N.

Publicado em: 15th ACM Conference on Information and Knowledge Management (CIKM06), Arlington, US, November 2006 Pages: 842-843

Utilizando dados reais para modelar a carga de uma máquina de buscas a partir de um ponto de vista do sistema, os autores analisam a distribuição do recebimento de requisições e o tempo de execução por requisição. Os resultados obtidos contrastam com modelos analíticos anteriores.

É realizado um tratamento estatístico dos dados de funcionamento da TodoBR e conclui-se que a distribuição hiperexponencial é a que melhor captura os tempos sendo analisados.

Tais dados caracterizam a carga do sistema e podem ser úteis para um melhor planejamento da paralelização das requisições.

Autor: Barroso, L.A.

Publicado em: ACM Queue, vol. 3, no. 7, September, 2005.

Escrito por um engenheiro do Google, este artigo trata dos custos associados à performance computacional. O TCO total cost ownership de um cluster computacional de larga escala é dividido em quatro componentes principais: preço do hardware, energia (recorrente e investimento inicial do data center), custos operacionais recorrentes do data center, e custo da infraestrutura de hardware.

No caso do Google, que produz seu próprio software e trabalha com a comunidade open source, os três primeiros items são os mais importantes. São mostrados dados de performance, performance por preço do servidor e performance por watt para três gerações de plataforma de hardware usadas pelo Google, em que observa-se que a questão do consumo de energia é a que teve menor melhora nos últimos anos, sendo potencialmente um grande limitador de performance futura.

A solução apresentada no artigo é o uso de CMP (chip multiprocessing), que atinge uma melhor performance através de paralelismo de threads, possibilidando um menor clock e consequentemente menor consumo de energia. Porém, para beneficiar dessa arquitetura, é necessário que as aplicações estejam preparadas para serem executadas em múltiplos cores.

O autor menciona algumas bibliotecas do Google que auxiliam a programação multithread, afirma que o aumento do número de threads para melhorar a escabilidade têm sido um esforço bem sucedido, e que um sistema de computação distribuído com alta eficiência de custo é essencial para sistemas de larga escala com os do Google.

CMPs podem utilizar melhor os recursos do chip e o sistema de memória, levando a maior performance dentro do mesmo custo.

Dessa forma, ainda que o artigo não afirme que CMPs são utilizandos nos clusters do Google, indica que seu uso é provável.

Autores: Badue, C.S.; Barbosa, R.; Golgher, P.; Ribeiro-Neto, B.; Ziviani, N.

Publicado em: 28th International ACM SIGIR Conference on Researchand Development in Information Retrieval (SIGIR’05), Salvador, Brazil, August 2005, Pages: 577-578

Três questões relacionadas a máquinas de busca são analisadas neste artigo: balanceamento de carga, broke behavior e performance individual dos servidores de índice.

São mostrados os resultados de experimentos realizados com a base de dados do TodoBR, incluindo uma análise de tempo de processamento utilizado em CPU e em disco, em que se observa que o tempo em disco é dominante.

Autores: Badue, C.S.; Baeza-Yates, R.; Ribeiro-Neto, B.; Ziviani, A.; Ziviani, N.

Publicado em: Information Processing Management, Volume 43, Issue 3, 2007, Pages: 592-608

Este artigo aponta que a performance do processamento paralelo em um cluster de servidores de índice é impactada por três fatores: tempo de acesso a disco, tempo de comunicação em rede, e nível de concorrência das queries.

Após uma descrição detalhada do funcionamento dos servidores de índice, o problema do balanceamento de carga é discutido sob diversos aspectos, o principal deles sendo o tempo de acesso a disco, pois o tempo para recuperar a informação em servidores em que os dados necessários já estão no cache é algumas ordens de magnitude mais rápido, causando um desbalanceamento severo. Algumas alternativas de cache são analisadas, comparando o melhor e pior caso.

Porém, não são propostas soluções definitivas para o balanceamento de carga. Fica como trabalho futuro um modelo analítico para avaliar e comparar arquiteturas de busca dentro de diferentes restrições operacionais.