Sabía por la universidad sobre el filtro Bloom , una estructura de datos probabilística que lleva el nombre de Burton Bloom. Pero no tuve la oportunidad de usarlo. El mes pasado, apareció tal oportunidad, y esta estructura literalmente me fascinó. Sin embargo, pronto encontré algunos defectos en ella. Este artículo es una historia sobre mi breve historia de amor con el filtro Bloom.

En el proceso de investigación de falsificación de IP, fue necesario verificar las direcciones IP en los paquetes entrantes, comparándolas con la ubicación geográfica de nuestros centros de datos. Por ejemplo, los paquetes de Italia no deben ir al centro de datos brasileño. Este problema puede parecer simple, pero en el panorama cambiante de Internet está lejos de ser simple. Baste decir que al final acumulé muchos archivos de texto grandes con aproximadamente el siguiente contenido:

Esto significa que una solicitud de la dirección IP resuelta 192.0.2.1 se registró en el centro de datos de Cloudflare número 107. Estos datos provienen de muchas fuentes, incluidas nuestras muestras activas y pasivas, los registros de algunos dominios que poseemos (por ejemplo,cloudflare.com), fuentes abiertas (por ejemplo, tablas BGP), etc. La misma línea generalmente se repite en varios archivos.

Terminé con un gigantesco conjunto de datos de este tipo. En algún momento, en todas las fuentes recopiladas, conté mil millones de líneas. Por lo general, escribo scripts de bash para preprocesar los datos de entrada, pero en esta escala este enfoque no funcionó. Por ejemplo, la eliminación de duplicados de este pequeño archivo de 600 MiB y 40 millones de líneas de toma ... la eternidad:

Baste decir que las líneas de deduplicación con comandos comunes del tipo sorten varias configuraciones (véase --parallel, --buffer-sizey --unique) no era el mejor para un gran conjunto de tales datos.

Filtros Bloom

Ilustración de David Epstein en el dominio público

Entonces me di cuenta: ¡no ordene las líneas! Debe eliminar duplicados, por lo que algún tipo de estructura de datos 'establecida' funcionará mucho más rápido. Además, conozco aproximadamente el tamaño del archivo de entrada (el número de líneas únicas), y la pérdida de algunos datos no es crítica, es decir, la estructura de datos probabilística es bastante adecuada.

¡Esto es perfecto para los filtros Bloom!

Mientras leeWikipedia en los filtros Bloom, así es como veo esta estructura de datos.

¿Cómo implementaríala pluralidad? Dada una función hash ideal y una memoria infinita, simplemente podemos crear un mapa de bits infinito y establecer un número de bit para cada elementohash(item). Esto proporciona la estructura de datos ideal para la "multitud". ¿Derecha? Trivialmente Desafortunadamente, las funciones hash chocan y la memoria infinita no existe, por lo que en nuestra realidad tenemos que comprometernos. Pero podemos calcular la probabilidad de colisiones y administrar este valor. Por ejemplo, tenemos una buena función hash y 128 GB de memoria. Podemos calcular que la probabilidad de colisión para cada elemento nuevo es de 1 a 1099511627776. Cuando agrega más elementos, la probabilidad aumenta a medida que se llena el mapa de bits.

Además, podemos aplicar más de una función hash y obtener un mapa de bits más denso. Aquí es donde el filtro Bloom funciona bien, que es un conjunto de datos matemáticos con cuatro variables:

n - número de elementos insertados (número cardinal)
m - memoria utilizada por el mapa de bits
k - el número de funciones hash calculadas para cada entrada
p - probabilidad de coincidencia falsa positiva

Dado el número cardinal ny la probabilidad deseada de falsos positivos p, el filtro Bloom devuelve la memoria requerida my el número requerido de funciones hash k.

Echa un vistazo a esta excelente visualización de Thomas Hurst de cómo los parámetros se afectan entre sí.

mmuniq-bloom

