Google Borg: o ancestral do Kubernetes

01 · CONTEXTO

O que o Borg resolve

O Borg é o gerenciador de clusters do Google. Segundo o paper, ele admite, agenda, inicia, reinicia e monitora a gama completa de aplicações que a empresa executa. O texto lista três benefícios: esconder os detalhes de gestão de recursos e de tratamento de falhas, operar com confiabilidade e disponibilidade muito altas e permitir rodar cargas em dezenas de milhares de máquinas.

A carga é heterogênea. De um lado há serviços de longa duração que, em princípio, nunca devem cair e atendem pedidos curtos sensíveis à latência. De outro há jobs batch, que levam de poucos segundos a alguns dias e são muito menos sensíveis a flutuações de curto prazo. O Borg precisa tratar bem todos esses casos.

Quem usa o Borg envia jobs, e cada job tem uma ou mais tasks que rodam o mesmo programa. Cada job roda em uma única célula, um conjunto de máquinas gerenciado como unidade. Um cluster costuma hospedar uma célula grande e, às vezes, algumas células menores de teste ou uso especial; a célula mediana tem cerca de dez mil máquinas, excluídas as de teste.

02 · ARQUITETURA DA CÉLULA

Borgmaster, Borglets e um armazenamento Paxos

Uma célula tem máquinas, um controlador logicamente centralizado, o Borgmaster, e um agente em cada máquina, o Borglet. O Borgmaster de cada célula é formado por dois processos: o principal e um scheduler separado.

O Borgmaster é logicamente um processo único, mas é replicado cinco vezes. O estado da célula também é gravado num armazenamento distribuído baseado em Paxos. Um único mestre eleito por célula é ao mesmo tempo o líder Paxos e quem muta o estado. Eleger um novo mestre e fazer o failover leva tipicamente cerca de 10 s, podendo chegar a um minuto numa célula grande, porque parte do estado em memória precisa ser reconstruída.

O Borglet inicia e para tasks, reinicia as que falham, gerencia recursos locais e reporta o estado da máquina. É o Borgmaster que consulta cada Borglet a cada poucos segundos. Esse desenho dá ao Borgmaster controle sobre a taxa de comunicação, dispensa um mecanismo explícito de controle de fluxo e evita tempestades de recuperação.

1. O usuário opera o job por RPC; o caso mais comum é uma ferramenta de linha de comando.

2. O mestre eleito registra o job de forma persistente no armazenamento Paxos e acrescenta as tasks à fila de pendentes.

3. O Borgmaster é replicado e o estado fica no armazenamento Paxos; só o mestre eleito, que é o líder Paxos, muta o estado.

4. O scheduler, num processo separado, varre a fila de forma assíncrona e atribui tasks a máquinas.

5. Os Borglets iniciam e param as tasks e reportam o estado da máquina; o Borgmaster os consulta a cada poucos segundos.

03 · AGENDAMENTO

Viabilidade, pontuação e preempção

Quando um job é submetido, o Borgmaster o registra de forma persistente e acrescenta suas tasks à fila de pendentes. O scheduler varre essa fila de forma assíncrona e atribui tasks a máquinas que tenham recursos disponíveis e atendam às restrições do job. A varredura vai da prioridade mais alta para a mais baixa, com rodízio dentro de cada prioridade para garantir justiça entre usuários e evitar que um job grande bloqueie a fila.

O algoritmo tem duas partes: a checagem de viabilidade, que encontra as máquinas onde a task poderia rodar, e a pontuação, que escolhe uma das viáveis.

1. O Borgmaster grava o job e acrescenta suas tasks à fila de pendentes.

2. O scheduler varre a fila da prioridade mais alta para a mais baixa, com rodízio dentro de cada prioridade.

3. A viabilidade filtra as máquinas que cumprem as restrições da task e têm recursos, inclusive os ocupados por tasks de prioridade menor que podem ser despejadas.

4. A pontuação escolhe entre as viáveis, levando em conta, entre outros critérios, poucas e baixas preempções, máquinas que já têm os pacotes da task e o espalhamento por domínios de energia e falha.

