Un buen día para trie-hard: ahorrar 1% de cómputo

Motivación

• La red global de Cloudflare procesa más de 60 millones de solicitudes HTTP por segundo
• Usando un nuevo crate de Rust de código abierto, redujeron el uso de CPU y mejoraron la capacidad de procesamiento de su CDN
• Pingora es el núcleo del servicio proxy basado en Rust de Cloudflare, y fue liberado como código abierto
• El servicio Pingora-origin se encarga de reenviar las solicitudes de los usuarios a su destino real
• Cuando una solicitud sale de Cloudflare, es necesario eliminar la información interna
• Esta tarea ocurre con muchísima frecuencia y representa el 1.7% del uso de CPU

Benchmarking

• Usaron el crate Criterion de Rust para medir el rendimiento de la función en nanosegundos
• La función original clear_internal_headers tardaba en promedio 3.65µs

Reducir operaciones de lectura

• Redujeron las operaciones de lectura invirtiendo la dirección en la que eliminaban los headers
• Con este cambio, el tiempo de ejecución de la función mejoró de 3.65µs a 1.53µs
• El uso de CPU bajó de 1.71% a 0.717%

Búsqueda en estructuras de datos

• Intentaron almacenar y buscar los headers internos usando un hash map
• El tiempo de lectura del hash map es lineal y proporcional a la longitud de la clave
• Probaron otras estructuras de datos como conjuntos ordenados o máquinas de estado
• La implementación con expresiones regulares fue el doble de lenta que el hash map

Uso de trie

• Un trie es una estructura de datos en árbol que se usa para búsquedas por prefijo o sistemas de autocompletado
• Un trie puede identificar rápidamente los casos en los que una cadena no está incluida
• Las implementaciones existentes de trie eran más lentas que un hash map
• Cloudflare desarrolló su propia implementación optimizada de trie, llamada trie-hard

Trie Hard

• trie-hard guarda las relaciones entre nodos en los bits de enteros y usa memoria contigua para ganar velocidad
• Redujo el tiempo de ejecución de la función clear_internal_headers a 0.93µs
• El uso de CPU bajó de 1.71% a 0.43%
• En producción real, el rendimiento de trie-hard coincidió con el benchmark

Conclusión

• Es importante identificar y optimizar las partes lentas del código
• Pequeñas optimizaciones acumuladas pueden generar grandes mejoras de rendimiento
• La nube conectada de Cloudflare ofrece funciones como protección de red, aceleración de aplicaciones de Internet y defensa contra ataques DDoS

Resumen de GN⁺

• Cloudflare redujo el uso de CPU y mejoró la capacidad de procesamiento de su CDN mediante un nuevo crate de Rust de código abierto
• Al optimizar la eliminación de headers internos en el servicio Pingora-origin, redujo el uso de CPU en 1.28%
• Desarrolló una implementación de trie propia y optimizada llamada trie-hard, logrando una mejora importante de rendimiento
• Este artículo destaca la importancia de optimizar el código y elegir bien las estructuras de datos, mostrando cómo pequeñas optimizaciones pueden producir grandes mejoras de rendimiento
• Proyectos con funciones similares incluyen NGINX y HAProxy

[GN⁺]

Opinión de Hacker News

• Hubo varias especulaciones sobre cómo Cloudflare almacena y elimina encabezados internos

  • usar un diccionario o estructura de datos aparte
  • un solo encabezado que incluya todos los metadatos internos
  • poner prefijos a todos los encabezados, con los internos empezando con "I" y los externos con "E"
  • que todos los encabezados internos empiecen con "CFInt"
  • no se esperaba que funcionara con una lista específica de encabezados considerados internos
  • la web ya está llena de señales ambiguas y nombres de encabezados confusos
  • resulta extraño que una empresa tan grande como Cloudflare use un mecanismo tan propenso a errores

• Al principio se pensó que mapear caracteres UTF-8 con una máscara de bits era ineficiente

  • con 32 bits se puede cubrir a-z y seis caracteres especiales
  • con 64 bits se puede cubrir mayúsculas A-Z y seis caracteres especiales
  • eso ofrece espacio suficiente para encabezados HTTP y permite algoritmos de coincidencia rápidos
  • esta técnica es un Bloom Filter
  • aunque fue desarrollada en los años 70, cuando los recursos eran limitados, sigue siendo útil hoy

• Hay dudas sobre si la optimización de Cloudflare realmente vale la pena

  • se ahorraron alrededor de 500 núcleos de CPU
  • no se conocen los costos de Cloudflare, pero se estima un ahorro de unas decenas de miles de dólares
  • se duda si puede esperarse un ROI positivo de ingeniería
  • quizá sería mejor aplicar el filtro en la etapa de deserialización para evitar que los encabezados se generen

• No se sabe mucho sobre optimización de estructuras de datos, pero sorprende que se haya descartado tan rápido una tabla hash

  • al buscar en una tabla estática, parecería que una tabla hash sería más rápida

• Se usa una estructura de datos fancy para definir los elementos que se van a eliminar y luego quitarlos del mapa de encabezados con base en eso

  • se comparte un enlace al código relacionado con la llamada a "remove_header"

• Por fin salió una publicación de blog usando un trie

  • los problemas relacionados con tries no fueron en vano

• Hay curiosidad por saber si probaron con un Bloom Filter pequeño

  • una convolución rápida sobre las claves de encabezado y una prueba con Bloom Filter podrían evitar recorrer el trie

• También hay curiosidad por saber si intentaron una tabla hash perfecta para hacer coincidir un conjunto estático de elementos

  • podría reducirse a unas cuantas operaciones aritméticas y una sola comparación de cadenas

• La optimización resulta interesante

  • hay curiosidad por saber si era posible marcar los encabezados como internos al momento de generar la solicitud
  • así el filtrado al salir sería más simple

• Hay curiosidad por saber por qué el crate regex no funcionó mejor

  • debería poder compilar múltiples búsquedas de cadenas literales en un autómata Aho-Corasick