6 ms·

How to Design a Scalable Rate Limiting Algorithm

196 points by pidginbil 9y ago

RealNeatoDude 9y ago
Excellent article! One question though: > A better approach is to use a “set-then-get” mindset, relying on atomic operators that implement locks in a very performant fashion, allowing you to quickly increment and check counter values without letting the atomic operations get in the way. Can you elaborate on this? Why is it more performant? And what are the trade-offs vs. get-then-set?
- graphememes 9y ago
  Was passing by and saw this, a better explanation and in-depth analysis can be found here: > https://blog.figma.com/an-alternative-approach-to-rate-limiting-f8a06cf7c94c https://blog.figma.com/an-alternative-approach-to-rate-limit...
luckystarr 9y ago
For a different view on the topic watch "Stop Rate Limiting! Capacity Management Done Right" https://www.youtube.com/watch?v=m64SWl9bfvk https://www.youtube.com/watch?v=m64SWl9bfvk The basic premise is not do do req/s limiting but rather concurrency limiting which results in req/s limiting by itself. Concurrency limiting is rather simple and doesn't require a lot of code complexity.
- daddykotex 9y ago
  This video was very interesting, thanks for sharing!
- snoman 9y ago
  Wow! That was an incredible talk/demonstration. Thanks for that!
- zie 9y ago
  The problem here is, it depends on WHY you are rate limiting. If it's just to balance so you don't overload your backends, then absolutely this is a great way to do it. If however you are trying to limit client(s) because the service is an authentication gateway for instance, then you want to limit user/pass requests to X number then concurrency limiting isn't a good way to do that. So you may need both, depending on your use-cases, so it's not a one-size fits all solution.
  - bogomipz 9y ago
    What is the use case for your second example? I am not following. Wouldn't that just be rate limiting by client IP though?
    - zlynx 9y ago
      I heard about a case where someone built a phone app backend without rate limiting. Someone found this hole and successfully attacked 70,000 accounts by running password dictionary cracks against the authentication API. Modern distributed systems are simply too fast and users are too dumb with picking passwords to allow unlimited password attempts.
    - zie 9y ago
      Well you can rate limit via a lot of things, definitely by IP is a good idea, but for ipv6, you typically want to limit by blocks(since every ipv6 user currently usually gets a full block of IP's), but you also probably want to also limit by username, i.e. if you keep trying to login as user 'root', you only get 3 attempts/minute or something. After X attempts via the same IP, you can block/ban that IP via a FW rule/etc for say 5 mins. or 30m, or whatever. It all depends on your security posture, you could go crazy and actually lock the account after 3 failures, but then you hand bad people a free DDOS... so you have to be careful about doing that.. But you could soft-lock and require a correct password and an email address verification after X failed attempts(i.e. correct login, plus they have to click a link in an email). Anyways, see what I'm saying here? Authentication access is something you really want to get right, and it's a complicated topic.
    - 9y ago
- thatusernametho 9y ago
  He mentioned that nginx using lua managed the requests but I didn't see the code for that. Is that available anywhere?
- pwdisswordfish2 9y ago
  On the origin is he only measuring connections? HTTP/1.1 says a single connection can contain more than one request. The client I use has this feature. "Modern" browsers do not. Whether proxies pipeline requests to origin servers (irrespective of the client features) I do not know. But it seems like they could preserve some origin capacity that way. Perhaps they adhere to one request per connection. Ideally, as a user, I think it would be useful to get more diagnostics in response headers on the health of the proxies and origins. Something more informative than HTTP status codes. That way we can build "intelligent clients" that self-adjust to current conditions in response to diagnostics they get in the responses. (The presenter references the adaptive approach of the TCP congestion algorithm.) Some websites return diagnostics in webpage content. But of course one only gets them after a successful (cf. failed) transaction. For example, I believe wikipedia.org or archive.vector.co.uk return some diagnostics on some aspect of their setup (probably not intended to be utilised by clients).
daddykotex 9y ago
Disregarding the article completely, I'll share my opinion on Kong because we use quite a bit at my workplace. We use an old version (0.9.x as of right now). The things I shared below might not be true anymore in new versions but I can't tell and are regarding the plugin system. IMO, the idea of taking things like authentication, rate limiting, etc in a proxy is a wonderful idea (https://2tjosk2rxzc21medji3nfn1g-wpengine.netdna-ssl.com/wp-content/uploads/2017/12/illustration2.png https://2tjosk2rxzc21medji3nfn1g-wpengine.netdna-ssl.com/wp-...). So in theory, the approach Kong takes is wonderful, but I think the implementation is not so much. Kong is layer over nginx and uses lua as a scripting language to add all sorts of stuff. Quickly, you reach the limit of the plugins capability so you think, well, I will write my own plugins. Well, to me it was a very unpleasing experience. I found that the thing was hard to test and hard to maintain. Maybe my criticism is more lua than Kong but since Kong relies heavily on lua, there is not much I can do. There is also magic happening. You declare a schema.lua files to configure the store to hold your data. Then automatically you've got a DAO interface available with a bunch of method on it to work with the store. You don't know what methods are available or what arguments should be passed into these functions. Anyway, this is my take after spending quite a few hours working on home made plugins in lua for Kong. In the end, I'm glad Kong is open source and it's a great piece of software. It helped us reduce our applications complexity but make sure you don't start to shift to much logic into it because the plugin system can be hard to work with.
- khaledtaha 9y ago
  Have you found any viable alternatives to Kong?
  - daddykotex 9y ago
    So far we're still using Kong. Planning an upgrade soon. But we try to avoid shifting to much domain logic in the form of Kong plugins.
    - fosk 9y ago
      If I may ask, what kind of functionality have you been trying to implement in a Kong plugin?
forgotpassagan 9y ago
This may be how Kong does it but it's not really 'high performance'. The right way to do rate limiting is to limit by IP using a counting Bloom Filter or Cuckoo filter along with random samples. When you hit a false positive then you have a second normal rate limiter to 'mop up' IPs that are over the first limiter. This doesn't give you a hard exact limit but gets the job done storing far less state. You also need to bucket by IP sub-ranges in IPV6 to stop people crap flooding you with tons of unique IP's
jdwyah 9y ago
One thing that RateLim.it uses to its advantage is calculating the “nextPossiblePass” for each limit. This allows clients to cache forever that something is over the limit until time X and not have to make another request. In the bursty case this let’s clients effectively short circuit and protect the system. Disclaimer: I work on https://www.ratelim.it/documentation/basic_rate_limits https://www.ratelim.it/documentation/basic_rate_limits
yread 9y ago
Nice article (although the illustrations aren't very... illustrative). Anybody knows how does Kong compare with WSO2 API Manager?
thelicx 9y ago
I have been using Kong since 2016 on various APIs and I have been impressed by the continuous increase of performance after every release. I wish upgrades were easier but I know they are working on it (the "migrations" between each major version), but overall it's a fast and pluggable layer for any API inside or outside the firewall, especially if you are running containers. On this note for those of you who haven't noticed it yet, they have released an Alpine version of their Docker image, but it's still not the default one. I would actually recommend using it to further reduce the size of Kong containers: https://konghq.com/blog/kong-alpine-docker/ https://konghq.com/blog/kong-alpine-docker/
jively 9y ago
> A better approach is to use a “set-then-get” mindset, relying on atomic operators that implement locks in a very performant fashion, allowing you to quickly increment and check counter values without letting the atomic operations get in the way. In a highly distributed system you’d probably want to avoid a centralised data store altogether for fast moving data like rate limits. CRDTs and bucket weighting might be a more effective strategy. The article states that tracking per-node could cause a problem with race conditions but that assumes it’s the counter that’s the problem. If the node cluster is aware of the other nodes and the relative load of the cluster, you can use this value to weight the isolated rate limiter and the only data that needs to be shared can be broadcast between the nodes using a pub/sub mechanism. If some variance is permitted (+/- a margin either side of the limit) then having the nodes synchronise their “token weight” based on the size of the cluster means that the nodes can then manage the rate limit in-memory without ever needing to track in a data store. It does trade-off accuracy, but for accuracy you can then revert to the set-then-get centralised counter, the trade-off being performance because of increased round trip time to the day store. In most rate limit scenarios, at least from what we’ve seen, extreme accuracy isn’t usually that important vs. being able to scale amd rate limit without having to also scale a data layer to handle the counters.
dmaumenee 9y ago
I use Kong EE for a client, I have read Kong EE documentation carefully and made a lot of tests. The current implementation (0.29) have this behavior (that not meet our needs). 1) All incoming requests are take into account, including those which have been rejected (with 429 error). If the consumer exceed his limit during many consecutive time windows, all the requests of the consecutive time windows will be rejected (with 429 error). 2) For a windows size of 1 second, the computed weight of the previous windows is always 100%. If the limit was reach during the previous second, all requests made in the current windows will be rejected (with 429 errors).
dmaumenee 9y ago
The performance degradation of doing strict rate limit relying on Kong Cluster data store (Postgres or Cassandra) is amplified by the lake of database connection pool management. Each incoming http request induce the creation of a new database connection, this process is very expensive especially with Cassandra when authentication is enabled.
SmartWatchPicks 9y ago
Thanks for share . https://www.smartwatchpicks.com/ https://www.smartwatchpicks.com/

196 points by pidginbil 9y ago

Excellent article! One question though: > A better approach is to use a “set-then-get” mindset, relying on atomic operators that implement locks in a very performant fashion, allowing you to quickly increment and check counter values without letting the atomic operations get in the way. Can you elaborate on this? Why is it more performant? And what are the trade-offs vs. get-then-set?

graphememes 9y ago
Was passing by and saw this, a better explanation and in-depth analysis can be found here: > https://blog.figma.com/an-alternative-approach-to-rate-limiting-f8a06cf7c94c https://blog.figma.com/an-alternative-approach-to-rate-limit...

luckystarr 9y ago

For a different view on the topic watch "Stop Rate Limiting! Capacity Management Done Right" https://www.youtube.com/watch?v=m64SWl9bfvk https://www.youtube.com/watch?v=m64SWl9bfvk The basic premise is not do do req/s limiting but rather concurrency limiting which results in req/s limiting by itself. Concurrency limiting is rather simple and doesn't require a lot of code complexity.

daddykotex 9y ago
This video was very interesting, thanks for sharing!
snoman 9y ago
Wow! That was an incredible talk/demonstration. Thanks for that!
zie 9y ago
The problem here is, it depends on WHY you are rate limiting. If it's just to balance so you don't overload your backends, then absolutely this is a great way to do it. If however you are trying to limit client(s) because the service is an authentication gateway for instance, then you want to limit user/pass requests to X number then concurrency limiting isn't a good way to do that. So you may need both, depending on your use-cases, so it's not a one-size fits all solution.
- bogomipz 9y ago
  What is the use case for your second example? I am not following. Wouldn't that just be rate limiting by client IP though?
  - zlynx 9y ago
    I heard about a case where someone built a phone app backend without rate limiting. Someone found this hole and successfully attacked 70,000 accounts by running password dictionary cracks against the authentication API. Modern distributed systems are simply too fast and users are too dumb with picking passwords to allow unlimited password attempts.
  - zie 9y ago
    Well you can rate limit via a lot of things, definitely by IP is a good idea, but for ipv6, you typically want to limit by blocks(since every ipv6 user currently usually gets a full block of IP's), but you also probably want to also limit by username, i.e. if you keep trying to login as user 'root', you only get 3 attempts/minute or something. After X attempts via the same IP, you can block/ban that IP via a FW rule/etc for say 5 mins. or 30m, or whatever. It all depends on your security posture, you could go crazy and actually lock the account after 3 failures, but then you hand bad people a free DDOS... so you have to be careful about doing that.. But you could soft-lock and require a correct password and an email address verification after X failed attempts(i.e. correct login, plus they have to click a link in an email). Anyways, see what I'm saying here? Authentication access is something you really want to get right, and it's a complicated topic.
  - 9y ago
thatusernametho 9y ago
He mentioned that nginx using lua managed the requests but I didn't see the code for that. Is that available anywhere?
pwdisswordfish2 9y ago
On the origin is he only measuring connections? HTTP/1.1 says a single connection can contain more than one request. The client I use has this feature. "Modern" browsers do not. Whether proxies pipeline requests to origin servers (irrespective of the client features) I do not know. But it seems like they could preserve some origin capacity that way. Perhaps they adhere to one request per connection. Ideally, as a user, I think it would be useful to get more diagnostics in response headers on the health of the proxies and origins. Something more informative than HTTP status codes. That way we can build "intelligent clients" that self-adjust to current conditions in response to diagnostics they get in the responses. (The presenter references the adaptive approach of the TCP congestion algorithm.) Some websites return diagnostics in webpage content. But of course one only gets them after a successful (cf. failed) transaction. For example, I believe wikipedia.org or archive.vector.co.uk return some diagnostics on some aspect of their setup (probably not intended to be utilised by clients).

daddykotex 9y ago

Disregarding the article completely, I'll share my opinion on Kong because we use quite a bit at my workplace. We use an old version (0.9.x as of right now). The things I shared below might not be true anymore in new versions but I can't tell and are regarding the plugin system. IMO, the idea of taking things like authentication, rate limiting, etc in a proxy is a wonderful idea (https://2tjosk2rxzc21medji3nfn1g-wpengine.netdna-ssl.com/wp-content/uploads/2017/12/illustration2.png https://2tjosk2rxzc21medji3nfn1g-wpengine.netdna-ssl.com/wp-...). So in theory, the approach Kong takes is wonderful, but I think the implementation is not so much. Kong is layer over nginx and uses lua as a scripting language to add all sorts of stuff. Quickly, you reach the limit of the plugins capability so you think, well, I will write my own plugins. Well, to me it was a very unpleasing experience. I found that the thing was hard to test and hard to maintain. Maybe my criticism is more lua than Kong but since Kong relies heavily on lua, there is not much I can do. There is also magic happening. You declare a schema.lua files to configure the store to hold your data. Then automatically you've got a DAO interface available with a bunch of method on it to work with the store. You don't know what methods are available or what arguments should be passed into these functions. Anyway, this is my take after spending quite a few hours working on home made plugins in lua for Kong. In the end, I'm glad Kong is open source and it's a great piece of software. It helped us reduce our applications complexity but make sure you don't start to shift to much logic into it because the plugin system can be hard to work with.

khaledtaha 9y ago
Have you found any viable alternatives to Kong?
- daddykotex 9y ago
  So far we're still using Kong. Planning an upgrade soon. But we try to avoid shifting to much domain logic in the form of Kong plugins.
  - fosk 9y ago
    If I may ask, what kind of functionality have you been trying to implement in a Kong plugin?

forgotpassagan 9y ago

This may be how Kong does it but it's not really 'high performance'. The right way to do rate limiting is to limit by IP using a counting Bloom Filter or Cuckoo filter along with random samples. When you hit a false positive then you have a second normal rate limiter to 'mop up' IPs that are over the first limiter. This doesn't give you a hard exact limit but gets the job done storing far less state. You also need to bucket by IP sub-ranges in IPV6 to stop people crap flooding you with tons of unique IP's

jdwyah 9y ago

One thing that RateLim.it uses to its advantage is calculating the “nextPossiblePass” for each limit. This allows clients to cache forever that something is over the limit until time X and not have to make another request. In the bursty case this let’s clients effectively short circuit and protect the system. Disclaimer: I work on https://www.ratelim.it/documentation/basic_rate_limits https://www.ratelim.it/documentation/basic_rate_limits

yread 9y ago

Nice article (although the illustrations aren't very... illustrative). Anybody knows how does Kong compare with WSO2 API Manager?

thelicx 9y ago

I have been using Kong since 2016 on various APIs and I have been impressed by the continuous increase of performance after every release. I wish upgrades were easier but I know they are working on it (the "migrations" between each major version), but overall it's a fast and pluggable layer for any API inside or outside the firewall, especially if you are running containers. On this note for those of you who haven't noticed it yet, they have released an Alpine version of their Docker image, but it's still not the default one. I would actually recommend using it to further reduce the size of Kong containers: https://konghq.com/blog/kong-alpine-docker/ https://konghq.com/blog/kong-alpine-docker/

jively 9y ago

> A better approach is to use a “set-then-get” mindset, relying on atomic operators that implement locks in a very performant fashion, allowing you to quickly increment and check counter values without letting the atomic operations get in the way. In a highly distributed system you’d probably want to avoid a centralised data store altogether for fast moving data like rate limits. CRDTs and bucket weighting might be a more effective strategy. The article states that tracking per-node could cause a problem with race conditions but that assumes it’s the counter that’s the problem. If the node cluster is aware of the other nodes and the relative load of the cluster, you can use this value to weight the isolated rate limiter and the only data that needs to be shared can be broadcast between the nodes using a pub/sub mechanism. If some variance is permitted (+/- a margin either side of the limit) then having the nodes synchronise their “token weight” based on the size of the cluster means that the nodes can then manage the rate limit in-memory without ever needing to track in a data store. It does trade-off accuracy, but for accuracy you can then revert to the set-then-get centralised counter, the trade-off being performance because of increased round trip time to the day store. In most rate limit scenarios, at least from what we’ve seen, extreme accuracy isn’t usually that important vs. being able to scale amd rate limit without having to also scale a data layer to handle the counters.

dmaumenee 9y ago

I use Kong EE for a client, I have read Kong EE documentation carefully and made a lot of tests. The current implementation (0.29) have this behavior (that not meet our needs). 1) All incoming requests are take into account, including those which have been rejected (with 429 error). If the consumer exceed his limit during many consecutive time windows, all the requests of the consecutive time windows will be rejected (with 429 error). 2) For a windows size of 1 second, the computed weight of the previous windows is always 100%. If the limit was reach during the previous second, all requests made in the current windows will be rejected (with 429 errors).

dmaumenee 9y ago

The performance degradation of doing strict rate limit relying on Kong Cluster data store (Postgres or Cassandra) is amplified by the lake of database connection pool management. Each incoming http request induce the creation of a new database connection, this process is very expensive especially with Cassandra when authentication is enabled.

SmartWatchPicks 9y ago

Thanks for share . https://www.smartwatchpicks.com/ https://www.smartwatchpicks.com/