Papers
Using load shedding to avoid overload
David Yanacek · Amazon Builders' Library (online technical article, published Dec 5, 2019; not a peer-reviewed paper), 2019
Why overload feeds itself: latency, timeout and goodput
The article starts from an observation in load tests: the latency of a lightly utilized server is lower than that of a heavily utilized one, because thread contention, context switches, garbage collection and I/O contention weigh more under load. At some point performance starts degrading even faster. The author ties this to the Universal Scalability Law, derived from Amdahl's law: parallelizing increases throughput, but it is limited by serialization points. In addition, throughput tends to drop when the system receives more work than its resources can handle, since the computer accepts the work but becomes too slow to be useful. When latency exceeds the client timeout, requests start failing; if median latency equals the timeout, half the requests time out and perceived availability is 50%. At that point a latency problem becomes an availability problem. To describe this, the author distinguishes throughput, the total requests per second sent to the server, from goodput, the subset handled without error and fast enough for the client to use the response. Overload amplifies itself in a cycle: when the client times out, all the server's progress on that request is wasted, and clients usually retry, multiplying the load. With a deep chain of services in which every layer retries, an overload in the bottom layer triggers cascading retries that amplify the load exponentially. The result is an overload that becomes a steady state.
The idea of load shedding and the need to test until it breaks
On the surface, load shedding is simple: when the server nears overload, it starts rejecting the excess requests so it can focus on the ones it decided to accept. The goal is to keep the latency of accepted requests low, so that the response arrives before the client's timeout. This way the server keeps availability high for what it accepted, and only the availability of the excess traffic is affected. On the overall availability charts the line still drops, which looks bad, but the key is that accepted requests stay available because they are served quickly. Load shedding lets the server sustain goodput while the offered throughput grows. However, rejecting is not free either, so the server eventually yields to Amdahl's law and goodput drops. The author insists on testing: anyone who has not taken the service under load to the breaking point, and well beyond it, should assume it will fail in the worst possible way. If in an overload test availability quickly falls to zero as throughput rises, it is a sign that load shedding mechanisms are missing. The ideal outcome is for goodput to form a plateau near full utilization and stay flat even as more load is applied. Tests should measure the availability and latency perceived by the client, not just those of the server, and it is through testing that you discover the combination of protections needed, since each mechanism adds complexity and has limited effectiveness.
Not wasting work: deadlines, bounded work, and priorities
A central part of the paper is avoiding throwing work away. If the server realizes in the middle of a request that the client has already timed out, it can abandon the rest instead of delivering a response that no one will hear. To do this, clients can send timeout hints, expressed as an absolute time or as a duration. An absolute time requires synchronized clocks across machines, and a duration requires knowing when to start the timer: under extreme overload, many requests sit in TCP buffers and, by the time the server reads them, the client has already given up. The author also reports that Amazon tries to apply the hints transitively, propagating the remaining time at each hop of the chain. He says that, despite the complications, enforcing the client's deadline on the server is better than the alternative, discarding doomed requests. Another practice is to design services to do bounded work: APIs that can return a lot of data are paginated, which makes it easier to estimate the load of each request, and admission control becomes very hard when the server does not know how much it will cost to process something. Prioritization also helps: the most important request the server receives is the load balancer's ping, because without a response the load balancer stops sending requests and the server sits idle. If an API depends on two calls for the client to finish its work, you should prioritize the one that completes work already started, and calls for the first page of a pagination go behind those for later pages, because a client that sees a failure after page N-1 and discards the results wastes N-2 calls and the retries made along the way.
Hidden queues and layered protection
The author pays close attention to queues. Many modern architectures have in-memory queues connecting thread pools, and every TCP-based service has an operating system buffer per socket, where an enormous volume of requests can pile up. When taking work off a queue, the team checks how long it sat waiting and, at a minimum, records that duration in metrics. Besides bounding queue sizes, the author considers it important to bound the time a request can stay in them, dropping those that are too old to free the server for newer ones, which are more likely to succeed. In an extreme version, a LIFO queue (last in, first out) is used when the protocol allows it; he mentions that HTTP/1.1 pipelining does not support it, but HTTP/2 generally does. Load balancers can also queue connections in what is called a surge queue, and then the server does not know how long the request waited. A generally safe pattern is spillover, which fails fast instead of queueing. The author says the Classic Load Balancer used a surge queue, and the Application Load Balancer rejects excess traffic. On layering, proxies such as NGINX have a maximum connections option, which is useful but used as a last resort, because it is hard to prioritize important traffic and the raw count of in-flight requests can be misleading. The frameworks team's final recommendation was to set the load balancer's and proxy's maximum connections to a high value and let the server apply more precise load shedding using local information, without exceeding the server's number of threads, processes or file descriptors, so that resources are left over for health checks.
Side effects, visibility and serverless alternatives
Load shedding has pitfalls described in the article. When a rejection happens even though capacity is available, it is a false positive, and Amazon's goal is to keep a service's false positive rate at zero. If it is regularly nonzero, the service is too sensitive or hosts are constantly overloaded, which may point to a scaling or balancing problem. You need to instrument who the client was and which operation it called, plus alarms for a meaningful volume of rejections. You also should not pollute latency metrics with requests that failed fast: if the service rejects 60% of traffic, median latency can look great even while the latency of successful requests is terrible. Another risk is disabling reactive autoscaling: if load shedding rejects requests at a CPU target similar to the scaling one, scaling never gets the signal, or gets it late, to launch instances. In addition, the fleet may be running much closer to the rejection point than CPU indicates and have no headroom for the loss of an Availability Zone, so you need to test until it breaks. The article also mentions using it to save money by shaping non-critical traffic such as crawlers, and recommends care and that this shaping happen as early as possible. Finally, serverless environments provide resource isolation: in AWS Lambda each invocation runs in its own environment and serves only one request at a time, so goodput stays flat instead of dropping, although slow dependencies can still raise concurrency.
See the ideas at work
Practice the designs that use this paper in the System Design school.