El buen día de trie-hard: ahorrar 1% de cómputo
(blog.cloudflare.com)- Cloudflare publicó el crate open source de Rust trie-hard para reducir el uso de CPU de Pingora, su proxy basado en Rust, en una red que procesa en promedio más de 60 millones de solicitudes HTTP por segundo
- El cuello de botella estaba en la función
clear_internal_headersdepingora-origin, que elimina headers usados para enrutamiento interno, medición y optimización en solicitudes no cacheadas que salen de Cloudflare, y se ejecuta en una ruta de 35 millones de solicitudes por segundo - La implementación anterior intentaba eliminar más de 100 headers internos en cada solicitud y tardaba en promedio 3.65µs, consumiendo el 1.71% del tiempo total de CPU de
pingora-origin, equivalente a 680 núcleos de CPU de un total de 40 mil compute-seconds/s - Recorrer primero los headers reales de la solicitud bajó el promedio a 1.53µs, 2.39 veces más rápido, pero el ahorro total de CPU en teoría apenas llegaba a 0.993%, así que hacía falta una mejor estructura de búsqueda
- La nueva implementación con trie redujo el tiempo promedio de ejecución a 0.93µs, y el muestreo en producción desde julio de 2024 mostró que el uso real de CPU de
clear_internal_headersbajó hasta 0.34%
El costo que Cloudflare quería reducir
- La red global de Cloudflare procesa en promedio más de 60 millones de solicitudes HTTP por segundo
- Esta optimización comenzó en Pingora, el núcleo de su servicio de proxy basado en Rust, y en
pingora-origin, el servicio de producción que corre encima de él pingora-originse encarga del último paso de enviar las solicitudes no cacheadas del usuario al servidor de destino real, el origin- Antes de que una solicitud salga de la infraestructura de Cloudflare, este servicio debe eliminar de los headers la información usada para enrutamiento interno, medición y optimización
- A nivel global, las solicitudes que salen de
pingora-originson 35 millones por segundo al momento de escribir esto
La función cuello de botella: clear_internal_headers
- La función problemática está en una ruta muy caliente que se ejecuta en todas las solicitudes
// 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);
});
}
- Esta pequeña función por sí sola usa más de 1.7% del tiempo total de CPU de
pingora-origin - El tiempo total de CPU de
pingora-origines de 40,000 compute-seconds por segundo, una escala equivalente a tener 40 mil núcleos de CPU saturados ejecutando solo este servicio - De ese total, 1.7%, es decir unos 680 núcleos de CPU, se dedican solo a evaluar
clear_internal_headers
Medición base y primera mejora
- Para medir el rendimiento usaron el crate de Rust criterion
- Criterion agrega múltiples ejecuciones aisladas para medir tiempos de código Rust a nivel de nanosegundos, y también ofrece retroalimentación sobre mejoras o regresiones con el tiempo
- La entrada del benchmark fue un gran conjunto sintético de solicitudes con distribución uniforme entre headers internos y no internos
- El tiempo promedio de ejecución del
clear_internal_headersoriginal se midió en 3.65µs -
Invertir la dirección de la búsqueda
- El código anterior ejecutaba
request_header.remove_header(h)para cada elemento de la lista de headers internos, así que si había más de 100 headers internos se hacían más de 100 evaluaciones por solicitud - Una solicitud promedio tiene muchos menos headers que eso, en el rango de 10 a 30, así que recorrer los headers reales de la solicitud y buscarlos en el conjunto de headers internos reduce la cantidad de lecturas
http::HeaderMapde Rust todavía no tieneretain, así que había que reunir en una etapa aparte los headers internos a eliminar y luego borrarlos- Solo con este cambio, el tiempo promedio de ejecución bajó de 3.65µs a 1.53µs, una mejora de 2.39 veces
- En teoría, el uso total de CPU bajaría de 1.71% a 0.717%, con un ahorro de 0.993%
- El código anterior ejecutaba
Búsqueda de una mejor estructura de datos para consulta
- Tras invertir la dirección de la búsqueda, ya era posible elegir en qué estructura de datos guardar la lista estática de headers 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);
});
}
- El primer intento fue
std::HashMap, pero el hash de claves de tipo string tiene que leer todos los bytes, así que aunque sea tiempo constante respecto al tamaño de la tabla, sigue siendo tiempo lineal respecto a la longitud de la clave L - El objetivo era encontrar una estructura de datos con mejor comportamiento de lectura que O(L) respecto a la longitud de la clave
-
Alternativas revisadas
- Los conjuntos ordenados como
BTreeSetusan búsqueda basada en comparaciones, lo que ofrece comportamiento O(log(L)) respecto a la longitud de la clave, pero también implica tiempo logarítmico respecto al tamaño del conjunto - FST, un conjunto ordenado rápido, también resultó en benchmarks unos 50ns más lento que el hashmap estándar
- Las máquinas de estado, como parsers o expresiones regulares, reciben la entrada una unidad a la vez y en cada paso deciden si vale la pena seguir evaluando, por lo que pueden identificar rápido strings que no coinciden
- Eso encaja bien en este caso, donde en promedio solo hay 1 a 2 headers internos por solicitud, así que predominan los casos negativos
- Una implementación de
clear_internal_headerscon expresiones regulares tardó cerca de 2 veces más que la solución basada en hashmap, aunque fue un resultado rápido considerando que no se trata de una herramienta conocida por su velocidad cruda
- Los conjuntos ordenados como
Por qué un trie era lo correcto
- Un trie es una estructura de datos en árbol que suele usarse para búsqueda por prefijo o autocompletado sobre un conjunto conocido de strings
- Cada nodo de un trie representa una subcadena encontrada en el conjunto inicial de strings, y las conexiones entre nodos representan caracteres que pueden seguir a un prefijo dado
- Al empezar desde el nodo raíz, se puede reducir el espacio de búsqueda desde el primer carácter posible, lo que permite descartar rápido strings que no pertenecen al conjunto
- La lectura en un trie ofrece comportamiento O(log(L)) en casos de no coincidencia, aunque los casos de coincidencia siguen siendo O(L)
- Como más del 90% de los headers de una solicitud no son headers internos, este caso de uso se beneficia de una gran cantidad de no coincidencias
-
Límites de las implementaciones de trie existentes
- Benchmarkearon varias implementaciones de trie de crates.io, pero los resultados no fueron los esperados
- La mayoría de los tries están pensados para casos como autocompletado en respuesta a eventos de teclado, no para priorizar la optimización de una ruta caliente con decenas de millones de solicitudes por segundo
- La implementación existente más rápida que encontraron fue radix_trie, pero seguía siendo 1µs más lenta que el hashmap
- Al final escribieron una nueva implementación de trie adaptada a este caso de uso
trie-hard y los resultados en producción
-
Cloudflare publicó el nuevo crate open source de Rust trie-hard
-
trie-hardgana velocidad al guardar las relaciones entre nodos en los bits de enteros sin signo y mantener todo el árbol en un bloque contiguo de memoria -
En benchmarks,
trie-hardredujo el tiempo promedio de ejecución declear_internal_headersa 0.93µs -
El uso de CPU esperado es de 0.43%, lo que implica reducir en 1.28% el uso total de cómputo de
pingora-originfrente al 1.71% anterior -
Resultados reales por muestreo
trie-hardestá corriendo en producción desde julio de 2024- La medición de rendimiento se recopiló mediante muestreo estadístico de stack traces a lo largo del tiempo
- La proporción de muestras que incluyen una función específica se usa para estimar el uso de CPU de esa función
- Los resultados del muestreo en producción fueron, en general, cercanos a las predicciones del benchmark local
Implementación Muestras de stack trace que incluyen clear_internal_headersUso real de CPU Uso de CPU estimado Original 19 / 1111 1.71% n/a Hashmap 9 / 1103 0.82% 0.72% trie-hard 4 / 1171 0.34% 0.43%
Conclusión desde la operación
- Antes de escribir una nueva estructura de datos, primero hay que saber dónde y cuánto se está perdiendo rendimiento en el código
- Con herramientas como flame graphs, profiling y benchmarking, se pueden encontrar ahorros significativos incluso en funciones medidas en microsegundos
- Optimizar operaciones que ya son muy cortas puede parecer trivial, pero a escala de decenas de millones de solicitudes por segundo, las pequeñas mejoras se acumulan y reducen el uso total de cómputo
1 comentarios
Comentarios de Hacker News
Si me hubieran pedido adivinar a grandes rasgos cómo Cloudflare almacena y elimina headers internos, habría pensado en un diccionario o estructura de datos aparte, un único header que contuviera todos los metadatos internos, una forma de distinguir internos/externos con un prefijo, o un prefijo como
CFIntNo se me habría ocurrido el método de considerar como headers internos los nombres de headers que estén en una lista específica. Surgen preguntas como qué pasa si alguien más usa el mismo nombre, qué pasa si se omite una limpieza, qué pasa si programas que corren al mismo tiempo difieren entre sí respecto de la lista, qué pasa si el header
Connectionapunta a un header interno de Cloudflare, o qué pasa si el algoritmo de diferencia de conjuntos es lentoLa web ya está llena de señales in-band y nombres de headers ambiguos hasta lo exasperante, así que se siente raro que una empresa de la escala de Cloudflare use internamente un mecanismo tan engorroso y propenso a errores
cf-cache-statusEso incluía eliminar headers internos en ambos sentidos en los proxies de borde, también en el tráfico entrante
El enfoque de lista tiene desventajas, pero también muchas ventajas. Al señalar posibles fallas de este enfoque, a menudo parece ignorarse la historia y las dificultades que surgen a la escala de Cloudflare. Una lista enumerada es la forma más simple y flexible, y no requiere un acuerdo previo sobre la estructura de las claves de los headers. Considerando la cantidad de equipos de Cloudflare, la posibilidad de adquisiciones tecnológicas, etc., esto probablemente era importante
Si se precarga, en la práctica se combinan estas ideas y se fija la cantidad de headers internos por request. En ese punto, se podría usar una tabla hash enlazada que preserve el orden de creación y, en la lista final que se devuelve al cliente, eliminar simplemente los primeros N
Pensé un momento en el efecto de mapear caracteres UTF-8 con una máscara de bits, y al principio no me pareció muy inteligente. Pero luego me di cuenta de que con 32 bits se pueden incluir
a-zy 6 caracteres especiales, y con 64 bits se pueden incluir además las mayúsculasA-Zy otros 6 caracteres especialesPara headers HTTP es espacio suficiente, y como basta con enmascarar y comparar algunos enteros, se vuelve un algoritmo de matching muy rápido. Saber qué carácter corresponde a qué bit también requiere solo una consulta a una tabla de 256 palabras
Lo que el autor omitió es que esta técnica, técnicamente, es un filtro de Bloom. Estas cosas son interesantes porque vienen de una época en la que los recursos de cómputo eran muchísimo más limitados que ahora; en este caso, una optimización de 1970, y aun así seguimos usando la misma vieja optimización en rincones del mundo real
https://en.wikipedia.org/wiki/Bloom_filter
trie-hardy un filtro de Bloom. Un filtro de Bloom es probabilístico y usa hashing. Es útil cuando se pueden aceptar falsos positivos raros a cambio de no tener falsos negativos, pero eso no es lo que se necesita aquí. Aquí hace falta exactitud, y el hashing en sí es la etapa que hay que superarMás bien, esto se parece más a una versión mejorada o una variante del algoritmo de Liang usado en TeX para almacenar el diccionario de partición silábica. La tesis trata el algoritmo de Bloom como “superimposed coding”, lo que evoca fuertemente una época en la que la memoria era el recurso más escaso. Creo que te va a gustar ^_^
https://tug.org/docs/liang/liang-thesis.pdf
Los datos presentados para demostrar la ganancia en realidad no tienen suficiente potencia estadística para mostrar eso. No hay muestras suficientes
Un análisis muy simple en R sería
prop.test(c(9, 4), c(1103,1171)), y la prueba de igualdad de dos proporciones con corrección de continuidad da un valor p de 0.222Un valor p de 0.22 no está por debajo del mágico 0.05, y el intervalo de confianza del 95% sugiere que el trie podría ser, de hecho, apenas peor
Viendo el análisis previo, parece probable que el trie sea mejor y hay evidencia débil, pero sería preferible tomar muchas más muestras para tener certeza de cuánto mejor es
Para el objetivo de analizar rendimiento, describir el número de comparaciones con notación Big O se siente raro. Una comparación cuesta alrededor de 1 ciclo, y con paralelismo a nivel de instrucciones y SIMD se pueden hacer varias en un ciclo
El verdadero cuello de botella y origen de la lentitud es la memoria. Acceder a memoria cuesta miles de ciclos, y si hace falta un recorrido de TLB o una interrupción del OS, puede llegar a decenas o cientos de miles de ciclos. Si quieren usar Big O, debería ser para estimar la cantidad de cache misses
Yo probablemente usaría una función hash perfecta a medida y el truco de
popcountde Phil Bagwell. Sería más rápido que otras soluciones que consultan memoria varias vecesLa CPU es rápida; la memoria, lenta
No soy ningún experto en optimización de estructuras de datos, pero, especialmente considerando que la tabla en la que se busca es estática, me sorprendió que descartaran tan rápido una tabla hash. Me cuesta creer que una tabla hash especialmente optimizada no sería más rápida que su implementación de trie.
Para este uso, esa es una ventaja con la que el hash no puede competir. El resto de la técnica consiste en recortar lo suficiente el factor constante del trie para que esa ventaja inicial se vea recompensada en el rendimiento real.
std::collections::HashMap: https://github.com/rust-lang/rustc-hashCon unos 100 elementos estáticos, o1hash también podría funcionar: https://github.com/rurban/smhasher/blob/master/o1hash.h
El artículo crea el conjunto
to_removecon una estructura de datos elegante y luego lo recorre para eliminar elementos del mapa de headers base.La llamada a
remove_headerparece ser este código: https://docs.rs/pingora-http/0.3.0/src/pingora_http/lib.rs.html#576Esa función llama a
.remove()en otras dos estructuras de datos, y ambas terminan bajando a este código enorme: https://docs.rs/http/latest/src/http/header/map.rs.html#1550Por fin salió un post de blog donde aparece un trie. Los problemas de tries de LeetCode no fueron en vano ;)
Aun así, definitivamente no es una herramienta que saque con frecuencia.
Es un parser de user agent para Go: https://github.com/medama-io/go-useragent
Normalmente este tipo de problema depende de mucho parsing con expresiones regulares, así que estuvo bueno poder probar un enfoque más novedoso.
Si el conjunto de elementos a matchear es estático, me pregunto si probaron una tabla hash perfecta. Se reduciría a unas cuantas operaciones aritméticas y una comparación de cadenas; sería interesante ver cómo se compara con un trie.
En teoría, si se usan expresiones regulares, el matching se hace con una máquina de estados, así que debería tener un rendimiento de peor caso O(k), parecido al trie. Pero, según entiendo, las bibliotecas de expresiones regulares usan backtracking en vez de construir una máquina de estados real, así que el rendimiento ya no es O(k).
Igual me sorprende que no hayan encontrado una biblioteca de expresiones regulares ya existente, con buen rendimiento y basada en máquinas de estado. Debería rendir parecido a un trie, aunque en la práctica factores como los patrones de acceso a memoria o el rendimiento de ciertas operaciones aritméticas influyen más a fondo, así que es difícil adivinar.
¿Habrán probado con un filtro de Bloom muy pequeño? Si procesas rápidamente la clave del header de una forma parecida a una convolución y la comparas contra un filtro de Bloom, parece que en la mayoría de los casos podrías evitar por completo recorrer el trie con un costo de apenas unos ciclos.
También parecen existir opciones como SIMD, instrucciones CRC integradas o un filtro de Bloom de 256 bits.
Un enfoque más simple también podría valer la pena. Si se analiza la frecuencia de aciertos/fallos en los nodos del trie, quizá se puedan encontrar posiciones específicas de caracteres con una tasa de fallo mayor que la del primer carácter. Revisar primero esas posiciones especiales podría hacerlo más rápido. Claro, eso requiere asumir que los datos de headers son bastante regulares por naturaleza.
Mi opinión es esta. Primero, ¿vale la pena hacerlo? Parece que se ahorraron unos 500 núcleos de CPU, pero no sé si son núcleos reales o si incluyen también núcleos con hyperthreading.
No conozco los costos de Cloudflare, pero eso equivale a una cantidad de servidores de un solo dígito, y el ahorro probablemente sea de decenas de miles de dólares al año. No es algo despreciable, pero no sé si se puede esperar un ROI positivo frente a la inversión de ingeniería.
Segundo, si van a entrar en este nivel de detalle, me pregunto si evaluaron poner un filtro en la etapa de deserialización para que los headers ni siquiera se generen desde el principio.
También se sigue ahorrando energía y se reducen las emisiones de carbono.
Prefiero ver a una empresa intentando hacer algo 1% más rápido que haciendo tonterías como analizar headers con IA para tratar de vender sandalias.
Ese valor podría ser de un millón de dólares.