प्रसंस्करण अनुरोधों की गति को सीमित करना, या अपने ग्राहक पर DDoS हमले की व्यवस्था करना नहीं

कभी-कभी जब एक हाईलोड उत्पाद विकसित करते हैं, तो एक स्थिति उत्पन्न होती है जब यह संभव नहीं के रूप में कई अनुरोधों को संसाधित करने के लिए आवश्यक होता है, लेकिन प्रति यूनिट समय अनुरोधों की संख्या को सीमित करने के लिए। हमारे मामले में, यह अंतिम सूचनाओं की संख्या है जो अंतिम उपयोगकर्ताओं को भेजी जाती है। कटौती के तहत एल्गोरिदम, उनके पेशेवरों और विपक्षों को सीमित करने के बारे में और पढ़ें।

पहले, हमारे बारे में थोड़ा। Pushwoosh हमारे ग्राहकों और उनके उपयोगकर्ताओं के बीच संचार के लिए एक b2b सेवा है। हम पुश सूचनाओं, ईमेल और अन्य संचार चैनलों के माध्यम से उपयोगकर्ताओं के साथ संवाद करने के लिए व्यापक समाधान प्रदान करते हैं। वास्तव में संदेश भेजने के अलावा, हम दर्शकों को खंडित करने, आंकड़े एकत्र करने और संसाधित करने और बहुत कुछ करने के लिए उपकरण प्रदान करते हैं। ऐसा करने के लिए, स्क्रैच से हमने कई तकनीकों के जंक्शन पर एक उच्च भार वाला उत्पाद बनाया, जिसका केवल एक छोटा सा हिस्सा पीएचपी, गोलांग, पोस्टग्रेक्यूएल, मोंगोडीबी, अपाचे काफ्का हैं। हमारे कई समाधान अद्वितीय हैं, उदाहरण के लिए, उच्च गति सूचनाएँ। हम प्रति दिन 2 बिलियन से अधिक एपीआई अनुरोधों की प्रक्रिया करते हैं, हमारे डेटाबेस में 3 बिलियन से अधिक डिवाइस हैं, और पूरे समय में हमने इन उपकरणों को 500 बिलियन से अधिक सूचनाएं भेजी हैं।

और यहां हम एक ऐसी स्थिति में आते हैं, जहां सूचनाओं को लाखों उपकरणों तक पहुंचाने की आवश्यकता नहीं है जितनी जल्दी हो सके (जैसा कि पहले ही बताई गई उच्च गति में है), लेकिन कृत्रिम रूप से गति को सीमित करना ताकि हमारे ग्राहकों के सर्वर जब वे अधिसूचना खोलने जाते हैं, उसी समय के अंतर्गत न आएं। लोड।

यहाँ, विभिन्न दर सीमित एल्गोरिदम हमारी सहायता के लिए आते हैं, जो हमें प्रति यूनिट समय अनुरोधों की संख्या को सीमित करने की अनुमति देते हैं। एक नियम के रूप में, इसका उपयोग उदाहरण के लिए किया जाता है, एपीआई डिजाइन करते समय, इस तरह से हम सिस्टम को आकस्मिक या दुर्भावनापूर्ण अतिरिक्त अनुरोधों से बचा सकते हैं, जिसके परिणामस्वरूप अन्य ग्राहकों को सेवा में देरी या इनकार होता है। यदि दर सीमा लागू की जाती है, तो सभी ग्राहक प्रति यूनिट समय अनुरोधों की एक निश्चित संख्या तक सीमित रहते हैं। इसके अलावा, संवेदनशील डेटा से जुड़े सिस्टम के कुछ हिस्सों तक पहुंचते समय दर सीमित किया जा सकता है; इस प्रकार, यदि कोई हमलावर उन तक पहुंच प्राप्त करता है, तो वह जल्दी से सभी डेटा तक नहीं पहुंच पाएगा।

दर सीमित करने के कई अलग-अलग तरीके हैं। इस लेख में, हम विभिन्न एल्गोरिदम के पेशेवरों और विपक्षों पर विचार करेंगे, साथ ही इन समस्याओं को हल करते समय उत्पन्न होने वाली समस्याएं भी।

अनुरोध प्रसंस्करण गति सीमा एल्गोरिदम

लीक बाल्टी (लीकिंग बाल्टी)

