A Cloudflare conseguiu recuperar mais de 100 terabytes de memória RAM em sua rede global após redesenhar parte do algoritmo de distribuição de solicitações do serviço Pingora Backend Router (PBR). A melhoria resultou de uma combinação de compressão da representação dos pontos de hash, redução do número desses pontos com base em análise estatística e uma migração gradual que preservou a estabilidade do cache e do tráfego para os servidores de origem.
O problema na distribuição de solicitações
A Cloudflare usa a biblioteca pingora-ketama para implementar consistent hashing, um método que ajuda a direcionar solicitações armazenáveis em cache para o mesmo servidor sempre que possível. Isso permite manter uma única cópia do arquivo dentro do centro de dados e oferecer um caminho estável para acessá-lo.
Porém, usar um único ponto de hash por servidor pode causar uma grande variação nos tamanhos dos intervalos que os servidores possuem no anel de hash e, consequentemente, uma variação nas cargas de trabalho. Por isso, o Pingora usa um grande número de hashes virtuais por servidor, com pesos associados à capacidade de armazenamento. Além disso, são criados anéis separados para diferentes conjuntos de características e restrições. O acúmulo desses anéis chegou, em alguns casos, a consumir 6 gigabytes por processo.
Otimização da representação dos dados e redução dos hashes
Cada elemento que representava um ponto no anel era composto por um valor de hash de 32 bits e um índice de 32 bits para o servidor, totalizando oito bytes na memória. A equipe da Cloudflare percebeu que, na prática, o índice não precisava de mais de 16 bits, pois o serviço não coordenaria mais de cerca de 65 mil servidores ao mesmo tempo.
Reduzir o tipo do índice, por si só, não foi suficiente devido às regras de alinhamento do Rust, pois a estrutura continuaria tendo oito bytes. Por isso, a Cloudflare passou a armazenar o valor e o índice em um array bruto de seis bytes, com funções para acessar cada um deles. Essa mudança reduziu em 25% o consumo de memória relacionado ao hash.
O maior ganho, porém, veio da revisão do número de hashes. O serviço usava um valor-base de 160 pontos por servidor, multiplicado pelo peso do servidor associado à capacidade de armazenamento. A análise mostrou que grandes aumentos no número de hashes proporcionam melhorias decrescentes na margem de erro; no exemplo discutido pela Cloudflare, adicionar os últimos 90 mil hashes reduziu o erro em apenas cerca de 0,7%.
Além disso, usar valores de hash de 32 bits torna as colisões mais prováveis à medida que o número de pontos aumenta, o que pode acrescentar um erro inesperado à distribuição. Com base nos cálculos e nas simulações, a Cloudflare reduziu em 90% o número de hashes por servidor sem aumento perceptível do erro, o que contribuiu para as economias finais.
O que muda na prática?
Trocar o anel de hash em toda a rede de uma só vez não era uma opção segura, pois redistribuiria as solicitações e, na prática, causaria a perda de grande parte da eficiência do cache, com a possibilidade de aumentar o tráfego em direção aos servidores de origem. Por isso, o PBR manteve temporariamente os anéis antigo e novo na memória e escolheu entre eles para cada solicitação, proporcionando um caminho claro de reversão.
A migração foi executada em etapas, começando por pequenos locais de validação e depois por centros de dados maiores. O controle da porcentagem de solicitações que usavam o novo anel também foi separado da definição dos centros de dados autorizados a participar. A Cloudflare monitorou os efeitos da seleção de servidores, as versões dos anéis, os erros de conexão, o consumo de memória, o tempo de inicialização, o comportamento do cache e o tráfego para os servidores de origem antes de remover o caminho antigo.
Significado para a engenharia
A experiência mostra que otimizações de baixo nível, como escolher o tamanho de um campo dentro de uma estrutura de dados ou definir um número adequado de pontos de hash, podem ter efeitos amplificados quando aplicadas a uma rede com milhares de servidores. Ao mesmo tempo, o resultado não significa que reduzir a memória seja seguro em todos os sistemas; a precisão da distribuição, as probabilidades de colisão, os pesos dos servidores, as restrições das funcionalidades e a forma de execução da migração são fatores que devem ser medidos antes da mudança.
As alterações passaram a estar disponíveis no pacote pingora-ketama por meio de um recurso do Cargo atualmente não anunciado. A versão v2 oferece suporte ao formato de armazenamento compactado, a um método de ordenação mais rápido e à possibilidade de configurar o número-base de hashes, mantendo a versão v1 e permitindo executar os dois anéis em conjunto e tomar a decisão no nível da solicitação.