Percentiles de Captura de Datos en Vivo

Question

Busco a un algoritmo que determina los percentiles para la captura de datos en tiempo real.

Por ejemplo, considere el desarrollo de una aplicación de servidor.

El servidor podría tener tiempos de respuesta de la siguiente manera: 17 ms 33 ms 52 ms 60 ms 55 ms etc.

Es útil informar sobre el tiempo de respuesta percentil 90, percentil 80 tiempo de respuesta, etc.

El algoritmo ingenuo es insertar cada tiempo de respuesta en una lista. Cuando se solicitan estadísticas, ordenar la lista y obtener los valores en las posiciones adecuadas.

usos de memoria escala de forma lineal con el número de solicitudes.

¿Existe un algoritmo que produce las estadísticas de percentil "aproximadas" dadas uso de memoria limitada? Por ejemplo, digamos que quiero resolver este problema de una manera que procesar millones de solicitudes pero sólo quiero usar decir un kilobyte de memoria para percentil de seguimiento (descartando el registro de solicitudes de edad no es una opción ya que los percentiles se supone que deben ser para todas las solicitudes).

También se requiere que no hay un conocimiento a priori de la distribución. Por ejemplo, no quiero especificar cualquier intervalo de cubos antes de tiempo.

Answer 1

Creo que hay muchos buenos algoritmos aproximados para este problema. Una buena aproximación de primer corte es simplemente usar una matriz de tamaño fijo (por ejemplo 1K valor de los datos). Fijar cierta probabilidad p. Para cada solicitud, con probabilidad p, escribir su tiempo de respuesta en la matriz (reemplazando el tiempo más antiguo de allí). Dado que la matriz es un submuestreo de la transmisión en vivo y desde el submuestreo conserva la distribución, haciendo las estadísticas de esa matriz le dará una aproximación de las estadísticas de la corriente total, en vivo.

Este enfoque tiene varias ventajas: no requiere información a priori, y es fácil de código. Se puede construir con rapidez y de forma experimental determinar, por el servidor en particular, en qué momento cada vez mayor el tampón tiene sólo un efecto insignificante sobre la respuesta. Ese es el punto en el que la aproximación es suficientemente precisa.

Si usted encuentra que necesita demasiada memoria para darle estadísticas que son lo suficientemente precisa, entonces tendrá que seguir perforando. Las palabras clave son: "stream computing", "estadísticas Stream", y por supuesto "percentiles". También puede intentar enfoque de "ira y maldiciones" 's.

Answer 2

Si desea mantener el uso de la memoria constante a medida que más y más datos, entonces usted va a tener que volver a muestrear que los datos de alguna manera. Eso implica que se debe aplicar algún tipo de rebinning esquema. Puede esperar hasta que adquiera una cierta cantidad de las materias primas antes de comenzar el rebinning, pero no se puede evitar por completo.

Entonces, la pregunta es realmente preguntando "¿cuál es la mejor manera de hurgar en la basura de forma dinámica los datos de mi"? Hay un montón de enfoques, pero si desea reducir al mínimo sus suposiciones sobre el rango o la distribución de los valores que puede recibir, a continuación, un enfoque sencillo es promediar sobre cubos de tamaño fijo k , con anchos logarítmicamente distribuidas . Por ejemplo, digamos que usted quiere sostener 1000 valores en la memoria en un momento dado. Elija un tamaño de k , dicen 100. Escoja su resolución mínima, dicen 1ms. Entonces

• El primer cubo ocupa de valores entre 0-1ms (width = 1 ms)
• segundo cubo: 1-3ms (W = 2 ms)
• Tercera de cubo: 3-7ms (W = 4 ms)
• Cuarto de cubo: 7-15ms (W = 8 ms)
• ...
• Décimo de cubo: 511-1023ms (w = 512ms)

enfoque

