Papers
Large-scale cluster management at Google with Borg
Abhishek Verma, Luis Pedrosa, Madhukar Korupolu, David Oppenheimer, Eric Tune, John Wilkes · EuroSys 2015, 2015
O problema: rodar todo o workload do Google em dezenas de milhares de máquinas
O Borg é o gerenciador de clusters do Google: ele admite, agenda, inicia, reinicia e monitora as aplicações que a empresa executa. O paper o apresenta com três benefícios principais: esconder os detalhes de gerenciamento de recursos e de tratamento de falhas, para que os usuários foquem na aplicação; operar com alta confiabilidade e disponibilidade; e permitir rodar workloads em dezenas de milhares de máquinas de forma eficiente. O workload é heterogêneo e tem duas partes. A primeira são serviços de longa duração que nunca deveriam cair e atendem requisições sensíveis a latência (produtos como Gmail e busca, além de infraestrutura interna como o BigTable). A segunda são jobs batch, que levam de alguns segundos a alguns dias e toleram melhor oscilações de desempenho. Os autores chamam os jobs de maior prioridade de produção (prod) e o restante de não produção (non-prod). Em uma célula representativa, os jobs prod recebem cerca de 70% da CPU alocada e usam cerca de 60% da CPU total. Em memória, recebem cerca de 55% e respondem por cerca de 85% do uso. A diferença entre o que é alocado e o que é de fato usado se torna central mais adiante, na recuperação de recursos.
A visão do usuário: jobs, tasks, allocs, prioridade e quota
O usuário submete trabalho ao Borg na forma de jobs, cada um com uma ou mais tasks que executam o mesmo programa. Cada task roda como um conjunto de processos Linux dentro de um container, e não em máquinas virtuais, porque os autores não queriam pagar o custo da virtualização. Um job roda em uma única célula, que é o conjunto de máquinas gerenciado como uma unidade; a célula mediana tem cerca de 10 mil máquinas. Um alloc é um conjunto reservado de recursos em uma máquina, que continua atribuído esteja ou não em uso e pode agrupar tasks de jobs diferentes. Todo job tem uma prioridade, e uma task de prioridade alta pode obter recursos às custas de uma de prioridade menor, inclusive matando-a (preempção). Para evitar cascatas de preempção, tasks da banda de prioridade de produção não fazem preempção umas nas outras. A quota é expressa como um vetor de recursos por prioridade e por período, e é verificada no admission control: um job sem quota suficiente é rejeitado já na submissão, em vez de ficar esperando. A quota de prioridade mais alta custa mais, e a de prioridade zero é tratada como infinita, o que faz o sistema vender mais do que existe nesse nível.
Arquitetura: Borgmaster replicado, Borglets e o scheduler
Uma célula tem um controlador logicamente centralizado, o Borgmaster, e um agente chamado Borglet em cada máquina. O Borgmaster é logicamente um único processo, mas na prática é replicado cinco vezes. Cada réplica mantém em memória o estado da célula, também gravado em um store distribuído baseado em Paxos. Um master eleito atua como líder do Paxos e como único mutador de estado. A eleição e o failover costumam levar cerca de 10 segundos, podendo chegar a um minuto em células grandes. O Borgmaster consulta cada Borglet a cada poucos segundos (polling), o que dá a ele controle sobre a taxa de comunicação e evita tempestades de recuperação. Se uma máquina deixa de responder a vários polls, ela é marcada como indisponível e suas tasks são reagendadas. Uma propriedade importante é que as tasks em execução continuam rodando mesmo que o Borgmaster inteiro caia. O scheduler é um processo separado: ele varre de forma assíncrona a fila de tasks pendentes, da prioridade mais alta para a mais baixa, e tem duas fases. A checagem de viabilidade encontra máquinas que atendem às restrições e têm recursos disponíveis, e a pontuação (scoring) escolhe uma delas entre as viáveis.
Scheduling em escala: scoring híbrido, caching e randomização relaxada
O Borg usou originalmente uma variante do E-PVM para pontuar máquinas. Na prática, ela espalhava a carga por todas as máquinas, deixando folga para picos, mas fragmentava os recursos e atrapalhava tasks grandes (o que os autores chamam de worst fit). O extremo oposto, o best fit, empacota máquinas o mais justo possível, mas penaliza estimativas erradas de recursos e prejudica aplicações com carga em rajadas. O modelo atual é um híbrido que procura reduzir recursos presos (stranded), isto é, os que não podem ser usados porque outro recurso da máquina já está totalmente alocado. Ele dá cerca de 3 a 5% a mais de eficiência de empacotamento que o best fit. Para escalar a células com dezenas de milhares de máquinas, o paper descreve três técnicas. O score caching guarda as pontuações até que algo relevante mude. As equivalence classes avaliam viabilidade e pontuação uma única vez para um grupo de tasks com requisitos idênticos. A randomização relaxada examina máquinas em ordem aleatória até achar viáveis suficientes, em vez de pontuar todas. O scheduler também foi separado do Borgmaster e trabalha sobre uma cópia em cache do estado, de forma parecida com o controle de concorrência otimista. Segundo os autores, um pass online sobre a fila pendente termina normalmente em menos de meio segundo.
Utilização e trade-offs: compartilhar máquinas e recuperar recursos
Um objetivo central do Borg é usar bem a frota, porque ganhar poucos pontos percentuais de utilização economiza muito dinheiro. Para comparar políticas, os autores usam a compaction de célula: dado um workload, medem quão pequena a célula pode ficar, removendo máquinas até o workload deixar de caber. Com essa métrica, mostram que separar prod e non-prod em células diferentes exigiria 20 a 30% mais máquinas na célula mediana. Isso acontece porque jobs prod costumam reservar mais do que usam, e o Borg reaproveita essa folga para o trabalho non-prod. Em células compartilhadas, 98% das máquinas rodam os dois tipos de task. O mecanismo é a recuperação de recursos: o Borgmaster estima a reserva de cada task a cada poucos segundos, partindo do limite pedido e decaindo devagar em direção ao uso real mais uma margem de segurança. Tasks prod nunca dependem de recursos recuperados; tasks non-prod usam as reservas e, se a estimativa errar e faltarem recursos, são mortas ou limitadas (throttled), nunca as prod. Cerca de 20% do workload roda em recursos recuperados na célula mediana. O paper também mostra o custo de alternativas: arredondar pedidos para potências de 2 exigiria de 30 a 50% mais recursos no caso mediano.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.