This is the third part that wraps the series of blog posts on Cinnamon Loadshedder. After giving an overall picture in part one, and diving into the use of PID regulator in part two, we will share how we made adaptive concurrency limiting work in production. Read on to see how we adopted a decade-old idea, the TCP-Vegas algorithm, and adjusted it to work in production across a wide range of services and settings.

The big challenge in any load shedder is that it needs an estimate of the capacity of the service. Essentially, how many requests can the service handle? If the estimate is too low, the service will be too quick at rejecting requests and it will run ineffectively, as it is not utilizing all the available resources. On the other hand if the estimate is too high, the service tries to respond to more requests than it is able to and latencies will go up, and potentially bring down the service. 

A common denominator for capacity is the maximum number of concurrent requests the service can handle and, in essence, you really want to select the value shown in the diagram below, such that you maximize the throughput of the service.

This optimal value can’t really be hardcoded, because it varies heavily:

Thus, for Cinnamon to be useful in many different services, we need an automatic way to estimate the optimal value. And this automatic way should not require any tuning by service owners, as we want to deploy it to thousands of microservices. Thus, we opted to implement a solution that continuously estimates the capacity and tries to hit the optimal value above. Or more precisely, it continuously estimates the maximum number of concurrent requests for every endpoint based on the latencies it observes for the endpoints. We call this number for the inflight limit and this blog post is dedicated to explaining how we arrived at it.

To recap, the diagram below shows the Cinnamon architecture, and this post will dive into the area marked by the red box in Figure 2.

The component responsible for continuously estimating the inflight is called Auto-tuner. Auto-tuner runs in a background goroutine and updates the limit, which the scheduler then uses to figure out whether it can pop any requests from the request priority queue and handle, as shown in Figure 3.

We won’t be diving more into the scheduler, so the rest of this post is only about the background goroutine that updates the inflight limit. At a very high level, Auto-tuner compares the observed request processing latency with some reference latency, and based on that adjusts to the inflight limit value. As we base this logic on the TCP-Vegas algorithm, we’ll first describe how TCP-Vegas works, and then how to make it work without configuration.

The underlying idea is to track how long a given request takes and compare it with a reference time. If the current requests take a lot longer than the reference time, then the service is too loaded and you can decrease the inflight limit. On the other hand, if the request timing is much smaller than the reference, then the service can handle more requests and so you can increase the inflight limit. Lastly, if the timing is not too different, then the service is fine and you don’t change anything. 

The big question is how you then define these concepts:

TCP-Vegas answers this, where the pseudo-code below shows a vanilla implementation of TCP Vegas. In this snippet sample is the latest observed request time, targetLatency is the reference time and currentLimit is the current inflight limit:

The idea is to take the ratio between targetLatency and sample along with the current inflight limit (aka. currentLimit) and then depending on the queue we either increase or decrease the limit. TCP Vegas uses the logarithmic function to smooth the changes. 

Visualizing this, Figure 3 shows what the relation between sample and targetLatency should be for either decreasing, increasing, or not changing the inflight limit. Essentially, what you can see is that the ratio span, where we don’t change anything, gets more narrow as the inflight limit increases. In other words, the smaller the limit is, the more the latencies have to vary before we do anything.

An important step for TCP-Vegas is how to set the targetLatency value. Most implementations set it by setting it to the smallest observed sample time encountered (and then reset it at fixed intervals). That way the targetLatency is automatically updated as the service runs, and query patterns change. 

In the next section we’ll describe some of the encountered issues with this “vanilla” TCP-Vegas and how we fixed them.

A vanilla TCP-Vegas works well in stable environments, such as test scenarios where the incoming rate of requests is stable, you run the same hardware, etc. But, when hitting production, a vanilla TCP-Vegas is simply not good enough, as you also have to deal with:

The above issues can be boiled down to a) adjust the sample to not only be a single value, but actually representing a distribution, b) improving how we “reset” the targetLatency, and c) make bounds on the inflight limit.  We’ll discuss these in the following.

Taking a single latency sample and comparing it with the reference time makes the comparison highly susceptible to spiky requests caused by e.g., network routing imbalances, a temporarily loaded CPU, network timeouts, etc., all of which can severely skew the numbers within a short interval. 

To fix this we aggregate the request latencies and use the aggregated value as the sample value. Specifically, as shown in Figure 4, we collect request latencies over a time interval, and 1) take a percentile of these values, and 2) smoothe the percentile. 

