El almacenamiento en caché es una idea omnipresente en informática que mejora significativamente el rendimiento de los sistemas de almacenamiento y recuperación al almacenar un subconjunto de elementos populares más cerca del cliente según los patrones de solicitud. Una parte algorítmica importante de la gestión de caché es la política de decisión utilizada para actualizar dinámicamente el conjunto de elementos que se almacenan, que se ha optimizado ampliamente durante varias décadas, lo que ha dado como resultado varios heurística eficiente y robusta. Si bien la aplicación del aprendizaje automático a las políticas de caché ha mostrado resultados prometedores en los últimos años (por ejemplo, LRBMás, volante a la izquierda, aplicaciones de almacenamiento), sigue siendo un desafío superar las heurísticas sólidas de una manera que pueda generalizar de manera confiable más allá de los puntos de referencia a la configuración de producción, mientras se mantienen los gastos generales competitivos de cómputo y memoria.
En “HALP: política de desalojo de preferencias aprendidas asistidas por heurística para la red de entrega de contenido de YouTube”, presentado en INDE 2023presentamos un marco escalable de desalojo de caché de última generación que se basa en recompensas y usos aprendidos preferencia de aprendizaje con retroalimentación automática. El marco de Preferencia aprendida asistida por heurística (HALP) es un meta-algoritmo que utiliza la aleatorización para fusionar una regla de desalojo de línea de base heurística ligera con un modelo de recompensa aprendida. El modelo de recompensa es una red neuronal liviana que se entrena continuamente con retroalimentación automática continua sobre las comparaciones de preferencias diseñadas para imitar el oráculo fuera de línea. Discutimos cómo HALP ha mejorado la eficiencia de la infraestructura y la latencia de reproducción de video del usuario para YouTube. Red de entrega de contenidos.
Preferencias aprendidas para decisiones de desalojo de caché
El marco HALP calcula las decisiones de desalojo de caché en función de dos componentes: (1) un modelo de recompensa neuronal entrenado con retroalimentación automatizada a través del aprendizaje de preferencias y (2) un meta-algoritmo que combina un modelo de recompensa aprendido con una heurística rápida. A medida que el caché observa las solicitudes entrantes, HALP entrena continuamente una pequeña red neuronal que predice una recompensa escalar para cada elemento al formular esto como un método de aprendizaje de preferencias a través de por parejas retroalimentación de preferencias. Este aspecto de HALP es similar a aprendizaje por refuerzo a partir de la retroalimentación humana (RLHF), pero con dos distinciones importantes:
- La retroalimentación es automatizado y aprovecha los resultados conocidos sobre la estructura de los servicios fuera de línea óptimo políticas de desalojo de caché.
- el modelo es aprendido continuamente usando un búfer transitorio de ejemplos de entrenamiento construidos a partir del proceso de retroalimentación automatizado.
Las decisiones de desalojo se basan en un mecanismo de filtrado de dos pasos. Primero, se selecciona un pequeño subconjunto de candidatos utilizando una heurística que es eficiente, pero subóptima en términos de rendimiento. Luego, un paso de reclasificación optimiza desde dentro de los candidatos de referencia mediante el uso moderado de una función de puntuación de red neuronal para “aumentar” la calidad de la decisión final.
Como una implementación de política de caché lista para producción, HALP no solo toma decisiones de desalojo, sino que también subsume el proceso integral de muestreo de consultas de preferencia por pares utilizadas para construir de manera eficiente comentarios relevantes y actualizar el modelo para impulsar las decisiones de desalojo.
Un modelo de recompensa neuronal
HALP utiliza una capa ligera de dos capas perceptrón multicapa (MLP) como su modelo de recompensa para puntuar selectivamente elementos individuales en el caché. Las características se construyen y administran como un “caché fantasma” solo de metadatos (similar a las políticas clásicas como ARCO). Después de cualquier solicitud de búsqueda dada, además de las operaciones regulares de caché, HALP lleva a cabo la contabilidad (p. ej., seguimiento y actualización de metadatos de características en un almacén de clave-valor con capacidad restringida) necesaria para actualizar la representación interna dinámica. Esto incluye: (1) funciones etiquetadas externamente proporcionadas por el usuario como entrada, junto con una solicitud de búsqueda de caché, y (2) funciones dinámicas construidas internamente (por ejemplo, tiempo desde el último acceso, tiempo promedio entre accesos) construidas a partir de los tiempos de búsqueda observados en Cada artículo.
HALP aprende su modelo de recompensa completamente en línea a partir de una inicialización de peso aleatoria. Esto puede parecer una mala idea, especialmente si las decisiones se toman exclusivamente para optimizar el modelo de recompensa. Sin embargo, las decisiones de desalojo se basan tanto en el modelo de recompensa aprendida como en una heurística subóptima pero simple y robusta como LRU. Esto permite un rendimiento óptimo cuando el modelo de recompensa se ha generalizado por completo, al tiempo que se mantiene sólido frente a un modelo de recompensa temporalmente poco informativo que aún debe generalizarse o está en proceso de adaptarse a un entorno cambiante.
Otra de las ventajas de la formación online es la especialización. Cada servidor de caché se ejecuta en un entorno potencialmente diferente (por ejemplo, ubicación geográfica), lo que influye en las condiciones de la red local y qué contenido es localmente popular, entre otras cosas. La capacitación en línea captura automáticamente esta información al tiempo que reduce la carga de la generalización, a diferencia de una única solución de capacitación fuera de línea.
Puntuación de muestras de una cola de prioridad aleatoria
Puede ser poco práctico optimizar la calidad de las decisiones de desalojo con un objetivo exclusivamente aprendido por dos razones.
- Restricciones de eficiencia informática: la inferencia con una red aprendida puede ser significativamente más costosa que los cálculos realizados en políticas de caché prácticas que operan a escala. Esto limita no solo la expresividad de la red y las características, sino también la frecuencia con la que se invocan durante cada decisión de desalojo.
- Robustez para generalizar fuera de distribución: HALP se implementa en una configuración que implica aprendizaje continuo, donde una carga de trabajo que cambia rápidamente puede generar patrones de solicitud que pueden estar temporalmente fuera de distribución con respecto a los datos vistos anteriormente.
Para abordar estos problemas, HALP primero aplica una regla de puntuación heurística económica que corresponde a una prioridad de desalojo para identificar una pequeña muestra de candidatos. Este proceso se basa en un muestreo aleatorio eficiente que se aproxima exacto colas de prioridad. Se pretende que la función de prioridad para generar muestras candidatas sea rápida de calcular utilizando algoritmos sintonizados manualmente existentes, por ejemplo, LRU. Sin embargo, esto se puede configurar para aproximar otras heurísticas de reemplazo de caché mediante la edición de una función de costo simple. A diferencia de trabajo prioritariodonde la aleatorización se usó para compensar la aproximación por eficiencia, HALP también confía en la aleatorización inherente en los candidatos de la muestra a través de los pasos de tiempo para proporcionar la necesaria exploratorio diversidad en los candidatos muestreados tanto para entrenamiento como para inferencia.
El elemento final desalojado se elige entre los candidatos suministrados, equivalente al lo mejor de n muestra reordenada, correspondiente a la maximización de la predicha puntuación de preferencia según el modelo de recompensa neuronal. El mismo grupo de candidatos que se usa para las decisiones de desalojo también se usa para construir las consultas de preferencia por pares para la retroalimentación automatizada, lo que ayuda a minimizar el sesgo de entrenamiento e inferencia entre las muestras.
 |
