Centiles de capture de données en direct

Je recherche un algorithme qui détermine les centiles pour la capture de données en direct.

Par exemple, considérez le développement d’une application serveur.

Le serveur peut avoir les temps de réponse suivants: 17 ms 33 ms 52 ms 60 ms 55 ms etc.

Il est utile de rapporter le temps de réponse du 90ème percentile, le temps de réponse du 80ème percentile, etc.

L’algorithme naïf consiste à insérer chaque temps de réponse dans une liste. Lorsque des statistiques sont demandées, sortingez la liste et obtenez les valeurs appropriées.

Les utilisations de mémoire évoluent linéairement avec le nombre de requêtes.

Existe-t-il un algorithme qui génère des statistiques de approximation “approximatives” compte tenu de l’utilisation limitée de la mémoire? Par exemple, supposons que je veuille résoudre ce problème de manière à traiter des millions de requêtes, mais que je ne souhaite utiliser qu’un seul kilo-octet de mémoire pour le suivi des centiles (la suppression des anciennes requêtes n’est pas une option être pour toutes les demandes).

Exiger également qu’il n’y ait pas de connaissance a priori de la dissortingbution. Par exemple, je ne souhaite pas spécifier de plages de compartiments à l’avance.

Je crois qu’il existe de nombreux algorithmes approximatifs pour ce problème. Une bonne approche consiste à utiliser un tableau de taille fixe (par exemple, 1 Ko de données). Corrige une probabilité p. Pour chaque requête, avec probabilité p, écrivez son temps de réponse dans le tableau (en remplaçant le temps le plus ancien). Étant donné que le tableau est un sous-échantillonnage du stream en direct et que le sous-échantillonnage conserve la dissortingbution, effectuer les statistiques sur ce tableau vous donnera une approximation des statistiques du stream complet en direct.

Cette approche présente plusieurs avantages: elle ne nécessite aucune information a priori et est facile à coder. Vous pouvez le construire rapidement et déterminer expérimentalement, pour votre serveur particulier, à quel point la croissance du tampon n’a qu’un effet négligeable sur la réponse. C’est le point où l’approximation est suffisamment précise.

Si vous trouvez que vous avez besoin de trop de mémoire pour vous donner des statistiques suffisamment précises, vous devrez creuser davantage. Les bons mots-clés sont: “stream computing”, “stream statistics”, et bien sûr “percentiles”. Vous pouvez également essayer l’approche de “ire and curses”.

Si vous souhaitez conserver l’utilisation de la mémoire constante lorsque vous recevez de plus en plus de données, vous devrez rééchantillonner ces données d’une manière ou d’une autre. Cela implique que vous devez appliquer une sorte de système de rebinning . Vous pouvez attendre d’acquérir une certaine quantité d’entrées brutes avant de commencer le rebinning, mais vous ne pouvez pas l’éviter complètement.

Donc, votre question demande vraiment “quel est le meilleur moyen de regrouper dynamicment mes données”? Il y a beaucoup d’approches, mais si vous voulez minimiser vos hypothèses sur la plage ou la dissortingbution des valeurs que vous pouvez recevoir, une approche simple consiste à faire la moyenne sur des compartiments de taille fixe k , avec des largeurs dissortingbuées logarithmiquement. Par exemple, supposons que vous souhaitiez stocker 1000 valeurs en mémoire à la fois. Choisissez une taille pour k , par exemple 100. Choisissez votre résolution minimale, par exemple 1ms. alors

  • Le premier compartiment traite des valeurs entre 0-1ms (width = 1ms)
  • Deuxième seau: 1-3ms (w = 2ms)
  • Troisième seau: 3-7ms (w = 4ms)
  • Quasortingème seau: 7-15ms (w = 8ms)
  • Dixième seau: 511-1023ms (w = 512ms)

