]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | /* |
2 | * This file is open source software, licensed to you under the terms | |
3 | * of the Apache License, Version 2.0 (the "License"). See the NOTICE file | |
4 | * distributed with this work for additional information regarding copyright | |
5 | * ownership. You may not use this file except in compliance with the License. | |
6 | * | |
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, | |
12 | * software distributed under the License is distributed on an | |
13 | * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY | |
14 | * KIND, either express or implied. See the License for the | |
15 | * specific language governing permissions and limitations | |
16 | * under the License. | |
17 | */ | |
18 | ||
19 | /* | |
20 | * Copyright (C) 2016 ScyllaDB | |
21 | */ | |
22 | ||
23 | #include <seastar/core/thread.hh> | |
11fdf7f2 | 24 | #include <seastar/testing/test_case.hh> |
9f95a23c TL |
25 | #include <seastar/testing/thread_test_case.hh> |
26 | #include <seastar/testing/test_runner.hh> | |
11fdf7f2 | 27 | #include <seastar/core/sstring.hh> |
11fdf7f2 TL |
28 | #include <seastar/core/fair_queue.hh> |
29 | #include <seastar/core/do_with.hh> | |
f67539c2 | 30 | #include <seastar/util/later.hh> |
11fdf7f2 | 31 | #include <seastar/core/sleep.hh> |
9f95a23c | 32 | #include <seastar/core/print.hh> |
11fdf7f2 | 33 | #include <boost/range/irange.hpp> |
11fdf7f2 TL |
34 | #include <chrono> |
35 | ||
36 | using namespace seastar; | |
37 | using namespace std::chrono_literals; | |
38 | ||
9f95a23c | 39 | struct request { |
f67539c2 | 40 | fair_queue_ticket fqdesc; |
9f95a23c TL |
41 | unsigned index; |
42 | ||
43 | request(unsigned weight, unsigned index) | |
44 | : fqdesc({weight, 0}) | |
45 | , index(index) | |
11fdf7f2 | 46 | {} |
9f95a23c | 47 | }; |
11fdf7f2 | 48 | |
9f95a23c TL |
49 | |
50 | class test_env { | |
51 | fair_queue _fq; | |
52 | std::vector<int> _results; | |
53 | std::vector<std::vector<std::exception_ptr>> _exceptions; | |
54 | std::vector<priority_class_ptr> _classes; | |
55 | std::vector<request> _inflight; | |
56 | ||
57 | void drain() { | |
58 | do {} while (tick() != 0); | |
59 | } | |
60 | public: | |
61 | test_env(unsigned capacity) : _fq(capacity) | |
62 | {} | |
63 | ||
64 | // As long as there is a request sitting in the queue, tick() will process | |
65 | // at least one request. The only situation in which tick() will return nothing | |
66 | // is if no requests were sent to the fair_queue (obviously). | |
67 | // | |
68 | // Because of this property, one useful use of tick() is to implement a drain() | |
69 | // method (see above) in which all requests currently sent to the queue are drained | |
70 | // before the queue is destroyed. | |
71 | unsigned tick(unsigned n = 1) { | |
72 | unsigned processed = 0; | |
73 | _fq.dispatch_requests(); | |
74 | ||
75 | for (unsigned i = 0; i < n; ++i) { | |
76 | std::vector<request> curr; | |
77 | curr.swap(_inflight); | |
78 | ||
79 | for (auto& req : curr) { | |
80 | processed++; | |
81 | _results[req.index]++; | |
82 | _fq.notify_requests_finished(req.fqdesc); | |
83 | } | |
84 | ||
85 | _fq.dispatch_requests(); | |
86 | } | |
87 | return processed; | |
11fdf7f2 TL |
88 | } |
89 | ||
9f95a23c TL |
90 | ~test_env() { |
91 | drain(); | |
92 | for (auto& p: _classes) { | |
93 | _fq.unregister_priority_class(p); | |
94 | } | |
95 | } | |
96 | ||
97 | size_t register_priority_class(uint32_t shares) { | |
98 | _results.push_back(0); | |
99 | _exceptions.push_back(std::vector<std::exception_ptr>()); | |
100 | _classes.push_back(_fq.register_priority_class(shares)); | |
101 | return _classes.size() - 1; | |
102 | } | |
11fdf7f2 | 103 | |
9f95a23c TL |
104 | void do_op(unsigned index, unsigned weight) { |
105 | auto cl = _classes[index]; | |
106 | auto req = request(weight, index); | |
11fdf7f2 | 107 | |
9f95a23c | 108 | _fq.queue(cl, req.fqdesc, [this, index, req] () mutable noexcept { |
11fdf7f2 | 109 | try { |
9f95a23c | 110 | _inflight.push_back(std::move(req)); |
11fdf7f2 | 111 | } catch (...) { |
9f95a23c TL |
112 | auto eptr = std::current_exception(); |
113 | _exceptions[index].push_back(eptr); | |
114 | _fq.notify_requests_finished(req.fqdesc); | |
11fdf7f2 TL |
115 | } |
116 | }); | |
11fdf7f2 | 117 | } |
9f95a23c | 118 | |
11fdf7f2 | 119 | void update_shares(unsigned index, uint32_t shares) { |
9f95a23c | 120 | auto cl = _classes[index]; |
f67539c2 | 121 | cl->update_shares(shares); |
11fdf7f2 | 122 | } |
9f95a23c TL |
123 | |
124 | void reset_results(unsigned index) { | |
125 | _results[index] = 0; | |
126 | } | |
127 | ||
11fdf7f2 TL |
128 | // Verify if the ratios are what we expect. Because we can't be sure about |
129 | // precise timing issues, we can always be off by some percentage. In simpler | |
130 | // tests we really expect it to very low, but in more complex tests, with share | |
131 | // changes, for instance, they can accumulate | |
132 | // | |
133 | // The ratios argument is the ratios towards the first class | |
9f95a23c TL |
134 | void verify(sstring name, std::vector<unsigned> ratios, unsigned expected_error = 1) { |
135 | assert(ratios.size() == _results.size()); | |
136 | auto str = name + ":"; | |
137 | for (auto i = 0ul; i < _results.size(); ++i) { | |
138 | str += format(" r[{:d}] = {:d}", i, _results[i]); | |
139 | } | |
140 | std::cout << str << std::endl; | |
141 | for (auto i = 0ul; i < ratios.size(); ++i) { | |
142 | int min_expected = ratios[i] * (_results[0] - expected_error); | |
143 | int max_expected = ratios[i] * (_results[0] + expected_error); | |
144 | BOOST_REQUIRE(_results[i] >= min_expected); | |
145 | BOOST_REQUIRE(_results[i] <= max_expected); | |
146 | BOOST_REQUIRE(_exceptions[i].size() == 0); | |
147 | } | |
11fdf7f2 TL |
148 | } |
149 | }; | |
150 | ||
151 | // Equal ratios. Expected equal results. | |
9f95a23c TL |
152 | SEASTAR_THREAD_TEST_CASE(test_fair_queue_equal_2classes) { |
153 | test_env env(1); | |
11fdf7f2 | 154 | |
9f95a23c TL |
155 | auto a = env.register_priority_class(10); |
156 | auto b = env.register_priority_class(10); | |
11fdf7f2 TL |
157 | |
158 | for (int i = 0; i < 100; ++i) { | |
9f95a23c TL |
159 | env.do_op(a, 1); |
160 | env.do_op(b, 1); | |
11fdf7f2 | 161 | } |
9f95a23c TL |
162 | |
163 | later().get(); | |
164 | // allow half the requests in | |
165 | env.tick(100); | |
166 | env.verify("equal_2classes", {1, 1}); | |
11fdf7f2 TL |
167 | } |
168 | ||
169 | // Equal results, spread among 4 classes. | |
9f95a23c TL |
170 | SEASTAR_THREAD_TEST_CASE(test_fair_queue_equal_4classes) { |
171 | test_env env(1); | |
11fdf7f2 | 172 | |
9f95a23c TL |
173 | auto a = env.register_priority_class(10); |
174 | auto b = env.register_priority_class(10); | |
175 | auto c = env.register_priority_class(10); | |
176 | auto d = env.register_priority_class(10); | |
11fdf7f2 TL |
177 | |
178 | for (int i = 0; i < 100; ++i) { | |
9f95a23c TL |
179 | env.do_op(a, 1); |
180 | env.do_op(b, 1); | |
181 | env.do_op(c, 1); | |
182 | env.do_op(d, 1); | |
11fdf7f2 | 183 | } |
9f95a23c TL |
184 | later().get(); |
185 | // allow half the requests in | |
186 | env.tick(200); | |
187 | env.verify("equal_4classes", {1, 1, 1, 1}); | |
11fdf7f2 TL |
188 | } |
189 | ||
190 | // Class2 twice as powerful. Expected class2 to have 2 x more requests. | |
9f95a23c TL |
191 | SEASTAR_THREAD_TEST_CASE(test_fair_queue_different_shares) { |
192 | test_env env(1); | |
11fdf7f2 | 193 | |
9f95a23c TL |
194 | auto a = env.register_priority_class(10); |
195 | auto b = env.register_priority_class(20); | |
11fdf7f2 TL |
196 | |
197 | for (int i = 0; i < 100; ++i) { | |
9f95a23c TL |
198 | env.do_op(a, 1); |
199 | env.do_op(b, 1); | |
11fdf7f2 | 200 | } |
9f95a23c TL |
201 | later().get(); |
202 | // allow half the requests in | |
203 | env.tick(100); | |
204 | return env.verify("different_shares", {1, 2}); | |
11fdf7f2 TL |
205 | } |
206 | ||
207 | // Equal ratios, high capacity queue. Should still divide equally. | |
208 | // | |
209 | // Note that we sleep less because now more requests will be going through the | |
210 | // queue. | |
9f95a23c TL |
211 | SEASTAR_THREAD_TEST_CASE(test_fair_queue_equal_hi_capacity_2classes) { |
212 | test_env env(10); | |
11fdf7f2 | 213 | |
9f95a23c TL |
214 | auto a = env.register_priority_class(10); |
215 | auto b = env.register_priority_class(10); | |
11fdf7f2 TL |
216 | |
217 | for (int i = 0; i < 100; ++i) { | |
9f95a23c TL |
218 | env.do_op(a, 1); |
219 | env.do_op(b, 1); | |
11fdf7f2 | 220 | } |
9f95a23c | 221 | later().get(); |
11fdf7f2 | 222 | |
9f95a23c TL |
223 | // queue has capacity 10, 10 x 10 = 100, allow half the requests in |
224 | env.tick(10); | |
225 | env.verify("hi_capacity_2classes", {1, 1}); | |
11fdf7f2 TL |
226 | } |
227 | ||
228 | // Class2 twice as powerful, queue is high capacity. Still expected class2 to | |
229 | // have 2 x more requests. | |
230 | // | |
231 | // Note that we sleep less because now more requests will be going through the | |
232 | // queue. | |
9f95a23c TL |
233 | SEASTAR_THREAD_TEST_CASE(test_fair_queue_different_shares_hi_capacity) { |
234 | test_env env(10); | |
11fdf7f2 | 235 | |
9f95a23c TL |
236 | auto a = env.register_priority_class(10); |
237 | auto b = env.register_priority_class(20); | |
11fdf7f2 TL |
238 | |
239 | for (int i = 0; i < 100; ++i) { | |
9f95a23c TL |
240 | env.do_op(a, 1); |
241 | env.do_op(b, 1); | |
11fdf7f2 | 242 | } |
9f95a23c TL |
243 | later().get(); |
244 | // queue has capacity 10, 10 x 10 = 100, allow half the requests in | |
245 | env.tick(10); | |
246 | env.verify("different_shares_hi_capacity", {1, 2}); | |
11fdf7f2 TL |
247 | } |
248 | ||
249 | // Classes equally powerful. But Class1 issues twice as expensive requests. Expected Class2 to have 2 x more requests. | |
9f95a23c | 250 | SEASTAR_THREAD_TEST_CASE(test_fair_queue_different_weights) { |
f67539c2 | 251 | test_env env(2); |
11fdf7f2 | 252 | |
9f95a23c TL |
253 | auto a = env.register_priority_class(10); |
254 | auto b = env.register_priority_class(10); | |
11fdf7f2 TL |
255 | |
256 | for (int i = 0; i < 100; ++i) { | |
9f95a23c TL |
257 | env.do_op(a, 2); |
258 | env.do_op(b, 1); | |
11fdf7f2 | 259 | } |
9f95a23c TL |
260 | later().get(); |
261 | // allow half the requests in | |
262 | env.tick(100); | |
263 | env.verify("different_weights", {1, 2}); | |
11fdf7f2 TL |
264 | } |
265 | ||
9f95a23c TL |
266 | // Class2 pushes many requests over. Right after, don't expect Class2 to be able to push anything else. |
267 | SEASTAR_THREAD_TEST_CASE(test_fair_queue_dominant_queue) { | |
268 | test_env env(1); | |
11fdf7f2 | 269 | |
9f95a23c TL |
270 | auto a = env.register_priority_class(10); |
271 | auto b = env.register_priority_class(10); | |
11fdf7f2 TL |
272 | |
273 | for (int i = 0; i < 100; ++i) { | |
9f95a23c | 274 | env.do_op(b, 1); |
11fdf7f2 | 275 | } |
9f95a23c TL |
276 | later().get(); |
277 | ||
278 | // consume all requests | |
279 | env.tick(100); | |
280 | // zero statistics. | |
281 | env.reset_results(b); | |
282 | for (int i = 0; i < 20; ++i) { | |
283 | env.do_op(a, 1); | |
284 | env.do_op(b, 1); | |
285 | } | |
286 | // allow half the requests in | |
287 | env.tick(20); | |
288 | env.verify("dominant_queue", {1, 0}); | |
11fdf7f2 TL |
289 | } |
290 | ||
9f95a23c TL |
291 | // Class2 pushes many requests at first. After enough time, this shouldn't matter anymore. |
292 | SEASTAR_THREAD_TEST_CASE(test_fair_queue_forgiving_queue) { | |
293 | test_env env(1); | |
11fdf7f2 | 294 | |
9f95a23c TL |
295 | auto a = env.register_priority_class(10); |
296 | auto b = env.register_priority_class(10); | |
11fdf7f2 TL |
297 | |
298 | for (int i = 0; i < 100; ++i) { | |
9f95a23c | 299 | env.do_op(b, 1); |
11fdf7f2 | 300 | } |
9f95a23c TL |
301 | later().get(); |
302 | ||
303 | // consume all requests | |
304 | env.tick(100); | |
305 | sleep(500ms).get(); | |
306 | env.reset_results(b); | |
307 | for (int i = 0; i < 100; ++i) { | |
308 | env.do_op(a, 1); | |
309 | env.do_op(b, 1); | |
310 | } | |
311 | later().get(); | |
312 | ||
313 | // allow half the requests in | |
314 | env.tick(100); | |
315 | env.verify("forgiving_queue", {1, 1}); | |
11fdf7f2 TL |
316 | } |
317 | ||
318 | // Classes push requests and then update swap their shares. In the end, should have executed | |
319 | // the same number of requests. | |
9f95a23c TL |
320 | SEASTAR_THREAD_TEST_CASE(test_fair_queue_update_shares) { |
321 | test_env env(1); | |
11fdf7f2 | 322 | |
9f95a23c TL |
323 | auto a = env.register_priority_class(20); |
324 | auto b = env.register_priority_class(10); | |
11fdf7f2 TL |
325 | |
326 | for (int i = 0; i < 500; ++i) { | |
9f95a23c TL |
327 | env.do_op(a, 1); |
328 | env.do_op(b, 1); | |
11fdf7f2 | 329 | } |
9f95a23c TL |
330 | |
331 | later().get(); | |
332 | // allow 25% of the requests in | |
333 | env.tick(250); | |
334 | env.update_shares(a, 10); | |
335 | env.update_shares(b, 20); | |
336 | ||
337 | later().get(); | |
338 | // allow 25% of the requests in | |
339 | env.tick(250); | |
340 | env.verify("update_shares", {1, 1}, 2); | |
11fdf7f2 TL |
341 | } |
342 | ||
343 | // Classes run for a longer period of time. Balance must be kept over many timer | |
344 | // periods. | |
9f95a23c TL |
345 | SEASTAR_THREAD_TEST_CASE(test_fair_queue_longer_run) { |
346 | test_env env(1); | |
11fdf7f2 | 347 | |
9f95a23c TL |
348 | auto a = env.register_priority_class(10); |
349 | auto b = env.register_priority_class(10); | |
11fdf7f2 TL |
350 | |
351 | for (int i = 0; i < 20000; ++i) { | |
9f95a23c TL |
352 | env.do_op(a, 1); |
353 | env.do_op(b, 1); | |
354 | } | |
355 | // In total allow half the requests in, but do it over a | |
356 | // long period of time, ticking slowly | |
357 | for (int i = 0; i < 1000; ++i) { | |
358 | sleep(1ms).get(); | |
359 | env.tick(2); | |
11fdf7f2 | 360 | } |
9f95a23c | 361 | env.verify("longer_run", {1, 1}, 2); |
11fdf7f2 TL |
362 | } |
363 | ||
364 | // Classes run for a longer period of time. Proportional balance must be kept over many timer | |
365 | // periods, despite unequal shares.. | |
9f95a23c TL |
366 | SEASTAR_THREAD_TEST_CASE(test_fair_queue_longer_run_different_shares) { |
367 | test_env env(1); | |
11fdf7f2 | 368 | |
9f95a23c TL |
369 | auto a = env.register_priority_class(10); |
370 | auto b = env.register_priority_class(20); | |
11fdf7f2 TL |
371 | |
372 | for (int i = 0; i < 20000; ++i) { | |
9f95a23c TL |
373 | env.do_op(a, 1); |
374 | env.do_op(b, 1); | |
11fdf7f2 | 375 | } |
9f95a23c TL |
376 | |
377 | // In total allow half the requests in, but do it over a | |
378 | // long period of time, ticking slowly | |
379 | for (int i = 0; i < 1000; ++i) { | |
380 | sleep(1ms).get(); | |
381 | env.tick(2); | |
382 | } | |
383 | env.verify("longer_run_different_shares", {1, 2}, 2); | |
11fdf7f2 TL |
384 | } |
385 | ||
386 | // Classes run for a random period of time. Equal operations expected. | |
9f95a23c TL |
387 | SEASTAR_THREAD_TEST_CASE(test_fair_queue_random_run) { |
388 | test_env env(1); | |
11fdf7f2 | 389 | |
9f95a23c TL |
390 | auto a = env.register_priority_class(1); |
391 | auto b = env.register_priority_class(1); | |
11fdf7f2 | 392 | |
9f95a23c | 393 | std::default_random_engine& generator = testing::local_random_engine; |
11fdf7f2 TL |
394 | // multiples of 100usec - which is the approximate length of the request. We will |
395 | // put a minimum of 10. Below that, it is hard to guarantee anything. The maximum is | |
396 | // about 50 seconds. | |
397 | std::uniform_int_distribution<uint32_t> distribution(10, 500 * 1000); | |
398 | auto reqs = distribution(generator); | |
399 | ||
400 | // Enough requests for the maximum run (half per queue, + leeway) | |
9f95a23c TL |
401 | for (uint32_t i = 0; i < reqs; ++i) { |
402 | env.do_op(a, 1); | |
403 | env.do_op(b, 1); | |
11fdf7f2 TL |
404 | } |
405 | ||
9f95a23c TL |
406 | later().get(); |
407 | // In total allow half the requests in | |
408 | env.tick(reqs); | |
409 | ||
410 | // Accept 5 % error. | |
411 | auto expected_error = std::max(1, int(round(reqs * 0.05))); | |
412 | env.verify(format("random_run ({:d} requests)", reqs), {1, 1}, expected_error); | |
11fdf7f2 | 413 | } |