Centiles de capture de données en direct

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

Question

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

Par exemple, considérons le développement d'une application serveur.

Le serveur peut avoir des temps de réponse comme suit: 17 ms 33 ms 52 ms 60 ms 55 ms etc.

Il est utile de signaler le temps de réponse 90e percentile, le temps de réponse 80e percentile, etc.

L'algorithme naïf consiste à insérer chaque temps de réponse dans une liste. Lorsque les statistiques sont demandées, trier la liste et obtenir les valeurs aux positions appropriées.

échelles usages de la mémoire de façon linéaire avec le nombre de demandes.

Y at-il un algorithme qui donne des statistiques percentile « approximatives » étant donné l'utilisation de la mémoire limitée? Par exemple, disons que je veux résoudre ce problème d'une manière que je traite des millions de demandes mais que vous voulez utiliser uniquement dire un kilo-octet de mémoire pour percentile de suivi (en rejetant le suivi des anciennes demandes ne sont pas une option puisque les centiles sont censés être pour toutes les demandes).

exige également qu'il n'y a pas une connaissance a priori de la distribution. Par exemple, je ne veux pas préciser les gammes de seaux à l'avance.

Était-ce utile?

La solution

Je crois qu'il ya beaucoup de bons algorithmes approximatifs pour ce problème. Une bonne approche première coupe est d'utiliser simplement un tableau de taille fixe (par exemple 1K valeur de données). Fixer une certaine probabilité p. Pour chaque demande, avec une probabilité p, écrire son temps de réponse dans la matrice (en remplaçant le temps le plus ancien en bas). Étant donné que le tableau est un sous-échantillonnage du flux en direct et depuis la distribution conserve sous-échantillonnage, faire les statistiques sur ce tableau vous donnera une approximation des statistiques du plein, en direct.

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

Si vous trouvez que vous avez besoin trop de mémoire pour vous donner des statistiques qui sont assez précis, vous devrez creuser plus loin. Les bons mots-clés sont: « stream computing », « les statistiques de flux », et bien sûr « centiles ». Vous pouvez également essayer « ire et malédictions » approche.

Autres conseils

Si vous voulez garder la constante utilisation de la mémoire que vous obtenez de plus en plus de données, alors vous allez devoir resample que les données en quelque sorte. Cela implique que vous devez appliquer une sorte de système réensilant. Vous pouvez attendre jusqu'à ce que vous acquérir une certaine quantité des matières premières avant de commencer le réensilant, mais vous ne pouvez pas éviter complètement.

Votre question est vraiment demander « quelle est la meilleure façon de binning dynamiquement mes données »? Il y a beaucoup d'approches, mais si vous voulez réduire vos hypothèses sur la plage ou la distribution de valeurs que vous pouvez recevoir, puis une approche simple est en moyenne par rapport aux godets de taille fixe k , avec des largeurs logarithmiquement distribués . Par exemple, disons que vous voulez tenir 1000 valeurs en mémoire à un moment donné. Choisissez une taille pour k , disent 100. Choisissez le votre résolution minimale, disent 1ms. Ensuite,

  • Le premier godet porte sur des valeurs comprises entre 0-1ms (width = 1ms)
  • Godet: 1-3ms (w = 2ms)
  • Godet tiers: 3-7ms (w = 4 ms)
  • Godet Quatrième: 7-15ms (w = 8ms)
  • ...
  • Godet dixième: 511-1023ms (w = 512ms)

Ce type de approche log-échelle est similaire aux systèmes utilisés dans chunking algorithmes de table de hachage , utilisée par certains systèmes de fichiers et des algorithmes d'allocation de mémoire. Il fonctionne bien lorsque vos données dispose d'une grande plage dynamique.

Comme de nouvelles valeurs viennent, vous pouvez choisir comment vous voulez rééchantillonner, en fonction de vos besoins. Par exemple, vous pouvez suivre un mouvement moyenne, utilisez un first-in-first-out , ou une autre méthode plus sophistiquée. Voir l'algorithme Kademlia pour une approche (utilisée par Bittorrent ).

En fin de compte, vous perdez doit réarrangement des informations. Vos choix concernant la binning détermineront les détails de ce que l'information est perdue. Une autre façon de le dire est que le magasin de mémoire de taille constante implique un compromis entre la gamme dynamique ; comment vous faites ce compromis est à vous, mais comme un problème d'échantillonnage, il n'y a pas contourner ce fait fondamental.

Si vous êtes vraiment intéressé par les avantages et les inconvénients, aucune réponse sur ce forum peut espérer être suffisant. Vous devriez regarder dans la théorie de l'échantillonnage . Il y a une énorme quantité de recherches sur ce sujet disponible.

Pour ce que ça vaut, je pense que votre temps de serveur ont une plage dynamique relativement faible, donc une échelle plus détendue pour permettre un échantillonnage plus élevé de valeurs communes peut fournir des résultats plus précis.

