Web Services১১ মিনিট পাঠ

রেট লিমিটার ডিজাইন (Design a Rate Limiter)

সার্ভার ডুবে যাওয়ার আগেই ফ্লাড বা বন্যার পানি আটকে দিন
scope:বাস্তব জগতের সিস্টেম (Real-World System)difficulty:মাঝারি

রেট লিমিট (Rate Limit) কেন প্রয়োজন?

কল্পনা করুন একটি পানির কল। এটি সামান্য খুলে রাখলে আপনি সুন্দরভাবে পানি পেতে থাকবেন। কিন্তু যদি আপনি এর সাথে ৫০টি হোজ পাইপ যুক্ত করে একেবারে পুরোপুরি খুলে দেন — তবে পাইপগুলো ফেটে যাবে। একটি রেট লিমিটার (rate limiter) হলো একটি ভালভ (valve) যা পানির প্রবাহ নিয়ন্ত্রণ করে।

রেট লিমিটিং ছাড়া আপনার API যেসব ঝুঁকির সম্মুখীন হতে পারে:

  • ডিনায়াল অফ সার্ভিস (DoS) আক্রমণ: কোনো ক্ষতিকারক ব্যক্তি বা হ্যাকার আপনার সার্ভারে লক্ষ লক্ষ রিকোয়েস্ট পাঠিয়ে বন্যা (flood) বইয়ে দেয়, যাতে আসল ব্যবহারকারীদের জন্য সার্ভিসটি আন-অ্যাভেইলেবল বা ব্যবহার অযোগ্য হয়ে যায়।
  • ত্রুটিপূর্ণ বা মিসবিহেভিং ক্লায়েন্ট: কোনো বাগ যুক্ত স্ক্রিপ্ট ভুল করে সেকেন্ডে ১০টি রিকোয়েস্টের পরিবর্তে ১০,০০০টি রিকোয়েস্ট পাঠাতে পারে।
  • রিসোর্সেস স্টারভেশন: কোনো একজন ভারী ব্যবহারকারী একাই আপনার সার্ভারের সমস্ত ক্ষমতা বা সক্ষমতা ব্যবহার করে ফেলে, যার ফলে অন্যদের জন্য কিছুই অবশিষ্ট থাকে না।
  • অতিরিক্ত খরচ: ক্লাউড এনভায়রনমেন্টে প্রতিটি রিকোয়েস্টের জন্য টাকা খরচ হয়। অনিয়ন্ত্রিত ট্র্যাফিক রাতের ঘুম হারাম করে দিতে পারে।

রেট লিমিটিং আপনার সিস্টেমের ন্যায্য ব্যবহার (fair usage) নিশ্চিত করে এবং সিস্টেমকে ওভারলোড হওয়া থেকে রক্ষা করে। গুগল, টুইটার, গিটহাব, স্ট্রাইপ এর মতো প্রতিটি বড় API তে রেট লিমিটার ব্যবহার করা হয়।

▸ সমস্যা: সার্ভার রিকোয়েস্টের বন্যায় ওভারহেল্মড হয়ে যায়
Click chart to zoom
কোর রেট লিমিটিং সিদ্ধান্ত নেওয়ার প্রক্রিয়া — প্রতিটি অ্যালগরিদম এই প্যাটার্নটিই অনুসরণ করে, শুধু তাদের কাউন্টার ট্র্যাক করার পদ্ধতিটি ভিন্ন

রেট লিমিটার কোথায় বসাবেন