We only record successful requests and they only include the time spent inside the business logic (and thus exclude any time spent in the Cinnamon queue). Each interval is at least 2 seconds and maximum 30 seconds (both can be configured), where what dictates the length is the number of requests – i.e., each interval needs to have at least 250 requests before we use it. When aggregating we use the 90th percentile (i.e., P90) as default and a median filter and exponential smoothing for smoothing. 

Choosing the right duration for the interval is essentially a trade-off between the amount of signal you get (e.g., number of requests) versus how fast you want to react. Having 2 seconds as a minimum works really well for most of our services, as they generally respond within 10-50 milliseconds, and thus you quickly get hundreds of requests and their response times. The problem is more the relatively low number of services that have response times of 1-10 seconds. For them, we opt to cap the reaction time to 30 seconds, and then use whatever number of requests we have seen so far. So far it has worked well. 

Similarly choosing a good percentile is a trade-off between when to react versus reducing the noise at the upper percentiles. So far we have found the 90th percentile to be adequate. The only issues we have encountered with P90 are services, where, e.g., the service is backed by a cache, and the cache-hit ratio is ~90%. Then for some intervals, the P90 latency will be very low (i.e., due to higher cache-hits) and some intervals will be very high (i.e., due to lower cache-hits). In these cases, we typically change the quantile to be P95 or P80 to avoid these cases.

As we save the response time for every successful request, we have made a trade-off of memory consumption vs. precision, in that we use the approximate datastructure t-digest to aggregate durations into a quantile. It means we lose a bit of accuracy, for stable memory usage, which is important for, e.g., services with many endpoints and/or serving many requests.

The targetLatency value describes logically, what the target response time should be. In an ideal case, where the load and the type of requests are the same, targetLatency should be a constant. Unfortunately production is far from that. To solve this, a simple solution is to use the lowest recorded sample observed as the targetLatency and then periodically reset it to the latest observed sample. 

This solution is simple, but it has one major drawback–namely that during long overloads, it leads to an ever-increasing targetLatency, and thus an ever-increasing inflight limit (as shown in Figure 6, where we used this solution in an earlier version of Cinnamon).

The issue is that when the targetLatency is periodically reset, it is set to the latest sample under load. This sample is higher and we will likely not see a lower value, because the service is already loaded. An increased targetLatency means that a higher latency value does not lead to a decreasing inflight, but rather the contrary, where the inflight limit is increased. This process then repeats and you get the picture above.

In essence, the issue is that when resetting the targetLatency to, e.g., a higher value, we don’t really know whether it will improve the throughput of the service. Thus, to fix this we’re using a concept from statistics called covariance, that tells whether two series of values are correlated in that higher values of one leads to higher values of the other. And the nice property of covariance is that it is easy to calculate. In our case, covariance allows us to see whether the last few inflight values are actually leading to higher throughput. The diagram below shows the idea of covariance between observed inflight requests and throughput. In the first case (Figure 7A), increasing inflight (thus processing more concurrent requests) leads to higher throughput (which is good). On the lower graph (Figure 7B), increasing the inflight requests is bad, as it decreases the throughput):

The idea is that we have a running window (typically lasting 50 intervals), where we convert the highest number of concurrent requests processed in addition to the latency sample to an estimated throughput (as given by Little’s Law). Based on these 50 intervals, we calculate the covariance. If the covariance is negative, Auto-tuner will always reduce the inflight limit, when resetting the targetLatency. Note that we have to use the actual observed number of concurrent requests and not the limit, as we might have cases, where the limit is, e.g., 20, but only 3 requests were processed at the same time. 

The diagram below shows the effect of using covariance for the same overload case shown in Figure 6. Essentially, the inflight is stable, and so are the request latencies (i.e., the latency sample graph).

When looking at the graph in Figure 7B, you could consider to be more selective around which of the data points to use for the covariance. As an example in 7B, it seems that there is positive covariance for inflight values between 10 and 35, and therefore, if the periodic reset would select an inflight in this area you would actually want to increase the inflight limit. So far we haven’t really seen a need for it as just using all the last 50 data points has been enough. It is likely because the history is bounded, because during long overloads the periodic reset ends up oscillating between positive or negative covariance.

During normal mode, when a service is doing fine and the sampled latencies are close to the targetLatency, a vanilla TCP-Vegas would allow the inflight limit to increase unbounded. This happens because the ratio between sample and targetLatency will be close to 1 and thus TCP-Vegas increases the limit, even though the actual number of concurrent requests is stable. The unbounded inflight limit is a problem when/if the service becomes overloaded, as the inflight limit is very high and thus it takes “forever” to decrease the inflight limit to actually protect the service.

