Convert limiter queue to adopt LIFO strategy
This MR introduces a new feature flag that allows users to change between queuing strategies (LIFO or FIFO( current default )) when using dynamic limiting.
Original issue here: #5396 (closed)
Summary of benchmark results:
Each row's column follows the following format: benchmark name/parameters, number of iterations, average time per operation, average memory allocated per operation, and average number of allocations per operation.
1. FIFO 100 requests
BenchmarkUnaryLimitQueueStrategyHandler/use_resizable_semaphore_in_concurrency_limiter=true,use_resizable_semaphore_lifo_strategy=false/100_requests-12 1 5012930459 ns/op 7949312 B/op 103434 allocs/op
2. LIFO 100 requests
BenchmarkUnaryLimitQueueStrategyHandler/use_resizable_semaphore_in_concurrency_limiter=true,use_resizable_semaphore_lifo_strategy=true/100_requests-12 1 5012386083 ns/op 7436960 B/op 101638 allocs/op
3. FIFO 200 requests
BenchmarkUnaryLimitQueueStrategyHandler/use_resizable_semaphore_in_concurrency_limiter=true,use_resizable_semaphore_lifo_strategy=false/200_requests-12 1 5511813459 ns/op 16189592 B/op 213121 allocs/op
4. LIFO 200 requests
BenchmarkUnaryLimitQueueStrategyHandler/use_resizable_semaphore_in_concurrency_limiter=true,use_resizable_semaphore_lifo_strategy=true/200_requests-12 1 5513659791 ns/op 15954576 B/op 212270 allocs/opFor both 100 requests and 200 requests tests, the LIFO queue strategy performs better than FIFO strategy in terms of lower memory allocation and fewer memory allocations done per operation. The difference is small, but consistent as the number of requests increases.
The difference in benchmark tests were too small to differentiate between LIFO and FIFO, so prometheus metrics were further collected to contrast their performance.
1. FIFO 100 requests every 500 ms for 5 rounds
gitaly_concurrency_limiting_acquiring_seconds_0.025 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.500 -> 299.000000
gitaly_concurrency_limiting_acquiring_seconds_10.000 -> 500.000000
sample_sum -> 125.826786
sample_count -> 500.000000
gitaly_concurrency_limiting_acquiring_seconds_0.005 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.010 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.050 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.250 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.100 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_1.000 -> 500.000000
gitaly_concurrency_limiting_acquiring_seconds_2.500 -> 500.000000
gitaly_concurrency_limiting_acquiring_seconds_5.000 -> 500.000000
BenchmarkUnaryLimitQueueStrategyHandler/use_resizable_semaphore_in_concurrency_limiter=true,use_resizable_semaphore_lifo_strategy=false/100_requests-12 1 5012930459 ns/op 7949312 B/op 103434 allocs/op
2. LIFO 100 requests every 500 ms for 5 rounds
gitaly_concurrency_limiting_acquiring_seconds_0.025 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.005 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.010 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.250 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.050 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.500 -> 317.000000
gitaly_concurrency_limiting_acquiring_seconds_1.000 -> 500.000000
gitaly_concurrency_limiting_acquiring_seconds_2.500 -> 500.000000
gitaly_concurrency_limiting_acquiring_seconds_5.000 -> 500.000000
gitaly_concurrency_limiting_acquiring_seconds_0.100 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_10.000 -> 500.000000
sample_sum -> 125.450174
sample_count -> 500.000000
BenchmarkUnaryLimitQueueStrategyHandler/use_resizable_semaphore_in_concurrency_limiter=true,use_resizable_semaphore_lifo_strategy=true/100_requests-12 1 5012386083 ns/op 7436960 B/op 101638 allocs/op
3. FIFO 200 requests every 500 ms for 5 rounds
gitaly_concurrency_limiting_acquiring_seconds_0.025 -> 60.000000
gitaly_concurrency_limiting_acquiring_seconds_1.000 -> 339.000000
sample_count -> 524.000000
gitaly_concurrency_limiting_acquiring_seconds_0.010 -> 60.000000
gitaly_concurrency_limiting_acquiring_seconds_2.500 -> 524.000000
gitaly_concurrency_limiting_acquiring_seconds_0.100 -> 60.000000
gitaly_concurrency_limiting_acquiring_seconds_0.050 -> 60.000000
gitaly_concurrency_limiting_acquiring_seconds_0.500 -> 159.000000
gitaly_concurrency_limiting_acquiring_seconds_10.000 -> 524.000000
sample_sum -> 339.509596
gitaly_concurrency_limiting_acquiring_seconds_0.005 -> 54.000000
gitaly_concurrency_limiting_acquiring_seconds_0.250 -> 60.000000
gitaly_concurrency_limiting_acquiring_seconds_5.000 -> 524.000000
gitaly_requests_dropped_total -> 476.000000
BenchmarkUnaryLimitQueueStrategyHandler/use_resizable_semaphore_in_concurrency_limiter=true,use_resizable_semaphore_lifo_strategy=false/200_requests-12 1 5511813459 ns/op 16189592 B/op 213121 allocs/op
4. LIFO 200 requests every 500 ms for 5 rounds
gitaly_concurrency_limiting_acquiring_seconds_1.000 -> 450.000000
sample_sum -> 294.229239
gitaly_concurrency_limiting_acquiring_seconds_0.010 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.025 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.100 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.250 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_10.000 -> 529.000000
gitaly_requests_dropped_total -> 471.000000
gitaly_concurrency_limiting_acquiring_seconds_0.005 -> 224.000000
gitaly_concurrency_limiting_acquiring_seconds_0.050 -> 250.000000
gitaly_concurrency_limiting_acquiring_seconds_0.500 -> 319.000000
gitaly_concurrency_limiting_acquiring_seconds_2.500 -> 479.000000
gitaly_concurrency_limiting_acquiring_seconds_5.000 -> 529.000000
sample_count -> 529.000000
BenchmarkUnaryLimitQueueStrategyHandler/use_resizable_semaphore_in_concurrency_limiter=true,use_resizable_semaphore_lifo_strategy=true/200_requests-12 1 5513659791 ns/op 15954576 B/op 212270 allocs/op`For the 100 requests batch, the sample sum was almost the same. This indicates that at relatively low traffic of 500 requests, the total time that requests spent using either strategy was the same. There were also no dropped requests.
For the 200 requests batch, the dropped requests were the same but the sample sum makes a difference - 339.5 vs 294.2 (FIFO vs LIFO). Here we can see that the lower value sample sum of LIFO indicates that collectively across all requests, it results in a lower total time calls are rate limited. That means that requests are getting served faster when traffic increases. Furthermore if you look at the cumulative count of gitaly_concurrency_limiting_acquiring_seconds_1.000 , FIFO vs LIFO is 339 vs 450. This also shows a significant difference in requests being processed by the rate limiter within the upper bound of 1 second. For this number, the higher is better as it indicates they are queued so that they can be served. In the 200 request batch, 1000 requests in total are made. sample_count is the total requests served , LIFO does outperform FIFO here serving 529 > 524 requests.
Overall, the results indicate that at low traffic intensity, queuing does not matter. But at higher traffic intensity, LIFO can perform slightly better, processing more requests than FIFO.