Guiado por la intuición, agregué la herramienta probabilística mmuniq-bloom a mi arsenal, que toma la entrada STDIN y devuelve solo líneas únicas en STDOUT. ¡Debería ser mucho más rápido que una combinación de sort+ uniq!

Ahi esta:

mmuniq-bloom.c

Por simplicidad y velocidad, inicialmente establecí algunos parámetros. Primero, a menos que se indique lo contrario, mmuniq-bloom usa ocho funciones hash k = 8. Esto parece estar cerca del número óptimo para nuestro tamaño de datos, y la función hash puede producir rápidamente ocho hashes decentes. Luego alineamos la memoria men el mapa de bits a la potencia de dos para evitar una operación costosa %modulo, que en ensamblador se reduce a lenta div. Si la matriz es igual a la potencia de dos, simplemente podemos usar AND bit a bit (por diversión, lea cómo los compiladores optimizan algunas operaciones de división al multiplicar por una constante mágica ).

Ahora podemos ejecutarlo en el mismo archivo de datos que usamos antes:

¡Oh, eso es mucho mejor! 12 segundos en lugar de dos minutos. El programa utiliza una estructura de datos optimizada, una cantidad relativamente limitada de memoria, un análisis de línea optimizado y un buen almacenamiento en búfer de salida ... y con todo esto, 12 segundos parecen una eternidad en comparación con la herramienta wc -l:

¿Qué está pasando? Entiendo que contar cadenas es wcmás fácil que calcular cadenas únicas, pero ¿está realmente justificada la diferencia de 26 veces? ¿Qué toma la CPU mmuniq-bloom?

Debe ser para calcular hashes. La utilidad wcno gasta el procesador, haciendo todos estos cálculos matemáticos extraños para cada una de las 40 millones de líneas. Utilizo una función hash bastante trivial siphash24, seguro que quema el procesador, ¿verdad? Verifiquemos ejecutando solo la función hash, pero nono realizar operaciones con el filtro Bloom:

esto es extraño. El cálculo de la función hash solo lleva unos dos segundos, aunque todo el programa en la ejecución anterior se ejecutó durante 12 segundos. ¿Un filtro Bloom funciona durante 10 segundos? ¿Cómo es esto posible? Esta es una estructura de datos tan simple ...

Arma secreta - Profiler

Es hora de aplicar la herramienta adecuada para esta tarea: ejecutemos el generador de perfiles y veamos en qué está trabajando el procesador. Primero, corramos stracepara verificar que no haya llamadas inesperadas del sistema:

todo se ve bien. Diez llamadas a mmap4 ms cada una (3971 μs) son interesantes, pero está bien. Precargamos la memoria con MAP_POPULATE, para luego evitar errores debido a la falta de una página.

¿Cuál es el próximo paso? Por supuesto que lo es perf!

Entonces veamos el resultado:

Entonces, realmente quemamos el 87.2% de los ciclos en el código principal. Veamos dónde exactamente. El equipo perf annotate process_line --sourcemuestra inmediatamente algo inesperado.

Vemos que el 26.90% del procesador se quemó enmov, ¡Pero eso no es todo! El compilador inserta correctamente la función y expande el bucle. ¡Resulta que la mayoría de los ciclos van a esto movo a la línea uint64_t v = *p!

Obviamente, el rendimiento es incorrecto, ¿cómo puede una cadena tan simple tomar tantos recursos? Pero repetir la prueba con cualquier otro perfilador muestra el mismo problema. Por ejemplo, me gusta usar google-perftools con kcachegrind debido a los coloridos diagramas:

El resultado de la visualización es el siguiente:

Permítanme resumir lo que hemos descubierto hasta ahora.

La utilidad estándar wcprocesa un archivo de 600 MiB durante 0,45 s de tiempo de procesador. Nuestra herramienta optimizada mmuniq-bloomfunciona 12 segundos. El procesador se graba en una instrucción mov, desreferenciando la memoria ...

Imagen de Jose Nicdao , CC BY / 2.0

