Rate Limit एल्गोरिद्म को विज़ुअलाइज़ करके समझें

Rate Limit (उपयोग सीमा) की ज़रूरत क्यों होती है?

• अगर बहुत सारे प्रतिभागियों वाले Twitch चैट में एक स्पैमर हो, तो उपयोग सीमा न होने पर वह स्पैमर पूरी बातचीत पर हावी हो सकता है।
• उपयोग सीमा के ज़रिए हर उपयोगकर्ता को निष्पक्ष रूप से भाग लेने का मौका मिल सकता है।
• Rate Limiter (उपयोग सीमा नियंत्रक) किसी निश्चित अवधि में तय सीमा से अधिक अनुरोधों को रोककर सेवा के ट्रैफ़िक को नियंत्रित करता है। यह चैट में स्पैम नियंत्रण के अलावा भी उपयोगी है।
• उदाहरण के लिए, login form में उपयोग सीमा के माध्यम से brute force attack को रोका जा सकता है, जबकि कम संख्या में गलत अनुमान की अनुमति दी जा सकती है।
• API endpoint पर भी अक्सर उपयोग सीमा लागू की जाती है ताकि कोई एक उपयोगकर्ता संसाधनों पर एकाधिकार न कर सके।
  • अगर किसी उपयोगकर्ता को किसी महंगे API endpoint को प्रति मिनट केवल 100 बार कॉल करने की अनुमति दी जाए, तो counter का उपयोग करके प्रति मिनट 100 hits को ट्रैक किया जाता है, और उसके बाद के अनुरोध ब्लॉक कर दिए जाते हैं।
  • यह सबसे सरल उपयोग सीमा एल्गोरिद्म में से एक, Fixed Window Limiter, है।
  • यह सेवा ट्रैफ़िक को नियंत्रित करने का एक सामान्य तरीका है।

Fixed windows एल्गोरिद्म

• एक निश्चित समय window के भीतर अनुरोधों की संख्या सीमित की जाती है।
• हर समय window की शुरुआत में अनुरोध counter को 0 पर reset कर दिया जाता है।
• फायदे
  • इसे लागू करना और समझना आसान है।
  • यह उपयोगकर्ताओं के लिए पूर्वानुमेय है।
• नुकसान
  • अगर किसी window के अंत के करीब अनुरोध शुरू हों, तो सीमा से अधिकतम 2 गुना तक burst की अनुमति मिल सकती है।
• वास्तविक उदाहरण: GitHub API प्रति घंटे 5,000 अनुरोधों की अनुमति देने वाला fixed time window rate limiter इस्तेमाल करता है।
• समय window की शुरुआत को स्थिर अंतराल पर तय करने के बजाय, हर समय window उस window के भीतर उपयोगकर्ता के पहले अनुरोध के समय बनाई जा सकती है।
• इस तरीके में उपयोगकर्ता को अगली समय window तक बचा समय बताना विशेष रूप से महत्वपूर्ण होता है।

Sliding windows एल्गोरिद्म

• सारी capacity को एक साथ फिर से भरने के बजाय, sliding window एक बार में एक अनुरोध के हिसाब से capacity भरती है।
• फायदे
  • यह अनुरोध ट्रैफ़िक के वितरण को अधिक smooth बनाता है।
  • यह उच्च लोड के लिए उपयुक्त है।
• नुकसान
  • यह fixed time window की तुलना में उपयोगकर्ताओं के लिए कम पूर्वानुमेय है।
  • हर अनुरोध का timestamp स्टोर करना resource-intensive है।
• क्योंकि sliding window उच्च ट्रैफ़िक परिदृश्यों में सबसे अधिक उपयोगी है, इसलिए मूल एल्गोरिद्म का resource-intensive होना उल्टा असर डालता है।
• इसलिए अधिकांश वास्तविक sliding window rate limiter approximation का उपयोग करते हैं।
• approximation पिछले fixed time window में अनुमत अनुरोधों की संख्या और वर्तमान fixed time window में अनुमत अनुरोधों की संख्या की गणना करता है, और पिछले window के अनुमत अनुरोधों को वर्तमान समय पर समाप्त होने वाली floating time window के overlap के अनुपात में weight देता है।
• यह approximation अनुरोधों को लगभग समान अनुपात में सीमित करता है, लेकिन कहीं अधिक efficient है।
• वास्तविक उदाहरण: Cloudflare का configurable rate limiter approximate sliding window का उपयोग करता है।

Token buckets एल्गोरिद्म

• समय window की अवधि के बजाय, एक ऐसे bucket की कल्पना की जाती है जो एक निश्चित दर से "tokens" से भरता है।
• हर अनुरोध इस bucket से एक token निकालता है, और bucket खाली होने पर अगला अनुरोध ब्लॉक हो जाता है।
• bucket की capacity उन अधिकतम अनुरोधों को दर्शाती है जिन्हें burst के रूप में support किया जा सकता है।
• refill interval दीर्घकालिक औसत अनुमत अनुरोध अंतराल को दर्शाता है।
• इस एल्गोरिद्म का एक मुख्य लाभ यह है कि कई rate limiter के बिना भी अलग-अलग burst और average capacity रखी जा सकती है।
• फायदे
  • यह उच्च ट्रैफ़िक burst की अनुमति देता है, लेकिन दीर्घकालिक औसत अनुरोध दर लागू करता है।
  • यह उपयोगकर्ताओं के लिए अधिक लचीला है क्योंकि यह अनुमत सीमा के भीतर ट्रैफ़िक स्पाइक की अनुमति देता है।
