Balanceamento de carga no datacenter

Escrito por Alejandro Forero Cuervo

Editado por Sarah Chavis

Este capítulo se concentra no balanceamento de carga no datacenter. Especificamente, ele discute algoritmos para distribuição de trabalho em um determinado datacenter para um fluxo de queries. Cobrimos as políticas em nível de aplicação para rotear solicitações em servidores individuais que possam processá-las. Princípios de rede em nível inferior (por exemplo, switches, roteamento de pacotes) e seleção de datacenter estão fora do escopo deste capítulo.

Suponha que haja um fluxo de queries chegando ao datacenter – elas podem vir do próprio datacenter, datacenters remotos ou uma mistura de ambos – a uma taxa que não exceda os recursos que o datacenter possui para processá-las (ou apenas excede por períodos de tempo muito curtos). Suponha também que existam serviços dentro do datacenter, em relação aos quais essas queries operam. Esses serviços são implementados como muitos processos de servidor homogêneos e intercambiáveis, executados principalmente em máquinas diferentes. Os serviços menores normalmente têm pelo menos três desses processos (usar menos processos significa perder 50% ou mais de sua capacidade se você perder uma única máquina) e o maior pode ter mais de 10.000 processos (dependendo do tamanho do datacenter). No caso típico, os serviços são compostos por entre 100 e 1.000 processos. Chamamos esses processos de tarefas de backend (ou apenas backends). Outras tarefas, conhecidas como tarefas de cliente, mantêm conexões com as tarefas de backend. Para cada query recebida, uma tarefa de cliente deve decidir qual tarefa de backend deve lidar com a query. Os clientes se comunicam com os backends usando um protocolo implementado em cima de uma combinação de TCP com UDP.

Devemos observar que os datacenters do Google abrigam um conjunto muito diversificado de serviços que implementam diferentes combinações das políticas discutidas neste capítulo. Nosso exemplo de trabalho, conforme descrito, não se encaixa em nenhum serviço diretamente. É um cenário generalizado que nos permite discutir as várias técnicas que consideramos úteis para vários serviços. Algumas dessas técnicas podem ser mais (ou menos) aplicáveis a casos de uso específicos, mas essas técnicas foram projetadas e implementadas por vários engenheiros do Google ao longo de muitos anos.

Essas técnicas são aplicadas em muitas partes da nossa stack. Por exemplo, a maioria das solicitações HTTP externas chega ao GFE (Google Frontend), nosso sistema de proxy reverso HTTP. O GFE usa esses algoritmos, juntamente com os algoritmos descritos no Capítulo 19, para rotear as solicitações de payloads e metadados aos processos individuais que executam as aplicações que podem processar essas informações. Isso se baseia em uma configuração que mapeia vários padrões de URL para aplicações individuais sob o controle de diferentes equipes. Para produzir os payloads de resposta (que eles retornam ao GFE, para serem devolvidos aos navegadores), essas aplicações geralmente usam esses mesmos algoritmos para se comunicar com a infraestrutura ou serviços complementares dos quais dependem. Às vezes, a stack de dependências pode ficar relativamente profunda, onde uma única solicitação HTTP de entrada pode acionar uma longa cadeia transitiva de solicitações dependentes para vários sistemas, potencialmente com alta distribuição em vários pontos.

O caso ideal

Em um caso ideal, a carga de um determinado serviço é distribuída perfeitamente por todas as suas tarefas de backend e, a qualquer momento, as tarefas de backend menos e mais carregadas consomem exatamente a mesma quantidade de CPU.

Só podemos enviar tráfego para um datacenter até o ponto em que a tarefa mais carregada atinja seu limite de capacidade; isso está representado na figura abaixo para dois cenários no mesmo intervalo de tempo. Durante esse período, o algoritmo de balanceamento de carga entre datacenters deve evitar o envio de tráfego adicional para o datacenter, para não haver o risco de sobrecarregar algumas tarefas.

Conforme mostrado no gráfico à esquerda na figura abaixo, uma quantidade significativa de capacidade é desperdiçada: a capacidade ociosa de cada tarefa, exceto a tarefa mais carregada.

Mais formalmente, sendo CPU[i] a taxa de CPU consumida pela tarefa i em um determinado ponto de tempo, e supondo que a tarefa 0 seja a tarefa mais carregada; então, no caso de uma grande propagação, estamos desperdiçando a soma das diferenças na CPU de qualquer tarefa para CPU[0]: ou seja, a soma sobre todas as tarefas i de (CPU[0] – CPU[i]) será desperdiçada. Neste caso, “desperdiçada” significa reservada, mas não utilizada.

