Una estampida de caché es un tipo de falla en cascada que puede ocurrir cuando los sistemas de computación masivamente paralelos con mecanismos de almacenamiento en caché se encuentran bajo una carga muy alta. Este comportamiento a veces también se denomina acumulación de perros . [1] [2]
Para comprender cómo ocurren las estampidas de caché, considere un servidor web que use memcached para almacenar en caché las páginas renderizadas durante un período de tiempo, para facilitar la carga del sistema. Bajo una carga particularmente alta en una sola URL, el sistema permanece receptivo mientras el recurso permanezca en caché, y las solicitudes se manejan accediendo a la copia en caché. Esto minimiza la costosa operación de renderizado.
Con poca carga, las fallas de caché dan como resultado un único recálculo de la operación de renderizado. El sistema continuará como antes, con una carga promedio que se mantendrá muy baja debido a la alta tasa de aciertos de la caché.
Sin embargo, bajo una carga muy pesada, cuando caduca la versión en caché de esa página, puede haber suficiente simultaneidad en la granja de servidores para que varios subprocesos de ejecución intenten representar el contenido de esa página simultáneamente. De manera sistemática, ninguno de los servidores simultáneos sabe que los demás están haciendo el mismo renderizado al mismo tiempo. Si está presente una carga suficientemente alta, esto puede ser suficiente por sí solo para provocar el colapso de la congestión del sistema a través del agotamiento de los recursos compartidos. El colapso de la congestión evita que la página se vuelva a procesar y almacenar en caché por completo, ya que cada intento de hacerlo se agota. Por lo tanto, la estampida de caché reduce la tasa de aciertos de caché a cero y mantiene el sistema continuamente en colapso por congestión mientras intenta regenerar el recurso mientras la carga siga siendo muy pesada.
Para dar un ejemplo concreto, supongamos que la página en cuestión tarda 3 segundos en renderizarse y tenemos un tráfico de 10 solicitudes por segundo. Luego, cuando la página almacenada en caché expira, tenemos 30 procesos que vuelven a calcular simultáneamente la representación de la página y actualizan la memoria caché con la página representada.
Uso típico de caché
A continuación se muestra un patrón de uso de caché típico para un elemento que debe actualizarse cada ttl unidades de tiempo:
function fetch ( clave , ttl ) { valor ← cache_read ( clave ) if (! valor ) { valor ← recompute_value () cache_write ( clave , valor , ttl ) } valor de retorno}
Si la función recompute_value () lleva mucho tiempo y se accede a la clave con frecuencia, muchos procesos llamarán simultáneamente recompute_value () al expirar el valor de la caché.
En aplicaciones web típicas, la función recompute_value () puede consultar una base de datos, acceder a otros servicios o realizar alguna operación complicada (razón por la cual este cálculo en particular se almacena en caché en primer lugar). Cuando la tasa de solicitudes es alta, la base de datos (o cualquier otro recurso compartido) sufrirá una sobrecarga de solicitudes / consultas, lo que a su vez puede causar un colapso del sistema.
Mitigación de estampida de caché
Se han propuesto varios enfoques para mitigar las estampidas de caché. (También conocido como prevención de la acumulación de perros) Se pueden agrupar aproximadamente en 3 categorías principales.
Cierre
Para evitar múltiples recálculos simultáneos del mismo valor, cuando se pierde un caché, un proceso intentará adquirir el bloqueo para esa clave de caché y volver a calcularlo solo si lo adquiere.
Existen diferentes opciones de implementación para el caso en el que no se adquiere el bloqueo :
- Espere hasta que se vuelva a calcular el valor
- Devuelva un "no encontrado" y haga que el cliente maneje la ausencia del valor correctamente
- Mantenga un elemento obsoleto en la caché para usarlo mientras se vuelve a calcular el nuevo valor
Si se implementa correctamente, el bloqueo puede evitar las estampidas por completo, pero requiere una escritura adicional para el mecanismo de bloqueo. Además de duplicar el número de escrituras, el principal inconveniente es una implementación correcta del mecanismo de bloqueo que también se encarga de los casos extremos, incluida la falla del proceso de adquisición de la cerradura, el ajuste de un tiempo de vida para la cerradura, las condiciones de carrera. , y así.
Recomputación externa
Esta solución mueve el recálculo del valor de la caché de los procesos que lo necesitan a un proceso externo. El recálculo del proceso externo se puede activar de diferentes formas:
- Cuando el valor de la caché se acerca a su vencimiento
- Periódicamente
- Cuando un proceso que necesita el valor encuentra una falta de caché
Este enfoque requiere una parte móvil más, el proceso externo, que debe mantenerse y monitorearse. Además, esta solución requiere una separación / duplicación de código no natural y es principalmente adecuada para claves de caché estáticas (es decir, no generadas dinámicamente, como en el caso de claves indexadas por un id).
Vencimiento anticipado probabilístico
Con este enfoque, cada proceso puede volver a calcular el valor de la caché antes de su vencimiento al tomar una decisión probabilística independiente, donde la probabilidad de realizar el recálculo temprano aumenta a medida que nos acercamos al vencimiento del valor. Dado que la decisión probabilística se toma de forma independiente por cada proceso, el efecto de la estampida se mitiga ya que menos procesos expirarán al mismo tiempo.
Se ha demostrado que la siguiente implementación basada en una distribución exponencial es óptima en términos de su efectividad para prevenir estampidas y cómo pueden ocurrir los recálculos tempranos. [3]
función x-fetch ( clave , ttl , beta = 1) { valor , delta , vencimiento ← lectura_caché ( clave ) if (! valor || tiempo () - delta * beta * log (rand (0,1)) ≥ vencimiento ) { inicio ← tiempo () valor ← recompute_value () delta ← tiempo () - inicio cache_write ( clave , ( valor , delta ), ttl ) } valor de retorno}
El parámetro beta se puede establecer en un valor mayor que 1 para favorecer los recálculos anteriores y reducir aún más las estampidas, pero los autores muestran que la configuración beta = 1 funciona bien en la práctica. La variable delta representa el tiempo necesario para volver a calcular el valor y se utiliza para escalar la distribución de probabilidad de forma adecuada.
Este enfoque es simple de implementar y reduce eficazmente las estampidas de caché al favorecer automáticamente los recálculos tempranos cuando aumenta la tasa de tráfico. Un inconveniente es que se necesita más memoria en la caché, ya que necesitamos agrupar el valor delta con el elemento de la caché; cuando el sistema de almacenamiento en caché no admite la recuperación del tiempo de caducidad de la clave, también necesitamos almacenar la vencimiento (es decir, time () + ttl ) en el paquete.
Referencias
- ^ Galbraith, Patrick (2009), Desarrollo de aplicaciones web con Apache, MySQL, memcached y Perl , John Wiley & Sons, p. 353, ISBN 9780470538326.
- ^ Allspaw, John; Robbins, Jesse (2010), Operaciones web: mantener los datos a tiempo , O'Reilly Media, págs. 128-132, ISBN 9781449394158.
- ^ Vattani, A .; Chierichetti, F .; Lowenstein, K. (2015), "Optimal Probabilistic Cache Stampede Prevention" (PDF) , Proceedings of the VLDB Endowment , VLDB, 8 (8): 886–897, doi : 10.14778 / 2757807.2757813 , ISSN 2150-8097.
enlaces externos
- Minimizar las estampidas de caché , Joshua Thijssen, 2010
- Problemas y soluciones para el uso típico de caché de Perl , Jonathan Swartz, 2008