Reservoir sampling: un método de extracción aleatoria justa para datos de tamaño desconocido

• Reservoir sampling es una técnica de extracción que, incluso en un flujo de datos cuyo tamaño total se desconoce, mantiene en memoria solo una cantidad fija de elementos y da a todos la misma oportunidad de ser elegidos.
• Para un arreglo de tamaño conocido basta con barajarlo o hacer una selección de índices aleatorios, pero en un stream donde no se puede volver a elementos ya vistos se necesita otro enfoque.
• Para seleccionar un solo elemento, se adopta el elemento n con una probabilidad de 1/n, equilibrando la posibilidad de selección del nuevo elemento con la posibilidad de supervivencia de los elementos existentes.
• Al extraer varios elementos, se adopta el nuevo elemento con una probabilidad de k/n según la cantidad k a conservar y, si es necesario, se reemplaza aleatoriamente uno de los elementos actualmente guardados.
• Aplicado a la recolección de logs, permite no superar un límite de procesamiento como máximo 5 por segundo, y al mismo tiempo reducir tanto la pérdida de logs en periodos tranquilos como el uso de memoria.

---

Muestreo en un conjunto de tamaño conocido

• Si se quieren sacar 3 cartas al azar de un mazo de 10, basta con barajar todo el mazo y tomar las primeras 3 para dar a cada carta la misma probabilidad de selección.
• Si el mazo crece a 1 millón de cartas, barajarlo directamente se vuelve difícil, pero en una estructura accesible por índice, como un arreglo, se logra el mismo objetivo eligiendo 3 índices aleatorios.
• En un arreglo en memoria es fácil acceder a un índice específico, pero contar hasta la carta 436,234 en un mazo físico tomaría mucho tiempo en la práctica.

Restricciones que aparecen en un stream de tamaño desconocido

• Si solo se puede ver 1 carta a la vez, sostener 1 carta al mismo tiempo y no se puede volver a cartas ya vistas, hay que elegir la carta final sin conocer el total.
• Un servicio de recolección de logs se enfrenta a un problema parecido.
  • Recibe mensajes de log de otros servicios y los almacena en un solo lugar.
  • Si los logs se disparan por un mal release o un aumento repentino de tráfico, el servicio de recolección puede verse sobrepasado.
• El servicio de recolección de logs del ejemplo tiene un umbral que le permite procesar 5 logs por segundo.
• Enviar solo el 10% de los logs ayuda a no superar el umbral durante picos, pero también descarta innecesariamente el 90% de los logs en periodos tranquilos.
• El comportamiento deseado es enviar todos los logs en periodos tranquilos y, durante picos, enviar como máximo 5 por segundo.
• Si cada segundo se envían solo los primeros 5 logs vistos, los logs que llegan después pierden la oportunidad de ser elegidos, así que no es justo.

Reservoir sampling de un solo elemento

• Reservoir sampling mantiene una muestra justa entre los elementos vistos hasta el momento, incluso sin conocer el total.
• También se podrían guardar todos los mensajes en memoria y elegir después, pero si no se conoce la magnitud del pico, es difícil predecir cuánta memoria hará falta.
• Este método resuelve el mismo problema sin usar más memoria que la cantidad de muestras solicitada.
• La regla para elegir una sola carta es simple:
  • La primera carta siempre se conserva.
  • La nueva carta n se conserva con una probabilidad de 1/n.
  • Si se decide conservar la nueva carta, se descarta la carta conservada anteriormente.
• Si se reemplaza con 50% de probabilidad en cada carta, las cartas del final tienen ventaja y el método no es justo.
  • Para que la primera carta siga estando después de la décima, debe sobrevivir a múltiples oportunidades de reemplazo.
  • La última carta puede quedar en la mano con que sea elegida una sola vez.
• La regla 1/n equilibra no solo la probabilidad de selección de la nueva carta, sino también la probabilidad de supervivencia de las cartas existentes.
  • La primera carta se conserva con probabilidad de 1/1, es decir, 100%.
  • En la segunda carta, la nueva se elige con probabilidad de 1/2, y la primera también permanece con probabilidad de 1/2.
  • En la tercera carta, la nueva se elige con probabilidad de 1/3, y la carta conservada existente también queda con 50% × 2/3, es decir, probabilidad de 1/3.
• En general, en el paso n la probabilidad de que una carta existente permanezca es 1/(n-1) * (1-(1/n)), y la probabilidad de que la nueva carta sea elegida es 1/n, por lo que ambas se igualan.

Extensión para extraer varios elementos

