fork of https://github.com/sourcegraph/zoekt
1package main
2
3import (
4 "testing"
5 "time"
6
7 "github.com/sourcegraph/log/logtest"
8)
9
10func TestQueue_BackoffOnFail(t *testing.T) {
11 backoffDuration := 1 * time.Millisecond
12 maxBackoffDuration := backoffDuration * 2
13
14 queue := NewQueue(backoffDuration, maxBackoffDuration, logtest.Scoped(t))
15 opts := IndexOptions{RepoID: 1, Name: "foo"}
16
17 queue.AddOrUpdate(opts)
18 emptyQueue(queue)
19
20 queue.SetIndexed(opts, indexStateFail)
21
22 bumpTime := time.Now()
23 queue.Bump([]uint32{opts.RepoID})
24
25 // item is disallowed from being pushed to heap during backoff period
26 if item, ok := queue.Pop(); ok {
27 qi := queue.items[item.RepoID]
28 if qi.backoff.backoffUntil.Before(bumpTime) {
29 t.Errorf("backoffDuration already passed before first attempt to push item to heap in Bump(). Increase backoffDuration for the Queue. backoffDuration: %s. maxBackoffDuration: %s.",
30 backoffDuration, maxBackoffDuration)
31 } else {
32 t.Fatal("queue should be empty")
33 }
34 }
35}
36
37func TestQueue_BackoffAllowAfterDuration(t *testing.T) {
38 backoffDuration := 1 * time.Millisecond
39 maxBackoffDuration := backoffDuration * 2
40
41 queue := NewQueue(backoffDuration, maxBackoffDuration, logtest.Scoped(t))
42 opts := IndexOptions{RepoID: 1, Name: "foo"}
43
44 queue.AddOrUpdate(opts)
45 emptyQueue(queue)
46
47 queue.SetIndexed(opts, indexStateFail)
48
49 if _, ok := queue.Pop(); ok {
50 t.Fatal("queue should be empty after SetIndexed")
51 }
52
53 time.Sleep(backoffDuration * 20)
54
55 queue.Bump([]uint32{opts.RepoID})
56
57 if _, ok := queue.Pop(); !ok {
58 t.Fatal("queue should no longer be empty after waiting for longer than the backoff duration and then bumping index options")
59 }
60}
61
62func TestQueue_ResetBackoffUntil(t *testing.T) {
63 backoffDuration := 1 * time.Hour
64 maxBackoffDuration := backoffDuration * 2
65
66 queue := NewQueue(backoffDuration, maxBackoffDuration, logtest.Scoped(t))
67 opts := IndexOptions{RepoID: 1, Name: "foo"}
68
69 queue.AddOrUpdate(opts)
70 emptyQueue(queue)
71
72 queue.SetIndexed(opts, indexStateFail)
73
74 if _, ok := queue.Pop(); ok {
75 t.Fatal("queue should be empty after SetIndexed")
76 }
77
78 queue.SetIndexed(opts, indexStateSuccess)
79
80 queue.Bump([]uint32{opts.RepoID})
81
82 if _, ok := queue.Pop(); !ok {
83 t.Fatal("queue should no longer be empty after resetting backoff until time to zero value")
84 }
85}
86
87func TestQueue_ResetFailuresCount(t *testing.T) {
88 backoffDuration := 1 * time.Millisecond
89 maxBackoffDuration := 1000 * time.Millisecond
90
91 queue := NewQueue(backoffDuration, maxBackoffDuration, logtest.Scoped(t))
92 opts := IndexOptions{RepoID: 1, Name: "foo"}
93
94 queue.AddOrUpdate(opts)
95 emptyQueue(queue)
96
97 // consecutive failures will push backoff until to a further out time
98 for i := 0; i < 1000; i++ {
99 queue.SetIndexed(opts, indexStateFail)
100 }
101
102 if _, ok := queue.Pop(); ok {
103 t.Fatal("queue should be empty after SetIndexed")
104 }
105
106 queue.SetIndexed(opts, indexStateSuccess)
107
108 queue.Bump([]uint32{opts.RepoID})
109
110 // backoff until is only one duration in the future after resetting consecutive failures count
111 queue.SetIndexed(opts, indexStateFail)
112
113 if _, ok := queue.Pop(); ok {
114 t.Fatal("queue should be empty after SetIndexed")
115 }
116
117 time.Sleep(backoffDuration)
118
119 queue.Bump([]uint32{opts.RepoID})
120
121 if _, ok := queue.Pop(); !ok {
122 t.Fatal("queue should no longer be empty after waiting a backoff duration for the first failure")
123 }
124}
125
126func TestQueue_MaxBackoffDuration(t *testing.T) {
127 backoffDuration := 1 * time.Hour
128 maxBackoffDuration := 1 * time.Millisecond
129
130 queue := NewQueue(backoffDuration, maxBackoffDuration, logtest.Scoped(t))
131 opts := IndexOptions{RepoID: 1, Name: "foo"}
132
133 queue.AddOrUpdate(opts)
134 emptyQueue(queue)
135
136 // consecutive failures increase duration up to a maximum
137 for i := 0; i < 100; i++ {
138 queue.SetIndexed(opts, indexStateFail)
139 }
140
141 if _, ok := queue.Pop(); ok {
142 t.Fatal("queue should be empty after SetIndexed")
143 }
144
145 // sleep past maxBackoffDuration but long before backoffDuration would pass
146 time.Sleep(maxBackoffDuration * 200)
147
148 queue.Bump([]uint32{opts.RepoID})
149
150 if _, ok := queue.Pop(); !ok {
151 t.Fatal("queue should no longer be empty after max backoff duration has passed")
152 }
153}
154
155func TestQueue_BackoffDisabled(t *testing.T) {
156 cases := []struct {
157 name string
158 backoffDuration time.Duration
159 maxBackoffDuration time.Duration
160 }{{
161 name: "negative backoff",
162 backoffDuration: -1 * time.Minute,
163 maxBackoffDuration: 1 * time.Minute,
164 }, {
165 name: "negative maximum backoff",
166 backoffDuration: 1 * time.Minute,
167 maxBackoffDuration: -1 * time.Minute,
168 }, {
169 name: "negative backoff and negative maximum backoff",
170 backoffDuration: -1 * time.Minute,
171 maxBackoffDuration: -1 * time.Minute,
172 }}
173
174 for _, tc := range cases {
175 t.Run(tc.name, func(t *testing.T) {
176 queue := NewQueue(tc.backoffDuration, tc.maxBackoffDuration, logtest.Scoped(t))
177 opts := IndexOptions{RepoID: 1, Name: "foo"}
178
179 queue.AddOrUpdate(opts)
180 emptyQueue(queue)
181 queue.SetIndexed(opts, indexStateFail)
182
183 queue.Bump([]uint32{opts.RepoID})
184
185 if _, ok := queue.Pop(); !ok {
186 t.Fatal("queue should not be empty after bump when backoff is disabled")
187 }
188 })
189 }
190}
191
192func TestBackoff_AllowByDefault(t *testing.T) {
193 backoffDuration := 1 * time.Minute
194 maxBackoffDuration := 2 * backoffDuration
195
196 backoff := backoff{
197 backoffDuration: backoffDuration,
198 maxBackoff: maxBackoffDuration,
199 }
200
201 now := time.Now()
202 assertAllow(t, now, backoff)
203}
204
205func TestBackoff_Disallow(t *testing.T) {
206 backoffDuration := 10 * time.Minute
207 maxBackoffDuration := 2 * backoffDuration
208 opts := IndexOptions{RepoID: 1, Name: "foo"}
209
210 backoff := backoff{
211 backoffDuration: backoffDuration,
212 maxBackoff: maxBackoffDuration,
213 }
214
215 now := time.Now()
216 backoff.Fail(now, logtest.Scoped(t), opts)
217 assertDisallow(t, now, backoff)
218}
219
220func TestBackoff_BackoffExpiration(t *testing.T) {
221 backoffDuration := 10 * time.Minute
222 maxBackoffDuration := 2 * backoffDuration
223 opts := IndexOptions{RepoID: 1, Name: "foo"}
224
225 backoff := backoff{
226 backoffDuration: backoffDuration,
227 maxBackoff: maxBackoffDuration,
228 }
229
230 now := time.Now()
231 backoff.Fail(now, logtest.Scoped(t), opts)
232 assertDisallow(t, now, backoff)
233
234 backoffUntil := now.Add(backoffDuration)
235 assertDisallow(t, backoffUntil, backoff)
236
237 // backoff not applied for any timestamp after backoff until
238 expiredBackoff := now.Add(backoffDuration + (1 * time.Nanosecond))
239 assertAllow(t, expiredBackoff, backoff)
240}
241
242func TestBackoff_ResetBackoffUntil(t *testing.T) {
243 backoffDuration := 10 * time.Minute
244 maxBackoffDuration := 2 * backoffDuration
245 opts := IndexOptions{RepoID: 1, Name: "foo"}
246
247 backoff := backoff{
248 backoffDuration: backoffDuration,
249 maxBackoff: maxBackoffDuration,
250 }
251
252 now := time.Now()
253 backoff.Fail(now, logtest.Scoped(t), opts)
254 assertDisallow(t, now, backoff)
255
256 backoff.Reset()
257 assertAllow(t, now, backoff)
258}
259
260func TestBackoff_MaximumBackoffUntil(t *testing.T) {
261 backoffDuration := 10 * time.Minute
262 maxBackoffDuration := 25 * time.Minute
263 opts := IndexOptions{RepoID: 1, Name: "foo"}
264
265 backoff := backoff{
266 backoffDuration: backoffDuration,
267 maxBackoff: maxBackoffDuration,
268 }
269
270 firstIndex := time.Now()
271 backoff.Fail(firstIndex, logtest.Scoped(t), opts)
272 currentBackoffUntil := backoffDuration
273
274 // disallowed before we pass backoff until timestamp
275 assertDisallow(t, firstIndex.Add(currentBackoffUntil-1*time.Minute), backoff)
276
277 secondIndex := firstIndex.Add(currentBackoffUntil + 1*time.Minute)
278 backoff.Fail(secondIndex, logtest.Scoped(t), opts)
279
280 // failures applies increased backoff duration due to consecutive failures
281 currentBackoffUntil += backoffDuration
282
283 // disallowed before we pass backoff until timestamp
284 assertDisallow(t, secondIndex.Add(currentBackoffUntil-1*time.Minute), backoff)
285
286 thirdIndex := secondIndex.Add(currentBackoffUntil + 1*time.Minute)
287 backoff.Fail(thirdIndex, logtest.Scoped(t), opts)
288
289 // This would be the new backoff until timestamp if we were not bounded by maxBackoffDuration
290 currentBackoffUntil += backoffDuration
291 // currentBackoffUntil is not applied since it exceeds maximum
292 assertAllow(t, thirdIndex.Add(currentBackoffUntil-1*time.Minute), backoff)
293
294 // Maximum backoff duration was applied
295 assertDisallow(t, thirdIndex.Add(maxBackoffDuration-1*time.Minute), backoff)
296}
297
298func TestBackoff_IncrementConsecutiveFailures(t *testing.T) {
299 failedCount := 5
300 backoffDuration := 1 * time.Minute
301 maxBackoffDuration := time.Duration(failedCount) * backoffDuration
302 opts := IndexOptions{RepoID: 1, Name: "foo"}
303
304 backoff := backoff{
305 backoffDuration: backoffDuration,
306 maxBackoff: maxBackoffDuration,
307 }
308
309 now := time.Now()
310 expectedFailuresCount := 0
311
312 for i := 0; i < failedCount; i++ {
313 backoff.Fail(now.Add(time.Duration(i)*backoffDuration), logtest.Scoped(t), opts)
314 expectedFailuresCount++
315 assertFailuresCount(t, expectedFailuresCount, backoff)
316 }
317}
318
319func TestBackoff_MaximumConsecutiveFailures(t *testing.T) {
320 maximumCount := 3
321 failedCount := 2 * maximumCount
322 backoffDuration := 1 * time.Minute
323 maxBackoffDuration := time.Duration(maximumCount) * backoffDuration
324 opts := IndexOptions{RepoID: 1, Name: "foo"}
325
326 backoff := backoff{
327 backoffDuration: backoffDuration,
328 maxBackoff: maxBackoffDuration,
329 }
330
331 now := time.Now()
332 expectedFailuresCount := 0
333
334 // consecutive failures count increments per failure
335 for i := 0; i < maximumCount; i++ {
336 backoff.Fail(now.Add(time.Duration(i)*backoffDuration), logtest.Scoped(t), opts)
337 expectedFailuresCount++
338 assertFailuresCount(t, expectedFailuresCount, backoff)
339 }
340
341 // consecutive failures count does not change
342 for i := maximumCount - 1; i < failedCount; i++ {
343 backoff.Fail(now.Add(time.Duration(i)*backoffDuration), logtest.Scoped(t), opts)
344 assertFailuresCount(t, expectedFailuresCount, backoff)
345 }
346}
347
348func TestBackoff_ResetConsecutiveFailures(t *testing.T) {
349 failedCount := 3
350 backoffDuration := 10 * time.Minute
351 maxBackoffDuration := time.Duration(failedCount) * backoffDuration
352 opts := IndexOptions{RepoID: 1, Name: "foo"}
353
354 backoff := backoff{
355 backoffDuration: backoffDuration,
356 maxBackoff: maxBackoffDuration,
357 }
358
359 for i := 0; i < failedCount; i++ {
360 now := time.Now()
361
362 // fail j consecutive times
363 for j := i; j <= i; j++ {
364 backoff.Fail(now.Add(time.Duration(j)*backoffDuration), logtest.Scoped(t), opts)
365 }
366
367 // reset behavior is independent of current consecutiveFailures count
368 backoff.Reset()
369 assertFailuresCount(t, 0, backoff)
370 }
371}
372
373func assertAllow(t *testing.T, now time.Time, b backoff) {
374 if indexingAllowed := b.Allow(now); !indexingAllowed {
375 t.Errorf("Indexing is not allowed to proceed by default at %s due to backing off until %s",
376 now, b.backoffUntil)
377 }
378}
379
380func assertDisallow(t *testing.T, now time.Time, b backoff) {
381 if indexingAllowed := b.Allow(now); indexingAllowed {
382 t.Errorf("Indexing is allowed to proceed at %s after failure despite being set to backoff until %s",
383 now, b.backoffUntil)
384 }
385}
386
387func assertFailuresCount(t *testing.T, expected int, b backoff) {
388 if failuresCount := b.consecutiveFailures; failuresCount != expected {
389 t.Errorf("Item currently tracks %d consecutive failures when expected consecutive failures count is %d",
390 failuresCount, expected)
391 }
392}
393
394func emptyQueue(q *Queue) {
395 for ok := true; ok; _, ok = q.Pop() {
396 }
397}