-
Notifications
You must be signed in to change notification settings - Fork 1.4k
/
pacer.go
297 lines (261 loc) · 10.5 KB
/
pacer.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
package vegeta
import (
"fmt"
"math"
"time"
)
// A Pacer defines the rate of hits during an Attack.
type Pacer interface {
// Pace returns the duration an Attacker should wait until
// hitting the next Target, given an already elapsed duration and
// completed hits. If the second return value is true, an attacker
// should stop sending hits.
Pace(elapsed time.Duration, hits uint64) (wait time.Duration, stop bool)
// Rate returns a Pacer's instantaneous hit rate (per seconds)
// at the given elapsed duration of an attack.
Rate(elapsed time.Duration) float64
}
// A PacerFunc is a function adapter type that implements
// the Pacer interface.
type PacerFunc func(time.Duration, uint64) (time.Duration, bool)
// Pace implements the Pacer interface.
func (pf PacerFunc) Pace(elapsed time.Duration, hits uint64) (time.Duration, bool) {
return pf(elapsed, hits)
}
// A ConstantPacer defines a constant rate of hits for the target.
type ConstantPacer struct {
Freq int // Frequency (number of occurrences) per ...
Per time.Duration // Time unit, usually 1s
}
// Rate is a type alias for ConstantPacer for backwards-compatibility.
type Rate = ConstantPacer
// ConstantPacer satisfies the Pacer interface.
var _ Pacer = ConstantPacer{}
// String returns a pretty-printed description of the ConstantPacer's behaviour:
// ConstantPacer{Freq: 1, Per: time.Second} => Constant{1 hits/1s}
func (cp ConstantPacer) String() string {
return fmt.Sprintf("Constant{%d hits/%s}", cp.Freq, cp.Per)
}
// Pace determines the length of time to sleep until the next hit is sent.
func (cp ConstantPacer) Pace(elapsed time.Duration, hits uint64) (time.Duration, bool) {
switch {
case cp.Per == 0 || cp.Freq == 0:
return 0, false // Zero value = infinite rate
case cp.Per < 0 || cp.Freq < 0:
return 0, true
}
expectedHits := uint64(cp.Freq) * uint64(elapsed/cp.Per)
if hits < expectedHits {
// Running behind, send next hit immediately.
return 0, false
}
interval := uint64(cp.Per.Nanoseconds() / int64(cp.Freq))
if math.MaxInt64/interval < hits {
// We would overflow delta if we continued, so stop the attack.
return 0, true
}
delta := time.Duration((hits + 1) * interval)
// Zero or negative durations cause time.Sleep to return immediately.
return delta - elapsed, false
}
// Rate returns a ConstantPacer's instantaneous hit rate (i.e. requests per second)
// at the given elapsed duration of an attack. Since it's constant, the return
// value is independent of the given elapsed duration.
func (cp ConstantPacer) Rate(elapsed time.Duration) float64 {
return cp.hitsPerNs() * 1e9
}
// hitsPerNs returns the attack rate this ConstantPacer represents, in
// fractional hits per nanosecond.
func (cp ConstantPacer) hitsPerNs() float64 {
return float64(cp.Freq) / float64(cp.Per)
}
const (
// MeanUp is a SinePacer Offset that causes the attack to start
// at the Mean attack rate and increase towards the peak.
MeanUp float64 = 0
// Peak is a SinePacer Offset that causes the attack to start
// at the peak (maximum) attack rate and decrease towards the Mean.
Peak = math.Pi / 2
// MeanDown is a SinePacer Offset that causes the attack to start
// at the Mean attack rate and decrease towards the trough.
MeanDown = math.Pi
// Trough is a SinePacer Offset that causes the attack to start
// at the trough (minimum) attack rate and increase towards the Mean.
Trough = 3 * math.Pi / 2
)
// SinePacer is a Pacer that describes attack request rates with the equation:
// R = MA sin(O+(2𝛑/P)t)
// Where:
// R = Instantaneous attack rate at elapsed time t, hits per nanosecond
// M = Mean attack rate over period P, sp.Mean, hits per nanosecond
// A = Amplitude of sine wave, sp.Amp, hits per nanosecond
// O = Offset of sine wave, sp.StartAt, radians
// P = Period of sine wave, sp.Period, nanoseconds
// t = Elapsed time since attack start, nanoseconds
//
// Many thanks to http://ascii.co.uk/art/sine and "sps" for the ascii here :-)
//
// Mean -| ,-'''-.
// +Amp | ,-' | `-.
// | ,' | `. O=𝛑
// | ,' O=𝛑/2 `. MeanDown
// | / Peak \ /
// |/ \ /
// Mean -+-------------------------\--------------------------> t
// |\ \ /
// | \ \ O=3𝛑/2 /
// | O=0 `. Trough ,'
// | MeanUp `. | ,'
// Mean | `-. | ,-'
// -Amp -| `-,,,-'
// |<-------------------- Period --------------------->|
//
// This equation is integrated with respect to time to derive the expected
// number of hits served at time t after the attack began:
// H = Mt - (AP/2𝛑)cos(O+(2𝛑/P)t) + (AP/2𝛑)cos(O)
// Where:
// H = Total number of hits triggered during t
type SinePacer struct {
// The period of the sine wave, e.g. 20*time.Minute
// MUST BE > 0
Period time.Duration
// The mid-point of the sine wave in freq-per-Duration,
// MUST BE > 0
Mean Rate
// The amplitude of the sine wave in freq-per-Duration,
// MUST NOT BE EQUAL TO OR LARGER THAN MEAN
Amp Rate
// The offset, in radians, for the sine wave at t=0.
StartAt float64
}
// SinePacer satisfies the Pacer interface.
var _ Pacer = SinePacer{}
// String returns a pretty-printed description of the SinePacer's behaviour:
// SinePacer{
// Period: time.Hour,
// Mean: Rate{100, time.Second},
// Amp: Rate{50, time.Second},
// StartAt: MeanDown,
// } =>
// Sine{Constant{100 hits/1s} ± Constant{50 hits/1s} / 1h, offset 1𝛑}
func (sp SinePacer) String() string {
return fmt.Sprintf("Sine{%s ± %s / %s, offset %g𝛑}", sp.Mean, sp.Amp, sp.Period, sp.StartAt/math.Pi)
}
// invalid tests the constraints documented in the SinePacer struct definition.
func (sp SinePacer) invalid() bool {
return sp.Period <= 0 || sp.Mean.hitsPerNs() <= 0 || sp.Amp.hitsPerNs() >= sp.Mean.hitsPerNs()
}
// Pace determines the length of time to sleep until the next hit is sent.
func (sp SinePacer) Pace(elapsedTime time.Duration, elapsedHits uint64) (time.Duration, bool) {
if sp.invalid() {
// If the SinePacer configuration is invalid, stop the attack.
return 0, true
}
expectedHits := sp.hits(elapsedTime)
if elapsedHits < uint64(expectedHits) {
// Running behind, send next hit immediately.
return 0, false
}
// Re-arranging our hits equation to provide a duration given the number of
// requests sent is non-trivial, so we must solve for the duration numerically.
// math.Round() added here because we have to coerce to int64 nanoseconds
// at some point and it corrects a bunch of off-by-one problems.
nsPerHit := math.Round(1 / sp.hitsPerNs(elapsedTime))
hitsToWait := float64(elapsedHits+1) - expectedHits
nextHitIn := time.Duration(nsPerHit * hitsToWait)
// If we can't converge to an error of <1e-3 within 5 iterations, bail.
// This rarely even loops for any large Period if hitsToWait is small.
for i := 0; i < 5; i++ {
hitsAtGuess := sp.hits(elapsedTime + nextHitIn)
err := float64(elapsedHits+1) - hitsAtGuess
if math.Abs(err) < 1e-3 {
return nextHitIn, false
}
nextHitIn = time.Duration(float64(nextHitIn) / (hitsAtGuess - float64(elapsedHits)))
}
return nextHitIn, false
}
// Rate returns a SinePacer's instantaneous hit rate (i.e. requests per second)
// at the given elapsed duration of an attack.
func (sp SinePacer) Rate(elapsed time.Duration) float64 {
return sp.hitsPerNs(elapsed) * 1e9
}
// ampHits returns AP/2𝛑, which is the number of hits added or subtracted
// from the Mean due to the Amplitude over a quarter of the Period,
// i.e. from 0 → 𝛑/2 radians
func (sp SinePacer) ampHits() float64 {
return (sp.Amp.hitsPerNs() * float64(sp.Period)) / (2 * math.Pi)
}
// radians converts the elapsed attack time to a radian value.
// The elapsed time t is divided by the wave period, multiplied by 2𝛑 to
// convert to radians, and offset by StartAt radians.
func (sp SinePacer) radians(t time.Duration) float64 {
return sp.StartAt + float64(t)*2*math.Pi/float64(sp.Period)
}
// hitsPerNs calculates the instantaneous rate of attack at
// t nanoseconds after the attack began.
// R = MA sin(O+(2𝛑/P)t)
func (sp SinePacer) hitsPerNs(t time.Duration) float64 {
return sp.Mean.hitsPerNs() + sp.Amp.hitsPerNs()*math.Sin(sp.radians(t))
}
// hits returns the number of hits that have been sent during an attack
// lasting t nanoseconds. It returns a float so we can tell exactly how
// much we've missed our target by when solving numerically in Pace.
// H = Mt - (AP/2𝛑)cos(O+(2𝛑/P)t) + (AP/2𝛑)cos(O)
// This re-arranges to:
// H = Mt + (AP/2𝛑)(cos(O) - cos(O+(2𝛑/P)t))
func (sp SinePacer) hits(t time.Duration) float64 {
if t <= 0 || sp.invalid() {
return 0
}
return sp.Mean.hitsPerNs()*float64(t) + sp.ampHits()*(math.Cos(sp.StartAt)-math.Cos(sp.radians(t)))
}
// LinearPacer paces an attack by starting at a given request rate
// and increasing linearly with the given slope.
type LinearPacer struct {
StartAt Rate
Slope float64
}
// Pace determines the length of time to sleep until the next hit is sent.
func (p LinearPacer) Pace(elapsed time.Duration, hits uint64) (time.Duration, bool) {
switch {
case p.StartAt.Per == 0 || p.StartAt.Freq == 0:
return 0, false // Zero value = infinite rate
case p.StartAt.Per < 0 || p.StartAt.Freq < 0:
return 0, true
}
expectedHits := p.hits(elapsed)
if hits == 0 || hits < uint64(expectedHits) {
// Running behind, send next hit immediately.
return 0, false
}
rate := p.Rate(elapsed)
interval := math.Round(1e9 / rate)
if n := uint64(interval); n != 0 && math.MaxInt64/n < hits {
// We would overflow wait if we continued, so stop the attack.
return 0, true
}
delta := float64(hits+1) - expectedHits
wait := time.Duration(interval * delta)
return wait, false
}
// Rate returns a LinearPacer's instantaneous hit rate (i.e. requests per second)
// at the given elapsed duration of an attack.
func (p LinearPacer) Rate(elapsed time.Duration) float64 {
a := p.Slope
x := elapsed.Seconds()
b := p.StartAt.hitsPerNs() * 1e9
return a*x + b
}
// hits returns the number of hits that have been sent during an attack
// lasting t nanoseconds. It returns a float so we can tell exactly how
// much we've missed our target by when solving numerically in Pace.
func (p LinearPacer) hits(t time.Duration) float64 {
if t < 0 {
return 0
}
a := p.Slope
b := p.StartAt.hitsPerNs() * 1e9
x := t.Seconds()
return (a*math.Pow(x, 2))/2 + b*x
}