Perzentile der Live-Datenerfassung

StackOverflow https://stackoverflow.com/questions/1248815

Frage

Ich suche einen Algorithmus, der Perzentile für die Live-Datenerfassung ermittelt.

Betrachten Sie beispielsweise die Entwicklung einer Serveranwendung.

Der Server kann folgende Antwortzeiten haben:17 ms 33 ms 52 ms 60 ms 55 ms usw. usw.

Es ist nützlich, die Reaktionszeit des 90. Perzentils, die Reaktionszeit des 80. Perzentils usw. anzugeben.

Der naive Algorithmus besteht darin, jede Antwortzeit in eine Liste einzufügen.Wenn Statistiken angefordert werden, sortieren Sie die Liste und rufen Sie die Werte an den richtigen Positionen ab.

Die Speichernutzung skaliert linear mit der Anzahl der Anfragen.

Gibt es einen Algorithmus, der bei begrenzter Speichernutzung „ungefähre“ Perzentilstatistiken liefert?Nehmen wir zum Beispiel an, ich möchte dieses Problem so lösen, dass ich Millionen von Anfragen verarbeite, aber nur, sagen wir, ein Kilobyte Speicher für die Perzentilverfolgung verwenden möchte (das Verwerfen der Verfolgung für alte Anfragen ist keine Option, da die Perzentile dies tun sollen). für alle Anfragen gelten).

Erfordern Sie außerdem, dass keine a priori Kenntnis der Verteilung vorliegt.Beispielsweise möchte ich vorab keine Bucket-Bereiche festlegen.

War es hilfreich?

Lösung

Ich glaube, dass es für dieses Problem viele gute Näherungsalgorithmen gibt.Ein guter erster Ansatz besteht darin, einfach ein Array fester Größe zu verwenden (z. B. Daten im Wert von 1 KB).Bestimmen Sie eine Wahrscheinlichkeit p.Schreiben Sie für jede Anfrage mit der Wahrscheinlichkeit p ihre Antwortzeit in das Array (und ersetzen Sie die älteste Zeit darin).Da es sich bei dem Array um eine Unterabtastung des Live-Streams handelt und die Verteilung durch die Unterabtastung erhalten bleibt, erhalten Sie durch die Erstellung der Statistiken für dieses Array eine Annäherung an die Statistiken des gesamten Live-Streams.

Dieser Ansatz hat mehrere Vorteile:Es erfordert keine Vorabinformationen und ist einfach zu programmieren.Sie können es schnell erstellen und experimentell für Ihren speziellen Server ermitteln, an welchem ​​Punkt das Anwachsen des Puffers nur einen vernachlässigbaren Einfluss auf die Antwort hat.Das ist der Punkt, an dem die Näherung hinreichend genau ist.

Wenn Sie feststellen, dass Sie zu viel Speicher benötigen, um ausreichend präzise Statistiken zu erhalten, müssen Sie weiter nachforschen.Gute Schlüsselwörter sind:„Stream Computing“, „Stream Statistics“ und natürlich „Perzentile“.Sie können auch den Ansatz von „Ire and Curses“ ausprobieren.

Andere Tipps

Wenn Sie die Speichernutzung konstant halten wollen, wie Sie mehr und mehr Daten zu bekommen, dann wirst du Resampling die irgendwie Daten. Das bedeutet, dass Sie irgendeine Art von Rebinning Schema. Sie können warten, bis Sie eine bestimmte Menge an Roh-Eingänge erwerben, bevor die Rebinning beginnen, aber man kann es nicht ganz vermeiden.

So Ihre Frage wirklich fragt: „Was ist der beste Weg, meine Daten dynamisch Binning“? Es gibt viele Ansätze, aber wenn Sie Ihre Annahmen über den Umfang oder die Verteilung von Werten minimieren möchten Sie empfangen, dann wird ein einfacher Ansatz ist Eimer feste Größe im Durchschnitt über k , mit logarithmisch verteilt Breiten . Zum Beispiel können Sie sagen 1000 Werte im Speicher zu einem beliebigen Zeitpunkt halten wollen. Wählen Sie eine Größe für k , sagen 100. Wählen Sie Ihre minimale Auflösung, sagen 1ms. Dann

  • Der erste Eimer befasst sich mit Werten zwischen 0-1ms (width = 1 ms)
  • Zweiter Eimer: 1-3ms (w = 2ms)
  • Third Eimer: 3-7ms (w = 4 ms)
  • Vierte Eimer: 7-15ms (w = 8 ms)
  • ...
  • Zehnte Eimer: 511-1023ms (w = 512ms)

