4 ms·

Ha, I wrote one of these a year ago. The problem being solved was gracefully degrading a service if the request volume was too high. Some additional tweaks you

by hansvm 2y ago

Ha, I wrote one of these a year ago. The problem being solved was gracefully degrading a service if the request volume was too high. Some additional tweaks you might care about: 1. It's easy to change the "numerator" being measured to something continuous rather than discrete. As a rate limiter in my application I found CPU seconds per second to be much more useful than requests per second. If you have more control over the low-level networking then queue depth or something might be more applicable, but you work with what you have. 2. It's easy to change the units of the configuration parameters. I haven't checked if it's already in these units for example, but TFA's "averaging period" can easily be re-cast as a half-life (in microseconds or hours or whatever's most convenient). Anywho, this is a nice write-up on exponential smoothing. I like the attention to edge cases affecting rate-limiting specifically. As a bit of a fun aside, the state-update equation here is an Euler update solving the exponential ODE, fusing in the new knowledge you have (new requests) as instantaneous tweaks. For rate-limiting in particular the exponential is probably a good choice (numerically stable, hardware instructions, works even when time gaps or other features are far outside of your intended configuration space, ...), but in other domains, like memoryless (still "stateful", obviously, but only requiring an amalgamation condensed into the very last state, as opposed to some O(n) thing) animation updates, you might prefer other properties like the ability to decay to exactly 0 in finite time. You can also recover leaky buckets and other similar algorithms with the right choice of ODE.

brightball 2y ago
> As a rate limiter in my application I found CPU seconds per second to be much more useful than requests per second. This is really insightful and makes good sense. I've toyed for years with the idea of building a "Cost Benefit Cache" that basically tracked the request volume for a piece of data, the time to retrieve that data and the size of the data retrieved to make decisions about what to cache during system stress. The idea was basically a cost benefit formula where the cost is the size of the data, so how much of the available cache space would it use, while the benefit is the seconds of savings from requests * average retrieval time. Requests per second alone doesn't really matter if the request is low/no impact.
- CBLT 2y ago
  Google had a library like that, and one of the foot guns is that requests that are malformed or otherwise do 0 work have incredibly low cost, which results in them being prioritized above all other requests. Every user had to configure some obscure options to set cost multipliers based on return code to try and correct for this, which felt like a pretty fundamental bug that was being hacked around. Edit: this was actually for cost-based load balancing, not load shedding. You obviously can't load shed based on return code.
  - travisjungroth 2y ago
    Interesting that “if the request is bad or there’s an error” is a difficult condition to implement universally.
    - jpollock 2y ago
      When you've got 80,000 engineers you end up with lots of different opinions on what the wire protocol should look like. * Sometimes, you want to fail closed - errors are returned for all errors. * Sometimes, you want to fail open - ok is returned for errors. * Sometimes, you want to separate "failure" from "denied", the code "worked", but it didn't do what the client wanted - think "payment declined", so you return "OK", with the actual result in the response. Compare the different costs to charge a credit card that is expired vs one that works. * The expired one can be checked before calling out to the processor - cheap, returns "OK + Declined". * The success ends up with a call to the processor and takes a second or two, returns "OK + Success".
    - hansvm 2y ago
      Some things are really hard to appropriately abstract, but there's so much similarity we can't help but be tempted to try. Soemthing that I wrote at $WORK recently was a data-oriented exponentially smoothed reservoir sampling order statistic randomized splay tree. All of those components exist individually. Even picking on two of them though; given a tree implementation it's trivial (as a human) to create an analogous order-statistic tree. In any pseudo-mainstream programming language though, especially at a system level, how do you tack on the "order-statistic" behavior to an arbitrary tree? It's not too bad if you additional require some interface the primary tree needs to adhere to. That interface is, necessarily, biased toward the needs of an order-statistic tree though. There isn't actually that much difference between implementing a tree which adheres to the interface and one which just does every operation manually. Plus, there are some allocation questions and other inefficiencies (or, alternatively, unsoundness) that level of abstraction introduces which you can avoid by writing the whole thing from scratch. Bringing it back to the $GOOG library, the problem is that you have a lot of code which _looks_ like it's the same, but it's impossible to make it actually _be_ the same without heavy lifting for callers of that library. Taking those monolithic frameworks (e.g., inadvisedly popular rate-limiting shenanigans) and turning them into libraries of helpful utilities often helps. General solutions are harder to come by.
jeffbee 2y ago
CPU rate is only quasi-continuous. The fact of a thread running or not running is binary. You cannot be 63% on a CPU, that is an illusion of sampling and integration. But the real trouble with CPU rate is that it represents the past, not the future. It tells you what happened to the last request and nothing about what will happen to the next request. A signal with actual predictive power is how many other requests are running or waiting to run.
- hansvm 2y ago
  Like everything, the devil's in the details. In our case, non-idle cumulative thread CPU time (including system activity) is a nice metric. If it exceeds 70%, start sending some 503s (or 500s depending on the client). A single core can easily service 100B requests per day, a few times more than we needed to, so if we exceeded that by enough margin to saturate every core to 70% then the right course of action was some combination of (1) scale up, and (2) notify engineering that a moderately important design assumption was violated. We could still service 100B requests per day per core, but the excess resulted in a few 5xx errors for a minute while autoscaling kicked in. It's not good enough for every service, but it was absolutely what we needed and leaps and bounds better than what we had before, with a side-benefit of being "obviously" correct (simple code causes fewer unexpected bugs). The core idea (in tweaking the numerator in exponential smoothing) isn't any easily refutable definition of CPU time though. It's that you're able to tailor the algorithm to your individual needs. A related metric is just the wall-clock time from the beginning of a request being queued till when it was serviced (depending on your needs, maybe compared to the actual processing time of said request). If you ever get to total_time >= 2 * processing_time, that likely indicates a queue about to exceed a critical threshold. > how many other requests are running or waiting to run I referenced that idea pretty explicitly: "If you have more control over the low-level networking then queue depth or something might be more applicable, but you work with what you have." Yes, that matters. That doesn't make other approaches invalid. Even then, you usually want a smoothed version of that stat for automated decision-making.

