प्रॉम्प्ट और दायरा
प्रति-उपयोगकर्ता टोकन-बकेट रेट लिमिटर लागू करें। प्रत्येक बकेट में अधिकतम capacity, प्रति सेकंड refillRate की रिफिल दर और एक वर्तमान टोकन बैलेंस होता है। एक अनुरोध में उपयोगकर्ता आईडी, टाइमस्टैम्प और लागत शामिल होती है। यदि रिफिल किया गया बैलेंस लागत को पूरा करता है, तो इसे उपभोग करें और अनुरोध की अनुमति दें; अन्यथा इसे अस्वीकार करें। API, जटिलता, समय की सटीकता, कॉनकरेंसी और परीक्षणों की व्याख्या करें।
यह बैकएंड, प्लेटफ़ॉर्म और इंफ्रास्ट्रक्चर कोडिंग इंटरव्यू के लिए उपयुक्त है। AWS टोकन बकेट का वर्णन अनुरोधों का प्रतिनिधित्व करने वाले टोकन के रूप में करता है, जो एक कॉन्फ़िगर की गई दर पर रिफिल होते हैं, जिसमें प्रति अनुरोध एक टोकन का उपभोग होता है, और सीमाओं को बढ़ाने से पहले उनका परीक्षण करने की सिफारिश करता है।
इंटरव्यूअर क्या मूल्यांकन करता है
- क्या आप प्रत्येक बकेट के लिए टाइमर शुरू करने के बजाय लेज़ी रिफिल (lazy refill) निकालते हैं।
- क्या आप मोनोटोनिक समय का उपयोग करते हैं ताकि वॉल-क्लॉक रोलबैक से टोकन न बन सकें।
- क्या टोकन पर सीमा (cap) लगाई गई है और अस्वीकृत अनुरोध बैलेंस को अप्रभावित छोड़ते हैं।
- क्या आप सिंगल-प्रोसेस मेमोरी और डिस्ट्रीब्यूटेड शेयर्ड स्टेट के बीच अंतर करते हैं।
- क्या आप कॉनकरेंसी, संख्यात्मक सटीकता, लंबे समय तक निष्क्रियता के अंतराल और अमान्य पैरामीटर को कवर करते हैं।
पहले पूछे जाने वाले स्पष्टीकरण
पुष्टि करें:
- क्या
costहमेशा एक धनात्मक पूर्णांक होता है, या यह भिन्नात्मक हो सकता है? - क्या नियतात्मक परीक्षणों के लिए समय इंजेक्ट किया जाता है, या लिमिटर द्वारा स्वयं पढ़ा जाता है?
- क्या सिंगल-प्रोसेस कार्यान्वयन पर्याप्त है, या उदाहरणों (instances) को कोटा साझा करना होगा?
- क्या अस्वीकृति में शेष टोकन या अनुमानित पुनर्श्याम (retry) समय शामिल होना चाहिए?
यदि अनिर्दिष्ट है, तो एक प्रोसेस, गैर-ऋणात्मक पूर्णांक लागत, एक नैनोसेकंड मोनोटोनिक क्लॉक, और बकेट क्षमता तक बर्स्ट की अनुमति मान लें।
तीस-सेकंड उत्तर ढांचा
प्रति उपयोगकर्ता tokens और lastRefillAt स्टोर करें। प्रत्येक अनुरोध पर, मोनोटोनिक बीते हुए समय का उपयोग करके min(capacity, tokens + elapsed * refillRate) के साथ लेज़ी रिफिल करें। केवल तभी अनुमति दें जब रिफिल किया गया बैलेंस cost को कवर करता हो; अन्यथा स्थिति को सुरक्षित रखें और अस्वीकार करें। एक प्रोसेस में, प्रति-उपयोगकर्ता लॉक या एटॉमिक क्रिटिकल सेक्शन पढ़ने, रिफिल करने, जांचने और लिखने को अविभाज्य बनाता है। एक डिस्ट्रीब्यूटेड परिनियोजन में, एक एटॉमिक शेयर्ड-स्टोर स्क्रिप्ट या लेनदेन में समान संक्रमण चलाएं। एक नियंत्रणीय-क्लॉक मॉडल परीक्षण के साथ पैरामीटर, क्लॉक व्यवहार, सीमाओं और समवर्ती कॉलों को मान्य करें।
चरण-दर-चरण गहन विश्लेषण
1. स्थिति और अपरिवर्तनीयता (Invariants)
प्रति उपयोगकर्ता tokens, lastRefillAt और वैकल्पिक रूप से एक संस्करण स्टोर करें। अपरिवर्तनीय नियम 0 <= tokens <= capacity है, और lastRefillAt कभी पीछे नहीं जाता है। निर्माण के समय सकारात्मक क्षमता और रिफिल दर को मान्य करें। लागत धनात्मक होनी चाहिए और क्षमता से अधिक नहीं होनी चाहिए; अन्यथा स्थिति को बदले बिना एक पैरामीटर त्रुटि लौटाएं।
2. लेज़ी रिफिल
मान लें कि now वर्तमान समय है और elapsed = now - lastRefillAt है। elapsed * refillRate जोड़ें, फिर बैलेंस को min(capacity, tokens + refill) के साथ सीमित (clamp) करें। भले ही बकेट भरा हो, lastRefillAt को now पर आगे बढ़ाएं ताकि अंतराल को दोबारा न गिना जाए। परिमेय अंकगणित (rational arithmetic) के साथ पूर्णांक नैनोसेकंड फ़्लोटिंग-पॉइंट ड्रिफ्ट को कम करते हैं; यदि फ़्लोट्स का उपयोग किया जाता है, तो राउंडिंग को परिभाषित करें और लंबे रन का परीक्षण करें।
3. अनुमति देना और अस्वीकार करना
यदि रिफिल किया गया बैलेंस कम से कम cost है, तो लागत घटाएं और अनुमति दें। अन्यथा कुछ भी न घटाएं; अस्वीकृति लौटाएं और वैकल्पिक रूप से retryAfter लौटाएं। शून्य रिफिल दर और क्षमता से अधिक लागत को संभालते हुए, विलंब का अनुमान (cost - tokens) / refillRate के रूप में लगाएं, जिसे ऊपर की ओर राउंड किया गया हो। एक अस्वीकृति को सफलता की तरह नहीं दिखना चाहिए या कर्सर को पीछे नहीं ले जाना चाहिए।
4. कॉनकरेंसी और स्टोरेज
सिंगल-प्रोसेस कोड को पढ़ने, रिफिल करने, निर्णय लेने और लिखने को एक क्रिटिकल सेक्शन में रखना चाहिए; शार्ड किए गए प्रति-उपयोगकर्ता लॉक एक वैश्विक लॉक से बचाते हैं। जब कई इंस्टेंस कोटा साझा करते हैं, तो एप्लिकेशन लॉक अपर्याप्त होते हैं। संपूर्ण स्थिति संक्रमण के लिए Redis Lua, एक डेटाबेस रो लॉक, या किसी अन्य एटॉमिक लेनदेन का उपयोग करें। नेटवर्क रीट्राई के दौरान एक अनुरोध आईडी साथ रखें ताकि खोई हुई प्रतिक्रिया गलती से व्यावसायिक टोकन का दो बार उपभोग न करे।
5. समाप्ति और कार्डिनैलिटी
lastRefillAt और लीज नीति का उपयोग करके निष्क्रिय उपयोगकर्ता स्थिति को समाप्त करें, जबकि यह सुनिश्चित करें कि एक नया अनुरोध सही ढंग से इनिशियलाइज़ हो। स्थिति सीमा, शार्डिंग और निष्कासन (eviction) नीति के साथ उच्च-कार्डिनैलिटी उपयोगकर्ताओं से सुरक्षित रहें। निष्कासित बकेट को पूरी क्षमता पर फिर से बनाना एक बर्स्ट उत्पन्न कर सकता है, इसलिए उत्पादन नीति में यह स्पष्ट होना चाहिए कि क्या यह स्वीकार्य है। हमलावर द्वारा नियंत्रित उपयोगकर्ता आईडी को कभी भी एक अनबाउंंडेड मैप बढ़ाने की अनुमति न दें।
6. परीक्षण और अवलोकनीयता (Observability)
प्रारंभ में भरी हुई बकेट, बार-बार अस्वीकृति, सटीक रिफिल, क्षमता के बराबर लागत, समय में कोई प्रगति न होना, क्लॉक रोलबैक, लंबे समय तक निष्क्रिय अंतराल, विवाद और डुप्लिकेट कॉल का परीक्षण करें। एक इंजेक्ट की गई क्लॉक के साथ, पुष्टि करें कि बैलेंस सीमाओं के भीतर रहता है और सफल लागत कभी भी प्रारंभिक क्षमता प्लस सैद्धांतिक रिफिल से अधिक नहीं होती है। अनुमति और अस्वीकृति दर, टोकन वितरण, स्थिति गणना, लॉक प्रतीक्षा, एटॉमिक-स्क्रिप्ट त्रुटियों और मेमोरी उपयोग को ट्रैक करें।
उच्च-गुणवत्ता वाला नमूना उत्तर
मैं allow(userId, now, cost) को प्रदर्शित करूंगा। उपयोगकर्ता स्थिति में केवल tokens और lastRefillAt शामिल हैं। एक क्रिटिकल सेक्शन के अंदर, बीते हुए समय की गणना करें, रिफिल करें, क्षमता के अनुसार सीमित करें और निर्णय लें। सफलता पर, लागत घटाएं और कर्सर को now पर ले जाएं; अस्वीकृति पर, रिफिल किया गया बैलेंस रखें लेकिन कुछ भी उपभोग न करें। सभी समय अंकगणित एक मोनोटोनिक क्लॉक का उपयोग करते हैं, इसलिए स्थिति पीछे नहीं जा सकती।
एक प्रोसेस के लिए मैं शार्ड किए गए प्रति-उपयोगकर्ता लॉक का उपयोग करूंगा। कई इंस्टेंस के लिए मैं अलग-अलग नेटवर्क पढ़ने और लिखने के बजाय समान संक्रमण को Redis Lua या एक एटॉमिक डेटाबेस लेनदेन में रखूंगा। एक अनुरोध आईडी रीट्राई आइडम्पोटेंसी का समर्थन करती है; यह व्यावसायिक ऑपरेशन को ठीक एक बार (exactly once) नहीं बनाती है। समाप्ति और उच्च-कार्डिनैलिटी नियंत्रण मेमोरी के दुरुपयोग को रोकते हैं।
परीक्षण शून्य बीते हुए समय, सटीक रिफिल, पूर्ण-लागत अनुरोधों, लंबी निष्क्रिय अवधियों, क्लॉक रोलबैक और कॉनकरेंसी के लिए एक नियंत्रणीय क्लॉक का उपयोग करते हैं। एक प्रॉपर्टी टेस्ट यह दावा करता है कि प्रत्येक बैलेंस शून्य और क्षमता के बीच रहता है और संचयी अनुमत लागत कभी भी प्रारंभिक क्षमता प्लस रिफिल से अधिक नहीं होती है। उत्पादन में मैं अस्वीकृति दर, टोकन वितरण, स्थिति वृद्धि, लॉक प्रतीक्षा और स्टोरेज-स्क्रिप्ट त्रुटियों पर नज़र रखूंगा; AWS मार्गदर्शन भी किसी प्रस्तावित सीमा को बढ़ाने से पहले उसका परीक्षण करने का आह्वान करता है।
सामान्य गलतियाँ
- प्रत्येक बकेट के लिए एक टाइमर शुरू करना, जिससे शेड्यूलिंग लागत उपयोगकर्ता संख्या के साथ बढ़ती है।
- वॉल-क्लॉक समय का उपयोग करना, जिससे NTP रोलबैक अतिरिक्त टोकन बनाता है।
- क्षमता क्लैंप को भूल जाना और असीमित संचय की अनुमति देना।
- अस्वीकृत अनुरोधों के लिए शुल्क लेना और चुपचाप उपयोगकर्ता कोटा का उपभोग करना।
- इन-प्रोसेस लॉक को क्रॉस-इंस्टेंस एटॉमिकिटी के रूप में मानना।
cost > capacityको स्वीकार करना, जो हमेशा के लिए प्रतीक्षा कर सकता है या एक गलत रीट्राई समय उत्पन्न कर सकता है।- राउंडिंग और लंबे समय तक चलने वाले ड्रिफ्ट को परिभाषित किए बिना फ़्लोटिंग पॉइंट का उपयोग करना।
- केवल अनुक्रमिक कॉलों का परीक्षण करना और समवर्ती रीड-मॉडिफ़ाई-राइट रेस को छोड़ देना।
अनुवर्ती प्रश्न और उत्तर
फिक्स्ड-विंडो काउंटर क्यों नहीं?
एक फिक्स्ड विंडो सरल है लेकिन सीमा पर एक छोटा दोहरा बर्स्ट की अनुमति दे सकती है। एक टोकन बकेट क्षमता के साथ अनुमत बर्स्ट और रिफिल के साथ निरंतर दर व्यक्त करता है। यदि कोई बर्स्ट स्वीकार्य नहीं है, तो स्लाइडिंग विंडो या लीकी बकेट से तुलना करें।
आप Retry-After कैसे लौटाते हैं?
लापता बैलेंस को रिफिल दर से विभाजित करें और ऊपर की ओर राउंड करें। शून्य रिफिल या क्षमता से अधिक लागत के साथ, अनंत टाइमस्टैम्प के बजाय एक कॉन्फ़िगरेशन या गैर-पुनर्श्याम परिणाम लौटाएं।
क्या होगा यदि Redis अनुपलब्ध है?
एंडपॉइंट जोखिम के अनुसार फेल-क्लोज्ड, एक सीमित स्थानीय बजट, या एक स्पष्ट डिग्रेडेशन चुनें, और कारण रिकॉर्ड करें। प्रत्येक इंस्टेंस को बजट के बिना फेल ओपन न होने दें या आउटेज को एक सामान्य अस्वीकृति के रूप में न छिपाएं।
आप क्षमता और रिफिल दर कैसे बदलते हैं?
परिवर्तन समय तक पुराने मापदंडों के तहत रिफिल करें, फिर एक स्पष्ट नीति के तहत बैलेंस को क्लैंप या रूपांतरित करें और कॉन्फ़िगरेशन संस्करण रिकॉर्ड करें। क्षमता कम करने पर नई सीमा से ऊपर के मौजूदा बैलेंस को एटॉमिक रूप से संभालना होगा।
आप कैसे साबित करते हैं कि कोई ओवरसेलिंग नहीं है?
यादृच्छिक समय पर एक स्टेट-मशीन प्रॉपर्टी टेस्ट चलाएं और यह साबित करें कि प्रत्येक अंतराल में अनुमत लागत प्रारंभिक टोकन प्लस सैद्धांतिक रिफिल द्वारा सीमित है। एटॉमिक क्रिटिकल सेक्शन को सत्यापित करने के लिए समवर्ती तनाव परीक्षण जोड़ें।