exponential backoff broken with high values about redislock

[dim]

Excellent point, would you mind submit a PR with a fix?

[pierrre]

Actually, I'm not really a user of this library.
I'm implementing a similar library, which provides slightly different features (and I don't want to disturb you with these features).

I don't know how to fix the exponential backoff without breaking the backward compatibility of your library.

Here is my code.
It's not tested, because I'm still working on it.

// ExponentialRetry retries after an exponential delay.
// The delay is multiplied by two, up to the maximum value.
func ExponentialRetry(start, max time.Duration) RetryStrategy {
	return &exponentialRetry{
		d:   start,
		max: max,
	}
}

type exponentialRetry struct {
	d   time.Duration
	max time.Duration
}

func (r *exponentialRetry) Retry() (time.Duration, bool) {
	if r.d > r.max {
		return r.max, true
	}
	d := r.d
	r.d *= 2
	return d, true
}

Of course, it suffers from the same "overflow" issue, but the user will have to wait until the duration is reached, which can't happen, because the value is too high.
In your implementation the "multiply by 2" logic is always computed, even if the maximum is reached.

[dim]

So the idea there is to increase backoff using 2^n rather than n*2. It's only a theoretical problem though, as 2<<55 => 72057594037927936 which is 2.2 million years. I therefore doubt it would ever overflow :)

[pierrre]

The problem in this code is real

redislock/redislock.go

Lines 279 to 286 in 1b9b4ef

	r.cnt++
	if d := time.Duration(2<<r.cnt) * time.Millisecond; d < r.min {
	return r.min
	} else if r.max != 0 && d > r.max {
	return r.max
	} else {
	return d
	}

Let's say that r.max is equal to 1 second.
For the 53/54/55 retry you will have very high values, but it will be limited by the max value of 1 second.
For the 56th retry, you will start to have a negative value, so it will be limited by the min value.
For the 57th retry, the value will always be 0, so it will be limited by the min value.

You don't have to wait for a very long time if you want to trigger this bug, if the "max" limit is low enough.
It happens after the 56th retry.

[dim]

Addressed in #8, thanks for the report