by hansvm 2y ago

brightball 2y ago

> As a rate limiter in my application I found CPU seconds per second to be much more useful than requests per second. This is really insightful and makes good sense. I've toyed for years with the idea of building a "Cost Benefit Cache" that basically tracked the request volume for a piece of data, the time to retrieve that data and the size of the data retrieved to make decisions about what to cache during system stress. The idea was basically a cost benefit formula where the cost is the size of the data, so how much of the available cache space would it use, while the benefit is the seconds of savings from requests * average retrieval time. Requests per second alone doesn't really matter if the request is low/no impact.

CBLT 2y ago
Google had a library like that, and one of the foot guns is that requests that are malformed or otherwise do 0 work have incredibly low cost, which results in them being prioritized above all other requests. Every user had to configure some obscure options to set cost multipliers based on return code to try and correct for this, which felt like a pretty fundamental bug that was being hacked around. Edit: this was actually for cost-based load balancing, not load shedding. You obviously can't load shed based on return code.
- travisjungroth 2y ago
  Interesting that “if the request is bad or there’s an error” is a difficult condition to implement universally.
  - jpollock 2y ago
    When you've got 80,000 engineers you end up with lots of different opinions on what the wire protocol should look like. * Sometimes, you want to fail closed - errors are returned for all errors. * Sometimes, you want to fail open - ok is returned for errors. * Sometimes, you want to separate "failure" from "denied", the code "worked", but it didn't do what the client wanted - think "payment declined", so you return "OK", with the actual result in the response. Compare the different costs to charge a credit card that is expired vs one that works. * The expired one can be checked before calling out to the processor - cheap, returns "OK + Declined". * The success ends up with a call to the processor and takes a second or two, returns "OK + Success".
  - hansvm 2y ago
    Some things are really hard to appropriately abstract, but there's so much similarity we can't help but be tempted to try. Soemthing that I wrote at $WORK recently was a data-oriented exponentially smoothed reservoir sampling order statistic randomized splay tree. All of those components exist individually. Even picking on two of them though; given a tree implementation it's trivial (as a human) to create an analogous order-statistic tree. In any pseudo-mainstream programming language though, especially at a system level, how do you tack on the "order-statistic" behavior to an arbitrary tree? It's not too bad if you additional require some interface the primary tree needs to adhere to. That interface is, necessarily, biased toward the needs of an order-statistic tree though. There isn't actually that much difference between implementing a tree which adheres to the interface and one which just does every operation manually. Plus, there are some allocation questions and other inefficiencies (or, alternatively, unsoundness) that level of abstraction introduces which you can avoid by writing the whole thing from scratch. Bringing it back to the $GOOG library, the problem is that you have a lot of code which _looks_ like it's the same, but it's impossible to make it actually _be_ the same without heavy lifting for callers of that library. Taking those monolithic frameworks (e.g., inadvisedly popular rate-limiting shenanigans) and turning them into libraries of helpful utilities often helps. General solutions are harder to come by.

jeffbee 2y ago

CPU rate is only quasi-continuous. The fact of a thread running or not running is binary. You cannot be 63% on a CPU, that is an illusion of sampling and integration. But the real trouble with CPU rate is that it represents the past, not the future. It tells you what happened to the last request and nothing about what will happen to the next request. A signal with actual predictive power is how many other requests are running or waiting to run.

hansvm 2y ago
Like everything, the devil's in the details. In our case, non-idle cumulative thread CPU time (including system activity) is a nice metric. If it exceeds 70%, start sending some 503s (or 500s depending on the client). A single core can easily service 100B requests per day, a few times more than we needed to, so if we exceeded that by enough margin to saturate every core to 70% then the right course of action was some combination of (1) scale up, and (2) notify engineering that a moderately important design assumption was violated. We could still service 100B requests per day per core, but the excess resulted in a few 5xx errors for a minute while autoscaling kicked in. It's not good enough for every service, but it was absolutely what we needed and leaps and bounds better than what we had before, with a side-benefit of being "obviously" correct (simple code causes fewer unexpected bugs). The core idea (in tweaking the numerator in exponential smoothing) isn't any easily refutable definition of CPU time though. It's that you're able to tailor the algorithm to your individual needs. A related metric is just the wall-clock time from the beginning of a request being queued till when it was serviced (depending on your needs, maybe compared to the actual processing time of said request). If you ever get to total_time >= 2 * processing_time, that likely indicates a queue about to exceed a critical threshold. > how many other requests are running or waiting to run I referenced that idea pretty explicitly: "If you have more control over the low-level networking then queue depth or something might be more applicable, but you work with what you have." Yes, that matters. That doesn't make other approaches invalid. Even then, you usually want a smoothed version of that stat for automated decision-making.