Este exemplo ilustra como práticas ruins de balanceamento de carga no datacenter limitam artificialmente a disponibilidade de recursos: você pode estar reservando 1.000 CPUs para seu serviço em um determinado datacenter, mas não conseguir usar mais do que, digamos, 700 CPUs.

Identificando tarefas ruins: controle de fluxo e “lame ducks”

Antes de podermos decidir qual tarefa de backend deve receber uma solicitação de cliente, precisamos identificar — e evitar — tarefas insalubres em nosso pool de backends.

Uma abordagem simples para tarefas insalubres: controle de fluxo

Suponha que nossas tarefas de cliente rastreiem o número de solicitações ativas que enviaram em cada conexão para uma tarefa de backend. Quando essa contagem de solicitações ativas atinge um limite configurado, o cliente trata o backend como não íntegro e não envia mais solicitações. Para a maioria dos backends, 100 é um limite razoável; no caso médio, as solicitações tendem a terminar rápido o suficiente para que seja muito raro que o número de solicitações ativas de um determinado cliente atinja esse limite em condições normais de operação. Essa forma (muito básica!) de controle de fluxo também serve como uma forma simplista de balanceamento de carga: se uma determinada tarefa de backend ficar sobrecarregada e as solicitações começarem a se acumular, os clientes evitarão esse backend e a carga de trabalho se espalhará organicamente entre as outras tarefas de backend.

Infelizmente, essa abordagem muito simplista protege apenas as tarefas de backend contra formas muito extremas de sobrecarga e é muito fácil para os backends ficarem sobrecarregados bem antes que esse limite seja atingido. O inverso também é verdadeiro: em alguns casos, os clientes podem atingir esse limite quando seus backends ainda têm muitos recursos disponíveis. Por exemplo, alguns backends podem ter solicitações de longa duração que proíbem respostas rápidas. Vimos casos em que esse limite padrão saiu pela culatra, fazendo com que todas as tarefas de backend se tornassem inacessíveis, com solicitações bloqueadas nos clientes até atingirem o tempo limite e falharem. Aumentar o limite de solicitação ativa pode evitar essa situação, mas não resolve o problema subjacente de saber se uma tarefa é realmente insalubre ou simplesmente lenta para responder.

Uma abordagem robusta para tarefas insalubres: estado “lame duck”

Nota do tradutor: “lame duck” diz respeito a uma tecnologia que deixará de funcionar em breve, ou seja, o estágio seguinte é tornar-se inútil e obsoleta.

Do ponto de vista do cliente, uma determinada tarefa de backend pode estar em qualquer um dos seguintes estados:

Integrada

A tarefa de backend foi inicializada corretamente e está processando solicitações.

Recusando conexões

A tarefa de backend não responde. Isso pode acontecer porque a tarefa está iniciando ou desligando, ou porque o backend está em um estado anormal (embora seja raro um backend parar de escutar em sua porta se não estiver desligando).

Lame duck

A tarefa de backend está escutando em sua porta e pode servir, mas está pedindo explicitamente aos clientes que parem de enviar solicitações.

Quando uma tarefa entra no estado lame duck, ela transmite esse fato para todos os seus clientes ativos. Mas, e os clientes inativos? Com a implementação de RPC do Google, clientes inativos (ou seja, clientes sem conexões TCP ativas) ainda enviam verificações de integridade periódicas do UDP. O resultado é que as informações do lame duck são propagadas rapidamente para todos os clientes – normalmente em 1 ou 2 RTT – independentemente de seu estado atual.

A principal vantagem de permitir que uma tarefa exista em um estado lame duck quase operacional é que ela simplifica o desligamento limpo, o que evita servir erros para todas as solicitações que estavam ativas em tarefas de backend que estão sendo desligadas. Desativar uma tarefa de backend que tenha solicitações ativas sem atender a nenhum erro facilita envios de código, atividades de manutenção ou falhas de máquina que podem exigir a reinicialização de todas as tarefas relacionadas. Esse desligamento seguiria as seguintes etapas gerais:

O agendador de tarefas envia um sinal SIGTERM para a tarefa de backend.
A tarefa de backend entra no estado lame duck e solicita que seus clientes enviem novas solicitações para outras tarefas de backend. Isso é feito através de uma chamada de API na implementação RPC que é explicitamente chamada no SIGTERM.
Qualquer solicitação em andamento iniciada antes de a tarefa de backend entrar no estado lame duck (ou depois de entrar no estado lame duck, mas antes de um cliente detectá-la) é executada normalmente.
À medida que as respostas fluem de volta para os clientes, o número de solicitações ativas no backend diminui gradualmente para zero.
Após um intervalo configurado, a tarefa de backend é encerrada de forma limpa ou o agendador de tarefas a elimina. O intervalo deve ser definido com um valor grande o suficiente para que todas as solicitações típicas tenham tempo suficiente para serem concluídas. Esse valor depende do serviço, mas uma boa regra geral é entre 10s e 150s, dependendo da complexidade do cliente.

Essa estratégia também permite que um cliente estabeleça conexões com tarefas de backend enquanto executa procedimentos de inicialização potencialmente de longa duração (e, portanto, ainda não está pronto para começar a servir). As tarefas de backend poderiam começar a ouvir conexões apenas quando estivessem prontas para servir, mas isso atrasaria a negociação das conexões desnecessariamente. Assim que a tarefa de backend estiver pronta para começar a ser veiculada, ela sinalizará isso explicitamente para os clientes.

Limitando o pool de conexões com subconfigurações

Além do gerenciamento de integridade, outra consideração para o balanceamento de carga é a subconfiguração: limitar o pool de possíveis tarefas de backend com as quais uma tarefa de cliente interage.

Cada cliente em nosso sistema RPC mantém um pool de conexões de longa duração com seus backends que é usado para enviar novas solicitações. Essas conexões geralmente são estabelecidas no início, quando o cliente está iniciando e geralmente permanecem abertas, com solicitações fluindo por elas, até a morte do cliente. Um modelo alternativo seria estabelecer e encerrar uma conexão para cada solicitação, mas esse modelo tem custos significativos de recursos e latência. No caso de uma conexão que permanece inativa por muito tempo, nossa implementação RPC tem uma otimização que alterna a conexão para um modo “inativo” barato onde, por exemplo, a frequência de verificações de integridade é reduzida e a conexão TCP subjacente cai em favor do UDP.

Cada conexão requer alguma memória e CPU (devido à verificação periódica de integridade) em ambas as pontas. Embora essa sobrecarga seja pequena em teoria, ela pode se tornar rapidamente significativa quando ocorre em muitas máquinas. A subconfiguração evita a situação em que um único cliente se conecta a um número muito grande de tarefas de backend ou uma única tarefa de backend recebe conexões de um número muito grande de tarefas de cliente. Em ambos os casos, você potencialmente desperdiça uma quantidade muito grande de recursos para um ganho muito pequeno.

Escolhendo o subconjunto certo

Escolher o subconjunto certo se resume a escolher a quantas tarefas de backend cada cliente se conecta – o tamanho do subconjunto – e o algoritmo de seleção. Normalmente, usamos um tamanho de subconjunto de 20 a 100 tarefas de backend, mas o tamanho de subconjunto “certo” para um sistema depende muito do comportamento típico de seu serviço. Por exemplo, você pode querer usar um tamanho de subconjunto maior se:

O número de clientes é significativamente menor do que o número de backends. Nesse caso, você deseja que o número de backends por cliente seja grande o suficiente para que não acabe com tarefas de backend que nunca receberão tráfego.
Há desequilíbrios de carga frequentes nas tarefas do cliente (ou seja, uma tarefa do cliente envia mais solicitações do que outras). Esse cenário é típico em situações em que os clientes ocasionalmente enviam enxurradas de solicitações. Nesse caso, os próprios clientes recebem solicitações de outros clientes que ocasionalmente têm um grande fan-out (número de entradas que podem ser conectadas a uma saída específica; por exemplo, “ler todas as informações de todos os seguidores de um determinado usuário”). Como uma enxurrada de solicitações será concentrada no subconjunto atribuído ao cliente, você precisa de um tamanho de subconjunto maior para garantir que a carga seja distribuída uniformemente pelo conjunto maior de tarefas de backend disponíveis.

Uma vez que o tamanho do subconjunto é determinado, precisamos de um algoritmo para definir o subconjunto de tarefas de backend que cada tarefa do cliente usará. Isso pode parecer uma tarefa simples, mas se torna complexa rapidamente ao trabalhar com sistemas de grande escala onde o provisionamento eficiente é crucial e as reinicializações de sistema são garantidas.