আপনার কাছে কয়েকটি বিকল্প রয়েছে:

  • ক্লায়েন্ট-সাইড: ক্লায়েন্ট নিজেই তার রিকোয়েস্টগুলো লিমিট বা সীমাবদ্ধ করে। এটি অনির্ভরযোগ্য — কারণ কোনো দূষিত ক্লায়েন্ট বা হ্যাকার খুব সহজেই এটি এড়িয়ে যেতে পারে।
  • সার্ভার-সাইড: আপনার API সার্ভার রিকোয়েস্ট প্রসেস করার আগেই লিমিট চেক করে। এটি একটি সাধারণ এবং সহজ পদ্ধতি।
  • মিডলওয়্যার / এপিআই গেটওয়ে: ব্যাকএন্ড সার্ভারে পৌঁছানোর আগেই একটি সম্পূর্ণ আলাদা স্তর (যেমন Nginx, Kong, বা AWS API Gateway) রেট লিমিটিং হ্যান্ডেল করে। প্রোডাকশনের ক্ষেত্রে এটি সবচেয়ে সাধারণ পদ্ধতি — যা আপনার সার্ভারকে অতিরিক্ত ট্রাফিকের হাত থেকে পুরোপুরি রক্ষা করে।

অধিকাংশ সিস্টেম API Gateway পদ্ধতি ব্যবহার করে থাকে। এটি সেন্ট্রালাইজড, যেকোনো ল্যাঙ্গুয়েজের জন্য ব্যবহার করা যায় (language-agnostic), এবং এর জন্য আপনার অ্যাপ্লিকেশনের কোডে কোনো পরিবর্তন করার প্রয়োজন পড়ে না।

অ্যালগরিদম ১: টোকেন বাকেট (Token Bucket)

এটি সবচেয়ে জনপ্রিয় রেট লিমিটিং অ্যালগরিদম। একে একটি আর্কেড টোকেন মেশিনের মতো ভাবতে পারেন:

  • আপনার কাছে একটি বাকেট (bucket) বা বালতি আছে যা টোকেন ধারণ করতে পারে (ধরা যাক, সর্বোচ্চ ১০টি টোকেন)।
  • একটি নির্দিষ্ট হারে টোকেন যোগ করা হয় (ধরা যাক, প্রতি সেকেন্ডে ১টি টোকেন)।
  • প্রতিটি রিকোয়েস্ট করতে ১টি টোকেনের প্রয়োজন হয়। যদি বালতিতে টোকেন থাকে, তবে রিকোয়েস্টটি কার্যকর হয়।
  • যদি বাকেটটি খালি থাকে, তবে রিকোয়েস্টটি বাতিল হয়ে যায় (HTTP 429)।
  • যদি বাকেটটি পূর্ণ থাকে, তবে নতুন টোকেন উপচে পড়ে (অর্থাৎ বাতিল হয়ে যায়)।

এটি কেন দুর্দান্ত: এটি অল্প সময়ের জন্য অতিরিক্ত ট্র্যাফিক (burs of traffic - বাকেটের সাইজ পর্যন্ত) পারমিট বা অ্যালাউ করে, এবং একই সাথে দীর্ঘমেয়াদী গড়ের হার বা রেট (long-term average rate) বজায় রাখে। ১০ সাইজের বাকেট এবং ১/সেকেন্ড রিফিল রেট যুক্ত একজন ব্যবহারকারী তাৎক্ষণিকভাবে ১০টি রিকোয়েস্ট পাঠাতে পারেন, এবং এরপরে প্রতি সেকেন্ডে ১টি রিকোয়েস্ট পাঠাতে পারেন।

কারা ব্যবহার করে: Amazon, Stripe, এবং বেশিরভাগ ক্লাউড API।

▸ টোকেন বাকেট: টোকেন রিফিল হয়, রিকোয়েস্ট তা কনজিউম বা গ্রহণ করে

টোকেন বাকেটের ইমপ্লিমেন্টেশন

import time


class TokenBucket:
    def __init__(self, capacity: int, refill_rate: float):
        """
        capacity: Maximum number of tokens the bucket can hold
        refill_rate: Number of tokens added per second
        """
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self.last_refill = time.time()


    def _refill(self):
        now = time.time()
        elapsed = now - self.last_refill
        new_tokens = elapsed * self.refill_rate
        self.tokens = min(self.capacity, self.tokens + new_tokens)
        self.last_refill = now


    def allow_request(self) -> bool:
        self._refill()
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False




