Non-uniform histogram

[arthurprs]

Current histogram is a great uniform histogram but it's a poor metrics histogram most of the time, as the first data point has the same weight as the most recent data point.

This lib should provide some sort of decaying histogram as well.

[posix4e]

@arthurprs stupid question, any reason why we just wouldn't use two histograms, each half the size. One for short term one for long. Can you provide some examples?

[posix4e]

@brayniac might have some opinions here

[brayniac]

@arthurprs - I'm curious if you know of a stats library that handles histograms that way. What I've seen is that histograms are latched over some intergation window - eg record for 60s, extract data, clear histogram, record. This gives you access to the percentiles and other derived metrics for that minute. This is how I did it for my time-interval stats library (https://github.com/brayniac/tic)

[arthurprs]

My experience is probably biased but most libraries that I know provide or even default to a decaying histogram.

Java: https://github.com/dropwizard/metrics/blob/3.2-development/metrics-core/src/main/java/com/codahale/metrics/MetricRegistry.java#L525

Python: https://github.com/omergertel/pyformance/blob/master/pyformance/meters/histogram.py#L22

C#: https://github.com/Recognos/Metrics.NET/blob/2e7e3ba625298bd8dc35e577122a5285d3a50619/Src/Metrics/MetricsConfig.cs#L29

[arthurprs]

If you consider the prometheus style libraries the "decay sampling" Histograms are called Summaries instead, sort of.

[brayniac]

@arthurprs - cool! Thanks for the links. I need to do some reading before I have more to say. I'm curious to learn when decaying might be a better fit than latched.

[sfackler]

I ended up implementing a copy of Java Metric's ExponentiallyDecayingReservoir to swap out the HDR histogram that metrics uses by default - snapshots are about 100x faster in addition to having time decay. I can push it upstream if people are interested.

[arthurprs]

Please do, if you put it in GH I can cherry-pick. I'm not sure @posix4e position since he marked the crate deprecated.

[brayniac]

I wonder if this is something we should support in tic. Would appreciate benchmarks/links.

[arthurprs]

I posted links up thread.

[brayniac]

@arthurprs - sorry, links/benches request was for @sfackler - was replying from mobile =)

[sfackler]

Here's the histogram implementation: https://gist.github.com/sfackler/2ea5c5b2ee0cc1447b9ae415292adaba

I don't have the exact code I used for the benchmark comparison, but it was IIRC just loading up an HDR Histogram and the histogram in the gist with default settings, filling them with 0..1000 and then generating a snapshot (count, min, max, mean, stddev, p50, p75, p95, p98, p99, p999) in the Bencher::iter closure. The average times were 3,544,088 ns for HDR vs 36,804 ns for the new one.

[posix4e]

Neat I'd be willing to take it as a pr

…

On Thu, May 25, 2017 at 09:06 Steven Fackler ***@***.***> wrote: Here's the histogram implementation: https://gist.github.com/sfackler/2ea5c5b2ee0cc1447b9ae415292adaba I don't have the exact code I used for the benchmark comparison, but it was IIRC just loading up an HDR Histogram and the histogram in the gist with default settings, filling them with 0..1000 and then generating a snapshot (count, min, max, mean, stddev, p50, p75, p95, p98, p99, p999) in the Bencher::iter closure. The average times were 3,544,088 ns for HDR vs 36,804 ns for the new one. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#81 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAxN29DvoEEYxLpuitnfjJtz0NDm6WW_ks5r9ab5gaJpZM4NgOly> .

[sfackler]

Update times are a bit slower since it has to pull the current time but it's still decently fast - maybe 100ns? Don't have hard numbers for that written down anywhere.

[sfackler]

Cool, I'll push one up today.

[brayniac]

@sfackler - thanks. I hacked together a quick benchmark for update operation for the decaying histogram proposed: https://github.com/brayniac/histobench

TLDR:

     Running target/release/deps/bench_decaying-c16fb48d5628f0a5

running 1 test
test decaying_increment ... bench:         119 ns/iter (+/- 9)

test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 0 filtered out

     Running target/release/deps/bench_histogram-984d88d3e7dfe1ad

running 1 test
test brayniac_increment ... bench:           7 ns/iter (+/- 0)

test result: ok. 0 passed; 0 failed; 0 ignored; 1 measured; 0 filtered out

Percentiles in my histogram crate should be fairly cheap - and ideally we can handle those kinds of things without blocking the threads we're trying to get metrics from. The cost per increment here might be too high for something like tic - 119ns limits us to no more than 10M increments/s - staying closer to 10ns allows for up to 100M/s.

EDIT: looks like calculating p90 and stddev is a lot cheaper with the proposed decaying histogram. histobench repo updated with additional coverage

[sfackler]

Oh yeah, if you have very update heavy workloads then exponential time decay is not going to work well.

[sfackler]

I published this at https://crates.io/crates/exponential-decay-histogram

[posix4e]

neat

…

On Mon, May 29, 2017, 17:43 Steven Fackler ***@***.***> wrote: I published this at https://crates.io/crates/exponential-decay-histogram — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#81 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAxN203Xt3VyVdjGyUKGxiZFSlQ5PNfLks5r-2YTgaJpZM4NgOly> .