उपयोगकर्ता साइन-अप पृष्ठ पर एक उपयोगकर्ता नाम दिया गया है, हम कैसे बता सकते हैं कि यह पहले ही पंजीकृत हो चुका है?

अनुक्रमित डेटाबेस से पूछताछ करते समय मदद मिलती है, यह धीमा होता है और नेटवर्क कॉल करता है।

चीजों को गति देने के लिए, हम रेडिस जैसे की-वैल्यू स्टोर में पंजीकृत उपयोगकर्ता नामों की सूची को कैश कर सकते हैं।

हालाँकि, इसका अर्थ है लाखों रिकॉर्ड को कैश करना और हमारी मेमोरी फ़ुटप्रिंट को दोगुना करना।

हम इस प्रतीत होने वाली तुच्छ समस्या में बेहतर कैसे कर सकते हैं?

ब्लूम फ़िल्टर उत्तर हो सकता है, आइए इसे देखें!

ब्लूम फ़िल्टर क्या है?

एक ब्लूम फ़िल्टर एक सरल प्रश्न का उत्तर देता है,

क्या किसी दिए गए सेट में कोई तत्व मौजूद है?

ब्लूम फ़िल्टर एक संभाव्य डेटा संरचना है। उपरोक्त प्रश्न को देखते हुए, यह निम्न में से किसी भी उत्तर को आउटपुट करता है

• शायद हाँ
• 100% नहीं

और इसका सबसे बड़ा फायदा यह है कि यह CONSTANT समय और स्थान में करता है।

यह कैसे काम करता है?

एक ब्लूम फिल्टर में दो घटक होते हैं

• एक एन-आकार बिट सरणी
• कई हैशिंग कार्य

यह पहली बार एन-आकार बिट सरणी के रूप में शुरू किया गया है, इसके सभी बिट शून्य पर सेट हैं। आइए मान लें कि सरणी की लंबाई अभी 10 है।

एक आइटम जोड़ना

एक आइटम जोड़ना तुच्छ है

• आइटम "टाइगर" कहा गया है, हैशिंग फ़ंक्शन का उपयोग करके हैश किया गया है
• एक बंधे हुए सूचकांक को प्राप्त करने के लिए उत्पन्न हैश सरणी की लंबाई से मॉड है
• बिट सरणी का सूचकांक तब 1 पर सेट होता है

किसी आइटम को जोड़ने के समान, हम हैशिंग फ़ंक्शन का उपयोग करके तत्व को हैश करते हैं और एक बाउंडेड इंडेक्स प्राप्त करने के लिए इसे संशोधित करते हैं।

आउटपुट का मूल्यांकन निम्नानुसार किया जाता है,

• यदि बिट सरणी का सूचकांक मान 0 है, तो आइटम सेट में नहीं है।
• अन्यथा, आइटम संभवतः सेट में है

ब्लूम फिल्टर का भंडारण

ब्लूम फ़िल्टर को सरणी के रूप में संग्रहीत करने के बजाय, हम इसके बिट प्रतिनिधित्व को दशमलव संख्या में परिवर्तित कर सकते हैं।

उदाहरण के लिए, हम एक सरणी 10011को 19 में परिवर्तित कर सकते हैं और इसे कैश में संग्रहीत कर सकते हैं।

यदि सूची बहुत बार नहीं बदलती है, तो सर्वर ग्राहक को दशमलव संख्या भेज सकता है, जिससे ग्राहक पक्ष पर सत्यापन किया जा सकता है।

क्या हम बेहतर कर सकते हैं?

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

हम निम्नलिखित समाधानों के माध्यम से झूठी सकारात्मकता की संभावना को कम कर सकते हैं।

• सरणी की लंबाई बढ़ाएँ
• हैशिंग कार्यों की संख्या बढ़ाएँ

एक इंडेक्स के बजाय, हम कई हैश का उपयोग करके कई इंडेक्स प्राप्त कर सकते हैं।

कोई आइटम जोड़ते समय, सभी प्राप्त इंडेक्स 1 पर सेट किए जाएंगे।

एक आइटम के सेट में होने का दावा किया जाता है, केवल तभी जब सभी इंडेक्स 1 पर सेट हों।

इन विधियों का लाभ उठाकर, हम झूठी सकारात्मकता की संभावना को काफी कम कर सकते हैं।

अनुप्रयोग

आइए कुछ वास्तविक जीवन के उदाहरण देखें।

जांचें कि उपयोगकर्ता साइन-अप प्रवाह में उपयोगकर्ता नाम मौजूद है या नहीं

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

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

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

जबकि झूठी सकारात्मकता हो सकती है , एक ब्लूम फ़िल्टर आसान होता है जब हम यह बताना चाहते हैं कि कोई आइटम निश्चित रूप से सूची में नहीं है या नहीं।

समय और स्थान दोनों में इसकी दक्षता के कारण इसे फ़िल्टरिंग की पहली परत के रूप में उपयोग किया जा सकता है।

मुझे आशा है कि आपको यह मददगार लगेगा, और मैं आपको अगले एक पर देखूंगा!