Percentili di Live Capture dati

https://stackoverflow.com/questions/1248815

12-09-2019
|

Domanda

Sto cercando un algoritmo che determina percentili per l'acquisizione dei dati in tempo reale.

Si consideri ad esempio lo sviluppo di un'applicazione server.

Il server potrebbe avere tempi di risposta nel modo seguente: 17 ms 33 ms 52 ms 60 ms 55 ms ecc.

E 'utile per segnalare il tempo di risposta 90 ° percentile, tempo di risposta 80 ° percentile, ecc.

L'algoritmo ingenuo è quello di inserire ogni volta la risposta in un elenco. Quando sono richiesti statistiche, ordinare l'elenco e ottenere i valori nelle posizioni corrette.

usi della memoria scale linearmente con il numero di richieste.

C'è un algoritmo che produce le statistiche percentili "approssimative" dato l'uso della memoria limitata? Per esempio, diciamo che voglio risolvere questo problema in un modo che mi elaborare milioni di richieste, ma solo voglia di utilizzare dire una kilobyte di memoria per percentile monitoraggio (scartando il tracking per le vecchie richieste non è un'opzione in quanto i percentili sono tenuti a essere per tutte le richieste).

richiedono anche che non ci sia una conoscenza a priori della distribuzione. Per esempio, io non voglio specificare eventuali intervalli di secchi prima del tempo.

Soluzione

Credo che ci siano molti buoni algoritmi approssimati per questo problema. Un buon approccio primo taglio è sufficiente utilizzare una matrice a dimensione fissa (ad esempio 1K valore dei dati). Fissare una certa probabilità p. Per ogni richiesta, con probabilità p, scrivere il tempo di risposta nella matrice (sostituendo il tempo più antica lì). Dal momento che l'array è un sottocampionamento del flusso dal vivo e dal sottocampionamento preserva la distribuzione, facendo le statistiche sui tale matrice vi darà un ravvicinamento delle statistiche della piena, in diretta streaming.

Questo approccio ha diversi vantaggi: non richiede alcuna informazione a priori, ed è facile da codice. È possibile creare rapidamente e sperimentalmente determinare, per il server particolare, a che punto di crescita del buffer ha solo un effetto trascurabile sulla risposta. Questo è il punto in cui l'approssimazione è sufficientemente precisa.

Se si scopre che è necessario troppa memoria per darvi le statistiche che sono abbastanza precisi, allora si dovrà scavare ulteriormente. Le buone parole chiave sono: "stream computing", "statistiche stream", e, naturalmente, "percentili". Si può anche provare l'approccio "ire e maledizioni" 's.

Altri suggerimenti

Se si desidera mantenere l'utilizzo della memoria costante come si ottiene sempre più dati, allora si sta andando ad avere per ricampionamento che i dati in qualche modo. Ciò implica che è necessario applicare una sorta di rebinning schema. Si può aspettare fino a quando si acquista una certa quantità di ingressi prime prima di iniziare la rebinning, ma non si può evitare del tutto.

Quindi la tua domanda è veramente chiedere "qual è il modo migliore di binning in modo dinamico i miei dati"? Ci sono un sacco di approcci, ma se si vuole ridurre al minimo le ipotesi circa la gamma o la distribuzione di valori che è possibile ricevere, quindi un approccio semplice è quello di media oltre secchi di dimensioni fisse k , con larghezze logaritmicamente distribuiti . Per esempio, diciamo che si vuole tenere 1000 valori in memoria in qualsiasi momento. Scegli una dimensione per k , dicono 100. Scegli il tuo risoluzione minima, dicono 1ms. Poi

Il primo segmento si occupa di valori tra 0-1ms (width = 1 ms)
secondo secchio: 1-3ms (w = 2 ms)
Terzo secchio: 3-7ms (w = 4 ms)
Quarto secchio: 7-15ms (w = 8ms)
...
secchio Decimo: 511-1023ms (w = 512ms)

Questo tipo di log-scalata approccio è simile ai sistemi chunking utilizzati in algoritmi tabella hash , utilizzato da alcuni filesystem e algoritmi di allocazione di memoria. Funziona bene quando i dati dispone di un ampio range dinamico.

Come nuovi valori vengono in, è possibile scegliere come si desidera ricampionare, a seconda delle vostre esigenze. Ad esempio, è possibile tenere traccia di un media mobile , utilizzare un first-in-first-out , o qualche altro metodo più sofisticato. Vedere la href="http://en.wikipedia.org/wiki/Kademlia" rel="noreferrer"> Kademlia algoritmo per un approccio (usato da Bittorrent ).

In definitiva, rebinning deve perdere alcune informazioni. Le scelte per quanto riguarda il binning determineranno le specifiche di quali informazioni si perde. Un altro modo di dire questo è che l'archivio della memoria dimensione costante implica un trade-off tra gamma dinamica e campionamento fedeltà ; come si fanno che trade-off è a voi, ma come ogni problema di campionamento, non c'è nessun ottenere intorno a questo fatto di base.

Se siete veramente interessati ai pro ei contro, quindi nessuna risposta su questo forum può sperare di essere sufficiente. Si dovrebbe guardare in teoria del campionamento . C'è una quantità enorme di ricerca su questo argomento a disposizione.

Per quello che vale, ho il sospetto che i tempi di server avrà una parte relativamente piccola della gamma dinamica, quindi una scala più rilassata per consentire maggiore campionamento dei valori comuni possono fornire risultati più accurati.

Modifica :. Per rispondere alla tua commento, ecco un esempio di un semplice algoritmo di binning

di memorizzare 1000 valori, in 10 bidoni. Ogni bin quindi contiene 100 valori. Assumere ogni bidone è implementata come una matrice dinamica (una 'lista', in termini Perl o Python).
Quando un nuovo valore è disponibile in:
- Determinare quale bin dovrebbe essere immagazzinato in, in base ai limiti bin che hai scelto.
- Se il bidone non è pieno, aggiungere il valore all'elenco bin.
- Se il bidone è pieno, rimuovere il valore in cima alla lista bidone, e aggiungere il nuovo valore al fondo della lista bin. Questosignifica i vecchi valori vengono gettati via nel corso del tempo.
Per trovare il 90 ° percentile, sorta bin 10. Il 90 ° percentile è il primo valore nella lista ordinata (elemento 900/1000).

Se non ti piace buttare via i vecchi valori, allora è possibile implementare uno schema alternativo da usare al posto. Ad esempio, quando un bidone è pieno (raggiunge 100 valori, nel mio esempio), si potrebbe prendere la media dei più antichi 50 elementi (vale a dire i primi 50 della lista), disfarsi di tali elementi, e quindi aggiungere il nuovo elemento media il bidone, lasciando con un bidone di 51 elementi che ora dispone di spazi per contenere 49 nuovi valori. Questo è un semplice esempio di rebinning.

Un altro esempio di rebinning è downsampling ; gettando via ogni 5 valore in un elenco ordinato, per esempio.

Spero che questo esempio concreto aiuta. Il punto chiave da asporto è che ci sono molti modi per realizzare una memoria costante invecchiamento algoritmo; solo tu puoi decidere ciò che è soddisfacente dato le vostre esigenze.

Ho appena pubblicato un post sul blog questo argomento . L'idea di base è quella di ridurre la necessità di un calcolo esatto in favore di "il 95% per cento di risposte prendere 500ms-600ms o meno" (per tutti i percentili esatte di 500ms-600ms)

È possibile utilizzare qualsiasi numero di secchi di qualsiasi dimensione arbitraria (ad esempio 0 ms-50ms, 50ms-100ms, ... qualsiasi cosa che misura il vostro caso d'uso). Normalmente, non dovrebbe essere un problema, ma tutte le richieste che superano un certo tempo di risposta (ad esempio 5 secondi per un'applicazione web) nell'ultima secchio (cioè> 5000 ms).

Per ogni tempo di risposta appena catturata, è sufficiente incrementare un contatore per il secchio cade in. Per stimare l'n-esimo percentile, tutto ciò che serve è sommando i contatori fino a quando la somma supera n per cento del totale.

Questo approccio richiede soltanto 8 byte per secchio, che permette di tracciare 128 secchi con 1K di memoria. Più che sufficiente per analizzare i tempi di risposta di un'applicazione web utilizzando una granularità di 50 ms).

A titolo di esempio, ecco un Google Grafico ho creato da 1 ora dei dati acquisiti (utilizzando 60 contatori con 200ms per secchio):

Nizza, non è vero? :) Per saperne di più sul mio blog .

