Robinhood, o serviço interno de balanceamento de carga da Dropbox

• Robinhood é o serviço interno de balanceamento de carga da Dropbox, implantado em 2020
• Ele roteia o tráfego interno entre servidores para distribuir a carga dos serviços de forma equilibrada
• Antes do Robinhood, a maioria dos serviços da Dropbox enfrentava dificuldades com distribuição desigual de carga entre backends
• Diferenças de hardware e limitações dos algoritmos anteriores de balanceamento de carga causavam problemas de confiabilidade devido a instâncias sobrecarregadas
• Para resolver isso, era necessário superprovisionar a frota de serviços, o que aumentava os custos de hardware

Novos recursos do Robinhood

• Com o uso de um controlador PID (Proportional-Integral-Derivative), passou a ser possível gerenciar desequilíbrios de carga com mais rapidez e eficácia
• Isso levou a melhorias na confiabilidade da infraestrutura e a uma redução significativa nos custos de hardware
• Com o crescimento das cargas de trabalho de IA que alimentam recursos inteligentes mais recentes, o gerenciamento eficiente da demanda por recursos de GPU se tornou mais importante do que nunca

Desafios de balanceamento de carga na Dropbox

• O sistema de service discovery da Dropbox pode escalar para centenas de milhares de hosts distribuídos em vários data centers ao redor do mundo
• Alguns serviços da Dropbox têm milhões de clientes, mas não é possível permitir que cada cliente se conecte a todas as instâncias de servidor
  • Isso colocaria pressão excessiva de memória nos servidores e, em reinicializações, os handshakes TLS poderiam sobrecarregá-los
• Em vez disso, o sistema de service discovery fornece a cada cliente um subconjunto de servidores aos quais ele pode se conectar
• A melhor estratégia de balanceamento de carga disponível para o cliente é fazer round robin na lista de endereços fornecida pelo sistema de service discovery
  • No entanto, com esse método, a carga de cada instância de servidor pode ficar bastante desequilibrada
  • Aumentar o tamanho do subconjunto é uma mitigação simples, mas não elimina totalmente o desequilíbrio e apenas adiciona mais um parâmetro para o responsável pelo serviço
• Um problema mais profundo é que, mesmo enviando o mesmo número de requisições para cada servidor, o hardware subjacente pode variar entre eles
  • Ou seja, as requisições consomem quantidades diferentes de recursos em classes de hardware distintas
• O ponto central é que os clientes não têm visibilidade sobre a carga dos servidores
• No passado, tentou-se resolver isso fazendo com que os servidores incluíssem a carga nos headers de resposta
  • Assim, os clientes poderiam fazer o próprio balanceamento de carga escolhendo o endpoint menos carregado dentro do subconjunto de endereços
  • Os resultados foram promissores, mas ainda havia algumas desvantagens
    • Como tanto servidores quanto clientes precisavam de mudanças de código para suportar o header especial de carga, era difícil adotar isso globalmente
    • Os resultados eram bons, mas não bons o suficiente

Decisão de construir o Robinhood

• Em 2019, foi tomada a decisão oficial de construir o Robinhood
• Esse novo serviço foi construído sobre o sistema interno de service discovery já existente, coletando informações de carga dos servidores e anexando-as às informações de roteamento
• O Robinhood aproveita o Endpoint Discovery Service do Envoy para incorporar informações de carga aos pesos dos endpoints, permitindo que os clientes façam round robin com base em pesos
• Como a comunidade gRPC está adotando o protocolo Envoy xDS, o Robinhood é compatível tanto com Envoy quanto com clientes gRPC
• Como não havia na época uma solução existente de balanceamento de carga que atendesse aos requisitos da Dropbox, decidiu-se construir um novo serviço

Resultados do Robinhood

• Após vários anos de uso em produção, os resultados se mostraram promissores
• Foi possível reduzir em 25% o tamanho da frota de alguns serviços de grande porte, economizando custos significativos de hardware por ano
• A confiabilidade também melhorou com a redução de processos excessivamente utilizados

