Struct HdrHistogram

Source

pub struct HdrHistogram { /* private fields */ }

Expand description

Histogram with significant_digits of precision in [1, 5].

Implementations§

Source §

Record value, then correct for coordinated omission. Under a fixed-rate load generator, one slow operation blocks every request that should have been issued while it stalled; those requests are never sampled, so the tail reads far better than the system delivered. When value exceeds expected_interval, this backfills the samples the generator would have taken during the stall - synthetic values at value - expected_interval, value - 2*expected_interval, … down to expected_interval - so the percentiles reflect the latency those blocked requests would have seen.

This is Gil Tene’s recordValueWithExpectedInterval. expected_interval == 0 (or a value no larger than it) disables the correction, leaving this equivalent to Self::record.

Examples found in repository ?

examples/sample_app.rs (line 108)

46fn base_tick_to_trade() {
47    println!("== base: tick-to-trade latency capture ==");
48    let mut h = HdrHistogram::new(3);
49
50    // A right-skewed latency stream: most ops sit in a tight band, a small
51    // fraction spike into the tail. Deterministic xorshift so the numbers are
52    // reproducible.
53    let mut rng = 0x2545_F491_4F6C_DD1Du64;
54    let mut next = || {
55        rng ^= rng << 13;
56        rng ^= rng >> 7;
57        rng ^= rng << 17;
58        rng
59    };
60    let n = 2_000u64;
61    for i in 0..n {
62        let base = 700 + next() % 300; // 700..1000 ns steady state
63        if i % 50 == 0 {
64            h.record(4_000 + next() % 4_000); // ~2% tail spike, 4us..8us
65        } else {
66            h.record(base);
67        }
68    }
69
70    let p50 = h.value_at_percentile(0.50);
71    let p99 = h.value_at_percentile(0.99);
72    let p999 = h.value_at_percentile(0.999);
73    println!(
74        "  n={n} p50={p50}ns p99={p99}ns p999={p999}ns max={}ns",
75        h.max()
76    );
77    assert_eq!(h.count(), n, "every sample recorded");
78    assert!(
79        p50 <= 1_100,
80        "median sits in the steady-state band: p50={p50}"
81    );
82    assert!(
83        p99 >= 2_000,
84        "the 2% tail lifts p99 well past the median: p99={p99}"
85    );
86    assert!(p999 >= p99 && h.max() >= p999, "percentiles are monotone");
87
88    // The reporting surface a dashboard actually wants alongside the
89    // percentiles: the floor, the mean, the fraction inside the SLO, and what
90    // the whole thing costs in memory.
91    let within_slo = h.percentile_at_or_below_value(2_000);
92    println!(
93        "  min={}ns mean={:.0}ns within-2us={:.1}% footprint={}KB",
94        h.min(),
95        h.mean(),
96        within_slo * 100.0,
97        h.footprint_bytes() / 1024
98    );
99    assert!(within_slo > 0.9, "most ops sit inside the 2us band");
100
101    // Coordinated omission: a fixed-rate loop issues one op every 10 ns, then
102    // stalls for 1000 ns. The naive histogram sees one slow sample; the
103    // corrected one backfills the 99 requests the stall blocked.
104    let mut naive = HdrHistogram::new(3);
105    let mut corrected = HdrHistogram::new(3);
106    for _ in 0..1_000 {
107        naive.record(10);
108        corrected.record_with_expected_interval(10, 10);
109    }
110    naive.record(1_000);
111    corrected.record_with_expected_interval(1_000, 10);
112    let naive_p99 = naive.value_at_percentile(0.99);
113    let corrected_p99 = corrected.value_at_percentile(0.99);
114    println!("  coordinated omission: naive p99={naive_p99}ns, corrected p99={corrected_p99}ns");
115    assert!(
116        naive_p99 <= 20,
117        "uncorrected tail hides the stall: {naive_p99}"
118    );
119    assert!(
120        corrected_p99 >= 500,
121        "correction lifts the tail: {corrected_p99}"
122    );
123}

Source

pub fn value_at_percentile(&self, q: f64) -> u64

Value at the given quantile (0.0..=1.0). 0 if empty.

