- L’échantillonnage en réservoir est une technique originale et efficace pour extraire un échantillon aléatoire de manière équitable lorsque la taille des données est inconnue
- Il est utilisé dans divers domaines, notamment la collecte de logs en temps réel, car il permet de résoudre efficacement des situations que les méthodes traditionnelles ne prennent pas en charge
- L’idée clé consiste à mettre à jour l’espace de stockage avec une probabilité de 1/n à chaque apparition d’un nouvel élément, afin d’offrir à tous les éléments la même chance d’être sélectionnés
- Lorsqu’on souhaite choisir plusieurs échantillons, la probabilité est étendue à k/n, puis un échantillon existant est remplacé aléatoirement selon cette probabilité
- Cet algorithme garantit un échantillonnage équitable avec très peu de mémoire, tout en améliorant l’efficacité et la fiabilité du traitement en temps réel
Concept et nécessité de l’échantillonnage en réservoir
- L’échantillonnage en réservoir est une technique efficace permettant d’extraire des échantillons de façon équitable dans un ensemble de données dont la taille totale est inconnue
- En règle générale, lorsqu’on connaît la taille des données, il est efficace de tirer un indice aléatoire, mais cette méthode devient impossible lorsque la taille est inconnue
- Avec de grands volumes de données arrivant de façon linéaire (par exemple un flux de logs), il faut limiter l’utilisation de la mémoire tout en garantissant que chaque donnée ait la même probabilité d’être choisie
Échantillonnage lorsque la taille est connue
- Dans un ensemble de taille limitée (par exemple 10 cartes), la méthode du shuffle, qui consiste à mélanger tous les éléments puis à choisir autant d’éléments que souhaité en tête de liste, est adaptée pour garantir l’équité
- En exploitant la structure de tableau d’un ordinateur, on peut aussi sélectionner directement des indices aléatoires afin d’extraire rapidement des échantillons
- Cependant, dans la pratique, cette approche est inefficace pour des millions de données ou pour un flux dont la taille est inconnue
Échantillonnage lorsque la taille est inconnue : problèmes et nécessité
- Il arrive fréquemment dans le monde réel qu’on reçoive les données une par une, qu’on ne puisse en stocker qu’une seule à la fois et qu’il soit impossible de revenir sur les données déjà passées
- Dans les systèmes de collecte de logs, une brusque hausse du trafic peut survenir, et il faut alors n’envoyer qu’une partie des données afin d’éviter une surcharge du serveur
- Choisir arbitrairement seulement les premiers éléments ne donne pas à tous les éléments la même chance, ce qui entraîne un problème de manque d’équité
Principe de l’algorithme d’échantillonnage en réservoir
- À chaque arrivée d’une donnée, on calcule n, le nombre d’éléments reçus jusque-là, puis on fait en sorte que la nouvelle donnée soit sélectionnée avec une probabilité de 1/n
- La première donnée est toujours sélectionnée, puis chaque nouvelle donnée remplace l’ancienne avec une probabilité de plus en plus faible, ce qui permet de conserver une probabilité de sélection identique
- À la fin, la donnée conservée a une probabilité uniforme d’être n’importe laquelle parmi l’ensemble
- Ce mécanisme n’utilise pas un simple lancer de pièce, mais une probabilité de 1/n, ce qui garantit à toutes les données une chance équitable
Intuition mathématique (explication avec l’exemple des cartes)
- 1re donnée : elle est sélectionnée à coup sûr (probabilité 1/1)
- 2e donnée : elle est sélectionnée avec une probabilité de 1/2, et la donnée existante n’a plus que 50 % de chances de rester
- 3e donnée : la nouvelle donnée est sélectionnée avec une probabilité de 1/3, et la probabilité de survie des données existantes s’accumule selon la valeur complémentaire de cette probabilité
- En généralisant, jusqu’à la n-ième donnée, toutes les données conservent toujours une probabilité de 1/n
Extension à la sélection de plusieurs échantillons (k-out-of-n)
- Pour tirer k échantillons, la nouvelle donnée est sélectionnée avec une probabilité de k/n et, si elle est retenue, elle remplace aléatoirement l’un des éléments actuellement stockés
- Cette méthode garantit elle aussi que tous les éléments stockés ont la même probabilité de rester dans l’échantillon
- En utilisant une mémoire constante (de taille k seulement), il devient possible d’extraire équitablement plusieurs échantillons même dans de très grands flux de données
Utilisation de l’échantillonnage en réservoir dans un service de collecte de logs
- Parmi les logs reçus chaque seconde, on ne conserve qu’un maximum de k éléments (par exemple 5) à l’aide de l’échantillonnage en réservoir, puis seuls ces échantillons sont envoyés au serveur
- Lorsque le volume de données est faible, tous les logs sont transmis sans perte ; même en cas d’explosion du trafic, on n’envoie jamais plus de k éléments, ce qui permet de garantir la stabilité du service
- En envoyant les échantillons à intervalles réguliers, on introduit un léger délai sur le temps réel, mais on améliore globalement la stabilité et l’efficacité en termes de coûts
Applications supplémentaires et ressources de référence
- Si certaines données (par exemple des logs d’erreur) sont plus importantes, on peut utiliser une variante d’échantillonnage en réservoir pondéré (Weighted Reservoir Sampling)
- Des notions plus avancées figurent dans des ressources externes comme Wikipédia, mais le principe de base reste le maintien de l’équité
Conclusion
- L’échantillonnage en réservoir est un algorithme très élégant et pratique qui permet d’échantillonner de manière équitable et avec une bonne efficacité mémoire dans des flux de données dont la taille est inconnue
- Dans le traitement des données en temps réel, il présente des avantages en matière de rapidité, de cohérence et de faible consommation de ressources, ce qui lui donne une forte valeur d’usage dans de nombreux domaines
1 commentaires
Commentaire Hacker News
Quand j’étais enfant et que je vivais à la campagne, un ami de mon père devait chaque année, dans le cadre de son travail, mesurer la population de ptarmigans dans la montagne
La méthode consistait à suivre un itinéraire défini et, à intervalles réguliers, à effrayer les oiseaux pour les faire s’envoler puis les compter
Il remettait ensuite ces chiffres au bureau responsable, qui estimait alors la population totale
Une année, cet ami était à l’étranger, donc il a expliqué la méthode en détail à un autre ami pour qu’il le remplace
Mais le jour du relevé, cet ami a tout simplement oublié, et comme c’était fastidieux, il a envoyé des chiffres approximatifs qui avaient l’air plausibles
L’année suivante, la une du journal local titrait : « hausse record de la population de ptarmigans »
Si cette variation brutale a fait la une, c’est parce que ces chiffres servaient à fixer les permis de chasse. Son ami n’y avait pas pensé
J’ai déjà travaillé sur le système de réservation d’une grande station de ski, et je devais finaliser un rapport statistique officiel à transmettre à l’administration (sur les nuitées, etc.)
Faute de temps, j’ai travaillé toute la nuit, et les statistiques de cette année-là étaient très éloignées des valeurs réelles
Bonjour ! o/
Je suis l’auteur de l’article. Questions et retours bienvenus
Le code de tous mes billets est disponible sous licence MIT sur https://github.com/samwho/visualisations. Servez-vous librement
Je trouve que c’est un excellent billet
Dans une autre direction d’optimisation du reservoir sampling, au lieu de tirer un nombre aléatoire pour vérifier chaque élément et décider s’il faut le remplacer, on peut tirer des sauts selon une loi géométrique
C’est intéressant dans des cas comme les lecteurs de bande, où on peut sauter beaucoup d’éléments à faible coût (on ne connaît pas la longueur totale de la bande, mais on peut laisser la majeure partie du système en veille pendant les sauts)
Pour tirer un échantillon de taille k parmi n éléments, il suffit d’environ O(k * log(n/k)) tirages et sauts
Une autre idée que j’aime bien consiste à attribuer une priorité aléatoire à chaque carte à son arrivée, puis à conserver les k meilleures
Il y a ici un problème connexe : comment sélectionner les k meilleurs éléments d’un flux de longueur inconnue en O(n) temps et O(k) mémoire
Il suffit de tout mettre dans un tampon non trié de taille 2*k et, lorsqu’il est plein, d’utiliser quickselect randomisé ou median-of-medians pour ne garder que les k meilleurs
Répété n fois, cela donne un temps total en O(n)
Dans le même registre, le rendezvous hashing est aussi intéressant
Et pour l’alias method, cet article peut aider : https://www.keithschwarz.com/darts-dice-coins/
Je me demande si cette méthode peut être imbriquée
Par exemple, si je fais du reservoir sampling dans mon service, et que le service collecteur de logs en fait lui aussi, est-ce que cela revient au même que de ne faire l’échantillonnage qu’une seule fois côté collecteur ?
J’ai particulièrement aimé les animations et les explications
Notamment les différentes interactions comme mélanger 100 fois dans le graphique, que j’ai trouvées très marquantes
Au début, on parle de tirer 3 cartes parmi 10 ou 436 234, puis on bascule soudain à l’exemple où l’on ne regarde qu’une seule carte à la fois pour n’en tirer qu’une ; j’ai trouvé ça un peu déroutant
Une séparation de section au niveau du passage « Maintenant, ajoutons une courbe ! » rendrait peut-être l’ensemble plus clair.
À partir de là, on suppose qu’on n’a qu’une seule carte en main et qu’on ne connaît même pas la taille du paquet
J’aime particulièrement le design du site
Les interactions, le personnage du chien, la police, les couleurs, la mise en page générale : tout est réussi
L’ensemble du blog donne l’impression d’un véritable trésor
Ravi de l’avoir découvert
J’ai aimé les graphismes
En revanche, je ne suis pas certain que cette méthode soit totalement valide du point de vue statistique. Tous les logs d’une période donnée ont bien la même probabilité d’être sélectionnés, mais je me demande si les logs produits pendant des « périodes lentes » ne deviennent pas surreprésentés dans les statistiques globales
Par exemple, si l’on veut déterminer quel endpoint consomme le plus de CPU sur l’ensemble du système afin de l’optimiser, est-ce que les logs d’un endpoint dont le trafic explose temporairement ne risquent pas d’être sous-représentés, au point de mal évaluer les endpoints réellement les plus utilisés ?
Ou encore pour le capacity planning par service, j’ai l’impression que les services à trafic en rafales seraient sous-représentés
Dans quels cas le reservoir sampling est-il réellement adapté, et quels types d’analyses statistiques peut-on faire correctement avec cette méthode ?
Très bon article ; si les maths et les stats étaient enseignées comme ça, ce serait bien plus agréable à apprendre
Ça m’a fait penser à https://distill.pub/
La formule « Sometimes the hand of fate must be forced » m’a marqué
J’ai particulièrement aimé l’interactivité
Je trouve le design du site et la pédagogie vraiment magnifiques. Merci
Je me demande s’il existe un flux RSS pour le blog
Billet très clair et très bien illustré
Pour aller vers des extensions plus avancées, il existe aussi des algorithmes qui calculent combien d’éléments sauter d’un coup au lieu d’appliquer la méthode de base
Pour les détails, voir : https://richardstartin.github.io/posts/reservoir-sampling
Bon article et bonne explication
Pour la collecte réelle de logs, je recommanderais d’essayer d’abord diverses méthodes, puis de n’utiliser l’équité (fairness) qu’en dernier recours
Par exemple, on peut introduire des priorités entre les logs et commencer par supprimer les logs de faible priorité (forte verbosité)
Pour les logs qui décrivent une même activité, on peut réduire les répétitions intermédiaires et ne conserver que le début, la fin et les changements d’état importants
On peut aussi agréger les logs similaires ou dupliqués et ne stocker qu’un résumé, ce qui réduit le volume total tout en facilitant l’identification des tendances
Je me renseigne beaucoup en ce moment sur l’observability, et les méthodes mentionnées correspondent à une approche hybride de head/tail sampling.
On peut voir des explications ici : https://docs.honeycomb.io/manage-data-volume/sample/
L’article en parle aussi
En pratique, il est important d’appliquer une notion de « budget » plutôt que de simplement jeter tous les logs de faible priorité
On peut aussi plafonner le nombre total de logs avec un budget global distinct
Le reservoir sampling gère aussi très bien ce type de contrainte
Bon article et bonnes explications
L’article de Vitter décrit l’« Algorithm R », qui correspond à une forme de reservoir sampling.
Référence : https://www.cs.umd.edu/~samir/498/vitter.pdf
Un article antérieur de Vitter, https://dl.acm.org/doi/10.1145/358105.893, cite le volume 2 de TAOCP de Knuth, mais Knuth lui-même ne donne pas de source claire
C’est très bien présenté, et pour le weighted reservoir sampling on peut consulter https://gregable.com/2007/10/reservoir-sampling.html
Il existe aussi une méthode facile à appliquer en environnement distribué avec map-reduce, ainsi qu’une approche très simple qui consiste à associer une valeur aléatoire à chaque élément puis à conserver le Top N
La méthode de base qui consiste à attribuer à chaque élément une priorité avec POW(RANDOM(), 1.0 / weight) puis à prendre le Top N perd en stabilité numérique quand les poids sont très grands ou très petits
De plus, l’échantillon obtenu ne reflète pas toujours suffisamment bien la distribution de la population d’origine, surtout quand le poids total est concentré sur un petit nombre d’éléments
Cela reste malgré tout une approximation tout à fait acceptable dans la plupart des cas
Pour plus de détails : https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html
Cet article m’a rappelé la méthode utilisée par les Alliés pendant la Seconde Guerre mondiale pour estimer la production de chars allemands à partir des numéros de série
Les équipes sur le terrain estimaient alors la production réelle à un niveau environ cinq fois supérieur, tandis que la méthode fondée sur les numéros de série dépassait 90 % de précision
Excellent billet, et les visualisations sont vraiment remarquables
En production, nous utilisons une variante similaire pour estimer en temps réel des valeurs de percentile sur de très grands flux
Les valeurs de percentile changent parfois, mais restent généralement stables pendant de très nombreuses répétitions. Les données sous-jacentes sont quasi stationnaires
Avec une sauvegarde par splay tree, on peut faire l’estimation en temps amorti O(1), avec une plage d’erreur plus large que d’autres méthodes à consommation RAM égale
On peut aussi ajuster la probabilité de remplacement pour raccourcir la « demi-vie » des données, c’est-à-dire biaiser l’estimation vers les données plus récentes
Du point de vue de la data science, le volume de données lui-même contient une information importante, donc il faut absolument enregistrer aussi le taux d’échantillonnage
Par exemple, si le taux est de 10 %, on peut enregistrer 10 avec chaque échantillon afin de reconstituer et d’estimer correctement les décomptes, les sommes, les moyennes, etc.
Ce billet illustre bien les compromis inhérents à la collecte de telemetry (traces, logs, metrics)
C’est un domaine d’analyse de données difficile d’accès, que beaucoup de développeurs sous-estiment
Des données qui semblent identiques peuvent produire des graphiques complètement différents selon la manière dont elles ont été échantillonnées, et beaucoup de gens passent à côté de ce point