রেট লিমিটিং অ্যালগরিদম (Rate Limiting Algorithms)
রেট লিমিটিং বিভিন্ন অ্যালগরিদম ব্যবহার করে প্রয়োগ করা সম্ভব। যদিও এই গাইডটি প্রতিটি অ্যালগরিদমের বিস্তারিত ব্যাখ্যায় যাবে না, তবে উচ্চ-স্তরে এগুলো বোঝা আপনাকে সঠিক অ্যালগরিদম নির্বাচন করতে সাহায্য করবে। নিচে জনপ্রিয় অ্যালগরিদমগুলোর তালিকা দেওয়া হলো:
- টোকেন বাকেট (Token bucket)
- লিকিং বাকেট (Leaking bucket)
- ফিক্সড উইন্ডো কাউন্টার (Fixed window counter)
- স্লাইডিং উইন্ডো লগ (Sliding window log)
- স্লাইডিং উইন্ডো কাউন্টার (Sliding window counter)
টোকেন বাকেট অ্যালগরিদম (Token Bucket Algorithm)
টোকেন বাকেট অ্যালগরিদম ব্যাপকভাবে ব্যবহৃত হয় এবং বড় কোম্পানিগুলো সাধারণত এটি তাদের রেট লিমিটিং-এ ব্যবহার করে।
এটি কীভাবে কাজ করে তা নিচে ব্যাখ্যা করা হলো:
- একটি টোকেন বাকেট (token bucket) হলো একটি কন্টেইনার যার একটি পূর্বনির্ধারিত ক্ষমতা (capacity) রয়েছে।
- নির্দিষ্ট সময় পর পর বাকেটে টোকেন যোগ করা হয়।
- বাকেট পূর্ণ হয়ে গেলে অতিরিক্ত টোকেন বাতিল (discard) হয়ে যায়।
চিত্র ৪ (Figure 4) — বাকেট পূর্ণ হলে নতুন টোকেন বাদ পড়ে যায় (discarded)।
প্রতিটি রিকোয়েস্ট একটি করে টোকেন ব্যবহার করে। রিকোয়েস্ট আসলে:
- পর্যাপ্ত টোকেন থাকলে → টোকেন সরিয়ে রিকোয়েস্ট পাস করা হয়
- পর্যাপ্ত টোকেন না থাকলে → রিকোয়েস্ট বাদ দেওয়া হয় (dropped)
টোকেন বাকেটের প্যারামিটার:
- Bucket size: সর্বোচ্চ কতটি টোকেন থাকতে পারবে
- Refill rate: প্রতি সেকেন্ডে কতটি টোকেন যোগ হবে
কতগুলো বাকেট থাকবে? — এটি রেট লিমিটিং রুলের ওপর নির্ভর করে:
চিত্র ৫ (Figure 5) — বিভিন্ন ক্লায়েন্টের জন্য আলাদা আলাদা টোকেন বাকেট।
সুবিধা:
- সহজে বোঝা ও প্রয়োগ করা যায়
- মেমোরি দক্ষ (memory efficient)
- ট্রাফিকের হঠাৎ বৃদ্ধি (burst of traffic) সামলাতে পারে
অসুবিধা:
- bucket size এবং refill rate — এই দুটি প্যারামিটার সঠিকভাবে টিউন করা কঠিন হতে পারে।
লিকিং বাকেট অ্যালগরিদম (Leaking Bucket Algorithm)
লিকিং বাকেট অ্যালগরিদম টোকেন বাকেটের মতোই, তবে রিকোয়েস্টগুলো একটি নির্দিষ্ট হারে প্রক্রিয়া করা হয়। এটি সাধারণত একটি FIFO (First In First Out) কিউ (queue) ব্যবহার করে।
চিত্র ৬ (Figure 6) — লিকিং বাকেট: রিকোয়েস্ট কিউতে জমা হয়, নির্দিষ্ট হারে প্রক্রিয়া হয়।
প্যারামিটার:
- Bucket size: কিউর সর্বোচ্চ আকার
- Outflow rate: প্রতি সেকেন্ডে কতটি রিকোয়েস্ট প্রক্রিয়া হবে
সুবিধা:
- আউটফ্লো রেট স্থির থাকায় স্থিতিশীল আউটফ্লো নিশ্চিত হয়
- মেমোরি দক্ষ
অসুবিধা:
- ট্রাফিক বার্স্টের সময় পুরনো রিকোয়েস্টগুলো কিউ ভরে ফেলে এবং নতুনগুলো রেট লিমিট হয়ে যায়
- দুটি প্যারামিটার সঠিকভাবে টিউন করা কঠিন
ফিক্সড উইন্ডো কাউন্টার (Fixed Window Counter)
এই অ্যালগরিদমটি টাইমলাইনকে নির্দিষ্ট আকারের সময় উইন্ডোতে (time window) ভাগ করে এবং প্রতিটি উইন্ডোর জন্য একটি কাউন্টার রাখে।
চিত্র ৭ (Figure 7) — সার্ভারগুলোর মধ্যে রেট লিমিট কাউন্টার শেয়ার করার চ্যালেঞ্জ।
চিত্র ৮ (Figure 8) — কাউন্টার রিসেটের আগে ও পরে অবস্থা।
চিত্র ৯ (Figure 9) — ফিক্সড উইন্ডোতে রিকোয়েস্ট কাউন্ট।
সুবিধা:
- মেমোরি দক্ষ
- বোঝা ও প্রয়োগ করা সহজ
- নির্দিষ্ট উইন্ডোর শেষে কাউন্টার রিসেট করা স্বাভাবিক ব্যবহারের উপযুক্ত
অসুবিধা:
- উইন্ডোর প্রান্তে ট্রাফিকের বার্স্ট কোটার চেয়ে বেশি রিকোয়েস্ট পাঠাতে পারে
স্লাইডিং উইন্ডো লগ (Sliding Window Log)
ফিক্সড উইন্ডো কাউন্টার অ্যালগরিদমের সমস্যা সমাধান করে স্লাইডিং উইন্ডো লগ অ্যালগরিদম।
চিত্র ১০ (Figure 10) — টাইমস্ট্যাম্প লগ ব্যবহার করে রিকোয়েস্ট ট্র্যাকিং।
কীভাবে কাজ করে:
- রিকোয়েস্টের টাইমস্ট্যাম্প (timestamp) একটি কেশড (cache) লগে সংরক্ষণ করা হয়
- নতুন রিকোয়েস্ট আসলে পুরনো টাইমস্ট্যাম্পগুলো সরিয়ে ফেলা হয়
- লগের সাইজ অনুযায়ী রিকোয়েস্ট অনুমতি দেওয়া বা বাতিল করা হয়
সুবিধা:
- রেট লিমিটিং অত্যন্ত নির্ভুল
অসুবিধা:
- প্রচুর মেমোরি ব্যবহার করে, কারণ প্রত্যাখ্যাত (rejected) রিকোয়েস্টের টাইমস্ট্যাম্পও সংরক্ষণ করতে হয়
স্লাইডিং উইন্ডো কাউন্টার (Sliding Window Counter)
এই অ্যালগরিদম ফিক্সড উইন্ডো কাউন্টার এবং স্লাইডিং উইন্ডো লগ উভয়ের সমন্বয়।
চিত্র ১১ (Figure 11) — রোলিং উইন্ডোতে আগের মিনিট (৭০%) ও বর্তমান মিনিট (৩০%) মিলিয়ে গণনা।
সুবিধা:
- মেমোরি দক্ষ
- ট্রাফিক স্পাইক (spike) মসৃণ করে
- তুলনামূলকভাবে নির্ভুল
অসুবিধা:
- শুধুমাত্র আনুমানিক (approximate) গণনা কারণ এটি ধরে নেয় আগের উইন্ডোতে রিকোয়েস্ট সমানভাবে বিতরণ হয়েছিল।
উচ্চ-স্তরের আর্কিটেকচার (High-level Architecture)
রেট লিমিটিং অ্যালগরিদমের মূল প্রশ্ন হলো: কাউন্টার কোথায় রাখব? ডাটাবেসে রাখা ঠিক নয় কারণ ডিস্ক অ্যাক্সেস ধীর। আমরা ইন-মেমোরি ক্যাশ (in-memory cache) ব্যবহার করি কারণ এটি দ্রুত এবং টাইম-বেসড এক্সপায়ারেশন পলিসি সাপোর্ট করে। Redis হলো রেট লিমিটিং-এর জন্য একটি জনপ্রিয় বিকল্প।