Examples found in repository ?

examples/sample_app.rs (line 70)

46fn base_tick_to_trade() {
47    println!("== base: tick-to-trade latency capture ==");
48    let mut h = HdrHistogram::new(3);
49
50    // A right-skewed latency stream: most ops sit in a tight band, a small
51    // fraction spike into the tail. Deterministic xorshift so the numbers are
52    // reproducible.
53    let mut rng = 0x2545_F491_4F6C_DD1Du64;
54    let mut next = || {
55        rng ^= rng << 13;
56        rng ^= rng >> 7;
57        rng ^= rng << 17;
58        rng
59    };
60    let n = 2_000u64;
61    for i in 0..n {
62        let base = 700 + next() % 300; // 700..1000 ns steady state
63        if i % 50 == 0 {
64            h.record(4_000 + next() % 4_000); // ~2% tail spike, 4us..8us
65        } else {
66            h.record(base);
67        }
68    }
69
70    let p50 = h.value_at_percentile(0.50);
71    let p99 = h.value_at_percentile(0.99);
72    let p999 = h.value_at_percentile(0.999);
73    println!(
74        "  n={n} p50={p50}ns p99={p99}ns p999={p999}ns max={}ns",
75        h.max()
76    );
77    assert_eq!(h.count(), n, "every sample recorded");
78    assert!(
79        p50 <= 1_100,
80        "median sits in the steady-state band: p50={p50}"
81    );
82    assert!(
83        p99 >= 2_000,
84        "the 2% tail lifts p99 well past the median: p99={p99}"
85    );
86    assert!(p999 >= p99 && h.max() >= p999, "percentiles are monotone");
87
88    // The reporting surface a dashboard actually wants alongside the
89    // percentiles: the floor, the mean, the fraction inside the SLO, and what
90    // the whole thing costs in memory.
91    let within_slo = h.percentile_at_or_below_value(2_000);
92    println!(
93        "  min={}ns mean={:.0}ns within-2us={:.1}% footprint={}KB",
94        h.min(),
95        h.mean(),
96        within_slo * 100.0,
97        h.footprint_bytes() / 1024
98    );
99    assert!(within_slo > 0.9, "most ops sit inside the 2us band");
100
101    // Coordinated omission: a fixed-rate loop issues one op every 10 ns, then
102    // stalls for 1000 ns. The naive histogram sees one slow sample; the
103    // corrected one backfills the 99 requests the stall blocked.
104    let mut naive = HdrHistogram::new(3);
105    let mut corrected = HdrHistogram::new(3);
106    for _ in 0..1_000 {
107        naive.record(10);
108        corrected.record_with_expected_interval(10, 10);
109    }
110    naive.record(1_000);
111    corrected.record_with_expected_interval(1_000, 10);
112    let naive_p99 = naive.value_at_percentile(0.99);
113    let corrected_p99 = corrected.value_at_percentile(0.99);
114    println!("  coordinated omission: naive p99={naive_p99}ns, corrected p99={corrected_p99}ns");
115    assert!(
116        naive_p99 <= 20,
117        "uncorrected tail hides the stall: {naive_p99}"
118    );
119    assert!(
120        corrected_p99 >= 500,
121        "correction lifts the tail: {corrected_p99}"
122    );
123}
124
125/// `concurrent-writes` feature: several market-data feed handlers record into
126/// one histogram from different threads with no external lock - the only
127/// contention is the per-bucket atomic increment.
128#[cfg(feature = "concurrent-writes")]
129fn concurrent_feed_handlers() {
130    use std::sync::Arc;
131    use std::thread;
132    use subms_hdr_histogram::ConcurrentHdrHistogram;
133    println!("\n== concurrent-writes: many feed handlers, one histogram ==");
134    let h = Arc::new(ConcurrentHdrHistogram::new(3));
135    let threads = 4;
136    let per_thread = 50_000u64;
137    let mut handles = vec![];
138    for _ in 0..threads {
139        let h = h.clone();
140        handles.push(thread::spawn(move || {
141            for i in 0..per_thread {
142                h.record((i % 1_000) + 500);
143            }
144        }));
145    }
146    for j in handles {
147        j.join().unwrap();
148    }
149    println!(
150        "  {} records lock-free, p99={}ns",
151        h.count(),
152        h.value_at_percentile(0.99)
153    );
154    assert_eq!(
155        h.count(),
156        threads as u64 * per_thread,
157        "no writes lost under contention"
158    );
159}
160
161/// `dual-recorder` feature: producers record continuously; a reporter thread
162/// grabs an interval snapshot on a timer by rotating the active side and
163/// draining the inactive one, never blocking the producers.
164#[cfg(feature = "dual-recorder")]
165fn dual_recorder_interval_report() {
166    use subms_hdr_histogram::DualRecorder;
167    println!("\n== dual-recorder: lock-free interval percentile report ==");
168    let rec = DualRecorder::new(3);
169    for v in 1..=500u64 {
170        rec.record(v);
171    }
172    let interval = rec.get_interval_histogram();
173    println!(
174        "  interval count={}, p99={}",
175        interval.count(),
176        interval.value_at_percentile(0.99)
177    );
178    let next = rec.get_interval_histogram();
179    assert_eq!(
180        interval.count(),
181        500,
182        "first interval captured every record"
183    );
184    assert_eq!(
185        next.count(),
186        0,
187        "the next interval starts empty after the rotate"
188    );
189}
190
191/// `merge` feature: two shards each keep their own histogram; a periodic
192/// roll-up sums one into the other for a fleet-wide percentile view. The merge
193/// is exact - identical to recording every value into a single histogram.
194#[cfg(feature = "merge")]
195fn merge_shard_rollup() {
196    use subms_hdr_histogram::merge;
197    println!("\n== merge: roll per-shard histograms into a fleet view ==");
198    let mut shard_a = HdrHistogram::new(3);
199    let mut shard_b = HdrHistogram::new(3);
200    for v in 1..=500u64 {
201        shard_a.record(v);
202    }
203    for v in 501..=1_000u64 {
204        shard_b.record(v);
205    }
206    merge(&mut shard_a, &shard_b).expect("identical shape merges");
207    println!(
208        "  fleet count={}, p50={}, p99={}",
209        shard_a.count(),
210        shard_a.value_at_percentile(0.5),
211        shard_a.value_at_percentile(0.99)
212    );
213    assert_eq!(shard_a.count(), 1_000, "both shards folded in");
214    assert!(
215        shard_a.value_at_percentile(0.99) >= 900,
216        "the high tail came from shard b"
217    );
218}

