Um bom dia para trie-hard: economizando 1% de computação

Motivação

• A rede global da Cloudflare processa mais de 60 milhões de requisições HTTP por segundo
• Reduziu o uso de CPU e melhorou a capacidade de processamento do CDN usando um novo crate open source em Rust
• Pingora é o núcleo do serviço de proxy da Cloudflare baseado em Rust, e foi disponibilizado como open source
• O serviço Pingora-origin tem o papel de encaminhar as requisições do usuário ao destino real
• Quando a requisição sai da Cloudflare, é necessário remover informações internas
• Esse trabalho acontece com muita frequência e representa 1,7% do uso de CPU

Benchmarking

• O crate Rust Criterion foi usado para medir o desempenho da função em nanossegundos
• A função original clear_internal_headers levava em média 3,65µs

Reduzindo operações de leitura

• As operações de leitura foram reduzidas invertendo a direção da remoção dos headers
• Com essa mudança, o tempo de execução da função melhorou de 3,65µs para 1,53µs
• O uso de CPU caiu de 1,71% para 0,717%

Busca em estruturas de dados

• Foi testada uma abordagem para armazenar e buscar headers internos usando um hashmap
• O tempo de leitura do hashmap é linear, proporcional ao tamanho da chave
• Outras estruturas de dados, como conjunto ordenado ou máquina de estados, também foram testadas
• A implementação com expressões regulares foi duas vezes mais lenta que o hashmap

Uso de trie

• Trie é uma estrutura de dados em árvore usada para busca por prefixo ou sistemas de autocomplete
• O trie consegue identificar rapidamente quando uma string não está presente
• Implementações existentes de trie eram mais lentas que o hashmap
• A Cloudflare desenvolveu sua própria implementação otimizada de trie, chamada trie-hard

Trie Hard

• O trie-hard armazena relações entre nós nos bits de inteiros e usa memória contígua para ganhar velocidade
• Reduziu o tempo de execução da função clear_internal_headers para 0,93µs
• O uso de CPU caiu de 1,71% para 0,43%
• Em produção real, o desempenho do trie-hard correspondeu ao observado nos benchmarks

Conclusão

• É importante identificar e otimizar as partes lentas do código
• Pequenas otimizações podem se acumular e trazer grandes ganhos de desempenho
• A Connected Cloud da Cloudflare oferece recursos como proteção de rede, aceleração de aplicações de internet e defesa contra ataques DDoS

Resumo do GN⁺

• A Cloudflare reduziu o uso de CPU e melhorou a capacidade de processamento do CDN com um novo crate open source em Rust
• Otimizou a remoção de headers internos no serviço Pingora-origin, reduzindo o uso de CPU em 1,28%
• Desenvolveu o trie-hard, sua própria implementação otimizada de trie, melhorando significativamente o desempenho
• O artigo destaca a importância da otimização de código e da escolha de estruturas de dados, mostrando que pequenas otimizações podem gerar grandes ganhos de desempenho
• Projetos com funcionalidades semelhantes incluem NGINX e HAProxy

[GN⁺]

Comentários do Hacker News

• Houve várias especulações sobre a forma como a Cloudflare armazena e remove cabeçalhos internos

  • uso de um dicionário ou estrutura de dados separada
  • um único cabeçalho contendo todos os metadados internos
  • prefixar todos os cabeçalhos, com os internos começando com 'I' e os externos com 'E'
  • todos os cabeçalhos internos começando com "CFInt"
  • não esperavam que funcionasse com uma lista específica de cabeçalhos considerados internos
  • a web já está cheia de sinais ambíguos e nomes de cabeçalhos
  • é estranho que uma empresa de grande porte como a Cloudflare use um mecanismo tão propenso a erros

• No início, acharam ineficiente mapear caracteres UTF-8 para uma bitmask

  • com 32 bits, dá para incluir a-z e seis caracteres especiais
  • com 64 bits, dá para incluir maiúsculas A-Z e seis caracteres especiais
  • isso oferece espaço suficiente para cabeçalhos HTTP e permite um algoritmo de correspondência rápido
  • essa técnica é um Bloom Filter
  • foi desenvolvida nos anos 1970, quando os recursos eram limitados, mas ainda continua útil hoje

• Houve questionamentos sobre se a otimização da Cloudflare realmente vale a pena

  • economizou cerca de 500 núcleos de CPU
  • não sabem qual é o custo da Cloudflare, mas estimam uma economia de algumas dezenas de milhares de dólares
  • há dúvidas se dá para esperar um ROI positivo para o esforço de engenharia
  • talvez fosse melhor aplicar o filtro na etapa de desserialização para que os cabeçalhos nem fossem gerados

• Não entendem muito de otimização de estruturas de dados, mas se surpreenderam por terem descartado tabelas hash tão rapidamente

  • achavam que uma tabela hash seria mais rápida ao buscar em uma tabela estática

• Foi usada uma estrutura de dados fancy para montar os itens a remover e, com base nisso, removê-los do mapa de cabeçalhos

  • foi fornecido um link para o código relacionado à chamada de "remove_header"

• Finalmente saiu um post de blog usando trie

  • os problemas sobre trie não foram em vão

• Queriam saber se testaram um Bloom Filter pequeno

  • uma convolução rápida na chave do cabeçalho e um teste de Bloom Filter poderiam evitar percorrer a trie

• Queriam saber se tentaram uma tabela hash perfeita, já que estão casando um conjunto estático de itens

  • isso poderia ser reduzido a algumas operações aritméticas e uma única comparação de string

• A otimização é interessante

  • queriam saber se era possível marcar os cabeçalhos como internos no momento da criação da requisição
  • isso tornaria a filtragem na saída mais simples

• Queriam saber por que o crate regex não funcionou melhor

  • ele deveria compilar várias buscas por strings literais em um autômato Aho-Corasick