O algoritmo de seleção para clientes deve atribuir backends uniformemente para otimizar o provisionamento de recursos. Por exemplo, se uma subconfiguração sobrecarregar um backend em 10%, todo o conjunto de backends precisará ser superprovisionado em 10%. O algoritmo também deve lidar com reinicializações e falhas de maneira elegante e robusta, continuando a carregar os backends da maneira mais uniforme possível, minimizando a rotatividade. Nesse caso, “churn” refere-se à seleção de substituição de backend. Por exemplo, quando uma tarefa de backend fica indisponível, seus clientes podem precisar escolher temporariamente um backend substituto. Quando um backend substituto é selecionado, os clientes devem criar novas conexões TCP (e provavelmente realizar uma negociação em nível de aplicação), o que cria sobrecarga adicional. Da mesma forma, quando uma tarefa de cliente é reiniciada, ela precisa reabrir as conexões com todos os seus backends.

O algoritmo também deve lidar com redimensionamentos no número de clientes e/ou número de backends, com churn de conexão mínimo e sem conhecer esses números antecipadamente. Essa funcionalidade é particularmente importante (e complicada) quando todo o conjunto de tarefas de cliente ou backend é reiniciado um de cada vez (por exemplo, para enviar uma nova versão). À medida que os backends são enviados, queremos que os clientes continuem atendendo, de forma transparente, com a menor perda de conexão possível.

Um algoritmo de seleção de subconjunto: subconjunto aleatório

Uma implementação ingênua de um algoritmo de seleção de subconjunto pode fazer com que cada cliente embaralhe aleatoriamente a lista de backends uma vez e preencha seu subconjunto selecionando backends resolvíveis/saudáveis da lista. Embaralhando uma vez e, em seguida, escolhendo backends do início da lista lida com reinicializações e falhas de forma robusta (por exemplo, com relativamente pouca rotatividade) porque explicitamente os limita a consideração. No entanto, descobrimos que essa estratégia funciona muito mal na maioria dos cenários práticos porque distribui a carga de maneira muito desigual.

Durante o trabalho inicial de balanceamento de carga, implementamos subconjuntos aleatórios e calculamos a carga esperada para vários casos. Como exemplo, considere:

300 clientes
300 backends
Um tamanho de subconjunto de 30% (cada cliente se conecta a 90 backends)

Como mostra a figura abaixo, o backend menos carregado tem apenas 63% da carga média (57 conexões, onde a média é de 90 conexões) e o mais carregado tem 121% (109 conexões). Na maioria dos casos, um tamanho de subconjunto de 30% já é maior do que gostaríamos de usar na prática. A distribuição de carga calculada muda toda vez que executamos a simulação enquanto o padrão geral permanece.

Infelizmente, tamanhos menores de subconjuntos levam a desequilíbrios ainda piores. Por exemplo, a figura abaixo mostra os resultados se o tamanho do subconjunto for reduzido para 10% (30 backends por cliente). Nesse caso, o backend menos carregado recebe 50% da carga média (15 conexões) e o mais carregado recebe 150% (45 conexões).

Concluímos que, para que o subconjunto aleatório distribua a carga de maneira relativamente uniforme em todas as tarefas disponíveis, precisaríamos de subconjuntos de tamanhos de até 75%. Um subconjunto tão grande é simplesmente impraticável; a variação no número de clientes que se conectam a uma tarefa é muito grande para considerar um subconjunto aleatório uma boa política de seleção de subconjunto em escala.

Um algoritmo de seleção de subconjunto: subconjunto determinístico

A solução do Google para as limitações do subconjunto aleatório é o subconjunto determinístico. O código a seguir implementa esse algoritmo, descrito em detalhes a seguir:

Dividimos as tarefas do cliente em “rodadas”, onde round i consiste em subset_count de tarefas consecutivas do cliente, começando na tarefa subset_count × i, e subset_count é o número de subconjuntos (ou seja, o número de tarefas de backend dividido pelo tamanho do subconjunto desejado). Dentro de cada rodada, cada backend é atribuído a exatamente um cliente (exceto possivelmente a última rodada, que pode não conter clientes suficientes, portanto, alguns backends podem não ser atribuídos).

Por exemplo, se tivermos 12 tarefas de backend [0, 11] e um tamanho de subconjunto desejado de 3, teremos rodadas contendo 4 clientes cada (subset_count = 12/3). Se tivéssemos 10 clientes, o algoritmo anterior poderia produzir os seguintes shuffled_backends:

