Which form of jitter is better: adding a random wait time to a predetermined wait time that grows exponentially with each retry attempt, or following something like [0] where every retry attempt increases the possible wait time choices and the "jitter" is to randomly pick one of them?
To illustrate the latter option, suppose the smallest retry time unit is 1 second. The first attempt gives you a random choice in {0, 1}. The second attempt gives you a random choice in {0, 1, 2}. The third attempt gives you a random choice in {0, 1, 2, 4}. The fourth attempt gives you a random choice in {0, 1, 2, 4, 8}. This goes on until a ceiling in the number of attempts or a set wall clock time is reached.
It depends on what you want. The first option will tend towards longer waits, and the second towards shorter waits.
I would tend towards increasing the minimum wait at each iteration (until you get to some maximim wait), because it it failed 10 times in the last minute, it's likely going to fail many times in the next minute, so we don't need to try more than once or twice.
Also: in case the client random is broken, you don't want to accidentaly end up with everyone retrying after zero seconds forever.
To illustrate the latter option, suppose the smallest retry time unit is 1 second. The first attempt gives you a random choice in {0, 1}. The second attempt gives you a random choice in {0, 1, 2}. The third attempt gives you a random choice in {0, 1, 2, 4}. The fourth attempt gives you a random choice in {0, 1, 2, 4, 8}. This goes on until a ceiling in the number of attempts or a set wall clock time is reached.
[0]: https://en.wikipedia.org/wiki/Exponential_backoff#Example_ex...