Arquitetura do Robinhood

• Uma instância do Robinhood é implantada em cada data center e é composta por três partes: serviço de balanceamento de carga, proxy e banco de dados de roteamento

Serviço de balanceamento de carga (LBS)

• O núcleo do Robinhood
• Responsável por coletar informações de carga e gerar informações de roteamento com pesos de endpoint
• Como várias instâncias atualizam ao mesmo tempo as informações de roteamento de um serviço, ele usa um shard manager interno para atribuir um worker primário a cada serviço
• Como cada serviço é independente, é possível particionar o LBS por serviço e escalá-lo horizontalmente

Proxy

• Responsável por encaminhar as informações de carga do serviço para a partição correspondente do LBS dentro do data center
• O uso de um proxy também reduz o número de conexões diretas com o processo do LBS
  • Sem o proxy, todos os processos do LBS precisariam se conectar a todos os nós da infraestrutura
  • Em vez disso, os processos do LBS se conectam apenas ao proxy, reduzindo bastante a pressão de memória do LBS
• O proxy se conecta apenas a nós dentro do mesmo data center, o que permite escalá-lo horizontalmente
• Esse padrão é usado em muitas partes da infraestrutura para proteger serviços contra o recebimento de conexões TLS em excesso

Banco de dados de roteamento

• Um banco de dados baseado em ZooKeeper/etcd que armazena informações de roteamento dos serviços, como nomes de host, endereços IP e pesos gerados pelo LBS
• ZooKeeper e etcd podem notificar em tempo real todos os watchers sobre mudanças em nós/chaves, o que os torna muito adequados ao caso de uso de service discovery orientado a leitura da Dropbox
• A consistência eventual garantida por ZooKeeper/etcd também é suficiente para service discovery

Analisando mais de perto o serviço de balanceamento de carga

• O objetivo do balanceamento de carga é fazer com que a utilização de todos os nós seja igual à utilização média
• Um controlador PID é usado para manter a utilização de cada nó quase igual à utilização média
• O LBS cria um controlador PID para cada nó e usa a utilização média como setpoint
• O LBS usa a saída do controlador PID como delta para o peso do endpoint e normaliza os pesos entre todos os endpoints do serviço
• Embora novos nós precisem de alguns ajustes até convergir para a utilização média, o controlador PID é muito eficaz para balanceamento de carga

Cenários de operação do LBS

• O LBS foi projetado para lidar com vários cenários que podem afetar o balanceamento de carga, desde reinicializações de nós até ausência de relatórios de carga
• Para manter o desempenho ideal, o LBS implementa várias estratégias para tratar esses casos excepcionais

Inicialização do LBS

• O LBS mantém em memória as informações de carga e o estado do controlador PID
• Durante uma reinicialização do LBS, ele não começa a atualizar pesos imediatamente e espera um pouco até receber relatórios de carga
• No caso dos pesos do controlador PID, o LBS os restaura lendo os pesos dos endpoints no banco de dados de roteamento

Nós com cold start

• Novos nós entram com frequência na frota de serviços, então é importante evitar o problema de Thundering Herd
• Como a utilização inicial de um novo nó geralmente é 0, o LBS define o peso desse novo nó como um peso de endpoint baixo e deixa o controlador PID elevá-lo até a utilização média

Relatórios de carga ausentes

• Em ambientes de sistemas distribuídos, falhas são comuns
• Devido a congestionamento de rede ou falhas de hardware, os relatórios de carga de alguns nós podem atrasar ou não chegar
• O LBS ignora esses nós durante a atualização dos pesos, então os pesos de endpoint desses nós não são alterados
• No entanto, se muitos relatórios de carga estiverem ausentes, o cálculo da utilização média pode se tornar impreciso
• Por segurança, o LBS nesse caso pula completamente a etapa de atualização de pesos

Métricas de utilização

• A utilização de CPU é a métrica de balanceamento de carga mais usada na Dropbox
• Para serviços que não têm gargalo de CPU, o número de requisições em andamento é uma boa métrica alternativa
• O LBS foi implementado para oferecer suporte a balanceamento de carga com base em CPU e/ou requisições em andamento