Therefore it is critical to bound the inflight limit, to cap the time it takes to decrease the limit when overloads starts. In our case, we use the recorded number of concurrently processed requests and multiply it with 10 and use that as the limit. Thus, if you have an interval where a service has processed 10 concurrent requests, the inflight limit would be capped at 100. On the one hand this bounds the time it takes to decrease the limit, while still allowing a burst of requests to be handled by the service.

Lastly, we also have a lower bound in place, that is equal to the number of CPU cores assigned to the service. The intuition behind it is that we want to utilize the cores as much as possible, so if you have an endpoint that is CPU bound each request gets a full CPU core to run. You could argue that there might be cases where one request needs multiple cores, but we haven’t seen that being a problem in practice. If Auto-tuner hits the lower bound multiple times in a row it indicates that the targetLatency value is wrong and thus it also triggers a reset of targetLatency.

As mentioned, all the fun (with TCP-Vegas) happens when it is deployed and used in production. Thus, in this section we’ll demonstrate some situations where Auto-tuner has helped out.

To verify Auto-tuner performance we used the Ballast load testing framework. Ballast allowed us to run load tests in production safely by providing the following important features:

In the graphs below, you can see the result from one of such load tests. The top graph shows throughput per priority, where we highlight only the test traffic. The middle graph shows latency samples aggregated over 10 second intervals. Here we use M3 timers to see the min, mean, and max values. Finally, the bottom graph shows the raw inflight limit value emitted by the service nodes.

The load test starts at T_a. During the test, we gradually increase low-priority traffic (marked as t4 and t5 on the top graph, where t stands for tier). After a certain point (moment T_b), the load becomes too high, and the overload manifests itself on the latency graph in the middle. Auto-tuner reacts by lowering the inflight limit. The inflight limit stops at the value of 16, which is the lowest possible value for this service. After hitting this lower bound several times in a row, Auto-tuner discards the current targetLatency (moment T_c): this is a protective measure that saves Auto-tuner from being guided by an outlier targetLatency. After this reset, the limit slightly overshoots, and finds the equilibrium at the value of 18 (moment T_d). The limit stays at this value until the test ends (moment T_e).

Let’s dive into another interesting case, this time from production, where Auto-tuner saved the day for one of our services. Essentially one of our services (a.k.a., foo)  became overloaded, not because of an increase in traffic, but because one of its dependencies degraded and became substantially slower. The response times of the downstream service (let’s call it bar) did increase, but most importantly it did not die completely, because Auto-tuner reduced the inflight in foo. If not, foo would have overwhelmed bar completely and thus all requests would have been errors. 

The graphs (Figure 10A) below are focused on foo in a single data center with 9 service nodes. The top graph shows inbound traffic and what was accepted by Cinnamon. The middle graph shows hander latency excluding time spent in the Cinnamon queue. And in the bottom graph you can see the latency samples observed by Auto-tuner (similar to Figure 9), where we include the minimum, the mean, and the maximum observed sample in each interval across the service nodes.

Note that in this case the latency profile of the endpoint rapidly changes, because the downstream dependency starts to take a lot longer. Thus Cinnamon needs to kick in to reduce traffic to the downstream (to help it recover), which means sending fewer concurrent requests. What is further interesting is that while P99 and P90 latencies do increase, the P50 does not change. Had Auto-tuner not decreased the inflight, then the P50 response times would have increased significantly as well.

The graphs (Figure 10B) below show how the inflight limit and its utilization (i.e., ratio of inflight and inflightLimit) behave, along with the CPU utilization of the service nodes. Looking at the inflight limit value, the behavior is similar to what we’ve seen in the load test. Normally, the limit oscillates around a relatively high value. When the overload starts, the limit goes down. Furthermore, you see the inflight limit increasing around 17:45 and that is because the P90 latency drops as seen in the graph above.

What is interesting is that when you look at the inflight limit utilization graph, it normally hovers around 10% (due to our 10x inflight bound), but then goes up to 100%, as Auto-tuner reduces the inflight (and we have enough traffic to take up the inflight spots.)

The provided CPU usage graph illustrates that the service was overloaded without running out of CPU. Even though the amount of traffic hasn’t increased, the service wasn’t able to service the requested throughput, due to an increase in latency.

Adaptive concurrency limiting significantly simplified onboarding to Cinnamon by eliminating the need for manual inflight limit tuning. More importantly, it keeps the Cinnamon configuration up to date with the current state of the service and the environment it operates in.

Before choosing TCP-Vegas we experimented with other congestion control algorithms like AIMD and gradient descent, but we found that using TCP-Vegas leads to more stable inflight limits and is better at handled latency variations at low inflight numbers

For additional information on starting a similar project, the open-source concurrency-limits library by Netflix^® is a great starting point.