• La selección de un solo elemento puede extenderse a la selección de varios elementos.
• Para seleccionar k elementos, cambian dos reglas:
  • El nuevo elemento se selecciona con probabilidad de k/n, no 1/n.
  • Si hace falta reemplazar, se elige aleatoriamente uno de los k elementos actualmente conservados y se cambia por el nuevo elemento.
• La probabilidad de selección de los elementos existentes se expresa como k/(n-1), y al multiplicarla por la probabilidad de no ser reemplazados por el nuevo elemento, se mantiene la justicia.
• Como todos los elementos conservados tienen la misma probabilidad de ser objetivo de reemplazo, en cada paso también se mantiene igual la posibilidad de que cada elemento siga estando.
• La implementación se resume en usar un arreglo de tamaño k:
  • Para cada nuevo elemento, se genera un número aleatorio entre 0 y n.
  • Si el número aleatorio es menor que k, se reemplaza el elemento de ese índice por el nuevo elemento.
  • Si no, se descarta el nuevo elemento.

Aplicarlo a un servicio de recolección de logs

• En el ejemplo de recolección de logs, se configura k=5 para conservar como máximo 5 mensajes de log a la vez.
• Cada segundo se envían los logs seleccionados al servicio de recolección de logs y, después, se vacía el arreglo de tamaño 5 y se empieza de nuevo.
• Este método crea un patrón por lotes, enviando grupos de logs a intervalos regulares en lugar de un stream de logs en tiempo real.
• A cambio, la cantidad de logs transmitidos no supera el umbral y, en periodos tranquilos, el total de logs y los logs transmitidos se mueven casi juntos.
• En periodos tranquilos no se pierden logs; durante picos no se envían más logs que el umbral por segundo, y el espacio de almacenamiento tampoco supera los k=5 logs.

Cuando se necesitan pesos

• Algunos logs pueden ser más valiosos que otros.
• Por ejemplo, quizá se quieran conservar todos los logs de error.
• En esos casos se puede usar una variante de reservoir sampling con pesos.
• Reservoir sampling es un algoritmo que permite resolver con poca memoria un problema de muestreo de streams que al principio parece imposible.

[GN⁺]

Opiniones de Hacker News

• Cuando era chico vivía en el campo, y escuché que un amigo de mi padre, por su trabajo, tenía que contar cada año la población de lagópodos alpinos en la montaña.
  Caminaba por una ruta definida, hacía que las aves se asustaran y levantaran vuelo a intervalos regulares, contaba la cantidad y luego entregaba el total a la oficina correspondiente, donde lo usaban para estimar la población total.
  Un año tuvo que viajar al extranjero durante la época del relevamiento, así que le explicó en detalle el método a un amigo y le pidió que lo reemplazara; pero ese amigo se olvidó el día en cuestión y, como también era una molestia, presentó un número más o menos plausible.
  Al año siguiente, la portada del diario local salió con el título aumento récord de la población de lagópodos alpinos, porque ese amigo no había pensado que esa estimación se usaba para definir la cantidad de permisos de caza.
  https://en.wikipedia.org/wiki/Rock_ptarmigan

  • No hay que confiar en las estadísticas.
    Hace años hice sistemas de reservas para resorts de esquí bastante grandes, y mientras trabajábamos toda la noche porque el cronograma venía atrasado, una de las últimas cosas que había que terminar era un reporte estadístico oficial, como la cantidad de huéspedes alojados, que publicaba el gobierno.
    Solo diré que las estadísticas de ese año tenían muy poca relación con la realidad.