Modifier . Pour répondre à votre commentaire, voici un exemple d'un algorithme simple de binning

  • Vous stocker 1000 valeurs, dans 10 bacs. Chaque bac peut contenir donc 100 valeurs. On suppose chaque bac est utilisé comme une matrice dynamique (une « liste », en termes Perl ou Python).

  • Quand une nouvelle valeur entre en jeu:

    • Déterminez quel bac il doit être stocké dans, sur la base des limites de bin que vous avez choisi.
    • Si le bac est pas plein, ajoutez la valeur à la liste bin.
    • Si le bac est plein, supprimez la valeur en haut de la liste bin et ajoutez la nouvelle valeur au bas de la liste bin. Cettemoyens anciennes valeurs sont jetés au fil du temps.

  • Pour le 90e percentile, sorte bin 10. Le 90e centile est la première valeur de la liste triée (élément 900/1000).

Si vous ne l'aimez pas jeter les anciennes valeurs, alors vous pouvez mettre en œuvre un certain schéma alternatif à utiliser à la place. Par exemple, lorsqu'un bac est plein (atteint 100 valeurs, dans mon exemple), vous pouvez prendre la moyenne des plus anciens 50 éléments (par exemple les 50 premiers dans la liste), jeter ces éléments, puis ajouter le nouvel élément moyen de le bac, vous laissant avec un bac de 51 éléments qui a maintenant l'espace pour contenir 49 nouvelles valeurs. Ceci est un exemple simple de réensilant.

Un autre exemple de réensilant est downsampling; jeter chaque valeur 5 dans une liste triée, par exemple.

J'espère que cet exemple concret aide. Le point clé pour enlever est qu'il ya beaucoup de façons de réaliser un algorithme de vieillissement mémoire constante; vous seul pouvez décider ce qui est satisfaisant compte tenu de vos besoins.

Je viens de publier un blog sur ce sujet . L'idée de base est de réduire l'exigence d'un calcul exact en faveur de « 95% pour cent des réponses prendre 500ms-600ms ou moins » (pour tous les centiles exactes de 500ms-600ms)

Vous pouvez utiliser un certain nombre de seaux de toute taille arbitraire (par exemple 0ms-50ms, 50ms-100ms, ... juste quelque chose qui correspond à votre usecase). Normalement, il ne devrait pas être un problème, mais toutes les demandes qui dépassent un certain temps de réponse (par exemple 5 secondes pour une application Web) dans le dernier seau (à savoir> 5000ms).

Pour chaque temps de réponse nouvellement capturé, vous pouvez tout simplement incrémenter un compteur pour le seau tombe dans. Pour estimer le n-ième percentile, tout ce qui est nécessaire est résumé des compteurs jusqu'à ce que la somme est supérieure pour cent n du total.

Cette approche ne nécessite que 8 octets par seau, ce qui permet de suivre 128 seaux avec 1K de mémoire. Plus que suffisant pour analyser les temps de réponse d'une application Web en utilisant une granularité de 50ms).

À titre d'exemple, voici une Google Chart J'ai créé de 1 heure des données saisies (en utilisant 60 compteurs à 200ms par seau):

Nice, est-ce pas? :) En savoir plus sur mon blog .

(Il a été tout à fait un certain temps que cette question a été posée, mais je voudrais souligner quelques documents de recherche connexes)

Il y a eu une quantité importante de la recherche sur les centiles approximatives des flux de données au cours des dernières années. Quelques articles intéressants avec des définitions de l'algorithme complet:

Tous ces documents proposent des algorithmes avec la complexité de l'espace sous-linéaire pour le calcul des percentiles approximatives sur un flux de données.

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

Utilisez un tableau dynamique T [] de grands entiers ou quelque chose où T [n] compte le numer de fois le temps de réponse était n millisecondes. Si vous êtes vraiment en train de faire des statistiques sur une application de serveur, puis peut-être 250 ms les temps de réponse sont votre limite absolue de toute façon. Ainsi, votre 1 KB détient un entier de 32 bits pour chaque ms entre 0 et 250, et vous avez une pièce de rechange pour un bac de trop-plein. Si vous voulez quelque chose avec plus de bacs, aller avec 8 numéros de bits pour 1000 bacs, et le moment un compteur provoque un débordement (c.-à-demande 256e à ce temps de réponse) vous décalez les bits dans tous les bacs par 1. (réduisant de moitié la valeur tous les bacs). Cela signifie que vous ignorer tous les bacs qui capturent moins de 1 / 127e des retards les plus visités prises bin.

Si vous avez vraiment besoin d'un ensemble de casiers spécifiques que je suggère d'utiliser le premier jour des demandes de venir avec un ensemble fixe raisonnable bacs. Tout ce que dynamique serait très dangereux dans une application en direct, sensibles aux performances. Si vous choisissez cette voie, vous feriez mieux de savoir ce que vous faites, ou un jour vous allez obtenir appelé sortir du lit pour expliquer pourquoi votre suivi statistique est en train de manger soudainement CPU 90% et 75% de mémoire sur le serveur de production.

En ce qui concerne les statistiques supplémentaires: Pour moyenne et la variance il y a quelques beaux algorithmes récursifs qui prennent très peu de mémoire. Ces deux statistiques peuvent être en eux-mêmes assez utile pour beaucoup de distributions parce que le théorème central limite les états de que les distributions que découlant d'un nombre suffisamment important de variables indépendantes approchent de la distribution normale (qui est entièrement défini par la moyenne et la variance), vous pouvez utiliser l'un des

Non affilié à StackOverflow
scroll top