Global Distributed Rate Limiter ডিজাইন

ধরো তোমার API-তে নিয়ম: প্রতি ব্যবহারকারী মিনিটে সর্বোচ্চ ১০০ রিকোয়েস্ট। একটা সার্ভার হলে সহজ — একটা counter রাখলেই হলো। কিন্তু যখন ৫০০টা সার্ভার তিনটা region-এ ছড়ানো, আর ব্যবহারকারীর রিকোয়েস্ট যেকোনো সার্ভারে যেতে পারে — তখন "মিনিটে ১০০" কে গুনবে? এটাই global distributed rate limiter-এর আসল সমস্যা।

১. সমস্যা বোঝা (Requirements)

ফাংশনাল রিকোয়ারমেন্ট:

• প্রতি ব্যবহারকারী/API key/IP-তে সীমা প্রয়োগ (যেমন ১০০ req/min)।
• বিভিন্ন rule (per-endpoint, per-tier)।
• সীমা ছাড়ালে 429 Too Many Requests রিটার্ন + Retry-After header।

নন-ফাংশনাল রিকোয়ারমেন্ট:

• খুবই Low latency — rate limiter প্রতিটা রিকোয়েস্টের পথে বসে, তাই কয়েক মিলিসেকেন্ডের বেশি যোগ করা যাবে না।
• High availability — rate limiter পড়লে কী হবে? (fail-open নাকি fail-closed?)
• Scale — লক্ষ লক্ষ QPS, বহু region।
• যুক্তিসঙ্গত accuracy — সামান্য বেশি/কম গোনা সহনীয় কিনা ঠিক করা।

২. স্কেল আন্দাজ (Estimation)

মোট ট্রাফিক          = 1,000,000 req/sec (১০ লক্ষ QPS)
সার্ভার সংখ্যা         = 500, region = 3
প্রতি সার্ভার          ≈ 2,000 req/sec

প্রতি রিকোয়েস্টে যদি Redis hit হয়:
   Redis লোড         = 1,000,000 ops/sec (read+increment)
   একটা Redis node   ≈ 100k-200k ops/sec
   => 5-10 Redis shard লাগবে শুধু rate limit-এর জন্য

কেন্দ্রীয় Redis call latency ≈ 0.5-2 ms (একই region)
ক্রস-region call latency      ≈ 50-150 ms  (অগ্রহণযোগ্য!)

memory: key = userId+window; প্রতি key ~50 bytes
   active users 10M => ~500 MB (সহজেই ধরে)

মূল উপলব্ধি: প্রতি রিকোয়েস্টে কেন্দ্রীয় Redis hit করা একই region-এ সহনীয়, কিন্তু ক্রস-region call latency মেরে ফেলবে। তাই region-aware ডিজাইন লাগবে।

৩. API ডিজাইন

Rate limiter সাধারণত একটা middleware/sidecar; এর অভ্যন্তরীণ "check" API এমন দেখায়:

# অভ্যন্তরীণ চেক (প্রতি রিকোয়েস্টে কল হয়)
ALLOW?  key="user:42:GET:/search"  limit=100  window=60s
  -> { "allowed": true,  "remaining": 73, "reset": 1718960400 }
  -> { "allowed": false, "remaining": 0,  "retry_after": 12 }

# ক্লায়েন্ট যে header পায়
HTTP 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
Retry-After: 12

# কনফিগ (control plane)
PUT /v1/rules
    body: { "scope": "api_key", "limit": 100, "window": "1m", "endpoint": "/search" }

৪. ডেটা মডেল

উপাদান	কী রাখে	স্টোরেজ
Counter	প্রতি (key, window)-এ count	Redis (in-memory, atomic)
Rules	কোন scope-এ কত limit	config store / cache
Local counter	সার্ভার-লোকাল আংশিক count	প্রসেস memory

Counter key ডিজাইন: ratelimit:{scope}:{id}:{window_start} — যেমন ratelimit:user:42:1718960400। window-নির্ভর key হলে পুরোনো window স্বয়ংক্রিয়ভাবে অপ্রাসঙ্গিক হয় আর TTL দিয়ে মুছে যায়।

কেন Redis? কারণ এটা in-memory (দ্রুত), atomic operation (INCR, Lua script) দেয় যাতে race condition ছাড়াই count + check এক ধাপে হয়, আর TTL দিয়ে window expire করা যায়।

অ্যাটমিসিটি জরুরি: "read করো, ১ যোগ করো, লিখো" আলাদা ধাপে করলে দুই রিকোয়েস্ট একই মান পড়ে দুজনেই বাড়াবে — সীমা ভেঙে যাবে। তাই একটাই atomic INCR বা Lua script ব্যবহার করো।

৫. হাই-লেভেল ডিজাইন

তিনটা মূল আর্কিটেকচার আছে, ট্রেড-অফসহ:

(ক) Centralized counter (Redis): প্রতিটা সার্ভার প্রতি রিকোয়েস্টে কেন্দ্রীয় Redis-এ INCR করে।

Request --> App Server --> Redis INCR(key)
   count <= limit ?  --> ALLOW
   count >  limit ?  --> 429

• ✅ সবচেয়ে accurate (সব সার্ভার একই counter দেখে)।
• ❌ প্রতি রিকোয়েস্টে network hop; Redis একটা SPOF + hot key ঝুঁকি।

(খ) Local-only: প্রতিটা সার্ভার নিজের memory-তে গোনে।

• ✅ শূন্য network latency, super দ্রুত।
• ❌ ভুল — N সার্ভার থাকলে কার্যকর সীমা N গুণ হয়ে যায়।

(গ) Local + periodic sync (হাইব্রিড): প্রতিটা সার্ভার লোকালি গোনে, প্রতি কয়েকশো ms পর পর Redis-এ নিজের count শেয়ার করে আর গ্লোবাল estimate টানে।

• ✅ দ্রুত (বেশিরভাগ চেক লোকাল) + প্রায়-accurate।
• ❌ সামান্য overshoot সম্ভব (sync window-এর মধ্যে)।

বাস্তবে বড় স্কেলে (গ) সবচেয়ে জনপ্রিয় — latency কম রেখে গ্রহণযোগ্য accuracy দেয়।

৬. গভীরে (Deep Dive)

(ক) অ্যালগরিদম: কোন window?

• Fixed window counter: প্রতি মিনিটের শুরুতে রিসেট। সরল, কিন্তু boundary সমস্যা — ৫৯ সেকেন্ডে ১০০ + পরের ০ সেকেন্ডে ১০০ = ২ সেকেন্ডে ২০০ পার হয়ে যায়।
• Sliding window log: প্রতিটা রিকোয়েস্টের timestamp রাখে, নিখুঁত — কিন্তু memory ব্যয়বহুল।
• Sliding window counter: বর্তমান ও আগের window-র weighted গড় — prev_count * overlap_ratio + current_count। প্রায়-নিখুঁত কিন্তু সস্তা। সবচেয়ে ব্যবহৃত।
• Token bucket: নির্দিষ্ট হারে token জমা হয়, প্রতি রিকোয়েস্ট একটা token খরচ করে; burst সহ্য করে। API gateway-তে জনপ্রিয়।

(খ) Hot key সমস্যা

একটা বিশাল গ্রাহকের একটাই API key যদি সেকেন্ডে ৫০ হাজার রিকোয়েস্ট পাঠায়, সেই key-এর counter যেই Redis shard-এ থাকে সেটা একা overloaded হয়। সমাধান:

• Local pre-aggregation: সার্ভার লোকালি গুনে batched ভাবে Redis-এ পাঠায়, প্রতি রিকোয়েস্টে নয়।
• Key sharding: key:shard1..N ভাগ করে আলাদা node-এ, পড়ার সময় যোগফল নাও (approximate)।

(গ) Multi-region

ক্রস-region Redis call ১০০ ms+, তাই সাধারণত প্রতিটা region-এ নিজস্ব rate limit প্রয়োগ হয় (limit/region ভাগ করে), অথবা eventual sync হয়। কঠোরভাবে global limit লাগলে latency বনাম accuracy-র দাম দিতে হয় — এটা ব্যবসায়িক সিদ্ধান্ত।

৭. বটলনেক ও স্কেলিং

• Redis SPOF: Redis Cluster + replica দিয়ে HA; failover-এ লোকাল fallback।
• Network overhead: প্রতি রিকোয়েস্টে round-trip কমাতে Lua script-এ check+incr একসাথে, আর local+sync হাইব্রিড।
• Clock skew: sliding window timestamp সার্ভারের ঘড়ির উপর নির্ভর করে; NTP দিয়ে সিঙ্ক রাখো।
• Memory growth: key-তে TTL দাও যাতে পুরোনো window নিজে নিজে মুছে যায়।
• Hot key: উপরে আলোচিত sharding + pre-aggregation।

৮. সারসংক্ষেপ

Distributed rate limiter-এর মূল প্রশ্ন তিনটা: counter কোথায় (Redis কেন্দ্রীয়, atomic), কোন algorithm (sliding window counter সাধারণত সেরা ভারসাম্য), আর accuracy বনাম latency কতটা ছাড় দেবে (local+sync হাইব্রিড)। মনে রাখো — rate limiter প্রতিটা রিকোয়েস্টের পথে বসে, তাই এর latency ও availability পুরো সিস্টেমকে প্রভাবিত করে। তাই fail-open ডিফল্ট, hot key-র জন্য pre-aggregation, আর region-aware কৌশল রাখা জরুরি।