5 ms·

Hey, this is very close to something I've been needing recently (and in Go, nonetheless). Is there any way to get a similar thing for a sliding window of a str

Hey, this is very close to something I've been needing recently (and in Go, nonetheless). Is there any way to get a similar thing for a sliding window of a stream? For example, to be able to report (estimated) 90th percentile latencies for server requests in the last 5 minutes, hour, and day.

bmizerany 13y ago
Yes. I use this for that. Query then Reset every 5 minutes.
- kingfishr 13y ago
  Oh, that'll be great! That's not quite the same as a sliding window of last 5 minutes, but it'll definitely work for my use case. (Intuitively, a sliding window seems very hard/impossible -- how do you discard old events without keeping a complete record?)
  - teraflop 13y ago
    There are other algorithms that handle the sliding-window case, e.g. http://research.microsoft.com/pubs/77611/quantiles.pdf http://research.microsoft.com/pubs/77611/quantiles.pdf But for all but the most extreme cases, it's sufficient to just keep all the values in memory until they fall out of your window. Even if you're getting 1000 requests/second, that's still only 300,000 values that you have to store.
    - bmizerany 13y ago
      There may be a way to implement this in perks/quantiles by adding another piece of metadata for the timestamp. There is a space cost for this, but it may be okay or even opt-in. Maybe I'll look into this soon. Edit: I do agree that if you're working with datasets that fit in memory, you're probably better off keeping all the samples to find your percentile and not using this package. In fact, perks will not compress for datasets under 500 values.
  - jcrites 13y ago
    I have seen continuous exponential decay applied to this problem.
- deleted 13y ago
  [deleted]
bmizerany 13y ago
I added an example for you (although not a "slidding" window): http://godoc.org/github.com/bmizerany/perks/quantile#__example_package-Window http://godoc.org/github.com/bmizerany/perks/quantile#__examp...

bmizerany 13y ago

Yes. I use this for that. Query then Reset every 5 minutes.

kingfishr 13y ago
Oh, that'll be great! That's not quite the same as a sliding window of last 5 minutes, but it'll definitely work for my use case. (Intuitively, a sliding window seems very hard/impossible -- how do you discard old events without keeping a complete record?)
- teraflop 13y ago
  There are other algorithms that handle the sliding-window case, e.g. http://research.microsoft.com/pubs/77611/quantiles.pdf http://research.microsoft.com/pubs/77611/quantiles.pdf But for all but the most extreme cases, it's sufficient to just keep all the values in memory until they fall out of your window. Even if you're getting 1000 requests/second, that's still only 300,000 values that you have to store.
  - bmizerany 13y ago
    There may be a way to implement this in perks/quantiles by adding another piece of metadata for the timestamp. There is a space cost for this, but it may be okay or even opt-in. Maybe I'll look into this soon. Edit: I do agree that if you're working with datasets that fit in memory, you're probably better off keeping all the samples to find your percentile and not using this package. In fact, perks will not compress for datasets under 500 values.
- jcrites 13y ago
  I have seen continuous exponential decay applied to this problem.
deleted 13y ago
[deleted]

bmizerany 13y ago

I added an example for you (although not a "slidding" window): http://godoc.org/github.com/bmizerany/perks/quantile#__example_package-Window http://godoc.org/github.com/bmizerany/perks/quantile#__examp...