Adaptive Timeout Strategies for Microservice Applications

MIT PRIMES 2024

Abstract

Timeouts are critical in determining whether a request has succeeded or failed. Developers face several challenges when setting timeout values in distributed systems; the specific challenge we investigate being the systems’ propensity to change, both over the short- and long-term. We propose a timeout-optimized policy targeting change over different time scales, assuming APIs that are both idempotent and atomic. We evaluate our approaches on a home-grown microservices testbed, by comparing the timeout percentage, total time taken, and closeness to actual latency when our approaches and the industry standard of Exponential Backoff are used in simulated environments with changing system performance.

Introduction

In the past, systems have traditionally been built in monoliths, with all of their components running on a single machine. With increasing speed and scale requirements, monolithic systems have faced several challenges. For one, the entire system must scale together, resulting in some components being over- or under-scaled. Monolithic applications are often hard to deploy because of their large size and are often tightly coupled, lack modularity, and have a limited development stack.

In the last two decades, organizations have been moving from using one monolith to many small independent applications called microservices which communicate via requests to achieve more complex tasks. Microservices commonly communicate with each other using request protocols such as RPC (Remote Procedure Call) and HTTP (Hypertext Transfer Protocol) which often result in long tail latencies; for example in a system where the server usually responds in 10ms, the 99th percentile is often as high as 1 second. In such a case, timeouts are employed to determine whether a request has failed or simply taking longer than usual. After the client has waited a certain amount of time, the request times out, is deemed failed, and a retry is issued.

Correct timeouts are vital in distributed systems to determine whether information is flowing as intended. However, there has been little work so far on how to allocate timeouts. Ultimately, poor timeouts result in additional latency for the user. Short timeouts will result in legitimate responses being prematurely abandoned by the user, causing unnecessary retries. Long timeouts will result in resources being allocated fruitlessly (requests that will never return a response would be kept alive for longer than necessary, taking resources away from other requests), slowing the system down for any requests which may actually provide responses. Thus, extensively long timeouts risk violating Service Level Agreements (SLAs) and in easier exploitation through Denial-of-Service attacks.

When individual services in a distributed system change, as they frequently do, it is important for every service to automatically update its timeouts to not cause user frustration or security vulnerabilities. In this paper, we investigate methods for assigning timeouts in dynamic (constantly changing) microservice applications.

Assumptions

We assume that requests are both atomic, that they succeed fully or fail entirely, and idempotent, that they are repeatable: no matter the number of requests sent, the behavior is the same. In addition, we assume a dynamic system, one that is constantly changing.

Timeout Principles

The algorithms we propose aim to satisfy the following principles:

Optimal. An optimal timeout will result in the smallest feasibly possible amount of latency for a given client. Long latencies result in degraded throughput, and short timeouts result in high latencies. Balancing these two issues will result in an optimal timeout.

Dynamic. The performance of microservices is constantly changing, both over the short- and long-term. In the short term, the microservice might experience higher latency due to increased load, for example, and in the long term, the implementation of the microservice might change. The algorithms we propose aim to be adaptive to both of these forms of change.

Sequential Timeout Values

A request may time out due to a fatal server error, or just a temporary increase in latency. Normally, when a request times out, the client will issue another request with the same timeout value. However, by increasing the timeout value on a retry request after a failed request, we can do both of the following:

Be less sensitive to unfavorable network or load conditions on the server side
Determine whether we actually have a server failure

We propose a new way of dynamically setting timeouts, something we call sequential timeouts. Define an increasing sequence of values, $a_1, \dots, a_N$ . The client will send its first request with $a_1$ , and if we time out with some timeout value $a_m$ , we will send a retry with the longer timeout $a_{m+1}$ . This allows the system to be resilient over the short-term.

Mathematical Model for Expected Latency

First, we introduce two functions that take in timeout value. Define $f$ to be the probability density function for latency, and define $g$ to be a “cost” function: how much latency increases given a higher timeout value. We propose the following model $E$ , the expected value of latency, given some timeout value $t$ :

