Backoff algorithm is still not very good

[bboreham]

Here's a list of gaps observed in a querier trace, between DynamoDB.BatchGetItemPages that errored:

First one: 100ms, 190ms, 180ms, 200ms, 660ms, 2050ms
Next one: 60ms, 140ms, 250ms, 170ms, 440ms
Next one: 10ms, 160ms, 290ms, 600ms, 140ms, 100ms, 3880ms
Next one: 40ms, 60ms, 120ms, 370ms, 1240ms

All of this is consistent with the implementation, which picks a random number within a range that doubles, but it doesn't feel right. I think we should have a base number that doubles, and add a few milliseconds for jitter.

Next issue is that calls that return unprocessed errors also increase the backoff. Since we commonly get a number of ProvisionedThroughputExceeded errors followed by a number of calls with unprocessed keys, we crank the delay up to tens of seconds.

I think we should reset the backoff as long as there is no error, and eliminate WaitWithoutCounting().

Finally I would drop the max backoff time from 50 seconds - it's too long compared to the default write context timeout of 1 minute, also compared to the typical time an end-user will wait for a query. Say 20 seconds?

So the base times would be:
100ms, 200ms, 400ms, 800ms, 1.6s, 3.2s, 6.4s, 12.8s, 20s, 20s, 20s, 20s, 20s, 20s, 20s, 20s, 20s, 20s, 20s

Typical retries in a 1 minute timeout, if they all error ~9
Total time to get to MaxRetries=20 ~6 minutes.

[bboreham]

gRPC has a backoff strategy more like what I was proposing: https://github.com/grpc/grpc/blob/master/doc/connection-backoff.md

(although that's for connections, so has much larger timeouts than we want for DB calls)

[bboreham]

I think the code would be a lot simpler if it was implemented as a Retryer instead of re-coding the whole retry loop.

[bboreham]

In #1131 I used a rate-limiter to delay if the request is throttled, which empirically works quite nicely.
The more throttling the slower it goes.

[pracucci]

I personally find the backoff-min-period misleading, cause it doesn't do what it states to do "Minimum delay when backing off". With the current "Full jitter" implementation there's no way to enforce any min period.

I think we should have a base number that doubles, and add a few milliseconds for jitter.

Have you had any further discussion about it? Interested in re-evaluating it?

[bboreham]

#1131 is pretty good for writes. I think I didn’t do reads because I’d need to fix up the auto-scaling code but it’s a logical next step.

For the other places we use backoff, I still think my suggestions in this issue are reasonable.

[gouthamve]

Fixed in #1599