algorithm - tecnica - Percentiles de captura de datos en vivo

perimetro braquial tecnica (6)

Estoy buscando un algoritmo que determine los percentiles para la captura de datos en vivo.

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

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

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

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

Los usos de memoria se escalan linealmente con el número de solicitudes.

¿Existe un algoritmo que arroje estadísticas percentiles "aproximadas" dado el uso limitado de la memoria? Por ejemplo, supongamos que quiero resolver este problema de manera que procese millones de solicitudes, pero solo deseo utilizar un kilobyte de memoria para el seguimiento de percentiles (descartar el seguimiento de solicitudes anteriores no es una opción, ya que se supone que los percentiles deben ser para todas las solicitudes).

También requiere que no haya conocimiento a priori de la distribución. Por ejemplo, no quiero especificar ningún rango de cubos antes de tiempo.

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

Ha habido una gran cantidad de investigación sobre percentiles aproximados de flujos de datos en los últimos años. Algunos artículos interesantes con definiciones completas de algoritmos:

Todos estos documentos proponen algoritmos con complejidad de espacio sub-lineal para el cálculo de percentiles aproximados sobre un flujo de datos.

Acabo de publicar una publicación de blog sobre este tema . La idea básica es reducir el requisito de un cálculo exacto a favor de "95% por ciento de respuestas tomar 500ms-600ms o menos" (para todos los percentiles exactos de 500ms-600ms)

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

Para cada tiempo de respuesta recién capturado, simplemente incrementa un contador para el cubo en el que cae. Para estimar el percentil n-ésimo, todo lo que se necesita es sumar contadores hasta que la suma exceda n por ciento del total.

Este enfoque solo requiere 8 bytes por cubeta, lo que permite rastrear 128 cubos con 1K de memoria. Más que suficiente para analizar los tiempos de respuesta de una aplicación web utilizando una granularidad de 50 ms).

Como ejemplo, aquí hay un gráfico de Google que he creado a partir de 1 hora de datos capturados (usando 60 contadores con 200ms por cubo):

tiempos de respuesta http://j.mp/3bTf36

Bien, ¿verdad? :) Lee más en mi blog .

Creo que hay muchos buenos algoritmos aproximados para este problema. Un buen enfoque de primer corte es simplemente usar una matriz de tamaño fijo (digamos 1K de datos). Arregle alguna probabilidad p. Para cada solicitud, con probabilidad p, escriba su tiempo de respuesta en la matriz (reemplazando el tiempo más antiguo allí). Como la matriz es un submuestreo de la transmisión en vivo y como el submuestreo preserva la distribución, al hacer las estadísticas en esa matriz, obtendrá una aproximación de las estadísticas de la transmisión en vivo completa.

Este enfoque tiene varias ventajas: no requiere información a priori y es fácil de codificar. Puede construirlo rápidamente y determinar experimentalmente, para su servidor particular, en qué punto el crecimiento del buffer tiene un efecto insignificante en la respuesta. Ese es el punto donde la aproximación es suficientemente precisa.

Si encuentra que necesita demasiada memoria para brindarle estadísticas que sean lo suficientemente precisas, entonces deberá profundizar más. Las buenas palabras clave son: "flujo de computación", "estadísticas de flujo" y, por supuesto, "percentiles". También puedes probar el enfoque de "ira y maldiciones".

Pruebe el algoritmo simple definido en el documento "Procedimiento secuencial para la estimación simultánea de varios percentiles" (Raatikainen). Es rápido, requiere 2 * m + 3 marcadores (para m percentiles) y tiende a una aproximación precisa rápidamente.

Si desea mantener el uso de la memoria constante a medida que obtiene más y más datos, entonces tendrá que resample a resample esos datos de alguna manera. Eso implica que debe aplicar algún tipo de esquema de rebinning . Puede esperar hasta que adquiera una cierta cantidad de entradas sin procesar antes de comenzar el reenganche, pero no puede evitarlo por completo.

Entonces, su pregunta realmente es: "¿Cuál es la mejor forma de agrupar dinámicamente mis datos"? Hay muchos enfoques, pero si quiere minimizar sus suposiciones sobre el rango o distribución de valores que puede recibir, entonces un enfoque simple es promediar sobre cubos de tamaño fijo k , con anchuras logarítmicamente distribuidas. Por ejemplo, digamos que desea mantener 1000 valores en la memoria al mismo tiempo. Elija un tamaño para k , digamos 100. Elija su resolución mínima, digamos 1ms. Entonces

El primer cubo trata con valores entre 0-1 ms (ancho = 1 ms)
Segundo cubo: 1-3ms (w = 2ms)
Tercer cubo: 3-7ms (w = 4ms)
Cuarto cubo: 7-15ms (w = 8ms)
...
Décimo cubo: 511-1023ms (w = 512ms)

Este tipo de enfoque de log-scaled de log-scaled es similar a los sistemas de fragmentación utilizados en algoritmos de tabla hash , utilizados por algunos sistemas de archivos y algoritmos de asignación de memoria. Funciona bien cuando sus datos tienen un amplio rango dinámico.