| Una descripción general del proceso de dos etapas invocado para cada decisión de desalojo. |
Aprendizaje de preferencias en línea con retroalimentación automatizada
El modelo de recompensa se aprende mediante la retroalimentación en línea, que se basa en etiquetas de preferencia asignadas automáticamente que indican, siempre que sea factible, el orden de preferencia clasificado por el tiempo necesario para recibir accesos futuros, a partir de una instantánea dada en el tiempo entre cada muestra consultada de elementos. Esto es similar a la política óptima de Oracle, que, en un momento dado, expulsa un elemento con el acceso futuro más lejano de todos los elementos en el caché.
 |
| Generación del feedback automatizado para el aprendizaje del modelo de recompensas. |
Para que este proceso de retroalimentación sea informativo, HALP construye consultas de preferencia por pares que tienen más probabilidades de ser relevantes para las decisiones de desalojo. En sincronía con las operaciones de caché habituales, HALP emite una pequeña cantidad de consultas de preferencia por pares al tomar cada decisión de desalojo y las agrega a un conjunto de comparaciones pendientes. Las etiquetas de estas comparaciones pendientes solo se pueden resolver en un futuro aleatorio. Para operar en línea, HALP también realiza una contabilidad adicional después de cada solicitud de búsqueda para procesar las comparaciones pendientes que se pueden etiquetar de forma incremental después de la solicitud actual. HALP indexa el búfer de comparación pendiente con cada elemento involucrado en la comparación y recicla la memoria consumida por las comparaciones obsoletas (ninguna de las cuales puede obtener un nuevo acceso) para garantizar que la sobrecarga de memoria asociada con la generación de comentarios permanezca limitada a lo largo del tiempo.
 |