लीक बकेट एक एल्गोरिथ्म है जो एक कतार का उपयोग करके प्रसंस्करण गति को सीमित करने के लिए सबसे सरल, सबसे सहज दृष्टिकोण प्रदान करता है, जिसे "बाल्टी" अनुरोध के रूप में दर्शाया जा सकता है। जब कोई अनुरोध प्राप्त होता है, तो इसे कतार के अंत में जोड़ा जाता है। नियमित अंतराल पर, कतार में पहला तत्व संसाधित होता है। इसे फीफो कतार के रूप में भी जाना जाता है। यदि कतार भरी हुई है, तो अतिरिक्त अनुरोधों को छोड़ दिया जाता है (या "लीक")।

इस एल्गोरिथ्म का लाभ यह है कि यह आउटबर्स्ट को सुचारू करता है और लगभग एक ही गति से अनुरोधों को संसाधित करता है, एकल सर्वर या लोड बैलेंसर पर लागू करना आसान है, यह स्मृति उपयोग में कुशल है, क्योंकि प्रत्येक उपयोगकर्ता के लिए कतार का आकार सीमित है।
हालांकि, यातायात में तेज वृद्धि के साथ, कतार पुराने अनुरोधों से भरी हो सकती है और अधिक हाल के अनुरोधों को संसाधित करने की क्षमता से प्रणाली को वंचित कर सकती है। वह यह भी गारंटी नहीं देता है कि अनुरोध किसी भी निश्चित समय में संसाधित किए जाएंगे। इसके अलावा, यदि आप दोष सहिष्णुता प्रदान करने या थ्रूपुट बढ़ाने के लिए बैलेंसरों को लोड करते हैं, तो आपको एक समन्वय नीति लागू करनी चाहिए और उनके बीच वैश्विक प्रतिबंध सुनिश्चित करना चाहिए।

इस एल्गोरिथ्म की एक भिन्नता है - टोकन बाल्टी ("टोकन के साथ बाल्टी" या "मार्कर बास्केट एल्गोरिदम")।

इस तरह के कार्यान्वयन में, एक स्थिर गति से टोकन को "बाल्टी" में जोड़ा जाता है, और अनुरोध को संसाधित करते समय, "बाल्टी" से टोकन हटा दिया जाता है; यदि पर्याप्त टोकन नहीं हैं, तो अनुरोध को छोड़ दिया गया है। आप बस टाइमस्टैम्प का उपयोग टोकन के रूप में कर सकते हैं।

कई "बकेट" का उपयोग करने के लिए भिन्नताएं हैं, जबकि दोनों आकार और उनमें टोकन की प्राप्ति की दर अलग-अलग "बकेट" के लिए भिन्न हो सकती है। यदि अनुरोध को संसाधित करने के लिए पहले "बाल्टी" में पर्याप्त टोकन नहीं हैं, तो दूसरे में उनकी उपस्थिति आदि की जांच की जाती है, लेकिन अनुरोध प्रसंस्करण की प्राथमिकता कम हो जाती है (एक नियम के रूप में, यह नेटवर्क इंटरफेस के डिजाइन में उपयोग किया जाता है, उदाहरण के लिए, आप फ़ील्ड मान को बदल सकते हैं DSCP संसाधित पैकेट)।

लीक बाल्टी कार्यान्वयन से मुख्य अंतर यह है कि सिस्टम के निष्क्रिय होने पर टोकन जमा हो सकते हैं और फटने बाद में हो सकते हैं, जबकि अनुरोध संसाधित होंगे (चूंकि पर्याप्त टोकन हैं), जबकि लीक बाल्टी को लोड को सुचारू करने की गारंटी है डाउनटाइम के मामले में भी।

फिक्स्ड विंडो

यह एल्गोरिथ्म अनुरोधों को ट्रैक करने के लिए n सेकंड की विंडो का उपयोग करता है। आमतौर पर, 60 सेकंड (मिनट) या 3600 सेकंड (घंटा) जैसे मूल्यों का उपयोग किया जाता है। प्रत्येक आवक अनुरोध इस विंडो के लिए काउंटर बढ़ाता है। यदि काउंटर एक निश्चित सीमा मान से अधिक है, तो अनुरोध को छोड़ दिया गया है। आमतौर पर, विंडो वर्तमान समय अंतराल की निचली सीमा से निर्धारित होती है, अर्थात, जब खिड़की 60 सेकंड चौड़ी होती है, तो 12:00:03 पर आने वाला अनुरोध विंडो 12:00:00 पर जाएगा।

