In the rapidly evolving realm of the internet, imagine a bustling playground where web applications serve millions of users, each with their own demands. 🌐🌍 But what if a few users, or even automated bots trying to exploit., start hogging all the swings and slides, leaving others frustrated? 😱 That's where our hero, rate limiting, swoops in to save the day! 🦸♂️
🛡️ The Shield of Fairness: Introducing Rate Limiting
Picture this: a popular ice cream truck in your neighborhood. 🍦 It's awesome, right? Now, imagine if one super-hungry kid stood in line and bought all the ice cream before anyone else got a chance. Not fair, huh? That's where rate limiting comes in. It's like a magic fence that ensures everyone gets a fair share of the ice cream. 🍨
There are many ways to implement rate limiting, but we'll focus on one of the most popular algorithms: the token bucket algorithm. 🪣 Later on, we will use other algorithms like the leaky bucket algorithm and the sliding window algorithm with redis.
🪣 The Token Bucket Algorithm: Our Digital Playground Organizer
Okay, so how does this magic fence work? Enter the token bucket algorithm – a smart trick that keeps things balanced. Imagine each user has a bucket of tokens. 🪣 These tokens are like coupons that they need to give to the ice cream truck to get their treat. When a user wants ice cream, they give a token, and their bucket slowly refills over time. ⏳
🔁 Refills and Fair Play: How Token Buckets Keep the Fun Going
Let's break it down even more. Imagine you have a bucket of cookies. 🍪 Every 10 seconds, someone sneaks in and adds a few more cookies to your bucket. But when you want a cookie, you have to give one back. If your bucket is empty, you have to wait for it to refill before grabbing more cookies. This way, everyone gets a turn, and no one hogs all the cookies! 🙌
🎮 Game On: Implementing Token Buckets with Redis
So, how do we make this digital magic happen? Enter Redis, our secret tool. It's like a super-fast memory bank. 🏦 We use it to store info about the token buckets. With code, we build the rules: how fast the bucket refills, how many tokens it can hold, and what happens when someone tries to grab a cookie without any tokens left.
💻 🚰 The Token Bucket Algorithm in Action
- Bucket Initialization: Initially, the bucket is full with 10 tokens. 🪣
┌───────────────┐
│ Tokens: 10 │
│ │
│ Refill in │
│ 20 seconds │
└───────────────┘- User Requests: As the user makes requests, they spend tokens from the bucket. Here's how it unfolds:
┌───────────────┐
│ Tokens: 9 │
│ │
│ Refill in │
│ 20 seconds │
└───────────────┘
┌───────────────┐
│ Tokens: 8 │
│ │
│ Refill in │
│ 20 seconds │
└───────────────┘
┌───────────────┐
│ Tokens: 7 │
│ │
│ Refill in │
│ 20 seconds │
└───────────────┘- Refill Time: After 20 seconds have passed, the bucket is refilled with 10 tokens. 🔄
┌───────────────┐
│ Tokens: 10 │
│ │
│ Refill in │
│ 20 seconds │
└───────────────┘- Continued Requests: The user continues making requests:
┌───────────────┐
│ Tokens: 9 │
│ │
│ Refill in │
│ 20 seconds │
└───────────────┘
┌───────────────┐
│ Tokens: 8 │
│ │
│ Refill in │
│ 20 seconds │
└───────────────┘- Bucket Empty: When the bucket is empty, the user has to wait for it to refill before making more requests. ⏳
┌───────────────┐
│ Tokens: 0 │
│ │
│ Refill in │
│ 20 seconds │
└───────────────┘Implementing Token Bucket Algorithm with Redis
Now, let's bring our token bucket algorithm to life using TypeScript and Redis. Here's how the code components come together:
Token Bucket Algorithm Functions (token-bucket.ts):
import Redis from "ioredis";
// 🪣 Data structure for token bucket
interface TokenBucketData {
tokens: number; // 🧺 Number of tokens in the bucket
ts: number; // ⏰ Timestamp of last update
}
// 🎛️ Options for token bucket configuration
export interface TokenBucketOptions {
capacity: number; // 📦 Maximum tokens the bucket can hold
refillAmount: number; // 💧 Number of tokens added on each refill
refillTime: number; // ⏳ Time interval between refills (in seconds)
}
// ⚡ Refills the token bucket with new tokens
async function refillBucket(
client: Redis, // 📡 Redis client instance
key: string, // 🧷 Key to identify the token bucket
capacity: number, // 📦 Maximum capacity of the bucket
refillAmount: number, // 💧 Number of tokens added on each refill
refillTime: number // ⏳ Time interval between refills (in seconds)
): Promise<TokenBucketData | null> {
const reply = await client.hgetall(key);
if (!reply) {
return null; // ❌ Token bucket not found
}
const { tokens, ts } = reply;
const currentTime = Date.now();
const elapsedTime = Math.floor(
(currentTime - parseInt(ts)) / (refillTime * 1000)
);
const newTokens = elapsedTime * refillAmount;
const updatedTokens = Math.min(capacity, parseInt(tokens) + newTokens);
await client.hmset(key, "tokens", updatedTokens, "ts", currentTime);
return { tokens: updatedTokens, ts: currentTime };
}
// 📦 Creates a new token bucket or returns an existing one
async function createBucket(
client: Redis, // 📡 Redis client instance
key: string, // 🧷 Key to identify the token bucket
capacity: number // 📦 Maximum capacity of the bucket
): Promise<TokenBucketData> {
const bucket = client.hgetall(key);
if (!bucket) {
const currentTime = Date.now();
await client.hmset(key, "tokens", capacity, "ts", currentTime);
return { tokens: capacity, ts: currentTime };
} else {
return bucket as unknown as TokenBucketData;
}
}
// 🚀 Handles incoming requests using token bucket strategy
async function handleRequest(
client: Redis, // 📡 Redis client instance
key: string, // 🧷 Key to identify the token bucket
capacity: number, // 📦 Maximum capacity of the bucket
refillAmount: number, // 💧 Number of tokens added on each refill
refillTime: number // ⏳ Time interval between refills (in seconds)
): Promise<boolean> {
const bucket = await createBucket(client, key, capacity);
const currentTime = Date.now();
const elapsedTime = Math.floor((currentTime - bucket.ts) / 1000);
if (elapsedTime >= refillTime) {
const refilledBucket = await refillBucket(
client,
key,
capacity,
refillAmount,
refillTime
);
if (!refilledBucket) {
console.log(`Request[REJECTED] for ${key} -- BUCKET NOT FOUND\n`);
return false;
}
bucket.tokens = refilledBucket.tokens;
} else {
if (bucket.tokens <= 0) {
console.log(
`Request[REJECTED] for ${key} (tokens - ${
bucket.tokens
}) -- ${new Date().toLocaleTimeString()}\n`
);
return false;
}
}
console.log(
`Request[ACCEPTED] for ${key} (tokens - ${
bucket.tokens
}) -- ${new Date().toLocaleTimeString()}\n`
);
await client.hset(key, "tokens", bucket.tokens - 1);
return true;
}
// 🚀 Creates a token bucket manager with specified options
export function createTokenBucket(options: TokenBucketOptions) {
const client = new Redis(); // Initialize the ioredis client here
return {
refillBucket: (key: string) =>
refillBucket(
client,
key,
options.capacity,
options.refillAmount,
options.refillTime
),
createBucket: (key: string) => createBucket(client, key, options.capacity),
handleRequest: (key: string) =>
handleRequest(
client,
key,
options.capacity,
options.refillAmount,
options.refillTime
),
};
}
Express Middleware (middleware.ts):
import express from "express";
import {
createTokenBucket,
TokenBucketOptions,
} from "../token-bucket-limiter/token-bucket"; // Update the import path to match your actual tokenBucket module
const tokenBucketOptions: TokenBucketOptions = {
capacity: 10,
refillAmount: 10,
refillTime: 20, //seconds
};
const tokenBucket = createTokenBucket(tokenBucketOptions);
export function tokenBucketMiddleware() {
return async (
req: express.Request,
res: express.Response,
next: express.NextFunction
) => {
const key = "user:" + req.ip; // Use the client's IP address as the key
const accepted = await tokenBucket.handleRequest(key);
if (accepted) {
next();
} else {
res.status(429).send("Too Many Requests");
}
};
}
Express Server (index.ts):
import express, { Response, Request } from "express";
import { tokenBucketMiddleware } from "./middleware/rate-limiter";
const app = express();
app.get(
"/token-route",
tokenBucketMiddleware(),
(req: Request, res: Response) => {
return res.send("Request Accepted");
}
);
const PORT = 3000;
app.listen(PORT, () => {
console.log(`Server is running on port ${PORT}`);
});
Code repository
The complete code for this example is available on GitHub.
Conclusion
And there you have it – rate limiting and token buckets save the day! Just like a kind teacher ensuring everyone gets a turn on the swings, these tech tricks make sure no one hogs all the fun. So next time you use a cool app or website, remember the unsung heroes working behind the scenes to keep things fair for everyone! 🌐🎉
Next Steps
- How to implement rate limiting with sliding windows
- How to implement rate limiting with leaky buckets
- How to implement rate limiting with fixed window counters