histogram.go 8.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329
  1. /*
  2. *
  3. * Copyright 2017 gRPC authors.
  4. *
  5. * Licensed under the Apache License, Version 2.0 (the "License");
  6. * you may not use this file except in compliance with the License.
  7. * You may obtain a copy of the License at
  8. *
  9. * http://www.apache.org/licenses/LICENSE-2.0
  10. *
  11. * Unless required by applicable law or agreed to in writing, software
  12. * distributed under the License is distributed on an "AS IS" BASIS,
  13. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14. * See the License for the specific language governing permissions and
  15. * limitations under the License.
  16. *
  17. */
  18. // Copyright (c) 2015 Arista Networks, Inc.
  19. // Use of this source code is governed by the Apache License 2.0
  20. // that can be found in the COPYING file.
  21. package stats
  22. import (
  23. "bytes"
  24. "encoding/json"
  25. "fmt"
  26. "io"
  27. "strconv"
  28. "strings"
  29. "time"
  30. )
  31. // HistogramValue is the value of Histogram objects.
  32. type HistogramValue struct {
  33. // Count is the total number of values added to the histogram.
  34. Count int64
  35. // Sum is the sum of all the values added to the histogram.
  36. Sum int64
  37. // Min is the minimum of all the values added to the histogram.
  38. Min int64
  39. // Max is the maximum of all the values added to the histogram.
  40. Max int64
  41. // Buckets contains all the buckets of the histogram.
  42. Buckets []HistogramBucket
  43. }
  44. // HistogramBucket is one histogram bucket.
  45. type HistogramBucket struct {
  46. // LowBound is the lower bound of the bucket.
  47. LowBound int64
  48. // Count is the number of values in the bucket.
  49. Count int64
  50. }
  51. // PrintChart writes textual output of the histogram values.
  52. func (v HistogramValue) PrintChart(w io.Writer) {
  53. avg := float64(v.Sum) / float64(v.Count)
  54. fmt.Fprintf(w, "Count: %d Min: %d Max: %d Avg: %.2f\n", v.Count, v.Min, v.Max, avg)
  55. fmt.Fprintf(w, "%s\n", strings.Repeat("-", 60))
  56. if v.Count <= 0 {
  57. return
  58. }
  59. maxBucketDigitLen := len(strconv.FormatInt(v.Buckets[len(v.Buckets)-1].LowBound, 10))
  60. if maxBucketDigitLen < 3 {
  61. // For "inf".
  62. maxBucketDigitLen = 3
  63. }
  64. maxCountDigitLen := len(strconv.FormatInt(v.Count, 10))
  65. percentMulti := 100 / float64(v.Count)
  66. accCount := int64(0)
  67. for i, b := range v.Buckets {
  68. fmt.Fprintf(w, "[%*d, ", maxBucketDigitLen, b.LowBound)
  69. if i+1 < len(v.Buckets) {
  70. fmt.Fprintf(w, "%*d)", maxBucketDigitLen, v.Buckets[i+1].LowBound)
  71. } else {
  72. fmt.Fprintf(w, "%*s)", maxBucketDigitLen, "inf")
  73. }
  74. accCount += b.Count
  75. fmt.Fprintf(w, " %*d %5.1f%% %5.1f%%", maxCountDigitLen, b.Count,
  76. float64(b.Count)*percentMulti, float64(accCount)*percentMulti)
  77. const barScale = 0.1
  78. barLength := int(float64(b.Count)*percentMulti*barScale + 0.5)
  79. fmt.Fprintf(w, " %s\n", strings.Repeat("#", barLength))
  80. }
  81. }
  82. // MarshalJSON marshal the HistogramValue into JSON.
  83. func (v HistogramValue) MarshalJSON() ([]byte, error) {
  84. var b bytes.Buffer
  85. var min int64
  86. var max int64
  87. var avg float64
  88. var percentMulti float64
  89. if v.Count != 0 {
  90. min = v.Min
  91. max = v.Max
  92. avg = float64(v.Sum) / float64(v.Count)
  93. percentMulti = 100 / float64(v.Count)
  94. }
  95. fmt.Fprintf(&b,
  96. `{"stats":{"count":%d,"min":%d,"max":%d,"avg":%.2f}, "buckets": {`,
  97. v.Count, min, max, avg)
  98. for i, bucket := range v.Buckets {
  99. fmt.Fprintf(&b, `"[%d,`, bucket.LowBound)
  100. if i+1 < len(v.Buckets) {
  101. fmt.Fprintf(&b, `%d)":{`, v.Buckets[i+1].LowBound)
  102. } else {
  103. fmt.Fprintf(&b, `inf)":{`)
  104. }
  105. fmt.Fprintf(&b, `"count":%d,"percentage":%.1f}`,
  106. bucket.Count, float64(bucket.Count)*percentMulti)
  107. if i != len(v.Buckets)-1 {
  108. fmt.Fprintf(&b, ",")
  109. }
  110. }
  111. fmt.Fprint(&b, `}}`)
  112. return b.Bytes(), nil
  113. }
  114. // String returns the textual output of the histogram values as string.
  115. func (v HistogramValue) String() string {
  116. var b bytes.Buffer
  117. v.PrintChart(&b)
  118. return b.String()
  119. }
  120. // A Histogram accumulates values in the form of a histogram. The type of the
  121. // values is int64, which is suitable for keeping track of things like RPC
  122. // latency in milliseconds. New histogram objects should be obtained via the
  123. // New() function.
  124. type Histogram struct {
  125. opts HistogramOptions
  126. buckets []bucketInternal
  127. count *Counter
  128. sum *Counter
  129. tracker *Tracker
  130. }
  131. // HistogramOptions contains the parameters that define the histogram's buckets.
  132. type HistogramOptions struct {
  133. // NumBuckets is the number of buckets.
  134. NumBuckets int
  135. // GrowthFactor is the growth factor of the buckets. A value of 0.1
  136. // indicates that bucket N+1 will be 10% larger than bucket N.
  137. GrowthFactor float64
  138. // SmallestBucketSize is the size of the first bucket. Bucket sizes are
  139. // rounded down to the nearest integer.
  140. SmallestBucketSize float64
  141. // MinValue is the lower bound of the first bucket.
  142. MinValue int64
  143. }
  144. // bucketInternal is the internal representation of a bucket, which includes a
  145. // rate counter.
  146. type bucketInternal struct {
  147. lowBound int64
  148. count *Counter
  149. }
  150. // NewHistogram returns a pointer to a new Histogram object that was created
  151. // with the provided options.
  152. func NewHistogram(opts HistogramOptions) *Histogram {
  153. if opts.NumBuckets == 0 {
  154. opts.NumBuckets = 32
  155. }
  156. if opts.SmallestBucketSize == 0.0 {
  157. opts.SmallestBucketSize = 1.0
  158. }
  159. h := Histogram{
  160. opts: opts,
  161. buckets: make([]bucketInternal, opts.NumBuckets),
  162. count: newCounter(),
  163. sum: newCounter(),
  164. tracker: newTracker(),
  165. }
  166. low := opts.MinValue
  167. delta := opts.SmallestBucketSize
  168. for i := 0; i < opts.NumBuckets; i++ {
  169. h.buckets[i].lowBound = low
  170. h.buckets[i].count = newCounter()
  171. low = low + int64(delta)
  172. delta = delta * (1.0 + opts.GrowthFactor)
  173. }
  174. return &h
  175. }
  176. // Opts returns a copy of the options used to create the Histogram.
  177. func (h *Histogram) Opts() HistogramOptions {
  178. return h.opts
  179. }
  180. // Print returns the histogram as a chart.
  181. func (h *Histogram) Print() string {
  182. return h.Value().String()
  183. }
  184. // String returns a JSON representation of the histogram for expvars.
  185. func (h *Histogram) String() string {
  186. j, err := json.Marshal(h.Value())
  187. if err != nil {
  188. return ""
  189. }
  190. return string(j)
  191. }
  192. // Add adds a value to the histogram.
  193. func (h *Histogram) Add(value int64) error {
  194. bucket, err := h.findBucket(value)
  195. if err != nil {
  196. return err
  197. }
  198. h.buckets[bucket].count.Incr(1)
  199. h.count.Incr(1)
  200. h.sum.Incr(value)
  201. h.tracker.Push(value)
  202. return nil
  203. }
  204. // LastUpdate returns the time at which the object was last updated.
  205. func (h *Histogram) LastUpdate() time.Time {
  206. return h.count.LastUpdate()
  207. }
  208. // Value returns the accumulated state of the histogram since it was created.
  209. func (h *Histogram) Value() HistogramValue {
  210. b := make([]HistogramBucket, len(h.buckets))
  211. for i, v := range h.buckets {
  212. b[i] = HistogramBucket{
  213. LowBound: v.lowBound,
  214. Count: v.count.Value(),
  215. }
  216. }
  217. v := HistogramValue{
  218. Count: h.count.Value(),
  219. Sum: h.sum.Value(),
  220. Min: h.tracker.Min(),
  221. Max: h.tracker.Max(),
  222. Buckets: b,
  223. }
  224. return v
  225. }
  226. // Delta1h returns the change in the last hour.
  227. func (h *Histogram) Delta1h() HistogramValue {
  228. b := make([]HistogramBucket, len(h.buckets))
  229. for i, v := range h.buckets {
  230. b[i] = HistogramBucket{
  231. LowBound: v.lowBound,
  232. Count: v.count.Delta1h(),
  233. }
  234. }
  235. v := HistogramValue{
  236. Count: h.count.Delta1h(),
  237. Sum: h.sum.Delta1h(),
  238. Min: h.tracker.Min1h(),
  239. Max: h.tracker.Max1h(),
  240. Buckets: b,
  241. }
  242. return v
  243. }
  244. // Delta10m returns the change in the last 10 minutes.
  245. func (h *Histogram) Delta10m() HistogramValue {
  246. b := make([]HistogramBucket, len(h.buckets))
  247. for i, v := range h.buckets {
  248. b[i] = HistogramBucket{
  249. LowBound: v.lowBound,
  250. Count: v.count.Delta10m(),
  251. }
  252. }
  253. v := HistogramValue{
  254. Count: h.count.Delta10m(),
  255. Sum: h.sum.Delta10m(),
  256. Min: h.tracker.Min10m(),
  257. Max: h.tracker.Max10m(),
  258. Buckets: b,
  259. }
  260. return v
  261. }
  262. // Delta1m returns the change in the last 10 minutes.
  263. func (h *Histogram) Delta1m() HistogramValue {
  264. b := make([]HistogramBucket, len(h.buckets))
  265. for i, v := range h.buckets {
  266. b[i] = HistogramBucket{
  267. LowBound: v.lowBound,
  268. Count: v.count.Delta1m(),
  269. }
  270. }
  271. v := HistogramValue{
  272. Count: h.count.Delta1m(),
  273. Sum: h.sum.Delta1m(),
  274. Min: h.tracker.Min1m(),
  275. Max: h.tracker.Max1m(),
  276. Buckets: b,
  277. }
  278. return v
  279. }
  280. // findBucket does a binary search to find in which bucket the value goes.
  281. func (h *Histogram) findBucket(value int64) (int, error) {
  282. lastBucket := len(h.buckets) - 1
  283. min, max := 0, lastBucket
  284. for max >= min {
  285. b := (min + max) / 2
  286. if value >= h.buckets[b].lowBound && (b == lastBucket || value < h.buckets[b+1].lowBound) {
  287. return b, nil
  288. }
  289. if value < h.buckets[b].lowBound {
  290. max = b - 1
  291. continue
  292. }
  293. min = b + 1
  294. }
  295. return 0, fmt.Errorf("no bucket for value: %d", value)
  296. }