sean cassidy : Rate Limiting per User

When writing the HTTP API for DiNet, I had a problem that many services must deal with: one user maliciously generating traffic and denying service to legitimate users. In fact, the problem is much more severe in a flood network like DiNet (the diluvian part of the name is not a misnomer), as one user can generate a lot of traffic on routers.

Further, I didn't want to use a leaky bucket style algorithm because that would penalize all users for one user's malicious behavior. So, I decided upon this algorithm: N map counters.

  1. Each time interval, a new map is created, and the oldest map is destroyed.
  2. All requests go to the newest map. They look up the user ID (or IP address) in the map, and increment the counter.
  3. Each request that comes in performs a look up on each of the N maps, and gets the counter from each key
  4. This counter is scaled by the age of the map, so that the oldest is scaled by 1/N, the second oldest 2/N, and the latest is scaled by 1.
  5. The scaled results are added together and compared with a static limit.

This can also be done for the total number of requests to have a global limit in case of a DDoS rather than a single user/IP address attack. The scaling algorithm, currently linear, might work better as an exponential or polynomial distribution.

The time interval can be any amount of time. I think that it would depend on your service what you would choose. Half a minute to a minute sounds about right to me. The total number of buckets is another interesting tuning parameter. Somewhere in the neighborhood of 2-5 sounds like a good guess. Testing and application idiosyncrasies will determine the ideal value.

I've coded this up and it seems to be working well for the DiNet HTTP API. It uses the fantastic uthash library for its maps.