इस एल्गोरिथ्म का लाभ यह है कि यह पुराने के प्रसंस्करण के आधार पर, बिना हाल के अनुरोधों के प्रसंस्करण प्रदान करता है। हालाँकि, विंडो बॉर्डर के पास ट्रैफ़िक का एक एकल फट संसाधित अनुरोधों की संख्या को दोगुना कर सकता है, क्योंकि यह थोड़े समय के लिए वर्तमान और अगली विंडो दोनों के लिए अनुरोध की अनुमति देता है। इसके अलावा, यदि कई उपयोगकर्ता विंडो काउंटर के रीसेट होने की प्रतीक्षा कर रहे हैं, उदाहरण के लिए, घंटे के अंत में, वे इस समय लोड को बढ़ाने के लिए उकसा सकते हैं इस तथ्य के कारण कि वे उसी समय एपीआई का उपयोग करेंगे।

स्लाइडिंग लॉग

इस एल्गोरिथ्म में प्रत्येक उपयोगकर्ता अनुरोध के टाइमस्टैम्प को ट्रैक करना शामिल है। इन अभिलेखों को संग्रहीत किया जाता है, उदाहरण के लिए, हैश सेट या टेबल में और समय के अनुसार क्रमबद्ध; मॉनिटर किए गए अंतराल के बाहर के रिकॉर्ड को छोड़ दिया जाता है। जब एक नया अनुरोध आता है, तो हम अनुरोधों की आवृत्ति निर्धारित करने के लिए रिकॉर्ड की संख्या की गणना करते हैं। यदि अनुरोध स्वीकार्य मात्रा के बाहर है, तो उसे छोड़ दिया जाता है।

इस एल्गोरिथ्म का लाभ यह है कि यह उन समस्याओं के अधीन नहीं है जो फिक्स्ड विंडो की सीमाओं पर उत्पन्न होती हैं, अर्थात, गति सीमा को सख्ती से देखा जाएगा। इसके अलावा, चूंकि प्रत्येक ग्राहक के अनुरोधों की व्यक्तिगत रूप से निगरानी की जाती है, इसलिए कुछ बिंदुओं पर कोई पीक लोड वृद्धि नहीं होती है, जो पिछले एल्गोरिथ्म की एक और समस्या है।

हालांकि, प्रत्येक अनुरोध के बारे में जानकारी संग्रहीत करना महंगा हो सकता है, इसके अलावा, प्रत्येक अनुरोध के लिए पिछले अनुरोधों की संख्या की गणना करने की आवश्यकता होती है, संभवतः पूरे क्लस्टर पर, जिसके परिणामस्वरूप यह दृष्टिकोण यातायात के बड़े विस्फोट और सेवा हमलों से इनकार करने के लिए अच्छी तरह से पैमाने पर नहीं होता है।

स्लाइडिंग विंडो

यह एक हाइब्रिड दृष्टिकोण है जो एक फिक्स्ड विंडो को संसाधित करने की कम लागत और सीमा लॉग की उन्नत परिस्थितियों को संभालता है। जैसा कि सरल फिक्स्ड विंडो में , हम प्रत्येक विंडो के लिए काउंटर को ट्रैक करते हैं, और फिर ट्रैफ़िक के फटने को रोकने के लिए वर्तमान समय स्टैंप पर आधारित पिछली विंडो के अनुरोध आवृत्ति के भारित मूल्य को ध्यान में रखते हैं। उदाहरण के लिए, यदि वर्तमान विंडो का 25% समय बीत चुका है, तो हम पिछले एक के अनुरोधों के 75% को ध्यान में रखते हैं। प्रत्येक कुंजी को ट्रैक करने के लिए आवश्यक अपेक्षाकृत कम मात्रा में डेटा हमें बड़े क्लस्टर में स्केल करने और काम करने की अनुमति देता है।