¡Oh! Como podría olvidarlo. ¡El acceso aleatorio a la memoria esrealmentelento! ¡Muy, muy, muy lento!

De acuerdo con losnúmeros que todo programador debe saber, un solo acceso a la RAM toma alrededor de 100 ns. Vamos a contar: 40 millones de líneas, 8 hashes cada una. Dado que nuestro filtro Bloom tiene un tamaño de 128 MiB, ennuestro hardware antiguono cabe en el caché L3. Los hashes se distribuyen uniformemente en una amplia gama de memoria: cada uno de ellos genera una pérdida de caché. Ponlo todo junto, y resulta ...

Resulta que 32 segundos se queman solo en accesos de memoria. El programa real se ajusta en solo 12 segundos, porque el filtro Bloom todavía se beneficia del almacenamiento en caché. Esto es fácil de ver con perf stat -d:

Sí, deberíamos haber tenido un mínimo de 320 millones de errores de caché (LLC-load-miss), pero solo sucedieron 280 millones: esto todavía no explica por qué el programa funcionó en solo 12 segundos. Pero no importa. Es importante que el número de errores de caché sea un problema real, y solo podemos resolverlo reduciendo el número de accesos a la memoria. Intentemos configurar el filtro Bloom para usar solo una función hash:

¡Ay! ¡En verdad duele! Para obtener una probabilidad de colisión de 1 por 10,000 líneas, el filtro Bloom requería 64 gigabytes de memoria. ¡Es horrible!

Además, no parece que la velocidad haya aumentado significativamente. Le tomó 22 segundos al sistema operativo preparar la memoria para nosotros, pero aún pasamos 11 segundos en el espacio del usuario. Creo que ahora todas las ventajas de un acceso más raro a la memoria se compensan con una menor probabilidad de ingresar a la memoria caché debido al gran aumento del tamaño de la memoria. Anteriormente, ¡128 MiB eran suficientes para el filtro Bloom!

Rechazar los filtros de floración

Esto se está volviendo ridículo. Para reducir la probabilidad de falsos positivos, debe usar muchos hash en el filtro Bloom (por ejemplo, ocho) con muchos accesos a la memoria, o dejar una función hash, pero use grandes cantidades de memoria.

En realidad no tenemos un límite de memoria, queremos minimizar el número de llamadas a él. Necesitamos una estructura de datos que cueste un máximo de una pérdida de caché por elemento y use menos de 64 gigabytes de RAM ...

Por supuesto, puede implementar estructuras de datos complejas, como un filtro de cuco , pero ciertamente hay una opción más fácil. ¿Qué pasa con la buena y antigua tabla hash de sondeo lineal?

Ilustración de Vadims Podans

Conoce a mmuniq-hash

Aquí está la nueva versión de mmuniq-bloom usando una tabla hash:

mmuniq-hash.c

En lugar de los bits para el filtro Bloom, ahora almacenamos hashes de 64 bits de la función 'siphash24' . Esto proporciona una protección mucho mejor contra colisiones de hash: mucho mejor que una por cada 10.000 líneas.

Contemos. Agregar un nuevo elemento a una tabla hash, digamos con 40 millones de entradas, da la posibilidad de colisiones hash 40 000 000/2^64. Esto es aproximadamente 1 en 461 mil millones, una probabilidad bastante baja. ¡Pero no agregamos un elemento al conjunto precargado! En cambio, agregamos 40 millones de filas al conjunto inicialmente vacío. Según la paradoja del cumpleaños , esto aumenta enormemente la probabilidad de colisiones. Una aproximación razonable sería una estimación '~n^2/2m, en nuestro caso es~(40M^2)/(2*(2^64)). Resulta una posibilidad de 23,000. En otras palabras, con una buena función hash, esperamos una colisión en uno de los 23,000 conjuntos aleatorios de 40 millones de elementos. Esta es una probabilidad distinta de cero, pero aún mejor que en el filtro Bloom, y es completamente tolerable para nuestro caso de uso.