Este tipo de escala log- es similar a los sistemas de chunking utilizados en algoritmos de hash mesa , utilizado por algunos sistemas de archivos y los algoritmos de asignación de memoria. Funciona bien cuando los datos tienen un gran rango dinámico.

A medida que nuevos valores vienen en, puede elegir cómo desea volver a muestrear, dependiendo de sus necesidades. Por ejemplo, se puede realizar un seguimiento de un media móvil , utilizar un primero en entrar, primero en salir , o algún otro método más sofisticado. Ver la href="http://en.wikipedia.org/wiki/Kademlia" rel="noreferrer"> Kademlia algoritmo para un enfoque (utilizado por Bittorrent ).

En última instancia, rebinning se debe perder algo de información. Sus opciones con respecto a la binning determinarán los detalles de lo que se pierde información. Otra forma de decir esto es que el almacenamiento de memoria tamaño constante implica un compromiso entre rango dinámico y la fidelidad de muestreo; la forma de hacer que la compensación es de usted, pero como cualquier problema de muestreo, no hay manera de evitar este hecho básico.

Si está realmente interesado en los pros y los contras, entonces no hay respuesta en este foro puede aspirar a ser suficiente. Usted debe mirar en teoría del muestreo . Hay una enorme cantidad de investigación sobre este tema disponible.

Por lo que vale, sospecho que sus tiempos de servidores tendrán un relativamente pequeño rango dinámico, por lo que una escala más relajado para permitir una mayor toma de muestras de los valores comunes pueden proporcionar unos resultados más precisos.

Editar . Para responder a su comentario, he aquí un ejemplo de un sencillo algoritmo de agrupación

• almacenar valores de 1000, en 10 contenedores. Por tanto, cada bin tiene 100 valores. Supongamos que cada bin se implementa como una matriz dinámica (a 'lista', en términos Perl o Python).

• Cuando un nuevo valor entra en juego:

  • Determinar qué bandeja debe ser almacenado en, en base a los límites de basura que ha elegido.
  • Si el contenedor no está lleno, añadir el valor a la lista bin.
  • Si la bandeja está llena, quitar el valor en la parte superior de la lista de bin, y añadir el nuevo valor a la parte inferior de la lista bin. Estalos valores medios de edad se tiran a través del tiempo.

• Para encontrar el percentil 90, más o menos bin 10. El percentil 90 es el primer valor de la lista ordenada (elemento 900/1000).

Si no le gusta tirar los viejos valores, a continuación, se puede implementar un esquema alternativo que usar. Por ejemplo, cuando un cubo se llena (alcanza los 100 valores, en mi ejemplo), se puede tomar el promedio de los 50 elementos más antiguos (es decir, el primero 50 en la lista), desechar esos elementos, y luego añadir el nuevo elemento promedio a la papelera, dejándole con un cubo de 51 elementos que ahora dispone de espacio para contener 49 nuevos valores. Este es un ejemplo sencillo de rebinning.

Otro ejemplo de rebinning es submuestreo ; tirar todos los valores quinto en una lista ordenada, por ejemplo.

Espero que este ejemplo concreto ayuda. El punto clave para llevar es que hay un montón de maneras de lograr un recuerdo constante de envejecimiento algoritmo; sólo usted puede decidir lo que es satisfactorio teniendo en cuenta sus necesidades.

Answer 3

He acaba de publicar un blog el este tema. La idea básica es la de reducir la necesidad de un cálculo exacto a favor del "95% por ciento de las respuestas de tomar 500ms-600ms o menos" (para todos los percentiles exactos de 500ms-600ms)

Se puede usar cualquier número de cubos de cualquier tamaño arbitrario (por ejemplo 0 ms-50ms, 50ms-100ms, ... cualquier cosa que se adapte a su caso de uso). Normalmente, no debería ser un problema a pero todas las solicitudes que superan un tiempo de respuesta determinada (por ejemplo, 5 segundos para una aplicación de web) en el último cubo (es decir> 5000ms).

