Percentis de captura Live Data

Question

Eu estou procurando um algoritmo que determina percentis para captura de dados ao vivo.

Por exemplo, considere o desenvolvimento de uma aplicação de servidor.

O servidor pode ter tempos de resposta da seguinte forma: 17 ms 33 ms 52 ms 60 ms 55 ms etc.

É útil para relatar o 90º percentil tempo de resposta, 80º percentil tempo de resposta, etc.

O algoritmo ingênuo é inserir cada tempo de resposta em uma lista. Quando as estatísticas são solicitados, uma espécie da lista e obter os valores para as posições adequadas.

Memória usages escalas linearmente com o número de pedidos.

Existe um algoritmo que os rendimentos "aproximada" percentil estatísticas dado o uso de memória limitada? Por exemplo, digamos que eu quiser resolver este problema de uma forma que eu processar milhões de pedidos, mas só quer usar dizer um kilobyte de memória para o percentil de rastreamento (descartando o rastreamento para solicitações de idade não é uma opção desde os percentis são supostos ser para todos os pedidos).

Também exigem que não há um conhecimento a priori da distribuição. Por exemplo, eu não quero especificar quaisquer gamas de baldes antes do tempo.

Answer 1

Eu acredito que há muitos bons algoritmos aproximados para este problema. Uma boa abordagem de primeira corte é simplesmente usar uma matriz de tamanho fixo (digamos 1K no valor de dados). Corrigir alguma probabilidade p. Para cada pedido, com probabilidade p, escrever seu tempo de resposta para a matriz (que substitui o tempo mais antigo de lá). Desde a matriz é um subsampling da transmissão ao vivo e desde subamostragem preserva a distribuição, fazendo as estatísticas sobre essa matriz lhe dará uma aproximação das estatísticas da cheia, transmissão ao vivo.

Esta abordagem tem várias vantagens: ela não exige nenhuma informação a priori, e é fácil de código. Você pode construí-lo rapidamente e determinar experimentalmente, para o seu servidor em particular, em que ponto o crescimento do tampão tem apenas um efeito negligenciável sobre a resposta. Esse é o ponto onde a aproximação é suficientemente preciso.

Se você achar que precisa de muita memória para dar-lhe estatísticas que são bastante preciso, então você vai ter que cavar ainda mais. Boas palavras-chave são: "fluxo de computação", "estatísticas de fluxo", e naturalmente "percentis". Você também pode tentar abordagem "ire e maldições" 's.

Answer 2

Se você quiser manter o constante uso da memória como você obtém mais e mais dados, então você vai ter que resample que os dados de alguma forma. Isso implica que você deve aplicar algum tipo de rebinning esquema . Você pode esperar até que você adquire uma certa quantidade de matérias-primas antes de iniciar o rebinning, mas você não pode evitá-lo por completo.

Assim, a pergunta que realmente está perguntando "o que é a melhor maneira de binning dinamicamente meus dados"? Há muitas abordagens, mas se você quiser minimizar suas suposições sobre a faixa ou distribuição de valores que você pode receber, em seguida, uma abordagem simples é média ao longo de baldes de tamanho fixo k , com larguras logaritmicamente distribuídos . Por exemplo, digamos que você quer segurar 1000 valores na memória a qualquer momento. Escolha um tamanho para k , diz 100. Escolha a sua resolução mínima, dizem 1ms. Então

• A primeira trata de balde com valores entre 0-1ms (largura = 1 ms)
• Em segundo lugar balde: 1-3ms (W = 2ms)
• Em terceiro lugar balde: 3-7ms (W = 4ms)
• Quarta balde: 7-15ms (W = 8ms)
• ...
• balde Décima: 511-1023ms (w = 512ms)

Este tipo de abordagem log-escalado é semelhante aos sistemas chunking utilizados em algoritmos de hash tabela , usado por alguns sistemas de arquivos e algoritmos de alocação de memória. Ele funciona bem quando os seus dados tem um grande alcance dinâmico.

À medida que novos valores entram, você pode escolher como você deseja resample, dependendo de suas necessidades. Por exemplo, você poderia controlar uma média movimento, use uma first-in-first-out , ou algum outro método mais sofisticado. Veja a Kademlia algoritmo para uma abordagem (usado por Bittorrent ).

Em última análise, rebinning deve perder algumas informações. Suas escolhas em relação à binning irá determinar os detalhes do que a informação é perdida. Outra maneira de dizer isso é que o armazenamento de memória tamanho constante implica um trade-off entre faixa dinâmica e o amostragem fidelidade ; como você fazer essa trade-off é com você, mas como qualquer problema de amostragem, não há como contornar esse fato básico.

Se você está realmente interessado nos prós e contras, então nenhuma resposta sobre este fórum pode ter esperança de ser suficiente. Você deve olhar para amostragem teoria . Há uma enorme quantidade de pesquisas sobre este tema disponível.

Por que vale a pena, eu suspeito que seus tempos de servidores terá um relativamente pequeno alcance dinâmico, por isso uma escala mais relaxado para permitir maior amostragem de valores comuns podem proporcionar resultados mais precisos.

Editar :. Para responder seu comentário, aqui está um exemplo de um algoritmo de binning simples

• Você armazenar 1000 valores, em 10 caixas. Portanto, cada compartimento tem 100 valores. Suponha que cada bin é implementada como uma matriz dinâmica (a 'lista', em termos Perl ou Python).