Diese Art von skalierten log Ansatz ist ähnlich wie die Chunking Systemen in Hash-Tabelle Algorithmen , die von einigen Dateisystemen und Speicherzuordnungsalgorithmen verwendet. Es funktioniert gut, wenn die Daten einen großen Dynamikbereich hat.

Als neue Werte kommen in, können Sie wählen, wie Sie das gesampelt werden soll, je nach Ihren Anforderungen. Zum Beispiel könnten Sie eine rel="noreferrer"> bewegen, verwenden Sie ein first-in-first-out oder eine andere kompliziertere Verfahren. Sehen Sie sich den Kademlia Algorithmus für einen Ansatz (verwendet von Bittorrent ).

Schließlich Rebinning müssen Sie einige Informationen verlieren. Sie haben die Wahl, die Binning bezüglich bestimmen, die Besonderheiten, welche Informationen verloren. Ein anderer Weg, dies zu sagen ist, dass die konstante Größe Gedächtnisspeicher impliziert einen Trade-off zwischen Dynamikbereich und die Sampling fidelity ; wie Sie, dass Trade-off ist bis zu Ihnen, aber wie jedes Probenahme Problem, gibt es kein Entkommen, um diese grundlegende Tatsache.

Wenn Sie in den Vor-und Nachteile wirklich interessiert sind, dann kann keine Antwort auf dieses Forum hoffen ausreichend. Sie sollten Stichprobentheorie schauen. Es gibt eine riesige Menge an Forschung zu diesem Thema zur Verfügung.

Für das, was es wert ist, vermute ich, dass der Server mal einen relativ kleinen Dynamikbereich hat, so ein entspannter Skalierung höhere Sampling gemeinsamen Wertes zu ermöglichen, können genauere Ergebnisse liefern.

Bearbeiten . Ihren Kommentar zu beantworten, hier ist ein Beispiel für einen einfachen Binning-Algorithmus

  • Sie speichern 1000 Werte, in 10 Behältern. Jeder Behälter hält somit 100 Werte. Es sei angenommen, jedes Fach als dynamisches Array (eine ‚Liste‘, in Perl oder Python Bedingungen) umgesetzt wird.

  • Wenn ein neuer Wert kommt in:

    • Sie fest, welche sind es gespeichert werden soll, auf der Grundlage der Bin Grenzen Sie gewählt haben.
    • Wenn der Behälter nicht voll ist, fügen Sie den Wert an die Bin-Liste.
    • Wenn der Behälter voll ist, wird der Wert an der Spitze des Behälters Liste entfernen, und hängen an den Boden des Behälters Liste den neuen Wert. DieseEs sind Mittel alte Werte weggeworfen im Laufe der Zeit.

  • das 90. Perzentil zu finden, Sortierbehälter 10. Die 90. Perzentil ist der erste Wert in der sortierten Liste (Element 900/1000).

Wenn Sie nicht wie die alten Werte wegzuwerfen, dann können Sie einige alternative Schema implementieren, anstatt zu verwenden. Zum Beispiel, wenn ein Fach voll ist (100 erreicht Werte, in meinem Beispiel), können Sie den Mittelwert der ältesten 50 Elemente nehmen könnten (dh die ersten 50 in der Liste), die Elemente verwerfen, und dann fügen Sie das neue mittlere Element das ist, Sie mit einem Behälter von 51 Elementen zu verlassen, die nun Platz 49 neue Werte zu halten hat. Dies ist ein einfaches Beispiel für Rebinning.

Ein weiteres Beispiel für Rebinning ist Unterabtasten ; jeden fünften Wert in einer sortierten Liste, zum Beispiel des Wegwerfen.

Ich hoffe, das konkrete Beispiel hilft. Der entscheidende Punkt wegzunehmen ist, dass es gibt viele Möglichkeiten, einen konstanten Speicheralterungs Algorithmus zu erreichen; können nur Sie entscheiden, was Ihre Anforderungen zufrieden stellend gegeben ist.

Ich habe gerade einen Blogeintrag veröffentlicht am dieses Thema . Die Grundidee ist es, die Voraussetzung für eine exakte Berechnung für „95% Prozent der Antworten nehmen 500ms-600ms oder weniger“ (für alle genauen Perzentile von 500ms-600ms)

