Reservoir Sampling: Faire Zufallsstichproben aus Daten unbekannter Größe

 (samwho.dev)
1 Punkte von GN⁺ 2025-05-09 | 1 Kommentare | Auf WhatsApp teilen
  • Reservoir Sampling ist eine einzigartige und effiziente Technik, um fair Zufallsstichproben zu ziehen, wenn die Größe der Daten unbekannt ist
  • Sie wird in vielen Bereichen eingesetzt, etwa bei der Erfassung von Echtzeit-Logs, weil sie Situationen effizient löst, die mit traditionellen Methoden nicht praktikabel sind
  • Die Kernidee besteht darin, den Speicherplatz bei jedem neuen Element mit Wahrscheinlichkeit 1/n zu aktualisieren, sodass alle Elemente die gleiche Chance auf Auswahl erhalten
  • Wenn mehrere Stichproben gezogen werden sollen, wird die Wahrscheinlichkeit auf k/n erweitert, und entsprechend dieser Wahrscheinlichkeit wird eine bestehende Stichprobe zufällig ersetzt
  • Der Algorithmus garantiert faires Sampling bei geringem Speicherverbrauch und erhöht die Effizienz und Zuverlässigkeit von Echtzeitverarbeitung

Konzept und Notwendigkeit von Reservoir Sampling

  • Reservoir Sampling ist eine effiziente Technik, um fair Stichproben aus einer Datenmenge zu ziehen, deren Gesamtgröße unbekannt ist
  • Im Normalfall ist es effektiv, bei bekannter Datenmenge zufällige Indizes zu ziehen, aber bei unbekannter Größe ist diese Methode nicht möglich
  • Bei großen Datenmengen, die linear eintreffen (z. B. Log-Streams), muss der Speicherverbrauch begrenzt werden, während gleichzeitig sichergestellt werden muss, dass jedes Datum mit derselben Wahrscheinlichkeit ausgewählt wird

Sampling bei bekannter Größe

  • Bei einer Menge mit begrenzter Größe (z. B. 10 Karten) eignet sich das Mischen aller Elemente und anschließende Auswählen der gewünschten Anzahl von vorne, um Fairness zu garantieren
  • Mit der Array-Struktur eines Computers lassen sich Zufallsindizes direkt auswählen, um schnell Stichproben zu ziehen
  • Bei Millionen von Datenpunkten oder Streams unbekannter Größe ist diese Vorgehensweise jedoch ineffizient

Sampling bei unbekannter Größe: Probleme und Notwendigkeit

  • In der Praxis kommt häufig die Situation vor, dass Daten sequenziell einzeln eintreffen, nur 1 Element gespeichert werden kann und bereits vergangene Daten nicht mehr zurückgeholt werden können
  • In Log-Sammelsystemen kann es etwa zu plötzlichen Traffic-Spitzen kommen, sodass nur ein Teil per Sampling weitergesendet werden darf, um Serverüberlastung zu vermeiden
  • Beliebig einfach die ersten paar Elemente auszuwählen, führt zu mangelnder Fairness, weil dadurch nicht allen Einträgen die gleiche Chance gegeben wird

Funktionsweise des Reservoir-Sampling-Algorithmus

  • Bei jedem eingehenden Datum wird die bisherige Anzahl n berechnet, und das neue Datum wird mit Wahrscheinlichkeit 1/n ausgewählt
  • Das erste Datum wird immer ausgewählt; danach ersetzt jedes neue Datum mit schrittweise sinkender Wahrscheinlichkeit das bestehende Datum, wodurch die gleiche Auswahlwahrscheinlichkeit erhalten bleibt
  • Am Ende ist die Wahrscheinlichkeit gleichmäßig verteilt, unabhängig davon, welches Datum aus der Gesamtmenge im Speicher verbleibt
  • Statt eines Münzwurfs wird eine Wahrscheinlichkeit von 1/n verwendet, um allen Daten eine faire Chance zu garantieren