class SlidingWindowCounter:
    def __init__(self, max_requests: int, window_seconds: int):
        self.max_requests = max_requests
        self.window = window_seconds
        self.prev_count = 0
        self.curr_count = 0
        self.window_start = time.time()


    def allow_request(self) -> bool:
        now = time.time()
        elapsed = now - self.window_start


        # Slide the window if needed
        if elapsed >= self.window:
            self.prev_count = self.curr_count
            self.curr_count = 0
            self.window_start = now
            elapsed = 0


        # Weighted count: blend of previous and current window
        weight = 1 - (elapsed / self.window)
        estimated = self.prev_count * weight + self.curr_count


        if estimated < self.max_requests:
            self.curr_count += 1
            return True
        return False




# Demo: Token Bucket
bucket = TokenBucket(capacity=5, refill_rate=1)  # 5 burst, 1/sec steady
results = []
for i in range(8):
    results.append("OK" if bucket.allow_request() else "DENIED")
print(f"Rapid-fire 8 requests: {results}")
# First 5 succeed (bucket was full), next 3 are denied


time.sleep(2)  # Wait 2 seconds → 2 tokens refill
results = [bucket.allow_request() for _ in range(3)]
print(f"After 2s wait, 3 requests: {['OK' if r else 'DENIED' for r in results]}")
Output
Rapid-fire 8 requests: ['OK', 'OK', 'OK', 'OK', 'OK', 'DENIED', 'DENIED', 'DENIED']
After 2s wait, 3 requests: ['OK', 'OK', 'DENIED']

অ্যালগরিদম ২: লিকিং বাকেট (Leaking Bucket)

এটি টোকেন বাকেটের মতোই, তবে এটি একটি স্থির, কনস্ট্যান্ট রেটে রিকোয়েস্ট প্রসেস করে। নিচে ছিদ্র যুক্ত একটি বালতির কথা ভাবুন — আপনি যত দ্রুতই পানি ঢালুন না কেন, একটি নির্দিষ্ট স্থির হারেই তা থেকে পানি বের হবে।

  • রিকোয়েস্টগুলো একটি কিউ (queue) তে (অর্থাৎ বালতিতে) প্রবেশ করে।
  • রিকোয়েস্টগুলো একটি স্থির হারে (fixed rate) প্রসেস করা হয় (যেন পানি লিক হয়ে বের হচ্ছে)।
  • যদি কিউ বা বালতি পূর্ণ থাকে, তবে নতুন রিকোয়েস্টগুলো বাতিল বা ড্রপ হয়ে যায়।

টোকেন বাকেট থেকে পার্থক্য: টোকেন বাকেট বার্স্ট (bursts) বা হঠাৎ অনেক রিকোয়েস্ট একবারে অ্যালাউ করে (আপনি একবারে সব টোকেন ব্যবহার করতে পারেন)। লিকিং বাকেট একটি সম্পূর্ণ মসৃণ বা স্মুদ, ধ্রুব আউটপুট রেট (constant output rate) প্রয়োগ করে। এটি তখন সবচেয়ে বেশি উপযোগী যখন আপনার প্রেডিক্টেবল বা অনুমানযোগ্য, অবিচ্ছিন্ন প্রসেসিং প্রয়োজন হয় — যেমন ইমেইল পাঠানো বা পেমেন্ট প্রসেস করা।

অ্যালগরিদম ৩: ফিক্সড উইন্ডো কাউন্টার (Fixed Window Counter)

