Une bonne journée pour trie-hard : économiser 1 % de calcul

Motivation

• Le réseau mondial de Cloudflare traite plus de 60 millions de requêtes HTTP par seconde
• Utilisation d'une nouvelle crate Rust open source pour réduire l'utilisation CPU et améliorer la capacité de traitement du CDN
• Pingora est au cœur du service proxy basé sur Rust de Cloudflare, désormais publié en open source
• Le service Pingora-origin a pour rôle de transmettre les requêtes des utilisateurs vers leur destination réelle
• Lorsque les requêtes quittent Cloudflare, il est nécessaire de supprimer les informations internes
• Cette opération se produit très fréquemment et représente 1,7 % de l'utilisation CPU

Benchmarking

• Utilisation de la crate Rust Criterion pour mesurer les performances de la fonction à l'échelle de la nanoseconde
• La fonction clear_internal_headers d'origine prenait en moyenne 3,65µs

Réduire les opérations de lecture

• Réduction des lectures en inversant le sens de suppression des en-têtes
• Ce changement a amélioré le temps d'exécution de la fonction de 3,65µs à 1,53µs
• Réduction de l'utilisation CPU de 1,71 % à 0,717 %

Recherche dans les structures de données

• Tentative de stockage et de recherche des en-têtes internes à l'aide d'une table de hachage
• Le temps de lecture d'une table de hachage est linéairement proportionnel à la longueur de la clé
• Essais avec d'autres structures de données, comme un ensemble trié ou une machine à états
• Une implémentation avec des expressions régulières est deux fois plus lente qu'une table de hachage

Utilisation d'un trie

• Un trie est une structure de données en arbre utilisée pour la recherche par préfixe ou les systèmes d'autocomplétion
• Un trie peut identifier rapidement les cas où une chaîne n'est pas présente
• Les implémentations de trie existantes sont plus lentes qu'une table de hachage
• Cloudflare a développé sa propre implémentation de trie optimisée, appelée trie-hard

Trie Hard

• trie-hard stocke les relations entre nœuds dans les bits d'entiers et utilise la mémoire de manière contiguë pour gagner en vitesse
• Réduction du temps d'exécution de la fonction clear_internal_headers à 0,93µs
• Réduction de l'utilisation CPU de 1,71 % à 0,43 %
• En production réelle, les performances de trie-hard correspondent aux benchmarks

Conclusion

• Il est important d'identifier les parties lentes du code et de les optimiser
• De petites optimisations peuvent s'additionner pour produire de gros gains de performance
• Le connectivity cloud de Cloudflare fournit des fonctions comme la protection du réseau, l'accélération des applications Internet et la défense contre les attaques DDoS

Le résumé de GN⁺

• Cloudflare réduit l'utilisation CPU et améliore la capacité de traitement de son CDN grâce à une nouvelle crate Rust open source
• L'optimisation de la suppression des en-têtes internes dans le service Pingora-origin réduit l'utilisation CPU de 1,28 %
• Cloudflare a développé sa propre implémentation de trie optimisée, trie-hard, pour améliorer fortement les performances
• Cet article souligne l'importance de l'optimisation du code et du choix des structures de données, et montre que de petites optimisations peuvent produire de gros gains de performance
• Parmi les projets offrant des fonctions similaires, on peut citer NGINX et HAProxy

[GN⁺]

Commentaires sur Hacker News

• Plusieurs hypothèses ont été formulées sur la façon dont Cloudflare stocke et supprime les en-têtes internes

  • utilisation d’un dictionnaire ou d’une structure de données séparée
  • un en-tête unique contenant toutes les métadonnées internes
  • un préfixe ajouté à tous les en-têtes, les internes commençant par « I » et les externes par « E »
  • tous les en-têtes internes commencent par "CFInt"
  • l’idée qu’une liste spécifique d’en-têtes désigne les en-têtes internes n’avait pas été anticipée
  • le Web est déjà rempli de signaux ambigus et de noms d’en-têtes confus
  • il est étrange qu’une entreprise à grande échelle comme Cloudflare utilise un mécanisme aussi sujet aux erreurs

• Au départ, l’idée de mapper des caractères UTF-8 vers un bitmask semblait inefficace

  • 32 bits permettent d’inclure a-z et six caractères spéciaux
  • 64 bits permettent d’inclure les majuscules A-Z et six caractères spéciaux
  • cela offre suffisamment d’espace pour les en-têtes HTTP et permet un algorithme de correspondance rapide
  • cette technique est un filtre de Bloom
  • c’est une technique développée dans les années 1970 à une époque de ressources limitées, mais elle reste encore utile aujourd’hui

• Des doutes existent sur la valeur réelle de l’optimisation de Cloudflare

  • environ 500 cœurs CPU ont été économisés
  • le coût de Cloudflare n’est pas connu, mais l’économie est estimée à quelques dizaines de milliers de dollars
  • on peut se demander si un ROI positif sur l’ingénierie est réellement attendu
  • il serait peut-être préférable d’appliquer le filtre lors de l’étape de désérialisation afin d’éviter la création des en-têtes

• Sans être très au fait des optimisations de structures de données, certains sont surpris que la table de hachage ait été écartée si vite

  • pour rechercher dans une table statique, une table de hachage semblait pouvoir être plus rapide

• Une structure de données sophistiquée est utilisée pour définir les éléments à supprimer, puis les retirer de la map d’en-têtes sur cette base

  • un lien vers le code impliquant l’appel à remove_header est fourni

• Un billet de blog utilisant un trie est enfin sorti

  • les problèmes liés aux tries n’auront pas été vains

• Certains se demandent si un petit filtre de Bloom a été essayé

  • une convolution rapide sur les clés d’en-têtes et un test via filtre de Bloom pourraient éviter de parcourir le trie

• Certains se demandent si une table de hachage parfaite a été testée pour faire correspondre un ensemble statique d’éléments

  • cela pourrait se réduire à quelques opérations arithmétiques et une seule comparaison de chaîne

• L’optimisation est jugée intéressante

  • certains se demandent s’il était possible de marquer les en-têtes comme internes dès la création de la requête
  • le filtrage en sortie en serait simplifié

• Certains se demandent pourquoi la crate regex n’a pas donné de meilleurs résultats

  • elle devrait compiler la recherche de plusieurs chaînes littérales en un automate d’Aho-Corasick