5. Se a máquina escolhida não tem espaço, o Borg preempta tasks de prioridade menor, da mais baixa à mais alta, e as devolve à fila de pendentes.

6. O scheduler informa as atribuições ao mestre, que as aplica se estiverem adequadas, e o Borglet da máquina inicia a task.

O modelo atual é um híbrido que tenta reduzir os recursos presos (stranded), aqueles que não podem ser usados porque outro recurso da máquina está totalmente alocado. O paper reporta cerca de 3–5% de ganho de eficiência de empacotamento sobre o best fit nas cargas do Google.

Quando chega mais trabalho do que cabe, o Borg recorre a prioridade e cota. Existem faixas de prioridade que não se sobrepõem, em ordem decrescente: monitoramento, produção, batch e best effort. Cascatas de preempção poderiam ocorrer; para eliminar a maior parte delas, as tasks da faixa de produção não podem preemptar umas às outras. A cota decide quais jobs são admitidos e é checada na admissão, não no agendamento: um job sem cota suficiente é rejeitado imediatamente na submissão.

O tempo de início de uma task é muito variável, com mediana típica de cerca de 25 s, e a instalação de pacotes responde por cerca de 80% do total. Por isso o scheduler prefere máquinas que já têm os pacotes necessários.

04 · ESCALA DO AGENDADOR

Como uma célula grande continua rápida

Um único Borgmaster gerencia muitos milhares de máquinas, e várias células têm taxas de chegada acima de 10 000 tasks por minuto. As primeiras versões tinham um laço síncrono simples que aceitava pedidos, agendava tasks e falava com os Borglets. Para escalar células maiores, o scheduler foi separado em outro processo, que opera em paralelo com as demais funções replicadas do Borgmaster.

Uma réplica do scheduler opera sobre uma cópia em cache do estado da célula. O mestre aceita as atribuições a menos que sejam inadequadas, por exemplo por terem partido de estado desatualizado, e nesse caso elas são reconsideradas na passada seguinte. O paper compara a ideia ao controle de concorrência otimista do Omega.

Os autores medem o efeito do conjunto: agendar toda a carga de uma célula do zero levou algumas centenas de segundos, mas não terminou em mais de 3 dias com as técnicas desligadas. Em operação normal, uma passada online sobre a fila de pendentes termina em menos de meio segundo.

05 · FALHAS E DISPONIBILIDADE

Falhas são a norma

O paper parte de que falhas são a norma em sistemas de grande escala. As aplicações devem tratá-las com replicação, estado persistente em sistema de arquivos distribuído e checkpoints, e o Borg ainda tenta reduzir o impacto: reagenda automaticamente as tasks despejadas, espalha as tasks de um job por domínios de falha como máquinas, racks e domínios de energia, e usa representações declarativas de estado desejado com operações idempotentes, de modo que um cliente que falhou possa reenviar sem dano os pedidos esquecidos.

1. Um Borglet deixa de responder a várias consultas do Borgmaster.

2. A máquina é marcada como inativa e as tasks que rodavam nela são reagendadas em outras máquinas.

3. Se a comunicação volta, o Borgmaster manda o Borglet matar as tasks já reagendadas, para evitar duplicatas.

4. Em outro cenário, se todas as réplicas do Borgmaster falham, os Borglets seguem operando e as tasks em execução continuam de pé.

5. Mesmo assim manter o mestre no ar importa: com ele fora, não se submetem jobs novos nem se atualizam os existentes, e tasks de máquinas com falha não são reagendadas.

O Borgmaster atinge 99,99% de disponibilidade na prática combinando replicação, controle de admissão contra sobrecarga e implantação com ferramentas simples e de baixo nível para reduzir dependências externas. Cada célula é independente das outras para diminuir erros correlados de operador e a propagação de falhas, e o paper diz que são esses objetivos, e não limites de escalabilidade, o principal argumento contra células maiores.

Um detalhe de projeto: o Borg limita a taxa com que busca novos lugares para as tasks de máquinas inacessíveis, porque não consegue distinguir uma falha de máquinas em larga escala de uma partição de rede.