এটি অত্যন্ত সহজ পদ্ধতি। সময়কে একটি নির্দিষ্ট উইন্ডোতে (যেমন, প্রতি মিনিটে) ভাগ করা হয় এবং বর্তমান উইন্ডোতে কতটা রিকোয়েস্ট এসেছে তা গণনা করা হয়। যদি গণনা নির্দিষ্ট সীমা ছাড়ায়, তবে রিকোয়েস্ট বাতিল করা হয়।

  • উইন্ডো: ১২:০০:০০ – ১২:০০:৫৯ → ম্যাক্স বা সর্বোচ্চ ১০০টি রিকোয়েস্ট
  • কাউন্টার: ০, ১, ২, ... ১০০ → ১২:০১:০০ পর্যন্ত বাকি সব কিছু বাতিল করুন

সমস্যা: বাউন্ডারি স্পাইক (Boundary spikes) এর অন্যতম প্রধান সমস্যা। যদি একজন ব্যবহারকারী ১২:০০:৫৯ টায় ১০০টি রিকোয়েস্ট পাঠায় এবং ১২:০১:০০ টায় আরও ১০০টি পাঠায়, তবে সে ২ সেকেন্ডে মোট ২০০টি রিকোয়েস্ট পাঠিয়েছে — যা নির্ধারিত হারের দ্বিগুণ! যদিও প্রতিটি উইন্ডোর ভেতরে এটি ঠিক মনে হয়, তবে বাউন্ডারির ফাঁকফোকর দিয়ে এক সাথে প্রচুর রিকোয়েস্ট চলে আসে। এটি ফিক্সড উইন্ডোর সবচেয়ে বড় দুর্বলতা।

▸ স্লাইডিং উইন্ডো: একটি চলমান সময়ের উইন্ডোতে রিকোয়েস্ট কাউন্ট করা

অ্যালগরিদম ৪: স্লাইডিং উইন্ডো (Sliding Window)

এটি মূলত ফিক্সড উইন্ডোর বাউন্ডারি সমস্যাটি সমাধান করে। এর দুটি প্রকারভেদ বা রূপ রয়েছে:

স্লাইডিং উইন্ডো লগ (Sliding Window Log): এটি মূলত সকল রিকোয়েস্টের টাইমস্ট্যাম্পের (timestamps) একটি স্টোর করা লগ হিসেবে কাজ করে। প্রতিটি নতুন রিকোয়েস্টের জন্য উইন্ডোর বাইরের পুরনো টাইমস্ট্যাম্পগুলো মুছে ফেলা হয় এবং অবশিষ্টগুলো গণনা করা হয়। যদি এই গগণা নির্দিষ্ট সীমার নিচে থাকে, তবে রিকোয়েস্ট অ্যালাউ করা হয়। এটি বেশ সঠিক হলেও মেমোরির প্রচুর বা ভারী ব্যবহার করে — কারণ আপনাকে প্রতিটি টাইমস্ট্যাম্প স্টোর করে রাখতে হয়।

স্লাইডিং উইন্ডো কাউন্টার (Sliding Window Counter): এটি মূলত একটি হাইব্রিড বা মিশ্র পদ্ধতি। এটি পূর্ববর্তী উইন্ডো এবং বর্তমান উইন্ডোর কাউন্ট বা গণনা ধরে রাখে। একটি ওয়েটেড এভারেজ বা গড় পদ্ধতি ব্যবহার করে বর্তমান রেট অনুমান করা হয়: estimated = prev_count × overlap_ratio + curr_count। এটি একটি অনুমান নির্ভর হিসাব হলেও খুব কম মেমরি ব্যবহার করে এবং রেডিজ (Redis) এর মাধ্যমে বাউন্ডারির সমস্যা খুব দারুণভাবে সমাধান করতে পারে।

স্লাইডিং উইন্ডো কাউন্টার বেশিরভাগ সিস্টেমের জন্য একটি দুর্দান্ত ব্যালেন্স প্রদান করে — এটি যথেষ্ট সঠিক, কম মেমোরি ব্যবহার করে এবং খুব সহজেই ইমপ্লিমেন্ট বা প্রয়োগ করা যায়।

