7 ms·

Using load shedding to avoid overload

243 points by kristianpaul 5y ago

sfkgtbor 5y ago
I think the blog post about load shedding by Netflix has some good examples. "Keeping Netflix Reliable Using Prioritized Load Shedding" https://netflixtechblog.com/keeping-netflix-reliable-using-prioritized-load-shedding-6cc827b02f94 https://netflixtechblog.com/keeping-netflix-reliable-using-p...
- athoscouto 5y ago
  I also like "Performance Under Load" by Eran Landau, William Thurston and Tim Bozarth (https://netflixtechblog.medium.com/performance-under-load-3e6fa9a60581 https://netflixtechblog.medium.com/performance-under-load-3e...) very much.
zinekeller 5y ago
It is also a concept on electricity grid management: https://en.wikipedia.org/wiki/Rolling_blackout https://en.wikipedia.org/wiki/Rolling_blackout
- edge17 5y ago
  Indeed. This is the first I've heard the term used outside electric grid management.
ccannon 5y ago
This is a master class. So many good tidbits.
tyingq 5y ago
The article does mention prioritization, but doesn't mention my favorite pattern with this. A priority queue that favors end users "farther down the process" is nice for load shedding. Like, for an ecommerce site, being able to prioritize users in the checkout path first, not-in-checkout but non-empty cart second, etc. Or prioritizing features in a similar way. Turning off, for example, "people that bought this, bought that", under load.
- dyanacek 5y ago
  This is a great way to describe it! I gave a similar example of pagination and how the later pages might be better to prioritize over initial pagination requests, but your example is a nicer illustration. Thanks for that! There’s also someone I was talking to after writing the article who said they can fall back to statically rendered versions of certain pages on Amazon.com during overload. The trick is to have a page that is still useful! And for the “turning off features” idea - this happens today on Amazon.com. If a feature on the site fails to render successfully or on time, it’s left off of the page. Critical functionality can be left off, so it’s a judgement call on what’s allowed to fail the page render.
  - tyingq 5y ago
    Ah, yes, you're right...I missed the pagination example fitting that pattern. "If a feature on the site fails to render successfully or on time, it’s left off of the page. Critical functionality can be left off, so it’s a judgement call on what’s allowed to fail the page render." Oh, that's useful also, but I meant a step farther where the page doesn't ask for those widgets if (load > X). Which avoids calling it at all.
    - dyanacek 5y ago
      Good point around avoiding the call in the first place. This is a very tricky topic, I’ve found. Things that try to guess the nuanced health of a dependency can lead to outages when they guess wrong. These circuit breakers are helpful if they’re right, but harmful if they’re wrong. For example, say a service is backed by a partitioned cache cluster, where the data is hashed to a particular cache node. Now let’s say one node has a problem, causing requests to data that lives on that node to fail, but others to succeed. If a client is making requests for data that happens to live on all nodes (the client doesn’t know about these nodes by the way, it’s just an implementation detail of the service) and sees an increased error rate, should it start failing some requests? It could take a single partition outage and increase the scope of impact into a full outage. Anyway I’ve been meaning to write an Amazon Builders’ Library article on this topic, or to convince someone else to do it (looking at you, Marc Brooker!)
raister 5y ago
Since we are using the power abstraction, why not instead of load shedding, start up secondary machines servicing, which are slower, but could handle a bunch of simultaneous requests for some clients, or even tertiary ones? That could at least postpone the load shedding, or handle localised surges in service demand due to user behaviour more effectively.
- kevindong 5y ago
  Sometimes there's limits to how high you can scale without overloading dependencies. For example, the database that the service accesses might only support n connections and the service is already using approximately n connections.
- Aachen 5y ago
  The article is in Germany for me so I've only read a part of it before I got tired of trying to read German, but I think they mention as one of the first things that what you describe, preventing an overload in the first place, is their primary strategy. The request dropping (less jargon-y and more descriptive than "load shedding", which refers to consuming more rather than less) only kicks in when that fails or isn't fast enough.
  - zinekeller 5y ago
    This official PDF should be in English: https://d1.awsstatic.com/builderslibrary/pdfs/using-load-shedding-to-avoid-overload.pdf https://d1.awsstatic.com/builderslibrary/pdfs/using-load-she...
  - 5e92cb50239222b 5y ago
    You can change language in the footer, waaay down.
throwaway984393 5y ago
> Goodput is the subset of the throughput that is handled without errors and with low enough latency for the client to make use of the response. "Back in my day..." we used HPS (hits per second) and CPU load as the "goodput". A 'hit' was only recorded via an access log at the end of a successful request<->response. Of course this doesn't measure whether the latency of the responses is unacceptable, just that there was a completed response... so that's where CPU Load came in. If you're doing a lot of HPS and load gets too high, you know latency is just going to get worse to the point of unavailability, so you start load shedding. In our less-advanced old-school practice, load shedding was merely lowering the maximum requests per second option of the HTTP servers, waiting, and lowering again, until the load recovered. Our tools could reconfigure the server's settings without restarting, but required issuing an admin command to the server and "waiting in line" while the server processed all the other CPU requests under load, which meant the problem might continue for longer than we'd like. To get around "waiting in line", you would use a transparent network filter (either a proxy, or IPTables) to load-shed. This can be called a "middlebox" solution. But sometimes termination of connections isn't feasible without "dirty" terminations that might cause bugs in clients or servers... and that's [one of the reasons] why people hate middleboxes. But they're great when they work! You would also probably use Apdex today instead of CPU Load. If your API has contractual minimum latency guarantees, you'd skip Apdex and just use latency itself.
- dyanacek 5y ago
  These remain as great techniques! Even iptables like you mention - it’s extremely good at cheaply shedding new handshakes, vs later on in processing the request. You lose a little visibly, but it’s a powerful outer “layer of the onion”. And good callout on middle boxes. Even high level abstraction ones like Amazon API Gateway. In fact this is my favorite feature of it. API Gateway can reject a very high rate of excess traffic for a small overloaded service behind it.
samwisedum 5y ago
Denying requests to avoid fulfilling requests
- dyanacek 5y ago
  It’s a tricky topic because load shedding is a last resort that kicks in when there’s already a problem. So until auto scaling catches up or the issue is mitigated some other way, we try to make as many customers happy as possible, rather than making everyone equally unhappy.
motohagiography 5y ago
Related concept in a recent HN thread about a paper describing how to use randomization to increase system resiliance: https://news.ycombinator.com/item?id=28702821 https://news.ycombinator.com/item?id=28702821
jeffbee 5y ago
This is a great article but leaves out a key idea. Load shedding is really a key topic in cost utilization. You need load shedding to be able to serve closer to your capacity red line. You can always buy your way out of overload. Load shedding is a feature that, if you have it, allows you to more comfortably dial back your resources and serve closer to the limit.
- ozzythecat 5y ago
  > You can always buy your way out of overload. Not really. My service may depend on other services that I have no control over. Perhaps I have extra money to scale up my own service, but those other services may be owned by different teams or organizations entirely.
  - shukantpal 5y ago
    With money, you can in-house those services and scale them up if those "other" organizations won't scale up.
    - ozzythecat 5y ago
      With infinite money, sure. Realistically you won’t have the budget. And even if it’s “in house”, it’s going to be some service run by another team or organization within your company that has their own priorities, roadmap, and deliverables. They’re not just going to scale up their service because you asked them. They basically don’t have to do anything for you at all. And even if they agree - everything has a cost. There’s simply the overhead of even sending an email or a Slack message and setting up a meeting, getting people ramped up on your use case, why you need them to scale, for how long, for what use cases, etc etc. everything has a cost and money and budget are always constrained.
      - shukantpal 5y ago
        That's why the "with money" not "with little money"
- 5y ago
vander_elst 5y ago
Related: https://sre.google/sre-book/addressing-cascading-failures/#xref_cascading-failure_load-shed-graceful-degredation https://sre.google/sre-book/addressing-cascading-failures/#x...
londons_explore 5y ago
Most real world services have dependencies, and load tests don't accurately represent the fact that the dependencies have other users and changes in performance of a dependency will dramatically change the performance of the service being tested. That pretty much means you can't have hard coded '100 requests per second per instance'. Instead, I suspect the future of load shedding is automatic maximum "goodput" tracking. For example, the load balancer can alternate between 90 and 100 parallel requests, and if more requests are completed with fewer parallel requests then start alternating between 80 and 90 to figure which of those is better...
throwawaythekey 5y ago
Load shedding as a technique seems to make sense but to me it never seems to be the correct tool to reach for. Of course you need some basic load shedding to handle ddos type scenarios, but anything beyond that seems like overkill. At (work) our services achieve high availability (99.99%) simply by being composed of reliable parts. Most effort is focused here and it seems to have a good payoff ratio. When we do try to add anything like graceful degradation it seems to strongly hurt code readability/ease of understanding because it requires additional code branches and either a fair bit of boilerplate or extra abstractions. This could be a result of the scale we are at/the maturity of our tools but I'm interested in if anyone else has some hands on experience.

243 points by kristianpaul 5y ago

I think the blog post about load shedding by Netflix has some good examples. "Keeping Netflix Reliable Using Prioritized Load Shedding" https://netflixtechblog.com/keeping-netflix-reliable-using-prioritized-load-shedding-6cc827b02f94 https://netflixtechblog.com/keeping-netflix-reliable-using-p...

athoscouto 5y ago
I also like "Performance Under Load" by Eran Landau, William Thurston and Tim Bozarth (https://netflixtechblog.medium.com/performance-under-load-3e6fa9a60581 https://netflixtechblog.medium.com/performance-under-load-3e...) very much.

zinekeller 5y ago

It is also a concept on electricity grid management: https://en.wikipedia.org/wiki/Rolling_blackout https://en.wikipedia.org/wiki/Rolling_blackout

edge17 5y ago
Indeed. This is the first I've heard the term used outside electric grid management.

ccannon 5y ago

This is a master class. So many good tidbits.

tyingq 5y ago

The article does mention prioritization, but doesn't mention my favorite pattern with this. A priority queue that favors end users "farther down the process" is nice for load shedding. Like, for an ecommerce site, being able to prioritize users in the checkout path first, not-in-checkout but non-empty cart second, etc. Or prioritizing features in a similar way. Turning off, for example, "people that bought this, bought that", under load.

dyanacek 5y ago
This is a great way to describe it! I gave a similar example of pagination and how the later pages might be better to prioritize over initial pagination requests, but your example is a nicer illustration. Thanks for that! There’s also someone I was talking to after writing the article who said they can fall back to statically rendered versions of certain pages on Amazon.com during overload. The trick is to have a page that is still useful! And for the “turning off features” idea - this happens today on Amazon.com. If a feature on the site fails to render successfully or on time, it’s left off of the page. Critical functionality can be left off, so it’s a judgement call on what’s allowed to fail the page render.
- tyingq 5y ago
  Ah, yes, you're right...I missed the pagination example fitting that pattern. "If a feature on the site fails to render successfully or on time, it’s left off of the page. Critical functionality can be left off, so it’s a judgement call on what’s allowed to fail the page render." Oh, that's useful also, but I meant a step farther where the page doesn't ask for those widgets if (load > X). Which avoids calling it at all.
  - dyanacek 5y ago
    Good point around avoiding the call in the first place. This is a very tricky topic, I’ve found. Things that try to guess the nuanced health of a dependency can lead to outages when they guess wrong. These circuit breakers are helpful if they’re right, but harmful if they’re wrong. For example, say a service is backed by a partitioned cache cluster, where the data is hashed to a particular cache node. Now let’s say one node has a problem, causing requests to data that lives on that node to fail, but others to succeed. If a client is making requests for data that happens to live on all nodes (the client doesn’t know about these nodes by the way, it’s just an implementation detail of the service) and sees an increased error rate, should it start failing some requests? It could take a single partition outage and increase the scope of impact into a full outage. Anyway I’ve been meaning to write an Amazon Builders’ Library article on this topic, or to convince someone else to do it (looking at you, Marc Brooker!)

raister 5y ago

Since we are using the power abstraction, why not instead of load shedding, start up secondary machines servicing, which are slower, but could handle a bunch of simultaneous requests for some clients, or even tertiary ones? That could at least postpone the load shedding, or handle localised surges in service demand due to user behaviour more effectively.

kevindong 5y ago
Sometimes there's limits to how high you can scale without overloading dependencies. For example, the database that the service accesses might only support n connections and the service is already using approximately n connections.
Aachen 5y ago
The article is in Germany for me so I've only read a part of it before I got tired of trying to read German, but I think they mention as one of the first things that what you describe, preventing an overload in the first place, is their primary strategy. The request dropping (less jargon-y and more descriptive than "load shedding", which refers to consuming more rather than less) only kicks in when that fails or isn't fast enough.
- zinekeller 5y ago
  This official PDF should be in English: https://d1.awsstatic.com/builderslibrary/pdfs/using-load-shedding-to-avoid-overload.pdf https://d1.awsstatic.com/builderslibrary/pdfs/using-load-she...
- 5e92cb50239222b 5y ago
  You can change language in the footer, waaay down.

throwaway984393 5y ago

> Goodput is the subset of the throughput that is handled without errors and with low enough latency for the client to make use of the response. "Back in my day..." we used HPS (hits per second) and CPU load as the "goodput". A 'hit' was only recorded via an access log at the end of a successful request<->response. Of course this doesn't measure whether the latency of the responses is unacceptable, just that there was a completed response... so that's where CPU Load came in. If you're doing a lot of HPS and load gets too high, you know latency is just going to get worse to the point of unavailability, so you start load shedding. In our less-advanced old-school practice, load shedding was merely lowering the maximum requests per second option of the HTTP servers, waiting, and lowering again, until the load recovered. Our tools could reconfigure the server's settings without restarting, but required issuing an admin command to the server and "waiting in line" while the server processed all the other CPU requests under load, which meant the problem might continue for longer than we'd like. To get around "waiting in line", you would use a transparent network filter (either a proxy, or IPTables) to load-shed. This can be called a "middlebox" solution. But sometimes termination of connections isn't feasible without "dirty" terminations that might cause bugs in clients or servers... and that's [one of the reasons] why people hate middleboxes. But they're great when they work! You would also probably use Apdex today instead of CPU Load. If your API has contractual minimum latency guarantees, you'd skip Apdex and just use latency itself.

dyanacek 5y ago
These remain as great techniques! Even iptables like you mention - it’s extremely good at cheaply shedding new handshakes, vs later on in processing the request. You lose a little visibly, but it’s a powerful outer “layer of the onion”. And good callout on middle boxes. Even high level abstraction ones like Amazon API Gateway. In fact this is my favorite feature of it. API Gateway can reject a very high rate of excess traffic for a small overloaded service behind it.

samwisedum 5y ago

Denying requests to avoid fulfilling requests

dyanacek 5y ago
It’s a tricky topic because load shedding is a last resort that kicks in when there’s already a problem. So until auto scaling catches up or the issue is mitigated some other way, we try to make as many customers happy as possible, rather than making everyone equally unhappy.

motohagiography 5y ago

Related concept in a recent HN thread about a paper describing how to use randomization to increase system resiliance: https://news.ycombinator.com/item?id=28702821 https://news.ycombinator.com/item?id=28702821

jeffbee 5y ago

This is a great article but leaves out a key idea. Load shedding is really a key topic in cost utilization. You need load shedding to be able to serve closer to your capacity red line. You can always buy your way out of overload. Load shedding is a feature that, if you have it, allows you to more comfortably dial back your resources and serve closer to the limit.

ozzythecat 5y ago
> You can always buy your way out of overload. Not really. My service may depend on other services that I have no control over. Perhaps I have extra money to scale up my own service, but those other services may be owned by different teams or organizations entirely.
- shukantpal 5y ago
  With money, you can in-house those services and scale them up if those "other" organizations won't scale up.
  - ozzythecat 5y ago
    With infinite money, sure. Realistically you won’t have the budget. And even if it’s “in house”, it’s going to be some service run by another team or organization within your company that has their own priorities, roadmap, and deliverables. They’re not just going to scale up their service because you asked them. They basically don’t have to do anything for you at all. And even if they agree - everything has a cost. There’s simply the overhead of even sending an email or a Slack message and setting up a meeting, getting people ramped up on your use case, why you need them to scale, for how long, for what use cases, etc etc. everything has a cost and money and budget are always constrained.
    - shukantpal 5y ago
      That's why the "with money" not "with little money"
5y ago

vander_elst 5y ago

Related: https://sre.google/sre-book/addressing-cascading-failures/#xref_cascading-failure_load-shed-graceful-degredation https://sre.google/sre-book/addressing-cascading-failures/#x...

londons_explore 5y ago

Most real world services have dependencies, and load tests don't accurately represent the fact that the dependencies have other users and changes in performance of a dependency will dramatically change the performance of the service being tested. That pretty much means you can't have hard coded '100 requests per second per instance'. Instead, I suspect the future of load shedding is automatic maximum "goodput" tracking. For example, the load balancer can alternate between 90 and 100 parallel requests, and if more requests are completed with fewer parallel requests then start alternating between 80 and 90 to figure which of those is better...

throwawaythekey 5y ago

Load shedding as a technique seems to make sense but to me it never seems to be the correct tool to reach for. Of course you need some basic load shedding to handle ddos type scenarios, but anything beyond that seems like overkill. At (work) our services achieve high availability (99.99%) simply by being composed of reliable parts. Most effort is focused here and it seems to have a good payoff ratio. When we do try to add anything like graceful degradation it seems to strongly hurt code readability/ease of understanding because it requires additional code branches and either a fair bit of boilerplate or extra abstractions. This could be a result of the scale we are at/the maturity of our tools but I'm interested in if anyone else has some hands on experience.