O ponto-chave a ser observado é que cada rodada atribui apenas um backend em toda a lista a cada cliente (exceto o último, onde ficamos sem clientes). Neste exemplo, cada backend é atribuído a exatamente dois ou três clientes.

A lista deve ser embaralhada; caso contrário, os clientes recebem um grupo de tarefas de backend consecutivas que podem ficar temporariamente indisponíveis (por exemplo, porque o trabalho de backend está sendo atualizado gradualmente, em ordem, da primeira à última tarefa). Rodadas diferentes usam uma semente diferente para embaralhar. Caso contrário, quando um backend falha, a carga que estava recebendo é distribuída apenas entre os backends restantes em seu subconjunto. Se backends adicionais no subconjunto falharem, o efeito se compõe e a situação pode piorar de forma significante e bem rapidamente: se N backends em um subconjunto estiverem inativos, sua carga correspondente será distribuída pelos backends restantes (subset_size – N). Uma abordagem muito melhor é distribuir essa carga por todos os backends restantes usando um embaralhador diferente para cada rodada.

Quando usamos um embaralhamento diferente para cada rodada, os clientes na mesma rodada começarão com a mesma lista embaralhada, mas os clientes nas rodadas terão listas embaralhadas diferentes. A partir daqui, o algoritmo cria definições de subconjunto com base na lista embaralhada de backends e no tamanho de subconjunto desejado. Por exemplo:

Subset[0] = shuffled_backends[0] através de shuffled_backends[2]

Subset[1] = shuffled_backends[3] através de shuffled_backends[5]

Subset[2] = shuffled_backends[6] através de shuffled_backends[8]

Subset[3] = shuffled_backends[9] através de shuffled_backends[11]

onde shuffled_backend é a lista embaralhada criada por cada cliente. Para atribuir um subconjunto a uma tarefa de cliente, basta pegar o subconjunto que corresponde à sua posição dentro de sua rodada (por exemplo, (i % 4) para client[i] com quatro subconjuntos):

client[0], client[4], client[8] usará subset[0]

client[1], client[5], client[9] usará subset[1]

client[2], client[6], client[10] usará subset[2]

client[3], client[7], client[11] usará subset[3]

Como os clientes nas rodadas usarão um valor diferente para shuffled_backends (e, portanto, para subset) e os clientes nas rodadas usarão subconjuntos diferentes, a carga da conexão é distribuída uniformemente. Nos casos em que o número total de backends não é divisível pelo tamanho do subconjunto desejado, permitimos que alguns subconjuntos sejam ligeiramente maiores que outros, mas na maioria dos casos o número de clientes atribuídos a um backend será diferente em no máximo 1.

Como mostra a figura abaixo, a distribuição para o exemplo anterior de 300 clientes cada um se conectando a 10 de 300 backends produz resultados muito bons: cada backend recebe exatamente o mesmo número de conexões.

Políticas de balanceamento de carga

Agora que estabelecemos as bases de como uma determinada tarefa do cliente mantém um conjunto de conexões que são conhecidas como íntegras, vamos examinar as políticas de balanceamento de carga. Esses são os mecanismos usados pelas tarefas do cliente para selecionar qual tarefa de backend em seu subconjunto recebe uma solicitação do cliente. Muitas das complexidades nas políticas de balanceamento de carga decorrem da natureza distribuída do processo de tomada de decisão em que os clientes precisam decidir, em tempo real (e com apenas informações parciais e/ou obsoletas do estado do backend), qual backend deve ser usado para cada solicitação.

As políticas de balanceamento de carga podem ser muito simples e não levar em consideração nenhuma informação sobre o estado dos backends (por exemplo, Round Robin) ou podem atuar com mais informações sobre os backends (por exemplo, Round Robin Least-Loaded ou Weighted Round Robin).

Round Robin simples

Uma abordagem muito simples para o balanceamento de carga faz com que cada cliente envie solicitações em uma espécie de rodízio (do inglês “round-robin”) para cada tarefa de backend em seu subconjunto ao qual ele pode se conectar com sucesso e que não está no estado lame duck. Por muitos anos, essa foi nossa abordagem mais comum e ainda é usada por muitos serviços.

