What is the best way to implement a rate-limiting algorithm for web requests?

Question

Possible/partial duplicates:

• What’s a good rate limiting algorithm?
• Throttling method calls to M requests in N seconds
• Best way to implement request throttling in ASP.NET MVC?

I am looking for the best way to implement a moving time window rate limiting algorithm for a web application to reduce spam or brute force attacks.

Examples of use would be "Maximum number of failed login attempts from a given IP in the last 5 minutes", "Maximum number of (posts/votes/etc...) in the last N minutes".

I would prefer to use a moving time window algorithm, rather than a hard reset of statistics every X minutes (like twitter api).

This would be for a C#/ASP.Net app.

Vandalism

I don't think any of the supplied dupes really answer this question with an asp.net/c# slant. – Ancestry

@spender: hence that word "possible" ;-) – Yerga

Was really directed at the "close" voter rather than original question content. – Ancestry

@Vandalism can you tell us what approach you eventually used, and how do you like it? – Lyonnaise

Answer 1

Use a fast memory-based hashtable like memcached. The keys will be the target you are limiting (e.g. an IP) and the expiration of each stored value should be the maximum limitation time.

The values stored for each key will contain a serialized list of the last N attempts they made at performing the action, along with the time for each attempt.

Overwhelm

So for each attempt, i would deserialize the cached list, chop off the entries outside the time window, add new entry, count the items, and update the cache? – Vandalism

@Vandalism You could use Redis instead of Memcached. Redis has built in support for lists and get-first and get-last — I think that with Redis you won't need to deserialize the whole list. Google for "redis rate limiting" – Florencio

@Florencio Redis is definitely the correct solution for this. Support for lists and applying it to rate limiting work very well together. – Vandalism

Answer 2

We found out Token Bucket is better algorithm for this kind of rate-limiting. It's widely used in routers/switches so our operation folks are more familiar with the concept.

Kaplan

It sounds like you are suggesting implementation at the network switch layer. That can be a very good security implementation, but in the growing popularity of server-less environments, network layer protections are harder to implement when the underlying hardware infrastructure is hosted by a cloud provider. – Splenectomy

Answer 3

Just to add a more 'modern' answer to this problem: For .NET WebAPI, WebApiThrottle is excellent and probably does everything you want out of the box.

It's also available on NuGet.

Implementation takes only a minute or so and it's highly customisable:

config.MessageHandlers.Add(new ThrottlingHandler()
{
    Policy = new ThrottlePolicy(perSecond: 1, perMinute: 30, perHour: 500, perDay:2000)
    {
        IpThrottling = true,
        ClientThrottling = true,
        EndpointThrottling = true
    },
    Repository = new CacheRepository()
});

Watchband

is this project still alive? – Ierna

Answer 4

You find this page to be an interesting read:

http://www.codeproject.com/KB/aspnet/10ASPNetPerformance.aspx

The section to look out for starts as follows:

Prevent Denial of Service (DOS) Attack

Web services are the most attractive target for hackers because even a pre-school hacker can bring down a server by repeatedly calling a Web service which does expensive work.

EDIT: Similar question here:

Best way to implement request throttling in ASP.NET MVC?

Ancestry

Answer 5

I just added the answer to the question Block API requests for 5 mins if API rate limit exceeds.
I used HttpRuntime.Cache to allow only 60 requests per minute. Exceeding the limit will block the API for next 5 minutes.

Mucosa

Answer 6

I have been working on a new redis-based rate-limiting approach: http://blog.jnbrymn.com/2021/03/18/estimated-average-recent-request-rate-limiter.html

It is simpler than many other approaches that I've seen in that it doesn't require you to constantly create new redis keys (e.g. instead of one per user per minute window, it's just one per user). It has some nice properties regarding "forgetfulness and forgiveness" so that, for example, abusive users can't reoffend in the next minute window. It also has a nice interpretation as the state of the rate-limiter corresponds to an estimate of the user's recent request rate.

Ewe

Enjoyed reading your blog posts. Nice work. – Idiom

Thanks! We're considering implementing it at GitHub. – Ewe

Cool. Please link the repo if/when you do. – Idiom