Ce type d’approche log-scaled est similaire aux systèmes de fragmentation utilisés dans les algorithmes de table de hachage , utilisés par certains systèmes de fichiers et algorithmes d’allocation de mémoire. Cela fonctionne bien lorsque vos données ont une grande plage dynamic.

À mesure que de nouvelles valeurs entrent, vous pouvez choisir la méthode de rééchantillonnage en fonction de vos besoins. Par exemple, vous pouvez suivre une moyenne mobile , utiliser une méthode « premier entré , premier sorti» ou une autre méthode plus sophistiquée. Voir l’algorithme de Kademlia pour une approche (utilisé par Bittorrent ).

En fin de compte, le rebinning doit vous perdre certaines informations. Vos choix concernant le regroupement détermineront les spécificités des informations perdues. Une autre façon de le dire est que la mémoire de taille constante implique un compromis entre la plage dynamic et la fidélité d’échantillonnage ; comment vous faites ce compromis est à vous, mais comme tout problème d’échantillonnage, il n’y a pas de contourner ce fait de base.

Si vous êtes vraiment intéressé par le pour et le contre, alors aucune réponse sur ce forum ne peut suffire. Vous devriez examiner la théorie de l’échantillonnage . De nombreuses recherches sur ce sujet sont disponibles.

Pour ce que cela vaut, je pense que la durée de fonctionnement de votre serveur aura une plage dynamic relativement réduite. Par conséquent, une mise à l’échelle plus souple pour permettre un échantillonnage plus élevé des valeurs communes peut fournir des résultats plus précis.

Edit : Pour répondre à votre commentaire, voici un exemple d’un algorithme de binning simple.

  • Vous stockez 1000 valeurs, dans 10 cases. Chaque bac contient donc 100 valeurs. Supposons que chaque corbeille est implémentée en tant que tableau dynamic (une liste, en termes Perl ou Python).
  • Quand une nouvelle valeur arrive:

    • Déterminez dans quel bac il doit être stocké, en fonction des limites de bac que vous avez choisies.
    • Si le bac n’est pas plein, ajoutez la valeur à la liste de bacs.
    • Si la corbeille est pleine, supprimez la valeur en haut de la liste et ajoutez la nouvelle valeur en bas de la liste. Cela signifie que les anciennes valeurs sont jetées au fil du temps.
  • Pour trouver le 90e centile, sortinger la case 10. Le 90e centile est la première valeur de la liste sortingée (élément 900/1000).

Si vous n’aimez pas jeter de vieilles valeurs, vous pouvez alors implémenter un autre schéma à utiliser. Par exemple, lorsqu’un conteneur devient plein (atteint 100 valeurs, dans mon exemple), vous pouvez prendre la moyenne des 50 éléments les plus anciens (les 50 premiers de la liste), supprimer ces éléments, puis append le nouvel élément moyen à la corbeille, vous laissant avec un bac de 51 éléments qui a maintenant de la place pour contenir 49 nouvelles valeurs. Ceci est un exemple simple de réouverture.

Un autre exemple de rebobinage est le sous- échantillonnage ; jeter toutes les 5ème valeur dans une liste sortingée, par exemple.

J’espère que cet exemple concret aide. Le point essentiel à retenir est qu’il existe de nombreuses façons de parvenir à un algorithme de vieillissement constant de la mémoire. vous seul pouvez décider de ce qui est satisfaisant compte tenu de vos besoins.

Je viens de publier un article de blog sur ce sujet . L’idée de base est de réduire l’exigence d’un calcul exact en faveur de “95% des réponses prennent 500ms-600ms ou moins” (pour tous les centiles exacts de 500ms-600ms)

Vous pouvez utiliser n’importe quel nombre de compartiments de toute taille arbitraire (par exemple, 0ms-50ms, 50ms-100ms, … tout ce qui correspond à votre cas). Normalement, cela ne devrait pas être un problème pour toutes les demandes qui dépassent un certain temps de réponse (par exemple 5 secondes pour une application Web) dans le dernier compartiment (c.-à-d.> 5000 ms).