Limitações

• O controlador PID forma um loop de feedback para manter a utilização dos nós próxima do valor alvo, que é a utilização média
• Em situações com pouco feedback, como serviços com tráfego muito baixo ou requisições de latência muito alta medidas em minutos, o balanceamento de carga não funciona bem
• Serviços com requisições de alta latência devem ser assíncronos

Roteamento entre data centers

• As instâncias do LBS lidam com o balanceamento de carga dentro de cada data center
• O roteamento entre data centers envolve outras considerações
  • Por exemplo, busca-se rotear as requisições para o data center mais próximo a fim de reduzir o tempo de ida e volta
• Para isso, foi introduzida uma configuração de localidade que define a divisão de tráfego entre os data centers de destino

Avaliação de desempenho do balanceador de carga

• O desempenho do balanceamento de carga é medido pela razão max/avg
  • Se o responsável pelo serviço escolher o balanceamento de carga com base em CPU, usa-se maxCPU/avgCPU como métrica de desempenho
  • Em geral, o responsável pelo serviço provisiona o serviço com base na utilização máxima entre nós, porque o principal objetivo do balanceamento de carga é reduzir o tamanho da frota
• A estratégia de balanceamento de carga com controlador PID consegue manter a razão max/avg próxima de 1

Gráficos de avaliação de desempenho do balanceamento de carga

• Gráfico que mostra max/avg CPU e p95/avg CPU do maior cluster de proxies Envoy
  • Após ativar o balanceamento de carga baseado em controlador PID, as duas métricas caem para perto de 1
  • A razão max/avg caiu de 1,26 para 1,01, mostrando uma melhoria de 20%
• Gráfico que mostra uma análise por percentis da utilização de CPU por nó
  • Após ativar o balanceamento de carga baseado em controlador PID, max, p95, avg e p5 praticamente se unem em uma única linha
• Outro gráfico que mostra max/avg CPU e p95/avg CPU do maior cluster entre os clusters de frontend de banco de dados
  • Após ativar o balanceamento de carga baseado em controlador PID, as duas métricas caem para perto de 1
  • A razão max/avg caiu de 1,4 para 1,05, mostrando uma melhoria de 25%
• Outro gráfico que mostra uma análise por percentis da utilização de CPU por nó
  • Após ativar o balanceamento de carga baseado em controlador PID, max, p95, avg e p5 mais uma vez praticamente se unem em uma única linha

Motivo para construir o Config Aggregator

• O Robinhood oferece várias opções para o responsável pelo serviço escolher e também consegue aplicar alterações dinamicamente
• O responsável pelo serviço cria e atualiza a configuração do Robinhood para o serviço no diretório do serviço dentro do codebase
• Essas configurações são armazenadas em um serviço de gerenciamento de configuração, uma biblioteca prática que recebe em tempo real alterações na configuração do Robinhood
• Porém, por alguns problemas, não era possível compilar e enviar regularmente a mega configuração do Robinhood a partir do codebase
  • Quando alterações são introduzidas por um push de configuração, apertar o botão de rollback é arriscado
    • Porque não se sabe quantos outros serviços mudaram desde o último push
  • A equipe responsável pelo Robinhood também é responsável por cada push da mega configuração
    • Isso significa que a equipe do Robinhood precisa participar de todos os pushes de configuração alterados, o que é desperdício de tempo de engenharia
    • Porque a maioria dos incidentes pode ser resolvida pelo responsável pelo serviço
  • Para minimizar riscos potenciais, cada push leva horas para ser implantado em vários data centers
• Para resolver esses problemas, foi construído outro pequeno serviço chamado Config Aggregator

Config Aggregator