Mathematische Intuition (erklärt am Kartenbeispiel)

    1. Datum: wird immer ausgewählt (Wahrscheinlichkeit 1/1)
    1. Datum: wird mit Wahrscheinlichkeit 1/2 ausgewählt, das bestehende Datum bleibt nur mit 50 % Wahrscheinlichkeit erhalten
    1. Datum: Das neue Datum wird mit 1/3 ausgewählt, beim bestehenden Datum akkumuliert sich die Überlebenswahrscheinlichkeit über den Komplementärwert dieser Wahrscheinlichkeit
  • Verallgemeinert gilt: Bis einschließlich des n-ten Datums hat jedes Datum stets eine Wahrscheinlichkeit von 1/n

Erweiterung auf mehrere Stichproben (k-out-of-n)

  • Wenn k Stichproben gezogen werden sollen, wird jedes neue Datum mit Wahrscheinlichkeit k/n ausgewählt; bei Auswahl ersetzt es zufällig einen der aktuell gespeicherten Einträge
  • Auch bei diesem Verfahren bleibt die Wahrscheinlichkeit gleich, dass ein gespeicherter Eintrag als Stichprobe erhalten bleibt
  • Bei konstantem Speicherverbrauch (nur k Elemente) lassen sich so selbst aus großen Datenströmen fair mehrere Stichproben ziehen

Einsatz von Reservoir Sampling in Log-Sammeldiensten

  • Von den pro Sekunde eingehenden Logs werden mit Reservoir Sampling höchstens k Stück (z. B. 5) ausgewählt und nur diese Stichproben an den Server gesendet
  • Bei geringer Datenmenge werden alle Logs übertragen, sodass nichts verloren geht; selbst bei Traffic-Spitzen werden nie mehr als k Elemente gesendet, was die Stabilität des Dienstes sicherstellt
  • Durch das Senden der Stichproben in festen Intervallen entsteht zwar ein kleiner Delay bei der Echtzeitfähigkeit, insgesamt verbessert das jedoch Stabilität und Kosteneffizienz

Weitere Anwendungen und Referenzmaterial

  • Wenn bestimmte Daten (z. B. Fehler-Logs) wichtiger sind, kann eine Variante des gewichteten Reservoir Sampling (Weighted Reservoir Sampling) verwendet werden
  • Weiterführende Konzepte finden sich in externen Quellen wie Wikipedia, aber das Grundprinzip bleibt die Wahrung der Fairness