Source

pub fn sub_count(&self) -> u32

Examples found in repository ?

examples/perf_features.rs (line 57)

56fn sub_count(d: u32) -> usize {
57    HdrHistogram::new(d).sub_count() as usize
58}

Source

pub fn min(&self) -> u64

Lowest value recorded, as its bucket’s lower bound. 0 if empty. Read-side sweep, same cost class as Self::value_at_percentile.

Examples found in repository ?

examples/sample_app.rs (line 94)

46fn base_tick_to_trade() {
47    println!("== base: tick-to-trade latency capture ==");
48    let mut h = HdrHistogram::new(3);
49
50    // A right-skewed latency stream: most ops sit in a tight band, a small
51    // fraction spike into the tail. Deterministic xorshift so the numbers are
52    // reproducible.
53    let mut rng = 0x2545_F491_4F6C_DD1Du64;
54    let mut next = || {
55        rng ^= rng << 13;
56        rng ^= rng >> 7;
57        rng ^= rng << 17;
58        rng
59    };
60    let n = 2_000u64;
61    for i in 0..n {
62        let base = 700 + next() % 300; // 700..1000 ns steady state
63        if i % 50 == 0 {
64            h.record(4_000 + next() % 4_000); // ~2% tail spike, 4us..8us
65        } else {
66            h.record(base);
67        }
68    }
69
70    let p50 = h.value_at_percentile(0.50);
71    let p99 = h.value_at_percentile(0.99);
72    let p999 = h.value_at_percentile(0.999);
73    println!(
74        "  n={n} p50={p50}ns p99={p99}ns p999={p999}ns max={}ns",
75        h.max()
76    );
77    assert_eq!(h.count(), n, "every sample recorded");
78    assert!(
79        p50 <= 1_100,
80        "median sits in the steady-state band: p50={p50}"
81    );
82    assert!(
83        p99 >= 2_000,
84        "the 2% tail lifts p99 well past the median: p99={p99}"
85    );
86    assert!(p999 >= p99 && h.max() >= p999, "percentiles are monotone");
87
88    // The reporting surface a dashboard actually wants alongside the
89    // percentiles: the floor, the mean, the fraction inside the SLO, and what
90    // the whole thing costs in memory.
91    let within_slo = h.percentile_at_or_below_value(2_000);
92    println!(
93        "  min={}ns mean={:.0}ns within-2us={:.1}% footprint={}KB",
94        h.min(),
95        h.mean(),
96        within_slo * 100.0,
97        h.footprint_bytes() / 1024
98    );
99    assert!(within_slo > 0.9, "most ops sit inside the 2us band");
100
101    // Coordinated omission: a fixed-rate loop issues one op every 10 ns, then
102    // stalls for 1000 ns. The naive histogram sees one slow sample; the
103    // corrected one backfills the 99 requests the stall blocked.
104    let mut naive = HdrHistogram::new(3);
105    let mut corrected = HdrHistogram::new(3);
106    for _ in 0..1_000 {
107        naive.record(10);
108        corrected.record_with_expected_interval(10, 10);
109    }
110    naive.record(1_000);
111    corrected.record_with_expected_interval(1_000, 10);
112    let naive_p99 = naive.value_at_percentile(0.99);
113    let corrected_p99 = corrected.value_at_percentile(0.99);
114    println!("  coordinated omission: naive p99={naive_p99}ns, corrected p99={corrected_p99}ns");
115    assert!(
116        naive_p99 <= 20,
117        "uncorrected tail hides the stall: {naive_p99}"
118    );
119    assert!(
120        corrected_p99 >= 500,
121        "correction lifts the tail: {corrected_p99}"
122    );
123}

