envoyproxy / envoyproxy/envoy

Support a configurable queue for pending requests to use adaptive LIFO and CoDel

Open
#29,070 9 comments 3 reactions 2 assignees Claimed by @balrawi-figma View on GitHub
area/load balancing enhancement no stalebot
Dominant language
C++
Stars
28.9k
Forks
5.6k
Avg merge
1d 22h
Merged PRs (30d)
430

Description

*Title*: *Support a configurable queue for pending requests to use adaptive LIFO and CoDel*

*Description*:
There is no way today that I'm aware of to use different queuing strategies for pending requests for Envoy. The issue here is to have a way to configure the pending requests queue in Envoy.

*Why is this important?*
In an overloaded situation, using a simple FIFO queue impacts the p50 and p75 significantly (Some data from testing comparing different strategies are shared below).

Using controlled-delay (aka CoDel) has been a standard practice in the [linux kernel](https://man7.org/linux/man-pages/man8/tc-codel.8.html). It's also been a well [proven strategy](https://queue.acm.org/detail.cfm?id=2839461) to combine codel with an adaptive LIFO queue to mitigate request delays during an overloaded situation. Below are some numbers that I did using a [draft PR](https://github.com/envoyproxy/envoy/pull/28982) that shed some light regarding the improvements in p50 and p75 of request latencies across different configurations.

*Relevant Links*:
Related issue: https://github.com/envoyproxy/envoy/issues/9606
A draft PR for a possible implementation: https://github.com/envoyproxy/envoy/pull/28982

## Testing

*Setup*
Test an upstream with a controlled, random 'sleep' by sleeping between 0-3 seconds to simulate an overloaded situation saturating upstream capacity.

## Test 1: Existing FIFO queue in Envoy:

```
➜ hey -n 500 -c 120 -t 0 https://test/circuit_breaking

Summary:
Total: 94.1187 secs
Slowest: 51.9708 secs
Fastest: 0.0456 secs
Average: 14.8038 secs
Requests/sec: 5.0999

Total data: 960 bytes
Size/request: 2 bytes

Response time histogram:
0.046 [1] |
5.238 [256] |■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
10.431 [27] |■■■■
15.623 [15] |■■
20.816 [28] |■■■■
26.008 [14] |■■
31.201 [28] |■■■■
36.393 [33] |■■■■■
41.586 [33] |■■■■■
46.778 [22] |■■■
51.971 [23] |■■■■

Latency distribution:
10% in 0.9155 secs
25% in 2.0353 secs
50% in 4.7792 secs
75% in 29.8650 secs
90% in 41.4760 secs
95% in 46.5524 secs
99% in 51.0998 secs
```

## Test 2: Adaptive LIFO queue in Envoy (per PR):

```
➜ hey -n 500 -c 120 -t 0 https://test/circuit_breaking

Summary:
Total: 115.0796 secs
Slowest: 109.0175 secs
Fastest: 0.0432 secs
Average: 13.0082 secs
Requests/sec: 4.1710

Total data: 960 bytes
Size/request: 2 bytes

Response time histogram:
0.043 [1] |
10.941 [373] |■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
21.838 [22] |■■
32.735 [11] |■
43.633 [12] |■
54.530 [14] |■■
65.428 [17] |■■
76.325 [7] |■
87.223 [11] |■
98.120 [5] |■
109.017 [7] |■

Latency distribution:
10% in 0.0928 secs
25% in 1.0895 secs
50% in 2.1509 secs
75% in 7.4232 secs
90% in 54.1354 secs
95% in 74.5611 secs
99% in 103.9622 secs
```

## Test 3: Adaptive LIFO queue + CoDel in Envoy (per PR):
CoDel target delay is 5ms target delay and 100ms interval

```
➜ hey -n 500 -c 120 -t 0 https://test/circuit_breaking

Summary:
Total: 125.8912 secs
Slowest: 120.8633 secs
Fastest: 0.0805 secs
Average: 4.5031 secs
Requests/sec: 3.1773

Total data: 1553924 bytes
Size/request: 3884 bytes

Response time histogram:
0.081 [1] |
12.159 [394] |■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
24.237 [0] |
36.315 [0] |
48.394 [0] |
60.472 [0] |
72.550 [0] |
84.628 [0] |
96.707 [0] |
108.785 [0] |
120.863 [5] |■

Latency distribution:
10% in 0.9964 secs
25% in 1.7487 secs
50% in 3.1075 secs
75% in 3.8031 secs
90% in 5.8382 secs
95% in 5.8405 secs
99% in 120.0763 secs

Status code distribution:
[200] 52 responses
[503] 343 responses
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.