zu reduzieren

Sie können eine beliebige Anzahl von Eimern von jeder beliebigen Größe verwenden (zum Beispiel 0 ms-50 ms, 50 ms-100 ms, ... einfach alles, was Ihren usecase paßt). Normalerweise sollte es kein Problem sein, aber alle Anforderungen, die eine gewisse Reaktionszeit (beispielsweise 5 Sekunden für eine Web-Anwendung), in der letzten Schaufel überschreiten (d> 5000 ms).

Für jede neu aufgenommene Reaktionszeit, erhöhen Sie einfach einen Zähler für den Eimer es in fällt. Um den n-te Perzentil zu schätzen, alles, was gebraucht wird Zähler summiert, bis die Summe n Prozent der Gesamt überschreitet.

Dieser Ansatz erfordert nur 8 Byte pro Kübel, so dass 128 Eimer mit 1K Speicher verfolgen. Mehr als ausreichend für die Analyse von Antwortzeiten einer Web-Anwendung mit einer Körnung von 50 ms).

Als Beispiel ist hier ein Google Chart ich 1 Stunde erstellt haben von erfassten Daten (60 Zähler mit 200 ms pro Eimer verwendet):

Nizza, ist es nicht? :) mehr auf meinem Blog .

(Es ist schon eine ganze Weile, da diese Frage gestellt wurde, aber ich würde gerne ein paar ähnliche Forschungsarbeiten darauf hin)

Es hat sich auf ungefähre Perzentile von Datenströmen in den letzten Jahren eine erhebliche Menge an Forschung. Einige interessante Papiere mit voller Algorithmus Definitionen:

Alle diese Papiere schlagen Algorithmen mit sublinear Raum Komplexität für die Berechnung der ungefähren Perzentile über einen Datenstrom.

Versuchen Sie, den einfachen Algorithmus in dem Papier definiert „Sequential Verfahren für die gleichzeitige Schätzung von mehreren Perzentile“ (Raatikainen). Es ist schnell, erfordert 2 * m + 3 Marker (für m Perzentile) und neigt dazu, eine genaue Annäherung schnell.

Verwenden Sie ein dynamisches Array T [] von großen ganzen Zahlen oder etwas, wo T [n] zählt die numer Mal war die Reaktionszeit n Millisekunden. Wenn Sie wirklich Statistiken auf einer Server-Anwendung tun, dann möglicherweise 250 ms Reaktionszeiten ohnehin Ihr absolutes Limit sind. So Ihr 1 KB hält eine 32-Bit-Integer-für jede ms zwischen 0 und 250, und Sie haben eine gewissen Spielraum für einen Überlaufbehälter zu ersparen. Wenn Sie etwas mit mehr Bins wollen, gehen Sie mit 8-Bit-Zahlen für 1000 Bins, und in dem Moment ein Zähler würde überlaufen (dh 256. Anfrage zu dieser Reaktionszeit), um die Bits in allen Bins herunterschalten von 1. (effektiv den Wert Halbieren in alle Fächer). Dies bedeutet, dass Sie alle Bins außer Acht lassen, dass der Fang von weniger als 1 / 127th der Verzögerungen, die die meisten sind Fänge besucht.

Wenn Sie wirklich, wirklich eine Reihe spezieller Behälter benötigen würde ich mit dem ersten Tag der Anfragen vorschlagen mit einem vernünftigen festen Satz von Bins zu kommen. Alles, was dynamisches würde in einer Live-Performance sensible Anwendung sehr gefährlich sein. Wenn Sie diesen Weg wählen, würden Sie besser wissen, was Sie tut, oder einem Tag wird dich aus dem Bett genannt werden, zu erklären, warum Ihre Statistiken Tracker plötzlich 90% CPU und 75% Speicher auf dem Produktionsserver isst.

Wie für zusätzliche Statistiken: Für Mittelwert und die Varianz gibt es einige schön rekursive Algorithmen dass nehmen nur sehr wenig Speicher. Diese beiden Statistiken können sehr nützlich genug, um in sich selbst sein für viele Distributionen, weil der zentralen Grenzwertsatzes Staaten dass Verteilungen, die die aus einer ausreichend großen Anzahl von unabhängigen Variablen entstehen die Normalverteilung annähern (die vollständig durch Mittelwert und die Varianz definiert ist) können Sie eine der

Nicht verbunden mit StackOverflow
scroll top