Cloudflare logró recuperar más de 100 terabytes de memoria RAM en toda su red mundial tras rediseñar parte del algoritmo de distribución de solicitudes de su servicio Pingora Backend Router (PBR). La mejora se obtuvo mediante una combinación de compresión de la representación de los puntos de hash, reducción de su cantidad basándose en un análisis estadístico y una migración gradual que mantuvo la estabilidad de la caché y del tráfico hacia los servidores de origen.
El problema de la distribución de solicitudes
Cloudflare utiliza la biblioteca pingora-ketama para implementar consistent hashing, un método que ayuda a dirigir, siempre que sea posible, las solicitudes almacenables en caché al mismo servidor. Esto permite conservar una única copia del archivo dentro del centro de datos y proporcionar una ruta estable para acceder a él.
Sin embargo, utilizar un único punto de hash por servidor puede provocar una gran variación en el tamaño de los rangos que los servidores poseen en el anillo de hash y, por tanto, diferencias en las cargas de trabajo. Por ello, Pingora utiliza una gran cantidad de hashes virtuales por servidor, con pesos asociados a la capacidad de almacenamiento; además, se crean anillos separados para distintos grupos de características y restricciones. La acumulación de estos anillos llegó a consumir, en algunos casos, hasta 6 gigabytes por proceso.
Optimización de la representación de datos y reducción de los hashes
Cada elemento que representaba un punto del anillo constaba de un valor de hash de 32 bits y un índice de 32 bits hacia el servidor, es decir, ocho bytes en memoria. El equipo de Cloudflare consideró que, en la práctica, el índice no necesitaba más de 16 bits, porque el servicio no coordinaría más de unos 65.000 servidores al mismo tiempo.
Reducir el tipo del índice no bastaba por sí solo debido a las reglas de alineación de Rust, ya que la estructura seguiría ocupando ocho bytes. Por ello, Cloudflare volvió a almacenar el valor y el índice dentro de una matriz sin formato de seis bytes, con funciones para acceder a cada uno. Este cambio redujo en un 25% el consumo de memoria asociado al hash.
La mayor ganancia llegó de la revisión del número de hashes. El servicio utilizaba un valor base de 160 puntos por servidor, multiplicado por el peso del servidor asociado a su capacidad de almacenamiento. El análisis mostró que los grandes aumentos en el número de hashes proporcionaban mejoras decrecientes en el margen de error; en el ejemplo analizado por Cloudflare, añadir los últimos 90.000 hashes solo redujo el error aproximadamente un 0,7%.
Además, utilizar valores de hash de 32 bits hace que las colisiones sean más probables a medida que aumenta el número de puntos, lo que puede añadir un error inesperado a la distribución. Basándose en los cálculos y las simulaciones, Cloudflare redujo en un 90% el número de hashes por servidor sin un aumento apreciable del error, lo que contribuyó a los ahorros finales.
¿Qué cambia en la práctica?
Cambiar el anillo de hash en toda la red de una sola vez no era una opción segura, porque redistribuiría las solicitudes y provocaría de hecho la pérdida de gran parte de la eficacia de la caché, con la posibilidad de aumentar el tráfico hacia los servidores de origen. Por ello, PBR conservó temporalmente en memoria los anillos antiguo y nuevo, y eligió entre ellos para cada solicitud, lo que proporcionó una ruta de reversión clara.
La migración se ejecutó por etapas, comenzando por sitios de verificación pequeños y continuando con centros de datos más grandes. También se separó el control del porcentaje de solicitudes que utilizaban el anillo nuevo de la determinación de los centros de datos autorizados a participar. Cloudflare supervisó los efectos de la selección del servidor, las versiones del anillo, los errores de conexión, el consumo de memoria, el tiempo de inicio, el comportamiento de la caché y el tráfico hacia los servidores de origen antes de retirar la ruta antigua.
Implicaciones de ingeniería
La experiencia demuestra que las optimizaciones de bajo nivel, como elegir el tamaño de un campo dentro de una estructura de datos o determinar un número adecuado de puntos de hash, pueden amplificar sus efectos cuando se aplican a una red que contiene miles de servidores. Al mismo tiempo, el resultado no significa que reducir la memoria sea seguro en todos los sistemas; la precisión de la distribución, las probabilidades de colisión, los pesos de los servidores, las restricciones de las características y la forma de ejecutar la migración son factores que deben medirse antes del cambio.
Las modificaciones están disponibles en el paquete pingora-ketama mediante una característica de Cargo que actualmente no se anuncia. La versión v2 admite el formato de almacenamiento comprimido, un método de ordenación más rápido y la posibilidad de ajustar el número base de hashes, al tiempo que mantiene la versión v1 y permite ejecutar ambos anillos conjuntamente y tomar la decisión a nivel de solicitud.