Pour chaque nouveau temps de réponse capturé, il vous suffit d’incrémenter un compteur pour le compartiment dans lequel il se trouve. Pour estimer le centième centile, il suffit de faire la sum des compteurs jusqu’à ce que la sum dépasse n% du total.

Cette approche ne nécessite que 8 octets par compartiment, ce qui permet de suivre 128 compartiments avec 1 Ko de mémoire. Plus que suffisant pour parsingr les temps de réponse d’une application Web en utilisant une granularité de 50 ms.

À titre d’exemple, voici un graphique Google que j’ai créé à partir d’une heure de données capturées (en utilisant 60 compteurs avec 200 ms par compartiment):

temps de réponse http://j.mp/3bTf36

Nice, n’est-ce pas? 🙂 Lisez plus sur mon blog .

(Cela fait un certain temps que cette question a été posée, mais j’aimerais signaler quelques articles de recherche connexes)

Il y a eu beaucoup de recherches sur les centiles approximatifs des stream de données au cours des dernières années. Quelques articles intéressants avec des définitions d’algorithmes complètes:

  • Un algorithme rapide pour les quantiles approximatifs dans les stream de données à haut débit

  • Algorithmes déterministes spatio-temporels efficaces pour les quantiles biaisés sur les stream de données

  • Calcul efficace des quantiles biaisés sur les stream de données

Tous ces articles proposent des algorithmes avec une complexité spatiale sous-linéaire pour le calcul de percentiles approximatifs sur un stream de données.

Essayez l’algorithme simple défini dans l’article «Procédure séquentielle pour l’estimation simultanée de plusieurs centiles» (Raatikainen). Il est rapide, nécessite 2 * m + 3 marqueurs (pour les m centiles) et tend à une approximation précise rapidement.

Utilisez un tableau dynamic T [] de grands nombres entiers ou quelque chose où T [n] compte le nombre de fois où le temps de réponse était de n millisecondes. Si vous effectuez réellement des statistiques sur une application serveur, des délais de réponse de 250 ms sont votre limite absolue. Ainsi, votre 1 Ko contient un entier de 32 bits pour chaque ms entre 0 et 250, et vous avez de la place pour un bac de débordement. Si vous voulez quelque chose avec plus de cases, optez pour 8 numéros de bits pour 1000 cases, et au moment où un compteur débordera (c’est-à-dire 256ème requête à ce temps de réponse), vous décalerez les bits de 1. tous les bacs). Cela signifie que vous ne tenez pas compte de tous les emplacements qui capturent moins de 1 / 127ème des retards pris par le bac le plus visité.

Si vous avez vraiment besoin d’un ensemble de bacs spécifiques, je vous suggère d’utiliser le premier jour des demandes pour obtenir un ensemble de bacs raisonnable. Quelque chose de dynamic serait très dangereux dans une application en direct, sensible aux performances. Si vous choisissez ce chemin, vous feriez mieux de savoir ce que vous faites, ou un jour, vous allez être appelé hors du lit pour expliquer pourquoi votre outil de suivi des statistiques consum soudainement 90% de CPU et 75% de mémoire sur le serveur de production.

Comme pour les statistiques supplémentaires: Pour la moyenne et la variance, il existe de bons algorithmes récursifs qui prennent très peu de mémoire. Ces deux statistiques peuvent être utiles en elles-mêmes pour un grand nombre de dissortingbutions, car le théorème de la limite centrale indique que les dissortingbutions qui proviennent d’un nombre suffisamment grand de variables indépendantes s’approchent de la dissortingbution normale (entièrement définie par la moyenne et la variance). l’un des tests de normalité sur le dernier N (où N est suffisamment grand mais contraint par vos besoins en mémoire) pour contrôler si l’hypothèse de normalité est toujours valable.