- Reservoir Sampling ist eine Stichprobentechnik, die selbst in Datenströmen mit unbekannter Gesamtgröße nur eine feste Anzahl von Elementen im Speicher hält und allen Elementen die gleiche Auswahlchance gibt
- Für Arrays mit bekannter Größe reichen Mischen oder zufällige Indexauswahl aus, aber bei Streams, in denen man nicht zu bereits vorbeigelaufenen Elementen zurückkehren kann, ist ein anderer Ansatz nötig
- Bei der Auswahl eines einzelnen Elements wird das n-te Element mit Wahrscheinlichkeit 1/n übernommen, sodass die Auswahlchance neuer Elemente und die Überlebenschance bestehender Elemente ausgewogen bleiben
- Wenn mehrere Elemente gezogen werden, wird ein neues Element mit Wahrscheinlichkeit k/n übernommen; falls nötig, wird eines der aktuell gespeicherten Elemente zufällig ersetzt
- Auf Log-Erfassung angewendet kann man so eine Verarbeitungsobergrenze wie maximal 5 Elemente pro Sekunde einhalten und gleichzeitig Log-Verluste in ruhigen Phasen sowie den Speicherverbrauch reduzieren
Sampling aus Mengen mit bekannter Größe
- Wenn man aus 10 Karten zufällig 3 zieht, kann man einfach das gesamte Deck mischen und die ersten 3 Karten nehmen, wodurch jede Karte die gleiche Auswahlwahrscheinlichkeit erhält
- Wächst das Deck auf 1 Million Karten, ist direktes Mischen schwierig, aber in einer Struktur mit Indexzugriff wie einem Array erreicht man dasselbe Ziel, indem man 3 zufällige Indizes auswählt
- Auf ein Array im Speicher kann man leicht über einen bestimmten Index zugreifen, aber in einem Kartenstapel die 436.234. Karte abzuzählen, wäre in der Praxis sehr aufwendig
Einschränkungen bei Streams unbekannter Größe
- Wenn man jeweils nur 1 Karte sehen, gleichzeitig nur 1 Karte halten und nicht zu bereits gesehenen Karten zurückkehren kann, muss man am Ende 1 Karte auswählen, ohne die Gesamtzahl zu kennen
- Auch ein Log-Erfassungsdienst steht vor einem ähnlichen Problem
- Er empfängt Log-Nachrichten von anderen Diensten und speichert sie an einem Ort
- Bei einem fehlerhaften Release oder einem plötzlichen Traffic-Anstieg kann der Erfassungsdienst überlastet werden
- Im Beispiel hat der Log-Erfassungsdienst einen Schwellenwert von 5 Logs pro Sekunde, die verarbeitet werden können
- Wenn man einfach 10 % der Logs sendet, verhindert das zwar in Spitzenphasen das Überschreiten des Schwellenwerts, verwirft aber auch in ruhigen Phasen unnötig 90 % der Logs
- Gewünscht ist ein Verhalten, bei dem in ruhigen Phasen alle Logs gesendet werden und in Spitzenphasen höchstens 5 pro Sekunde
- Wenn man einfach nur die ersten 5 Logs pro Sekunde sendet, verlieren später eintreffende Logs ihre Auswahlchance, was unfair ist
Reservoir Sampling für ein einzelnes Element
- Reservoir Sampling hält selbst dann eine faire Stichprobe aus den bisher gesehenen Elementen aufrecht, wenn die Gesamtzahl unbekannt ist
- Man könnte auch alle Nachrichten im Speicher ablegen und später auswählen, aber wenn das Ausmaß von Spitzen unbekannt ist, lässt sich der benötigte Speicher schwer vorhersagen
- Dieser Ansatz löst dasselbe Problem, ohne mehr Speicher zu verbrauchen als die angeforderte Stichprobengröße
- Die Regel für die Auswahl einer einzelnen Karte ist einfach
- Die erste Karte wird immer behalten
- Die n-te neue Karte wird mit Wahrscheinlichkeit 1/n behalten
- Wenn man sich entscheidet, die neue Karte zu behalten, wird die bisher gespeicherte Karte verworfen
- Würde man bei jeder Karte mit 50 % Wahrscheinlichkeit ersetzen, wären spätere Karten im Vorteil und die Auswahl wäre nicht fair
- Damit die erste Karte auch nach der 10. Karte noch erhalten bleibt, müsste sie mehrere Ersetzungsgelegenheiten überstehen
- Die letzte Karte kann in der Hand bleiben, wenn sie nur einmal ausgewählt wird
- Die 1/n-Regel gleicht nicht nur die Auswahlwahrscheinlichkeit neuer Karten aus, sondern auch die Überlebenswahrscheinlichkeit bestehender Karten
- Die erste Karte wird mit 1/1, also 100 %, gespeichert
- Bei der zweiten Karte wird die neue Karte mit Wahrscheinlichkeit 1/2 ausgewählt, und die erste Karte bleibt ebenfalls mit Wahrscheinlichkeit 1/2 erhalten
- Bei der dritten Karte wird die neue Karte mit Wahrscheinlichkeit 1/3 ausgewählt, und die zuvor gespeicherte Karte kommt ebenfalls auf 1/3 Wahrscheinlichkeit, nämlich 50 % × 2/3
- Allgemein ist in Schritt n die Wahrscheinlichkeit, dass eine bestehende Karte erhalten bleibt,
1/(n-1) * (1-(1/n)), und die Wahrscheinlichkeit, dass die neue Karte ausgewählt wird, ist ebenso1/n
Erweiterung auf mehrere Elemente
- Die Auswahl eines einzelnen Elements lässt sich auf mehrere Elemente erweitern
- Wenn man k Elemente auswählen möchte, ändern sich zwei Regeln
- Ein neues Element wird nicht mit
1/n, sondern mit Wahrscheinlichkeit k/n ausgewählt - Wenn ein Austausch nötig ist, wird eines der aktuell gespeicherten k Elemente zufällig ausgewählt und durch das neue Element ersetzt
- Ein neues Element wird nicht mit
- Die Auswahlwahrscheinlichkeit eines bestehenden Elements lässt sich als
k/(n-1)ausdrücken; multipliziert mit der Wahrscheinlichkeit, nicht durch das neue Element ersetzt zu werden, bleibt die Fairness erhalten - Da alle gespeicherten Elemente mit derselben Wahrscheinlichkeit als Ersatzkandidaten infrage kommen, bleibt auch in jedem Schritt die Chance jedes Elements gleich, weiterhin erhalten zu bleiben
- Die Implementierung lässt sich als Array der Größe k formulieren
- Für jedes neue Element wird eine Zufallszahl von 0 bis n erzeugt
- Ist die Zufallszahl kleiner als k, wird das Element an diesem Index durch das neue Element ersetzt
- Andernfalls wird das neue Element verworfen
Anwendung auf einen Log-Erfassungsdienst
- Im Log-Beispiel wird
k=5gesetzt, sodass zu einem Zeitpunkt höchstens 5 Log-Nachrichten gespeichert werden - Die pro Sekunde ausgewählten Logs werden an den Log-Erfassungsdienst gesendet; danach wird das Array der Größe 5 geleert und der Vorgang beginnt erneut
- Dieser Ansatz erzeugt statt eines kontinuierlichen Echtzeit-Log-Streams ein gebündeltes Muster, bei dem Logs in festen Intervallen gesendet werden
- Dafür überschreitet die Zahl der gesendeten Logs den Schwellenwert nicht, und in ruhigen Phasen bewegen sich Gesamtzahl und gesendete Zahl der Logs nahezu gemeinsam
- In ruhigen Phasen gehen keine Logs verloren, in Spitzenphasen werden nicht mehr Logs pro Sekunde gesendet als der Schwellenwert erlaubt, und auch der Speicherbedarf übersteigt nie
k=5Logs
Wenn Gewichtung nötig ist
- Manche Logs können wertvoller sein als andere
- Zum Beispiel möchte man Fehler-Logs möglicherweise vollständig behalten
- In solchen Fällen kann man eine Variante des gewichteten Reservoir Sampling verwenden
- Reservoir Sampling ist ein Algorithmus, der das zunächst unmöglich wirkende Problem des Stream-Samplings mit wenig Speicher lösbar macht
1 Kommentare
Meinungen auf Hacker News
Als ich klein war, lebte ich auf dem Land, und ich hörte, dass ein Freund meines Vaters beruflich jedes Jahr in den Bergen die Population der Alpenschneehühner zählen musste.
Er ging eine festgelegte Route ab, scheuchte in bestimmten Abständen Vögel auf, sodass sie aufflogen, zählte sie und reichte die Summe bei der Behörde ein; sie wurde dann zur Schätzung der Gesamtpopulation verwendet.
In einem Jahr musste er während des Erhebungszeitraums ins Ausland, erklärte einem Freund die Methode genau und bat ihn, es für ihn zu übernehmen. Der Freund vergaß es am betreffenden Tag, fand es außerdem lästig und reichte einfach eine grob plausibel klingende Zahl ein.
Im nächsten Jahr titelte die lokale Zeitung auf der Titelseite Rekordzuwachs bei der Alpenschneehuhn-Population; der Freund hatte nicht bedacht, dass diese Schätzung zur Festlegung der Jagdquoten verwendet wurde.
https://en.wikipedia.org/wiki/Rock_ptarmigan
Früher habe ich die Buchungssysteme für ziemlich große Skigebiete gebaut. Als der Zeitplan ins Rutschen geraten war und wir Nachtschichten machten, gehörte zu den letzten Dingen, die noch fertig werden mussten, ein offizieller Statistikbericht für die Regierung, etwa über die Zahl der Übernachtungsgäste.
Sagen wir einfach: Die Statistik dieses Jahres hatte mit der Realität kaum etwas zu tun.
Ich bin der Autor dieses Beitrags. Wenn ihr Fragen habt, kann ich sie beantworten, und Feedback ist ebenfalls willkommen.
Der Code für alle Beiträge liegt unter https://github.com/samwho/visualisations und steht unter der MIT-Lizenz, kann also frei verwendet werden.
Eine interessantere Erweiterung des Reservoir Sampling besteht darin, statt für jedes Element eine Zufallszahl zu ziehen, um zu entscheiden, ob und was ersetzt wird, einen Wert aus der geometrischen Verteilung zu ziehen und damit festzulegen, wie viele Elemente bis zur nächsten Ersetzung sicher übersprungen werden können.
Das ist besonders nützlich, wenn man viele Elemente billig überspringen kann, etwa wenn man ein Bandlaufwerk vorspulen kann, aber die Gesamtlänge nicht kennt, oder wenn man den Großteil des Systems während des Überspringens in einen Stromsparzustand versetzen kann.
Wenn man k aus n Elementen auswählt, führt diese Methode ungefähr O(k * log (n/k)) Sampling- und Skip-Schritte aus.
Konzeptionell bevorzuge ich eine Version des Reservoir Sampling, bei der jeder Karte beim Eintreffen eine feste zufällige Priorität zugewiesen wird und nur die k Karten mit der höchsten Priorität behalten werden.
Das daraus folgende Problem ist, aus einem Stream unbekannter Länge die Top-k in O(n) Zeit und O(k) Speicher auszuwählen. Naiv kann man einen Min-Heap halten; das braucht zwar O(k) Speicher, aber O(n log k) Zeit.
Stattdessen kann man einen ungeordneten Puffer mit Kapazität bis zu 2k verwenden, Elemente hinzufügen und, sobald er voll ist, per zufälligem quickselect oder median-of-medians in O(k) nur die Top-k behalten. Da für alle n Elemente jeweils alle k Elemente O(2k) Arbeit anfällt, ergibt sich eine Laufzeit von O(n).
Ein verwandtes Thema ist Rendezvous Hashing: https://en.wikipedia.org/wiki/Rendezvous_hashing
Am Rande gibt es auch einen guten Artikel zur Alias-Methode für Sampling aus diskreten Wahrscheinlichkeitsverteilungen: https://www.keithschwarz.com/darts-dice-coins/
Allerdings ging es anfangs darum, 3 Karten zufällig aus einem Deck mit 10 oder 436.234 Karten auszuwählen, und dann wechselte es plötzlich zu einer Geschichte, in der nur noch 1 Karte ausgewählt wird, was mich kurz verwirrt hat.
Eine Abschnittsüberschrift vor „Now let me throw you a curveball...“ im Sinne von „Ab jetzt wechseln wir zu der vereinfachten Annahme, dass wir nicht 3 Karten, sondern nur 1 Karte halten und die Deckgröße ebenfalls nicht kennen“ würde es wohl klarer machen.
Allerdings bin ich mir nicht sicher, ob ich die statistische Validität dieses Ansatzes richtig verstanden habe. Ich verstehe, dass alle Logs eines bestimmten Zeitraums die gleiche Wahrscheinlichkeit haben, aufgenommen zu werden; aber werden dann Logs, die in „langsamen Zeiten“ entstehen, in den Gesamtmetriken nicht überrepräsentiert?
Wenn ich zum Beispiel wissen möchte, welcher Endpoint die meiste Zeit verbraucht, um die Gesamtkosten der gesamten Flotte (CPU-Sekunden usw.) zu senken, könnten Endpoints mit burst-artigem Traffic gegenüber Endpoints mit kontinuierlichem Traffic unterrepräsentiert sein; dafür scheint diese Methode ungeeignet.
Dann könnte man Zeit damit verschwenden, einen Endpoint zu optimieren, der in der Praxis gar nicht viel Traffic hat.
Auch bei der Kapazitätsplanung pro Service frage ich mich, ob es richtig ist, dass Services mit burst-artigem Traffic unterrepräsentiert werden.
Ich würde gern wissen, für welche Use Cases Reservoir Sampling geeignet ist und welche statistischen Analysen man mit den zurückgegebenen Daten durchführen kann.
Der Artikel und die Erklärungen sind hervorragend.
Aus praktischer Sicht würde ich diese Methode für Log-Erfassung trotzdem wohl erst ganz zuletzt einsetzen. Ich verstehe, dass man bei einem Spike irgendetwas verwerfen muss, aber der Kern ist, was man verwerfen sollte.
Es scheint mir nicht besonders sinnvoll, „fair“ zu entscheiden, was verworfen wird.
Besser ist es, zuerst Logs mit niedriger Priorität zu verwerfen; wenn es Log-Level wie debug/info/warning/error gibt, kann man Ereignisse mit höherem Schweregrad priorisieren und ausführliche Debug-Logs zuerst wegwerfen.
Außerdem kann man Log-Sequenzen als Teil einer Aktivität zusammenfassen: Bei erfolgreichen Aktivitäten protokolliert man nur Start und Ende oder wesentliche Zustandsänderungen und lässt repetitive Zwischen-Logs weg.
Bei Spikes kann man ähnliche oder doppelte Meldungen aggregieren und zusammenfassen, statt jede Log-Zeile zu speichern; das reduziert die Menge und macht Trends besser sichtbar.
Und man möchte auch die Gesamtzahl der erfassten Log-Zeilen durch ein größeres Budget begrenzen. Reservoir Sampling kann all das abdecken.
Faires Reservoir Sampling lässt sich auch auf kontrollierte Weise unfair machen. Zum Beispiel kann man für Einträge mit besonders interessantem Inhalt die Wahrscheinlichkeit erhöhen, dass sie behalten werden.
Als letztes Mittel konkurriert diese Technik mit weniger prinzipiengeleiteten, verzerrten Zufallsauswahlen oder sogar mit Auswahlalgorithmen, die gar nicht zufällig sind.
Ein wirklich gut geschriebener und gut visualisierter Artikel.
Als fortgeschrittene Erweiterung gibt es Algorithmen, die statt eines Versuchs pro Datensatz die Anzahl der zu überspringenden Datensätze berechnen. Einen guten Artikel dazu gibt es hier: https://richardstartin.github.io/posts/reservoir-sampling
Eine Variante des gewichteten Reservoir Sampling wird in ReSTIR (Spatiotemporal Reservoir Resampling für Echtzeit-Raytracing) verwendet. Das ist ein stochastischer Lichttransport-Schätzer mit eingebauter raumzeitlicher Rauschunterdrückung.
Ein Lichttransport-Schätzer versucht zu berechnen, wie viel Licht durch eine Szene geht (https://en.wikipedia.org/wiki/Radiance). Dafür muss die Radiance aller möglichen Wege, die Licht nehmen kann, integriert werden, während die Energieerhaltung gewahrt bleibt (https://en.wikipedia.org/wiki/Rendering_equation).
Außer in sehr einfachen Fällen hat dieses Integral der Rendering-Gleichung keine handhabbare geschlossene Lösung und muss daher stochastisch gelöst werden.
Die Grundidee ist die Monte-Carlo-Methode (https://en.wikipedia.org/wiki/Monte_Carlo_method): Man sampelt zufällig viele mögliche Pfade und bildet den Durchschnitt.
In den folgenden Jahrzehnten entstanden ausgefeiltere Strategien wie Importance Sampling (IS), Multiple Importance Sampling (MIS), Sample Importance Resampling (SIR), Resampled Importance Sampling (RIS), Weighted Reservoir Sampling (WRS) sowie ReSTIR, das RIS und WRS kombiniert.
Einen ausführlichen Artikel gibt es hier: https://agraphicsguynotes.com/posts/understanding_the_math_b...
Das erinnert mich daran, dass ich noch einmal genauer über den Algorithmus nachdenken sollte, mit dem die Alliierten anhand von Seriennummern die Zahl deutscher Panzer schätzten.
Die Schätzungen im Feld lagen etwa beim Fünffachen der tatsächlichen Produktion, während die Seriennummern-Methode zu über 90 % genau war.
Ein guter Artikel mit hervorragenden Erklärungen. Er scheint Algorithm R zu behandeln, den vermutlich Vitter als Erster beschrieben hat: https://www.cs.umd.edu/~samir/498/vitter.pdf
Vitters früheres Paper https://dl.acm.org/doi/10.1145/358105.893 zitiert Knuths TAOCP Band 2, und bei Knuth wiederum gibt es keine weitere Quellenangabe.
Aus Sicht der Datenwissenschaft enthält auch die Datenmenge selbst sehr wichtige Informationen; daher sollte man auch protokollieren, wie viele Einträge jeder Datenpunkt repräsentiert.
Wenn die Sampling-Rate zum Beispiel 10 % beträgt, kann man ein Feld mit dem Wert 10 aufnehmen und damit die meisten Statistiken wie count, sum und average rekonstruieren und schätzen.
Gut aufgebaut und gut erklärt. Falls dich die gewichtete Variante interessiert: Ich habe sie hier einmal kurz erläutert: https://gregable.com/2007/10/reservoir-sampling.html
Es gibt auch eine verteilte Variante, die sich leicht mit MapReduce umsetzen lässt.
Als sehr einfacher Algorithmus kann man auch für jedes Element im Stream ein zufälliges Paar erzeugen und die obersten N Einträge nach diesem Zufallswert behalten.
Erstens hat die intuitive Implementierung, bei der man mit
POW(RANDOM(), 1.0 / weight)einen Rang vergibt und dann die obersten N auswählt, Probleme mit der numerischen Stabilität, wenn die Gewichte sehr groß oder sehr klein sind.Zweitens hat die resultierende Stichprobe selbst im Erwartungswert nicht dieselbe Verteilung wie die Grundgesamtheit. Das gilt besonders dann, wenn sich das Gesamtgewicht auf wenige Elemente der Grundgesamtheit konzentriert, ist in vielen Fällen aber eine brauchbare Näherung.
Diese Probleme habe ich hier ausführlicher behandelt: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....
Ein hervorragender Beitrag, leicht zugänglich und mit ausgezeichneten Visualisierungen.
Bei $WORK verwenden wir eine ähnliche Variante, um ein verwandtes Problem zu lösen: die Schätzung bestimmter Perzentile in einem laufenden Stream.
Das auszuwählende Perzentil ändert sich gelegentlich, bleibt aber meist über mehr als eine Billion Iterationen hinweg konstant, und die zugrunde liegenden Daten sind quasi-stationär.
Stützt man diesen Prozess mit einem Splay-Tree, sind Perzentilschätzungen in amortisiert O(1) möglich. Bei gleichem RAM-Verbrauch ist die Fehlerspanne größer als bei mehreren anderen Verfahren, aber es ist sehr schnell.
Durch Anpassen der Ersetzungswahrscheinlichkeit kann man außerdem eine „Daten-Halbwertszeit“ nach Zeit oder Anzahl einführen und die Schätzung zugunsten neuerer Events verzerren; für manche Probleme ist das besser geeignet.