• नुकसान
  • fixed time window की तुलना में उपयोगकर्ताओं को सीमाएँ और refill time समझाना अधिक कठिन है।
• वास्तविक उदाहरण
  • Stripe प्रति उपयोगकर्ता 500 की सीमा और 0.01 सेकंड के refill interval वाला token bucket उपयोग करता है, जिससे लगातार प्रति सेकंड 100 अनुरोधों की अनुमति मिलती है, लेकिन अधिकतम 500 अनुरोधों तक burst की अनुमति होती है।
  • OpenAI का GPT-3.5 free tier 200 की सीमा और 86400 सेकंड/200 के refill interval वाला token bucket उपयोग करता है, जिससे यह प्रति दिन 200 अनुरोधों तक सीमित रहता है।

Rate limit लागू करते समय ध्यान देने योग्य बातें

• rate limiter के लिए persistent storage बनाना चाहिए।
• अगर persistent storage से सर्वर का कनेक्शन विफल हो जाए, तो अनुरोधों को ब्लॉक करने के बजाय सभी को अनुमति देनी चाहिए।
• वैकल्पिक रूप से burst ट्रैफ़िक को नियंत्रित किया जा सकता है।
• उचित key चुननी चाहिए (user ID, API key आदि)।
• उपयोगी rate limit errors दिखाने चाहिए (अगले अनुरोध तक प्रतीक्षा समय, 429 HTTP status code, x-ratelimit-* response headers आदि)।

[humblebee]

कोरियाई में संक्षेपित लेख पढ़कर मैंने सोचा, 'ठीक है, समझ तो आ गया, लेकिन क्या सब एक ही बात नहीं है?' लेकिन जब मैंने मूल लिंक का लेख पढ़ा, तो वह सचमुच बहुत अच्छी तरह समझाया गया है और उसकी visualization भी बेहद संतोषजनक है! 👍👍👍

[GN⁺]

Hacker News राय

Hacker News टिप्पणियों का संक्षिप्त सार

• लंबे अनुभव से मिली अतिरिक्त बातें:

  • Rate Limits: यह backend capacity की समस्या हल नहीं करते। इन्हें policy-based limitation के रूप में देखना चाहिए।
  • Bad Traffic: सिर्फ़ rate limits के अलावा अतिरिक्त उपायों पर भी विचार करना चाहिए। authentication status, user/session priority आदि के आधार पर traffic को प्राथमिकता देना उपयोगी है।
  • Communication: जब महत्वपूर्ण ग्राहक या internal teams rate limits तक पहुँच जाएँ, तब उसके लिए response plan तैयार होना चाहिए।
  • Concertina Effects: सभी fixed windows या कई sliding windows के एक साथ expire होने से बचाने के लिए हर user/session window में deterministic offset जोड़ना चाहिए।

• multi-tenant environment में DoS attacks रोकने के लिए fair queuing सबसे अच्छा approach है: हर client को उसकी अपनी queue दी जाती है, और background routine हर queue पर बारी-बारी से घूमकर requests process करती है। spam requests भेजने वाला client सिर्फ़ अपनी ही queue को congest करता है।

• client handling code implement करने का अनुभव: rate limit तक पहुँचने पर सबसे अच्छा backoff strategy क्या हो, यह हमेशा जिज्ञासा का विषय रहा। service perspective से trade-offs पढ़ना दिलचस्प लगा।

• बधाई संदेश: छोटे कंटेंट के लिए यह सबसे बेहतरीन visualization है, बहुत जानकारीपूर्ण है और मुख्य बिंदु बहुत अच्छी तरह व्यवस्थित हैं।

• GCRA algorithm: इसे rate limiting के लिए बेहतर algorithm माना गया। काश यह और ज़्यादा जाना-पहचाना और इस्तेमाल किया जाता।

  • GCRA implementation example
  • GCRA Wikipedia

• शानदार काम: महसूस होता है कि इस पोस्ट में बहुत समय और मेहनत लगी है। बहुत अच्छा।

• AWS Lambda में rate-limiting की समस्या: NodeJS में rate-limiting लागू करने की कोशिश की गई, लेकिन AWS Lambda में timers अजीब तरह से काम करते थे, जिससे लक्ष्य सीमा पार हो जाती थी। local tests में पास हुआ, लेकिन Lambda में विफल रहा। यह timer issue था या library issue, यह स्पष्ट नहीं था।

• जब rate limiting layer saturation में हो तो क्या करें: CF के अलावा कोई और विकल्प है या नहीं, यह जानने की जिज्ञासा थी। छोटे VPS पर DoS attacks से बचाव में nftable rules कितने प्रभावी हैं, यह भी प्रश्न था।

• ऐसे मौके जब इस resource की ज़रूरत थी: करियर में कई बार ऐसी resource की ज़रूरत पड़ी थी। अब इसके मौजूद होने से खुशी है।

• data visualization के प्रशंसक: यह जानने की जिज्ञासा थी कि क्या D3 इस्तेमाल किया गया है।