Fazit

  • Reservoir Sampling ist ein sehr eleganter und praktischer Algorithmus, mit dem sich Datenströme unbekannter Größe speichereffizient und fair sampeln lassen
  • Wegen seiner Vorteile bei Geschwindigkeit, Konsistenz und geringem Ressourcenverbrauch ist es für die Echtzeit-Datenverarbeitung in vielen Bereichen besonders wertvoll

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-05-09
Hacker-News-Kommentare

  • Als ich als Kind auf dem Land lebte, hatte ein Freund meines Vaters beruflich jedes Jahr die Population von Schneehühnern (ptarmigan) in den Bergen zu erfassen.
    Dabei lief er eine festgelegte Route ab und scheuchte die Vögel in regelmäßigen Zeitabständen auf, um sie zu zählen.
    Diese Zahlen reichte er beim zuständigen Amt ein, und dort wurde daraus die Gesamtpopulation geschätzt.
    In einem Jahr war der Freund meines Vaters im Ausland und erklärte einem anderen Freund die Methode ausführlich, damit dieser die Aufgabe übernimmt.
    Als der eigentliche Erhebungstag kam, hatte der andere es jedoch einfach vergessen und reichte aus Bequemlichkeit irgendwelche plausibel wirkenden Zahlen ein.
    Im Jahr darauf stand auf Seite 1 der Lokalzeitung die Schlagzeile „Rekordhafter Anstieg der Schneehuhn-Population“.
    Dass diese abrupte Veränderung überhaupt eine Meldung wert war, lag daran, dass die Zahlen als Grundlage für Jagdgenehmigungen verwendet wurden. Daran hatte der Freund nicht gedacht.

    • Die Moral ist: Statistiken sollte man nicht blind vertrauen.
      Ich habe einmal an dem Buchungssystem eines großen Skigebiets gearbeitet und musste den offiziellen Statistikbericht fertigstellen, der für Behörden eingereicht wurde und Dinge wie Übernachtungen von Gästen enthielt.
      Wegen Zeitmangels war das eine Nachtschicht-Aktion, und die Statistikdaten dieses Jahres lagen ziemlich weit von den tatsächlichen Werten entfernt.

  • Hallo! o/
    Ich bin der Autor dieses Artikels. Fragen oder Feedback sind willkommen.
    Der Code für alle Beiträge ist unter MIT-Lizenz auf https://github.com/samwho/visualisations verfügbar. Ihr könnt ihn gern verwenden.

    • Ich halte das für einen sehr guten Beitrag.
      Eine andere Richtung zur Optimierung von Reservoir Sampling besteht darin, nicht für jedes Item eine Zufallszahl zu ziehen, um zu prüfen, ob ersetzt wird, sondern die Sprungweite aus einer geometrischen Verteilung zu ziehen.
      Das ist interessant, wenn man günstig viele Elemente überspringen kann, etwa bei Tape Drives (man kennt die Bandlänge vorher nicht, kann aber während des Überspringens den Großteil des Systems im Sleep-Modus lassen).
      Um aus n Elementen k Stichproben zu ziehen, braucht man ungefähr nur O(k * log(n/k)) Sampling- und Skip-Operationen.
      Ein weiteres Konzept, das ich mag, ist, jedem ankommenden Element eine zufällige Priorität zuzuweisen und dann die Top-k zu behalten.
      Ein verwandtes Problem ist, wie man aus einem Stream unbekannter Länge die Top-k-Elemente mit O(n) Zeit und O(k) Speicher auswählt.
      Man wirft alles in einen unsortierten Puffer der Größe 2*k und behält, sobald er voll ist, mit Randomized Quickselect oder Median-of-Medians nur die Top-k.
      Wenn man diesen Prozess n-mal durchführt, braucht man O(n) Zeit.
      Als verwandte Technik ist auch Rendezvous Hashing interessant.
      Und zur Alias-Methode hilft dieser Beitrag weiter: https://www.keithschwarz.com/darts-dice-coins/

    • Ich frage mich, ob man diese Methode verschachtelt einsetzen kann.
      Wenn ich zum Beispiel in meinem Service Reservoir Sampling mache und der Log-Collector-Service ebenfalls Reservoir Sampling anwendet: Ist das dann äquivalent dazu, nur den Log-Collector einmal zu verwenden?

    • Mir haben vor allem die Animationen und Erklärungen gefallen.
      Besonders die verschiedenen Interaktionen im Diagramm, etwa 100-mal mischen, waren beeindruckend.
      Anfangs war ich etwas verwirrt, weil es beim Ziehen von 3 Karten aus 10 oder 436.234 Karten plötzlich zu einem Beispiel überging, bei dem man nur noch eine Karte nach der anderen sieht und 1 Karte auswählt.
      Im Abschnitt „Jetzt werfen wir eine Kurve rein!“ würde eine zusätzliche Abschnittstrennung das Verständnis verbessern.
      Ab da nehmen wir an, dass wir nur noch 1 Karte in der Hand haben und die Deckgröße ebenfalls unbekannt ist.

    • Ich mag besonders das Design der Website.
      Die Interaktionen, die Hundefigur, die Schriftarten und Farben, das gesamte Layout — alles hat mir gefallen.

    • Der ganze Blog wirkt wie eine Schatztruhe.
      Ich freue mich, ihn entdeckt zu haben.

    • Die Grafiken haben mir gefallen.
      Allerdings bin ich nicht sicher, ob diese Methode statistisch vollständig stichhaltig ist. Zwar werden innerhalb eines Zeitraums alle Logs mit derselben Wahrscheinlichkeit ausgewählt, aber ich frage mich, ob Logs aus „langsamen Phasen“ in der Gesamtstatistik nicht überrepräsentiert werden.
      Wenn man zum Beispiel herausfinden will, welcher Endpoint im Gesamtsystem die meiste CPU verbraucht, um ihn zu optimieren, werden dann Logs von Endpoints mit kurzzeitigem Traffic-Spike nicht unterrepräsentiert, sodass man stark genutzte Endpoints am Ende falsch bewertet?
      Oder auch bei Kapazitätsplanung pro Service: Services mit Burst-Traffic scheinen unterrepräsentiert zu werden.
      Für welche Einsatzzwecke eignet sich Reservoir Sampling eigentlich gut, und welche Arten statistischer Analysen sind damit möglich?

    • Sehr guter Artikel; Mathematik oder Statistik müsste man so unterrichten, dann würde das Lernen Spaß machen.
      Es hat mich an https://distill.pub/ erinnert.

    • Die Formulierung „Sometimes the hand of fate must be forced“ ist mir im Gedächtnis geblieben.

    • Mir gefällt besonders die Art der Interaktivität.

    • Ich finde das Website-Design und die Didaktik wirklich wunderschön. Vielen Dank.

    • Ich frage mich, ob der Blog einen RSS-Feed hat.

  • Ein sehr klarer und gut illustrierter Beitrag.
    Als fortgeschrittene Erweiterung gibt es auch Algorithmen, die statt der Basismethode direkt berechnen, wie viele Elemente jeweils übersprungen werden können.
    Eine gute Erklärung dazu gibt es hier: https://richardstartin.github.io/posts/reservoir-sampling

  • Guter Artikel und gute Erklärung.
    Für echtes Log-Collecting würde ich empfehlen, zuerst verschiedene andere Methoden auszuprobieren und Fairness nur als letztes Mittel einzusetzen.
    Zum Beispiel kann man Logs priorisieren und zuerst Logs mit niedriger Priorität (hoher Verbosity) verwerfen.
    Bei Logs, die semantisch eine einzige Aktivität bilden, kann man repetitive Zwischenlogs reduzieren und nur Start, Ende und wichtige Statusänderungen speichern.
    Wenn man ähnliche oder doppelte Logs aggregiert und als Zusammenfassung speichert, spart das nicht nur Gesamtspeicher, sondern hilft auch bei der Trenderkennung.

    • Ich lese mich in letzter Zeit viel in das Thema Observability ein, und die genannte Methode ist eine Mischform aus Head- und Tail-Sampling.
      Eine Erklärung dazu findet sich hier: https://docs.honeycomb.io/manage-data-volume/sample/

    • Dieser Punkt wird im Artikel auch behandelt.
      Tatsächlich ist es wichtiger, nicht einfach alle Low-Priority-Logs zu verwerfen, sondern ein „Budget“-Konzept anzuwenden und sie zu begrenzen.
      Die Gesamtzahl aller Logs kann zusätzlich durch ein separates übergeordnetes Budget limitiert werden.
      Reservoir Sampling kann mit solchen Einschränkungen ebenfalls gut umgehen.

  • Guter Artikel und gute Erklärung.
    In Vitters Arbeit wird „Algorithm R“ beschrieben, eine Form von Reservoir Sampling.
    Siehe dazu: https://www.cs.umd.edu/~samir/498/vitter.pdf

    • Allerdings sagt auch diese Arbeit nur „Algorithm R (which is a reservoir algorithm due to Alan Waterman)“ und lässt die Quelle weg.
      Vitters frühere Arbeit https://dl.acm.org/doi/10.1145/358105.893 verweist auf Band 2 von Knuths TAOCP, aber auch dort gibt es keine klare Quellenangabe.

  • Sehr gut zusammengestellt, und wer sich für Weighted Reservoir Sampling interessiert, findet eine Erklärung unter https://gregable.com/2007/10/reservoir-sampling.html
    Dort wird auch ein Verfahren beschrieben, das sich in verteilten Umgebungen leicht per Map-Reduce anwenden lässt, sowie eine sehr einfache Methode, bei der jedem Item ein Zufallswert zugeordnet und dann Top N beibehalten wird.

    • Zwei Anmerkungen zur gewichteten Variante:
      Die grundlegende Methode, für jedes Item mit POW(RANDOM(), 1.0 / weight) eine Priorität zu ziehen und dann die Top N auszuwählen, verliert bei sehr großen oder sehr kleinen Gewichtungen (weight) numerische Stabilität.
      Außerdem kann die resultierende Stichprobe die Verteilung der ursprünglichen Grundgesamtheit möglicherweise nicht ausreichend gut widerspiegeln. Das gilt besonders dann, wenn sich das Gesamtgewicht auf wenige Items konzentriert.
      Trotzdem ist es in den meisten Situationen eine ausreichend gute Näherung.
      Mehr dazu erklärt dieser Beitrag: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html

  • Beim Lesen dieses Artikels musste ich an die Methode denken, mit der die Alliierten im Zweiten Weltkrieg die deutsche Panzerproduktion anhand von Seriennummern schätzten.
    Die Leute vor Ort schätzten damals die tatsächliche Produktionsmenge auf etwa das Fünffache, aber die Methode mit den Seriennummern erreichte eine Genauigkeit von über 90 %.

  • Hervorragender Beitrag, und die Visualisierung ist wirklich ausgezeichnet.
    In echten Systemen verwenden wir eine ähnliche Variante, um sich ändernde Perzentilwerte in sehr großen Streams in Echtzeit zu schätzen.
    Der Perzentilwert ändert sich gelegentlich, bleibt aber meist über sehr viele Wiederholungen hinweg gleich. Die zugrunde liegenden Daten sind quasi-stationär.
    Mit einem Splay Tree als Fallback lässt sich das mit amortisiertem O(1) schätzen; gegenüber anderen Methoden ist die Fehlerspanne im Verhältnis zum RAM-Verbrauch zwar größer, dafür aber speichereffizient.
    Man kann auch die Ersetzungswahrscheinlichkeit anpassen, um die „Half-Life“ der Daten zu verkürzen, also die Schätzung bewusst stärker auf neuere Daten zu gewichten.

  • Aus Sicht der Data Science enthalten bereits die Datenmengen selbst wichtige Information, daher sollte die Sampling-Rate immer mit aufgezeichnet werden.
    Wenn zum Beispiel die Sampling-Rate 10 % beträgt, sollte man für jede Stichprobe den Wert 10 mitführen, damit sich Gesamtsummen, Summen, Mittelwerte usw. korrekt rekonstruieren oder schätzen lassen.

  • Dieser Beitrag zeigt die Trade-offs bei der Erfassung von Telemetry-Daten (Traces, Logs, Metrics) sehr gut.
    Dieser Bereich der Datenanalyse hat eine hohe Einstiegshürde und wird von vielen Entwicklern übersehen.

    • Darüber denke ich schon länger nach: Ich würde gern einmal einen Artikel darüber schreiben, wie stark sich allein die „Form der Linie“ in einem Diagramm je nach Sampling-Strategie verändern kann.
      Selbst wenn die Daten gleich aussehen, kann sich das beobachtete Diagramm komplett ändern, je nachdem, wie gesampelt wurde — und viele Menschen übersehen genau diesen Punkt.