Class: Sixty::Sketch

Inherits:
Object
  • Object
show all
Defined in:
lib/sixty/sketch.rb

Overview

DDSketch — quantile sketch with relative error guarantees.

A byte-for-byte port of packages/core/src/sketch.js. The format is the contract between every agent and the collector: the collector decodes these blobs with the JavaScript implementation, merges them across releases, and computes the percentiles a finding is made of. A Ruby sketch that decoded into slightly different buckets would not error anywhere — it would produce a p95 that quietly disagrees with the one a Node service in the same org reports, which is the kind of wrong this project exists to avoid.

So the header layout, the varint encoding and the bucket indexing are reproduced exactly rather than reimplemented idiomatically, and test/sketch_test.rb checks the bytes against fixtures generated by the JavaScript writer.

Why a sketch at all: latency is heavy-tailed and multimodal. A mean moves too little to detect a real p95 regression, and merges of DDSketches are lossless — which is what lets the collector store one sketch per 5-minute bucket and union arbitrary windows without the numbers drifting.

Constant Summary collapse

MAGIC = 
0xd5
VERSION = 
1
MIN_VALUE = 
1e-9
HEADER_BYTES =

1 magic + 1 version + 5 doubles + 1 flag.

43

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(alpha = 0.01) ⇒ Sketch

Returns a new instance of Sketch.

Parameters:

  • alpha (Float) (defaults to: 0.01) —

    relative accuracy, e.g. 0.01 for 1%



35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/sixty/sketch.rb', line 35

def initialize(alpha = 0.01)
  @alpha = alpha
  @gamma = (1 + alpha) / (1 - alpha)
  @log_gamma = Math.log(@gamma)
  @buckets = {}
  @zero_count = 0
  @count = 0
  @sum = 0.0
  @min = Float::INFINITY
  @max = -Float::INFINITY
end

Instance Attribute Details

#alpha ⇒ Object (readonly)

Returns the value of attribute alpha.



32
33
34
 
# File 'lib/sixty/sketch.rb', line 32

def alpha
  @alpha
end

#buckets ⇒ Object (readonly)

Returns the value of attribute buckets.



32
33
34
 
# File 'lib/sixty/sketch.rb', line 32

def buckets
  @buckets
end

#count ⇒ Object (readonly)

Returns the value of attribute count.



32
33
34
 
# File 'lib/sixty/sketch.rb', line 32

def count
  @count
end

#sum ⇒ Object (readonly)

Returns the value of attribute sum.



32
33
34
 
# File 'lib/sixty/sketch.rb', line 32

def sum
  @sum
end

#zero_count ⇒ Object (readonly)

Returns the value of attribute zero_count.



32
33
34
 
# File 'lib/sixty/sketch.rb', line 32

def zero_count
  @zero_count
end

Class Method Details

.from_binary(bytes) ⇒ Object

Only the tests decode; the agent is write-only. Kept here anyway because a codec whose two halves live in different languages is a codec nobody can check locally.

Raises:

  • (ArgumentError) 


133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
 
# File 'lib/sixty/sketch.rb', line 133

def self.from_binary(bytes)
  bytes = bytes.b
  return new if bytes.bytesize < HEADER_BYTES
  raise ArgumentError, 'not a DDSketch buffer' unless bytes.getbyte(0) == MAGIC

  version = bytes.getbyte(1)
  raise ArgumentError, "unsupported sketch version #{version}" unless version == VERSION

  alpha, zero_count, sum, min, max = bytes.byteslice(2, 40).unpack('E5')
  sketch = new(alpha)
  sketch.instance_variable_set(:@zero_count, zero_count)
  sketch.instance_variable_set(:@sum, sum)

  offset = HEADER_BYTES
  total = zero_count
  prev = 0
  while offset < bytes.bytesize
    delta, offset = read_varint(bytes, offset)
    count, offset = read_varint(bytes, offset)
    i = prev + unzigzag(delta)
    sketch.buckets[i] = (sketch.buckets[i] || 0) + count
    total += count
    prev = i
  end

  sketch.instance_variable_set(:@count, total)
  sketch.instance_variable_set(:@min, total.positive? ? min : Float::INFINITY)
  sketch.instance_variable_set(:@max, total.positive? ? max : -Float::INFINITY)
  sketch
end

Instance Method Details

#add(value, count = 1) ⇒ Object 



47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/sixty/sketch.rb', line 47

def add(value, count = 1)
  value = value.to_f
  return self if value.nan? || value.infinite? || count <= 0

  value = 0.0 if value.negative?

  @count += count
  @sum += value * count
  @min = value if value < @min
  @max = value if value > @max

  if value < MIN_VALUE
    @zero_count += count
    return self
  end

  i = index(value)
  @buckets[i] = (@buckets[i] || 0) + count
  self
end

#mean ⇒ Object 



100
101
102
 
# File 'lib/sixty/sketch.rb', line 100

def mean
  @count.zero? ? nil : @sum / @count
end

#merge(other) ⇒ Object

Lossless when both sketches share alpha. Mutates self.

Raises:

  • (ArgumentError) 


69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/sixty/sketch.rb', line 69

def merge(other)
  return self if other.nil? || other.count.zero?
  raise ArgumentError, "cannot merge sketches with different alpha" if (other.alpha - @alpha).abs > 1e-12

  other.buckets.each { |i, c| @buckets[i] = (@buckets[i] || 0) + c }
  @zero_count += other.zero_count
  @count += other.count
  @sum += other.sum
  @min = other.min if other.min < @min
  @max = other.max if other.max > @max
  self
end

#quantile(q) ⇒ Object 



82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
# File 'lib/sixty/sketch.rb', line 82

def quantile(q)
  return nil if @count.zero?
  return @min if q <= 0
  return @max if q >= 1

  rank = q * (@count - 1)
  return 0.0 if rank < @zero_count

  acc = @zero_count
  @buckets.keys.sort.each do |i|
    acc += @buckets[i]
    # Clamped to observed bounds: a bucket's nominal value can fall slightly
    # outside [min, max], and a p99 above any observed value reads as a bug.
    return [[value_at(i), @min].max, @max].min if acc > rank
  end
  @max
end

#to_base64 ⇒ Object

Base64 of the binary form, which is how the agent ships it over JSON.



126
127
128
 
# File 'lib/sixty/sketch.rb', line 126

def to_base64
  Base64.strict_encode64(to_binary)
end

#to_binary ⇒ Object

Compact binary form: header + zigzag-varint delta-encoded buckets.



105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
# File 'lib/sixty/sketch.rb', line 105

def to_binary
  indices = @buckets.keys.sort
  body = +''.b
  prev = 0
  indices.each do |i|
    write_varint(body, zigzag(i - prev))
    write_varint(body, @buckets[i].round)
    prev = i
  end

  header = [MAGIC, VERSION].pack('C2')
  # 'E' is an IEEE-754 double, little-endian — the same layout DataView
  # writes with littleEndian = true.
  header += [@alpha, @zero_count.to_f, @sum.to_f,
             @count.zero? ? 0.0 : @min.to_f,
             @count.zero? ? 0.0 : @max.to_f].pack('E5')
  header += [indices.empty? ? 0 : 1].pack('C')
  header + body
end