Skip to content

Commit 413d65f

Browse files
BenWhiteheadBenWhitehead
committed
chore: implement Backoff class to be used to calculate backoff between actions
ExponentialRetryAlgorithm in gax is implemented centered around unary rpcs. Because of this, we can't easily use it for our multiple operations within a single stream use case. Add Durations util class to make working with durations a bit easier.
1 parent 52639da commit 413d65f

File tree

4 files changed

+646
-0
lines changed

4 files changed

+646
-0
lines changed

‎google-cloud-storage/src/main/java/com/google/cloud/storage/Backoff.java‎

Lines changed: 328 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,328 @@
1+
/*
2+
* Copyright 2024 Google LLC
3+
*
4+
* Licensed under the Apache License, Version 2.0 (the "License");
5+
* you may not use this file except in compliance with the License.
6+
* You may obtain a copy of the License at
7+
*
8+
* http://www.apache.org/licenses/LICENSE-2.0
9+
*
10+
* Unless required by applicable law or agreed to in writing, software
11+
* distributed under the License is distributed on an "AS IS" BASIS,
12+
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13+
* See the License for the specific language governing permissions and
14+
* limitations under the License.
15+
*/
16+
17+
package com.google.cloud.storage;
18+
19+
import static com.google.common.base.Preconditions.checkArgument;
20+
import static com.google.common.base.Preconditions.checkState;
21+
import static java.time.Duration.ZERO;
22+
import static java.util.Objects.requireNonNull;
23+
24+
import com.google.api.gax.retrying.RetrySettings;
25+
import com.google.common.annotations.VisibleForTesting;
26+
import com.google.common.base.MoreObjects;
27+
import java.time.Duration;
28+
import java.util.Objects;
29+
import java.util.concurrent.ThreadLocalRandom;
30+
31+
/**
32+
* Encapsulated class to track a timeout and calculate a backoff.
33+
*
34+
* <p>Error tracking is explicitly not tracked here. This class only tracks elapsed duration and
35+
* timeout and whether there is budget for backoff.
36+
*
37+
* <p>This class does not use a clock, instead everything is tracked as durations provided by the
38+
* user. This has the advantage that tests of it and anything that depends on it are able to be 100%
39+
* reproducible.
40+
*
41+
* <p>This class also allows for a jittering algorithm to be provided to it, rather than being hard
42+
* coded against a random number generator like {@link ThreadLocalRandom}.
43+
*
44+
* <p>This class is not thread safe.
45+
*/
46+
final class Backoff {
47+
48+
private final Duration initialBackoff;
49+
private final Duration maxBackoff;
50+
private final Duration timeout;
51+
private final double retryDelayMultiplier;
52+
private final Jitterer jitterer;
53+
54+
private Duration cumulativeBackoff;
55+
private Duration previousBackoff;
56+
57+
private Backoff(
58+
Duration initialBackoff,
59+
double backoffDelayMultiplier,
60+
Duration maxBackoff,
61+
Duration timeout,
62+
Jitterer jitterer) {
63+
this.initialBackoff = initialBackoff;
64+
this.maxBackoff = maxBackoff;
65+
this.timeout = timeout;
66+
this.jitterer = jitterer;
67+
this.retryDelayMultiplier = backoffDelayMultiplier;
68+
this.cumulativeBackoff = ZERO;
69+
this.previousBackoff = ZERO;
70+
}
71+
72+
/**
73+
* Compute the next backoff given the provide {@code elapsed} duration between any previous
74+
* invocation and this one.
75+
*
76+
* <p>If there is remaining backoff budget, a backoff will be computed and returned as a {@link
77+
* BackoffDuration}. If the backoff budget doesn't have enough to allow for another backoff an
78+
* {@link BackoffResults#EXHAUSTED} will be returned.
79+
*
80+
* <p>{@code EXHAUSTED} can happen in the following circumstances
81+
*
82+
* <ol>
83+
* <li>If the existing {@link #cumulativeBackoff} + {@code elapsed} is >= {@link #timeout}
84+
* <li>If the existing {@link #cumulativeBackoff} + {@code elapsed} + {@code
85+
* nextBackoffDuration} is >= {@link #timeout}
86+
* </ol>
87+
*/
88+
BackoffResult nextBackoff(Duration elapsed) {
89+
checkArgument(
90+
Durations.gtEq(elapsed, ZERO), "elapsed must be >= PT0S (%s >= %s)", elapsed, ZERO);
91+
Duration cumulativeAndElapsed = cumulativeBackoff.plus(elapsed);
92+
93+
Duration nextDelay =
94+
Duration.ofNanos(Math.round(previousBackoff.toNanos() * retryDelayMultiplier));
95+
if (Durations.eq(nextDelay, ZERO)) {
96+
nextDelay = initialBackoff;
97+
}
98+
Duration nextBackoffWithJitter = jitterer.jitter(nextDelay);
99+
Duration cappedBackoff = Durations.min(nextBackoffWithJitter, maxBackoff);
100+
Duration newCumulativeElapsed = cumulativeAndElapsed.plus(cappedBackoff);
101+
cumulativeBackoff = newCumulativeElapsed;
102+
previousBackoff = cappedBackoff;
103+
104+
if (Durations.gtEq(newCumulativeElapsed, timeout)) {
105+
return BackoffResults.EXHAUSTED;
106+
} else {
107+
return BackoffDuration.of(cappedBackoff);
108+
}
109+
}
110+
111+
/**
112+
* If a backoff is interrupted (usually because of another error from a higher level), record how
113+
* much of the backoff actually happened.
114+
*/
115+
void backoffInterrupted(Duration consumedBackoff) {
116+
Duration unconsumedBackoff = previousBackoff.minus(consumedBackoff);
117+
cumulativeBackoff = cumulativeBackoff.minus(unconsumedBackoff);
118+
}
119+
120+
/**
121+
* Reset all state.
122+
*
123+
* <p>After calling this method, backoff durations will reset to their initial values.
124+
*/
125+
void reset() {
126+
cumulativeBackoff = ZERO;
127+
previousBackoff = ZERO;
128+
}
129+
130+
Duration getCumulativeBackoff() {
131+
return cumulativeBackoff;
132+
}
133+
134+
Duration getTimeout() {
135+
return timeout;
136+
}
137+
138+
@Override
139+
public boolean equals(Object o) {
140+
if (this == o) {
141+
return true;
142+
}
143+
if (!(o instanceof Backoff)) {
144+
return false;
145+
}
146+
Backoff backoff = (Backoff) o;
147+
return Double.compare(retryDelayMultiplier, backoff.retryDelayMultiplier) == 0
148+
&& Objects.equals(initialBackoff, backoff.initialBackoff)
149+
&& Objects.equals(maxBackoff, backoff.maxBackoff)
150+
&& Objects.equals(timeout, backoff.timeout)
151+
&& Objects.equals(jitterer, backoff.jitterer)
152+
&& Objects.equals(cumulativeBackoff, backoff.cumulativeBackoff);
153+
}
154+
155+
@Override
156+
public int hashCode() {
157+
return Objects.hash(
158+
initialBackoff, maxBackoff, timeout, retryDelayMultiplier, jitterer, cumulativeBackoff);
159+
}
160+
161+
@Override
162+
public String toString() {
163+
return MoreObjects.toStringHelper(this)
164+
.add("initialBackoff", initialBackoff)
165+
.add("maxBackoff", maxBackoff)
166+
.add("timeout", timeout)
167+
.add("retryDelayMultiplier", retryDelayMultiplier)
168+
.add("jitterer", jitterer)
169+
.add("cumulativeBackoff", cumulativeBackoff)
170+
.toString();
171+
}
172+
173+
/** Convenience method to create a Backoff from RetrySettings. */
174+
static Backoff.Builder from(RetrySettings retrySettings) {
175+
return newBuilder()
176+
.setInitialBackoff(retrySettings.getInitialRetryDelayDuration())
177+
.setRetryDelayMultiplier(retrySettings.getRetryDelayMultiplier())
178+
.setMaxBackoff(retrySettings.getMaxRetryDelayDuration())
179+
.setTimeout(retrySettings.getTotalTimeoutDuration());
180+
}
181+
182+
static Builder newBuilder() {
183+
return new Builder();
184+
}
185+
186+
static final class Builder {
187+
private Duration initialBackoff;
188+
private Duration maxBackoff;
189+
private Duration timeout;
190+
private double retryDelayMultiplier;
191+
private Jitterer jitterer;
192+
193+
private Builder() {}
194+
195+
Builder setInitialBackoff(Duration initialBackoff) {
196+
this.initialBackoff = initialBackoff;
197+
return this;
198+
}
199+
200+
Builder setMaxBackoff(Duration maxBackoff) {
201+
this.maxBackoff = maxBackoff;
202+
return this;
203+
}
204+
205+
Builder setTimeout(Duration timeout) {
206+
this.timeout = timeout;
207+
return this;
208+
}
209+
210+
Builder setRetryDelayMultiplier(double retryDelayMultiplier) {
211+
this.retryDelayMultiplier = retryDelayMultiplier;
212+
return this;
213+
}
214+
215+
Builder setJitterer(Jitterer jitterer) {
216+
this.jitterer = jitterer;
217+
return this;
218+
}
219+
220+
Backoff build() {
221+
checkState(retryDelayMultiplier >= 1.0, "retryDelayMultiplier must be >= 1.0");
222+
Duration effectiveTimeout = requireNonNull(timeout, "timeout must be non null");
223+
if (Durations.ltEq(effectiveTimeout, ZERO)) {
224+
effectiveTimeout = Durations.EFFECTIVE_INFINITY;
225+
}
226+
return new Backoff(
227+
requireNonNull(initialBackoff, "initialBackoff must be non null"),
228+
retryDelayMultiplier,
229+
requireNonNull(maxBackoff, "maxBackoff must be non null"),
230+
effectiveTimeout,
231+
requireNonNull(jitterer, "jitterer must be non null"));
232+
}
233+
}
234+
235+
interface BackoffResult {
236+
String errorString();
237+
}
238+
239+
enum BackoffResults implements BackoffResult {
240+
EXHAUSTED;
241+
242+
@Override
243+
public String errorString() {
244+
return name();
245+
}
246+
}
247+
248+
static final class BackoffDuration implements BackoffResult {
249+
private final Duration duration;
250+
251+
private BackoffDuration(Duration duration) {
252+
this.duration = duration;
253+
}
254+
255+
Duration getDuration() {
256+
return duration;
257+
}
258+
259+
@Override
260+
public String errorString() {
261+
return duration.toString();
262+
}
263+
264+
@Override
265+
public boolean equals(Object o) {
266+
if (this == o) {
267+
return true;
268+
}
269+
if (!(o instanceof BackoffDuration)) {
270+
return false;
271+
}
272+
BackoffDuration that = (BackoffDuration) o;
273+
return Objects.equals(duration, that.duration);
274+
}
275+
276+
@Override
277+
public int hashCode() {
278+
return Objects.hashCode(duration);
279+
}
280+
281+
@Override
282+
public String toString() {
283+
return MoreObjects.toStringHelper(this).add("duration", duration).toString();
284+
}
285+
286+
static BackoffDuration of(Duration duration) {
287+
return new BackoffDuration(duration);
288+
}
289+
}
290+
291+
/** Simple API to allow for the definition of a Jittering algorithm. */
292+
@FunctionalInterface
293+
interface Jitterer {
294+
Duration jitter(Duration baseline);
295+
296+
static Jitterer threadLocalRandom() {
297+
return ThreadLocalRandomJitterer.INSTANCE;
298+
}
299+
300+
@VisibleForTesting
301+
static Jitterer noJitter() {
302+
return NoJitter.INSTANCE;
303+
}
304+
}
305+
306+
private static final class ThreadLocalRandomJitterer implements Jitterer {
307+
private static final ThreadLocalRandomJitterer INSTANCE = new ThreadLocalRandomJitterer();
308+
309+
@Override
310+
public Duration jitter(Duration baseline) {
311+
if (Durations.gt(baseline, ZERO)) {
312+
long nanos = baseline.toNanos();
313+
long randNanos = ThreadLocalRandom.current().nextLong(nanos);
314+
return baseline.plusNanos(randNanos);
315+
}
316+
return baseline;
317+
}
318+
}
319+
320+
private static final class NoJitter implements Jitterer {
321+
private static final NoJitter INSTANCE = new NoJitter();
322+
323+
@Override
324+
public Duration jitter(Duration baseline) {
325+
return baseline;
326+
}
327+
}
328+
}

