Estampida de caché

Una estampida de caché es un tipo de fallo en cascada que puede ocurrir cuando los sistemas de computación masivamente paralelos con mecanismos de almacenamiento en caché se ven sometidos a una carga muy alta. Este comportamiento a veces también se denomina apilamiento de objetos . ^{[ 1 ] [ 2 ]}

Para comprender cómo se producen las sobrecargas de caché, consideremos un servidor web que utiliza memcached para almacenar en caché las páginas renderizadas durante un tiempo, con el fin de reducir la carga del sistema. Ante una carga particularmente alta en una sola URL, el sistema se mantiene receptivo mientras el recurso permanezca en caché, y las solicitudes se gestionan accediendo a la copia almacenada. Esto minimiza el costoso proceso de renderizado.

Con poca carga, los fallos de caché provocan un único recálculo de la operación de renderizado. El sistema seguirá funcionando como antes, manteniendo la carga media muy baja gracias a la alta tasa de aciertos de caché.

Sin embargo, bajo una carga muy elevada, cuando la versión en caché de esa página caduca, puede haber suficiente concurrencia en el clúster de servidores como para que múltiples hilos de ejecución intenten renderizar el contenido de esa página simultáneamente. De forma sistemática, ninguno de los servidores concurrentes sabe que los demás están realizando la misma renderización al mismo tiempo. Si la carga es suficientemente alta, esto por sí solo puede provocar un colapso por congestión del sistema debido al agotamiento de los recursos compartidos. El colapso por congestión impide que la página se vuelva a renderizar y almacenar en caché por completo, ya que cada intento de hacerlo expira. Por lo tanto, la saturación de caché reduce la tasa de aciertos de caché a cero y mantiene al sistema en un estado continuo de colapso por congestión mientras intenta regenerar el recurso durante el tiempo que la carga siga siendo muy elevada.

Para dar un ejemplo concreto, supongamos que la página en cuestión tarda 3 segundos en renderizarse y que tenemos un tráfico de 10 solicitudes por segundo. Entonces, cuando la página almacenada en caché caduca, tenemos 30 procesos que recalculan simultáneamente el renderizado de la página y actualizan la caché con la página renderizada.

A continuación se muestra un patrón típico de uso de la caché para un elemento que necesita actualizarse cada ttl unidades de tiempo:

función fetch( clave , ttl ) { valor ← cache_read( clave ) si (! valor ) { valor ← recalcular_valor() cache_write( clave , valor , ttl ) } valor de retorno } 

Si la función recompute_value() tarda mucho tiempo y se accede a la clave con frecuencia, muchos procesos llamarán simultáneamente a recompute_value() cuando expire el valor de la caché.

En las aplicaciones web típicas, la función recompute_value() puede consultar una base de datos, acceder a otros servicios o realizar alguna operación compleja (razón por la cual este cálculo en particular se almacena en caché). 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 provocar el colapso del sistema.

Se han propuesto varios métodos para mitigar las estampidas de caché (también conocidas como prevención de amontonamientos). Estos se pueden agrupar, a grandes rasgos, en tres categorías principales.

Para evitar que se vuelvan a calcular varias veces simultáneamente el mismo valor, en caso de que falle la caché, un proceso intentará adquirir el bloqueo para esa clave de caché y solo lo volverá a calcular si lo consigue.

Existen diferentes opciones de implementación para el caso en que no se adquiere el bloqueo:

• Espere hasta que se vuelva a calcular el valor.
• Devuelve un "no encontrado" y haz que el cliente gestione adecuadamente la ausencia del valor.
• Mantén un elemento obsoleto en la caché para usarlo mientras se recalcula el nuevo valor.

Si se implementa correctamente, el bloqueo puede prevenir por completo las estampidas, pero requiere una escritura adicional para el mecanismo de bloqueo. Además de duplicar el número de escrituras, el principal inconveniente radica en una implementación correcta del mecanismo de bloqueo que también contemple casos límite, como el fallo del proceso que adquiere el bloqueo, el ajuste del tiempo de vida del bloqueo, las condiciones de carrera, etc.

Esta solución traslada el recálculo del valor de la caché de los procesos que lo necesitan a un proceso externo. El recálculo del proceso externo puede activarse de diferentes maneras:

• Cuando el valor de la caché se acerca a su fecha de caducidad
• Periódicamente
• Cuando un proceso que necesita el valor encuentra un fallo de caché

Este enfoque requiere un componente adicional —el proceso externo— que necesita mantenimiento y supervisión. Además, esta solución exige una separación/duplicación de código poco convencional y es más adecuada para claves de caché estáticas (es decir, no generadas dinámicamente, como en el caso de las claves indexadas por un ID).

Con este enfoque, cada proceso puede recalcular el valor de la caché antes de su vencimiento mediante una decisión probabilística independiente. La probabilidad de realizar el recálculo anticipado aumenta a medida que se acerca la fecha de vencimiento del valor. Dado que cada proceso toma la decisión probabilística de forma independiente, se mitiga el efecto de la sobrecarga, ya que menos procesos expirarán simultáneamente.

Se ha demostrado que la siguiente implementación basada en una distribución exponencial es óptima en términos de su eficacia para prevenir estampidas y la rapidez con la que pueden ocurrir los recálculos. ^{[ 3 ]}

función x-fetch( clave , ttl , beta =1) { valor , delta , expiry ← cache_read( clave ) si (! valor || (tiempo() - delta * beta * log(rand(0,1))) ≥ expiry ) { inicio ← tiempo() valor ← recalcular_valor() delta ← tiempo() – inicio cache_write( clave , ( valor , delta ), ttl ) } valor de retorno } 

El parámetro beta puede establecerse en un valor mayor que 1 para favorecer los recálculos anticipados y reducir aún más las estampidas, pero los autores demuestran que establecer beta = 1 funciona bien en la práctica. La variable delta representa el tiempo necesario para recalcular el valor y se utiliza para escalar la distribución de probabilidad adecuadamente.

Este enfoque es sencillo de implementar y reduce eficazmente la sobrecarga de caché al priorizar automáticamente los recálculos tempranos cuando aumenta el tráfico. Una desventaja es que requiere más memoria en la caché, ya que necesitamos agrupar el delta de valor con el elemento de caché. Cuando el sistema de caché no admite la recuperación del tiempo de expiración de la clave, también necesitamos almacenar la expiración (es decir, time() + ttl ) en el agrupamiento.

• Minimizar las estampidas de caché , Joshua Thijssen, 2010
• Problemas y soluciones para el uso típico de la caché de Perl , Jonathan Swartz, 2008