Filtros de Bloom y optimización fallida
Los filtros de Bloom son conocidos para comprobar si un elemento está en un conjunto de manera eficiente de manera probabilista; esto es, el filtro puede responder cosas como ‘es posible que el elemento esté en el conjunto’ o ‘no está’. Se trata de obtener resultados cuando el conjunto de datos es tan grande que sería poco práctico utilizar otras técnicas más precisas.
En When Bloom filters don’t bloom nos cuentan sobre su uso en la detección de falseamientos de la IP (IP spoofing) para tomar decisiones sobre ellos en Cloudfare. El autor tenía un buen número de IPs recopiladas y al querer eliminar duplicados pensó que podrían servirle.
Nos cuenta detalles de sus desarrollos y la forma de hacerla más eficiente y como se encontró con un conjunto de datos que, aún así, no cabía en su memoria. Su programa invertía mucho tiempo moviendo datos entre las memorias disponibles.
Finalmente, indica algunas de las lecciones aprendidas:
El acceso a memoria secuencial y cuando se pueden predecir los siguientes accesos es algo que funciona bien en las CPUs modernas.
Modern CPUs are really good at sequential memory access when it’s possible to predict memory fetch patterns
Las estructuras de datos avanzadas son interesantes, pero hay que tener en cuenta el hardware y sus condicionantes (en este caso, las cachés).
Advanced data structures are very interesting, but beware. Modern computers require cache-optimized algorithms. When working with large datasets, not fitting L3, …
También algún comentario sobre el perfilado de programas.
Interesante.