E(t) \;=\; \frac{\int_t^{\infty} f(x)\,dx}{\int_0^{\infty} f(x)\,dx}\,\bigl(t + E(t)\bigr) \;+\; \frac{\int_0^t f(x)\,dx}{\int_0^{\infty} f(x)\,dx} \cdot \frac{\int_0^t x\,f(x)\,dx}{\int_0^t f(x)\,dx} \;+\; g(t)

The recurrence is a two-state Markov chain: a request is either Uncompleted (still outstanding) or Completed. From Uncompleted it self-loops with probability $\int_t^{\infty} f(x)\,dx / \int_0^{\infty} f(x)\,dx$ (we timed out and try again) and transitions to Completed with probability $\int_0^t f(x)\,dx / \int_0^{\infty} f(x)\,dx$ .

Fig 1 · Markov chain of one request attempt. Drag along the top strip to change t; the self-loop weight is the timeout probability, the transition weight is the success probability.

In order to use this model, we first derive $E$ .

E(t) \;=\; \frac{t\!\int_t^{\infty}\! f(x)\,dx \;+\; \int_0^t\! x\,f(x)\,dx \;+\; g(t)\!\int_0^{\infty}\! f(x)\,dx}{\int_0^{\infty}\! f(x)\,dx}.

We then minimize this function over $t$ to determine the optimal timeout value.

›Show derivation

Let us break this model down into its parts.

$\dfrac{\int_t^{\infty} f(x)\,dx}{\int_0^{\infty} f(x)\,dx}$	the probability that a request times out.
$t + E(t)$	the amount of time taken by another request (we timed out, so we need to try again).
$\dfrac{\int_0^t f(x)\,dx}{\int_0^{\infty} f(x)\,dx}$	the probability that a request succeeds.
$\dfrac{\int_0^t x\,f(x)\,dx}{\int_0^t f(x)\,dx}$	the expected latency given that the request took under time $t$ to complete.
$g(t)$	cost for sending an additional request.

Extension to sequences

This model is currently useful for changes in the long-term (simply recompute timeout values with new probability density function) but is ineffective in situations of short-term change; spikes in latency will always result in timeouts. To mitigate this issue, we use sequential timeout values. Define an increasing sequence $\{t_n\}_{0 \le n \le z}$ for some $z$ . We will always initially send a request with timeout value $t_0$ , but whenever we encounter a timeout at $t_i$ , we will send a retry with timeout value $t_{i+1}$ . If we timeout with value $t_z$ , the next request will be sent with timeout value $t_z$ again. $t_z$ is an input to the model.

E_n \;=\; \begin{cases} a_n + b_n\,E_{n+1} & n < z \\[6pt] \dfrac{a_z}{1 - b_z} & n \ge z \end{cases}

In order to use this improved model, we need to minimize it over $t_0, t_1, \dots, t_z$ . Since this $z+1$ -dimensional minimization is very computationally intensive, we propose a different implementation. Requiring $\nabla E_0 = \mathbf{0}$ reduces to a per-index condition — given $t_z$ , we work backwards to determine all $t_i$ by solving