Source

pub fn mean(&self) -> f64

Arithmetic mean over the recorded bucket lower bounds. 0.0 if empty. Quantised the same way the percentiles are, so it sits within the significant-digit error band rather than being exact.

Examples found in repository ?

examples/sample_app.rs (line 95)

46fn base_tick_to_trade() {
47    println!("== base: tick-to-trade latency capture ==");
48    let mut h = HdrHistogram::new(3);
49
50    // A right-skewed latency stream: most ops sit in a tight band, a small
51    // fraction spike into the tail. Deterministic xorshift so the numbers are
52    // reproducible.
53    let mut rng = 0x2545_F491_4F6C_DD1Du64;
54    let mut next = || {
55        rng ^= rng << 13;
56        rng ^= rng >> 7;
57        rng ^= rng << 17;
58        rng
59    };
60    let n = 2_000u64;
61    for i in 0..n {
62        let base = 700 + next() % 300; // 700..1000 ns steady state
63        if i % 50 == 0 {
64            h.record(4_000 + next() % 4_000); // ~2% tail spike, 4us..8us
65        } else {
66            h.record(base);
67        }
68    }
69
70    let p50 = h.value_at_percentile(0.50);
71    let p99 = h.value_at_percentile(0.99);
72    let p999 = h.value_at_percentile(0.999);
73    println!(
74        "  n={n} p50={p50}ns p99={p99}ns p999={p999}ns max={}ns",
75        h.max()
76    );
77    assert_eq!(h.count(), n, "every sample recorded");
78    assert!(
79        p50 <= 1_100,
80        "median sits in the steady-state band: p50={p50}"
81    );
82    assert!(
83        p99 >= 2_000,
84        "the 2% tail lifts p99 well past the median: p99={p99}"
85    );
86    assert!(p999 >= p99 && h.max() >= p999, "percentiles are monotone");
87
88    // The reporting surface a dashboard actually wants alongside the
89    // percentiles: the floor, the mean, the fraction inside the SLO, and what
90    // the whole thing costs in memory.
91    let within_slo = h.percentile_at_or_below_value(2_000);
92    println!(
93        "  min={}ns mean={:.0}ns within-2us={:.1}% footprint={}KB",
94        h.min(),
95        h.mean(),
96        within_slo * 100.0,
97        h.footprint_bytes() / 1024
98    );
99    assert!(within_slo > 0.9, "most ops sit inside the 2us band");
100
101    // Coordinated omission: a fixed-rate loop issues one op every 10 ns, then
102    // stalls for 1000 ns. The naive histogram sees one slow sample; the
103    // corrected one backfills the 99 requests the stall blocked.
104    let mut naive = HdrHistogram::new(3);
105    let mut corrected = HdrHistogram::new(3);
106    for _ in 0..1_000 {
107        naive.record(10);
108        corrected.record_with_expected_interval(10, 10);
109    }
110    naive.record(1_000);
111    corrected.record_with_expected_interval(1_000, 10);
112    let naive_p99 = naive.value_at_percentile(0.99);
113    let corrected_p99 = corrected.value_at_percentile(0.99);
114    println!("  coordinated omission: naive p99={naive_p99}ns, corrected p99={corrected_p99}ns");
115    assert!(
116        naive_p99 <= 20,
117        "uncorrected tail hides the stall: {naive_p99}"
118    );
119    assert!(
120        corrected_p99 >= 500,
121        "correction lifts the tail: {corrected_p99}"
122    );
123}