Infelizmente, embora o Round Robin tenha a vantagem de ser muito simples e ter um desempenho significativamente melhor do que apenas selecionar tarefas de backend aleatoriamente, os resultados dessa política podem ser muito ruins. Embora os números reais dependam de muitos fatores, como custo variável de consulta e diversidade de máquina, descobrimos que o Round Robin pode resultar em uma distribuição de até 2x no consumo de CPU da tarefa menos carregada para a mais carregada. Essa propagação é extremamente dispendiosa e ocorre por vários motivos, incluindo:

Subconjunto pequeno
Custos de consulta variáveis
Diversidade de máquinas
Fatores de desempenho imprevisíveis

Subconjunto pequeno

Uma das razões mais simples pelas quais o Round Robin distribui a carga mal é que todos os seus clientes podem não emitir solicitações na mesma taxa. Diferentes taxas de solicitações entre clientes são especialmente prováveis quando processos muito diferentes compartilham os mesmos backends. Nesse caso, e especialmente se você estiver usando tamanhos de subconjuntos relativamente pequenos, os backends nos subconjuntos dos clientes que geram mais tráfego naturalmente tenderão a ser mais carregados.

Custos de consulta variáveis

Muitos serviços lidam com solicitações que exigem quantidades muito diferentes de recursos para processamento. Na prática, descobrimos que a semântica de muitos serviços no Google é tal que as solicitações mais caras consomem 1.000 vezes (ou mais) CPU do que as solicitações mais baratas. O balanceamento de carga usando Round Robin é ainda mais difícil quando o custo da consulta não pode ser previsto com antecedência. Por exemplo, uma consulta como “devolver todos os e-mails recebidos pelo usuário XYZ no último dia” pode ser muito barata (se o usuário recebeu poucos e-mails ao longo do dia) ou extremamente cara.

O balanceamento de carga em um sistema com grandes discrepâncias no custo potencial da consulta é muito problemático. Pode ser necessário ajustar as interfaces de serviço para limitar funcionalmente a quantidade de trabalho realizado por solicitação. Por exemplo, no caso da consulta de e-mail descrita anteriormente, você pode introduzir uma interface de paginação e alterar a semântica da solicitação para “retornar os 100 e-mails mais recentes (ou menos) recebidos pelo usuário XYZ no último dia“. Infelizmente, muitas vezes é difícil introduzir essas mudanças semânticas. Isso não apenas requer alterações em todo o código do cliente, mas também envolve considerações adicionais de consistência. Por exemplo, o usuário pode estar recebendo novos e-mails ou excluindo e-mails enquanto o cliente busca e-mails página por página. Para este caso de uso, um cliente que itera ingenuamente pelos resultados e concatena as respostas (em vez de paginar com base em uma visualização fixa dos dados) provavelmente produzirá uma visualização inconsistente, repetindo algumas mensagens e/ou ignorando outras.

Para manter as interfaces (e suas implementações) simples, os serviços geralmente são definidos para permitir que as solicitações mais caras consumam 100, 1.000 ou até 10.000 vezes mais recursos do que as solicitações mais baratas. No entanto, variar os requisitos de recursos por solicitação naturalmente significa que algumas tarefas de backend terão azar e, ocasionalmente, receberão solicitações mais caras do que outras. A extensão em que essa situação afeta o balanceamento de carga depende de quão caras são as solicitações mais caras. Por exemplo, para um de nossos backends Java, as consultas consomem cerca de 15 ms de CPU em média, mas algumas consultas podem facilmente exigir até 10 segundos. Cada tarefa neste backend reserva vários núcleos de CPU, o que reduz a latência, permitindo que alguns dos cálculos ocorram em paralelo. Mas, apesar desses núcleos reservados, quando um backend recebe uma dessas grandes consultas, sua carga aumenta significativamente por alguns segundos. Uma tarefa mal comportada pode ficar sem memória ou até mesmo parar de responder completamente (por exemplo, devido ao thrashing de memória), mas mesmo no caso normal (ou seja, o backend tem recursos suficientes e sua carga normaliza quando a consulta grande é concluída), a latência de outros pedidos sofre devido à competição de recursos com o(s) pedido(s) mais caro(s).

Diversidade de máquinas

Outro desafio para o Simple Round Robin é o fato de que nem todas as máquinas no mesmo datacenter são necessariamente as mesmas. Um determinado datacenter pode ter máquinas com CPUs de desempenho variável e, portanto, a mesma solicitação pode representar uma quantidade de trabalho significativamente diferente para máquinas diferentes.

