O bom dia do trie-hard: economizando 1% de computação
(blog.cloudflare.com)- A Cloudflare lançou o crate open source em Rust trie-hard para reduzir o uso de CPU do proxy baseado em Rust Pingora em uma rede que processa em média mais de 60 milhões de requisições HTTP por segundo
- O gargalo era a função
clear_internal_headersdepingora-origin, que remove cabeçalhos usados para roteamento interno, medição e otimização em requisições não armazenadas em cache que saem da Cloudflare, e é executada no caminho de 35 milhões de requisições por segundo - A implementação anterior tentava remover mais de 100 cabeçalhos internos em toda requisição, levando em média 3.65µs, e consumia 1,71% do tempo total de CPU de
pingora-origin, o equivalente a 680 núcleos de CPU dentre 40 mil compute-seconds/s - Percorrer primeiro os cabeçalhos reais da requisição reduziu a média para 1.53µs, ficando 2,39 vezes mais rápido, mas a economia total de CPU teoricamente chegava a apenas 0,993%, então era necessária uma estrutura de busca melhor
- A nova implementação de trie reduziu o tempo médio de execução para 0.93µs e, nas medições por amostragem em produção desde julho de 2024, o uso real de CPU de
clear_internal_headerscaiu para 0,34%
O custo que a Cloudflare queria reduzir
- A rede global da Cloudflare processa em média mais de 60 milhões de requisições HTTP por segundo
- Esta otimização começou no Pingora, núcleo do serviço de proxy baseado em Rust, e no serviço de produção
pingora-originque roda sobre ele - O
pingora-originé responsável pela etapa final de enviar as requisições não armazenadas em cache dos usuários ao servidor de destino real, o origin - Antes que a requisição deixe a infraestrutura da Cloudflare, esse serviço precisa remover dos cabeçalhos as informações usadas para roteamento interno, medição e otimização
- Globalmente, no momento da publicação, saem de
pingora-origin35 milhões de requisições por segundo
A função gargalo: clear_internal_headers
- A função problemática fica em um caminho extremamente quente, executado em todas as requisições
// PERF: heavy function: 1.7% CPU time
pub fn clear_internal_headers(request_header: &mut RequestHeader) {
INTERNAL_HEADERS.iter().for_each(|h| {
request_header.remove_header(h);
});
}
- Só essa pequena função usava mais de 1,7% do tempo total de CPU de
pingora-origin - O tempo total de CPU de
pingora-originé de 40.000 compute-seconds por segundo, uma escala equivalente a 40 mil núcleos de CPU saturados executando apenas esse serviço - Desses, 1,7%, ou cerca de 680 núcleos de CPU, eram gastos apenas avaliando
clear_internal_headers
Medição de base e primeira melhoria
- Para medir desempenho, foi usado o crate Rust criterion
- O Criterion agrega várias execuções isoladas para medir o tempo do código Rust em nanosegundos e também fornece feedback sobre melhorias e regressões de desempenho ao longo do tempo
- A entrada do benchmark foi um grande conjunto sintético de requisições, com distribuição equilibrada entre cabeçalhos internos e não internos
- O tempo médio de execução da
clear_internal_headersoriginal foi medido em 3.65µs -
Invertendo a direção da busca
- O código anterior executava
request_header.remove_header(h)para cada item da lista de cabeçalhos internos, então, com mais de 100 cabeçalhos internos, fazia mais de 100 avaliações por requisição - Como uma requisição média tem bem menos cabeçalhos do que isso, algo em torno de 10 a 30, percorrer os cabeçalhos reais da requisição e procurar no conjunto de cabeçalhos internos reduz o número de leituras
- O
http::HeaderMapdo Rust ainda não temretain, então foi preciso primeiro coletar os cabeçalhos internos a remover em uma etapa separada e depois apagá-los - Só essa mudança reduziu o tempo médio de execução de 3.65µs para 1.53µs, um ganho de 2,39 vezes
- Em teoria, o uso total de CPU cairia de 1,71% para 0,717%, com uma economia de 0,993%
- O código anterior executava
Buscando uma estrutura de dados melhor para pesquisa
- Depois de inverter a direção da busca, passou a ser possível escolher em qual estrutura de dados armazenar a lista estática de cabeçalhos internos
pub fn clear_internal_headers(request_header: &mut RequestHeader) {
let to_remove = request_header
.headers
.keys()
.filter_map(|name| INTERNAL_HEADER_SET.get(name))
.collect::<Vec<_>>();
to_remove.into_iter().for_each(|k| {
request_header.remove_header(k);
});
}
- A primeira tentativa foi
std::HashMap, mas o hash de chaves string precisa ler todos os bytes, então, embora seja tempo constante em relação ao tamanho da tabela, continua sendo tempo linear em relação ao comprimento da chave L - O objetivo era encontrar uma estrutura de dados com comportamento de leitura melhor que O(L) em relação ao comprimento da chave
-
Alternativas avaliadas
- Conjuntos ordenados como
BTreeSetusam busca baseada em comparação e oferecem comportamento O(log(L)) em relação ao comprimento da chave, mas também exigem tempo logarítmico em relação ao tamanho do conjunto - O FST, um conjunto ordenado rápido, também ficou cerca de 50ns mais lento que o hashmap padrão nos benchmarks
- Máquinas de estado como parsers ou expressões regulares recebem a entrada uma unidade por vez e decidem a cada etapa se vale a pena continuar a avaliação, o que permite identificar rapidamente strings que não batem
- Como há em média apenas 1 ou 2 cabeçalhos internos por requisição, este caso de uso é dominado por casos negativos
- Uma implementação de
clear_internal_headerscom expressão regular levou cerca de 2 vezes mais tempo que a solução com hashmap, mas ainda foi um resultado rápido considerando que não é uma ferramenta conhecida por velocidade bruta
- Conjuntos ordenados como
Por que trie faz sentido
- Um trie é uma estrutura de dados em árvore frequentemente usada para busca por prefixo ou autocomplete em conjuntos conhecidos de strings
- Cada nó de um trie representa uma substring encontrada no conjunto inicial de strings, e as conexões entre nós representam os caracteres que podem vir depois de um determinado prefixo
- Começando pelo nó raiz, é possível reduzir o espaço de busca desde o primeiro caractere possível, excluindo rapidamente strings que não pertencem ao conjunto
- A leitura em trie oferece comportamento O(log(L)) para casos de não correspondência, embora os casos de correspondência ainda sejam O(L)
- Como mais de 90% dos cabeçalhos de requisição não são internos, esse padrão se encaixa bem neste caso de uso, que tem muitos casos de não correspondência
-
Limitações das implementações de trie existentes
- Várias implementações de trie em crates.io foram colocadas em benchmark, mas os resultados ficaram abaixo do esperado
- A maioria dos tries é voltada a casos de uso como autocomplete reagindo a eventos de teclado, e não tem como prioridade otimizar caminhos quentes com dezenas de milhões de requisições por segundo
- A implementação existente mais rápida encontrada foi radix_trie, mas ainda assim ficou 1µs mais lenta que o hashmap
- No fim, foi escrita uma nova implementação de trie voltada especificamente para este caso de uso
trie-hard e os resultados em produção
-
A Cloudflare lançou o novo crate open source em Rust trie-hard
-
O
trie-hardganha velocidade ao armazenar as relações entre nós nos bits de inteiros sem sinal e manter toda a árvore em um bloco contíguo de memória -
Nos benchmarks, o
trie-hardreduziu o tempo médio de execução declear_internal_headerspara 0.93µs -
O uso de CPU previsto é de 0,43%, o que representa uma redução de 1,28% no uso total de computação de
pingora-originem comparação com os 1,71% originais -
Resultados reais por amostragem
- O
trie-hardestá em produção desde julho de 2024 - A medição de desempenho foi coletada por amostragem estatística de stack traces ao longo do tempo
- A proporção de amostras contendo uma determinada função foi usada para estimar o uso de CPU dessa função
- Os resultados de amostragem em produção ficaram, em geral, próximos das previsões dos benchmarks locais
Implementação Amostras de stack trace com clear_internal_headersUso real de CPU Uso de CPU previsto Original 19 / 1111 1,71% n/a Hashmap 9 / 1103 0,82% 0,72% trie-hard 4 / 1171 0,34% 0,43% - O
Conclusão do ponto de vista operacional
- Antes de escrever uma nova estrutura de dados, é preciso entender onde e quanto o código está lento
- Com flame graphs, profiling e ferramentas de benchmark, é possível encontrar economias significativas até em funções medidas em microssegundos
- Otimizar operações que já são muito curtas pode parecer trivial, mas na escala de dezenas de milhões de requisições por segundo, pequenas melhorias se acumulam e reduzem o uso total de computação
1 comentários
Opiniões do Hacker News
Se me pedissem para chutar, por alto, como a Cloudflare armazena e remove headers internos, eu teria pensado em um dicionário ou estrutura de dados separada, um único header contendo todos os metadados internos, uma forma de distinguir interno/externo por prefixo, ou um prefixo como
CFIntAcho que eu não teria pensado no método de considerar como header interno nomes de headers que estão em uma lista específica. Isso levanta perguntas como: o que acontece se outra pessoa usar o mesmo nome, se houver falha na limpeza, se programas rodando simultaneamente tiverem listas diferentes, se o header
Connectionapontar para um header interno da Cloudflare, ou se o algoritmo de diferença de conjuntos for lentoA Web já está cheia de sinalização in-band e nomenclatura de headers irritantemente ambíguas, então parece estranho que uma empresa do porte da Cloudflare use internamente um mecanismo tão trabalhoso e propenso a erros
cf-cache-statusIsso incluía remover headers internos em ambas as direções no proxy de borda, inclusive no tráfego de entrada
O método por lista tem desvantagens, mas também muitas vantagens. Ao apontar as possíveis falhas dessa abordagem, muita gente parece ignorar a história e as dificuldades que surgem na escala da Cloudflare. Uma lista enumerada é a forma mais simples e flexível, e não exige acordo prévio sobre a estrutura das chaves de header. Considerando o número de equipes da Cloudflare, a possibilidade de aquisições de tecnologia etc., isso provavelmente foi importante
O pré-preenchimento, na prática, combina essas ideias e fixa o número de headers internos de cada requisição. Nesse ponto, seria possível usar uma tabela hash encadeada que preserva a ordem de criação e, na lista final a ser devolvida ao cliente, remover apenas os primeiros N itens
Pensei por um momento no efeito de mapear caracteres UTF-8 como máscaras de bits e, de início, isso não pareceu muito esperto. Mas então percebi que 32 bits comportam
a-ze 6 caracteres especiais, e 64 bits comportam tambémA-Ze mais 6 caracteres especiaisPara headers HTTP, é espaço suficiente, e basta mascarar e comparar alguns inteiros, então vira um algoritmo de correspondência muito rápido. A correspondência entre cada caractere e cada bit também exige só uma consulta a uma tabela de 256 palavras
O ponto que o autor deixou passar é que essa técnica é, tecnicamente, um filtro de Bloom. O que torna essas coisas interessantes é que se trata de uma otimização de uma época em que os recursos computacionais eram muito mais limitados do que hoje — neste caso, de 1970 — e, ainda assim, continuamos usando a mesma velha otimização em cantos do mundo real
https://en.wikipedia.org/wiki/Bloom_filter
trie-harde um filtro de Bloom. Um filtro de Bloom é probabilístico e usa hashing. Ele é bom quando você pode aceitar falsos positivos raros em troca de não ter falsos negativos, mas não é isso que é necessário aqui. Aqui é preciso exatidão, e o próprio hashing é a etapa que precisa ser vencidaIsso está mais para uma versão aprimorada ou uma variação do algoritmo de Liang, usado no TeX para armazenar dicionários de hifenização. A tese trata o algoritmo de Bloom como “superimposed coding”, o que remete fortemente a uma época em que memória era o recurso mais precioso. Acho que você vai gostar ^_^
https://tug.org/docs/liang/liang-thesis.pdf
Os dados apresentados para comprovar o ganho, na prática, não têm poder estatístico suficiente para mostrar isso. A amostra não é grande o bastante
Uma análise bem simples em R seria
prop.test(c(9, 4), c(1103,1171)), e o teste de igualdade de duas proporções com correção de continuidade dá um valor-p de 0,222Um valor-p de 0,22 não é menor que o mágico 0,05, e o intervalo de confiança de 95% sugere que o trie poderia, na verdade, ser ligeiramente pior
Pela análise prévia, parece que o trie deve ser melhor e há alguma evidência fraca, mas seria melhor coletar uma amostra muito maior para ter certeza de quanto ele é melhor
Para o objetivo de analisar desempenho, explicar o número de comparações em notação Big O soa estranho. Uma comparação custa algo como 1 ciclo, e com paralelismo em nível de instrução e SIMD é possível fazer várias em um ciclo
O gargalo real e a fonte de lentidão é a memória. Acessar a memória pode custar milhares de ciclos, e, se for necessário um walk de TLB ou uma interrupção do SO, pode chegar a dezenas ou centenas de milhares de ciclos. Se quiser usar Big O, deveria usá-la para estimar o número de cache misses
Eu provavelmente usaria uma função hash perfeita sob medida e o truque de
popcountdo Phil Bagwell. Seria mais rápido do que outras soluções que fazem várias consultas à memóriaA CPU é rápida, a memória é lenta
Não sou exatamente especialista em otimização de estruturas de dados, mas, especialmente considerando que a tabela alvo da busca é estática, achei surpreendente terem descartado tabelas hash tão rapidamente. É difícil acreditar que uma tabela hash especialmente otimizada não seria mais rápida que a implementação de trie deles
Para esse uso, essa é uma vantagem que o hash não consegue acompanhar. O resto das técnicas serve para reduzir o fator constante da trie o suficiente para que essa vantagem inicial seja recompensada no desempenho real
std::collections::HashMap: https://github.com/rust-lang/rustc-hashCom cerca de 100 itens estáticos, o o1hash também deve funcionar: https://github.com/rurban/smhasher/blob/master/o1hash.h
O artigo cria o conjunto
to_removecom uma estrutura de dados sofisticada e depois o percorre removendo itens do mapa de cabeçalhos básicoA chamada a
remove_headerparece ser este código: https://docs.rs/pingora-http/0.3.0/src/pingora_http/lib.rs.html#576Essa função chama
.remove()em duas outras estruturas de dados, e ambas acabam descendo para este código enorme: https://docs.rs/http/latest/src/http/header/map.rs.html#1550Finalmente saiu um post de blog com tries. Aqueles problemas de trie no LeetCode não foram em vão ;)
Ainda assim, certamente não é uma ferramenta que eu pegue com frequência
É um parser de user agent para Go: https://github.com/medama-io/go-useragent
Normalmente esse tipo de problema depende de muita análise com expressões regulares, então foi bom poder tentar uma abordagem um pouco mais nova
Se o conjunto de itens a casar é estático, fico curioso se tentaram uma tabela de hash perfeito. Ela deveria se reduzir a algumas operações aritméticas seguidas de uma comparação de string, e seria interessante ver como se compara à trie
Em teoria, usando regex, o casamento é feito com uma máquina de estados, então deveria ter desempenho O(k) no pior caso, parecido com uma trie. Mas, pelo que entendo, bibliotecas de regex usam backtracking em vez de construir uma máquina de estados real, então o desempenho deixa de ser O(k)
É surpreendente que não tenham encontrado uma biblioteca de regex baseada em máquina de estados já existente e com bom desempenho. Ela deveria ter desempenho parecido com o de uma trie, mas, na prática, fatores como padrão de acesso à memória e desempenho de certas operações aritméticas influenciam mais a fundo, então é difícil especular
Será que tentaram um filtro de Bloom bem pequeno? Se processarem rapidamente a chave do cabeçalho quase como uma convolução e compararem com o filtro de Bloom, parece que daria para evitar por completo a travessia da trie na maioria dos casos, ao custo de poucos ciclos
Parece haver opções como SIMD, instruções CRC nativas e tamanho de filtro de Bloom de 256 bits
Uma abordagem mais simples também pode valer a pena. Ao analisar a frequência de acertos/falhas dos nós da trie, talvez se encontre uma posição específica de caractere com taxa de falha maior que a do primeiro caractere. Verificar essas posições especiais primeiro poderia deixá-la mais rápida. Claro, isso exige a premissa de que os dados dos cabeçalhos sejam, por natureza, bastante regulares
Minha opinião é esta. Primeiro: isso é algo que vale a pena fazer? Parece que economizaram cerca de 500 núcleos de CPU, mas não sei se são núcleos reais ou se incluem também núcleos de hyperthreading
Não sei quais são os custos da Cloudflare, mas isso deve corresponder a uma quantidade de servidores na casa de um dígito, e a economia provavelmente fica na faixa de dezenas de milhares de dólares por ano. Não é desprezível, mas não sei se dá para esperar um ROI positivo em relação ao investimento de engenharia
Segundo: se vão entrar nesse nível de detalhe, fico curioso se consideraram colocar um filtro na etapa de desserialização para que os headers nem sejam criados em primeiro lugar
A redução de energia também continua, e as emissões de carbono diminuem
É bom ver uma empresa tentando tornar algo 1% mais rápido, em vez de fazer alguma besteira como analisar headers com IA para tentar vender sandálias
Esse valor pode ser de um milhão de dólares