उदाहरण से Bloom Filter को समझना

• Bloom Filter एक probabilistic data structure है, जो memory-efficient तरीके से किसी set में element की मौजूदगी को तेज़ी से जांचता है
• यह केवल इतना बताता है कि कोई element set में पक्का नहीं है, या हो सकता है मौजूद हो, और इसमें false positive की संभावना होती है
• इसकी मूल संरचना bit vector और कई hash functions का उपयोग करती है, जो हर element से जुड़े bits को 1 पर सेट करते हैं
• filter का आकार और hash functions की संख्या के आधार पर error rate और performance तय होते हैं, और इन्हें उपयोग के अनुसार समायोजित किया जा सकता है
• इसमें सुझाए गए hash functions, optimal settings तय करने के तरीके, space efficiency, और वास्तविक उपयोग के उदाहरण भी शामिल हैं

---

Bloom Filter क्या है

• Bloom Filter एक data structure है जो किसी खास element की set में मौजूदगी को तेज़ी से और memory-efficient तरीके से जांचता है
• इस efficiency के लिए Bloom Filter एक probabilistic data structure है, इसलिए जांच का परिणाम "set में पक्का नहीं है" या "set में हो सकता है मौजूद हो" में से एक होता है
• Bloom Filter की मुख्य संरचना bit vector है
• किसी element को जोड़ते समय, उस element को कई बार hash करके संबंधित index के bits को 1 पर सेट किया जाता है
• अगर हर hash function से निकले index के सभी bits 1 हों, तो इसे "मौजूद हो सकता है" माना जाता है; नहीं तो इसे "पक्का नहीं है" माना जाता है

काम करने का उदाहरण

• कई hash functions (जैसे: Fnv, Murmur) के ज़रिए elements को कई bit indexes पर map किया जाता है
• element जोड़ते समय, निकले हुए indexes के bits को 1 में बदल दिया जाता है
• किसी खास element की मौजूदगी जांचते समय, अगर उसी hash functions से निकले सभी indexes 1 हों, तो उसे "मौजूद हो सकता है" माना जाता है
• अगर उनमें से एक भी bit 0 हो, तो यह निश्चित रूप से कहा जा सकता है कि वह "set में नहीं है"
• इसी वजह से false positive की संभावना पैदा होती है

उन्नत विषय

सावधानी: लेखक के पास बड़े पैमाने की service में Bloom Filter को वास्तव में लागू करने का अनुभव नहीं है

Hash function का चयन

• independent और uniform distribution वाले hash functions की सिफारिश की जाती है
• cryptographic hash functions (sha1 आदि) धीमे होते हैं, इसलिए वे उपयुक्त नहीं हैं
• तेज़ और सरल hash functions के उदाहरण हैं: Murmur, xxHash, Fnv, HashMix आदि
• एक वास्तविक उदाहरण में md5 से murmur पर बदलने से 800% से अधिक speed improvement मिला

Bloom Filter का आकार तय करना

• filter size (m) जितना बड़ा होगा, false positive rate उतना कम होगा
• false positive rate को आम तौर पर (1-e^(-kn/m))^k से approximate किया जा सकता है
• expected element count (n), filter size (m), और hash functions की संख्या (k) को संतुलित तरीके से तय करना चाहिए

Hash functions कितने हों?

• hash functions की संख्या जितनी अधिक होगी, speed उतनी कम होगी और filter उतनी जल्दी भर जाएगा
• बहुत कम होने पर false positive rate बढ़ जाता है
• ideal k को (m/n)ln(2) से निकाला जाता है
• design करते समय यह प्रक्रिया अपनाई जाती है:
  • expected element count n का अनुमान लगाएँ
  • bits की संख्या m तय करें
  • optimal k निकालें
  • देखें कि मनचाहा error rate मिल रहा है या नहीं; नहीं तो m को समायोजित करें

Performance और space efficiency

• Bloom Filter में element add/existence check की time complexity O(k) होती है
• space efficiency, स्वीकार्य error rate और elements की range पर निर्भर करती है
• अगर elements की range का मोटा अनुमान भी न लगाया जा सके, तो hash table या scalable Bloom Filter बेहतर हो सकता है

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

• विस्तृत उपयोग उदाहरणों के लिए Wikipedia देखें
• C. Titus Brown ने Bloom Filter के bioinformatics application cases प्रस्तुत किए हैं

संदर्भ सामग्री