• Quando um novo valor vem em:

  • Determinar qual bin ele deve ser armazenado em, com base nos limites de lixo que você escolheu.
  • Se o bin não está cheio, acrescentar o valor à lista bin.
  • Se a caixa está cheia, remova o valor no topo da lista bin, e anexar o novo valor para a parte inferior da lista bin. Estameios valores antigos são jogados fora ao longo do tempo.

• Para encontrar o percentil 90, tipo bin 10. O percentil 90 é o primeiro valor na lista ordenada (elemento 900/1000).

Se você não gosta de jogar fora velhos valores, então você pode implementar algum esquema alternativo para usar em vez. Por exemplo, quando uma bin fica cheio (chega a 100 valores, no meu exemplo), você poderia tomar a média dos mais antigos 50 elementos (ou seja, os 50 primeiros na lista), descarte desses elementos, e em seguida, acrescentar o novo elemento média o bin, deixando-o com um escaninho de 51 elementos que agora tem espaço para armazenar 49 novos valores. Este é um exemplo simples de rebinning.

Outro exemplo de rebinning é downsampling ; jogando fora cada 5 valor em uma lista ordenada, por exemplo.

Espero que este exemplo concreto ajuda. O ponto-chave para tirar é que existem muitas maneiras de alcançar uma constante memória algoritmo de envelhecimento; só você pode decidir o que é satisfatório dado suas necessidades.

Answer 3

Eu apenas publicou um blog sobre este tema . A idéia básica é a de reduzir a necessidade de um cálculo exato em favor de "95% por cento das respostas tomar 500ms-600ms ou menos" (para todos os percentis exatas de 500ms-600ms)

Você pode usar qualquer número de baldes de qualquer tamanho arbitrário (por exemplo 0ms-50ms, 50ms-100ms, ... qualquer coisa que se encaixa o seu usecase). Normalmente, ele não deve ser um problema para mas todas as solicitações que excedam um determinado tempo de resposta (por exemplo, 5 segundos para uma aplicação web) no último balde (ou seja,> 5000 ms).

Para cada tempo de resposta recém-capturado, você simplesmente incrementar um contador para o balde cai em. Para estimar o n-percentil, tudo que é necessário é resumindo contadores até que a soma ultrapassa n por cento do total.

Esta abordagem exige apenas oito bytes por balde, permitindo que a faixa 128 baldes com 1K de memória. Mais do que suficiente para analisar os tempos de resposta de uma aplicação web utilizando uma granularidade de 50ms).

Como um exemplo, aqui é um Google Chart eu criei de uma hora de dados capturados (utilizando 60 contadores com 200ms por balde):

Nice, não é? :) Leia mais no meu blog .

Answer 4

(Tem sido algum tempo desde que esta pergunta foi feita, mas eu gostaria de apontar alguns trabalhos de pesquisa relacionados)

Tem havido uma quantidade significativa de pesquisas sobre percentis aproximadas de fluxos de dados nos últimos anos. Alguns trabalhos interessantes com definições algoritmo completo:

• um algoritmo rápido para aproximado quantiles em dados de alta velocidade córregos

• Space-e tempo- eficientes algoritmos determinísticos para quantiles tendenciosas sobre fluxos de dados

• eficaz de quantiles tendenciosos dados sobre fluxos

Todos estes papéis propor algoritmos com sub-linear complexidade espaço para o cálculo de percentis aproximados mais de um fluxo de dados.

Answer 5

Tente o algoritmo simples definido no jornal “Procedimento sequencial para simultânea Estimativa de vários percentis” (Raatikainen). É rápido, requer 2 * m + 3 marcadores (para m percentis) e tende a uma aproximação precisa rapidamente.

Answer 6

Use uma matriz dinâmica T [] de grandes inteiros ou algo onde T [n] conta o numer de vezes que o tempo de resposta foi n milissegundos. Se você realmente está fazendo estatísticas em um aplicativo de servidor, em seguida, possivelmente, 250 tempos de resposta ms são o seu limite absoluto de qualquer maneira. Portanto, o seu 1 KB detém um 32 bits inteiros para cada ms entre 0 e 250, e você tem algum espaço de sobra para uma bandeja de estouro. Se você quiser algo com mais bandejas, ir com 8 números de bits para 1000 caixas, e no momento um contador iria transbordar (ie pedido 256 naquele tempo de resposta) você muda os bits em todas as bandejas para baixo em 1. (efetivamente reduzir para metade o valor em todas as bandejas). Isto significa que você ignorar todas as caixas que captam menos de 1/127 dos atrasos que o mais visitados capturas lixo.

Se você realmente precisa de um conjunto de bandejas específicas que eu sugiro usar o primeiro dia de pedidos para chegar a um conjunto fixo razoável de caixas. Qualquer coisa dinâmica seria muito perigoso em uma aplicação sensível ao vivo, performance. Se você escolher esse caminho é melhor você souber o que fazer, ou um dia você vai obter chamado para fora da cama para explicar por que suas estatísticas rastreador é subitamente comer 90% de CPU e memória de 75% no servidor de produção.

Quanto a estatísticas adicionais: Para média e variância há algumas agradáveis ??algoritmos recursivos que ocupam muito pouco memória. Estas duas estatísticas pode ser bastante útil em si mesmos para um monte de distribuições porque os estados do Teorema do Limite Central que as distribuições que que surgem a partir de um número suficientemente grande de variáveis ??independentes aproximar a distribuição normal (que é totalmente definido pela média e variância), pode utilizar um dos testes de normalidade no último N (onde N suficientemente grande, mas limitado por seus requisitos de memória) para monitorar wether a suposição de normalidade ainda se mantém.