Cada vez que cambio de trabajo aprendo algo nuevo y esta vez una de esas cosas ha sido los filtros de caché. Cuando el espacio de memoria es limitado pero aún así necesitamos la velocidad que proporciona una caché debemos elegir de forma rápida qué entra en la caché y qué no. Para esa tarea tenemos los filtros, ¿los analizamos?
A través de una librería de Ali Fahadi llamada cuckoo_filter conocí esta técnica para almacenar en memoria únicamente los elementos que han sido requeridos para ser almacenados en caché al menos una vez.
En realidad, los filtros se basan en la creación de una tabla para establecer quienes son miembros de un conjunto de elementos y quienes no. Lo importante es poder determinarlo de forma muy rápida y eficiente consintiendo la posibilidad de obtener un porcentaje (aceptable) de falsos positivos pero no de falsos negativos. Vamos a echar un vistazo a cómo funcionan.
¿Cómo funcionan los filtros con referencia a la caché?
En principio, un sistema de caché funciona como un diccionario. Tenemos una clave y un valor. La clave puede formarse por la unión de los datos necesarios para obtener un cierto valor y los datos generados son datos de acceso costoso dentro del sistema que se almacenan en la caché para ser accesibles por una siguiente vez de forma más rápida.
El tiempo de permanencia en caché dependerá de la naturaleza de cada dato y cuándo pueda cambiar potencialmente. Hay datos que pueden mantenerse en una caché durante horas y otros datos que tan solo mantenemos unos milisegundos o segundos porque cambian con mucha frecuencia. En este último caso almacenar los datos nos ayuda a dar una respuesta rápida ante la solicitud reiterada de una información recién calculada que de ser calculada todas las veces podría poner en riesgo la estabilidad del sistema o degradar la experiencia del usuario.
Cuando invalidamos un resultado, debemos invalidarlo también dentro del filtro. La invalidación sucede cuando un valor cambia por ser eliminado o modificado y por tanto debemos replicarlo a todos los sistemas de caché de que dispongamos para no enviar en una respuesta un dato incorrecto. Como decía Phil Karlton:
Solo hay dos cosas realmente difíciles en la Ciencia de la Computación: invalidación de caché y ponerle nombre a las cosas.
A grandes rasgos no parece complejo. Es decir, el filtro de caché almacena una clave de una petición realizada para saber si se debe almacenar o no un elemento en la caché:
- Si el elemento es la primera vez que se consultó. Se responde de forma negativa. No se almacena nada en caché, pero sí se almacena la clave en el filtro.
- Si es la segunda vez, se responde de forma afirmativa, ya está almacenado en el filtro y por lo tanto se almacena también ahora en la caché.
- En las sucesivas veces, se responderá siempre de forma afirmativa y por tanto se almacenará.
Por tanto, la pregunta al filtro de caché se realiza únicamente cuando un dato no ha sido encontrado dentro de la caché y tras calcularlo queremos saber si deberíamos almacenarlo o no.
El funcionamiento del filtro tiene sentido si nos basamos en un sistema cuyas peticiones puedan ser muy extensas pero su medio de almacenamiento en caché muy limitado. Mientras que aprovechar la caché es positivo para acelerar las consultas, también es verdad que almacenar datos que no se usan mucho no supone una ventaja tampoco y además puede saturar la memoria de la caché haciendo más difícil mantener y actualizar datos que realmente sí sean mucho más empleados que otros.
Es una cuestión de optimización de acceso y almacenamiento. Por lo tanto, teniendo en cuenta sus elementos, podremos entender en las siguientes secciones cómo funcionan los filtros específicos y qué ventajas nos proporcionan:
- Clave: la clave por la que se localiza un elemento. Teniendo presente que se trata de un filtro para determinar si un valor puede o no ser almacenado en la caché, podemos no almacenar la clave completa o incluso almacenar una representación de la clave fácil de calcular. Veremos las opciones proporcionadas por los distintos filtros y sus ventajas e inconvenientes.
- Almacenamiento: la forma en la que se almacenan las claves determina la rapidez para encontrar estas claves cuando las busquemos dentro del sistema. Así mismo podemos encontrar filtros con un tamaño fijo para el almacenamiento de las claves y por lo tanto un algoritmo acorde para determinar cómo introducir nuevos elementos y eliminar antiguos elementos.
- Consulta: la forma en que determinamos si una clave existe dentro del filtro. La búsqueda dentro del almacenamiento, su efectividad y eficiencia. En algunos documentos se menciona a estas consultas como AMQ (Approximate Membership Queries) o consultas de membresía aproximadas.
Teniendo todos estos datos comenzamos revisando los filtros: Bloom, Cuckoo, XOR y Vacuum.
¿Dónde se emplean los filtros?
Encontramos muchos filtros Bloom y estructuras de datos relacionados dentro de sistemas de base de datos para evitar accesos a disco. Una estrategia popular para diseñar motores de base de datos debe soportar actualizaciones frecuentes en el árbol log-structured merge (LSM, o combinación estructurada por registros). A alto nivel, los árboles LSM mantienen un componente rápido en memoria que es combinado, por lotes, a datos en memoria persistente. El componente en memoria acumula actualizaciones de la base de datos así amortizando el coste de modificar el almacenamiento persistente. Para acelerar las búsquedas, muchas implementaciones de árboles LSM usan los filtros Bloom. Por ejemplo: levelDB, RocksDB o WiredTiger.
Google Chrome emplea los filtros Bloom para buscar de forma más rápida URLs dañinas cuando se quiere acceder a una URL concreta.
Bloom filters han estado también siendo usados de forma extensa en reducir la E/S a disco, evitando la búsqueda innecesaria de información en contenido remoto, funciones de red, servicios en dispositivos móviles y dispositivos IoT y muchas aplicaciones de gestión de datos incluyendo joins distribuidos, indexado, metadatos auxiliares y problemas de procesamiento de consultas.
Filtro de Bloom
En julio de 1970, Burton H. Bloom publicó en [Communications of the ACM][COMM-ACM] un artículo titulado Space/Time Trade-offs in Hash Coding with Allowable Errors, traducido sería Compensaciones de Espacio/Tiempo en la Codificación Hash con Errores Permitidos. El documento analiza la pertenencia a un grupo de una serie de mensajes analizados uno a uno, considerando el tamaño del área del hash (espacio), el tiempo requerido para identificar un mensaje como miembro o no del conjunto dado (tiempo) y la frecuencia de errores permitidos.
El filtro Bloom se basa en reservar un espacio de memoria donde cada celda (un bit) estará inicialmente a cero (0) y a través del cálculo de tres números hash entre 0 y N-1, donde N es el tamaño máximo, comprobar si estos elementos están a cero o a uno.
La primera vez que busquemos, obviamente encontraremos todo a cero (0) y por lo tanto sabremos sin lugar a dudas que el mensaje buscado no pertenece al grupo. Podemos en este momento cambiar las celdas marcadas por los hash a uno (1). La próxima vez que empleemos los mismos hash obtendremos todos esos valores a uno (1) y sabremos que sí forma parte del grupo. Podemos entonces almacenar el valor en la caché.
Aunque el sistema puede darnos falsos positivos en caso de colisión de hash con otros valores (en conjunto), nunca nos dará falsos negativos. Es decir, no hay forma de que un valor que esté en el filtro sea determinado como que no esté dentro del grupo.
También te habrás fijado que debido a esta colisión un elemento puede compartir (y de hecho comparte) celdas con otros valores. La invalidación o eliminación del filtro no es posible si queremos mantener la premisa de no emitir falsos negativos.
Ante esta limitación surgieron otros métodos posteriores para intentar solventar este problema:
- Counting Bloom Filters por Li Fan, Pei Cao, Jussara Almeida y Andrei Broder, en el año 2000, emplea contadores en lugar de bits de modo que si el valor es mayor que cero se está empleando y la eliminación consiste en la resta de todos los valores del hash concernientes a un valor concreto.
- Scalable Bloom Filters por Paulo Sérgio Almeida, Carlos Baquero, Nuno Preguiça, David Hutchison, en marzo de 2007, permite incrementar el tamaño del filtro de forma indefinida para mantener la probabilidad de falsos positivos muy alta.
Filtro de Cuco (Cuckoo)
En 2014, Bin Fan, David G. Andersen, Michael Kaminsky y Michael D. Mitzenmacher publicaron un artículo titulado Cuckoo Filter: Practically Better Than Bloom o Cuckoo Filter: Prácticamente Mejor que Bloom. En este artículo analizan los problemas comentados anteriormente sobre los filtros Bloom y proponen un nuevo método. En este caso, los autores pretenden con los filtros de cuco obtener las siguientes ventajas:
- Soporte para agregar y eliminar ítems dinámicamente.
- Proporcionar un rendimiento en búsqueda de ítems mayor que con el filtro Bloom clásico.
- Mayor facilidad de implementación.
- Uso de un menor espacio de almacenamiento para la mayoría de aplicaciones.
El filtro de cuco se basa en almacenar en una tabla las huellas (fingerprints) o representaciones de la clave o dato a almacenar en la caché. La dinámica es simple:
- Se genera la huella del dato.
- Se genera i 1 con la función hash sobre la clave
- Se genera i 2 con el resultado anterior haciendo xor con el valor retornado de hacer el hash sobre la huella del dato.
- Se busca en ambas celdas (i 1 e i 2 ), si alguna de ellas está vacía, se almacena el dato.
En caso de no haber encontrado un hueco con el cálculo inicial de los dos primeros hash entonces entramos en un bucle un poco confuso:
Aleatoriamente elegimos una de las celdas de los dos índices y reemplazamos la vieja huella con la nueva. Entonces calculamos el índice alternativo para la vieja huella y si no hay sitio libre para la vieja huella en su índice alterno buscamos en la siguiente iteración un espacio para esta huella y así hasta que consigamos emplazar todas las huellas o desistamos por alcanzar el número máximo de intentos retornando error.
La generación de la huella se realiza a través del hashing de cuco descrito por Rasmus Pagh y Flemming Friche Rodler en una conferencia en 2001 para evitar al máximo posible colisiones entre las huellas de elementos y así minimizar la probabilidad de falsos positivos.
A diferencia de Bloom, donde necesitamos calcular y modificar tres posiciones, en este caso solo necesitamos calcular tres posiciones en el peor escenario.
Algunas implementaciones en lugar de retornar un error eliminan el último valor encontrado en colisión de la tabla. Esto es contraproducente porque agrega la posibilidad de encontrar falsos negativos. Dependerá de nuestras necesidades, no obstante.
Filtro de Vacío (Vacuum filter)
En 2019, para la edición de VLDB (Very Large Data Base) de Los Angeles, Minmei Wang, Mingxun Zhou, Shouqian Shi y Chen Qian presentaron un documento titulado Vacuum Filters: More Space-Efficient and Faster Replacement for Bloom and Cuckoo Filters o Filtros de Vacío: Un Reemplazo Más Eficientes en Espacio y Más Rápido para los Filtros Bloom y Cuco.
El nombre proviene del envasado al vacío que utiliza el menor espacio para empacar artículos.
Este tipo de estructura de datos para soportar consultas de membresía (AMQ), proporciona mejores ventajas a opciones anteriores. Similar a los filtros cuco, los filtros de vacío también almacenan huellas en una tabla. Las mejoras de eficiencia en memoria y rendimiento vienen determinados por un innovación en la estrategia de inserción y eliminación de las huellas.
Según el documento consigue una decrementar el uso de memoria con respecto a los filtros cuco en un 25% y un 15% con respecto a Bloom, además de incrementar el rendimiento 10 veces con respecto a Bloom.
Filtro O-Exclusivo (XOR)
El 27 de enero de 2020, Thomas Mueller Graf y Daniel Lemire, publicaron Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters o Filtros O-Exclusivo: Más rápidos y más pequeños que los filtros Bloom y Cuco.
El proceso de construcción toma como referencia todas las claves posibles. La elección del algoritmo para generar la huella es elegido aleatoriamente. Con la lista de todas las huellas se comienza a buscar un grupo de tres funciones hash que no colisionen entre sí para construir una lista de huellas acorde al algoritmo de comprobación. El algoritmo de comprobación se basa en obtener la huella de un elemento x a través de la aplicación de la operación xor entre los tres elementos generados por las funciones hash elegidas. Por ejemplo, h1(x) nos dará un índice para obtener un valor de la lista de huellas B, por lo tanto:
B[h1(x)] xor B[h2(x)] xor B[h3(x)] = huella(x)Es decir, los tres elementos tomados de la lista de huellas (B) encontrados por las funciones hash correspondientes (h1, h2 y h3), aplicando la operación xor deben coincidir con el contenido de la huella para la clave dada (x).
La publicación promete más velocidad y menor uso de espacio que los filtros Bloom y Cuco pero al precio de tener que crear con antelación todo el conjunto de datos necesario. Si algún dato es modificado, agregado o eliminado es necesaria la recreación completa del filtro. Es una buena opción si nuestro conjunto de datos es muy estático pero no si requiere de modificaciones o ser dinámico.
Conclusiones
En la página de Tenzir analizan en un artículo diferentes implementaciones de los filtros de caché mostrando los datos recabados a modo de bancos de pruebas. Además se menciona otro filtro que no hemos tratado aquí como es el Filtro Morton.
Como vemos, las mejoras y filtros surgen de forma continua y no solo nuevos filtros sino también modificaciones a filtros existentes para intentar cubrir mejor una implementación concreta o un caso de uso concreto.
En caso de necesitar la implementación de alguno de estos mecanismos para aliviar un poco la carga en tu aplicación para saber exactamente si un elemento está disponible. Sobre todo si un elemento no pertenece a un grupo concreto, entonces merece la pena revisar las implementaciones y probarlos.
¿Y tú? ¿Te has planteado implementar algo que permita acelerar tu sistema? ¿Algo más que solo caché? ¿Has implementado o usas alguno de estos filtros y no los conocías? ¿O quizás sí que los conocías desde hace tiempo? ¿Empleas otro diferente? ¡Déjanos tu comentario!