• Broder, Mitzenmacher : Network Applications of Bloom Filters: A Survey — Bloom Filter का overview paper
• Wikipedia – Bloom Filter
• Kirsch, Mitzenmacher: Less Hashing, Same Performance
• Almeida आदि: Scalable Bloom Filters

[GN⁺]

Hacker News राय

• लगा कि यह लेख मेरे जैसे लोगों के लिए बिल्कुल सही है। नाम तो सुना था, लेकिन हर बार इसे देखना टालता रहा। इस बार लेख देखकर आखिरकार पढ़ा, और यह ठीक वैसा ही शुरुआती परिचय लगा जैसा मैं चाहता था
  • iBooks की search functionality implement करने के दौरान पहली बार Bloom filter के बारे में जाना था। यह बात अब 10 साल से भी पुरानी है
  • Bloom filter सच में बहुत मज़ेदार है। जब कोई समस्या हल करते हुए ऐसा मौका आता है कि Bloom filter की ज़रूरत पड़े, तो बहुत उत्साह होता है, लेकिन domain के हिसाब से ऐसे मौके कम आते हैं, यह थोड़ा अफ़सोसजनक है
• लेखक के लिए एक सुझाव। इंटरैक्टिव हिस्सा बहुत पसंद आया। Bloom filter की विशेषताओं को और अच्छी तरह समझाने के लिए ऐसा उदाहरण देना अच्छा होगा जहाँ दो strings में hash collision हो, फिर एक को input करके और दूसरे को दूसरे input box में डालकर दिखाया जाए। इससे यह समझना आसान होगा कि "यह सेट में है या नहीं, पक्का नहीं, लेकिन शायद है(maybe)" जैसी इसकी खास परिणाम-तर्कशैली क्यों आती है
  • उदाहरण के तौर पर "bloom" और "demonstrators " (अंत में space सहित) fnv: 7, murmur: 12 पर collision करते हैं
• 2009 में विश्वविद्यालय के दिनों में CUDA से Bloom filter implement करने का अनुभव रहा। मेरे advisor पहले Nvidia में थे। लेकिन career में मैं GPU programming से बिल्कुल अलग रास्ते पर चला गया। कभी-कभी लगता है कि कोई और चुनाव किया होता तो शायद 100 million dollar कमा सकता था
  • चूँकि यह computer science का 1970 का आइडिया है, शायद ऐसा संभव नहीं होता। GPGPU से जुड़े आइडिया पहले ही काफ़ी explore हो चुके लगते हैं। मैंने भी 10 साल पहले GPU पर Hashcash implement किया था, लेकिन अब देखता हूँ तो उसकी कीमत लगभग शून्य है
  • विश्वविद्यालय के graduation project में machine learning algorithm को CUDA पर port करने के बाद, यह सोचकर कि इसमें कुछ ख़ास नहीं, मैंने embedded programming की दिशा ले ली
  • मेरा भी ऐसा ही अनुभव है। 2009 में GeForce 8 और CUDA v1(!) के साथ शायद GPU-optimized bioinformatics toolkit सबसे पहले बनाया था। बस जिज्ञासा में बनाया, फिर पूरी तरह अलग रास्ते पर चला गया, और बड़ा पैसा कमाने का मौका चूक गया
  • मज़ाक में यह भी कहा गया कि अगर Bitcoin खरीद लिया होता तो और बड़ा पैसा बन सकता था
• एक ट्रिक है जो मुझे पसंद है। ऐसे छोटे set के लिए जिनमें elements कम हो सकते हैं लेकिन membership check बहुत बार होता है, 64-bit Bloom filter को बहुत सरल hash function के साथ जोड़कर रखना। यह बेवकूफ़ी जैसा लग सकता है, लेकिन इसकी cost इतनी कम है कि इसे एक तरह की बाज़ी की तरह इस्तेमाल किया जा सकता है। अगर फ़ायदा न भी हुआ तो membership check या insert में सिर्फ़ लगभग 10ns का overhead बढ़ता है, लेकिन सही बैठ जाए तो काम का बोझ बहुत कम कर सकता है
  • Chromium भी जगह-जगह ऐसे ट्रिक्स इस्तेमाल करता है। लेख में सिर्फ़ Safe Browsing का ज़िक्र है, लेकिन Blink layer में rapidhash और ऐसे micro-filters का काफ़ी सक्रिय उपयोग होता है। उदाहरण के लिए querySelector(), CSS bucket में hash lookup के prefilter, accessibility के लिए Aria attributes खोजते समय rapid reject वगैरह। 32-bit, 64-bit छोटे filter भी व्यवहार में अच्छी तरह काम करते हैं। बड़े Bloom filter भी ठीक से उपयोग किए जाते हैं, और मैंने भी ऐसे features सीधे जोड़े हैं
