Papers
Maglev: A Fast and Reliable Software Network Load Balancer
Danielle E. Eisenbud, Cheng Yi, Carlo Contavalli, Cody Smith, Roman Kononov, Eric Mann-Hielscher, Ardas Cilingiroglu, Bin Cheyney, Wentao Shang, Jinnah Dylan Hosein · NSDI 2016 (13th USENIX Symposium on Networked Systems Design and Implementation), 2016
O problema: balanceadores de hardware não acompanham o tráfego do Google
Um balanceador de carga de rede fica entre os roteadores e os servidores de um serviço: ele casa cada pacote com o serviço de destino e o encaminha a um dos endpoints desse serviço. Tradicionalmente isso era feito por aparelhos de hardware dedicados, e os autores apontam quatro limitações para o caso do Google. Primeiro, a escalabilidade é limitada pela capacidade máxima de uma única unidade. Segundo, esses aparelhos costumam ser implantados em pares, oferecendo apenas redundância 1+1, o que não atende ao requisito de alta disponibilidade. Terceiro, falta flexibilidade e programabilidade para iterar rápido em novas funcionalidades. Quarto, aumentar capacidade exige comprar e instalar fisicamente novo hardware. A alternativa proposta é construir o balanceador como um sistema distribuído de software rodando em servidores comuns Linux do próprio cluster. Isso permite escalar horizontalmente (scale-out) adicionando máquinas, obter redundância N+1, controlar e evoluir o sistema por conta própria e simplificar a implantação, já que só usa servidores existentes. Em contrapartida, o desafio é duplo: cada máquina precisa de alta vazão (a capacidade total é limitada por N x T) e o sistema precisa garantir persistência de conexão, isto é, pacotes da mesma conexão sempre chegam ao mesmo endpoint, mesmo com falhas frequentes. O Maglev serve o tráfego do Google desde 2008.
Arquitetura: VIPs, ECMP, encapsulamento GRE e Direct Server Return
Cada serviço do Google possui um ou mais endereços IP virtuais (VIPs), que não pertencem a uma interface física específica: são atendidos por vários endpoints atrás do Maglev. Cada máquina Maglev anuncia os VIPs ao roteador via BGP, todos com o mesmo custo. Assim, quando um pacote para um VIP chega ao roteador, ele o distribui entre as máquinas Maglev do cluster usando ECMP (Equal Cost Multipath). A máquina Maglev escolhe um endpoint do serviço, encapsula o pacote com GRE (Generic Routing Encapsulation) usando um cabeçalho IP externo destinado ao endpoint, e o envia. O endpoint desencapsula e consome o pacote. A resposta volta com o VIP como endereço de origem e o IP do usuário como destino, e é enviada diretamente ao roteador via Direct Server Return (DSR), de modo que o Maglev não precisa processar o tráfego de retorno, que costuma ser bem maior. Cada máquina Maglev tem dois componentes: o controller, que verifica periodicamente a saúde do forwarder e decide anunciar ou retirar todos os VIPs via BGP (assim o roteador só encaminha para máquinas saudáveis), e o forwarder, que trata os pacotes. Cada VIP é associado a um ou mais backend pools, cujos membros passam por health checks; pacotes só vão para backends saudáveis. É possível ainda dividir um cluster em shards de Maglevs, atendendo conjuntos distintos de VIPs, para isolar desempenho.
Processamento rápido de pacotes: kernel bypass e escolha de backend
Como as requisições de entrada costumam ser pequenas, o forwarder precisa lidar bem com pacotes minúsculos: assumindo pacotes IP de 100 bytes em média, ele precisaria processar cerca de 9,06 milhões de pacotes por segundo para saturar um link de 10 Gbps. Para chegar a isso, o Maglev é um aplicativo em espaço de usuário que ignora completamente a pilha de rede do kernel Linux. Na inicialização ele pré-aloca um pool de pacotes compartilhado com a placa de rede (NIC), e os pacotes se movem entre NIC e forwarder por filas em anel de ponteiros, sem cópia e sem envolvimento do kernel. Os pacotes são processados em lotes para reduzir o custo de cruzar fronteiras, e cada thread de pacote é fixada em um núcleo de CPU dedicado e não compartilha dados com as outras. Um módulo de steering calcula o hash da 5-tupla (IP e porta de origem, IP e porta de destino, protocolo) e distribui os pacotes entre as filas de recepção, em vez de usar round-robin, o que reduz reordenação dentro de uma conexão. Cada thread filtra pacotes que não são de nenhum VIP configurado, consulta sua tabela de conexões, escolhe um backend se necessário, encapsula em GRE e envia. Nos testes, a introdução do kernel bypass melhorou a vazão por máquina em mais de um fator de cinco, e uma máquina com NIC de 10 Gbps atingiu a capacidade da placa com pacotes pequenos usando 5 threads de pacote.
Persistência de conexão: tabela de conexões e hash consistente (Maglev hashing)
Para conexões orientadas a conexão como TCP, todos os pacotes precisam ir ao mesmo backend. O Maglev usa uma estratégia em duas partes: escolhe o backend com uma nova forma de hash consistente e registra a decisão em uma tabela de conexões local, de tamanho fixo, que mapeia o hash da 5-tupla ao backend. Mas só a tabela local não basta, por dois motivos: o ECMP do roteador pode redistribuir tráfego entre Maglevs quando o conjunto de máquinas muda (por exemplo, durante upgrades em rolling), e a tabela é finita e pode encher sob carga alta ou SYN flood. Para esses casos entra o hash consistente, que dá aos Maglevs a mesma escolha sem compartilhar estado. O Maglev hashing preenche uma tabela de lookup de tamanho M (primo) da seguinte forma: cada backend recebe uma lista de preferência, uma permutação de todas as posições da tabela, derivada de dois hashes do seu nome (offset e skip). Os backends então se revezam, cada um ocupando sua posição preferida ainda livre, até a tabela ficar completa. Isso faz o número de entradas por backend diferir em no máximo uma unidade. Na prática os autores escolhem M maior que 100 vezes o número de backends N, para limitar a diferença na fatia de espaço de hash a cerca de 1%. Pesos distintos de backends podem ser obtidos alterando a frequência relativa dos turnos.
Trade-offs e experiência operacional: balanceamento versus interrupção mínima
Hashing consistente clássico (Karger) e rendezvous hashing priorizam a interrupção mínima: quando backends mudam, poucas atribuições se alteram. O Maglev inverte a prioridade, por duas razões. Primeiro, ele precisa balancear a carga o mais uniformemente possível; do contrário, os backends teriam de ser superdimensionados para o pico. Segundo, em regime estável mudanças na tabela não causam resets de conexão, porque a afinidade entre conexões e Maglevs não muda; só quando ela muda os resets são proporcionais ao número de entradas alteradas. Nos experimentos com 1000 backends, o Maglev hashing deu balanceamento quase perfeito com qualquer tamanho de tabela; com tabela de 65537 entradas, Karger e rendezvous exigiram superprovisionamento de 29,7% e 49,5% respectivamente, caindo para 10,3% e 12,3% com 655373 entradas. Em contrapartida, o Maglev hashing é mais resiliente a mudanças de backend quando a tabela é maior, mas o tempo de geração da tabela cresce de 1,8 ms para 22,9 ms, e como há uma tabela por VIP o tamanho não pode crescer indefinidamente; o padrão é 65537. Na operação, os Maglevs eram originalmente implantados em pares ativo-passivo, mas migraram para o modelo ECMP com todas as máquinas ativas, ganhando capacidade, eficiência e simplicidade, já que o Maglev hashing protege contra flaps ocasionais de ECMP.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.