Circuit breaker retry budgets count retries inconsistently

[AdamEAnderson]

Circuit breaker retry budgets counts retries inconsistently: Retry budgets count retries in backoff as active, but doesn't count them towards the calculation of the limit

Description:
Retry budgets allow you to configure a circuit breaker on the proportion of requests that are retries. I will ignore the min retry limit control for this issue (assume it is 0) as it isn't pertinent.

Here is how that is calculated:

• Limit: (num_pending_requests + num_active_requests) * budget_percent / 100.0
• Count: number of outstanding retries, either active, pending, in backoff, or waiting for rate limiting

If the router decides a request needs a retry, it checks against the limit before proceeding, and if it doesn't fit returns the error instead of retrying.

The problem is that even when the retry budget is 100%, retries can still overflow due to how the limit is calculated.

Imagine the following scenario: a request has just been completed to the upstream and has received a retriable error. The retry budget is set to 100%.

In this scenario, the retry limit is 0 as there are no active or pending requests. When the router checks the retry budget, it sees that an additional retry would overflow because there is no space for additional retries, even though the budget is 100%.

This behavior is super unintuitive and not well described in the docs. It seems to me that the idea behind a retry budget is something like:

• Limit the percentage of outstanding requests to a single upstream so that you can't get into a situation where most of the upstream requests are retries, creating a storm
• Have a lower bound on the limit so that retries can continue at low request rates that may violate the budget due to low sample size

In that model, it makes very little sense that a budget of 100% still allows retries to overflow. In fact, validation on the percentage type used in configuration prevents you from even specifying a limit above 100%, making it very dangerous to enable the retry budget feature.

Second related problem:
While attempting to write an integration test to capture the above behavior, I discovered an additional counting inconsistency that depends on the upstream protocol version.

When using an HTTP 1 or HTTP 3 upstream, a request is still counted as active when the circuit breaker determination for its retry is being made. This can have an effect on the retry budget calculation.

When using an HTTP 2 upstream, the request is not considered as active.

The issue is most clear by reading the repro code below.

Proposal:
I would propose that we count retries in backoff towards the retry budget limit, i.e. limit = (pending + active + backoff) * budget. That would ensure that the actual value never exceeds a budget of 100%, and better captures the intuitive idea that a retry budget is out of the proportion of all outstanding requests including all retries.

For the upstream protocol inconsistency, I would propose that a request should not be considered as active when calculating budgets, as at that point the request is complete and no longer actively taking up resources for the upstream.

If folks are amenable to my proposal I can likely PR the changes.

Repro steps:
I have reproduced the issue in a circuit breaker integration test in envoy here.
The relevant code is below:

class RetryBudgetIntegrationTest : public HttpProtocolIntegrationTest {
public:
  void initialize() override { HttpProtocolIntegrationTest::initialize(); }
};

INSTANTIATE_TEST_SUITE_P(Protocols, RetryBudgetIntegrationTest,
                         testing::ValuesIn(HttpProtocolIntegrationTest::getProtocolTestParams()),
                         HttpProtocolIntegrationTest::protocolTestParamsToString);