E_{i+1} \;=\; \frac{\int_{t_i}^{\infty}\! f(x)\,dx \;+\; g'(t_i)\!\int_0^{\infty}\! f(x)\,dx}{f(t_i)}.

›Show derivation

For $n \ne z$ , let $E_n = a_n + b_n\,E_{n+1}$ . When $n = z$ , $E_z = a_z + b_z E_z$ , or $E_z = a_z / (1 - b_z)$ . Deriving $a_n$ and $b_n$ for future use:

a_n \;=\; \frac{\int_0^{t_n}\! x\,f(x)\,dx \;+\; t_n\!\int_{t_n}^{\infty}\! f(x)\,dx}{\int_0^{\infty}\! f(x)\,dx} \;+\; g(t_n)

b_n \;=\; \frac{\int_{t_n}^{\infty}\! f(x)\,dx}{\int_0^{\infty}\! f(x)\,dx}

To find minima we require $\nabla E_0 = \mathbf{0}$ . Expanding the chain,

\frac{\partial E_0}{\partial t_i} \;=\; \frac{\partial}{\partial t_i}\Bigl(a_0 + b_0\bigl(a_1 + b_1(a_2 + b_2(\cdots + a_i + b_i E_{i+1})\cdots)\bigr)\Bigr)

\phantom{\frac{\partial E_0}{\partial t_i}} \;=\; b_0 b_1 \cdots b_{i-1}\left(\frac{d a_i}{d t_i} + E_{i+1}\,\frac{d b_i}{d t_i}\right)

Since the $b_i$ are strictly positive, this vanishes iff $da_i/dt_i + E_{i+1}\,db_i/dt_i = 0$ . From the definitions above,

\frac{d a_i}{d t_i} \;=\; \frac{\int_{t_i}^{\infty}\! f(x)\,dx}{\int_0^{\infty}\! f(x)\,dx} + g'(t_i), \qquad \frac{d b_i}{d t_i} \;=\; -\,\frac{f(t_i)}{\int_0^{\infty}\! f(x)\,dx}.

Substituting and solving for $E_{i+1}$ gives equation (6). As we know $t_z$ , and have that $E_z = a_z/(1-b_z)$ , we can work our way backwards to determine all $t_i$ .

Tree search

Equation (6) is generally non-linear and for any distribution with more than one mode has several roots in each interval. The recurrence therefore branches: at every level there are multiple admissible $t_i$ , one broadly per mode. The Optimizer enumerates the whole tree and picks the leaf with the smallest $E_0$ .

In order to use the mathematical model outlined previously, we created a tree-based search algorithm to recursively find solutions to equation (6). First, we sampled regularly spaced values between an upper and lower bound (the minimum and maximum observed latencies, respectively) and determined the closest solution for each. For each of these solutions, excluding duplicates, we solve the equation again, ending up with a tree. When the tree depth (the number of elements in the timeout sequence, specified by the user) is reached, solutions are not found, and the sequence is ended by $t_z$ .

The tree is drawn as the bottom pane of the interactive figure in the next section. Every dot is a candidate $t$ at some depth; every edge is a parent to child relationship in the recursion. Faint edges are non-optimal branches; the red path is the sequence with the smallest $E_0$ , and its dots sit under the vertical retry-ladder lines that pass through the panes above. On multi-modal distributions the optimal path visibly spans across modes — which is exactly what a good retry ladder should do.

Interactive solving

Below is the Optimizer running live. Drag $t_z$ along the axis; the earlier $t_i$ markers are computed by solving the recurrence backwards.

Fig 2 · Three panes stacked. Top: latency PDF f(x) as filled area, cost g(x) as dashed diagonal. Middle: E(t) = a(t) / (1 − b(t)). Bottom: full search tree with the optimal path in red. Vertical rules are the retry ladder and pass through the optimal dots below.

Dynamic Timeout Control

In certain cases, it can be expensive to collect large amounts of data. Additionally, day-to-day variations are hard to account for in systems that process a lot of data to arrive at a perfect timeout value. When the latency of a system spikes, it is important to increase timeout values immediately in order to prevent cascading failures. In this approach, we take inspiration from the TCP congestion control algorithms.

TCP keeps track of a value known as cwnd, or congestion window. It modifies the cwnd by an amount known as the mss, or minimum segment size. TCP congestion control algorithms all have three phases:

Slow start, when TCP is aggressive and increases the cwnd by 1 mss upon every acknowledgement.
Congestion avoidance, when TCP is cautious and increases the cwnd by 1 mss per round trip time.
Fast recovery, when TCP encounters a packet loss and reduces cwnd to 1 or by a factor of $1/2$ .

We extend the key ideas here (upon a failure, be more lenient; upon a success, be more strict) to our dynamic timeout system:

Decrease timeout value on a successful request
Increase timeout value on failed request (timed out)

Combined System

Following evaluation of the Optimizer and the Controller independently, we discovered that the former was under-responsive and the latter was over-responsive (see Conclusions). Given these opposite problems, we propose a combined architecture that resolves both. Given the rapidly correcting Controller, we use this system for timeouts on diagnostic requests, those sent on a regular interval to determine the true latency of the system (not cut off by the Optimizer’s timeouts). The Optimizer was also modified to consider newer requests more than older requests by skewing the input data: the $i$ th oldest request in the buffer is repeated $i$ times, then fed to the algorithm. The Combined System is a Local architecture.

Testbed

A preliminary goal of the project was to implement a new distributed system from the ground up. DeathStarBench’s Social Network was considered but was difficult to modify — it uses Thrift for RPC calls, and Thrift did not have a mechanism to set or modify timeouts.

The testbed was designed with three principles: Simplicity, Robustness, and Comprehensibility. Systems were implemented in Python with a microservice library called Py-MS. A microservice generator takes a configuration file and creates a base for every service, letting the developer focus on service logic rather than boilerplate. Each service ran in a separate container on Debian-Slim Linux and communicated via HTTP requests; WRK2 supplied load and Jaeger provided tracing.

Because our algorithms operate between exactly two services, we created an even simpler testbed with only two services, App1 and App2. Our algorithms run outside of both services, so requests are sent to them to set timeout values. App2 models changes in latency by sleeping for a certain amount of time on each request given by a latency model function. App1 sends a request to App2, and if it gets a response back without timing out, it returns the elapsed time. Otherwise the response is code 500, and the tester outside the services records the elapsed time as the current timeout value.

Evaluation

We evaluated the latency on the two-service testbed, testing eight different scenarios, each 2000 requests long. Each algorithm was allowed a 200-request initialization period. Exponential backoff is modeled as a 5-element sequence whose first element is 20% higher than the starting latency and whose factor is 2.

Scenarios:

Stable — a constant baseline latency
Mean-Reverting Random Walk (mean 0.125 s, volatility 0.01, reversion 0.3)
Slow Increase / Slow Decrease — linear ramps between 0.1 s and 0.4 s
Fast Increase / Fast Decrease — step changes between 0.1 s and 0.4 s
Spikes / Dips — periodic excursions between 0.1 s and 0.4 s

Each solution is evaluated on three metrics: Speed (how fast timeouts recompute), Feasibility (resource usage per request), and Robustness (how many requests time out, and how close the timeout is to the observed latency).

Fig 3 · Simulated 800-request trace. Pick a scenario and algorithm from the dropdowns to see the timeout adapt over the run.

Results

The metric that best captures overall efficiency is Time Fraction — total elapsed time divided by the integral of the ideal latency curve. A value of $1.00$ means we spent exactly what an oracle would have; anything above is overhead.

Scenario	Combined	Exp. Backoff
Stable	0.861	1.07
Random walk	0.91	1.04
Slow increase	1.05	1.57
Fast increase	1.02	1.57
Slow decrease	1.05	1.08
Fast decrease	1.01	1.05
Spikes	0.981	1.20
Dips	1.04	1.06

Tab 1 · Time Fraction (elapsed time / integral of the latency model), Combined System vs Exponential Backoff. Lower is better.

Conclusions

The Controller and Optimizer significantly outperform Exponential Backoff on scenarios where the latency increases. Exponential Backoff performs equivalently to our Controller and Optimizer when latency is decreasing. The Controller performs better on Spikes than the Optimizer and Exponential Backoff, both performing equally. On Dips, the Optimizer performs equivalently to Exponential Backoff, both performing better than the Controller.

The Controller is able to maintain all of its statistics. However, it has a fundamental problem illustrated by how it times out on the way up from dips: it is much too dynamic, and its timeouts are not really useful in understanding the state of a microservice. On the contrary, the optimizer solution is too static, seen in how it takes a very long time to increase its timeout values on the fast increase.

The Combined solution remedies both of these issues, and by skewing data to newer results, it also outperforms the Optimizer, specifically in the case of a Fast Increase in latency. As expected, there are not significant differences between the Combined solution and Exponential backoff in Stable latency and Mean Reverting Random Walk. When latency decreases, the Combined solution’s timeout value also falls, giving it an advantage in Timeout Closeness. In situations of Dips and Spikes, the two algorithms perform similarly. When the latency increases, the Combined solution significantly outperforms Exponential Backoff.

In addition, the current testbed is very simplistic as it consisted of only two services. We will extend our methods to a full distributed system, evaluating both the local and global architectures, starting with the Triangle Area distributed system, then SocialNetwork, a significantly larger distributed system with more diverse processes commonly used for benchmarking.

Full paper: math.mit.edu/…/Velamoor-Samanta.pdf.