Lidar com a diversidade de máquinas — sem exigir homogeneidade rigorosa — foi um desafio por muitos anos no Google. Em teoria, a solução para trabalhar com capacidade heterogênea de recursos em uma frota é simples: dimensionar as reservas de CPU dependendo do tipo de processador/máquina. No entanto, na prática, a implementação dessa solução exigiu um esforço significativo, pois exigia que nosso agendador de tarefas considerasse as equivalências de recursos com base no desempenho médio da máquina em uma amostra de serviços. Por exemplo, 2 unidades de CPU na máquina X (uma máquina “lenta”) é equivalente a 0,8 unidades de CPU na máquina Y (uma máquina “rápida”). Com essas informações, o escalonador de tarefas deve ajustar as reservas de CPU para um processo com base no fator de equivalência e no tipo de máquina na qual o processo foi escalonado. Na tentativa de mitigar essa complexidade, criamos uma unidade virtual para taxa de CPU chamada “GCU” (Google Compute Units). As GCUs tornaram-se o padrão para a modelagem de taxas de CPU e foram usadas para manter um mapeamento de cada arquitetura de CPU em nossos datacenters para sua GCU correspondente com base em seu desempenho.

Fatores de desempenho imprevisíveis

Talvez o maior fator complicador para o Simple Round Robin seja que as máquinas – ou, mais precisamente, o desempenho das tarefas de backend – podem diferir muito devido a vários aspectos imprevisíveis que não podem ser contabilizados estaticamente.

Dois dos muitos fatores imprevisíveis que contribuem para o desempenho incluem:

Vizinhos antagônicos

Outros processos (geralmente não relacionados e executados por equipes diferentes) podem ter um impacto significativo no desempenho de seus processos. Vimos diferenças de desempenho dessa natureza de até 20%. Essa diferença decorre principalmente da competição por recursos compartilhados, como espaço em caches de memória ou largura de banda, de maneiras que podem não ser diretamente óbvias. Por exemplo, se a latência de solicitações de saída de uma tarefa de backend aumentar (devido à competição por recursos de rede com um vizinho antagônico), o número de solicitações ativas também aumentará, o que pode acionar o aumento do garbage collection.

Reinícios de tarefas

Quando uma tarefa é reiniciada, geralmente requer muito mais recursos por alguns minutos. Como apenas um exemplo, vimos essa condição afetar plataformas (como Java) que otimizam o código dinamicamente mais do que outras. Em resposta, na verdade adicionamos à lógica de algum código de servidor – mantemos os servidores no estado lame duck e os pré-aquecemos (acionando essas otimizações) por um período de tempo após o início, até que seu desempenho seja nominal. O efeito das reinicializações de tarefas pode se tornar um problema considerável quando atualizamos muitos servidores (por exemplo, envio de novas compilações, o que requer a reinicialização dessas tarefas) todos os dias.

Se sua política de balanceamento de carga não puder se adaptar a limitações de desempenho imprevistas, você acabará inerentemente com uma distribuição de carga abaixo da ideal ao trabalhar em escala.

Round Robin intermediário

Uma abordagem alternativa ao Simple Round Robin é fazer com que cada tarefa do cliente acompanhe o número de solicitações ativas que possui para cada tarefa de backend em seu subconjunto e use o Round Robin entre o conjunto de tarefas com um número mínimo de solicitações ativas.

Por exemplo, suponha que um cliente use um subconjunto de tarefas de backend t0 a t9 e atualmente tenha o seguinte número de solicitações ativas em cada backend:

Para uma nova solicitação, o cliente filtraria a lista de possíveis tarefas de backend apenas para aquelas tarefas com o menor número de conexões (t2, t3, t5, t7 e t8) e escolheria um backend dessa lista. Vamos supor que ele escolha t2. A tabela de estado de conexão do cliente agora teria a seguinte aparência:

Supondo que nenhuma das solicitações atuais tenha sido concluída, na próxima solicitação, o pool de candidatos de backend se torna t3, t5, t7 e t8.

Vamos avançar rapidamente até emitirmos quatro novas solicitações. Ainda supondo que nenhuma solicitação seja concluída nesse meio tempo, a tabela de estado de conexão teria a seguinte aparência:

Neste ponto, o conjunto de candidatos de backend são todas as tarefas, exceto t0 e t6. No entanto, se a solicitação em relação à tarefa t4 for concluída, seu estado atual se tornará “0 solicitações ativas” e uma nova solicitação será atribuída a t4.