• O Config Aggregator coleta todas as configurações por serviço e monta a mega configuração que o LBS vai usar
• O Config Aggregator monitora as configurações por serviço e propaga as alterações para a mega configuração em tempo real
• O Config Aggregator também fornece uma função de tombstone para evitar que a configuração do Robinhood de um serviço seja apagada acidentalmente
  • Se o responsável pelo serviço fizer push de uma alteração que remova o serviço da configuração do Robinhood, o Config Aggregator marca a entrada do serviço como tombstone em vez de removê-la imediatamente
  • A remoção real acontece alguns dias depois
  • Essa função também resolve condições de corrida que podem surgir por causa de ciclos de push diferentes entre a configuração do Robinhood e outras configurações de roteamento, como a configuração do Envoy
• Uma desvantagem do serviço de gerenciamento de configuração é que atualmente ele não tem versionamento
• A mega configuração é armazenada em backup periodicamente caso seja necessário reverter a configuração do LBS para um estado conhecido como bom

Estratégia de migração

• Trocar a estratégia de balanceamento de carga de uma vez só pode ser arriscado
• É por isso que o Robinhood permite configurar várias estratégias de balanceamento de carga para um serviço
• A Dropbox tem feature gates baseados em porcentagem, então foi implementada uma estratégia híbrida na qual o cliente usa como peso do endpoint uma soma ponderada dos pesos gerados pelas duas estratégias de balanceamento de carga
• Assim, é possível migrar gradualmente para a nova estratégia de balanceamento de carga, enquanto todos os clientes veem a mesma atribuição de pesos para os endpoints

Lições aprendidas

• Durante o design e a implementação do Robinhood, foram obtidas algumas lições importantes sobre o que funciona e o que não funciona
• Ao priorizar a simplicidade, minimizar mudanças nos clientes e planejar a migração desde o início, foi possível simplificar o desenvolvimento e a implantação do LBS e evitar armadilhas custosas

A configuração deve ser o mais simples possível

• O Robinhood introduziu muitas opções configuráveis para os responsáveis pelos serviços
• Porém, na maioria dos casos, o que eles precisam são as configurações padrão fornecidas
• Uma boa configuração padrão e simples (ou, melhor ainda, nenhuma configuração) pode economizar uma enorme quantidade de tempo de engenharia

As mudanças nos clientes também devem ser mantidas simples

• O rollout de mudanças para clientes internos pode levar meses
  • A maioria das implantações é enviada semanalmente, mas muitas ocorrem uma vez por mês ou nem chegam a ser implantadas por anos
• Quanto mais mudanças puderem ser movidas para o LBS, melhor
  • Por exemplo, no início foi decidido usar weighted round robin no design do cliente, e isso não foi alterado desde então
  • Isso acelerou bastante o progresso
• Limitar a maior parte das mudanças ao LBS também reduz riscos de estabilidade
  • Porque, se necessário, alterações no LBS podem ser revertidas em poucos minutos

A migração deve ser planejada na fase de design do projeto

• A migração consome uma quantidade enorme de tempo de engenharia
• Também há riscos de estabilidade a considerar
• Não é uma tarefa divertida, mas é importante
• Ao projetar um novo serviço, é preciso pensar o quanto antes em como migrar sem atritos os casos de uso existentes para o novo serviço
• Quanto mais exigências forem feitas ao responsável pelo serviço, mais a migração vira um pesadelo
  • Isso é ainda mais verdadeiro no caso de componentes básicos de infraestrutura
• O processo de migração do Robinhood não foi bem projetado desde o início, então foi gasto muito mais tempo do que o esperado reimplementando o processo e redesenhando a configuração
• O tempo de engenharia necessário para a migração deve ser um indicador-chave de sucesso

Efeito do Robinhood

• Depois de cerca de um ano em produção, pode-se dizer que a iteração mais recente do Robinhood resolveu de forma eficaz os antigos desafios de balanceamento de carga da Dropbox
• O algoritmo central, o controlador PID, mostrou resultados promissores e ganhos de desempenho significativos nos maiores serviços
• Também foram obtidos insights valiosos sobre o design e a operação de um serviço de balanceamento de carga na escala da Dropbox

Notas de rodapé

