Los informáticos han creado un algoritmo muy eficaz, aunque increíblemente sencillo, para determinar qué elementos se eliminarán del caché web para dejar espacio a otros nuevos. El nuevo algoritmo de código abierto, conocido como SIEVE, tiene el potencial de transformar la gestión del tráfico web a escala.
SIEVE es un proyecto conjunto entre científicos informáticos de la Universidad Emory, la Universidad Carnegie Mellon y la Fundación Pelican. El trabajo del equipo sobre SIEVE se presentará el día 21.calle Simposio USENIX sobre diseño e implementación de sistemas en red (NSDI) en Santa Clara, California, en abril.
La versión preliminar del artículo ya está causando sensación.
«SIEVE es cada vez más grande que nosotros», dice Yazhou Zhang, estudiante de doctorado en la Universidad Emory y coprimer autor del artículo. «Ya está funcionando bien, pero estamos recibiendo muchas buenas sugerencias para mejorarlo aún más. Esa es la belleza del mundo del código abierto».
Zhang fue coautor del artículo con Junqing (Jason) Yang, quien obtuvo una maestría en ciencias de la computación de la Universidad Emory y ahora es candidato a doctorado en la Universidad Carnegie Mellon.
«SIEVE es una mejora fácil de un algoritmo de desalojo de caché probado y verdadero que se ha utilizado durante décadas, lo que es literalmente como siglos en el mundo de la informática», afirma Ymir Vijfusson, profesor asociado del Departamento de Ciencias de la Computación de Emory. Universidad.
Vigfusson es coautor principal de este artículo, junto con Rashmi Vinayak, profesor asociado en el Departamento de Ciencias de la Computación de la Universidad Carnegie Mellon. Yao Yu, ingeniero informático de la Fundación Pelican, también es coautor.
Además de su velocidad y eficiencia, el principal factor que genera interés en SIEVE es su simplicidad, que se presta a la escalabilidad.
“La simplicidad es el colmo de la sofisticación”, dice Vigfusson. «Cuanto más simples sean las piezas dentro de un sistema diseñado para servir a miles de millones de personas en una fracción de segundo, más fácil será implementar y mantener ese sistema de manera eficiente».
Tenga a mano las «cosas calientes»
Mucha gente comprende el valor de reorganizar periódicamente su guardarropa. Los artículos que nunca se usan se pueden desechar y los artículos que rara vez se usan se pueden trasladar al ático o a otro lugar remoto. Esto deja los elementos más comunes a mano para poder encontrarlos rápidamente, sin tener que buscarlos.
Un caché es como un armario bien organizado para los datos de la computadora. El caché se llena con copias de los objetos más comunes solicitados por los usuarios, u «objetos calientes» en la terminología de TI. El caché mantiene esta pequeña colección de objetos calientes separada de la base de datos principal de la red informática, que es como un vasto depósito lleno de toda la información que el sistema puede proporcionar.
El almacenamiento en caché de objetos calientes permite que un sistema en red funcione de manera más eficiente y responda rápidamente a las solicitudes de los usuarios. La aplicación web puede manejar efectivamente más tráfico ingresando a un casillero fácil de usar para tomar la mayoría de los objetos que los usuarios desean en lugar de viajar al almacén y buscar en una enorme base de datos para cada pedido.
«El almacenamiento en caché está en todas partes», afirma Chang. «Es importante para todas las empresas, ya sean grandes o pequeñas, que utilizan aplicaciones web. Cada sitio web necesita un sistema de almacenamiento en caché».
Sin embargo, el almacenamiento en caché está relativamente poco estudiado en informática.
¿Cómo funciona el almacenamiento en caché?
Si bien se puede considerar el almacenamiento en caché como un armario bien organizado para una computadora, es difícil saber qué debe guardarse en ese armario cuando lo utilizan millones de personas, con necesidades en constante cambio.
Ejecutar una memoria caché rápida es costoso pero esencial para una buena experiencia de usuario web. El objetivo es mantener la información futura más útil dentro del caché. Otros organismos deben ser constantemente tamizados, o «expulsados» en términos técnicos, para dejar espacio a la siempre cambiante variedad de organismos calientes.
Los algoritmos de desalojo de caché determinan qué objetos deben eliminarse y cuándo.
FIFO, o “primero en entrar, primero en salir”, es un algoritmo de desalojo clásico desarrollado en la década de 1960. Imagine objetos alineados sobre una cinta transportadora. Los objetos solicitados recientemente ingresan por la izquierda y los objetos más antiguos se eliminan cuando llegan al final de la línea a la derecha.
En el algoritmo LRU, o «menos recientemente utilizado», los objetos también se mueven a lo largo de la línea hacia una eventual evacuación. Sin embargo, si se vuelve a pedir un objeto mientras desciende por la cinta transportadora, volverá al principio de la línea.
Existen cientos de variaciones de algoritmos de evacuación, pero tienden a requerir un mayor grado de complejidad para lograr eficiencia. Esto generalmente significa que pasan desapercibidos y requieren un alto mantenimiento, especialmente cuando se trata de grandes cargas de trabajo.
«Si un algoritmo es demasiado complejo, tiende a tener más errores, y todos esos errores deben corregirse», explica Zhang.
idea sencilla
Al igual que LRU y algunos otros algoritmos, SIEVE realiza una modificación simple al sistema FIFO básico.
SIEVE inicialmente nombra el objeto solicitado como «cero». Si se vuelve a llamar al objeto mientras se mueve hacia abajo por el cinturón, su estado cambiará a «uno». Cuando un objeto marcado como «uno» llega al final de la línea, se restablece automáticamente a «cero» y se expulsa.
El cursor, o «mano en movimiento», también borra objetos a medida que se mueven a lo largo de la línea. El cursor comienza al final de la línea y luego se mueve hacia el encabezado y se mueve en un círculo continuo. Cada vez que el cursor hace clic en un objeto llamado «cero», el objeto es expulsado.
«Es importante eliminar las cosas impopulares lo más rápido posible, y SIEVE es muy rápido en esta tarea», dice Zhang.
Además de esta rápida degradación de objetos, SIEVE logra mantener objetos comunes en la caché con un mínimo esfuerzo computacional, lo que se conoce como “actualización diferida” en terminología informática. Los investigadores creen que SIEVE es el algoritmo de borrado de caché más simple para lograr de manera efectiva una degradación rápida y una actualización lenta.
Menos tasa de pérdida
El propósito del almacenamiento en caché es lograr una tasa de falla baja: la fracción de objetos solicitados que deben recuperarse del «repositorio».
Para evaluar SIEVE, los investigadores realizaron experimentos con rastros de caché web de código abierto de Meta, Wikimedia, X y otros cuatro grandes conjuntos de datos. Los resultados muestran que SIEVE logra una tasa de error menor que nueve algoritmos de última generación en más del 45% de las trazas. El siguiente mejor algoritmo tiene una tasa de error más baja, de sólo el 15%.
La facilidad y simplicidad de SIEVE plantea la pregunta de por qué a nadie se le ocurrió este método antes. Zhang sostiene que el enfoque del equipo SIEVE en cómo han cambiado los patrones de tráfico web en los últimos años puede haber marcado la diferencia.
«Por ejemplo, los artículos nuevos ahora se vuelven 'cool' rápidamente, pero también desaparecen rápidamente. La gente pierde constantemente el interés en las cosas porque constantemente aparecen cosas nuevas», dice.
Las cargas de trabajo de caché web tienden a seguir lo que se conoce como distribuciones Zipfian generalizadas, donde un pequeño subconjunto de objetos representa una gran proporción de solicitudes. Es posible que SIEVE haya alcanzado un punto óptimo en Zipfian para sus cargas de trabajo actuales.
«Este es claramente un momento transformador para nuestra comprensión del borrado de caché en la web», afirma Vigfusson. «Cambia una construcción que se ha utilizado a ciegas durante tanto tiempo».
Añade que incluso una simple mejora en un sistema de almacenamiento en caché web podría ahorrarle millones de dólares a un importante centro de datos.
Zhang y Yang están en camino de recibir sus doctorados en mayo.
«Hacen un gran trabajo», dice Vigfusson. «Es seguro decir que ambos se encuentran ahora entre los expertos del mundo en limpieza de caché web».
/Liberación General. Este material de la organización/autores originales puede ser de naturaleza cronológica y está editado para mayor claridad, estilo y extensión. Mirage.News no asume posiciones corporativas ni partes, y todos los puntos de vista, posiciones y conclusiones expresadas en este documento son únicamente las de los autores. Ver en su totalidad aquí.
«Estudiante amistoso. Jugador certificado. Evangelista de las redes sociales. Fanático de Internet. Se cae mucho. Futuro ídolo adolescente».