Essa implementação realmente usa Round Robin, mas é aplicada em todo o conjunto de tarefas com solicitações ativas mínimas. Sem essa filtragem, a política pode não ser capaz de distribuir as solicitações o suficiente para evitar uma situação em que parte das tarefas de backend disponíveis não sejam utilizadas. A ideia por trás da política de menor carga é que as tarefas carregadas tenderão a ter maior latência do que aquelas com capacidade extra, e essa estratégia naturalmente tirará a carga dessas tarefas carregadas.

Dito tudo isso, aprendemos (da maneira mais difícil!) sobre uma armadilha muito perigosa da abordagem Round Robin menos carregado: se uma tarefa não estiver nada íntegra, ela pode começar a apresentar 100% de erros. Dependendo da natureza desses erros, eles podem ter latência muito baixa; muitas vezes é significativamente mais rápido apenas retornar um erro “Não estou íntegro!” do que efetivamente processar uma solicitação. Como resultado, os clientes podem começar a enviar uma quantidade muito grande de tráfego para a tarefa não íntegra, pensando erroneamente que a tarefa está disponível, em vez de fazê-la falhar rapidamente! Dizemos que a tarefa não íntegra está agora “afundando” o tráfego. Felizmente, essa armadilha pode ser resolvida com relativa facilidade modificando a política para contar erros recentes como se fossem solicitações ativas. Dessa forma, se uma tarefa de backend se tornar não íntegra, a política de balanceamento de carga começará a desviar a carga dela da mesma forma que desviaria a carga de uma tarefa sobrecarregada.

O Round Robin menos carregado apresenta duas limitações importantes:

A contagem de solicitações ativas pode não ser um proxy muito bom para a capacidade de um determinado backend

Muitas solicitações passam uma parte significativa de sua vida apenas aguardando uma resposta da rede (ou seja, aguardando respostas a solicitações que iniciam para outros backends) e muito pouco tempo no processamento real. Por exemplo, uma tarefa de backend pode processar duas vezes mais solicitações que outra (por exemplo, porque está sendo executada em uma máquina com uma CPU duas vezes mais rápida que o restante), mas a latência de suas solicitações ainda pode ser aproximadamente a mesma como a latência das requisições na outra tarefa (porque as requisições passam a maior parte de sua vida apenas esperando que a rede responda). Nesse caso, como o bloqueio de I/O geralmente consome zero de CPU, muito pouca RAM e nenhuma largura de banda, ainda gostaríamos de enviar o dobro de solicitações para o backend mais rápido. No entanto, o Round Robin menos carregado considerará ambas as tarefas de backend igualmente carregadas.

A contagem de solicitações ativas em cada cliente não inclui solicitações de outros clientes para os mesmos backends

Ou seja, cada tarefa do cliente tem apenas uma visão muito limitada do estado de suas tarefas de backend: a visão de suas próprias solicitações.

Na prática, descobrimos que grandes serviços usando o Round Robin menos carregado verão sua tarefa de backend mais carregada usando duas vezes mais CPU do que a menos carregada, tendo um desempenho tão ruim quanto o Round Robin.

Round Robin avançado

O Round Robin avançado é uma importante política de balanceamento de carga que melhora o Round Robin simples e intermediário, incorporando informações fornecidas pelo backend no processo de decisão.

O Round Robin avançado é bastante simples em princípio: cada tarefa do cliente mantém uma pontuação de “capacidade” para cada backend em seu subconjunto. As solicitações são distribuídas no modo Round-Robin, mas os clientes pesam as distribuições de solicitações para backends proporcionalmente. Em cada resposta (incluindo respostas a verificações de integridade), os backends incluem as taxas observadas atuais de consultas e erros por segundo, além da utilização (normalmente, uso da CPU). Os clientes ajustam as pontuações de capacidade periodicamente para escolher tarefas de backend com base em seu número atual de solicitações bem-sucedidas tratadas e em qual custo de utilização; solicitações com falha resultam em uma penalidade que afeta decisões futuras.

Na prática, o Round Robin avançado funcionou muito bem e reduziu significativamente a diferença entre as tarefas mais e menos utilizadas. A figura abaixo mostra as taxas de CPU para um subconjunto aleatório de tarefas de backend em torno do momento em que seus clientes alternaram de Round Robin intermediário para avançado. A propagação das tarefas menos carregadas para as tarefas mais carregadas diminuiu drasticamente.

Fonte: Google SRE Book