1 //
2 //
3 // Copyright 2016 gRPC authors.
4 //
5 // Licensed under the Apache License, Version 2.0 (the "License");
6 // you may not use this file except in compliance with the License.
7 // You may obtain a copy of the License at
8 //
9 // http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
16 //
17 //
18
19 #include "src/core/lib/backoff/backoff.h"
20
21 #include <algorithm>
22 #include <memory>
23
24 #include "gtest/gtest.h"
25
26 #include <grpc/grpc.h>
27
28 #include "src/core/lib/gprpp/time.h"
29 #include "src/core/lib/iomgr/exec_ctx.h"
30 #include "test/core/util/test_config.h"
31
32 namespace grpc {
33 namespace testing {
34 namespace {
35
36 using grpc_core::BackOff;
37
TEST(BackOffTest,ConstantBackOff)38 TEST(BackOffTest, ConstantBackOff) {
39 const auto initial_backoff = grpc_core::Duration::Milliseconds(200);
40 const double multiplier = 1.0;
41 const double jitter = 0.0;
42 const auto max_backoff = grpc_core::Duration::Seconds(1);
43 grpc_core::ExecCtx exec_ctx;
44 BackOff::Options options;
45 options.set_initial_backoff(initial_backoff)
46 .set_multiplier(multiplier)
47 .set_jitter(jitter)
48 .set_max_backoff(max_backoff);
49 BackOff backoff(options);
50
51 grpc_core::Timestamp next_attempt_start_time = backoff.NextAttemptTime();
52 EXPECT_EQ(next_attempt_start_time - grpc_core::Timestamp::Now(),
53 initial_backoff);
54 for (int i = 0; i < 10000; i++) {
55 next_attempt_start_time = backoff.NextAttemptTime();
56 EXPECT_EQ(next_attempt_start_time - grpc_core::Timestamp::Now(),
57 initial_backoff);
58 }
59 }
60
TEST(BackOffTest,MinConnect)61 TEST(BackOffTest, MinConnect) {
62 const auto initial_backoff = grpc_core::Duration::Milliseconds(100);
63 const double multiplier = 1.0;
64 const double jitter = 0.0;
65 const auto max_backoff = grpc_core::Duration::Seconds(1);
66 grpc_core::ExecCtx exec_ctx;
67 BackOff::Options options;
68 options.set_initial_backoff(initial_backoff)
69 .set_multiplier(multiplier)
70 .set_jitter(jitter)
71 .set_max_backoff(max_backoff);
72 BackOff backoff(options);
73 grpc_core::Timestamp next = backoff.NextAttemptTime();
74 EXPECT_EQ(next - grpc_core::Timestamp::Now(), initial_backoff);
75 }
76
TEST(BackOffTest,NoJitterBackOff)77 TEST(BackOffTest, NoJitterBackOff) {
78 const auto initial_backoff = grpc_core::Duration::Milliseconds(2);
79 const double multiplier = 2.0;
80 const double jitter = 0.0;
81 const auto max_backoff = grpc_core::Duration::Milliseconds(513);
82 BackOff::Options options;
83 options.set_initial_backoff(initial_backoff)
84 .set_multiplier(multiplier)
85 .set_jitter(jitter)
86 .set_max_backoff(max_backoff);
87 BackOff backoff(options);
88 // x_1 = 2
89 // x_n = 2**i + x_{i-1} ( = 2**(n+1) - 2 )
90 grpc_core::ExecCtx exec_ctx;
91 grpc_core::ExecCtx::Get()->TestOnlySetNow(
92 grpc_core::Timestamp::FromMillisecondsAfterProcessEpoch(0));
93 grpc_core::Timestamp next = backoff.NextAttemptTime();
94 EXPECT_EQ(next, grpc_core::Timestamp::FromMillisecondsAfterProcessEpoch(2));
95 grpc_core::ExecCtx::Get()->TestOnlySetNow(next);
96 next = backoff.NextAttemptTime();
97 EXPECT_EQ(next, grpc_core::Timestamp::FromMillisecondsAfterProcessEpoch(6));
98 grpc_core::ExecCtx::Get()->TestOnlySetNow(next);
99 next = backoff.NextAttemptTime();
100 EXPECT_EQ(next, grpc_core::Timestamp::FromMillisecondsAfterProcessEpoch(14));
101 grpc_core::ExecCtx::Get()->TestOnlySetNow(next);
102 next = backoff.NextAttemptTime();
103 EXPECT_EQ(next, grpc_core::Timestamp::FromMillisecondsAfterProcessEpoch(30));
104 grpc_core::ExecCtx::Get()->TestOnlySetNow(next);
105 next = backoff.NextAttemptTime();
106 EXPECT_EQ(next, grpc_core::Timestamp::FromMillisecondsAfterProcessEpoch(62));
107 grpc_core::ExecCtx::Get()->TestOnlySetNow(next);
108 next = backoff.NextAttemptTime();
109 EXPECT_EQ(next, grpc_core::Timestamp::FromMillisecondsAfterProcessEpoch(126));
110 grpc_core::ExecCtx::Get()->TestOnlySetNow(next);
111 next = backoff.NextAttemptTime();
112 EXPECT_EQ(next, grpc_core::Timestamp::FromMillisecondsAfterProcessEpoch(254));
113 grpc_core::ExecCtx::Get()->TestOnlySetNow(next);
114 next = backoff.NextAttemptTime();
115 EXPECT_EQ(next, grpc_core::Timestamp::FromMillisecondsAfterProcessEpoch(510));
116 grpc_core::ExecCtx::Get()->TestOnlySetNow(next);
117 next = backoff.NextAttemptTime();
118 EXPECT_EQ(next,
119 grpc_core::Timestamp::FromMillisecondsAfterProcessEpoch(1022));
120 grpc_core::ExecCtx::Get()->TestOnlySetNow(next);
121 next = backoff.NextAttemptTime();
122 // Hit the maximum timeout. From this point onwards, retries will increase
123 // only by max timeout.
124 EXPECT_EQ(next,
125 grpc_core::Timestamp::FromMillisecondsAfterProcessEpoch(1535));
126 grpc_core::ExecCtx::Get()->TestOnlySetNow(next);
127 next = backoff.NextAttemptTime();
128 EXPECT_EQ(next,
129 grpc_core::Timestamp::FromMillisecondsAfterProcessEpoch(2048));
130 grpc_core::ExecCtx::Get()->TestOnlySetNow(next);
131 next = backoff.NextAttemptTime();
132 EXPECT_EQ(next,
133 grpc_core::Timestamp::FromMillisecondsAfterProcessEpoch(2561));
134 }
135
TEST(BackOffTest,JitterBackOff)136 TEST(BackOffTest, JitterBackOff) {
137 const auto initial_backoff = grpc_core::Duration::Milliseconds(500);
138 auto current_backoff = initial_backoff;
139 const auto max_backoff = grpc_core::Duration::Seconds(1);
140 const double multiplier = 1.0;
141 const double jitter = 0.1;
142 BackOff::Options options;
143 options.set_initial_backoff(initial_backoff)
144 .set_multiplier(multiplier)
145 .set_jitter(jitter)
146 .set_max_backoff(max_backoff);
147 BackOff backoff(options);
148
149 grpc_core::ExecCtx exec_ctx;
150 grpc_core::Timestamp next = backoff.NextAttemptTime();
151 EXPECT_EQ(next - grpc_core::Timestamp::Now(), initial_backoff);
152
153 auto expected_next_lower_bound = grpc_core::Duration::Milliseconds(
154 static_cast<double>(current_backoff.millis()) * (1 - jitter));
155 auto expected_next_upper_bound = grpc_core::Duration::Milliseconds(
156 static_cast<double>(current_backoff.millis()) * (1 + jitter));
157
158 for (int i = 0; i < 10000; i++) {
159 next = backoff.NextAttemptTime();
160 // next-now must be within (jitter*100)% of the current backoff (which
161 // increases by * multiplier up to max_backoff).
162 const grpc_core::Duration timeout_millis =
163 next - grpc_core::Timestamp::Now();
164 EXPECT_GE(timeout_millis, expected_next_lower_bound);
165 EXPECT_LE(timeout_millis, expected_next_upper_bound);
166 current_backoff = std::min(
167 grpc_core::Duration::Milliseconds(
168 static_cast<double>(current_backoff.millis()) * multiplier),
169 max_backoff);
170 expected_next_lower_bound = grpc_core::Duration::Milliseconds(
171 static_cast<double>(current_backoff.millis()) * (1 - jitter));
172 expected_next_upper_bound = grpc_core::Duration::Milliseconds(
173 static_cast<double>(current_backoff.millis()) * (1 + jitter));
174 }
175 }
176
177 } // namespace
178 } // namespace testing
179 } // namespace grpc
180
main(int argc,char ** argv)181 int main(int argc, char** argv) {
182 ::testing::InitGoogleTest(&argc, argv);
183 grpc::testing::TestEnvironment env(&argc, argv);
184 grpc_init();
185 int ret = RUN_ALL_TESTS();
186 grpc_shutdown();
187 return ret;
188 }
189