TEST_P(RetryBudgetIntegrationTest, CircuitBreakerRetryBudgets) {
  // Create a config with a retry budget of 100% and a (very) long retry backoff
  config_helper_.addConfigModifier([](envoy::config::bootstrap::v3::Bootstrap& bootstrap) {
    auto* retry_budget = bootstrap.mutable_static_resources()
                             ->mutable_clusters(0)
                             ->mutable_circuit_breakers()
                             ->add_thresholds()
                             ->mutable_retry_budget();
    retry_budget->mutable_min_retry_concurrency()->set_value(0);
    retry_budget->mutable_budget_percent()->set_value(100);
  });
  config_helper_.addConfigModifier(
      [&](envoy::extensions::filters::network::http_connection_manager::v3::HttpConnectionManager&
              hcm) -> void {
        auto* retry_policy =
            hcm.mutable_route_config()->mutable_virtual_hosts(0)->mutable_retry_policy();
        retry_policy->set_retry_on("5xx");
        retry_policy->mutable_retry_back_off()->mutable_base_interval()->set_seconds(100);
      });
  initialize();

  Http::TestResponseHeaderMapImpl error_response_headers{{":status", "500"}};

  // Send a request that will fail and trigger a retry
  codec_client_ = makeHttpConnection(lookupPort("http"));
  auto response1 = codec_client_->makeHeaderOnlyRequest(default_request_headers_);
  waitForNextUpstreamRequest();
  upstream_request_->encodeHeaders(error_response_headers, true); // trigger retry
  EXPECT_TRUE(upstream_request_->complete());

  // Observe odd behavior of retry overflow even though the budget is set to 100%
  test_server_->waitForCounterEq("cluster.cluster_0.upstream_rq_total", 1);
  if (upstreamProtocol() == Http::CodecType::HTTP2) {
    // For H2 upstreams the observed behavior is that the retry budget max is 0
    // i.e. it doesn't count the request that just failed as active
    EXPECT_EQ(test_server_->counter("cluster.cluster_0.upstream_rq_retry_overflow")->value(), 1);
    // since the retry overflowed we get the error response
    ASSERT_TRUE(response1->waitForEndStream());
  } else {
    // For H1/H3 upstreams the observed behavior is that the retry budget max is 1
    // i.e. it counts the request that just failed as still active when calculating retries
    //
    // Now this retry is in backoff and not counted as an active or pending request,
    // but still counted against the retry limit
    EXPECT_EQ(test_server_->counter("cluster.cluster_0.upstream_rq_retry_overflow")->value(), 0);
  }

  // now we are in a slightly weird protocol-dependent state:
  // - For H2: the request is completed and there is no retry happening
  // - For H1/H3: the request is in a long retry backoff

  // make another request that will fail and trigger another retry
  Envoy::IntegrationCodecClientPtr codec_client2 = makeHttpConnection(lookupPort("http"));
  auto response2 = codec_client2->makeHeaderOnlyRequest(default_request_headers_);

  waitForNextUpstreamRequest();
  upstream_request_->encodeHeaders(error_response_headers, true); // trigger retry
  EXPECT_TRUE(upstream_request_->complete());

  test_server_->waitForCounterEq("cluster.cluster_0.upstream_rq_total", 2);
  // This time behavior is independent of upstream protocol, no matter what the retry overflows
  //
  // In the case of H2, it would overflow regardless of the retry in backoff due to the behavior
  // seen above
  //
  // However, for H1/H3 the retry in backoff is counted against the active retry count, but not
  // counted against the limit (active + pending requests) so we have:
  // - 1 retry in backoff
  // - 1 request counted as active (due to H1/H3 specific behavior seen above)
  // Because our retry budget is 100%, that gives us a retry limit of 1 since the retry in backoff
  // is not counted in active + pending requests So we overflow the retry budget on the second
  // request
  if (upstreamProtocol() == Http::CodecType::HTTP2) {
    EXPECT_EQ(test_server_->counter("cluster.cluster_0.upstream_rq_retry_overflow")->value(), 2);
  } else {
    EXPECT_EQ(test_server_->counter("cluster.cluster_0.upstream_rq_retry_overflow")->value(), 1);
  }

  // since the retry overflowed we get the error response
  ASSERT_TRUE(response2->waitForEndStream());

  if (upstreamProtocol() != Http::CodecType::HTTP2) {
    // For H1/H3: the first request is in a long retry backoff and must be manually abandoned
    // otherwise the codec destructor is annoyed about the outstanding request
    codec_client_->rawConnection().close(Envoy::Network::ConnectionCloseType::Abort);
  }
  codec_client2->close();
}

[kyessenov]

CC @tonya11en - not sure who should know the answer best here.

[tonya11en]

I'll need to refresh my memory on the details, but after reading the description and integration test, these are likely actual oversights in the initial implementation. With regards to a fix, I'm of the opinion that we shouldn't count retries in a backoff state as active, since they're not actively consuming upstream resources. I'll look a bit closer at this later today to assess whether that's even possible, but curious what you think about ignoring retries in the backoff state @AdamEAnderson ?

[AdamEAnderson]

I think ignoring retries in backoff state will actually lead to an even more problematic state.

Imagine this scenario:

1. The upstream cluster has a retry budget of 20%
2. Make 1000 requests simultaneously, all return 5xx and need to be retried.
3. Because retries in backoff aren't counted against resource limits, all 1000 retries are allowed to go ahead and enter exponential backoff.
4. All 1000 retries exit backoff and are queued into the upstream connection pool
5. Now despite a 20% budget we've just retried all of the requests causing another load of failures

Basically the problem is that this introduces a large delay into the circuit breaker signal. We can queue a ton of retries up in backoff without ever hitting limits, but once they come out of backoff and onto the connection pool we will easily overshoot whatever limit we had.

If you put in a decision point for a retry to overflow after a retry exits backoff and before it gets queued on the pool, then the router no longer has the failing request (since the original upstream codec stream was destroyed) so we have to give a very generic error, and the request has waited an extra backoff interval just to get cancelled.

Another way to think about it is in the context of the current implementation. There are two kinds of resources considered:

• Pending requests
• Active requests

Only the active requests are consuming upstream resources, but we need to count the pending ones too because they will consume resources soon, and we have to make a decision now.

[AdamEAnderson]

I did a bit more investigation into the H1/H3 vs H2 codec client differences and I'm not sure it's going to be possible to solve without serious risk.

We have to make the retry decision at the point of getting upstream headers, and if the decision is no we need to continue streaming the upstream response. So the upstream request needs to still be active in at least some cases.

For header-only requests, things get weird.

• H1 calls the decoder callbacks before destroying the stream
• H2 destroys the stream in the preDecode callback before the decoder callbacks are called
• H3 seems to never return endStream=true on decoded headers

I'm not sure we can unify this without a ton of risk and bending of the underlying pieces.

A fairly simple alternative is to tend towards allow in the case of ambiguity rather than tending towards deny.
We already state that circuit breakers can momentarily exceed limits due to multithreading, etc and are meant to be eventually consistent.
The easiest fix would be to always add 1 to the max when considering creating another retry, assuming that the request is no longer active (the associated retry count is always decremented on repeats correctly).

That would reduce (although not eliminate) weird behavior, and mean that in the worst case you overshoot the limit slightly rather than having something blocked that you think should be allowed.

[tonya11en]

Sorry for the delay- I finally gave this the attention it deserves and think we need to flesh this out a bit more before merging any changes. I think the way retry budgets enforce behavior has always been a bit awkward due to the fact that it's looking at point-in-time active retry counts. I think we shouldn't have to really think about whether a retry is in a backoff state or not.

The retry budget mechanism should be changed to enforce a maximum retry percentage for a time window. As we have it implemented now, a 100ms blip where all of the requests fail and need to be retried will cause the budget to be exceeded. What we really want is something like:

• Track how many retries have been sent in some time window.
• Track how many requests (including retries) have been sent in the window.
• Enforce that (num_retries / total_rq) never exceeds the configured retry budget.

With this scheme, today's weird behavior is just a special case where the time window is 0. Setting this time window to some nonzero value would still prevent retry storms, still give us an upper bound on the size of a retry burst, and simplifies things a bit. It would totally remove the need for that awkward min_retry_concurrency parameter and behave intuitively when a budget is 0% or 100%. I think this should also make the behavioral differences based on HTTP version moot.

Out in the wild, retry budget implementations have some sort of time dependency that is missing from Envoy's. There is a time dependency in the retry budget implementations of Tower (rust), Linkderd.), Finagle, and I'm sure a bunch of others.

Sorry to swoop in after you've sent out #30738, but I really think we need to fix the real issue.

edit: I'm happy to chat synchronously over slack or a call just so we can get on the same page. Feel free to ping me in the Envoy slack.

[AdamEAnderson]

I actually agree that this makes sense. We will still need to support the old setup as well for compatibility.

Proposal

Config would look something like:

• Retry budget window. How long to track a successful try as counting towards the budget before disregarding it as out of date.
• Budget percentage. How many retries are allowed per successful try? I.e. you can do 2 retries for every 1 successful try, etc. Could also make this be "How many retries are allowed per try completed?" which is more like the current version and has better 0-100% scaling compared to the alternative.
• Reserved retry rate. What is the amount of retries per second that should always be reserved, i.e. should be free regardless of ongoing tries. This is important for starting up and for allowing retries when there are relatively few requests per budget window.

