- El muestreo por reservorio es una técnica única y eficiente para extraer una muestra aleatoria de forma justa cuando no se conoce el tamaño de los datos
- Se utiliza en distintos ámbitos, como la recolección de logs en tiempo real, porque permite resolver de manera eficiente situaciones que los métodos tradicionales no pueden manejar
- La idea central es actualizar el espacio de almacenamiento con probabilidad 1/n cada vez que aparece un nuevo elemento, dando a todos los elementos la misma oportunidad de ser elegidos
- Si se quieren seleccionar varias muestras, la probabilidad se amplía a k/n y, según esa probabilidad, una muestra existente se reemplaza aleatoriamente
- Este algoritmo garantiza un muestreo justo usando poca memoria, y mejora la eficiencia y confiabilidad del procesamiento en tiempo real
Concepto y necesidad del muestreo por reservorio
- El muestreo por reservorio es una técnica eficiente para extraer muestras de manera justa de un conjunto de datos cuyo tamaño total se desconoce
- En general, cuando se conoce el tamaño de los datos, elegir un índice aleatorio es un método efectivo, pero cuando el tamaño no se conoce, ese enfoque no es posible
- En grandes volúmenes de datos que llegan de forma lineal (por ejemplo, un flujo de logs), es necesario limitar el uso de memoria y, al mismo tiempo, asegurar que cada dato tenga la misma probabilidad de ser elegido
Muestreo cuando se conoce el tamaño
- En un conjunto de tamaño limitado (por ejemplo, 10 cartas), el método de barajar todos los elementos y elegir desde el inicio la cantidad deseada es adecuado para garantizar la equidad
- Aprovechando la estructura de arreglo de una computadora, se pueden elegir índices aleatorios directamente para extraer muestras con rapidez
- Sin embargo, en la práctica, este enfoque resulta ineficiente con millones de datos o con flujos de tamaño desconocido
Muestreo cuando no se conoce el tamaño: problemas y necesidad
- En la realidad, con frecuencia se da la situación de recibir datos uno por uno, poder guardar solo 1 y no poder volver a revisar los datos que ya pasaron
- En sistemas de recolección de logs, por ejemplo, puede haber picos repentinos de tráfico, y en esos casos es necesario enviar solo una parte mediante muestreo para evitar la sobrecarga del servidor
- Elegir arbitrariamente solo los primeros elementos no da la misma oportunidad a todos los ítems, lo que genera un problema de falta de equidad
Principio del algoritmo de muestreo por reservorio
- Cada vez que llega un dato, se calcula n como la cantidad recibida hasta ese momento, y se hace que el nuevo dato sea elegido con probabilidad 1/n
- El primer dato se elige obligatoriamente y, después, cada dato nuevo reemplaza al existente con una probabilidad cada vez menor, manteniendo así una probabilidad de selección uniforme
- Al final, cualquier dato del conjunto total tiene la misma probabilidad de quedar almacenado
- No se basa en lanzar una moneda, sino en usar una probabilidad de 1/n para garantizar una oportunidad justa a todos los datos
Intuición matemática (explicada con el ejemplo de cartas)
- 1er dato: se elige obligatoriamente (la probabilidad es 1/1)
- 2do dato: se elige con probabilidad 1/2, y el dato anterior solo permanece con 50% de probabilidad
- 3er dato: el nuevo dato se elige con 1/3, y para los datos anteriores la probabilidad de supervivencia se acumula con el valor complementario de esa probabilidad
- En general, al incluir hasta el n-ésimo dato, todos los datos siempre tienen una probabilidad de 1/n
Extensión para seleccionar varias muestras (k-out-of-n)
- Para extraer k muestras, cada dato nuevo se elige con probabilidad k/n y, si resulta elegido, reemplaza aleatoriamente uno de los elementos almacenados
- Este método también hace que todos los elementos guardados tengan la misma probabilidad de permanecer como muestra
- Usando solo memoria constante (k elementos), permite extraer varias muestras de manera justa incluso en flujos de datos muy grandes
Uso del muestreo por reservorio en servicios de recolección de logs
- De los logs que entran cada segundo, se eligen como máximo k (por ejemplo, 5) mediante muestreo por reservorio, y solo esas muestras se envían al servidor
- Cuando hay pocos datos, todos los logs se envían sin pérdidas; y cuando el tráfico se dispara, no se envían más de k, lo que permite garantizar la estabilidad del servicio
- Enviar muestras a intervalos regulares introduce un pequeño retraso en tiempo real, pero en conjunto ayuda a asegurar estabilidad y eficiencia de costos
Aplicaciones adicionales y material de referencia
- Si algunos datos (por ejemplo, logs de error) son más importantes, se puede usar la variante de muestreo por reservorio ponderado (Weighted Reservoir Sampling)
- Los conceptos más avanzados aparecen en materiales externos como Wikipedia, pero el principio básico sigue siendo mantener la equidad
Conclusión
- El muestreo por reservorio es un algoritmo muy elegante y práctico que permite hacer un muestreo justo y eficiente en memoria sobre flujos de datos de tamaño desconocido
- En el procesamiento de datos en tiempo real, ofrece ventajas como rapidez, consistencia y bajo uso de recursos, por lo que tiene un alto valor de aplicación en muchos campos
1 comentarios
Comentarios de Hacker News
Cuando era niño y vivía en el campo, un amigo de mi padre tenía que medir profesionalmente cada año la población de ptarmigan (lagópodos) en las montañas.
Lo hacía siguiendo una ruta determinada y espantando a las aves a intervalos regulares para que levantaran vuelo, luego las contaba.
Entregaba esas cifras a la oficina encargada, y allí estimaban la población total.
Un año, como este amigo estaba en el extranjero, le explicó el método en detalle a otro amigo y le pidió que lo hiciera por él.
Pero cuando llegó la fecha real del estudio, ese amigo simplemente se olvidó, y como le daba flojera, mandó unos números inventados que sonaban plausibles.
Al año siguiente, en la portada del periódico local salió el titular: “aumento récord en la población de ptarmigan”.
El motivo de que un cambio tan brusco fuera noticia era que esas cifras se usaban para decidir los permisos de caza. El amigo no había pensado en eso
Una vez, trabajando en el sistema de reservaciones de un gran centro de esquí, tuve que terminar un informe estadístico oficial (para entregar al gobierno, con datos como noches de hospedaje de los huéspedes).
Estábamos tan cortos de tiempo que trabajamos toda la noche, y los datos estadísticos de ese año quedaron muy lejos de los valores reales
¡Hola! o/
Soy el autor de este artículo. Preguntas y comentarios son bienvenidos.
El código de todos los posts está disponible bajo licencia MIT en https://github.com/samwho/visualisations. Siéntanse libres de usarlo
Me parece un post muy bueno.
Otra dirección para optimizar reservoir sampling, en lugar de sacar un número aleatorio para cada ítem y verificar si se reemplaza, es muestrear saltos desde una distribución geométrica.
Es interesante en casos como una tape drive, donde puedes saltarte muchos elementos a bajo costo (aunque no se conozca de antemano la longitud de la cinta, puedes dejar dormida la mayor parte del sistema mientras haces el salto).
Para sacar una muestra de tamaño k entre n elementos, solo necesitas aproximadamente O(k * log(n/k)) operaciones de muestreo y salto.
Otro concepto que me gusta es asignar una prioridad aleatoria conforme llega cada carta y conservar las k más altas.
Aquí hay un problema relacionado: cómo seleccionar solo los top k ítems en un stream de longitud desconocida en O(n) tiempo y O(k) espacio.
Metes todo en un buffer desordenado de tamaño 2*k y, cuando se llena, usas quickselect aleatorizado o median-of-medians para quedarte solo con los top k.
Si haces esto a lo largo de n elementos, toma O(n) tiempo.
Otra técnica relacionada e interesante es rendezvous hashing.
Y para alias method, sirve bastante este artículo: https://www.keithschwarz.com/darts-dice-coins/
Me pregunto si este método puede usarse de forma anidada.
Por ejemplo, si hago reservoir sampling en mi servicio y el servicio recolector de logs también hace reservoir sampling, ¿el resultado sería equivalente a usar solo el recolector de logs?
Me gustaron especialmente la animación y la explicación.
En particular, fue muy llamativa la variedad de interacciones, como mezclar 100 veces en el gráfico.
Al principio me confundió un poco que, tras hablar de elegir 3 cartas entre 10 o entre 436,234, de repente cambiara al ejemplo de mirar solo una carta a la vez y elegir 1 carta.
Creo que ayudaría agregar una separación de sección en la parte de “¡Ahora voy a lanzar una curva!”.
En ese punto ya estamos suponiendo que solo tenemos 1 carta en la mano y que ni siquiera conocemos el tamaño del mazo
Me gustó especialmente el diseño del sitio.
Las interacciones, el personaje del perrito, la tipografía, los colores y el layout general, todo me gustó
Todo el blog se siente como un tesoro escondido.
Me alegró encontrarlo
Me gustaron los gráficos.
Pero no estoy seguro de que este método sea completamente sólido desde el punto de vista estadístico. Todos los logs dentro de un periodo tienen la misma probabilidad de ser elegidos, pero me preocupa si los logs generados en periodos “lentos” terminan sobrerrepresentados en la estadística total.
Por ejemplo, si quieres averiguar qué endpoint consumió más CPU en todo el sistema para optimizarlo, ¿no pasaría que los logs de endpoints con picos temporales de tráfico quedarían subrepresentados, haciendo difícil evaluar correctamente cuál endpoint se usó más en realidad?
O también en planeación de capacidad por servicio, parece que los servicios con tráfico en ráfagas quedarían subrepresentados.
Me da curiosidad para qué casos de uso encaja bien reservoir sampling y qué tipos de análisis estadístico se pueden hacer con este método
Muy buen artículo; así es como deberían enseñarse las matemáticas y la estadística para que sea divertido aprenderlas.
Me dio vibras parecidas a https://distill.pub/
Me impactó la frase “Sometimes the hand of fate must be forced”
Me gusta especialmente la forma en que está hecha la interacción
Me parece realmente hermoso tanto el diseño del sitio como la forma de enseñar. Gracias
Me pregunto si el blog tiene feed RSS
Es un post muy claro y bien ilustrado.
Como extensión más avanzada, también existen algoritmos que calculan cuántos elementos saltarse cada vez en lugar de usar el método básico.
Para una explicación más detallada, vale la pena ver https://richardstartin.github.io/posts/reservoir-sampling
Buen artículo y buena explicación.
Para la recolección real de logs, recomiendo intentar primero varios enfoques y dejar la fairness como último recurso.
Por ejemplo, asignar prioridades a los logs y descartar primero los de menor prioridad (los de mayor verbosidad).
En los logs que en conjunto representan una sola actividad, reducir los logs repetitivos intermedios y conservar solo el inicio, el final y los cambios de estado importantes.
Si agregas y resumes logs similares o duplicados, también reduces el volumen total y te resulta más fácil detectar tendencias
Últimamente he estado investigando mucho sobre observability, y el método mencionado es un enfoque híbrido de head/tail sampling.
Se puede consultar una explicación relacionada aquí: https://docs.honeycomb.io/manage-data-volume/sample/
El artículo también habla de esta parte.
De hecho, más que descartar todos los logs de baja prioridad, lo importante es aplicar el concepto de “presupuesto” para limitarlos.
La cantidad total de logs también puede limitarse con un presupuesto superior aparte.
Reservoir sampling también maneja bien este tipo de restricciones
Buen artículo y buena explicación.
En el paper de Vitter se describe “Algorithm R”, que es una forma de reservoir sampling.
Se puede consultar en https://www.cs.umd.edu/~samir/498/vitter.pdf
Un paper anterior de Vitter, https://dl.acm.org/doi/10.1145/358105.893, cita el volumen 2 de TAOCP de Knuth, pero Knuth tampoco da una fuente clara
Está muy bien organizado, y si te interesa weighted reservoir sampling, se explica en https://gregable.com/2007/10/reservoir-sampling.html
También hay un método que se aplica fácilmente en entornos distribuidos con map-reduce, y otro muy simple que consiste en emparejar cada ítem con un valor aleatorio y conservar el Top N
El método básico de sacar una prioridad con POW(RANDOM(), 1.0 / weight) para cada ítem y luego elegir el Top N tiene problemas de estabilidad numérica cuando los pesos son muy grandes o muy pequeños.
Además, la muestra resultante puede no reflejar suficientemente bien la distribución de la población original. En especial, esa tendencia se vuelve fuerte cuando el peso total está concentrado en unos pocos ítems.
Aun así, en la mayoría de los casos sigue siendo una aproximación suficientemente buena.
Más detalles en https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html
Este artículo me recordó el método que usaron los Aliados en la Segunda Guerra Mundial para estimar la producción de tanques alemanes a partir de sus números de serie.
El personal en campo estimaba una producción unas 5 veces mayor que la real, pero el método de los números de serie tuvo una precisión de más del 90%
Excelente publicación, y las visualizaciones son realmente sobresalientes.
En producción usamos una variante parecida para estimar en tiempo real percentiles cambiantes sobre streams muy grandes.
El valor del percentile cambia de vez en cuando, pero por lo general se mantiene durante muchísimas repeticiones. Los datos subyacentes son quasi-stationary.
Con respaldo en un splay tree, se puede estimar en tiempo amortizado O(1), aunque con un rango de error más amplio por uso de RAM que otros métodos.
También se puede ajustar la probabilidad de reemplazo para acortar la “half-life” de los datos; es decir, sesgar la estimación hacia datos más recientes
Desde el punto de vista de ciencia de datos, creo que la cantidad de datos en sí misma contiene información importante, así que la tasa de muestreo debe registrarse junto con los datos.
Por ejemplo, si la tasa de muestreo es 10%, puedes registrar 10 por muestra para reconstruir y estimar correctamente conteos totales, sumas, promedios, etc.
Este post muestra muy bien los trade-offs que tiene la recolección de telemetry (traces, logs, metrics).
Este campo del análisis de datos tiene una barrera de entrada alta y es un área que muchos desarrolladores pasan por alto
Aunque los datos parezcan iguales, la gráfica observada puede cambiar por completo dependiendo de cómo se muestrearon, y mucha gente pasa esto por alto