Rate Limiting helps to protect services against abusive behaviors targeting the application layer like Denial-of-service (DOS) attacks, brute-force password attempts etc. These attacks are usually look like they are coming from real users, but are typically generated by machines (or bots). As a result, these attacks are often harder to detect and can more easily bring down a service, application, or an API.
Our Rate Limiter should meet the following requirements:
- Limit the number of requests an entity can send to any application/API within a time window, e.g., 15 requests per second.
- Ratelimit should be designed to work with applications running in clusture mode.
- User should be notifed with an error message whenever the defined threshold is crossed.
- Ratelimit should be able to adapt to the changed traffic conditions. We should be able to throttle the rate limit on the fly without affecting services.
- The system should be highly available and scalable.
- Our rate limiter should not introduce substantial latencies affecting the user experience.
Basic idea behind rate limit API calls if to restrict sudden bust of request originating from a particular source (ip) or user. There are other factors that can be applied to uniquely identify the request but those all can be done for registered / authenticated / logged-in users. Once user is logged-in we can extract uuid and other parameters to keep track of the requests. Real challenge is to control the unauthenticated requests. For example, failed login-attempts, forgot passwords etc.
To implement ratelimiter API there are different methods which are as follows:-
In this approach we simply store the count of request and the start-time of the request. If number of requests exceeds the limit within the speficied time window, we will reject all the subsequent requests till the timeout occurs. This method has a shortcomming, if somebody simply sends bunch of request just before window expires, he can again send the traffic as soon as new window starts. So in inspite of ratelimit attacker will be allowed to pump 2x of the traffic it is allowed to send.
In this approach we can keep track of each request per user/source. We can store the timestamp of each request in a hashTable/Redis/memcached/dynamodb other NOSQL based database.In this way we can restrict user to make only allowed number of request with-in particular time window. There is one big drawback, we might have keep appending the timestamp if the allowed number of request within given timeframe is high. This causes big memory/storage consumption also less scalable.
In this approach we reduce the need of extra memory required to keep track of additional timestamp by keeping only 2 timestamps(t1 & t2) and 2 counters(c1 & c2).
Lets say for example some application allows user to make 100 requests per hour..
[1] Request at 05:00:00 AM set [t1=1629977000, c1=1, t2=0, c2=0] => Request Allowed
[2] Request at 05:00:10 AM set [t1=1629977000, c1=1,t2=1629977010, c2=1] =>Request Allowed
[3] Request at 05:01:00 AM set [t1=1629977000, c1=1,t2=1629977010, c2=2] =>Request Allowed
[Note here we have only incremented the c2 we have not modified the timestamp c2]
[4] Suddenly lot of request arrives and we keep on incrementing counter c2 till it touches the limit.
[t1=1629977000, c1=1,t2=1629977010, c2=99] =>Request Allowed
[5] 101th request at 05:45:00 AM set [t1=1629977000, c1=1,t2=1629977010, c2=99] =>Request Rejected with 429
[6] Once limit is reached, all the request placed within that time window will be rejected.
[7] After timeout (1 hour), new request will be allowed and counter will be swapped. Now c1 will hold the counter of c2 and t1 will hold the timestamp of t2.
[8] Request at 06:00:00 AM set [t1=1629977010, c1=99,t2=1629980600, c2=1] =>Request Allowed
As we can see from above soon the next request will be rejected ( because it crosses the max allowed limit). But it will soon be rolled over in next 10 second as window will slide further.
There are some limitations of this approach as it expects the consistent traffic.
With Above approach, we have seen one draw back where request burst happens just before the sliding window expiry and the timer t2 is set just after the second request recevied. This will give advantage to attackers and doesn't seems to be an efficient way.
Idea is to add one more counter and divide entier timeout window into three segments (start,mid,end). Keeping an addtional counter and timestamp variable ( cs, ts, cm, tm, ce, te). While incrementing the counter we simply calculate where does currentTime stamp fits into the time segment mentioned above.
Each segment will have their own counters which will keep the count of request falls within particular time range (ts-cs,tm-cm,te-ce).
For example if duration/timeLimit=30 seconds then
Ts = currentTimeStamp+0.
Tm = Ts+duration/2.
Te = Ts+duration.- On arrival of first request(Start Segment) timer ts will be set with current timestamp and counter cs=1.
- If Second request comes currentTime < Tm (Mid segement) , timer tm will be set to current time and cm=1.
- Any request that falls within the currentTime<Tm will be added to the counter cm.
- If at any givin point of time cs+cm+ce > maxAllowed, new request will be rejected.
- If request comes within the currentTime >= Tm (End segment) timer te and counter ce will be set.
- All subsequent request that falls into currentTime >=Tm and currentTime <=Te will simply increment the counter Ce
- If currtime > Te, we will simply move the window to the next time segment and swapping values of ts < tm < te, cs < cm < ce
In this way we can move our request limit with sliding window approach, we don't have to store each request's timestamp. Also incrementing counter segmentwise will help in controlling the rate of rquests.
if(cs == 0){
cs=1;
ts=currentTime;
}else{
if( cs - current_timestamp > maxTimeLimit/2){
ce++;
if( te === 0)
te = current_timestamp;
}else{
cm++;
if( tm == 0){ // Set only if not already assigned.
tm = current_timestamp;
}
}
}
In this approach [te] will always modify the timestamp with the last request placed.
After timeout, value of tm,cm will be pushed to ts, cs, and value of te, ce will be pushed to tm, tm.
This will help us in identifying the rate of traffic post mid-intervel and pre mid-intervel.
In this way we can keep the rate of api requests a bit more consistent and control the spike in a better way. Lets say for example some application allows user to make 100 requests per Hour..data set will look like this
[1] Request at 05:00:00 AM set [ts=1629977000, cs=1, tm=0, cm=0, te=0, ce=0] => Request Allowed
[2] Request at 05:00:10 AM set [ts=1629977000, cs=1, tm=1629977010, cm=1,te=0, ce=0] =>Request Allowed
[3] Request at 05:01:00 AM set [ts=1629977000, cs=1, tm=1629977010, cm=2, te=0, ce=0] =>Request Allowed
Note here we have only incremented the cm we have not modified the timestamp tm
[4] Suddenly lot of request(48) arrives between 05:01:00 and 05:30:00 and we keep on incrementing counter cm.
[ts=1629977000, cs=1, tm=1629977010, cm=50, te=0, ce=0]=>Request Allowed
[5] Request at 05:31:00 AM set [ts=1629977000, cs=1, tm=1629977010, cm=50, te=1629978800, ce=1] =>Request Allowed
Becasue current time > Tm, timer te and counter ce will be set.
[5] 101th request at 05:45:00 AM set [ts=1629977000, cs=1, tm=1629977010, cm=50, te=1629978800, ce=48] =>Request Rejected with 429
[6] Once limit is reached, all the request placed within that time window will be rejected.
[7] After timeout (1 hour), new request will be allowed and counter will be swapped. Now cs will store the counter of cm and ts will store the timestamp of tm
similarly cm will store the counter of ce and tm will store the counter of te. te will be set to currenttime stamp and ce=1
[8] Request at 06:00:00 AM set [ts=1629977010, cs=50, tm=1629978800, cm=48, te=0, ce=0] =>Request Allowed
As we can see from above soon the next request will be rejected ( because it crosses the max allowed limit). But it will soon be rolled over in next 10 second as window will slide further.
System Design Diagram
-
Custom Key Generator .RateLimiter solution provides flexibility to generate unique key from http request. User can provide their custom keygenerators during api init with configuration.
-
Custom DB Connectors. We have provided the interface which can be use to implement any databse connecter and can easily be plugged into ratelimiter.
export interface dbInterface {
+getData: (key: string) => Promise;
+setData: (key: string, data: string, callback: function) => void;
+removeData: (key: string) => void;
+updateData: (key: string, data: string, callback: function) => void;
}
class InMemoryStore implements dbInterface {
hashMap: any;
constructor() {
this.hashMap = new Map();
//return this;
}
getData = (key: string) => {
return new Promise((resolve, reject) => {
var data = this.hashMap.get(key);
if (data) return resolve(data);
else return reject("Data Not Found");
});
};
setData = (key: string, data: any, timeout:number,setDataCallback) => {
this.hashMap.set(key, JSON.stringify(data));
};
removeData = (key: string, deleteCallback) => {
this.hashMap.delete(key);
};
updateData = (key: string, data: any, timeout:number, setDataCallback) => {
/* In case of Redis, we will refresh the expiry of key */
this.hashMap.set(key, JSON.stringify(data));
};
};- Object of dbConnector can be injected to RateLimiter along with other config as describe in following sections.
- RateLimiter solution also provided flexibility to throttle the rate of request on the fly .
- On adding redis dbconnector we can utilize key expiry timer feature of Redis key.
- Multiple instance of apilimiter can be created, each object will maintain its own connection with DB.
- On using different DB connectors, we can manage the sharding and multi clustured db by implementing better partition key.
git clone https://github.com/ankitonweb/RateLimiter
cd RateLimiter
npm install
[To build]
npm run build
[To run unit tests]
npm run test
[To run examples]
npm run start
const RateLimiter = require('RateLimiter');
const ratelimiter = new RateLimiter(<configuration>); // Configuration objet as shown below
In current implementation, we have provided inmemory dbconnector and redis dbconnector. For Inmemroy you don't have to provide anything, for redis you will have to pass the redis endpoint uri in the config as shown below.
const opts = {
maxRequest: 1000, // Maximum number of requests allowed within in [duration] time limit.
endpoint: "", // endpoint url eg. redis:// , dynamo etc. Empty for Inmemory
duration: 3600, // Time window size in seconds, maxRequests allowed in this time window.
endpointType: "inmemory", // endpointType inmemory/redis/dynamo etc.
onConnectError: {}, // Optional for inmemory, good to have for redis and other db connectors
onConnect: {}, // Same as above.
keyGenerator: function (req) { // keyGenerator passed to RateLimiter, it counts the nunber of requests based on the key
// return req.query.userid; // We can customize the unique key comes with http request. For now we will just continue using ip.
return req.ip;
},
headers: true, // If true it appends the Rate limit information in header
dbConnector: new InMemoryStore(), // Injecting userdefined dbConnector
};Create an object of RateLimiter and apply to the middleware of application.
const express = require("express");
const RateLimiter=require('RateLimiter');
const app = express();
const opts = {
maxRequest: 1000,
endpoint: "",
duration: 3600,
endpointType: "inmemory",
onConnectError: {},
onConnect: {},
keyGenerator: function (req) {
return req.ip;
},
headers: true,
dbConnector: new InMemoryStore(),
};
function Server(opts = {}, port = {}) {
var apiLimiter = new RateLimiter(opts);
app.use("/somepath/", apiLimiter.rateLimit);
app.get("/somepath/", (req, res) => {
res.send("Hello World!");
});
port = port || 8000;
return new Promise((resolve, reject) => {
app.listen(port, () => {
return resolve(
`Application Server(with RateLimiter) Listening at http://localhost:${port}\n with following options\n ${JSON.stringify(opts)}`
);
});
});
}
module.exports = (opts, port = {}) => {
return Server(opts, port)
.then((res) => {
console.log(res);
return res;
})
.catch((err) => {
console.log("Error in starting application server");
throw new Error("Can't start Application server " + err);
});
};To throttle the rateLimit call
opts.maxRequest = 100;
apiLimiter.throttleRateLimit(opts);I have added some sample test scenarios in SimpleApplication and MixedScenarios. They covers following scenarios
- Using different keyGenerators(IP and UserID)
- Using InMemory DB.
- Implementing throttling on the fly.
- Applying multiple RateLimit in single application.
To execute example
node ./dist-example/SlidingWindowWithBS.js
node ./dist-example/MixedScenarios.jsCurrently very limited set of unit test cases is implmented
- This test checks the db interface.
- We have implemented 'inmemory' and 'redis' connector.
- Add/modify db entries.
- Connectivity with db.
- This test checks the basic ratelimiter functionality.
- It test different key generators ( IP & userID).
- Sets some limit on the maxRequest and then pumps traffic and expect it to fail.
There are other functional areas which we could have added as unit test cases like
- Verifying that requests are allowed after timeout.
- Edge case scenarios, request comes just when window is about to expire.
- Applying multiple ratelimit ( with different path values) and verifying that they don't cross over each other.
- Test cases with different userIDs, currently we have just used single userID for test.
- Handling exceptions, this is something not verified very well in current release. Proper test case would surely help.
- Performance testing in heavy traffic conditions.