1// Copyright 2017, OpenCensus Authors 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package trace 16 17import ( 18 "time" 19) 20 21// samplePeriod is the minimum time between accepting spans in a single bucket. 22const samplePeriod = time.Second 23 24// defaultLatencies contains the default latency bucket bounds. 25// TODO: consider defaults, make configurable 26var defaultLatencies = [...]time.Duration{ 27 10 * time.Microsecond, 28 100 * time.Microsecond, 29 time.Millisecond, 30 10 * time.Millisecond, 31 100 * time.Millisecond, 32 time.Second, 33 10 * time.Second, 34 time.Minute, 35} 36 37// bucket is a container for a set of spans for a particular error code or latency range. 38type bucket struct { 39 nextTime time.Time // next time we can accept a span 40 buffer []*SpanData // circular buffer of spans 41 nextIndex int // location next SpanData should be placed in buffer 42 overflow bool // whether the circular buffer has wrapped around 43} 44 45func makeBucket(bufferSize int) bucket { 46 return bucket{ 47 buffer: make([]*SpanData, bufferSize), 48 } 49} 50 51// add adds a span to the bucket, if nextTime has been reached. 52func (b *bucket) add(s *SpanData) { 53 if s.EndTime.Before(b.nextTime) { 54 return 55 } 56 if len(b.buffer) == 0 { 57 return 58 } 59 b.nextTime = s.EndTime.Add(samplePeriod) 60 b.buffer[b.nextIndex] = s 61 b.nextIndex++ 62 if b.nextIndex == len(b.buffer) { 63 b.nextIndex = 0 64 b.overflow = true 65 } 66} 67 68// size returns the number of spans in the bucket. 69func (b *bucket) size() int { 70 if b.overflow { 71 return len(b.buffer) 72 } 73 return b.nextIndex 74} 75 76// span returns the ith span in the bucket. 77func (b *bucket) span(i int) *SpanData { 78 if !b.overflow { 79 return b.buffer[i] 80 } 81 if i < len(b.buffer)-b.nextIndex { 82 return b.buffer[b.nextIndex+i] 83 } 84 return b.buffer[b.nextIndex+i-len(b.buffer)] 85} 86 87// resize changes the size of the bucket to n, keeping up to n existing spans. 88func (b *bucket) resize(n int) { 89 cur := b.size() 90 newBuffer := make([]*SpanData, n) 91 if cur < n { 92 for i := 0; i < cur; i++ { 93 newBuffer[i] = b.span(i) 94 } 95 b.buffer = newBuffer 96 b.nextIndex = cur 97 b.overflow = false 98 return 99 } 100 for i := 0; i < n; i++ { 101 newBuffer[i] = b.span(i + cur - n) 102 } 103 b.buffer = newBuffer 104 b.nextIndex = 0 105 b.overflow = true 106} 107 108// latencyBucket returns the appropriate bucket number for a given latency. 109func latencyBucket(latency time.Duration) int { 110 i := 0 111 for i < len(defaultLatencies) && latency >= defaultLatencies[i] { 112 i++ 113 } 114 return i 115} 116 117// latencyBucketBounds returns the lower and upper bounds for a latency bucket 118// number. 119// 120// The lower bound is inclusive, the upper bound is exclusive (except for the 121// last bucket.) 122func latencyBucketBounds(index int) (lower time.Duration, upper time.Duration) { 123 if index == 0 { 124 return 0, defaultLatencies[index] 125 } 126 if index == len(defaultLatencies) { 127 return defaultLatencies[index-1], 1<<63 - 1 128 } 129 return defaultLatencies[index-1], defaultLatencies[index] 130} 131