রেট লিমিটিং অ্যালগরিদম

১ · সমস্যা — কেন প্রতিটি প্রোডাকশন সিস্টেমে রেট লিমিটিং দরকার

একটি পাবলিক API যদি ক্লায়েন্টদের রিকোয়েস্ট হারে কোনো সীমা না রাখে, তাহলে একটি একক buggy স্ক্রিপ্ট বা ম্যালিশিয়াস ক্লায়েন্ট প্রতি সেকেন্ডে হাজার হাজার রিকোয়েস্ট পাঠিয়ে পুরো সার্ভিসকে অন্য সব ইউজারের জন্য ধীর বা অচল করে দিতে পারে। রেট লিমিটিংRate Limitingএকটি নির্দিষ্ট সময়সীমার মধ্যে একটি ক্লায়েন্ট বা ইউজার সর্বোচ্চ কতগুলো রিকোয়েস্ট করতে পারবে তা সীমিত করার কৌশল — সীমা অতিক্রম করলে অতিরিক্ত রিকোয়েস্ট প্রত্যাখ্যান বা বিলম্বিত করা হয়। এই সমস্যার সমাধান দেয় — প্রতিটি ক্লায়েন্টের জন্য একটি ন্যায্য সীমা বেঁধে দিয়ে, বাকি সবার জন্য সিস্টেমটিকে সুস্থিত রাখা।

২ · Token Bucket — বার্স্ট অনুমোদনকারী সবচেয়ে জনপ্রিয় অ্যালগরিদম

Token Bucket-এ একটি বাকেট থাকে যাতে সর্বোচ্চ capacity-টি টোকেন ধরে, এবং একটি ফিক্সড হারে (refill_rate, প্রতি সেকেন্ডে) নতুন টোকেন যোগ হতে থাকে (ধারণক্ষমতা পর্যন্ত)। প্রতিটি রিকোয়েস্ট ১টি টোকেন খরচ করে; বাকেট খালি হলে রিকোয়েস্ট প্রত্যাখ্যাত বা বিলম্বিত হয়।

৩ · Leaky Bucket — আউটপুট স্মুথিং

Leaky Bucket-এ রিকোয়েস্ট একটি কিউতে জমা হয় এবং সবসময় একটি স্থির হারে "লিক" করে বের হয় (প্রসেস হয়) — ইনপুটে যতই বার্স্ট আসুক না কেন। এটি Token Bucket-এর ঠিক বিপরীত দর্শন —

৪ · Fixed Window Counter ও তার বাউন্ডারি সমস্যা

Fixed Window Counter সবচেয়ে সহজ — প্রতিটি ফিক্সড সময় উইন্ডোতে (যেমন প্রতি মিনিট) একটি কাউন্টার রাখা হয়, উইন্ডো শেষে রিসেট হয়। সমস্যা — একটি উইন্ডোর একদম শেষে পুরো সীমার সমান রিকোয়েস্ট এবং পরের উইন্ডোর একদম শুরুতে আবার পুরো সীমার সমান রিকোয়েস্ট এলে, এই দুই উইন্ডোর সংযোগস্থলে অল্প সময়ের মধ্যেই কার্যত ~২x রেট পার হয়ে যেতে পারে — যদিও কোনো একটি উইন্ডোই একা তার সীমা ভাঙেনি।

Sliding Window (লগ বা কাউন্টার-ভিত্তিক) এই সমস্যা সমাধান করে ফিক্সড বাউন্ডারির বদলে একটি চলমান সময়-উইন্ডো (যেমন "গত ৬০ সেকেন্ড") ট্র্যাক করে — অতিরিক্ত মেমরি/গণনার খরচে, তবে বাউন্ডারি-বার্স্ট সমস্যা থাকে না।

৫ · Python-এ একটি সম্পূর্ণ Token Bucket

নিচের কোডে একটি TokenBucket ক্লাস আছে যার allow_request(current_time) মেথড প্রথমে অতিবাহিত সময় অনুযায়ী টোকেন রিফিল করে (ধারণক্ষমতা পর্যন্ত), তারপর টোকেন থাকলে একটি খরচ করে True রিটার্ন করে, না থাকলে False। বাস্তব সময়ের বদলে এক্সপ্লিসিট টাইমস্ট্যাম্প ব্যবহার করা হয়েছে যাতে ফলাফল সম্পূর্ণ ডিটারমিনিস্টিক হয়।

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity          # বাকেটে সর্বোচ্চ কতগুলো টোকেন থাকতে পারে
        self.refill_rate = refill_rate    # প্রতি সেকেন্ডে কতগুলো টোকেন যোগ হয়
        self.tokens = capacity            # শুরুতে বাকেট পূর্ণ
        self.last_check = 0.0             # শেষবার রিফিল করা হয়েছিল কখন

    def allow_request(self, current_time):
        elapsed = current_time - self.last_check
        refill = elapsed * self.refill_rate
        self.tokens = min(self.capacity, self.tokens + refill)
        self.last_check = current_time

        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

bucket = TokenBucket(capacity=5, refill_rate=1)   # ৫ টোকেন ধারণক্ষমতা, প্রতি সেকেন্ডে ১টি রিফিল

# পর্যায় ১: t=0 সময়ে ৭টি রিকোয়েস্ট একসাথে (burst) — বাকেটে মাত্র ৫টি টোকেন আছে
print("পর্যায় ১ — t=0 তে বার্স্ট (৭টি রিকোয়েস্ট):")
for i in range(7):
    allowed = bucket.allow_request(current_time=0)
    print(f"  রিকোয়েস্ট {i+1}: {'ALLOWED' if allowed else 'DENIED'} (tokens বাকি ≈ {bucket.tokens:.1f})")

# পর্যায় ২: ৩ সেকেন্ড অপেক্ষা (৩টি টোকেন রিফিল হবে)
print("\nপর্যায় ২ — t=3 (৩ সেকেন্ড অপেক্ষার পর, ৩টি রিকোয়েস্ট):")
for i in range(3):
    allowed = bucket.allow_request(current_time=3)
    print(f"  রিকোয়েস্ট {i+1}: {'ALLOWED' if allowed else 'DENIED'} (tokens বাকি ≈ {bucket.tokens:.1f})")

# পর্যায় ৩: t=3 তেই আরেকটি বার্স্ট — টোকেন প্রায় শেষ হয়ে যাবে
print("\nপর্যায় ৩ — t=3 তেই আরও ৩টি রিকোয়েস্ট (একই মুহূর্তে, নতুন রিফিল নেই):")
for i in range(3):
    allowed = bucket.allow_request(current_time=3)
    print(f"  রিকোয়েস্ট {i+1}: {'ALLOWED' if allowed else 'DENIED'} (tokens বাকি ≈ {bucket.tokens:.1f})")