histogram.go raw
1 // Copyright 2015 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package trace
6
7 // This file implements histogramming for RPC statistics collection.
8
9 import (
10 "bytes"
11 "fmt"
12 "html/template"
13 "log"
14 "math"
15 "sync"
16
17 "golang.org/x/net/internal/timeseries"
18 )
19
20 const (
21 bucketCount = 38
22 )
23
24 // histogram keeps counts of values in buckets that are spaced
25 // out in powers of 2: 0-1, 2-3, 4-7...
26 // histogram implements timeseries.Observable
27 type histogram struct {
28 sum int64 // running total of measurements
29 sumOfSquares float64 // square of running total
30 buckets []int64 // bucketed values for histogram
31 value int // holds a single value as an optimization
32 valueCount int64 // number of values recorded for single value
33 }
34
35 // addMeasurement records a value measurement observation to the histogram.
36 func (h *histogram) addMeasurement(value int64) {
37 // TODO: assert invariant
38 h.sum += value
39 h.sumOfSquares += float64(value) * float64(value)
40
41 bucketIndex := getBucket(value)
42
43 if h.valueCount == 0 || (h.valueCount > 0 && h.value == bucketIndex) {
44 h.value = bucketIndex
45 h.valueCount++
46 } else {
47 h.allocateBuckets()
48 h.buckets[bucketIndex]++
49 }
50 }
51
52 func (h *histogram) allocateBuckets() {
53 if h.buckets == nil {
54 h.buckets = make([]int64, bucketCount)
55 h.buckets[h.value] = h.valueCount
56 h.value = 0
57 h.valueCount = -1
58 }
59 }
60
61 func log2(i int64) int {
62 n := 0
63 for ; i >= 0x100; i >>= 8 {
64 n += 8
65 }
66 for ; i > 0; i >>= 1 {
67 n += 1
68 }
69 return n
70 }
71
72 func getBucket(i int64) (index int) {
73 index = log2(i) - 1
74 if index < 0 {
75 index = 0
76 }
77 if index >= bucketCount {
78 index = bucketCount - 1
79 }
80 return
81 }
82
83 // Total returns the number of recorded observations.
84 func (h *histogram) total() (total int64) {
85 if h.valueCount >= 0 {
86 total = h.valueCount
87 }
88 for _, val := range h.buckets {
89 total += int64(val)
90 }
91 return
92 }
93
94 // Average returns the average value of recorded observations.
95 func (h *histogram) average() float64 {
96 t := h.total()
97 if t == 0 {
98 return 0
99 }
100 return float64(h.sum) / float64(t)
101 }
102
103 // Variance returns the variance of recorded observations.
104 func (h *histogram) variance() float64 {
105 t := float64(h.total())
106 if t == 0 {
107 return 0
108 }
109 s := float64(h.sum) / t
110 return h.sumOfSquares/t - s*s
111 }
112
113 // StandardDeviation returns the standard deviation of recorded observations.
114 func (h *histogram) standardDeviation() float64 {
115 return math.Sqrt(h.variance())
116 }
117
118 // PercentileBoundary estimates the value that the given fraction of recorded
119 // observations are less than.
120 func (h *histogram) percentileBoundary(percentile float64) int64 {
121 total := h.total()
122
123 // Corner cases (make sure result is strictly less than Total())
124 if total == 0 {
125 return 0
126 } else if total == 1 {
127 return int64(h.average())
128 }
129
130 percentOfTotal := round(float64(total) * percentile)
131 var runningTotal int64
132
133 for i := range h.buckets {
134 value := h.buckets[i]
135 runningTotal += value
136 if runningTotal == percentOfTotal {
137 // We hit an exact bucket boundary. If the next bucket has data, it is a
138 // good estimate of the value. If the bucket is empty, we interpolate the
139 // midpoint between the next bucket's boundary and the next non-zero
140 // bucket. If the remaining buckets are all empty, then we use the
141 // boundary for the next bucket as the estimate.
142 j := uint8(i + 1)
143 min := bucketBoundary(j)
144 if runningTotal < total {
145 for h.buckets[j] == 0 {
146 j++
147 }
148 }
149 max := bucketBoundary(j)
150 return min + round(float64(max-min)/2)
151 } else if runningTotal > percentOfTotal {
152 // The value is in this bucket. Interpolate the value.
153 delta := runningTotal - percentOfTotal
154 percentBucket := float64(value-delta) / float64(value)
155 bucketMin := bucketBoundary(uint8(i))
156 nextBucketMin := bucketBoundary(uint8(i + 1))
157 bucketSize := nextBucketMin - bucketMin
158 return bucketMin + round(percentBucket*float64(bucketSize))
159 }
160 }
161 return bucketBoundary(bucketCount - 1)
162 }
163
164 // Median returns the estimated median of the observed values.
165 func (h *histogram) median() int64 {
166 return h.percentileBoundary(0.5)
167 }
168
169 // Add adds other to h.
170 func (h *histogram) Add(other timeseries.Observable) {
171 o := other.(*histogram)
172 if o.valueCount == 0 {
173 // Other histogram is empty
174 } else if h.valueCount >= 0 && o.valueCount > 0 && h.value == o.value {
175 // Both have a single bucketed value, aggregate them
176 h.valueCount += o.valueCount
177 } else {
178 // Two different values necessitate buckets in this histogram
179 h.allocateBuckets()
180 if o.valueCount >= 0 {
181 h.buckets[o.value] += o.valueCount
182 } else {
183 for i := range h.buckets {
184 h.buckets[i] += o.buckets[i]
185 }
186 }
187 }
188 h.sumOfSquares += o.sumOfSquares
189 h.sum += o.sum
190 }
191
192 // Clear resets the histogram to an empty state, removing all observed values.
193 func (h *histogram) Clear() {
194 h.buckets = nil
195 h.value = 0
196 h.valueCount = 0
197 h.sum = 0
198 h.sumOfSquares = 0
199 }
200
201 // CopyFrom copies from other, which must be a *histogram, into h.
202 func (h *histogram) CopyFrom(other timeseries.Observable) {
203 o := other.(*histogram)
204 if o.valueCount == -1 {
205 h.allocateBuckets()
206 copy(h.buckets, o.buckets)
207 }
208 h.sum = o.sum
209 h.sumOfSquares = o.sumOfSquares
210 h.value = o.value
211 h.valueCount = o.valueCount
212 }
213
214 // Multiply scales the histogram by the specified ratio.
215 func (h *histogram) Multiply(ratio float64) {
216 if h.valueCount == -1 {
217 for i := range h.buckets {
218 h.buckets[i] = int64(float64(h.buckets[i]) * ratio)
219 }
220 } else {
221 h.valueCount = int64(float64(h.valueCount) * ratio)
222 }
223 h.sum = int64(float64(h.sum) * ratio)
224 h.sumOfSquares = h.sumOfSquares * ratio
225 }
226
227 // New creates a new histogram.
228 func (h *histogram) New() timeseries.Observable {
229 r := new(histogram)
230 r.Clear()
231 return r
232 }
233
234 func (h *histogram) String() string {
235 return fmt.Sprintf("%d, %f, %d, %d, %v",
236 h.sum, h.sumOfSquares, h.value, h.valueCount, h.buckets)
237 }
238
239 // round returns the closest int64 to the argument
240 func round(in float64) int64 {
241 return int64(math.Floor(in + 0.5))
242 }
243
244 // bucketBoundary returns the first value in the bucket.
245 func bucketBoundary(bucket uint8) int64 {
246 if bucket == 0 {
247 return 0
248 }
249 return 1 << bucket
250 }
251
252 // bucketData holds data about a specific bucket for use in distTmpl.
253 type bucketData struct {
254 Lower, Upper int64
255 N int64
256 Pct, CumulativePct float64
257 GraphWidth int
258 }
259
260 // data holds data about a Distribution for use in distTmpl.
261 type data struct {
262 Buckets []*bucketData
263 Count, Median int64
264 Mean, StandardDeviation float64
265 }
266
267 // maxHTMLBarWidth is the maximum width of the HTML bar for visualizing buckets.
268 const maxHTMLBarWidth = 350.0
269
270 // newData returns data representing h for use in distTmpl.
271 func (h *histogram) newData() *data {
272 // Force the allocation of buckets to simplify the rendering implementation
273 h.allocateBuckets()
274 // We scale the bars on the right so that the largest bar is
275 // maxHTMLBarWidth pixels in width.
276 maxBucket := int64(0)
277 for _, n := range h.buckets {
278 if n > maxBucket {
279 maxBucket = n
280 }
281 }
282 total := h.total()
283 barsizeMult := maxHTMLBarWidth / float64(maxBucket)
284 var pctMult float64
285 if total == 0 {
286 pctMult = 1.0
287 } else {
288 pctMult = 100.0 / float64(total)
289 }
290
291 buckets := make([]*bucketData, len(h.buckets))
292 runningTotal := int64(0)
293 for i, n := range h.buckets {
294 if n == 0 {
295 continue
296 }
297 runningTotal += n
298 var upperBound int64
299 if i < bucketCount-1 {
300 upperBound = bucketBoundary(uint8(i + 1))
301 } else {
302 upperBound = math.MaxInt64
303 }
304 buckets[i] = &bucketData{
305 Lower: bucketBoundary(uint8(i)),
306 Upper: upperBound,
307 N: n,
308 Pct: float64(n) * pctMult,
309 CumulativePct: float64(runningTotal) * pctMult,
310 GraphWidth: int(float64(n) * barsizeMult),
311 }
312 }
313 return &data{
314 Buckets: buckets,
315 Count: total,
316 Median: h.median(),
317 Mean: h.average(),
318 StandardDeviation: h.standardDeviation(),
319 }
320 }
321
322 func (h *histogram) html() template.HTML {
323 buf := new(bytes.Buffer)
324 if err := distTmpl().Execute(buf, h.newData()); err != nil {
325 buf.Reset()
326 log.Printf("net/trace: couldn't execute template: %v", err)
327 }
328 return template.HTML(buf.String())
329 }
330
331 var distTmplCache *template.Template
332 var distTmplOnce sync.Once
333
334 func distTmpl() *template.Template {
335 distTmplOnce.Do(func() {
336 // Input: data
337 distTmplCache = template.Must(template.New("distTmpl").Parse(`
338 <table>
339 <tr>
340 <td style="padding:0.25em">Count: {{.Count}}</td>
341 <td style="padding:0.25em">Mean: {{printf "%.0f" .Mean}}</td>
342 <td style="padding:0.25em">StdDev: {{printf "%.0f" .StandardDeviation}}</td>
343 <td style="padding:0.25em">Median: {{.Median}}</td>
344 </tr>
345 </table>
346 <hr>
347 <table>
348 {{range $b := .Buckets}}
349 {{if $b}}
350 <tr>
351 <td style="padding:0 0 0 0.25em">[</td>
352 <td style="text-align:right;padding:0 0.25em">{{.Lower}},</td>
353 <td style="text-align:right;padding:0 0.25em">{{.Upper}})</td>
354 <td style="text-align:right;padding:0 0.25em">{{.N}}</td>
355 <td style="text-align:right;padding:0 0.25em">{{printf "%#.3f" .Pct}}%</td>
356 <td style="text-align:right;padding:0 0.25em">{{printf "%#.3f" .CumulativePct}}%</td>
357 <td><div style="background-color: blue; height: 1em; width: {{.GraphWidth}};"></div></td>
358 </tr>
359 {{end}}
360 {{end}}
361 </table>
362 `))
363 })
364 return distTmplCache
365 }
366