These Algo. typically used as Rate limiting Algorithm.
It is used to control amount of data or number of requests that can be proccessed in a given time period.
WORKING :
- Token are added to the Bucket at a fixed rate.
- The Bucket has a Max. Capacity, it can't hold more tokens than that.
- When a Request came, the Bucket is checked for number of token available
- If req. tokens are available then remove that tokens from the bucket and process the request.
- If no token are available, the request is rejected or pushed to a retry queue.
IMPLEMENTATION :
Token Bucket can be implemented in respect to user or application.
Means either we can use it rate limit the user, that a certain user can only make 10req/sec.
or we can use it to rate limit the application, that a certain application can only make 10req/sec.
class TokenBucket{
private refillRate:number; // no of token added to the bucket per second
private capacity:number;
private Bucket: number;
private lastRefillTime: number;
constructor(refillRate:number,capacity:number){
this.refillRate = refillRate;
this.capacity = capacity;
this.Bucket = capacity;
this.lastRefillTime = Date.now();
}
public refill(){
const time = Date.now();
const diff = time - this.lastRefillTime;
const tokensToAdd = Math.floor(diff* this.refillRate);
this.Bucket = min(this.capacity, this.Bucket+tokensToAdd);
this.lastRefillTime = time;
}
public allowRequest(){
// Update the Bucket with tokens
refill();
if(this.Bucket >= 1){
this.Bucket = this.Bucket - 1;
return true;
}
return false;
}
}
Example : LIMITING REQUESTS PER SECOND FOR USER IN NESTJS
FLOW
Client ──> NestJS API (Producer)
└── always send to RabbitMQ ➤ (free or premium queue)
Worker (Consumer)
└── Pull from queue(s)
└── Check Redis token bucket
├── ✅ Allowed → process job
└── ⛔ Not allowed → requeue with delay
Top comments (0)