यह एल्गोरिदम आपको अच्छे प्रदर्शन को बनाए रखते हुए दर सीमित करने की अनुमति देता है। इसके अलावा, ग्राहकों के अनुरोधों की संख्या को सीमित करने के बारे में जानकारी देने के लिए यह एक समझने योग्य तरीका है, और अन्य दर के एल्गोरिदम को लागू करते समय आने वाली समस्याओं से भी बचा जाता है।

वितरित प्रणालियों में दर सीमा

सिंक नीतियां

यदि आप कई नोड्स से मिलकर क्लस्टर का उपयोग करते समय वैश्विक दर को सीमित करना चाहते हैं, तो आपको प्रतिबंध नीति को लागू करने की आवश्यकता है। यदि प्रत्येक नोड ने केवल अपने स्वयं के प्रतिबंध को ट्रैक किया, तो उपयोगकर्ता इसे अलग-अलग नोड्स में केवल अनुरोध भेजकर बाईपास कर सकता है। वास्तव में, नोड्स की संख्या जितनी अधिक होगी, उतनी ही अधिक संभावना होगी कि उपयोगकर्ता वैश्विक सीमा से अधिक हो जाएगा।

सीमाएं निर्धारित करने का सबसे आसान तरीका यह है कि बैलेंसर पर "चिपचिपा सत्र" कॉन्फ़िगर किया जाए ताकि उपयोगकर्ता को उसी नोड पर निर्देशित किया जाए। जब क्लस्टर नोड्स अतिभारित होते हैं, तो इस पद्धति के नुकसान दोष सहिष्णुता और स्केलिंग समस्याओं की कमी है।

सबसे अच्छा समाधान, जो लोड संतुलन के लिए अधिक लचीले नियमों की अनुमति देता है, एक केंद्रीकृत डेटा वेयरहाउस (आपकी पसंद का) का उपयोग करना है। यह प्रत्येक विंडो और उपयोगकर्ता के लिए अनुरोधों की संख्या को काउंटर कर सकता है। इस दृष्टिकोण की मुख्य समस्याएं भंडारण अनुरोधों और दौड़ की स्थितियों के कारण प्रतिक्रिया समय में वृद्धि हैं।

दौड़ की स्थिति

एक केंद्रीकृत डेटा गोदाम के साथ सबसे बड़ी समस्याओं में से एक है प्रतिस्पर्धा करते समय दौड़ की स्थिति। ऐसा तब होता है जब आप प्राकृतिक गेट-तत्कालीन सेट दृष्टिकोण का उपयोग करते हैं, जिसमें आप वर्तमान काउंटर को निकालते हैं, इसे बढ़ाते हैं, और फिर परिणामी मूल्य को स्टोर में वापस भेजते हैं। इस मॉडल के साथ समस्या यह है कि इन कार्यों के पूर्ण चक्र को पूरा करने के लिए आवश्यक समय के दौरान (यानी, पढ़ना, वृद्धि और लिखना), अन्य अनुरोध आ सकते हैं, जिनमें से प्रत्येक में काउंटर को अमान्य (निम्न) मान के साथ संग्रहीत किया जाएगा। यह उपयोगकर्ता को एल्गोरिथ्म प्रदान करने की दर को सीमित करने की तुलना में अधिक अनुरोध भेजने की अनुमति देता है।

इस समस्या से बचने का एक तरीका यह है कि प्रश्न में कुंजी के चारों ओर एक लॉक सेट करें, काउंटर तक किसी अन्य प्रक्रिया को पढ़ने या लिखने के लिए पहुँच को रोकना। हालांकि, यह जल्दी से एक प्रदर्शन अड़चन बन सकता है और अच्छी तरह से पैमाने पर नहीं होता है, खासकर जब दूरस्थ सर्वर, जैसे कि रेडिस, एक अतिरिक्त डेटा स्टोर के रूप में उपयोग करते हैं।

परमाणु ऑपरेटरों के आधार पर एक बेहतर दृष्टिकोण "सेट - फिर - प्राप्त करें" है, जो आपको परमाणु कार्यों में हस्तक्षेप किए बिना काउंटर मानों को जल्दी से बढ़ाने और जांचने की अनुमति देता है।

प्रदर्शन अनुकूलन