Para cada tiempo de respuesta recién capturado, sólo tiene que incrementar un contador para el cubo que cae en. Para estimar el percentil de orden n, todo lo que se necesita es resumiendo contadores hasta que la suma excede n por ciento del total.

Este método sólo requiere 8 bytes por balde, lo que permite realizar un seguimiento de 128 cubos con 1 K de memoria. Más que suficiente para el análisis de los tiempos de respuesta de una aplicación web utilizando una granularidad de 50 ms).

A modo de ejemplo, he aquí una Google Chart He creado desde 1 hora de datos capturados (usando 60 contadores con 200 ms por balde):

Niza, ¿no es así? :) Leer más en mi blog .

Answer 4

(Ha pasado bastante tiempo desde que se hizo esta pregunta, pero me gustaría señalar algunos trabajos de investigación relacionados)

Ha habido una cantidad significativa de investigación sobre los percentiles aproximadas de los flujos de datos en los últimos años. Unos papeles interesantes con las definiciones completo algoritmo:

• Un algoritmo rápido para aproximada cuantiles de datos de alta velocidad arroyos

• espacio-tiempo-y algoritmos deterministas eficientes para cuantiles sesgadas más flujos de datos

• cómputo eficaz

  de cuantiles sesgadas sobre los flujos de datos

Todos estos documentos proponen algoritmos con complejidad espacio sub-lineal para el cálculo de percentiles aproximadas sobre una corriente de datos.

Answer 5

Prueba el sencillo algoritmo definido en el documento “Procedimiento Secuencial para el uso simultáneo Estimación de Varios Percentiles” (Raatikainen). Es rápido, requiere 2 * m + 3 marcadores (para m percentiles) y tiende a una aproximación precisa rápidamente.

Answer 6

Utilice una matriz dinámica T [] de grandes números enteros o algo donde T [n] cuenta el numer de veces que el tiempo de respuesta era n milisegundos. Si realmente está haciendo estadísticas de una aplicación de servidor luego, posiblemente, 250 ms tiempos de respuesta son su límite absoluto de todos modos. Por lo que su 1 KB sostiene un número entero de 32 bits por cada ms entre 0 y 250, y tienes algo de espacio de sobra para una bandeja de excedente. Si quieres algo con más contenedores, ir con los números de 8 bits para 1000 contenedores, y el momento en que un contador se desbordaría (es decir, 256º solicitud en ese tiempo de respuesta) que cambia los bits en todas las bandejas por 1. (reducir a la mitad el valor de la eficacia todos los bins). Esto significa que usted caso omiso de todos los contenedores que capturan menos de 1 / 127ª de los retrasos que la captura de bin más visitados.

Si realmente, realmente necesita un conjunto de contenedores específicos me gustaría sugerir el uso de la primera jornada de solicitudes para llegar a un conjunto fijo razonable de contenedores. Cualquier cosa dinámica sería muy peligroso en una aplicación sensible en vivo, el rendimiento. Si elige este camino es mejor que sabes lo que estás haciendo, o que un día van a ser llamado de la cama para explicar por qué el rastreador de estadísticas está comiendo repentinamente el 90% de la CPU y la memoria 75% en el servidor de producción.

En cuanto a las estadísticas adicionales: Para media y la varianza hay algunas href="http://people.revoledu.com/kardi/tutorial/RecursiveStatistic/index.html" agradables algoritmos recursivos que ocupan muy poca memoria. Estas dos estadísticas pueden ser útiles en sí mismos suficientes para una gran cantidad de distribuciones porque los estados del teorema del límite central de que las distribuciones que que surgen de un número suficientemente grande de variables independientes se aproximan a la distribución normal (que está totalmente definida por media y la varianza) se puede utilizar uno de los pruebas de normalidad en el último N (donde N suficientemente grande, pero limitada por sus requisitos de memoria) para supervisar wether el supuesto de normalidad aún mantiene.