The implementation would be similar to the tower implementation. We use a token bucket approach, adding tokens in for completed tries and subtracting them for retries. We divide the window into segments and have one bucket per segment of the window, for a given number of segments (say, 10). Then when the segment of the window elapses, we expire the old segment bucket and create a new one. This can be done with minimal locking, but will require a small amount of global locking that must happen once per segment.

Looking forwards

This seems to be an area where people could disagree on what the best approach is. Already we have two different retry limiting setups: static limit and instantaneous budgets. Both are shoved into the same circuit breaker config in the cluster.

We are going to have to support the legacy behavior around concurrency-based budgets as well as static limits, and also the new time-based budgets. It seems like this is somewhere extensions could be useful.

We would add a new extension point for retry limiting that has the new budget approach and the static limit as possible extensions. The extension acts kind of like a miniature version of the RetryStateImpl but with more limited purview. It gets instantiated once per stream and gets asked whether to allow a retry and gets called when a try completes with retry-related information.

I see this as the start of unpacking more of circuit breakers, outlier detection, and retry logic into more extensible components because the current state is a bit of a mess.

[tonya11en]

Already we have two different retry limiting setups: static limit and instantaneous budgets. Both are shoved into the same circuit breaker config in the cluster.

I wrote the retry budget implementation (sorry), so I can give a bit of context. It wasn't because folks disagreed on the approach- it was because we wanted to get rid of the static limits entirely in favor of budgets. Obviously that didn't happen, but I don't think there's going to be any objections on this front. I'll also help out with untangling this mess and the whole song-and-dance around deprecating, changing the default, docs, reviews, buy-in, etc.

This can probably just be modeled like the retry predicate extensions? Might be a good thing to grok before pitching the changes. I'll follow up on this tomorrow when I have fresh eyes/brain.

[AdamEAnderson]

Here's a more fleshed out idea of what the extension point would look like. Essentially we would be creating an expansion from the existing fixed retry_on field to have more complicated predicates. The idea here is that a limiter is really just a fancy, smart thing that answers "should we retry?".

I think the interface looks something like this:

/**
 * A predicate that determines if retries should be attempted. The predicate is instatiated
 * once per stream. This predicate forms only a part of the retry decision in combination
 * with the retry policy and any other retry predicates.
 */
class RetryPredicate {
public:
  /**
   * Always called after a try has been completed.
   * @param upstream_stream_info the stream info for the upstream request that has now finished.
   * @return whether a retry should be attempted. Returning false guarantees that the retry is not attempted.
   *         However returning true may or may not result in the retry being attempted depending on other predicates.
   */
  virtual bool shouldRetry(StreamInfo::StreamInfo& upstream_stream_info) const PURE;

  /**
   * Called immediately when a retry has been scheduled.
   * @param time_until_retry describes when the retry will be dispatched to the upstream.
   */
  virtual void onRetryScheduled(std::chrono::milliseconds time_until_retry) const PURE;

  virtual ~RetryPredicate() = default;
};

This should be expressive enough to capture all the limiter use cases we have, and also extensible enough to encapsulate any other complicated "should we retry?" questions in the future.

I'm not totally sure about how this interface interacts with everything else around it. For instance, here are a few different ideas:

• We add a list of custom predicates to the retry policy. These get anded with the result of the normal wouldRetry stuff based on retry_on and we only do the retry if both agree that we should be doing a retry. This lacks expressiveness in terms of describing "or" conditions as well. It's also somewhat confusing because we'd be doing limiting on a per-cluster basis and presumably storing some amount of info in the cluster, but the config is in the retry policy rather than the circuit breakers.
• We add a single one of these predicates to the circuit breakers. This makes the semantics more clear, but reduces the reusability for no good reason.
• We somehow use the matcher API in the retry policy to describe the tree of conditions. I think this is far more complicated, especially because we still need callbacks when retry-related events are happening even if the matcher isn't going on. It is also confusing because its unclear how the existing retry_on fits into the matcher setup. I'm also just not super familiar with the new matchers.

Thoughts?

[tonya11en]

@AdamEAnderson I think this is fine, but it would be more helpful if we had some example protos/configs to look at. Can you post up an example cluster config that configures this new retry budget and what it looks like with a basic circuit breaker?

[AdamEAnderson]

Sorry for the delay, I'm back around this week and will flesh out a detailed description.