El código con una tabla hash funciona más rápido, tiene mejores patrones de acceso a la memoria y menor probabilidad de falsos positivos que en el filtro Bloom.

No se alarme por la línea de "conflictos hash", solo muestra cuán llena está la tabla hash. Usamos la detección lineal, así que cuando entramos en el conjunto completo, simplemente tomamos el siguiente vacío. En nuestro caso, tenemos que omitir un promedio de 0.7 conjuntos para encontrar un lugar vacío en la tabla. Esto es normal. Como iteramos sobre los conjuntos en un orden lineal, la memoria debe estar cualitativamente llena.

Del ejemplo anterior, sabemos que nuestra función hash tarda unos dos segundos. Llegamos a la conclusión de que 40 millones de accesos a la memoria tardan unos cuatro segundos.

Lecciones aprendidas

Los procesadores modernos son realmente buenos en el acceso secuencial a la memoria cuando es posible predecir patrones de muestreo (ver captación previa de caché ). El acceso aleatorio a la memoria, por otro lado, es muy costoso.

Las estructuras de datos avanzadas son muy interesantes, pero tenga cuidado. Las computadoras modernas requieren el uso de algoritmos optimizados para caché. Cuando se trabaja con grandes conjuntos de datos que no caben en L3, se prefiere la optimización sobre el número de visitas, en lugar de la optimización sobre la cantidad de memoria utilizada.

Es justo decir que los filtros Bloom funcionan muy bien cuando se colocan en el caché L3. Pero si no, entonces son terribles. Esto no es noticia: los filtros Bloom están optimizados para la cantidad de memoria, no para la cantidad de llamadas. Por ejemplo, verArtículo científico sobre filtros de cuco .

Otra cosa son las discusiones interminables sobre las funciones hash. Honestamente, en la mayoría de los casos esto no importa. El costo de contar incluso las funciones hash complejas parece ser siphash24pequeño en comparación con el costo del acceso aleatorio a la memoria. En nuestro caso, simplificar la función hash traerá solo un pequeño beneficio. El tiempo de CPU se pierde en otro lugar, ¡esperando memoria!

Un colega a menudo dice: “Se puede suponer que los procesadores modernos son infinitamente rápidos. Trabajan a una velocidad infinita, hasta que descansan contra la pared de la memoria ".

Finalmente, no repitas mi error. Siempre debe realizar primero la creación de perfiles conperf stat -dy mire el contador de IPC (instrucciones por ciclo). Si es menos de uno, esto generalmente significa que el programa está atascado esperando memoria. Los valores óptimos son superiores a dos. Esto significa que la carga de trabajo está principalmente en la CPU. Desafortunadamente, en mis tareas, el IPC sigue siendo bajo ...

Superior mmuniq

Con la ayuda de colegas, escribí una versión mejorada de la herramienta mmuniq basada en una tabla hash. Aquí está el código:

mmuniq.c

Puede cambiar dinámicamente el tamaño de la tabla hash, admite entradas con un número cardinal arbitrario. Luego procesa los datos en paquetes, utilizando efectivamente la sugerencia prefetchen la CPU, que acelera el programa en un 35-40%. Tenga cuidado, el uso abundante prefetchen el código rara vez da efecto. Para usar esta función, reordené especialmente los algoritmos. Con todas las mejoras, el tiempo de ejecución se redujo a 2.1 segundos:

el fin

La creación de una herramienta básica que intenta superar a la combinación 'sort / uniq' ha revelado algunas características ocultas de la informática moderna. Después de sudar un poco, aceleramos el programa de más de dos minutos a dos segundos. Durante el desarrollo, aprendimos sobre el retraso en el acceso aleatorio a la memoria, así como el poder de las estructuras de datos compatibles con la caché. Las estructuras de datos extrañas llaman la atención, pero en la práctica a menudo es más eficiente reducir el número de accesos aleatorios a la memoria.

Cuando el filtro de floración no encaja