| Descripción general de todos los componentes principales de HALP. |
Resultados: Impacto en la CDN de YouTube
A través del análisis empírico, mostramos que HALP se compara favorablemente con las políticas de caché de última generación en los seguimientos de referencia públicos en términos de tasas de fallas de caché. Sin embargo, si bien los puntos de referencia públicos son una herramienta útil, rara vez son suficientes para capturar todos los patrones de uso en todo el mundo a lo largo del tiempo, sin mencionar las diversas configuraciones de hardware que ya hemos implementado.
Hasta hace poco, los servidores de YouTube usaban una variante LRU optimizada para el desalojo de caché de memoria. HALP aumenta la salida/entrada de la memoria de YouTube (la relación entre la salida del ancho de banda total servido por la CDN y el consumido para la recuperación (ingreso) debido a errores de caché) en aproximadamente un 12 % y la tasa de aciertos en la memoria en un 6 %. Esto reduce la latencia para los usuarios, ya que las lecturas de memoria son más rápidas que las lecturas de disco y también mejora la capacidad de salida de las máquinas limitadas por disco al proteger los discos del tráfico.
La siguiente figura muestra una reducción visualmente convincente en el proporción de bytes perdidos en los días posteriores al lanzamiento final de HALP en la CDN de YouTube, que ahora entrega significativamente más contenido desde el caché con una latencia más baja para el usuario final y sin tener que recurrir a una recuperación más costosa que aumenta los costos operativos.
 |
| Proporción total de bytes perdidos de YouTube en todo el mundo antes y después del lanzamiento (línea discontinua vertical). |
Una mejora del rendimiento agregado aún podría ocultar regresiones importantes. Además de medir el impacto general, también llevamos a cabo un análisis en el documento para comprender su impacto en diferentes racks mediante un análisis a nivel de máquina, y encontramos que es abrumadoramente positivo.
Conclusión
Introdujimos un marco de desalojo de caché de última generación escalable que se basa en recompensas y usos aprendidos preferencia de aprendizaje con retroalimentación automática. Debido a sus opciones de diseño, HALP se puede implementar de manera similar a cualquier otra política de caché sin la sobrecarga operativa de tener que administrar por separado los ejemplos etiquetados, el procedimiento de capacitación y las versiones del modelo como canalizaciones fuera de línea adicionales comunes a la mayoría de los sistemas de aprendizaje automático. Por lo tanto, solo incurre en una pequeña sobrecarga adicional en comparación con otros algoritmos clásicos, pero tiene el beneficio adicional de poder aprovechar características adicionales para tomar sus decisiones de desalojo y adaptarse continuamente a los patrones de acceso cambiantes.
Esta es la primera implementación a gran escala de una política de caché aprendida en una CDN ampliamente utilizada y con mucho tráfico, y ha mejorado significativamente la eficiencia de la infraestructura CDN al mismo tiempo que brinda una mejor calidad de experiencia a los usuarios.
Agradecimientos
Ramki Gummadi ahora es parte de Google DeepMind. Nos gustaría agradecer a John Guilyard por su ayuda con las ilustraciones y a Richard Schooler por sus comentarios sobre esta publicación.