Note: সাক্ষাৎকারের জন্য একটি কুইক চিট-শিট (Cheat sheet): টোকেন বাকেট = সবচেয়ে জনপ্রিয়, বার্স্ট ট্রাফিকের জন্য অ্যালাউ করে, AWS/Stripe ব্যবহার করে। লিকিং বাকেট = ধ্রুবক আউটপুট রেট, অবিচ্ছিন্ন প্রসেসিং এর জন্য ভালো। ফিক্সড উইন্ডো = খুব সহজ কিন্তু এর বাউন্টারি স্পাইক ইসু রয়েছে। স্লাইডিং উইন্ডো = নির্ভুলতার দিক থেকে সেরা, একটু জটিল। আলোচনার সময় ৪ টির কথাই মাথায় রাখবেন তবে ডিজাইন ডিসকাশনে (design discussion) সাধারণত ডিফল্ট হিসেবে টোকেন বাকেটকে বেছে নিতে পারেন।

ডিস্ট্রিবিউটেড রেট লিমিটিং (Distributed Rate Limiting)

উপরের অ্যালগরিদমগুলো একটি মাত্র সার্ভারে দারুণভাবে কাজ করে। কিন্তু যদি একটি লোড ব্যালান্সারের পেছনে ১০টি API সার্ভার থাকে, তখন কী করবেন? প্রতিটি সার্ভারের নিজস্ব কাউন্টার থাকে — একজন ব্যবহারকারী ১০টি সার্ভারে নক (hit) করে তার রেট লিমিট ১০ গুণ বাড়িয়ে নিতে পারে!

সমাধান:

সেন্ট্রালাইজড স্টোর (Redis): সকল সার্ভার Redis-এর মতো সেন্ট্রাল ডেটাবেসে থাকা একই কাউন্টার চেক এবং আপডেট করে। রেস কন্ডিশন (race conditions) এড়াতে Redis-এর অ্যাটমিক অপারেশন (INCR, EXPIRE) ব্যবহার করুন। এটি সবচেয়ে কমন বা সাধারণ একটি অ্যাপ্রোচ।

স্টিকি সেশন (Sticky sessions): প্রতিটি ব্যবহারকারীকে একটি নির্দিষ্ট সার্ভারে রাউট (IP হ্যাশের মাধ্যমে) করুন। এতে লোকাল রেট লিমিটিং ভালোভাবে কাজ করে। তবে এটি লোড ব্যালান্সারের ফ্লেক্সিবিলিটি কমিয়ে দেয় এবং SPOF (Single Point of Failure) তৈরি করতে পারে।

লোড ব্যালান্সার/গেটওয়েতে রেট লিমিট: মূল সার্ভারে রিকোয়েস্ট যাওয়ার আগে রেট লিমিটার বসান। Nginx, Kong, এবং AWS API Gateway-র মতো টুলে শেয়ার্ড স্টেটসহ বিল্ট-ইন রেট লিমিটার থাকে।

অ্যাটমিক রেট লিমিটিং-এর জন্য Redis স্ক্রিপ্ট:

Redis-এ একটি Lua স্ক্রিপ্ট ব্যবহার করে পারমাণবিকভাবে বা অ্যাটমিকভাবে চেক-এবং-ইনক্রিমেন্ট (check-and-increment) করুন। এটি রেস কন্ডিশন এড়ায়, যেখানে দুটি সার্ভার একসাথে কাউন্ট ৯৯ (যা লিমিট ১০০-এর কম) রিড করতে পারে এবং উভয়ই তাদের রিকোয়েস্ট অ্যালাউ বা অনুমতি দিতে পারে।

▸ গ্রহণ করুন অথবা বাতিল করুন: HTTP 429 (Too Many Requests)

HTTP 429 রেসপন্স