एक केंद्रीकृत डेटा वेयरहाउस का उपयोग करने का एक और नुकसान दर सीमित करने के लिए उपयोग किए जाने वाले काउंटरों की जांच में देरी के कारण प्रतिक्रिया समय में वृद्धि है ( गोल-यात्रा समय , या " गोल-यात्रा देरी")। दुर्भाग्य से, यहां तक ​​कि तेजी से भंडारण के लिए जाँच जैसे कि रेडिस प्रति अनुरोध कुछ मिलीसेकेंड के अतिरिक्त विलंब के परिणामस्वरूप होगा।

एक न्यूनतम देरी के साथ एक बाधा की परिभाषा बनाने के लिए, स्थानीय मेमोरी में जांच करना आवश्यक है। यह गति की जांच करने और अंततः एक सुसंगत मॉडल का उपयोग करने के लिए शर्तों को शिथिल करके किया जा सकता है।

उदाहरण के लिए, प्रत्येक नोड एक डेटा सिंक्रनाइज़ेशन चक्र बना सकता है जिसमें वह रिपॉजिटरी के साथ सिंक्रनाइज़ करेगा। प्रत्येक नोड समय-समय पर प्रत्येक उपयोगकर्ता के लिए काउंटर मूल्य और प्रभावित होने वाली विंडो को स्टोर में पहुंचाता है, जो मूल्यों को परमाणु अद्यतन करेगा। फिर नोड नए मान प्राप्त कर सकता है और स्थानीय मेमोरी में डेटा अपडेट कर सकता है। यह चक्र अंततः क्लस्टर में सभी नोड्स को अद्यतित करने की अनुमति देगा।

जिस अवधि के दौरान नोड्स को सिंक्रनाइज़ किया जाता है वह अनुकूलन योग्य होना चाहिए। कम तुल्यकालन अंतराल कम डेटा विसंगति को जन्म देगा जब लोड समान रूप से क्लस्टर के कई नोड्स में वितरित किया जाता है (उदाहरण के लिए, उस स्थिति में जब बैलेंसर "राउंड-रॉबिन" सिद्धांत के अनुसार नोड्स निर्धारित करता है), जबकि लंबे अंतराल के लिए स्टोरेज के लिए कम रीड / राइट लोड बनाते हैं। और सिंक्रनाइज़ किए गए डेटा प्राप्त करने के लिए प्रत्येक नोड पर लागत कम करें।

दर सीमा की तुलना एल्गोरिदम

विशेष रूप से, हमारे मामले में, हमें एपीआई के लिए ग्राहक के अनुरोध को अस्वीकार नहीं करना चाहिए, लेकिन डेटा के आधार पर, इसके विपरीत, उन्हें नहीं बनाएं; हालाँकि, हमें अनुरोधों को "खोने" का कोई अधिकार नहीं है। ऐसा करने के लिए, सूचना भेजते समय, हम send_rate पैरामीटर का उपयोग करते हैं, जो अधिकतम सूचनाओं को इंगित करता है जिन्हें हम भेजते समय प्रति सेकंड भेजेंगे।

इस प्रकार, हमारे पास आवंटित समय (मेरे उदाहरण में, एक फ़ाइल से पढ़ना) में एक निश्चित वर्कर का काम है, जो एक इनपुट के रूप में RateLimitingInterface इंटरफ़ेस प्राप्त करता है, यह बताता है कि क्या किसी निश्चित समय पर अनुरोध निष्पादित करना संभव है और यह कब तक चलेगा।

interface RateLimitingInterface { /** * @param int $rate Expected send rate */ public function __construct(int $rate); /** * @param float $currentTime Current timestamp in microseconds * @return bool */ public function canDoWork(float $currentTime): bool; } 

सभी कोड उदाहरण GitHub पर यहां देखे जा सकते हैं ।

मैं तुरंत समझाता हूं कि आपको वर्कर को टाइम स्लाइस ट्रांसफर करने की आवश्यकता क्यों है तथ्य यह है कि गति सीमा के साथ एक संदेश भेजने की प्रक्रिया करने के लिए एक अलग डेमॉन चलाना बहुत महंगा है, इसलिए send_rate को वास्तव में "प्रति यूनिट समय पर सूचनाओं की संख्या" पैरामीटर के रूप में उपयोग किया जाता है, जो लोड के आधार पर 0.01 - 1 सेकंड है।