• Soy el autor de este artículo. Si tienen preguntas, puedo responderlas, y también agradezco cualquier feedback.
  El código de todos los artículos está en https://github.com/samwho/visualisations y tiene licencia MIT, así que pueden usarlo libremente.

  • Muy buen artículo.
    Una extensión más interesante del muestreo de reservorio es que, en vez de generar un número aleatorio para cada elemento para decidir si reemplazar y a quién, se puede tomar un valor de una distribución geométrica para determinar cuántos elementos se pueden saltar de forma segura antes del próximo reemplazo.
    Es especialmente útil cuando se pueden saltar muchos elementos a bajo costo, como cuando se puede adelantar rápido una unidad de cinta pero no se conoce la longitud total, o cuando se puede dejar la mayor parte del sistema en modo de bajo consumo mientras se salta.
    Al elegir k elementos de n, este método realiza aproximadamente O(k * log (n/k)) operaciones de muestreo y salto.
    Conceptualmente, prefiero una versión del muestreo de reservorio en la que a cada carta, al llegar, se le asigna una prioridad aleatoria fija y se conservan solo las k con mayor prioridad.
    El problema que se desprende de eso es elegir los k mayores en un stream de longitud desconocida en O(n) tiempo y O(k) espacio. Si se mantiene simplemente un min-heap, se logra O(k) espacio, pero toma O(n log k) tiempo.
    En cambio, se puede usar un búfer sin ordenar con capacidad máxima de 2k, ir agregando elementos y, cuando se llena, quedarse solo con los k mayores en O(k) usando quickselect aleatorio o median-of-medians. Como por cada k elementos se hace O(2k) trabajo sobre el total de n, el tiempo de ejecución resulta O(n).
    Un tema relacionado es rendezvous hashing: https://en.wikipedia.org/wiki/Rendezvous_hashing
    Como derivación, también hay un buen artículo sobre el método alias para muestrear distribuciones de probabilidad discretas: https://www.keithschwarz.com/darts-dice-coins/
  • ¿Este método se puede componer consigo mismo? Por ejemplo, si hago muestreo de reservorio en mi servicio y el servicio de recolección de logs también hace muestreo de reservorio, me pregunto si el resultado sería el mismo que si solo lo hiciera el servicio de recolección de logs.
  • Las animaciones y las explicaciones estuvieron realmente buenas, y en especial me gustó la parte donde, en la vista de gráfico, se puede arrastrar hacia adelante o hacer clic en shuffle 100 times.
    Dicho eso, al principio se hablaba de elegir 3 cartas al azar de un mazo de 10 o de 436,234 cartas, y de repente se pasó a hablar de elegir solo 1 carta, así que me confundí un momento.
    Creo que quedaría más claro si antes de “Now let me throw you a curveball...” hubiera un título de sección del estilo: “A partir de ahora pasamos a una suposición simplificada: tendremos solo 1 carta, no 3, y además no conoceremos el tamaño del mazo”.
  • El diseño del sitio es muy bueno. Me gustaron todos los elementos interactivos, el personaje del perro en el rol de “público”, las fuentes, los colores, el layout, y el texto también es bueno.
  • Los gráficos estuvieron realmente buenos.
    Pero no sé si entendí bien la validez estadística de este enfoque. Entiendo que todos los logs de un período determinado tienen la misma probabilidad de ser incluidos, pero entonces, ¿no quedan sobrerrepresentados en las métricas globales los logs generados en “horas lentas”?
    Por ejemplo, si quiero saber qué endpoint consume más tiempo para reducir el costo total de toda la flota (CPU-segundos, etc.), parece que este método no sería adecuado, porque un endpoint con tráfico en ráfagas podría quedar subrepresentado frente a uno con tráfico constante.
    Entonces podríamos terminar perdiendo tiempo optimizando un endpoint que en realidad no tiene mucho tráfico.
    También me pregunto si, en la planificación de capacidad por servicio, es correcto que los servicios con tráfico en ráfagas queden subrepresentados.
    Me gustaría saber para qué casos de uso es adecuado el muestreo de reservorio y qué análisis estadísticos se pueden hacer con los datos devueltos.

• El artículo y la explicación son excelentes.
  Desde un punto de vista práctico, aun así creo que usaría este método para recolección de logs solo como último recurso. Entiendo que, si hay un pico repentino, algo hay que descartar, pero la clave es qué se debe descartar.
  No parece tener mucho sentido decidir “de forma justa” qué descartar.
  Es mejor descartar primero los logs de baja prioridad y, si hay niveles como debug/info/warning/error, priorizar los eventos de mayor gravedad y descartar antes los logs debug más verbosos.
  También es posible agrupar secuencias de logs como parte de una actividad: para actividades exitosas, registrar solo el inicio y el fin, o los cambios de estado clave, y omitir los logs intermedios repetitivos.
  Durante un pico, en vez de almacenar cada línea de log, agrupar y resumir mensajes similares o duplicados reduce el volumen y además deja ver mejor las tendencias.

  • Últimamente he estado profundizando en observabilidad, y el enfoque descrito probablemente se acerca a una combinación de head sampling y tail sampling: https://docs.honeycomb.io/manage-data-volume/sample/
  • El artículo trata esta parte. En la práctica, no es que uno quiera descartar todos los logs de baja prioridad, sino limitarlos dentro de un presupuesto.
    Y también se quiere limitar el número total de líneas de log recolectadas con un presupuesto mayor. El muestreo de reservorio puede manejar todo esto.
  • Si es posible, lo correcto es descartar o combinar algunos elementos, pero aun después de hacerlo puede que sigan quedando demasiados elementos importantes y haya que reducirlos al azar. Porque cualquier cosa es mejor que bloquear el sistema.
    El muestreo de reservorio justo también puede volverse injusto de manera controlada. Por ejemplo, se puede aumentar la probabilidad de conservar elementos cuyo contenido sea especialmente interesante.
    Como último recurso, es una técnica que compite con selecciones aleatorias sesgadas menos principistas, o incluso con algoritmos de selección que ni siquiera son aleatorios.

