Histogram buckets can be aggregated across service instances because each instance exports counts against the same boundaries. Unlike client-side summaries, this allows fleet-wide quantile estimates.
Design a HistogramBucketAggregator class:
HistogramBucketAggregator() creates a stateless aggregator.int[] mergeCumulativeCounts(int[][] instanceCounts) sums corresponding cumulative buckets.double quantile(int[] upperBounds, int[][] instanceCounts, double q) estimates a quantile and rounds it to 5 decimal places.
Each row in instanceCounts is cumulative and aligned with strictly increasing upperBounds. The first bucket has lower bound 0; every later bucket's lower bound is the preceding upper bound.
After merging, let rank = q * total, where total is the final cumulative count. Find the first bucket whose cumulative count reaches rank, then assume observations are uniformly distributed inside that bucket:
Example 1:
Input:
Output:
Explanation: The merged counts are [3,7,10]. Rank 5 lies halfway through the four observations between 100 and 200.
Example 2:
Input:
Output:
Explanation: Rank 9 is two observations into the three-observation interval from 200 to 500.
Constraints
1 <= instanceCounts.length <= 5001 <= upperBounds.length == instanceCounts[i].length <= 1000 < upperBounds[i] <= 10^9, strictly increasing.- Every row is nondecreasing and has a positive final count.
0 < q <= 1- Merged counts fit in a signed 32-bit integer.
- Round only the final quantile; answers are accepted within
10^-5. - At most
100 total method calls are made.
Aggregate Histogram Bucketsmedium