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