Conceitos
Maglev hashing e rastreamento de conexões
Intuição
Imagine uma recepção com vários atendentes e uma fila de clientes: a regra é que quem já começou a ser atendido por alguém continua com essa mesma pessoa até o fim. Para isso cada atendente anota num caderninho quem está atendendo. Mas o caderninho tem poucas páginas e, às vezes, a fila é redistribuída entre recepções diferentes, que não enxergam o caderno umas das outras. Então todas combinam antes uma tabela fixa de "cliente de tipo X vai para o atendente Y", montada de forma que cada atendente fique com praticamente a mesma quantidade de clientes. Assim, mesmo sem consultar o caderno, qualquer recepção chega à mesma resposta.
Como funciona
O Maglev é um balanceador de carga de rede em software: cada máquina Maglev anuncia os VIPs ao roteador via BGP com o mesmo custo, e o roteador distribui os pacotes entre elas por ECMP. O forwarder calcula o hash da 5-tupla (IP e porta de origem, IP e porta de destino, protocolo), consulta uma tabela de conexões local de tamanho fixo que mapeia esse hash ao backend e, se não houver entrada, escolhe um backend pelo Maglev hashing e registra a decisão na tabela. A tabela local sozinha não basta, por dois motivos: o ECMP pode redistribuir tráfego entre Maglevs quando o conjunto de máquinas muda (como em upgrades em rolling), e a tabela é finita e pode encher sob carga alta ou SYN flood. Nesses casos o hash consistente dá a todos os Maglevs a mesma escolha sem compartilhar estado. O Maglev hashing preenche uma tabela de lookup de tamanho M (primo): cada backend tem uma lista de preferência, uma permutação das posições da tabela derivada de dois hashes do seu nome (offset e skip), e os backends se revezam ocupando a posição preferida ainda livre até a tabela ficar completa. Com isso o número de entradas por backend difere em no máximo uma unidade, e pesos distintos podem ser obtidos alterando a frequência relativa dos turnos. Diferentemente do hash consistente clássico (Karger) e do rendezvous hashing, que priorizam a interrupção mínima, o Maglev prioriza o balanceamento uniforme, aceitando que mudanças na tabela alterem mais atribuições. Os autores escolhem M maior que 100 vezes o número de backends para limitar a diferença de fatia a cerca de 1%; o padrão é 65537, pois há uma tabela por VIP e tabelas maiores levam mais tempo para gerar (de 1,8 ms para 22,9 ms nos experimentos).
Na prática
No paper, com 1000 backends, o Maglev hashing deu balanceamento quase perfeito com qualquer tamanho de tabela, enquanto com 65537 entradas Karger e rendezvous exigiram superprovisionamento de 29,7% e 49,5%; esse balanceamento evita ter de superdimensionar os backends para o pico. Na operação do Google, os Maglevs migraram de pares ativo-passivo para o modelo ECMP com todas as máquinas ativas, ganhando capacidade, eficiência e simplicidade, porque o Maglev hashing protege contra flaps ocasionais de ECMP. Considere essa combinação (tabela de conexões por fluxo, hash consistente como fallback e ECMP na frente) ao projetar um balanceador L4 distribuído e sem estado compartilhado, em que uniformidade de carga importa mais do que mover o mínimo de fluxos a cada mudança.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.