RFC: QoS/Multi-tenancy for Circuit Breakers

While messing around with different load shedding mechanisms over the holidays, I hacked one up that may be used to perform fair load shedding (among other things) via the current circuit breakers. I'd love to start some discussion here around its viability.

TL; DR: Altering the concurrency control mechanisms (circuit breakers and adaptive concurrency) to allow for queuing of excess requests, rather than immediately shedding, can allow for multi-tenant load shedding support. This can mitigate the effect of "noisy neighbors" and provide isolation between arbitrary downstream tenants.

Problem: Indiscriminate load shedding

Consider a scenario with 2 downstream tenants sending traffic to some single server fronted by an Envoy sidecar. If the Envoy has a well configured circuit breaker or adaptive concurrency configured, it should be more-or-less protected from resource exhaustion because the concurrency control mechanisms will begin shedding load when a threshold is reached. If one of the downstream tenants is sending the vast majority of the traffic, it's responsible for triggering the load shedding, but both tenants will have the same percentage of their requests 503'd. This is a canonical noisy neighbor problem and to my knowledge, the current concurrency control mechanisms don't have any mitigations for this beyond the circuit breaker's priority config parameter.

Queuing/buffering requests instead of dropping

One extension to the concurrency control mechanisms that may mitigate this problem is to queue requests instead of immediately dropping them. This would allow us to employ various active queue management techniques, while still being able to maintain the current circuit breaker behavior if one prefers it.

I prototyped the idea via a few different simulations I hacked up, similar to the ones used to evaluate adaptive concurrency. There were 2 different clients sending traffic to a single server. One client had a steady, low request rate. The other steadily ramped up traffic until the concurrency control mechanisms were engaged.

The queue management technique used was a simple queue timeout. If a request sat queued beyond some threshold, it was dropped. This allows for a recreation of the current circuit breaker behavior by immediately timing out a request upon insertion into the queue, which results in immediately shedding a request instead of performing any queuing.

On the other hand, one can simply never time out a request in the queue, which would result in elevated latencies and timeouts caused by queuing delay, mirroring the absence of any circuit breakers from the downstream perspective and resulting in a congestion collapse and all requests timing out:

Notice above that once all of the requests hit some latency threshold, both downstream tenants got nothing but timeouts and the goodput dropped to zero. The goodput in this case is a request that received a reply from the upstream that was not a 503 and didn't time out.

A more reasonable approach here would be to set the queue timeouts to some fraction of the request timeouts. Now you have a circuit breaker that is more tolerant of bursts and an upper-bound on the allowed queuing delay to prevent latencies from getting out of hand:

Notice we still get all the greatest hits of circuit breaking: reasonable latencies and nonzero goodput! The circuit breaker is doing its job and protecting the server's goodput; however, the only reason any load shedding needs to occur is because only one of tenants. Both tenants are receiving 503s which is a bit... unfair.

Tenant isolation via fair queues

We can address the unfairness in load shedding observed above by offering more interesting queuing disciplines in the circuit breaker. If we swap out the FIFO queue used earlier with a classful fair queue, we now have isolation between the different tenants/classes. Here's the last example in the previous section, WITH queue timeouts, but with basic fair queuing between the tenants:

The throttling via 503 is occurring on ONLY misbehaving (orange) tenant! The other tenant is totally unaffected and isolated.

This even applies to the case without the queue timeouts. The only tenant experiencing the elevated latencies, timeouts, and goodput collapse is the one who is "misbehaving". The tenant in blue doesn't even notice anything because those elevated latencies are coming from the queuing delays:

It's also worth mentioning this approach isn't limited to fair queuing. Circuit breaker priorities can be implemented by using a priority queue, a weighted fair queue can be used to partition resources differently, or CoDel (or some other variant) can be used to keep latencies under control.

Conclusion

This seems promising to me based on the simulations I've hacked up, but I'm curious if anyone has thoughts on this approach to isolated circuit breaking. I think there may even be other features that we'd be able to get by simply using a fancier queuing discipline and exposing the relevant knobs.

Let me know what you all think!