वास्तव में, हम प्रति सेकंड send_rate के साथ 100 अलग-अलग अनुरोधों को संसाधित करते हैं, प्रत्येक क्वांटम समय के लिए 1 / N सेकंड आवंटित करते हैं, जहां N इस डेमॉन द्वारा संसाधित पुश की संख्या है। प्रसंस्करण के दौरान हम जिस पैरामीटर में सबसे अधिक रुचि रखते हैं, वह यह है कि send_rate का सम्मान किया जाएगा (छोटी त्रुटियों को एक दिशा या किसी अन्य में अनुमति दी जाती है) और हमारे हार्डवेयर पर लोड (भंडारण, सीपीयू और मेमोरी की खपत की न्यूनतम संख्या)।

आरंभ करने के लिए, आइए जानें कि कार्यकर्ता वास्तव में किन बिंदुओं पर काम करता है। सादगी के लिए, इस उदाहरण ने send_rate = 1000 के साथ 10,000-लाइन फ़ाइल संसाधित की (अर्थात, हम फ़ाइल से प्रति सेकंड 1000 लाइनें पढ़ते हैं)।

स्क्रीनशॉट में, मार्कर सभी एल्गोरिदम के क्षणों और संख्याओं को कॉल करते हैं। वास्तव में, यह एक डेटाबेस, एक तृतीय-पक्ष संसाधन, या किसी भी अन्य प्रश्न के लिए एक अपील हो सकती है, जिसकी संख्या हम समय की प्रति इकाई को सीमित करना चाहते हैं।

एक्स पैमाने पर - प्रसंस्करण की शुरुआत से 0 से 10 सेकंड तक, प्रत्येक सेकंड को दसवें में विभाजित किया जाता है, इसलिए अनुसूची 0 से 100 तक है)।

हम देखते हैं कि इस तथ्य के बावजूद कि सभी एल्गोरिदम send_rate (इसके लिए उनका इरादा है) के पालन के साथ सामना करते हैं, फिक्स्ड विंडो और स्लाइडिंग लॉग लगभग पूरे लोड को एक साथ "बाहर" देते हैं, जो कि टोकन बकेट और स्लाइडिंग के दौरान हमें बहुत सूट नहीं करता है। पिछले समय में लोड के बारे में डेटा की कमी के कारण विंडोज इसे प्रति यूनिट समय पर वितरित करता है (शुरुआत के समय पीक लोड के अपवाद के साथ)।

इस तथ्य के कारण कि वास्तव में कोड आमतौर पर स्थानीय फ़ाइल सिस्टम के साथ काम नहीं करता है, लेकिन तीसरे पक्ष के भंडारण के साथ, उत्तर में देरी हो सकती है, नेटवर्क समस्याएं और कई अन्य समस्याएं हो सकती हैं, हम यह जांचने की कोशिश करेंगे कि यह या वह एल्गोरिथ्म कैसे व्यवहार करेगा जब अनुरोधों में कुछ समय लगेगा। नहीं था। उदाहरण के लिए, 4 और 6 सेकंड के बाद।

यहां, ऐसा लग सकता है कि फिक्स्ड विंडो ने सही तरीके से काम नहीं किया और पहले और 7 से 8 सेकंड में अपेक्षित अनुरोधों से 2 गुना अधिक संसाधित किया, लेकिन वास्तव में ऐसा नहीं है, क्योंकि चार्ट पर लॉन्च के क्षण से समय की गणना की जाती है, और एल्गोरिथ्म वर्तमान यूनिक्स टाइमस्टैम्प का उपयोग करता है। ।

सामान्य तौर पर, मौलिक रूप से कुछ भी नहीं बदला है, लेकिन हम देखते हैं कि टोकन बाल्टी लोड को अधिक सुचारू रूप से चिकना करती है और कभी भी निर्दिष्ट दर सीमा से अधिक नहीं होती है, लेकिन डाउनटाइम के मामले में स्लाइडिंग लॉग अनुमेय मूल्य से अधिक हो सकता है।

निष्कर्ष

हमने दर सीमित करने के लिए सभी बुनियादी एल्गोरिदम की जांच की, जिनमें से प्रत्येक में इसके पेशेवरों और विपक्ष हैं और विभिन्न कार्यों के लिए उपयुक्त है। हमें उम्मीद है कि इस लेख को पढ़ने के बाद, आप अपनी समस्या को हल करने के लिए सबसे उपयुक्त एल्गोरिदम चुनेंगे।