A medida que ingresan nuevos valores, puede elegir cómo desea volver a muestrear, según sus requisitos. Por ejemplo, puede rastrear un promedio móvil , usar un método para el first-in-first-out entrar , o algún otro método más sofisticado. Ver el algoritmo de Kademlia para un enfoque (utilizado por Bittorrent ).

En última instancia, rebinning debe perder cierta información. Sus elecciones con respecto al binning determinarán los detalles de qué información se pierde. Otra forma de decir esto es que el almacenamiento de memoria de tamaño constante implica una compensación entre el rango dinámico y la fidelidad del muestreo ; cómo hacer esa compensación depende de usted, pero al igual que cualquier problema de muestreo, no hay forma de evitar este hecho básico.

Si realmente está interesado en los pros y los contras, entonces ninguna respuesta en este foro puede ser suficiente. Deberías considerar la teoría del muestreo . Hay una gran cantidad de investigaciones disponibles sobre este tema.

Por lo que vale, sospecho que los tiempos de su servidor tendrán un rango dinámico relativamente pequeño, por lo que una escala más relajada para permitir un mayor muestreo de valores comunes puede proporcionar resultados más precisos.

Editar : para responder a su comentario, aquí hay un ejemplo de un algoritmo de agrupamiento simple.

Almacena 1000 valores, en 10 contenedores. Por lo tanto, cada contenedor tiene 100 valores. Supongamos que cada contenedor se implementa como una matriz dinámica (una ''lista'', en términos de Perl o Python).
Cuando entra un nuevo valor:
- Determine en qué contenedor se debe almacenar, de acuerdo con los límites de contenedores que ha elegido.
- Si el contenedor no está lleno, agregue el valor a la lista de bin.
- Si el contenedor está lleno, elimine el valor en la parte superior de la lista del contenedor y anexe el nuevo valor al final de la lista del contenedor. Esto significa que los valores antiguos se eliminan con el tiempo.
Para encontrar el percentil 90, clasifique el recipiente 10. El percentil 90 es el primer valor en la lista ordenada (elemento 900/1000).

Si no le gusta tirar los valores antiguos, puede implementar algún esquema alternativo para usar en su lugar. Por ejemplo, cuando un contenedor se llena (alcanza los 100 valores, en mi ejemplo), puede tomar el promedio de los 50 elementos más antiguos (es decir, los primeros 50 en la lista), descartar esos elementos y luego agregar el nuevo elemento promedio a el contenedor, dejándolo con un contenedor de 51 elementos que ahora tiene espacio para contener 49 nuevos valores. Este es un simple ejemplo de rebinning.

Otro ejemplo de rebinning es la downsampling ; tirando cada 5to valor en una lista ordenada, por ejemplo.

Espero que este ejemplo concreto ayude. El punto clave que hay que quitar es que hay muchas maneras de lograr un algoritmo de envejecimiento de la memoria constante; solo usted puede decidir qué es satisfactorio según sus requisitos.

Utilice una matriz dinámica T [] de enteros grandes o algo donde T [n] cuente el número de veces que el tiempo de respuesta fue n milisegundos. Si realmente está haciendo estadísticas en una aplicación de servidor, posiblemente los tiempos de respuesta de 250 ms sean su límite absoluto de todos modos. De modo que su 1 KB contiene un entero de 32 bits por cada ms entre 0 y 250, y usted tiene espacio libre para una bandeja de desbordamiento. Si quieres algo con más contenedores, ve con números de 8 bits para 1000 contenedores, y en el momento en que un contador se desborde (es decir, la 256ª solicitud en ese tiempo de respuesta) cambias los bits en todos los contenedores por 1. (reduciendo a la mitad el valor de todos los contenedores). Esto significa que ignora todos los contenedores que capturan menos de 1/127 de los retrasos que atrapa el contenedor más visitado.

Si realmente, realmente necesitas un conjunto de contenedores específicos, te sugiero usar el primer día de solicitudes para crear un conjunto fijo razonable de contenedores. Cualquier cosa dinámica sería bastante peligrosa en una aplicación viva y sensible al rendimiento. Si eliges esa ruta, es mejor que sepas lo que estás haciendo, o un día te llamarán para explicar por qué tu rastreador de estadísticas está consumiendo 90% de CPU y 75% de memoria en el servidor de producción.

En cuanto a las estadísticas adicionales: para la media y la varianza existen algunos buenos algoritmos recursivos que ocupan muy poca memoria. Estas dos estadísticas pueden ser útiles en sí mismas para muchas distribuciones porque el teorema del límite central establece que las distribuciones que surgen de un número suficientemente grande de variables independientes se aproximan a la distribución normal (que está completamente definida por la media y la varianza) que puede usar una de las pruebas de normalidad en la última N (donde N es suficientemente grande pero está restringida por los requisitos de memoria) para monitorear si todavía se cumple la suposición de normalidad.