Une bonne journée pour trie-hard : économiser 1 % de calcul
(blog.cloudflare.com)- Cloudflare a publié le crate Rust open source trie-hard afin de réduire l’utilisation CPU de Pingora, son proxy basé sur Rust, sur un réseau qui traite en moyenne plus de 60 millions de requêtes HTTP par seconde
- Le goulot d’étranglement se trouvait dans la fonction
clear_internal_headersdepingora-origin, qui supprime les en-têtes utilisés en interne pour le routage, la mesure et l’optimisation sur les requêtes non mises en cache quittant Cloudflare, et s’exécute sur un chemin à 35 millions de requêtes par seconde - L’implémentation existante tentait de supprimer plus de 100 en-têtes internes à chaque requête, prenait en moyenne 3,65 µs, et consommait 1,71 % du temps CPU total de
pingora-origin, soit l’équivalent de 680 cœurs CPU sur 40 000 compute-seconds/s - Parcourir d’abord les en-têtes réels de la requête a ramené la moyenne à 1,53 µs, soit 2,39 fois plus rapide, mais le gain CPU global théorique plafonnait à 0,993 %, ce qui imposait une meilleure structure de recherche
- La nouvelle implémentation de trie a réduit le temps moyen d’exécution à 0,93 µs et, dans l’échantillonnage effectué en production depuis juillet 2024, l’usage CPU réel de
clear_internal_headersest descendu à 0,34 %
Le coût que Cloudflare voulait réduire
- Le réseau mondial de Cloudflare traite en moyenne plus de 60 millions de requêtes HTTP par seconde
- Cette optimisation est partie de Pingora, au cœur de son service de proxy basé sur Rust, et du service de production
pingora-originqui s’exécute dessus pingora-originest responsable de la dernière étape qui envoie les requêtes utilisateur non mises en cache vers le serveur de destination réel, l’origin- Avant que la requête ne quitte l’infrastructure Cloudflare, ce service doit supprimer des en-têtes les informations utilisées pour le routage interne, la mesure et l’optimisation
- À l’échelle mondiale, les requêtes quittant
pingora-originreprésentent 35 millions de requêtes par seconde au moment de la rédaction
La fonction goulot d’étranglement : clear_internal_headers
- La fonction en cause se trouve sur un chemin extrêmement chaud, exécuté pour chaque requête
// 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);
});
}
- À elle seule, cette petite fonction utilise plus de 1,7 % du temps CPU total de
pingora-origin - Le temps CPU total de
pingora-originest de 40 000 compute-seconds par seconde, soit une échelle comparable à 40 000 cœurs CPU saturés exécutant uniquement ce service - Sur ce total, 1,7 %, soit environ 680 cœurs CPU, est donc consacré uniquement à l’évaluation de
clear_internal_headers
Mesure de référence et première amélioration
- Les mesures de performance utilisent le crate Rust criterion
- Criterion agrège plusieurs exécutions isolées pour mesurer le temps du code Rust à la nanoseconde près et fournit aussi un retour sur les améliorations ou régressions de performance dans le temps
- Les entrées de benchmark sont un grand ensemble synthétique de requêtes où les en-têtes internes et non internes sont distribués uniformément
- Le temps moyen d’exécution de l’ancien
clear_internal_headersa été mesuré à 3,65 µs -
Inverser le sens de recherche
- Le code existant exécutait
request_header.remove_header(h)pour chaque élément de la liste des en-têtes internes ; avec plus de 100 en-têtes internes, cela représentait donc plus de 100 évaluations par requête - Une requête moyenne contient bien moins de 100 en-têtes, plutôt 10 à 30, il est donc plus efficace de parcourir les en-têtes réels de la requête et de les chercher dans l’ensemble des en-têtes internes
http::HeaderMapde Rust ne dispose pas encore deretain, il faut donc collecter dans une étape séparée les en-têtes internes à supprimer, puis les retirer- Ce seul changement a réduit le temps moyen d’exécution de 3,65 µs à 1,53 µs, soit une accélération de 2,39×
- En théorie, l’utilisation CPU totale passe de 1,71 % à 0,717 %, soit un gain de 0,993 %
- Le code existant exécutait
Recherche d’une meilleure structure de données
- Après avoir inversé le sens de recherche, il devenait possible de choisir dans quelle structure de données stocker la liste statique des en-têtes internes
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);
});
}
- La première tentative a utilisé
std::HashMap, mais le hachage de clés de type chaîne doit lire tous les octets : il est donc en temps constant par rapport à la taille de la table, mais linéaire par rapport à la longueur de clé L - L’objectif était de trouver une structure de données dont le comportement de lecture soit meilleur que O(L) par rapport à la longueur de clé
-
Alternatives étudiées
- Les ensembles triés comme
BTreeSetutilisent une recherche par comparaison et offrent un comportement en O(log(L)) par rapport à la longueur de clé, mais ils prennent aussi un temps logarithmique par rapport à la taille de l’ensemble - FST, un ensemble trié rapide, était aussi environ 50 ns plus lent qu’une hashmap standard dans les benchmarks
- Les machines à états, comme les parseurs ou les expressions régulières, consomment l’entrée unité par unité et décident à chaque étape si l’évaluation doit continuer, ce qui leur permet d’identifier rapidement les chaînes qui ne correspondent pas
- Les en-têtes internes ne sont présents qu’à hauteur de 1 à 2 par requête en moyenne, ce qui correspond bien à une situation où les cas négatifs dominent
- Une implémentation de
clear_internal_headersbasée sur des expressions régulières prenait environ 2 fois plus de temps que la solution à base de hashmap, mais le résultat restait rapide pour un outil qui n’est pas réputé pour sa vitesse brute
- Les ensembles triés comme
Pourquoi un trie convient
- Un trie est une structure de données en arbre souvent utilisée pour la recherche de préfixes ou l’autocomplétion dans un ensemble connu de chaînes
- Chaque nœud du trie représente une sous-chaîne trouvée dans l’ensemble initial de chaînes, et les liens entre nœuds représentent les caractères qui peuvent suivre un préfixe donné
- En partant du nœud racine, on peut réduire l’espace de recherche dès les premiers caractères possibles, ce qui permet d’écarter rapidement les chaînes absentes
- La lecture dans un trie offre un comportement en O(log(L)) pour les cas sans correspondance, mais reste en O(L) pour les cas avec correspondance
- Plus de 90 % des en-têtes de requête ne sont pas des en-têtes internes, ce qui rend cette approche adaptée à ce cas d’usage dominé par les non-correspondances
-
Limites des implémentations de trie existantes
- Plusieurs implémentations de trie sur crates.io ont été benchmarkées, mais les résultats étaient inférieurs aux attentes
- La plupart des tries sont conçus pour des cas d’usage comme l’autocomplétion réagissant à des événements clavier, où l’optimisation d’un chemin chaud à plusieurs dizaines de millions de requêtes par seconde n’est pas prioritaire
- L’implémentation existante la plus rapide trouvée était radix_trie, mais elle restait 1 µs plus lente que la hashmap
- Une nouvelle implémentation de trie a donc été écrite spécifiquement pour ce cas d’usage
trie-hard et résultats en production
-
Cloudflare a publié le nouveau crate Rust open source trie-hard
-
trie-hardgagne en vitesse en stockant les relations entre nœuds dans les bits d’entiers non signés et en conservant tout l’arbre dans un bloc mémoire contigu -
Dans les benchmarks,
trie-harda réduit le temps moyen d’exécution declear_internal_headersà 0,93 µs -
L’utilisation CPU attendue est de 0,43 %, soit une réduction de 1,28 % de l’utilisation de calcul totale de
pingora-originpar rapport aux 1,71 % initiaux -
Résultats d’échantillonnage réels
trie-hardest exécuté en production depuis juillet 2024- Les mesures de performance sont collectées par échantillonnage statistique des stack traces dans le temps
- Le pourcentage d’utilisation CPU d’une fonction est estimé à partir de la proportion d’échantillons contenant cette fonction
- Les résultats d’échantillonnage en production sont globalement proches des prédictions issues des benchmarks locaux
Implémentation Échantillons de stack trace contenant clear_internal_headersUtilisation CPU réelle Utilisation CPU prévue Originale 19 / 1111 1,71 % n/a Hashmap 9 / 1103 0,82 % 0,72 % trie-hard 4 / 1171 0,34 % 0,43 %
Conclusion côté exploitation
- Avant d’écrire une nouvelle structure de données, il faut d’abord savoir où et dans quelle mesure le code est lent
- Les flame graphs, les outils de profilage et de benchmarking permettent de trouver des gains significatifs même dans des fonctions à l’échelle de la microseconde
- Optimiser une opération déjà très courte peut sembler anodin, mais à l’échelle de dizaines de millions de requêtes par seconde, les petites améliorations s’accumulent et réduisent l’usage global du calcul
1 commentaires
Commentaires sur Hacker News
Si on m’avait demandé de deviner à peu près comment Cloudflare stocke et supprime les en-têtes internes, j’aurais probablement pensé à un dictionnaire ou une structure de données séparée, à un en-tête unique contenant toutes les métadonnées internes, à une distinction interne/externe par préfixe, ou à un préfixe comme
CFIntJe n’aurais sans doute pas imaginé une méthode qui considère comme internes les noms d’en-tête figurant dans une liste donnée. Ça soulève des questions comme : que se passe-t-il si quelqu’un d’autre utilise le même nom, s’il y a des oublis dans le nettoyage, si des programmes exécutés en parallèle n’ont pas la même liste, si l’en-tête
Connectiondésigne un en-tête interne de Cloudflare, ou si l’algorithme de différence d’ensembles est lentLe Web est déjà rempli jusqu’à l’exaspération de signalisation in-band ambiguë et de conventions de nommage d’en-têtes, donc ça paraît étrange qu’une entreprise de la taille de Cloudflare utilise en interne un mécanisme aussi lourd et sujet aux erreurs
cf-cache-statusCela incluait la suppression bidirectionnelle des en-têtes internes au niveau du proxy edge, y compris sur l’entrant
L’approche par liste a des inconvénients, mais aussi beaucoup d’avantages. Quand on pointe les défauts potentiels de cette approche, on semble souvent ignorer l’histoire et les difficultés qui apparaissent à l’échelle de Cloudflare. Une liste énumérée est la méthode la plus simple et la plus souple, et elle n’exige aucun accord préalable sur la structure des clés d’en-tête. Vu le nombre d’équipes chez Cloudflare, les possibilités d’acquisitions technologiques, etc., ce point a dû être important
Avec le préremplissage, on combine en fait ces idées tout en fixant le nombre d’en-têtes internes par requête. À ce stade, il suffirait d’utiliser une table de hachage chaînée qui préserve l’ordre de création, puis de supprimer les N premiers éléments de la liste finale à renvoyer au client
J’ai brièvement réfléchi à l’effet consistant à mapper les caractères UTF-8 sur un bitmask, et au début ça ne me semblait pas très malin. Puis j’ai réalisé qu’en 32 bits on peut caser
a-zet 6 caractères spéciaux, et qu’en 64 bits on peut ajouter les majusculesA-Zet 6 caractères spéciaux de plusC’est largement suffisant pour les en-têtes HTTP, et comme il suffit de masquer et comparer quelques entiers, ça donne un algorithme de correspondance très rapide. Il suffit aussi d’une seule consultation d’une table de 256 mots pour savoir à quel bit correspond chaque caractère
Ce que l’auteur a omis, c’est que cette technique est techniquement un filtre de Bloom. Ce qui rend ces choses intéressantes, c’est que même si c’est une optimisation apparue à une époque où les ressources de calcul étaient bien plus limitées — ici en 1970 — on continue malgré tout à retrouver les mêmes vieilles optimisations dans des recoins du monde réel
https://en.wikipedia.org/wiki/Bloom_filter
trie-hardet un filtre de Bloom. Un filtre de Bloom est probabiliste et utilise du hachage. C’est utile quand on veut tolérer de rares faux positifs tout en n’acceptant aucun faux négatif, mais ce n’est pas le besoin ici. Ici, il faut de l’exactitude, et le hachage lui-même est justement l’étape à battreEn réalité, c’est plus proche d’une version améliorée ou dérivée de l’algorithme de Liang utilisé dans TeX pour stocker les dictionnaires de césure. L’article traite l’algorithme de Bloom sous le nom de “superimposed coding”, ce qui évoque fortement l’époque où la mémoire était la ressource la plus précieuse. Ça devrait te plaire ^_^
https://tug.org/docs/liang/liang-thesis.pdf
Les données présentées pour démontrer le gain manquent en réalité de puissance statistique pour le montrer. L’échantillon n’est pas suffisant
En faisant une analyse très simple dans R, on obtient
prop.test(c(9, 4), c(1103,1171)), et avec le test d’égalité de deux proportions avec correction de continuité, on a une valeur de p de 0.222Une valeur de p de 0.22 n’est pas inférieure au magique 0.05, et l’intervalle de confiance à 95 % suggère que le trie pourrait en réalité être légèrement moins bon
L’analyse a priori laisse penser que le trie est meilleur, et il y a quelques faibles indices en ce sens, mais il vaudrait mieux prendre beaucoup plus d’échantillons pour être certain de l’ampleur du gain
Expliquer le nombre de comparaisons en notation grand O pour analyser les performances semble maladroit. Une comparaison, c’est à peu près 1 cycle, et avec le parallélisme au niveau des instructions et le SIMD, on peut même en faire plusieurs en un cycle
Le vrai goulot d’étranglement et la vraie source de lenteur, c’est la mémoire. Accéder à la mémoire peut coûter des milliers de cycles, et s’il faut un parcours du TLB ou une interruption système, on peut monter à des dizaines ou des centaines de milliers de cycles. Si on veut utiliser le grand O, ce serait pour estimer le nombre de défauts de cache
À leur place, j’utiliserais une fonction de hachage parfaite sur mesure et l’astuce
popcountde Phil Bagwell. Ce serait probablement plus rapide que d’autres solutions qui font plusieurs accès mémoireLe CPU est rapide, la mémoire est lente
Je ne prétends pas être très calé en optimisation de structures de données, mais j’ai été surpris qu’ils écartent si vite la table de hachage, surtout si l’on considère que la table des éléments à rechercher est statique. J’ai du mal à croire qu’une table de hachage spécialement optimisée ne serait pas plus rapide que leur implémentation de trie
Pour cet usage, c’est un avantage que le hachage ne peut pas rattraper. Tout le reste consiste à suffisamment réduire les facteurs constants du trie pour que cet avantage initial se traduise en performances réelles
FxHashMap, plus rapide questd::collections::HashMap: https://github.com/rust-lang/rustc-hashS’il y a environ 100 éléments statiques,
o1hashpourrait aussi convenir : https://github.com/rurban/smhasher/blob/master/o1hash.hCet article construit un ensemble
to_removeavec une jolie structure de données, puis le parcourt pour supprimer les éléments de la map d’en-têtes de baseL’appel à
remove_headersemble être ce code : https://docs.rs/pingora-http/0.3.0/src/pingora_http/lib.rs.html#576Cette fonction appelle ensuite
.remove()sur deux autres structures de données, et toutes deux finissent par retomber sur cet énorme morceau de code : https://docs.rs/http/latest/src/http/header/map.rs.html#1550Enfin un billet de blog où apparaît un trie. Mes problèmes de trie sur LeetCode n’auront donc pas servi à rien ;)
Cela dit, ce n’est clairement pas un outil que je sors souvent
C’est un parseur de user agents pour Go : https://github.com/medama-io/go-useragent
Comme ce genre de problème repose habituellement sur beaucoup de parsing par expressions régulières, c’était sympa de pouvoir essayer une approche un peu plus originale
Si l’ensemble des éléments à faire correspondre est statique, je me demande s’ils ont essayé une table de hachage parfaite. On réduirait cela à quelques opérations arithmétiques puis une comparaison de chaîne, et il serait intéressant de voir comment cela se compare à un trie
En théorie, si l’on utilise des expressions régulières, on fait la correspondance via une machine à états, donc on devrait obtenir des performances en O(k) dans le pire des cas, similaires à celles d’un trie. Mais si j’ai bien compris, les bibliothèques de regex utilisent du backtracking au lieu de construire une vraie machine à états, donc les performances ne sont plus en O(k)
Je trouve quand même surprenant qu’ils n’aient pas trouvé de bibliothèque de regex existante, performante et fondée sur une machine à états. Elle devrait avoir des performances comparables à un trie, mais en pratique des facteurs comme les motifs d’accès mémoire ou les performances de certaines opérations arithmétiques pèsent davantage, donc c’est difficile à deviner
Ont-ils essayé un tout petit filtre de Bloom ? En traitant rapidement les clés d’en-tête de manière quasi convolutive puis en les comparant au filtre de Bloom, on pourrait peut-être éviter complètement le parcours du trie dans la plupart des cas pour quelques cycles seulement
Il semble aussi y avoir des options comme le SIMD, les instructions CRC intégrées ou une taille de filtre de Bloom de 256 bits
Une approche plus simple pourrait aussi avoir de la valeur. En analysant la fréquence des succès et des échecs des nœuds du trie, on pourrait peut-être trouver certaines positions de caractères dont le taux d’échec est plus élevé que celui du premier caractère. Vérifier d’abord ces positions particulières pourrait accélérer encore les choses. Bien sûr, cela suppose que les données d’en-tête soient en elles-mêmes assez régulières
Voici ce que j’en pense. Premièrement, est-ce que ça vaut le coup ? On dirait qu’ils ont économisé l’équivalent d’environ 500 cœurs CPU, mais je ne sais pas s’il s’agit de vrais cœurs ou si cela inclut aussi les cœurs hyperthreadés
Je ne connais pas les coûts de Cloudflare, mais cela correspond probablement à un nombre de serveurs à un seul chiffre, et les économies doivent sans doute se situer à quelques dizaines de milliers de dollars par an. Ce n’est pas négligeable, mais je ne sais pas si on peut en attendre un ROI positif par rapport à l’investissement d’ingénierie
Deuxièmement, si on va à ce niveau de détail, je me demande s’ils ont envisagé de mettre un filtre à l’étape de désérialisation pour éviter que les en-têtes soient créés dès le départ
La réduction de la consommation électrique continue aussi, tout comme celle des émissions carbone
Je préfère voir une entreprise essayer de rendre quelque chose 1 % plus rapide que faire une idiotie du genre analyser des en-têtes avec de l’IA pour vendre des sandales
Cette valeur peut se chiffrer à un million de dollars