गोकर्ण के दृष्टिकोण से CUCKOO बनाम BLOOM फ़िल्टर

इस लेख में, मैं एक खिल फिल्टर पर कोयल फिल्टर की दक्षता को लागू करने और परीक्षण करने की कोशिश कर रहा हूं। (गोल डीएचटी पर पिछली पोस्ट पढ़ें, गोलंग में एक वितरित हैश टेबल को लागू करना)

परिचय

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

उदाहरण मामलों का उपयोग करें

  • Google Bigtable, Apache HBase और Apache Cassandra, और Postgresql गैर-मौजूद पंक्तियों या स्तंभों के लिए डिस्क लुकअप को कम करने के लिए ब्लूम फ़िल्टर का उपयोग करते हैं। महंगा डिस्क लुकअप से बचने से डेटाबेस क्वेरी ऑपरेशन का प्रदर्शन बढ़ जाता है।
  • यदि उपयोगकर्ता किसी लेख को पहले ही सुझा चुका है, तो यह जांचने के लिए माध्यम ब्लूम फिल्टर का उपयोग करता है
  • Ethereum, Ethereum blockchain पर लॉग को जल्दी खोजने के लिए ब्लूम फ़िल्टर का उपयोग करता है
  • दुर्भावनापूर्ण URL की पहचान करने के लिए Google Chrome वेब ब्राउज़र ने ब्लूम फ़िल्टर का उपयोग किया था। किसी भी URL को पहली बार स्थानीय ब्लूम फ़िल्टर के खिलाफ चेक किया गया था, और केवल तभी जब ब्लूम फ़िल्टर ने एक सकारात्मक परिणाम लौटाया था, URL का पूर्ण चेक प्रदर्शन किया था (और उपयोगकर्ता ने चेतावनी दी थी, यदि वह भी सकारात्मक परिणाम लौटाए)

"कोयल" में क्या है?

हमने डेटा प्लेटफ़ॉर्म पर ऐसे प्रश्नों का उत्तर देने के लिए कई स्थानों पर ब्लूम फ़िल्टर का उपयोग किया है। हाल ही में मैं इस पेपर पर कोयल फ़िल्टर पर आया, जिसने मेरी रुचि को पकड़ा। शीर्षक खुद कहता है, "कोयल फ़िल्टर: व्यावहारिक रूप से ब्लूम से बेहतर", इसलिए मैंने इसे जांचने का फैसला किया।

कोयल फिल्टर विलोपन, सीमित गिनती और एक बंधी हुई झूठी सकारात्मक संभावना की पेशकश करते हुए खिल फिल्टर के डिजाइन पर सुधार करते हैं, जबकि अभी भी एक समान अंतरिक्ष जटिलता बनाए रखते हैं। वे टकरावों को हल करने के लिए कोयल हैशिंग का उपयोग करते हैं और अनिवार्य रूप से एक कॉम्पैक्ट कोयल हैश तालिका है।

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

कलन विधि

फ़िल्टर के पैरामीटर:
1. दो हैश फंक्शंस: h1 और h2
2. n बकेट के साथ एक सरणी B। I-th बाल्टी को B [i] कहा जाएगा।

इनपुट: L, कोयल फिल्टर में डाले जाने वाले तत्वों की एक सूची।

कलन विधि:
जबकि L खाली नहीं है:
    L को सूची से पहला आइटम होने दें। L को सूची से x हटा दें।
    यदि B [h1 (x)] खाली है:
        बी में जगह x [h1 (x)]
    और, यदि B [h2 (x) खाली है]:
        जगह x में बी [h2 (x)]
    अन्य:
        Y को B [h2 (x)] में तत्व होने दें।
        Y से L तक प्रेप करें
        जगह x में बी [h2 (x)]

कार्यान्वयन

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

निवेशन

कलन विधि:

f = फिंगरप्रिंट (x);
i1 = हैश (एक्स);
i2 = i1 h हैश (f);
अगर बाल्टी [i1] या बाल्टी [i2] में एक खाली प्रविष्टि है तो
   उस बाल्टी में एफ जोड़ें;
   वापस किया;
// मौजूदा वस्तुओं को स्थानांतरित करना चाहिए;
i = अनियमित रूप से i1 या i2 चुनें;
एन = 0 के लिए; n <मैक्सनुमिक्स; n ++ करते हैं
   बेतरतीब ढंग से बाल्टी [i] से एक प्रविष्टि ई का चयन करें;
   स्वैप एफ और प्रवेश ई में संग्रहीत फिंगरप्रिंट;
   i = i ⊕ हैश (f);
   अगर बाल्टी [i] में एक खाली प्रविष्टि है तो
      बाल्टी में जोड़ें [i];
      वापस किया;
// हैशटेबल को पूर्ण माना जाता है;
वापसी विफलता;

कोड:

खोज

कलन विधि:

f = फिंगरप्रिंट (x);
i1 = हैश (एक्स);
i2 = i1 h हैश (f);
अगर बाल्टी [i1] या बाल्टी [i2] में तब है
    सच्चा लौटना;
विवरण झूठा है;

कोड:

हटाएं

कलन विधि:

f = फिंगरप्रिंट (x);
i1 = हैश (एक्स);
i2 = i1 h हैश (f);
अगर बाल्टी [i1] या बाल्टी [i2] में तब है
   इस बाल्टी से च की एक प्रति निकालें;
   सच्चा लौटना;
विवरण झूठा है;

कोड:

प्रदर्शन का परीक्षण

ब्लूम फ़िल्टर पर परीक्षण के लिए मैंने विल फिट्ज़गेराल्ड लाइब्रेरी का उपयोग किया है। कोयल फिल्टर के लिए लिया गया FPP (झूठी सकारात्मक संभावना) राशन 0.001 है

अंतरिक्ष जटिलता

कोयल और खिल फिल्टर के संबंध में, वे अलग-अलग झूठी सकारात्मक संभावनाओं पर अलग-अलग प्रदर्शन करते हैं। जब फ़िल्टर की झूठी सकारात्मक संभावना 3% से कम या उसके बराबर होती है, तो कोयल फ़िल्टर में प्रति प्रविष्टि कम बिट्स होते हैं। जब यह अधिक होता है, तो ब्लूम फ़िल्टर में प्रति प्रविष्टि कम बिट्स होते हैं।

समय जटिलता

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

दोनों फिल्टरों का एक समय विश्लेषण करने से निम्नलिखित परिणाम मिलते हैं:

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

अनुमान

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

कोड

संदर्भ

  • https://brilliant.org/wiki/cuckoo-filter/
  • https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
  • https://en.wikipedia.org/wiki/Cuckoo_hashing
  • https://blog.fastforwardlabs.com/2016/11/23/probabilistic-data-structure-showdown-cuckoo.html

यदि आप परीक्षण / कार्यान्वयन में कुछ भी गलत पाते हैं, तो कृपया अपना सुझाव / टिप्पणी छोड़ने के लिए स्वतंत्र महसूस करें।