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