Suppose you have a ressource on the web (for example an API) that either generates a lot of load, or that is prone to be abused by excessive use, you want to rate-limit it. That is, only a certain number of requests is allowed per time-period.
A possible way to do this is to use Memcache to record the number of requests received per a certain time period.
Task: Only allow 1000 requests per 5 minutes
First attempt:
The naive approach would be to have a key rate-limit-1.2.3.4 (where 1.2.3.4 would be the client’s IP address) with a expiration time of 5 minutes (aka 300 seconds) and increment it with every request. But consider this:
10:00: 250 reqs -> value 250
10:02: 500 reqs -> value 750
10:04: 250 reqs -> value 1000
10:06: 100 reqs -> value 1250 -> fails! (though there were only 850 requests in the last 5 minutes)
Whats the problem?
Memcache renews the expiration time with every set.
Second attempt:
Have a new key every 5 minutes: rate-limit-1.2.3.4-${minutes modulo 5}. This circumvents the problem that the key expiration but creates another one:
10:00: 250 reqs -> value 250
10:02: 500 reqs -> value 750
10:04: 250 reqs -> value 1000
10:06: 300 reqs -> value 300 -> doesn’t fail! (though there were 1050 requests in the last 5 minutes)
Solution:
Store the value for each minute separately: rate-limit-1.2.3.4-$hour$minute. When checking, query all the keys in the last 5 minutes to calculate the requests in the last 5 minutes.
Sample code:
foreach ($this->getKeys($minutes) as $key) {
$requests += $this->memcache->get($key);
}
$this->memcache->increment($key, 1);
if ($requests > $allowedRequests) throw new RateExceededException;
For your convenience I have open sourced my code at github: php-ratelimiter.
