Papers
Web Search for a Planet: The Google Cluster Architecture
Luiz André Barroso, Jeffrey Dean, Urs Hölzle · IEEE Micro, vol. 23, no. 2 (March-April 2003), 2003
O problema: busca na web consome computação demais por requisição
Poucos serviços web exigem tanta computação por requisição quanto um mecanismo de busca. Segundo os autores, em média uma única consulta ao Google lê centenas de megabytes de dados e consome dezenas de bilhões de ciclos de CPU. Sustentar um pico de milhares de consultas por segundo pede, portanto, uma infraestrutura comparável em tamanho às maiores instalações de supercomputação. A resposta do artigo é um cluster com mais de 15.000 PCs de classe comum (commodity), rodando software tolerante a falhas. A tese central é que essa combinação entrega desempenho superior por uma fração do custo de um sistema feito com menos servidores, porém mais caros e de ponta. Os autores destacam dois fatores que guiam todo o projeto: eficiência energética e relação preço/desempenho. A energia importa porque, na escala do Google, consumo e refrigeração viram fatores operacionais significativos e pressionam os limites de densidade de potência dos data centers disponíveis. O artigo também observa que a aplicação se presta bem à paralelização: consultas diferentes podem rodar em processadores diferentes e, como o índice é particionado, uma única consulta também pode usar vários processadores. Por isso, o desempenho de pico de cada processador importa menos do que o seu preço/desempenho.
Servindo uma consulta: DNS, GWS, servidores de índice e de documentos
O artigo percorre o caminho de uma consulta. O navegador primeiro resolve o nome via DNS. O serviço é formado por vários clusters distribuídos pelo mundo, cada um com alguns milhares de máquinas, o que protege contra falhas catastróficas de um data center, como terremotos ou quedas de energia em larga escala. Um balanceamento de carga baseado em DNS escolhe o cluster levando em conta a proximidade geográfica do usuário e a capacidade disponível em cada local, minimizando o tempo de ida e volta. Escolhido o cluster, todo o processamento da consulta é local a ele. Um balanceador de carga em hardware monitora o conjunto de servidores web do Google (GWS) e distribui as requisições entre eles. O GWS que recebe a consulta coordena a execução e monta a resposta HTML. A execução tem duas fases. Na primeira, os servidores de índice consultam um índice invertido, que mapeia cada palavra da consulta a uma lista de documentos que a contêm (a hit list). Eles intersectam as listas das palavras e calculam uma pontuação de relevância por documento, que define a ordem dos resultados. O resultado dessa fase é uma lista ordenada de identificadores de documento (docids). Na segunda fase, os servidores de documentos (docservers) pegam os docids e buscam em disco cada documento para extrair título, URL e um trecho com a palavra-chave em contexto. Em paralelo, o GWS aciona tarefas auxiliares, como o corretor ortográfico e o servidor de anúncios.
Index shards e replicação: paralelismo por consulta
O desafio da busca está no volume de dados. Os autores indicam que os documentos brutos somam várias dezenas de terabytes sem compressão, e que o índice invertido derivado deles ocupa, ele próprio, muitos terabytes. A saída é dividir o índice em pedaços chamados index shards, cada um contendo um subconjunto escolhido aleatoriamente dos documentos do índice completo. Para cada shard existe um pool de máquinas que atende às requisições, e o cluster de índice contém um pool por shard. Um balanceador de carga intermediário escolhe uma máquina dentro de cada pool, de modo que cada consulta vai a uma máquina (ou a um subconjunto delas) de cada shard. O mesmo esquema vale para os servidores de documentos: documentos distribuídos aleatoriamente em shards menores, várias réplicas por shard e roteamento por um balanceador. A consequência de projeto é que adicionar máquinas a cada pool aumenta a capacidade de atendimento, enquanto adicionar shards acomoda o crescimento do índice. Como os shards não precisam se comunicar entre si, o ganho de velocidade ao paralelizar a busca é quase linear e a latência média da consulta cai, pois o trabalho total é dividido entre mais CPUs e discos. Por isso a velocidade da CPU individual não influencia diretamente o desempenho global: dá para aumentar o número de shards para compensar CPUs mais lentas.
Confiabilidade em software e replicação para capacidade e tolerância a falhas
Os autores defendem que o melhor equilíbrio preço/desempenho vem de montar uma infraestrutura confiável a partir de PCs comuns e não confiáveis, entregando a confiabilidade no nível do software: replicando serviços em muitas máquinas e detectando e tratando falhas automaticamente. O artigo resume quatro princípios. Primeiro, confiabilidade em software: abrir mão de recursos de hardware tolerante a falhas, como fontes redundantes, arranjos de discos baratos (RAID) e componentes de alta qualidade, e tolerar falhas no software. Segundo, usar replicação para vazão e disponibilidade: como o serviço já é replicado para obter capacidade, essa tolerância a falhas vem de graça. Terceiro, preço/desempenho vence desempenho de pico: compra-se a geração de CPU com melhor desempenho por unidade de preço. Quarto, PCs comuns reduzem o custo da computação, permitindo gastar mais recursos por consulta, usar técnicas de ranqueamento mais caras ou pesquisar um índice maior. Na prática, se a réplica de um shard cai, o balanceador evita usá-la, e o sistema de gerenciamento do cluster tenta reavivá-la ou substituí-la. Durante a indisponibilidade a capacidade cai na proporção da fatia que a máquina representava, mas o serviço continua sem interrupção e todas as partes do índice seguem disponíveis. Também ajuda que a maior parte dos acessos seja somente leitura, com atualizações pouco frequentes e feitas desviando consultas da réplica, o que evita muitos problemas de consistência de um banco de dados de propósito geral.
Preço/desempenho com peças comuns: o exemplo dos racks
Os racks do Google têm de 40 a 80 servidores x86 montados nos dois lados de um rack feito sob medida. Os servidores se parecem com PCs desktop de faixa média, exceto pela escolha de discos grandes. Cada servidor tem um ou mais discos IDE de 80 GB, e o artigo cita um leque de gerações de CPU em uso, de Celeron de 533 MHz com um processador a Pentium III dual de 1,4 GHz. O critério final de seleção é o custo por consulta: despesas de capital (com depreciação) mais custos operacionais, divididos pelo desempenho. O artigo argumenta que um servidor dificilmente dura mais que dois ou três anos, então o custo do equipamento pesa muito. Para ilustrar, compara um rack de PCs de cerca de US$ 278.000 (176 CPUs Xeon de 2 GHz, 176 GB de RAM e 7 TB de disco) com um servidor multiprocessado típico de cerca de US$ 758.000 (8 CPUs Xeon de 2 GHz, 64 GB de RAM e 8 TB de disco). O multiprocessador custa cerca de três vezes mais, com 22 vezes menos CPUs e três vezes menos RAM. A diferença vem em grande parte da interconexão e da confiabilidade de máquinas de ponta, atributos de que a arquitetura redundante do Google não depende. Operar milhares de PCs traz custos de administração e reparo, mas eles são administráveis porque a aplicação é bastante homogênea, com configurações idênticas, ferramentas de instalação em grupo e reparos em lote.
Densidade de potência, limites e legado
O artigo dedica uma seção ao problema da energia. Um servidor de faixa média com dois Pentium III de 1,4 GHz consome cerca de 90 W de corrente contínua sob carga: aproximadamente 55 W para as CPUs, 10 W para um disco e 25 W para DRAM e placa-mãe. Com eficiência típica de fonte de cerca de 75%, isso vira cerca de 120 W de corrente alternada por servidor e aproximadamente 10 kW por rack. Um rack cabe em cerca de 25 pés quadrados, o que dá uma densidade de cerca de 400 W por pé quadrado, podendo passar de 700 W/pé² com processadores mais potentes. Já os data centers comerciais típicos ficam entre 70 e 150 W/pé², bem abaixo disso. Assim, até clusters de PCs simples precisam de refrigeração especial ou de espaço extra, e empacotar ainda mais servidores por rack tem uso prático limitado. Servidores de baixo consumo são atraentes, mas o que conta é watts por unidade de desempenho, e eles não podem custar muito mais: os autores estimam refrigeração e energia em cerca de US$ 1.500 por mês por rack, contra US$ 7.700 de depreciação. No fim, reconhecem limites do paralelismo massivo, como a capacidade de refrigeração dos data centers comerciais e o encaixe imperfeito das CPUs da época em cargas voltadas à vazão. Ainda assim, o modelo vale para outras aplicações com servidores sem estado privado e paralelismo no nível da requisição, como servidores web de alto volume.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.