Rate limiting — token bucket, leaky bucket আর sliding window

১ · Rate limiting কেন — ন্যায্যতা, ক্ষমতা রক্ষা, খরচ আর অপব্যবহার থেকে সুরক্ষা

ঈদের আগে রেলস্টেশনের টিকিট কাউন্টারে একটি নিয়ম প্রায়ই চোখে পড়ে: “একজন সর্বোচ্চ চারটি টিকিট”। কাউন্টার খালি থাকলেও নিয়মটি বদলায় না। এর উদ্দেশ্য ভিড় সামলানো নয়। উদ্দেশ্য হলো, কেউ একা পুরো ট্রেনের টিকিট কিনে ফেলতে না পারেন, আর লাইনের শেষ মানুষটিও কিছু পান।

সফটওয়্যারে এই নিয়মের নাম rate limiting: একজন ক্লায়েন্ট নির্দিষ্ট সময়ে কতগুলো অনুরোধ করতে পারবেন, তার সীমা। সীমা পেরোলে সার্ভার কাজটি না করে দ্রুত জানিয়ে দেয় — সাধারণত HTTP 429 Too Many Requests দিয়ে, সাথে কতক্ষণ পরে আবার চেষ্টা করা যাবে।

চারটি কারণ

কাছাকাছি চারটি ধারণা — গুলিয়ে ফেলবেন না

নিচের ছবিটি এই পর্বের মানচিত্র; পুরো পর্ব জুড়ে এর প্রতিটি অংশে ফিরব।

২ · কার হিসাব রাখবেন — user, API key, IP, tenant আর endpoint

Algorithm বাছাইয়ের আগে একটি প্রশ্ন: কার নামে গুনবেন? এই পরিচয়কে বলে rate-limit key. ভুল key বাছলে সবচেয়ে নিখুঁত algorithm-ও ভুল মানুষকে আটকায়।

বাস্তবে key প্রায়ই কয়েকটি মিলিয়ে, আর একাধিক নিয়ম একসাথে চলে। একটি কাল্পনিক অনলাইন দোকানের নিয়ম হতে পারে:

• IP: মিনিটে ৬০০ — শুধু বড় অস্বাভাবিক ঢল ঠেকাতে, auth-এর আগেই;
• user: মিনিটে ১২০, সব endpoint মিলিয়ে;
• user + POST /login: ১৫ মিনিটে ১০টি ভুল চেষ্টা;
• phone + POST /otp: ১০ মিনিটে ৩টি SMS — খরচ আর অপব্যবহার, দুটোই;
• tenant: চুক্তি অনুযায়ী সেকেন্ডে ৫০০, তার ভেতরে প্রতি user আলাদা।

যেকোনো একটি ভাঙলেই 429, আর উত্তরে জানানো ভালো কোনটি (অংশ ৭)।

ভাগ করা IP-র ফাঁদ — NAT আর CGNAT

বাসার Wi-Fi-তে পাঁচটি ফোন বাইরের জগতে একটিই public IP দেখায় — router-এর NAT. মোবাইল নেটওয়ার্কে এটি আরও বড় আকারে ঘটে: অপারেটরের CGNAT হাজারো গ্রাহককে কয়েকটি public IP-তে বসায়। IPv4 ঠিকানা ফুরিয়ে আসায় বহু দেশের মোবাইল নেটওয়ার্কে এটি প্রচলিত; বাংলাদেশের মোবাইল ডেটাতেও এমন হওয়াই স্বাভাবিক ধরে নেওয়া নিরাপদ, যদিও অপারেটর আর সময়ভেদে আলাদা। RFC 6598 (২০১২) এই কাজের জন্য আলাদা একটি ঠিকানা-পরিসরই সংরক্ষণ করেছে — বিস্তারিত Computer Networks · NAT-এ।

সব অনুরোধ সমান নয় — খরচ ধরে গোনা

একটি ছবি দেখা আর পুরো বছরের অর্ডারের export একই “১টি অনুরোধ” হলে সীমা সম্পদ রক্ষা করে না। তাই অনেক নকশায় প্রতিটি অনুরোধের একটি cost থাকে: সাধারণ GET ১ token, বড় search ৫, export ৫০। কিছু GraphQL API প্রকাশ্যেই query-র আনুমানিক খরচ ধরে “point”-ভিত্তিক সীমা দেয়, পর্ব ৯-এর query cost analysis-এর মতো। Token bucket-এ এটি সহজ: এক token-এর বদলে costটি কাটুন।

৩ · Token bucket আর leaky bucket — গড় হার আর burst

মানুষের ব্যবহার সমান তালে আসে না: অ্যাপ খুলতেই এক সেকেন্ডে ১৫টি অনুরোধ, তারপর দুই মিনিট শুধু পড়া। “সেকেন্ডে ১০টির বেশি নয়” কড়া নিয়ম এই স্বাভাবিক ঝাঁকুনিও আটকায়। দরকার এমন নিয়ম, যা গড়ে হার মানায়, কিন্তু অল্প burst সয়।