Criar e posicionar tasks não basta, pois clientes precisam achá-las mesmo depois de realocadas. O Borg cria um nome BNS estável por task, com nome da célula, do job e número da task, e grava o host e a porta da task num arquivo consistente e altamente disponível no Chubby, que o sistema de RPC usa para achar o endpoint. Ele também grava o tamanho do job e a saúde das tasks sempre que mudam, para que os balanceadores vejam para onde rotear.

1. O Borg grava o host e a porta da task num arquivo do Chubby, identificado pelo nome BNS estável da task.

2. Sempre que o tamanho do job ou a saúde das tasks mudam, o Borg atualiza essa informação no Chubby.

3. O balanceador usa essa informação para saber para onde rotear os pedidos.

4. O cliente consegue achar a task na máquina onde ela está agora, mesmo depois de realocada.

Cada task também publica a própria saúde: quase toda task tem um servidor HTTP embutido que publica informações de saúde, e o Borg monitora a URL de health-check e reinicia as tasks que não respondem rápido ou devolvem erro HTTP.

06 · UTILIZAÇÃO

Compartilhar máquinas e reaproveitar reservas

Um dos objetivos centrais do Borg é usar bem a frota de máquinas: aumentar a utilização em poucos pontos percentuais pode economizar milhões de dólares.

Quase todas as máquinas rodam ao mesmo tempo tasks prod e non-prod: 98% das máquinas em células compartilhadas e 83% no conjunto todo. Segregar as duas cargas em células separadas exigiria 20–30% mais máquinas na célula mediana, porque os jobs prod reservam recursos para picos raros e não os usam na maior parte do tempo, enquanto o Borg reclama o que não é usado.

A reclamação de recursos funciona assim: o Borg estima quanto uma task vai usar e reclama o resto para trabalho que tolera recursos de menor qualidade, como batch. O scheduler usa os limites no cálculo de viabilidade das tasks prod, então elas nunca dependem de recursos reclamados nem ficam expostas à sobrecarga; para as non-prod, usa as reservas das tasks existentes. Cerca de 20% da carga roda em recursos reclamados na célula mediana.

Quando falta recurso numa máquina, a reação depende do tipo de recurso. Recursos compressíveis, como ciclos de CPU e banda de disco, podem ser reduzidos sem matar a task; os não compressíveis, como memória e espaço em disco, em geral não. Sem recursos não compressíveis, o Borglet encerra tasks da prioridade mais baixa à mais alta; sem recursos compressíveis, ele estrangula o uso, favorecendo as tasks sensíveis à latência, e assim absorve picos curtos sem matar tasks.

Os pedidos de recursos são granulares: CPU em milicores, memória e disco em bytes, sem baldes ou slots de tamanho fixo. Arredondar os limites de jobs prod para a próxima potência de dois exigiria 30–50% mais recursos no caso mediano. Já dividir uma célula em células menores exigiria significativamente mais máquinas.

Compartilhar máquinas pede isolamento. Todas as tasks rodam em contêineres de recursos baseados em cgroups do Linux, e um chroot é o principal mecanismo de isolamento de segurança entre tasks na mesma máquina. Tasks sensíveis à latência (LS) de alta prioridade recebem o melhor tratamento e podem deixar tasks batch sem CPU por alguns segundos.

07 · LIÇÕES E O CAMINHO ATÉ O KUBERNETES

O que o Borg ensinou

O paper encerra com lições qualitativas de operar o Borg em produção por mais de uma década e de como elas foram aproveitadas no desenho do Kubernetes. Segundo os autores, praticamente todas as cargas de cluster do Google migraram para o Borg.

Duas outras lições merecem destaque. A primeira é otimizar para usuários avançados em detrimento dos casuais: a especificação BCL lista cerca de 230 parâmetros, e a riqueza da API dificulta a vida do usuário casual e limita sua evolução. A segunda é que a introspecção é vital: o Borg expõe informação de depuração a todos os usuários em vez de escondê-la, porque com milhares de usuários o self-help tem de ser o primeiro passo.