(E 'passato parecchio tempo da quando questa domanda è stato chiesto, ma vorrei sottolineare un paio di articoli di ricerca correlate)

C'è stata una notevole quantità di ricerche su percentili approssimative di flussi di dati in questi ultimi anni. Alcuni documenti interessanti con le definizioni piena algoritmo:

Tutti questi documenti propongono algoritmi con complessità spaziale sub-lineare per il calcolo dei percentili approssimate sopra un flusso di dati.

Prova il semplice algoritmo definito nel documento “Procedura sequenziale per la simultanea stima della Diversi percentili” (Raatikainen). E 'veloce, richiede 2 * m + 3 marcatori (per m percentili) e tende a un'accurata approssimazione rapidamente.

Utilizzare un array dinamico T [] di grandi numeri interi o qualcosa in cui T [n] Conta il numer di volte che il tempo di risposta è stato n millisecondi. Se davvero sta facendo statistiche su un'applicazione server poi eventualmente 250 ms tempi di risposta sono il limite assoluto in ogni caso. Così il vostro 1 KB può contenere una 32 bit intero per ogni ms tra 0 e 250, e si dispone di un certo margine di ricambio per un raccoglitore di esubero. Se si desidera qualcosa con più scomparti, andare con 8 numeri di bit per 1000 bidoni, e il momento in cui un contatore traboccherebbe (cioè richiesta 256e in quel tempo di risposta) si sposta i bit in tutti i bidoni dalla 1. (dimezzando in modo efficace il valore in tutti i contenitori). Questo significa che tutti i raccoglitori di ignorare che catturano meno di 1/127 ° dei ritardi che il più visitato catture bin.

Se davvero, davvero bisogno di un insieme di classi specifiche Io suggerirei di utilizzare il primo giorno di richieste a venire con un insieme fisso ragionevole di bidoni. Tutto ciò dinamica sarebbe abbastanza pericoloso in un'applicazione sensibile performance live. Se si sceglie questa strada è meglio sai cosa stai facendo, o un giorno si sta andando ad ottenere chiamato dal letto per spiegare perché il vostro statistiche inseguitore è improvvisamente mangiando il 90% della CPU e della memoria il 75% sul server di produzione.

Per quanto riguarda le statistiche aggiuntive: Per media e la varianza ci sono alcune href="http://people.revoledu.com/kardi/tutorial/RecursiveStatistic/index.html" belle algoritmi ricorsivi che occupano poca memoria. Questi due statistiche possono essere utile sufficiente di per sé per un sacco di distribuzioni perché gli stati del teorema del limite centrale che distribuzioni che che nascono da un numero sufficientemente elevato di variabili indipendenti avvicinano alla distribuzione normale (che è completamente definita dalla media e varianza) è possibile utilizzare uno dei test di normalità sull'ultima N (dove N sufficientemente grande ma vincolata dai vostri requisiti di memoria) per monitorare wether l'assunzione di normalità detiene ancora.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow