Automattic / kue

Kue is a priority job queue backed by redis, built for node.js.
http://automattic.github.io/kue
MIT License
9.45k stars 862 forks source link

Exponential Backoff Implementation Gives Unusually High Increment per Attempt #1111

Open jkcdarunday opened 6 years ago

jkcdarunday commented 6 years ago
Introduction

I observed that the delays when using exponential backoff seems rather odd to me as it seems to be returning results that are too high. For example, the ff. will be the delays for 10 attempts given that the initial delay is 2000 milliseconds (with the value in the parenthesis as the total delay).

File used to generate results: https://gist.github.com/jkcdarunday/6b6ea98718e8c3bab1ee909e4033482d

Results
Attempt 1: 2s (2s)
Attempt 2: 1s (3s)
Attempt 3: 1.5s (4.5s)
Attempt 4: 5.25s (9.75s)
Attempt 5: 39.375s (49.125s)
Attempt 6: 610.313s (659.438s)
Attempt 7: 19224.86s (19884.298s)
Attempt 8: 1220778.61s (1240662.908s)
Attempt 9: 155649272.775s (156889935.683s)
Attempt 10: 39768389194.013s (39925279129.696s)
Observations

It jumped significantly from 10m10s in Attempt 6 to 5h20m in Attempt 7. This goes further to Attempt 8 where it suddenly became a 14 day delay.

Expectation

Increase in delay per attempt should only be around 2-3 times. i.e. 5h to 10h, not 5h to 14 days.

Thoughts

I think the function did not put into consideration that the delay value is updated every time with the result of the backoff function and expected that the delay would always be the initial delay. This results in the delay being multiplied by 2 then by 4 then by 8 then by 16 which builds up quickly.

I believe that if we leave the delay as always 2000 in the example above, we'll get more plausible results.

Doing so, we get the following which looks closer to exponential growth:

Attempt 1: 2s (2s)
Attempt 2: 1s (3s)
Attempt 3: 3s (6s)
Attempt 4: 7s (13s)
Attempt 5: 15s (28s)
Attempt 6: 31s (59s)
Attempt 7: 63s (122s)
Attempt 8: 127s (249s)
Attempt 9: 255s (504s)
Attempt 10: 511s (1015s)
Attempt 11: 1023s (2038s)
Attempt 12: 2047s (4085s)
Attempt 13: 4095s (8180s)
Attempt 14: 8191s (16371s)
Attempt 15: 16383s (32754s)