Source

pub fn count_at_value(&self, value: u64) -> u64

Recordings that landed in value’s bucket. Constant time - the same index computation record does.

Source

pub fn percentile_at_or_below_value(&self, value: u64) -> f64

Fraction of recordings at or below value’s bucket, in 0.0..=1.0. The inverse of Self::value_at_percentile: that maps a rank to a value, this maps a value to its rank.

Examples found in repository ?

examples/sample_app.rs (line 91)

46fn base_tick_to_trade() {
47    println!("== base: tick-to-trade latency capture ==");
48    let mut h = HdrHistogram::new(3);
49
50    // A right-skewed latency stream: most ops sit in a tight band, a small
51    // fraction spike into the tail. Deterministic xorshift so the numbers are
52    // reproducible.
53    let mut rng = 0x2545_F491_4F6C_DD1Du64;
54    let mut next = || {
55        rng ^= rng << 13;
56        rng ^= rng >> 7;
57        rng ^= rng << 17;
58        rng
59    };
60    let n = 2_000u64;
61    for i in 0..n {
62        let base = 700 + next() % 300; // 700..1000 ns steady state
63        if i % 50 == 0 {
64            h.record(4_000 + next() % 4_000); // ~2% tail spike, 4us..8us
65        } else {
66            h.record(base);
67        }
68    }
69
70    let p50 = h.value_at_percentile(0.50);
71    let p99 = h.value_at_percentile(0.99);
72    let p999 = h.value_at_percentile(0.999);
73    println!(
74        "  n={n} p50={p50}ns p99={p99}ns p999={p999}ns max={}ns",
75        h.max()
76    );
77    assert_eq!(h.count(), n, "every sample recorded");
78    assert!(
79        p50 <= 1_100,
80        "median sits in the steady-state band: p50={p50}"
81    );
82    assert!(
83        p99 >= 2_000,
84        "the 2% tail lifts p99 well past the median: p99={p99}"
85    );
86    assert!(p999 >= p99 && h.max() >= p999, "percentiles are monotone");
87
88    // The reporting surface a dashboard actually wants alongside the
89    // percentiles: the floor, the mean, the fraction inside the SLO, and what
90    // the whole thing costs in memory.
91    let within_slo = h.percentile_at_or_below_value(2_000);
92    println!(
93        "  min={}ns mean={:.0}ns within-2us={:.1}% footprint={}KB",
94        h.min(),
95        h.mean(),
96        within_slo * 100.0,
97        h.footprint_bytes() / 1024
98    );
99    assert!(within_slo > 0.9, "most ops sit inside the 2us band");
100
101    // Coordinated omission: a fixed-rate loop issues one op every 10 ns, then
102    // stalls for 1000 ns. The naive histogram sees one slow sample; the
103    // corrected one backfills the 99 requests the stall blocked.
104    let mut naive = HdrHistogram::new(3);
105    let mut corrected = HdrHistogram::new(3);
106    for _ in 0..1_000 {
107        naive.record(10);
108        corrected.record_with_expected_interval(10, 10);
109    }
110    naive.record(1_000);
111    corrected.record_with_expected_interval(1_000, 10);
112    let naive_p99 = naive.value_at_percentile(0.99);
113    let corrected_p99 = corrected.value_at_percentile(0.99);
114    println!("  coordinated omission: naive p99={naive_p99}ns, corrected p99={corrected_p99}ns");
115    assert!(
116        naive_p99 <= 20,
117        "uncorrected tail hides the stall: {naive_p99}"
118    );
119    assert!(
120        corrected_p99 >= 500,
121        "correction lifts the tail: {corrected_p99}"
122    );
123}