• Es un artículo muy bien escrito y muy bien visualizado.
  Como extensión avanzada, hay algoritmos que, en lugar de hacer un ensayo por cada registro, calculan la cantidad de registros que se deben saltar. Hay un buen artículo sobre eso aquí: https://richardstartin.github.io/posts/reservoir-sampling

• Una variante de muestreo de reservorio ponderado se usa en ReSTIR (resampling de reservorio espacio-temporal para ray tracing en tiempo real). Es un estimador de transporte de luz probabilístico con eliminación de ruido espacio-temporal incorporada.
  Un estimador de transporte de luz intenta calcular la cantidad de luz que atraviesa una escena (https://en.wikipedia.org/wiki/Radiance). Para eso debe integrar la radiancia de todos los caminos posibles que la luz puede tomar, manteniendo la conservación de la energía (https://en.wikipedia.org/wiki/Rendering_equation).
  Salvo en casos muy simples, esta integral de la ecuación de renderizado no tiene una solución cerrada manejable, así que debe resolverse de forma probabilística.
  La idea básica es el método de Monte Carlo (https://en.wikipedia.org/wiki/Monte_Carlo_method): muestrear al azar muchos caminos posibles y promediarlos.
  Durante las décadas siguientes se desarrollaron estrategias más sofisticadas, como importance sampling (IS), multiple importance sampling (MIS), sample importance resampling (SIR), resampled importance sampling (RIS), weighted reservoir sampling (WRS), y ReSTIR, que combina RIS y WRS.
  Hay un artículo detallado aquí: https://agraphicsguynotes.com/posts/understanding_the_math_b...

• Esto me hace pensar que debería analizar más el algoritmo con el que los Aliados estimaron la cantidad de tanques alemanes usando números de serie.
  Las estimaciones de campo eran aproximadamente 5 veces la producción real, pero la técnica basada en números de serie tuvo más de 90% de precisión.

  • https://en.wikipedia.org/wiki/German_tank_problem

• Buen artículo y excelente explicación. Esto parece cubrir el Algorithm R, que probablemente Vitter fue el primero en describir: https://www.cs.umd.edu/~samir/498/vitter.pdf

  • Ese paper dice que “Algorithm R is Alan Waterman’s reservoir algorithm”, pero no incluye una cita.
    El paper anterior de Vitter https://dl.acm.org/doi/10.1145/358105.893 cita el volumen 2 de TAOCP de Knuth, y Knuth tampoco incluye otra cita.

• Desde la perspectiva de ciencia de datos, la cantidad de datos en sí también contiene información muy importante, así que conviene registrar cuántos elementos representa cada punto de datos.
  Por ejemplo, si la tasa de muestreo es de 10%, se puede incluir un campo con el valor 10, y así reconstruir y estimar la mayoría de las estadísticas, como count, sum y average.

• La estructura es buena y la explicación está bien hecha. Si te interesa la versión ponderada, alguna vez expliqué un poco sobre eso aquí: https://gregable.com/2007/10/reservoir-sampling.html
  También hay una versión distribuida que se puede implementar fácilmente con MapReduce.
  Como algoritmo muy simple, también es posible generar un par aleatorio para cada elemento del stream y conservar los N más altos según ese valor aleatorio.

  • Sobre la versión ponderada, hay dos puntos.
    Primero, la implementación intuitiva de asignar un ranking con POW(RANDOM(), 1.0 / weight) y luego elegir los N primeros tiene problemas de estabilidad numérica cuando los pesos son muy grandes o muy pequeños.
    Segundo, la muestra resultante no tiene la misma distribución que la población original ni siquiera en términos de valor esperado. Esto ocurre especialmente cuando el peso total está concentrado en unos pocos elementos de la población, aunque en muchos casos es una aproximación usable.
    Traté estos problemas con más detalle aquí: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....

• Excelente artículo, accesible y con visualizaciones muy buenas.
  En $WORK usamos una variante parecida para resolver un problema relacionado: estimar cierto percentil en un stream en ejecución.
  El percentil que queremos elegir cambia de vez en cuando, pero por lo general se mantiene fijo durante más de un billón de iteraciones, y los datos subyacentes son cuasi estacionarios.
  Si se apoya este proceso en un árbol splay, se puede estimar el percentil en O(1) amortizado. Con el mismo uso de RAM, tiene un margen de error mayor que varias otras técnicas, pero es muy rápido.
  También se puede ajustar la probabilidad de reemplazo para darle a los datos una “vida media” basada en tiempo o en cantidad, y sesgar la estimación hacia eventos más recientes; para algunos problemas, eso resulta más adecuado.