1. Sejam N, M e s respectivamente o número de servidores, o número de clientes e o tamanho do subconjunto de endereços. O número de clientes aos quais um servidor se conecta segue uma amostra da distribuição binomial B(M, s/n). Como mencionado antes, os clientes fazem round robin simples sobre o conjunto de endereços fornecido pelo service discovery. Portanto, se cada cliente enviar aproximadamente a mesma quantidade de requisições, a distribuição de carga no lado do servidor será semelhante a uma distribuição binomial.

2. O sistema de service discovery existente foi expandido para oferecer suporte ao protocolo gRPC xDS (A27). Na data em que este blog foi escrito, os clientes gRPC não ofereciam suporte a weighted round robin para pesos de endpoint do control plane, então foi implementado um seletor personalizado de weighted round robin com base em shortest-deadline-first scheduling.

3. Houve um caso interessante em que um serviço às vezes ficava congestionado por I/O com desempenho degradado. Nessas situações, a CPU daquele nó permanecia baixa, e o LBS começava a aumentar o peso do nó para elevar a CPU até a média, levando a uma espiral de degradação. Como solução, passou-se a usar o maior valor entre CPU e requisições em andamento como medida de carga para balancear o serviço.

Opinião do GN⁺

• O Robinhood parece ser um excelente serviço que resolveu de forma eficaz os desafios de balanceamento de carga da Dropbox. O uso de um controlador PID é especialmente impressionante
• Este é um bom exemplo de como o balanceamento de carga é um desafio difícil em uma infraestrutura global de grande escala. Há muitos fatores a considerar, como diferenças de hardware, distribuição desigual de carga e congestionamento de rede
• Parece importante projetar o sistema para que todos os componentes funcionem de forma orgânica e bem conectada. Embora LBS, proxy e banco de dados de roteamento sejam separados, eles interagem de forma estreita em tempo real
• Os gráficos que avaliam quantitativamente o desempenho do balanceamento de carga e visualizam as melhorias são impressionantes. Em especial, mostram bem como manter a razão max/avg próxima de 1 é importante para otimizar o tamanho da frota
• A introdução do Config Aggregator para separar as configurações por serviço também parece uma boa ideia. Isso permite que os responsáveis por cada serviço gerenciem suas próprias mudanças de forma independente
• A inclusão de mecanismos de segurança como tombstone também é um detalhe cuidadoso. É importante evitar a exclusão acidental de configurações
• As lições sobre a estratégia de migração também parecem úteis. Se a migração não for considerada desde o início, muito tempo pode ser desperdiçado depois
• No geral, o Robinhood parece ser uma solução sistemática e sofisticada para balanceamento de carga na escala da Dropbox. É um caso que também pode servir de referência para outras empresas com infraestrutura de grande porte

Soluções semelhantes:

• O Elastic Load Balancing (ELB) da AWS e o Cloud Load Balancing do Google Cloud também oferecem serviços gerenciados para balanceamento de carga em grande escala
• No caso do Kubernetes, ele possui seu próprio balanceador de carga (kube-proxy), mas, com soluções de service mesh como Istio ou Linkerd, é possível usar recursos mais avançados de balanceamento de carga e gerenciamento de tráfego
• O Zuul da Netflix e o Envoy da Lyft também oferecem recursos de balanceamento de carga baseados em proxy

Pontos a considerar na adoção:

• É necessário verificar a compatibilidade com a infraestrutura e os serviços existentes. Se for preciso migrar, deve-se definir uma estratégia
• É preciso testar e monitorar suficientemente os impactos em desempenho e estabilidade. Bugs na lógica de balanceamento de carga podem ser críticos
• É preciso definir o escopo e a velocidade da adoção considerando a capacidade da equipe. Em vez de aplicar tudo de uma vez, uma adoção gradual parece melhor
• No longo prazo, será necessário continuar otimizando e melhorando continuamente. Ajustar o algoritmo de balanceamento de carga conforme o contexto e eliminar gargalos são medidas que podem ajudar

[kbumsik]

É a primeira vez que ouço falar de um controlador PID no lado de software haha