Source

pub fn footprint_bytes(&self) -> usize

Counter-array footprint in bytes. Grows with the largest value recorded, not with how many values were recorded.

Examples found in repository ?

examples/sample_app.rs (line 97)

46fn base_tick_to_trade() {
47    println!("== base: tick-to-trade latency capture ==");
48    let mut h = HdrHistogram::new(3);
49
50    // A right-skewed latency stream: most ops sit in a tight band, a small
51    // fraction spike into the tail. Deterministic xorshift so the numbers are
52    // reproducible.
53    let mut rng = 0x2545_F491_4F6C_DD1Du64;
54    let mut next = || {
55        rng ^= rng << 13;
56        rng ^= rng >> 7;
57        rng ^= rng << 17;
58        rng
59    };
60    let n = 2_000u64;
61    for i in 0..n {
62        let base = 700 + next() % 300; // 700..1000 ns steady state
63        if i % 50 == 0 {
64            h.record(4_000 + next() % 4_000); // ~2% tail spike, 4us..8us
65        } else {
66            h.record(base);
67        }
68    }
69
70    let p50 = h.value_at_percentile(0.50);
71    let p99 = h.value_at_percentile(0.99);
72    let p999 = h.value_at_percentile(0.999);
73    println!(
74        "  n={n} p50={p50}ns p99={p99}ns p999={p999}ns max={}ns",
75        h.max()
76    );
77    assert_eq!(h.count(), n, "every sample recorded");
78    assert!(
79        p50 <= 1_100,
80        "median sits in the steady-state band: p50={p50}"
81    );
82    assert!(
83        p99 >= 2_000,
84        "the 2% tail lifts p99 well past the median: p99={p99}"
85    );
86    assert!(p999 >= p99 && h.max() >= p999, "percentiles are monotone");
87
88    // The reporting surface a dashboard actually wants alongside the
89    // percentiles: the floor, the mean, the fraction inside the SLO, and what
90    // the whole thing costs in memory.
91    let within_slo = h.percentile_at_or_below_value(2_000);
92    println!(
93        "  min={}ns mean={:.0}ns within-2us={:.1}% footprint={}KB",
94        h.min(),
95        h.mean(),
96        within_slo * 100.0,
97        h.footprint_bytes() / 1024
98    );
99    assert!(within_slo > 0.9, "most ops sit inside the 2us band");
100
101    // Coordinated omission: a fixed-rate loop issues one op every 10 ns, then
102    // stalls for 1000 ns. The naive histogram sees one slow sample; the
103    // corrected one backfills the 99 requests the stall blocked.
104    let mut naive = HdrHistogram::new(3);
105    let mut corrected = HdrHistogram::new(3);
106    for _ in 0..1_000 {
107        naive.record(10);
108        corrected.record_with_expected_interval(10, 10);
109    }
110    naive.record(1_000);
111    corrected.record_with_expected_interval(1_000, 10);
112    let naive_p99 = naive.value_at_percentile(0.99);
113    let corrected_p99 = corrected.value_at_percentile(0.99);
114    println!("  coordinated omission: naive p99={naive_p99}ns, corrected p99={corrected_p99}ns");
115    assert!(
116        naive_p99 <= 20,
117        "uncorrected tail hides the stall: {naive_p99}"
118    );
119    assert!(
120        corrected_p99 >= 500,
121        "correction lifts the tail: {corrected_p99}"
122    );
123}