যখন কোনো রিকোয়েস্ট রেট লিমিট করে দেওয়া হয়, তখন নিচের প্রয়োজনীয় হেডারসহ একটি 429 Too Many Requests রিটার্ন করুন:

  • X-RateLimit-Limit: 100 — একটি নির্দিষ্ট উইন্ডোতে সর্বোচ্চ অনুমোদিত রিকোয়েস্টের সংখ্যা।
  • X-RateLimit-Remaining: 0 — আপনার আর কতগুলো রিকোয়েস্ট বাকি আছে।
  • X-RateLimit-Reset: 1640000060 — উইন্ডোটি কখন রিসেট হবে (Unix Timestamp অনুযায়ী)।
  • Retry-After: 30 — কত সেকেন্ড অপেক্ষা করার পর আবার চেষ্টা করা যাবে।

একটি ভালো রেট লিমিটার রেসপন্স তথ্যাবহুল হওয়া উচিত, শাস্তিমূলক নয়। তারা ক্লায়েন্টদের ঠিক কীরকম আচরণ করতে হবে তা বলে দেয়। এটি অপ্রয়োজনীয় রিট্রাই স্ট্রম বা ক্রমাগত পুনরায় চেষ্টার প্রবণতাকে কমিয়ে দেয় এবং আপনার API-কে আরও বেশি ডেভেলপার-বান্ধব করে তোলে।

▸ Redis এর মাধ্যমে ডিস্ট্রিবিউটেড রেট লিমিটিং
Note: সাক্ষাৎকারের টিপস: একটি রেট লিমিটার ডিজাইন করার সময় এর বিভিন্ন ক্ষেত্রগুলো উল্লেখ করুন: যেমন প্রতি ইউজার (per-user), প্রতি আইপি (per-IP), প্রতি এপিআই-কী (per-API-key), অথবা গ্লোবাল (global)। একটি ভালোভাবে ডিজাইন করা সিস্টেমে একাধিক লেয়ার বা স্তর থাকে — ইনফ্রাস্ট্রাকচার রক্ষা করতে গ্লোবাল লিমিট, ফেয়ারনেস বা ন্যায্যতা নিশ্চিত করতে প্রতি-ইউজার বা পার-ইউজার লিমিট, এবং দামি অপারেশনগুলোর জন্য (যেমন ইমেইল পাঠানো) পার-এন্ডপয়েন্ট লিমিট।

Key Metrics

টোকেন বাকেট (check)
কনস্ট্যান্ট বা স্থির সময়, কনস্ট্যান্ট জায়গা
\(O(1)\) \(O(1)\)
লিকিং বাকেট (check)
কিউ চেক
\(O(1)\) \(O(1)\)
ফিক্সড উইন্ডো কাউন্টার
জনপ্রতি বা প্রতি উইন্ডো হিসেবে সিঙ্গেল কাউন্টার
\(O(1)\) \(O(1)\)
স্লাইডিং উইন্ডো লগ
n = উইন্ডোতে রিকোয়েস্টের সংখ্যা; হাই মেমোরি কনজিউম করে
\(O(n)\) \(O(n)\)
স্লাইডিং উইন্ডো কাউন্টার
২ টি কাউন্টারের ওয়েটেড গড়
\(O(1)\) \(O(1)\)
Redis INCR + EXPIRE
অ্যাটমিক ডিস্ট্রিবিউটেড কাউন্টার
~০.১-০.৫ ms \(O(1)\)

ছোট কুইজ

একটি টোকেন বাকেটের ধারণক্ষমতা বা ক্যাপাসিটি ১০ জন এবং রিফিল হার সেকেন্ড প্রতি ২ টোকেন। এটি বেশ দীর্ঘ সময় ধরে অব্যবহৃত ছিল বা আইডল পড়ে ছিল। এখন তাৎক্ষণিকভাবে কতগুলো রিকোয়েস্ট পাঠানো যাবে?

পড়া চালিয়ে যান