Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An Alternative Approach to Rate Limiting

medium.com

Post reply on HN
Print view View original

41–50 of 73 posts

Re: An Alternative Approach to Rate Limiting

#41

Post by wpeterson »

jdwyah wrote: post #3
jnwatson wrote: post #2

Sounds like a lot of work to avoid writing 20 lines of Lua.

agreed. I was a bit leery of diving into Lua as I was building http://ratelim.it but it really expands Redis's capabilities dramatically and was easy enough to add. My apps all write the lua into redis and store the hash when they boot up. Duplicative, but means everybody is on the same page and it's easy to store the lua in the main codebase.

Hey buddy!

Reading all the design and discussion I was. Rey curious how you structured things at a brass tacks storage level.

Re: An Alternative Approach to Rate Limiting

#42

Post by [deleted] »

jdwyah wrote: post #3
jnwatson wrote: post #2

Sounds like a lot of work to avoid writing 20 lines of Lua.

agreed. I was a bit leery of diving into Lua as I was building http://ratelim.it but it really expands Redis's capabilities dramatically and was easy enough to add. My apps all write the lua into redis and store the hash when they boot up. Duplicative, but means everybody is on the same page and it's easy to store the lua in the main codebase.

[deleted]

Re: An Alternative Approach to Rate Limiting

#43

Post by hyperpape »

joneholland wrote: post #39
drchickensalad wrote: post #38

Earlier quoted context omitted.

You have to send all the traffic from one client to one server then right? Seems not without heavy drawbacks. Otherwise you can easily get them to hit their limit super early with bad luck.

No, you evenly round robin all traffic to all servers. Each server contains a map of tokens per per client filling at a fixed interval. That interval is calculated by taking the total global token refresh rate and dividing it by the number of servers. The end result is exactly the same but, now you are stateless and have eliminated the bottleneck of a central token bucket.

Wait, each client does its own round robin (if you have three servers, I will hit 1 then 2 then 3)? Is that common?

Re: An Alternative Approach to Rate Limiting

#44

Post by joneholland »

hyperpape wrote: post #43
joneholland wrote: post #39

Earlier quoted context omitted.

No, you evenly round robin all traffic to all servers. Each server contains a map of tokens per per client filling at a fixed interval. That interval is calculated by taking the total global token refresh rate and dividing it by the number of servers. The end result is exactly the same but, now you are stateless and have eliminated the bottleneck of a central token bucket.

Wait, each client does its own round robin (if you have three servers, I will hit 1 then 2 then 3)? Is that common?

The client doesn't do it. You put your front ends behind a load balancer like an ELB, or use a reverse proxy like Nginx.

Edit: And yes, round robin is the most commonly used load distribution technique, and works very well assuming each request has a roughly equivalent unit of work cost.

Re: An Alternative Approach to Rate Limiting

#45

Post by perfmode »

chickenfries wrote: post #19
perfmode wrote: post #11

Earlier quoted context omitted.

I'd be curious to see the Lua code that implements this. Anyone care to indulge me?

I'm guessing it would look something like this... I omitted checking if the token is in the 1 minute window. It returns false if the user has reached the rate limit, true if the user has more tokens left. If the user has tokens left, it decrements the token the user has left before returning true. local id = "user_1" -- Get the number of tokens the user has left local tokens = redis.call("HGET", id, "tokens") if toke…

thats really not bad at all.

Re: An Alternative Approach to Rate Limiting

#46

Post by mason55 »

joneholland wrote: post #36

You know you can implement a token bucket that doesn't share state between your API servers, in about 10 lines of code, using just a in memory map. Your incoming requests should be balanced across all of the servers so you just derive the allowed throughput and divide by the number front ends....

This only works if your bucket size is much larger than your number of servers.

In the degenerate case, imagine a rate limit of 2 total requests per minute load balanced across 2 servers with enough traffic that my request is basically hitting a random server. In this case, 50% of the time my second request will be rate limited incorrectly because each server has a bucket of 1 and my second request went to the same server as my first.

I'm sure someone smarter than me (and better at probability) could come up with an equation where you input your rate limit & number of servers and it tells you the probability of a false positive for a user.

Re: An Alternative Approach to Rate Limiting

#47

Post by timothycrosley »

markwaldron wrote: post #30
timothycrosley wrote: post #4

I would think if you have a consumer application that can't handle double what is set as the rate limit during a very small corner case (start and end of the the minute barrier) you have bigger problems. As you're still effectively enforcing your rate limit over time with that approach. This just sounds like micro-optimization at its worst.

Had we not discovered the attack, we could have faced a huge surge in our delivery costs and a decline in our email sender reputation. This isn't just about the application being able to handle double the amount of load, it about keeping costs down and preventing someone from drastically increasing your bill. I work at a fintech company, and many of the 3rd party providers we use have a non-negligible cost per API ca…

but again, this is not something that allowing double calls within a minute on minute boundaries actually makes any difference on. Someone would have to be abusing it more then just a little bit for you to know to take action in either setup by the same degree. IE you can't investigate every single time one customer goes over limits by mistake if you have any sizable number of customers.

Re: An Alternative Approach to Rate Limiting

#48

Post by lenzm »

irgeek wrote: post #26

In response, we implemented a shadow ban: On the surface, the attackers continued to receive a 200 HTTP response code, but behind the scenes we simply stopped sending document invitations after they exceeded the rate limit. And right there they broke the service for legitimate users. Totally unacceptable collateral damage IMHO.

Shadow ban for everyone that exceeded the rate limit or just the one attacker? As others have said that's shitty for legitimate users that go over the rate limit.

Re: An Alternative Approach to Rate Limiting

#49

Post by joneholland »

mason55 wrote: post #46
joneholland wrote: post #36

You know you can implement a token bucket that doesn't share state between your API servers, in about 10 lines of code, using just a in memory map. Your incoming requests should be balanced across all of the servers so you just derive the allowed throughput and divide by the number front ends....

This only works if your bucket size is much larger than your number of servers. In the degenerate case, imagine a rate limit of 2 total requests per minute load balanced across 2 servers with enough traffic that my request is basically hitting a random server. In this case, 50% of the time my second request will be rate limited incorrectly because each server has a bucket of 1 and my second request went to the same s…

That's valid, if the distribution of work is not fair, this won't work.

In practice, when you are receiving enough traffic to make throttling practical you aren't usually throttling at 2 RPM across 2 servers.

Re: An Alternative Approach to Rate Limiting

#50

Post by pacaro »

It's good practice to rate limit endpoints for a variety of reasons, but in particular any endpoint that exposes user authentication should be rate limited.

So this should be a tool that every service at scale has access to.

IIRC the lack of rate limiting burned Apple relatively recently.

Is this yet another area where we all reinvent the wheel? I've yet to see a recommendation for an off the shelf solution

Post reply on HN