‎google-cloud-storage/src/main/java/com/google/cloud/storage/Durations.java‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
/*
2+
* Copyright 2024 Google LLC
3+
*
4+
* Licensed under the Apache License, Version 2.0 (the "License");
5+
* you may not use this file except in compliance with the License.
6+
* You may obtain a copy of the License at
7+
*
8+
* http://www.apache.org/licenses/LICENSE-2.0
9+
*
10+
* Unless required by applicable law or agreed to in writing, software
11+
* distributed under the License is distributed on an "AS IS" BASIS,
12+
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13+
* See the License for the specific language governing permissions and
14+
* limitations under the License.
15+
*/
16+
17+
package com.google.cloud.storage;
18+
19+
import java.time.Duration;
20+
21+
final class Durations {
22+
23+
/* {@code PT2562047H47M16.854775807S} ~ 106,751 days ~ 292.4 years */
24+
static final Duration EFFECTIVE_INFINITY = Duration.ofNanos(Long.MAX_VALUE);
25+
26+
private Durations() {}
27+
28+
static boolean eq(Duration lhs, Duration rhs) {
29+
return lhs.equals(rhs);
30+
}
31+
32+
static boolean ltEq(Duration lhs, Duration rhs) {
33+
return lhs.compareTo(rhs) <= 0;
34+
}
35+
36+
static boolean gtEq(Duration lhs, Duration rhs) {
37+
return lhs.compareTo(rhs) >= 0;
38+
}
39+
40+
static boolean gt(Duration lhs, Duration rhs) {
41+
return lhs.compareTo(rhs) > 0;
42+
}
43+
44+
static Duration min(Duration d1, Duration d2) {
45+
if (d1.compareTo(d2) < 0) {
46+
return d1;
47+
} else {
48+
return d2;
49+
}
50+
}
51+
}

0 commit comments

Comments
 (0)