• हाल ही में log message anti-spam feature में Bloom filter इस्तेमाल करने का अनुभव रहा। Log messages को hash करके filter में डालते हैं, और अगर वह पहले से filter में हो तो उसे print नहीं करते। समय-समय पर filter के bits पूरी तरह clear कर दिए जाते हैं। Bits को atomically पूरी तरह clear करने की ज़रूरत नहीं होती; अगर message आते समय कुछ bits clear भी हो जाएँ, तो log बस फिर से छप जाएगा। पहले हर message के लिए अलग counter रखा जाता था, लेकिन यह तरीका कहीं ज़्यादा efficient था। इस काम के लिए Bloom filter को सीधे लागू करके बहुत संतोष मिला
• Bloom filter visualization के उदाहरण के लिए इस पेज के आख़िरी हिस्से में अच्छा material है
• Eli Bendersky द्वारा लिखा गया Bloom filter का एक और introductory लेख सुझाऊँगा। अगर और विस्तार से जानना हो तो यहाँ देखें
• मुझे लगता है कि Bloom filter, set, और hash table को समझने के लिए ज़रूरी concepts में लगभग 95% समानता है। Set असल में ऐसा hash table है जिसमें सिर्फ़ keys मायने रखती हैं, और Bloom filter ऐसा set है जो hashing की collision properties का जानबूझकर सक्रिय उपयोग करता है। इसमें ऐसी hash functions का उपयोग किया जाता है जिनमें collision होने की संभावना जानबूझकर रखी जाती है। अगर कोई specific key कभी डाली गई है, तो वह ज़रूर match करेगी। लेकिन उसी hash value को बनाने वाली कोई दूसरी key भी हो सकती है। इसलिए यह bug नहीं, बल्कि एक जानबूझकर रखा गया गुण है
  • मैं भी Bloom filter को कुछ-कुछ ऐसे देखता हूँ जैसे hash table में actual data हटाकर सिर्फ़ buckets को track किया जा रहा हो। यह देखकर अच्छा लगा कि इस तरह की mindset सिर्फ़ मेरी नहीं है
  • यह बात भी जोड़ना अच्छा होगा कि Bloom filter collisions कम करने के लिए कई hash functions का उपयोग करता है। उदाहरण के लिए, अगर 3 hash functions हैं तो तीनों को match होना चाहिए तभी मानेंगे कि item set में है। इसी संरचना की वजह से false positive की संभावना कम होती है, जबकि false negative कभी नहीं आता
  • अगर आपने Bloom filter समझ लिया, तो random projection या Locality Sensitive Hashes के कुछ implementations भी जल्दी समझ में आने लगेंगे
• Cassandra read spike debug करते समय Bloom filter के उपयोग में गहराई से उतरने का अनुभव रहा। मौजूद ही नहीं होने वाली key के लिए भी sstable lookups बहुत ज़्यादा हो रहे थे, जो अजीब लगा। बाद में समझ आया कि हर sstable के साथ लगे Bloom filter का क्या मतलब है। Default false positive rate 0.1 था, जो हमारी स्थिति के लिए बहुत ज़्यादा था। ज़्यादातर cache miss थे, और false positive की वजह से बेकार lookups बहुत अधिक हो रहे थे। Rate को 0.01 तक घटाया तो memory usage थोड़ा बढ़ा, लेकिन फ़ालतू reads काफ़ी कम हो गईं और p99 read latency 16~18% तक कम हो गई
• मुझे Bloom filter बहुत पसंद है। तकनीकी चर्चा में मैं हमेशा तीन मुख्य concepts बताता हूँ: Bloom filter, Random Weight Hashing(Rendezvous Hashing, Highest Random Weight Hashing), और Cumulative flow diagram। मेरा मानना है कि ये तीनों concepts जटिल distributed systems को चलाने के लिए आवश्यक हैं
  • मेरा मानना है कि distributed hash table structures भी उतना ही महत्वपूर्ण विषय है। उदाहरण के लिए circle, chord, CAN, kademlia जैसी अलग-अलग architectures