Token bucket — বালতিতে token জমে

প্রতিটি key-এর একটি বালতি। প্রতি সেকেন্ডে r-টি token জমে, কিন্তু বালতিতে সর্বোচ্চ b-টি ধরে; উপচে পড়া token হারিয়ে যায়। প্রতিটি অনুরোধ একটি token নেয়। token না থাকলে অনুরোধ ফেরত।

বাস্তবে কেউ প্রতি সেকেন্ডে token যোগ করে না। প্রতি key-তে দুটি সংখ্যা রাখা হয় — শেষ token-সংখ্যা আর শেষ হিসাবের সময় — আর অনুরোধ এলে একবারেই হিসাব (lazy refill): tokens = min(b, tokens + r × (now − last)). নিচের stepper-এ r = সেকেন্ডে ২, b = ৫। শেষ সারিতে একই সিদ্ধান্ত GCRA দিয়ে (অংশ ৫)।

Leaky bucket — দুটি আলাদা জিনিস, একটি নাম

ফুটো বালতিতে পানি যত জোরেই ঢালুন, নিচ দিয়ে বেরোয় একই তালে। Leaky bucket নামে দুটি আলাদা পদ্ধতি চলে, আর বই ও documentation প্রায়ই দুটি মিশিয়ে ফেলে:

Nginx-এর documentation নিজেই limit_req-এর পদ্ধতিকে “leaky bucket” বলে। burst দিলে বাড়তি অনুরোধ অপেক্ষা করে নির্দিষ্ট তালে যায় — queue; সাথে nodelay দিলে অপেক্ষা ছাড়াই সঙ্গে সঙ্গে যায় — তখন আচরণ meter বা token bucket-এর মতো (খুঁটিনাটি সংস্করণভেদে আলাদা; পর্ব ১১-এর config দেখুন)।

এবার দুটি পাশাপাশি চালান: একই seeded অনুরোধ-স্রোত — পেছনে সেকেন্ডে গড়ে ৬টি, আর ২ ও ৬ নম্বর সেকেন্ডে ২০০ ms-এর মধ্যে ৩৫টি করে ঢল। সীমা r = ১০, b = ২০ (leaky queue-র আকারও ২০)।

// Token bucket (meter) vs leaky bucket (queue): same seeded bursty stream, 10 s.
// Limit: r = 10 req/s, b = 20 (token bucket burst = leaky-bucket queue size).
function rng(seed) {                                   // mulberry32: seeded, repeatable
  return () => { seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
}
const rand = rng(7), R = 10, B = 20, arr = [];
for (let t = 0; (t += -Math.log(1 - rand()) / 6) < 10;) arr.push(t);   // ~6 req/s background
for (const s of [2, 6]) for (let i = 0; i < 35; i++) arr.push(s + rand() * 0.2); // 2 bursts of 35
arr.sort((a, b) => a - b);
const row = () => ({ in: 0, tbOk: 0, tbNo: 0, lbOk: 0, lbNo: 0, lbOut: 0 });
const sec = Array.from({ length: 10 }, row);
let tokens = B, last = 0;                              // token bucket state: 2 numbers
let nextFree = 0, maxWait = 0; const outs = [];        // leaky bucket: 1 leaves every 1/R s
for (const t of arr) {
  const s = sec[Math.floor(t)]; s.in++;
  tokens = Math.min(B, tokens + (t - last) * R); last = t;     // lazy refill
  if (tokens >= 1) { tokens -= 1; s.tbOk++; } else s.tbNo++;
  const queued = outs.filter(o => o > t).length;              // still waiting in the bucket
  if (queued >= B) { s.lbNo++; continue; }
  const out = Math.max(t, nextFree); nextFree = out + 1 / R; outs.push(out);
  s.lbOk++; maxWait = Math.max(maxWait, out - t);
  if (out < 10) sec[Math.floor(out)].lbOut++;
}
console.log("sec  in | token bucket ok rej | leaky queue ok rej sent");
sec.forEach((s, i) => console.log(String(i).padStart(3) + String(s.in).padStart(4) + " |" +
  String(s.tbOk).padStart(16) + String(s.tbNo).padStart(4) + " |" + String(s.lbOk).padStart(15) +
  String(s.lbNo).padStart(4) + String(s.lbOut).padStart(5)));
const peak = k => Math.max(...sec.map(s => s[k]));
console.log("max admitted in one second: token bucket " + peak("tbOk") + ", leaky bucket sends " + peak("lbOut"));
console.log("leaky bucket longest wait in queue: " + (maxWait * 1000).toFixed(0) + " ms");

sec  in | token bucket ok rej | leaky queue ok rej sent
  0   5 |               5   0 |              5   0    5
  1   9 |               9   0 |              9   0    9
  2  41 |              23  18 |             24  17   10
  3   9 |               9   0 |              9   0   10
  4   4 |               4   0 |              4   0   10
  5   3 |               3   0 |              3   0   10
  6  46 |              28  18 |             28  18   10
  7   4 |               4   0 |              4   0   10
  8   9 |               9   0 |              9   0   10
  9   4 |               4   0 |              4   0   10
max admitted in one second: token bucket 28, leaky bucket sends 10
leaky bucket longest wait in queue: 1998 ms

৪ · Window দিয়ে গোনা — fixed window, sliding log আর sliding window counter

অনেক নিয়ম লেখা হয় window দিয়ে: “মিনিটে ১০০টি”। এর তিনটি প্রচলিত বাস্তবায়ন, প্রতিটির ভুলের ধরন আলাদা।

Fixed window counter — সরল, কিন্তু সীমানায় দ্বিগুণ

Fixed window counter-এ ঘড়ির প্রতিটি পূর্ণ মিনিটের জন্য একটি গণনা: ১০:১৫:০০ থেকে ১০:১৫:৫৯ পর্যন্ত একটি, ১০:১৬:০০-এ নতুন করে শূন্য। প্রতি key-তে একটি সংখ্যা, Redis-এ একটি INCR — খুব সস্তা।

সমস্যা সীমানায়। কেউ ০:৫৯-এ ১০০টি পাঠালেন (প্রথম মিনিটের সীমা পূর্ণ), আর ১:০০-এ আরও ১০০টি (নতুন মিনিট, গণনা শূন্য)। দুই সেকেন্ডের কম সময়ে ২০০টি — সীমার দ্বিগুণ। আর সবার window একই মুহূর্তে শূন্য হলে মিনিটের শুরুতে আটকে থাকারা একসাথে ফেরেন — ছোট একটি thundering herd.

Sliding window log — নিখুঁত, কিন্তু memory-খেকো

Sliding window log প্রতিটি গৃহীত অনুরোধের সময় একটি তালিকায় রাখে। নতুন অনুরোধ এলে ঠিক শেষ ৬০ সেকেন্ডের বাইরের সময়গুলো মুছে বাকিগুলো গোনে; ১০০-র কম হলে ছাড়ে। কোনো সীমানা নেই, তাই কোনো ফাঁকও নেই। দাম: প্রতি ব্যবহারকারীর জন্য সর্বোচ্চ ১০০টি timestamp. Redis-এ সাধারণত একটি sorted set দিয়ে করা হয়, score-এ সময় রেখে (অংশ ৫-এ memory-র হিসাব)।

Sliding window counter — দুটি সংখ্যায় কাছাকাছি অনুমান

মাঝামাঝি পথটি sliding window counter: শুধু এখনকার আর আগের fixed window-এর গণনা রাখুন, আর ধরে নিন আগের window-এর অনুরোধগুলো সমানভাবে ছড়ানো ছিল। এখনকার window-এ f অংশ সময় পেরোলে শেষ ৬০ সেকেন্ডে আগের window-এর (1 − f) অংশ এখনো ভেতরে:

এই পদ্ধতির একটি রূপ Cloudflare-এর ২০১৭ সালের দিকে প্রকাশিত engineering blog-এ বর্ণিত আছে, যেখানে তাঁরা লিখেছেন বাস্তব traffic-এ এর ভুল খুব কম পাওয়া গেছে (প্রকাশিত বর্ণনা অনুযায়ী; আপনার traffic-এ মাপা দরকার)। নিচের stepper-এ সীমা মিনিটে ১০০।

এবার তিনটি পদ্ধতিকে একই traffic দিন। তিনটি পরিস্থিতি: (A) সীমানার দুই পাশে ১০০ + ১০০; (B) মিনিটের শুরুতে ১০০, পরের মিনিটের মাঝে ১০০; (C) মিনিটের শেষে ১০০, পরের মিনিটের মাঝে ১০০। প্রতিটি ঢল ১ সেকেন্ডে (১০ ms অন্তর)।

// Limit: 100 requests per 60 s for one user. Three ways to count the same traffic.
const LIMIT = 100, W = 60;
function fixedWindow() { let win = -1, n = 0;
  return t => { const w = Math.floor(t / W); if (w !== win) { win = w; n = 0; }
    if (n < LIMIT) { n++; return true; } return false; }; }
function slidingLog() { const log = [];                 // every accepted timestamp
  return t => { while (log.length && log[0] <= t - W) log.shift();
    if (log.length < LIMIT) { log.push(t); return true; } return false; }; }
function slidingCounter() { let win = -1, cur = 0, prev = 0;   // two counters
  return t => { const w = Math.floor(t / W);
    if (w !== win) { prev = (w === win + 1) ? cur : 0; cur = 0; win = w; }
    const weight = 1 - (t - w * W) / W;               // share of previous window still inside
    if (prev * weight + cur < LIMIT) { cur++; return true; } return false; }; }
const burst = (start, n) => Array.from({ length: n }, (_, i) => start + i * 0.01);
const cases = {
  "A: 100 at 0:59, 100 at 1:00": [burst(59, 100), burst(60, 100)],
  "B: 100 at 0:01, 100 at 1:30": [burst(1, 100), burst(90, 100)],
  "C: 100 at 0:59, 100 at 1:30": [burst(59, 100), burst(90, 100)] };
console.log("case                           fixed     log  counter   (allowed: 1st burst + 2nd burst)");
for (const [name, [first, second]] of Object.entries(cases)) {
  const cols = [fixedWindow, slidingLog, slidingCounter].map(make => {
    const allow = make(), a = first.filter(t => allow(t)).length, b = second.filter(t => allow(t)).length;
    return (a + "+" + b).padStart(8); });
  console.log(name.padEnd(29) + cols.join(" "));
}
const fx = fixedWindow(), okA = [...burst(59, 100), ...burst(60, 100)].filter(t => fx(t));
console.log("\nfixed window, case A: " + okA.length + " allowed between " + okA[0].toFixed(2) +
  " s and " + okA[okA.length - 1].toFixed(2) + " s -> 2x the limit in under 2 s");

case                           fixed     log  counter   (allowed: 1st burst + 2nd burst)
A: 100 at 0:59, 100 at 1:00   100+100    100+0    100+2
B: 100 at 0:01, 100 at 1:30   100+100  100+100   100+52
C: 100 at 0:59, 100 at 1:30   100+100    100+0   100+52

fixed window, case A: 200 allowed between 59.00 s and 60.99 s -> 2x the limit in under 2 s

৫ · GCRA, তুলনা আর memory-র হিসাব

GCRA — একটি সংখ্যায় পুরো বালতি

GCRA (Generic Cell Rate Algorithm) এসেছে ১৯৯০-এর দশকের ATM network-এর traffic management থেকে। এটি token bucket-এর গণিত একটিমাত্র timestamp দিয়ে করে। ভাবনাটা এমন: নিয়মিত হারে চললে প্রতি T = 1/r সেকেন্ডে একটি অনুরোধ আসার কথা। প্রতি key-তে রাখা হয় শুধু theoretical arrival time (TAT) — পরের অনুরোধ “নিয়ম অনুযায়ী” কখন আসার কথা।

T   = 1 / r              // emission interval: seconds per request
tau = (b - 1) * T        // burst tolerance: how far ahead TAT may run

on request at time now:
    tat = max(TAT[key], now)
    if tat - now > tau:  reject (429); retry after (tat - now - tau)
    else:                TAT[key] = tat + T; allow

অংশ ৩-এর stepper-এর শেষ সারি এটিই: r = ২, তাই T = ০.৫ সেকেন্ড; b = ৫, তাই tau = ২। প্রথম ৫টি অনুরোধে TAT ০ থেকে ২.৫ হয়; ষষ্ঠটিতে TAT − now = ২.৫ > ২, ফেরত — token bucket-এর সাথে হুবহু মিল, অথচ state একটি সংখ্যা। বাড়তি সুবিধা: tat − now − tau সরাসরি বলে দেয় কত পরে আবার চেষ্টা করা যাবে — Retry-After-এর মান। কিছু open-source limiter (যেমন Redis-এর একটি module) GCRA ব্যবহার করে বলে তাদের documentation জানায় (সংস্করণভেদে যাচাই করুন)।

এক টেবিলে ছয়টি পদ্ধতি

Memory — ১ কোটি ব্যবহারকারীর হিসাব

ধরা যাক ১ কোটি (১০M) ব্যবহারকারী, প্রত্যেকের সীমা মিনিটে ১০০। নিচের হিসাবে অনুমানগুলো স্পষ্ট লেখা; আসল store-এ প্রতি key-এর বাড়তি খরচ সংস্করণ আর encoding-ভেদে আলাদা, তাই নিজের store-এ মেপে নিন।

// Memory for limiter state: 10 million users, limit 100 requests per minute each.
// Assumptions (state them!): timestamps 8 bytes, counters 4 bytes, and every user key
// costs a flat 64 bytes of overhead (key string + hash-table entry). Real stores differ.
const USERS = 10e6, LIMIT = 100, KEY = 64;
const algos = [
  // [name, bytes of state per user, what is stored]
  ["sliding log",            LIMIT * 8,  "up to 100 timestamps x 8 B"],
  ["sliding log, 64 B/entry", LIMIT * 64, "assume ~64 B per entry in a sorted set"],
  ["fixed window",           4 + 4,      "count + window id"],
  ["sliding window counter", 4 + 4 + 4,  "current + previous count + window id"],
  ["token bucket",           8 + 8,      "tokens (double) + last refill time"],
  ["GCRA",                   8,          "one timestamp: theoretical arrival time"],
];
const human = b => b >= 1e9 ? (b / 1e9).toFixed(2) + " GB" : (b / 1e6).toFixed(0) + " MB";
console.log("algorithm                state B  +key B  total for 10M users  stored");
for (const [name, state, what] of algos) {
  const per = state + KEY;
  console.log(name.padEnd(24) + String(state).padStart(8) + String(per).padStart(8) +
    human(per * USERS).padStart(21) + "  " + what);
}
// Only users active in the last minute need state; the rest expire (TTL).
const active = 0.05 * USERS;                         // assume 5% active at peak
console.log("\nif only 5% (" + active / 1e6 + "M) are active: sliding log " +
  human((LIMIT * 8 + KEY) * active) + ", token bucket " + human((16 + KEY) * active));

algorithm                state B  +key B  total for 10M users  stored
sliding log                  800     864              8.64 GB  up to 100 timestamps x 8 B
sliding log, 64 B/entry     6400    6464             64.64 GB  assume ~64 B per entry in a sorted set
fixed window                   8      72               720 MB  count + window id
sliding window counter        12      76               760 MB  current + previous count + window id
token bucket                  16      80               800 MB  tokens (double) + last refill time
GCRA                           8      72               720 MB  one timestamp: theoretical arrival time

if only 5% (0.5M) are active: sliding log 432 MB, token bucket 40 MB

৬ · Distributed rate limiting — ভাগ করা counter, race আর ঘড়ি

এক সার্ভারে limiter মানে memory-তে একটি hash table. কিন্তু gateway বাস্তবে হয়তো বিশটি, আর load balancer একজনের অনুরোধ যেকোনোটিতে পাঠায় (পর্ব ১৪)। প্রতিটি gateway নিজে নিজে “মিনিটে ১০০” গুনলে মোট সীমা কার্যত ২০ × ১০০ = ২,০০০। পর্ব ১১-এ ঠিক এই সতর্কতা ছিল: Nginx-এর গণনা একটি instance-এর ভেতরে। তিনটি পথ আছে।

পথ ১ — কেন্দ্রীয় store: Redis-এ INCR আর EXPIRE

সব gateway একটি ভাগ করা store-এ গোনে, সাধারণত Redis-এ, কারণ এটি memory-তে থাকে, দ্রুত, আর একটি key-এর ওপর command একটির পর একটি চালায় (পর্ব ৩০)। Fixed window-এর সরলতম রূপ Redis-এর নিজের documentation-এও বর্ণিত:

INCR   rl:u42:1015          -> (integer) 1     first request in this minute
EXPIRE rl:u42:1015 60                          only when INCR returned 1
...
INCR   rl:u42:1015          -> (integer) 101   > 100: reply 429

INCR নিজে atomic: দুটি gateway একসাথে ডাকলেও একজন ১০০, অন্যজন ১০১ পায় — কেউ একই সংখ্যা পায় না। কিন্তু দুটি command-এর মাঝখানে ফাঁক আছে: INCR-এর পরে gateway crash করলে EXPIRE কখনো চলে না, key চিরকাল থাকে, আর সেই ব্যবহারকারী চিরতরে আটকে যান। প্রতিকার: দুটি একসাথে একটি Lua script-এ, অথবা যেসব সংস্করণে EXPIRE … NX বিকল্প আছে (লেখার সময়ে Redis 7.0 থেকে) সেটি দিয়ে।

Race — “পড়ে, তারপর লেখা” কেন সীমা ফুটো করে

Token bucket-এর মতো জটিল state-এ একটি command যথেষ্ট নয়: পড়তে হয় (token, সময়), হিসাব করতে হয়, তারপর লিখতে হয়। এই তিন ধাপ আলাদা network call হলে মাঝখানে অন্য gateway ঢুকে পড়ে — ক্লাসিক race condition আর lost update — পর্ব ২৪-এ দেখেছেন, আর গোড়ার ধারণা Operating Systems · race condition-এ।

সংখ্যায়: দুটি gateway, ২০০ ms-এ ১,০০০টি অনুরোধ, প্রতিটি store call ১–৩ ms; তিন পদ্ধতি একই seeded interleaving-এ।

// Two gateway nodes share one counter (limit 100 per window) in a remote store.
// 1,000 requests arrive in 200 ms, split between nodes; each store call takes 1-3 ms.
function rng(seed) {                                   // mulberry32: seeded, repeatable
  return () => { seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
}
const LIMIT = 100, N = 1000;
function run(mode) {
  const rand = rng(99), ev = [];
  for (let i = 0; i < N; i++) {
    const t = rand() * 200, node = rand() < 0.5 ? "A" : "B";
    const rtt = 1 + 2 * rand();                         // read reply arrives after rtt
    ev.push({ t, kind: "read", id: i, node }, { t: t + rtt, kind: "write", id: i, node });
  }
  ev.sort((a, b) => a.t - b.t);                         // the seeded interleaving
  let counter = 0, admitted = 0; const seen = {}, perNode = { A: 0, B: 0 };
  for (const e of ev) {
    if (mode === "atomic INCR") {                       // one indivisible step in the store
      if (e.kind === "read") { counter++; if (counter <= LIMIT) { admitted++; perNode[e.node]++; } }
      continue;
    }
    if (e.kind === "read") { seen[e.id] = counter; continue; }   // GET (value is now stale)
    if (seen[e.id] >= LIMIT) continue;                  // decided on the stale value
    admitted++; perNode[e.node]++;
    if (mode === "GET then SET v+1") counter = seen[e.id] + 1;   // lost updates
    else counter++;                                     // GET then INCR
  }
  return [mode.padEnd(18), String(admitted).padStart(9), String(admitted - LIMIT).padStart(12),
    String(counter).padStart(14), ("A " + perNode.A + " / B " + perNode.B).padStart(16)].join("");
}
console.log("method             admitted  over limit  final counter      per node");
for (const m of ["GET then SET v+1", "GET then INCR", "atomic INCR"]) console.log(run(m));

method             admitted  over limit  final counter      per node
GET then SET v+1       1000         900            89   A 494 / B 506
GET then INCR           114          14           114     A 50 / B 64
atomic INCR             100           0          1000     A 47 / B 53

একটি Lua script-এ token bucket দেখতে এমন। এটি পড়ে বোঝার জন্য; production-এ নিজের Redis সংস্করণের documentation আর পরীক্ষায় যাচাই করুন:

-- KEYS[1] = bucket key; ARGV = rate (tokens/s), burst, now (ms), cost
local rate, burst = tonumber(ARGV[1]), tonumber(ARGV[2])
local now, cost   = tonumber(ARGV[3]), tonumber(ARGV[4])
local s = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(s[1]) or burst          -- new key: full bucket
local ts     = tonumber(s[2]) or now
tokens = math.min(burst, tokens + (now - ts) / 1000 * rate)
local allowed = 0
if tokens >= cost then tokens = tokens - cost; allowed = 1 end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(burst / rate * 1000) + 1000)
return { allowed, math.floor(tokens) }          -- whole tokens left

TTL বালতি পূর্ণ হওয়ার সময়ের একটু বেশি — তারপর key না থাকলেও ফল একই, কারণ নতুন key মানে পূর্ণ বালতি। Redis Cluster-এ একটি script-এর সব key একই shard-এ থাকতে হয়; একজন user-এর কয়েকটি key একসাথে ছুঁতে হলে key-তে hash tag (যেমন rl:{u42}:min) দিয়ে তাদের একই slot-এ রাখা হয় (পর্ব ৩০)।

পথ ২ — প্রতিটি node-এ local সীমা, মাঝে মাঝে মিলিয়ে নেওয়া

প্রতিটি অনুরোধে store-এ যাওয়া মানে এক round trip বাড়তি latency, আর store-ই নতুন single point of failure. বিকল্প:

• সীমা ভাগ করা: N-টি gateway থাকলে প্রত্যেকে limit ÷ N গোনে। Network call নেই। কিন্তু load balancer একজনের অনুরোধ সমান ভাগ না করলে তিনি নিজের সীমার আগেই আটকান, আর autoscaling-এ N বদলালে ভাগও বদলাতে হয়।
• মাঝে মাঝে মেলানো: প্রতিটি node local গোনে, আর প্রতি ১০০ ms-এর মতো সময়ে নিজের গণনা কেন্দ্রে বা অন্যদের পাঠায়, সবার মোট জেনে নেয়। সীমা প্রায় ঠিক, কিন্তু সিঙ্ক-এর ফাঁকে খানিকটা বাড়তি ঢোকে।
• Token leasing: gateway কেন্দ্র থেকে একসাথে ধরা যাক ১০টি token ধার নেয়, সেগুলো নিজের memory থেকে খরচ করে, ফুরালে আবার চায়। Store-এ call প্রায় ১০ গুণ কম; দাম হলো একজনের ধার নেওয়া অব্যবহৃত token অন্য gateway-তে কাজে লাগে না।

পথ ৩ — আনুমানিক global সীমা মেনে নেওয়া

সীমা ১০০ হলে ১০৫টি ছাড়া পেলে কি ক্ষতি? ন্যায্যতার সীমায় সাধারণত না; তাই অনেক ব্যবস্থা দুই স্তর রাখে — প্রতিটি node-এ একটি দ্রুত local token bucket (ঢিলা সীমা, ঢল ঠেকাতে) আর একটি কেন্দ্রীয় সেবা (সঠিক ভাগের জন্য)। Envoy proxy-তে local rate limit filter আর বাইরের global rate limit service, দুটিই আছে (documentation অনুযায়ী; সংস্করণভেদে আলাদা)। কিন্তু টাকা বা নিরাপত্তার সীমায় — OTP, পেমেন্ট চেষ্টা, login — নিখুঁত atomic হিসাবই নিন। আর একাধিক region-এ একটি নিখুঁত global সীমা মানে প্রতিটি অনুরোধে region পেরিয়ে সমন্বয়, অর্থাৎ বহু ms বাড়তি; সাধারণত প্রতিটি region-কে মোট সীমার একটি ভাগ দেওয়া হয় (পর্ব ৪০-এর consistency-র দর-কষাকষি এখানেও)।

ঘড়ি, hot key আর store বিকল হলে

• ঘড়ি: fixed window-এর key-তে মিনিটের নাম বসে, যেমন 1015. দুই gateway-এর ঘড়িতে কয়েকশো ms ফারাক (clock skew) থাকলে সীমানার কাছে তারা দুটি আলাদা window-এ গোনে। Token bucket-এ পিছিয়ে থাকা ঘড়ির now ঋণাত্মক ব্যবধান দেখাতে পারে। প্রতিকার: সময় এক উৎস থেকে নিন — store-এর নিজের ঘড়ি (Redis-এ TIME) — আর ঋণাত্মক ব্যবধান ০ ধরুন। ব্যবধান মাপতে wall clock নয়, monotonic clock (পর্ব ৩৯)।
• Hot key: একটি বড় tenant-এর একটি global key-তে সেকেন্ডে লাখো call গেলে একটি Redis shard-ই গরম হয়। প্রতিকার: counter-কে কয়েকটি ভাগে ভাঙা (sharded counter), local token leasing, বা আগে বের করা কোন key-গুলো এমন — heavy hitters, যা count-min sketch দিয়ে কম memory-তে খোঁজা যায় (পর্ব ৪৫)।
• Store বিকল: limiter-এর call-এ ছোট timeout (কয়েক ms) দিন। তারপর একটি সিদ্ধান্ত: fail open (সবাইকে ছেড়ে দিন — সেবা চালু, সুরক্ষা সাময়িক বন্ধ) নাকি fail closed (সবাইকে ফেরান — সুরক্ষা আছে, সেবা নেই)। সাধারণ API-তে প্রায়ই fail open, সাথে প্রতিটি node-এ একটি ঢিলা local সীমা; OTP বা পেমেন্টে fail closed. বারবার ব্যর্থ store-কে ডাকা থামাতে circuit breaker (পর্ব ৪৮)।

৭ · কোথায় বসাবেন আর কী উত্তর দেবেন — 429, Retry-After আর RateLimit header

কোথায় — প্রতিটি স্তরের নিজের কাজ

কী উত্তর — 429, Retry-After আর সীমার খবর

সীমা পেরোলে সঠিক উত্তর 429 Too Many Requests (পর্ব ৮-এ status code-এর তালিকা)। সাথে Retry-After — কত সেকেন্ড পরে, বা কোন সময়ের পরে, আবার চেষ্টা করা যাবে। আর ক্লায়েন্ট যাতে আগেই ধীর হতে পারে, স্বাভাবিক উত্তরেও সীমার খবর দেওয়া যায়:

HTTP/1.1 429 Too Many Requests
Retry-After: 20
RateLimit-Policy: "per-user";q=100;w=60
RateLimit: "per-user";r=0;t=20
Content-Type: application/problem+json
Cache-Control: no-store

{
  "type": "https://api.shop.example/problems/rate-limited",
  "title": "Too many requests",
  "status": 429,
  "detail": "Limit is 100 requests per minute. Try again in about 20 seconds."
}

ভালো উত্তরের চারটি নিয়ম: (১) কোন নিয়ম ভেঙেছে, তা জানান, ভেতরের তথ্য নয়; (২) উত্তরটি ছোট আর সস্তা রাখুন (পর্ব ১৮); (৩) Retry-After-এর মান সত্যিকারের হিসাব থেকে দিন — GCRA-তে tat − now − tau, fixed window-এ window শেষ হতে বাকি সময়; (৪) সবাইকে একই মান দিলে সবাই একই মুহূর্তে ফেরেন — মানটিতে একটু jitter যোগ করুন।

ক্লায়েন্টের দায়িত্ব

429 পেয়ে সঙ্গে সঙ্গে আবার পাঠানো ক্লায়েন্ট নিজের সমস্যা নিজেই বাড়ায়, আর retry storm তৈরি করে। নিয়ম: Retry-After থাকলে সেটি মানুন; না থাকলে exponential backoff আর jitter; retry-র মোট সংখ্যায় সীমা; আর যে অনুরোধ এখন জরুরি নয় (analytics, prefetch), তা বাদ দিন। Backoff-এর পুরো নকশা আছে পর্ব ৪৮-এ: Resilience pattern — timeout, retry, backoff, circuit breaker আর bulkhead. দরকারে ক্লায়েন্ট নিজের ভেতরেও একটি token bucket রাখে, যাতে সীমা ছোঁয়ার আগেই নিজে ধীর হয়।

৮ · Adaptive সীমা আর ইন্টারভিউতে rate limiter নকশা

স্থির সংখ্যা যখন যথেষ্ট নয়

“প্রতি user মিনিটে ১০০” একটি স্থির সংখ্যা, load test-এর দিনের ক্ষমতা ধরে বানানো। কিন্তু পেছনের database ধীর হলে একই হার অনেক বেশি ভার। পর্ব ১৮-এর হিসাবটি মনে করুন — Little-এর সূত্র L = λ·W: সেকেন্ডে ২০০টি অনুরোধ আর প্রতিটি ০.১ সেকেন্ড মানে ভেতরে গড়ে ২০টি; latency ০.৫ সেকেন্ড হলে একই ২০০-তে ভেতরে ১০০টি। Rate limit তখনও ২০০ ঢোকাবে।

তাই দুটি adaptive কৌশল প্রচলিত: (১) concurrency limit, যা ভেতরে চলমান অনুরোধ গোনে আর latency বাড়লে AIMD-এর মতো নিয়মে নিজের সীমা কমায় — পূর্ণ আলোচনা পর্ব ১৮-এ; (২) চাপ বুঝে rate limit বদলানো: পেছনের সার্ভিস সুস্থ থাকলে প্রতিটি tenant নিজের চুক্তির সীমা পান, চাপের সংকেত (latency, ত্রুটির হার) এলে সবার সীমা একই অনুপাতে, বা কম জরুরি শ্রেণিতে আগে, কমে। ক্লায়েন্টের দিকে একই ভাবনা adaptive throttling. সবই পরিমাপ-নির্ভর, তাই limiter-এর নিজের metric লাগে (পর্ব ৫০)।

ইন্টারভিউতে: “একটি rate limiter নকশা করুন”

এটি system design ইন্টারভিউর সবচেয়ে চেনা প্রশ্নগুলোর একটি। পর্ব ৬-এর কাঠামো ধরে এগোন — requirement, হিসাব, API ও data model, তারপর deep dive.

1. Requirement জিজ্ঞেস করুন। কার হিসাবে? কোন নিয়ম, burst কত? কয়টি gateway, কয়টি region? ১% বাড়তি চলবে? বিকল হলে fail open না closed? বাড়তি latency কত পর্যন্ত (ধরা যাক p99-এ ২ ms)?
2. হিসাব। Peak-এ সেকেন্ডে কতগুলো অনুরোধ, প্রতিটিতে store-এ কয়টি call, এক window-এ কতগুলো সক্রিয় key, প্রতি key-তে কত byte (অনুশীলন ৪-এ পুরো হিসাব)।
3. নিয়মের API আর data model. নিয়ম config-এ, কোডে নয়।
4. Algorithm বাছাই আর কারণ। সাধারণত token bucket বা GCRA (burst সয়, state ছোট); ছোট নিরাপত্তা-সীমায় sliding log.
5. Deep dive. Atomicity (Lua), sharding আর hot key, local cache বা token leasing, ঘড়ি, store বিকল হলে কী, একাধিক region, header আর ক্লায়েন্টের আচরণ, metric আর নতুন নিয়মের shadow mode.

{ "rules": [
  { "id": "user-default", "key": ["user"],          "rate": 100, "per": "1m", "burst": 20 },
  { "id": "login",        "key": ["user", "ip"],    "rate": 10,  "per": "15m" },
  { "id": "otp-sms",      "key": ["phone"],         "rate": 3,   "per": "10m", "failMode": "closed" },
  { "id": "tenant",       "key": ["tenant"],        "rate": 500, "per": "1s",  "burst": 1000 }
] }

Redis:  rl:{u42}:user-default  ->  hash { tokens: 17.4, ts: 1761638400123 }   TTL ~ 2 min
        rl:{8801XXXXXXXXX}:otp-sms  ->  sorted set of timestamps (exact, small)

৯ · AI-এর যুগে rate limiter-এর নকশা যাচাই

AI-কে rate limiter চাইলে কয়েক সেকেন্ডে Redis আর token bucket-এর কোড আসে, প্রায়ই সাথে “Kafka আর microservice যোগ করুন”। এক সার্ভারে কোডটি ঠিক চলতেও পারে; কিন্তু কার হিসাব, কয়টি gateway, store বিকল হলে কী — এসব প্রায়ই বাদ যায়। সাধারণ ভুলগুলো:

AI-এর rate limiter হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি নিয়মের key (user, API key, IP, tenant) স্পষ্ট, আর IP-সীমা ঢিলা
• Burst-এর ছাদ b + r·T আর memory-র হিসাব নিজে আবার করেছি
• প্রতিটি read-modify-write atomic (INCR বা Lua), আর প্রতিটি key-এর TTL আছে
• Gateway-সংখ্যা, ঘড়ির উৎস আর store বিকল হলে fail open বা closed — লেখা আছে
• উত্তরে 429 আর Retry-After; ক্লায়েন্টে backoff ও jitter; header-এর নাম documentation দেখে মিলিয়েছি
• একটি simulation বা load test চালিয়েছি — race-এ বাড়তি, সীমানার ২×, আর shadow mode-এ কতজন আটকাত