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

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

कीं : इसका मतलब है कि हल किए गए आईपी पते 192.0.2.1 से एक अनुरोध क्लाउडफेयर डेटा सेंटर नंबर 107 में दर्ज किया गया था। यह डेटा कई स्रोतों से आया है, जिसमें हमारे सक्रिय और निष्क्रिय नमूने शामिल हैं, कुछ डोमेन के लॉग जो हमारे स्वयं के हैं (उदाहरण के लिए,)cloudflare.com), खुले स्रोत (उदाहरण के लिए, बीजीपी टेबल), आदि। एक ही लाइन आमतौर पर कई फाइलों में दोहराई जाती है।

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

यह कहने के लिए पर्याप्त है कि sortविभिन्न विन्यासों में टाइप के साधारण आदेशों के साथ डिडुप्लिकेटिंग लाइनें (देखें --parallel, --buffer-sizeऔर --unique) इतने बड़े डेटा सेट के लिए सबसे अच्छा नहीं था।

ब्लूम फिल्टर

सार्वजनिक क्षेत्र में डेविड एपस्टीन का चित्रण

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

यह ब्लूम फ़िल्टर के लिए एकदम सही है!

जब आपब्लूम फ़िल्टर पर विकिपीडियापढ़ रहे हैं, तो इस तरह से मैं इस डेटा संरचना को देखता हूं।

आपबहुलताको कैसे लागू करेंगे? एक आदर्श हैश फ़ंक्शन और अनंत स्मृति को देखते हुए, हम बस एक अनंत बिटमैप बना सकते हैं और प्रत्येक तत्व के लिए एक बिट संख्या निर्धारित कर सकते हैंhash(item)। यह "भीड़" के लिए आदर्श डेटा संरचना प्रदान करता है। सही? तुच्छता। दुर्भाग्य से, हैश फ़ंक्शन टकराते हैं, और अनंत स्मृति मौजूद नहीं होती है, इसलिए हमारी वास्तविकता में हमें समझौता करना होगा। लेकिन हम टकराव की संभावना की गणना कर सकते हैं और इस मूल्य का प्रबंधन कर सकते हैं। उदाहरण के लिए, हमारे पास एक अच्छा हैश फ़ंक्शन और 128 जीबी मेमोरी है। हम गणना कर सकते हैं कि प्रत्येक नए तत्व के लिए टक्कर की संभावना 1099511627776 में 1 है। जब अधिक तत्व जोड़े जाते हैं, तो बिटमैप के भर जाने पर संभावना बढ़ जाती है।

इसके अलावा, हम एक से अधिक हैश फ़ंक्शन लागू कर सकते हैं और एक सघन बिटमैप प्राप्त कर सकते हैं। यह वह जगह है जहां ब्लूम फ़िल्टर अच्छी तरह से काम करता है, जो चार चर के साथ गणितीय डेटा का एक सेट है:

n सम्मिलित तत्वों की संख्या (कार्डिनल संख्या)
m - बिटमैप द्वारा उपयोग की जाने वाली मेमोरी
k - प्रत्येक इनपुट के लिए गणना की गई हैश फ़ंक्शन की संख्या
p - झूठे सकारात्मक संयोग की संभावना

कार्डिनल संख्या nऔर झूठी सकारात्मकता की वांछित संभावना को देखते हुए p, ब्लूम फ़िल्टर आवश्यक मेमोरी mऔर आवश्यक संख्या में हैश फ़ंक्शन देता है k।

इस उत्कृष्ट थॉमस हर्स्ट दृश्य को देखें कि पैरामीटर एक दूसरे को कैसे प्रभावित करते हैं।

mmuniq-खिले

अंतर्ज्ञान द्वारा निर्देशित, मैंने अपने शस्त्रागार में संभाव्य उपकरण mmuniq-bloom जोड़ा, जो इनपुट STDIN लेता है और STDOUT में केवल अद्वितीय लाइनें देता है। यह sort+ के संयोजन से बहुत तेज होना चाहिए uniq!

वह वहाँ है:

mmuniq-bloom.c

सादगी और गति के लिए, मैंने शुरू में कुछ मापदंडों को निर्धारित किया है। सबसे पहले, जब तक अन्यथा नहीं कहा जाता है, mmuniq-bloom आठ हैश फ़ंक्शन k = 8 का उपयोग करता है। यह हमारे डेटा आकार के लिए इष्टतम संख्या के करीब लगता है, और हैश फ़ंक्शन जल्दी से आठ सभ्य हैश का उत्पादन कर सकता है। फिर हम mबिटमैप में मेमोरी को एक महंगे ऑपरेशन से बचने के लिए दो की शक्ति में संरेखित करते हैं %modulo, जो कोडांतरक में धीमी गति से आता है div। यदि सरणी दो की शक्ति के बराबर है, तो हम बस बिटवाइज़ और (मज़े के लिए, यह पढ़ सकते हैं कि कंपाइलर कुछ डिवीजनों के संचालन को एक जादू स्थिरांक से गुणा करके कैसे अनुकूलित करते हैं )।

अब हम इसे उसी डेटा फ़ाइल पर चला सकते हैं जिसका हमने पहले उपयोग किया था:

ओह, यह बहुत बेहतर है! दो मिनट के बजाय 12 सेकंड। कार्यक्रम एक अनुकूलित डेटा संरचना, स्मृति की एक अपेक्षाकृत सीमित मात्रा, अनुकूलित लाइन पार्सिंग और अच्छा आउटपुट बफ़रिंग का उपयोग करता है ... और इस सब के साथ, उपकरण की तुलना में 12 सेकंड अनंत काल की तरह लगता है wc -l:

क्या हो रहा है? मैं समझता हूं कि wcअद्वितीय तारों की गणना की तुलना में स्ट्रिंग्स की गिनती करना आसान है, लेकिन क्या 26-बार का अंतर वास्तव में उचित है? सीपीयू क्या लेता है mmuniq-bloom?

कंप्यूटिंग हैश के लिए होना चाहिए। उपयोगिता wcप्रोसेसर को खर्च नहीं करती है, 40 मिलियन लाइनों में से प्रत्येक के लिए यह सब अजीब गणित कर रहा है। मैं एक गैर-तुच्छ हैश फ़ंक्शन का उपयोग करता हूं siphash24, यह सुनिश्चित करने के लिए कि यह प्रोसेसर को जलाता है, है ना? चलो केवल हैश फ़ंक्शन चलाकर सत्यापित करें, लेकिन नहींब्लूम फ़िल्टर के साथ कोई संचालन नहीं करना:

यह अजीब है। हैश फ़ंक्शन की गणना में केवल दो सेकंड लगते हैं, हालांकि पिछले रन में पूरे कार्यक्रम को 12 सेकंड के लिए निष्पादित किया गया था। क्या एक ब्लूम फ़िल्टर 10 सेकंड के लिए काम करता है? यह कैसे हो सकता है? यह एक ऐसी सरल डेटा संरचना है ...

गुप्त हथियार - प्रोफाइलर

इस कार्य के लिए सही उपकरण को लागू करने का समय आ गया है - चलो प्रोफाइलर चलाएं और देखें कि प्रोसेसर क्या काम कर रहा है। पहले, आइए straceयह सत्यापित करने के लिए चलें कि कोई अनपेक्षित सिस्टम कॉल नहीं है:

सब कुछ अच्छा लग रहा है। mmap4 एमएस प्रत्येक (3971 μs) के लिए दस कॉल पेचीदा हैं, लेकिन यह ठीक है। हम स्मृति को पहले से भर देते हैं MAP_POPULATE, बाद में पृष्ठ की कमी के कारण त्रुटियों को रोकते हैं।

अगला कदम क्या है? बेशक यह है perf!

फिर परिणाम देखें:

इसलिए, हम मुख्य कोड में 87.2% चक्र जलाते हैं। आइए देखें कि वास्तव में कहां है। टीम perf annotate process_line --sourceतुरंत कुछ अप्रत्याशित दिखाती है।

हम देखते हैं कि प्रोसेसर का 26.90% जल गया हैmov, लेकिन वह सब नहीं है! संकलक सही ढंग से फ़ंक्शन सम्मिलित करता है और लूप का विस्तार करता है। यह पता चला है कि अधिकांश चक्र इस movया लाइन पर जाते हैं uint64_t v = *p!

स्पष्ट रूप से सही गलत है, इतने सारे संसाधनों को इतनी सरल स्ट्रिंग कैसे ले सकती है? लेकिन किसी अन्य प्रोफाइलर के साथ परीक्षण को दोहराना उसी समस्या को दर्शाता है। उदाहरण के लिए, मैं रंगीन आरेखों के कारण kcachegrind के साथ google-perftools का उपयोग करना पसंद करता हूं:

विज़ुअलाइज़ेशन का परिणाम निम्नानुसार है:

मुझे संक्षेप में बताएं कि हमने अब तक क्या खोज की है।

मानक उपयोगिता wc0.45 s प्रोसेसर समय के लिए 600 MiB फ़ाइल संसाधित करती है। हमारा अनुकूलित टूल mmuniq-bloom12 सेकंड चलता है। प्रोसेसर को एक निर्देश पर जलाया जाता है mov, मेमोरी को डीरेल करना ...

जोस निकदाओ की छवि , CC BY / 2.0

ओह! मैं कैसे भूल सकता हूं। स्मृति तक यादृच्छिक पहुँचवास्तव मेंधीमी है! बहुत, बहुत, बहुत धीमा!संख्याओं के

अनुसारप्रत्येक प्रोग्रामर को पता होना चाहिए, रैम की एक सिंगल एक्सेस में लगभग 100 एनएस होती है। चलो गिनते हैं: 40 मिलियन लाइनें, 8 हैश प्रत्येक। चूंकि हमारे ब्लूम फ़िल्टर का आकार 128 MiB है,हमारे पुराने हार्डवेयर परयह L3 कैश में फिट नहीं होता है! हैश को समान रूप से मेमोरी की एक विस्तृत श्रृंखला में वितरित किया जाता है - उनमें से प्रत्येक कैश मिस उत्पन्न करता है। यह सब एक साथ रखो, और यह पता चला है ...

यह पता चला है कि 32 सेकंड केवल मेमोरी एक्सेस पर जलते हैं। असली कार्यक्रम सिर्फ 12 सेकंड में फिट बैठता है, क्योंकि ब्लूम फिल्टर अभी भी कैशिंग से लाभान्वित करता है। यह देखने में आसान है perf stat -d:

हाँ, हमारे पास न्यूनतम 320 मिलियन कैश मिस (एलएलसी-लोड-मिसेस) होना चाहिए था, लेकिन केवल 280 मिलियन हुआ: यह अभी भी यह नहीं बताता है कि कार्यक्रम ने केवल 12 सेकंड में काम क्यों किया। लेकिन यह बात नहीं है। यह महत्वपूर्ण है कि कैश मिस की संख्या एक वास्तविक समस्या है, और हम इसे केवल मेमोरी एक्सेस की संख्या को कम करके हल कर सकते हैं। चलो केवल एक हैश फ़ंक्शन का उपयोग करने के लिए ब्लूम फ़िल्टर को कॉन्फ़िगर करने का प्रयास करें:

Ay! यह वास्तव मे आघात देता है! 1 प्रति 10,000 लाइनों की टक्कर की संभावना पाने के लिए, ब्लूम फिल्टर को 64 गीगाबाइट मेमोरी की आवश्यकता होती है। यह भयानक है!

इसके अलावा, ऐसा नहीं लगता है कि गति में काफी वृद्धि हुई है। हमारे लिए मेमोरी तैयार करने में ऑपरेटिंग सिस्टम को 22 सेकंड का समय लगा, लेकिन हमने अभी भी यूजर स्पेस में 11 सेकंड का समय बिताया। मेरा मानना है कि अब मेमोरी तक पहुंचने के दुर्लभ लाभ के सभी लाभों की भरपाई तेजी से बढ़ी हुई मेमोरी साइज के कारण कैश में होने की कम संभावना से होती है। इससे पहले, ब्लूम फिल्टर के लिए 128 MiB पर्याप्त था!

ब्लूम फिल्टर को मना करना

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

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

बेशक, आप जटिल डेटा संरचनाओं को लागू कर सकते हैं, जैसे कोयल फ़िल्टर , लेकिन निश्चित रूप से एक आसान विकल्प है। क्या अच्छा पुराने रैखिक जांच हैश तालिका के बारे में? वादिम पोदन

का चित्रण

ममुनिअक-हैश से मिलो

यहाँ हैश तालिका का उपयोग करके mmuniq-bloom का नया संस्करण है:

mmuniq-hash.c

ब्लूम फ़िल्टर के लिए बिट्स के बजाय, अब हम 'siphash24' फ़ंक्शन से 64-बिट हैश को स्टोर करते हैं । यह हैश टक्करों के खिलाफ बहुत बेहतर सुरक्षा प्रदान करता है: प्रति 10,000 लाइनों में से एक से बेहतर।

गिनती करते हैं। हैश टेबल में एक नया आइटम जोड़ना, 40 मिलियन प्रविष्टियों के साथ, हैश टकराव की संभावना देता है 40 000 000/2^64। यह 461 बिलियन में लगभग 1 है - काफी कम संभावना है। लेकिन हम पहले से भरे सेट में एक तत्व नहीं जोड़ते हैं! इसके बजाय, हम शुरू में खाली सेट में 40 मिलियन पंक्तियों को जोड़ते हैं। जन्मदिन के विरोधाभास के अनुसार , इससे टकराव की संभावना बढ़ जाती है। एक उचित अनुमान एक अनुमान होगा '~n^2/2m, हमारे मामले में यह है~(40M^2)/(2*(2^64))। यह 23,000 में से एक मौका देता है। दूसरे शब्दों में, एक अच्छे हैश फ़ंक्शन के साथ, हम 40 मिलियन तत्वों के 23,000 यादृच्छिक सेटों में से एक में टक्कर की उम्मीद करते हैं। यह एक गैर-शून्य संभावना है, लेकिन ब्लूम फ़िल्टर की तुलना में अभी भी बेहतर है, और यह हमारे उपयोग के मामले के लिए पूरी तरह से सहन करने योग्य है।

हैश टेबल के साथ कोड तेजी से काम करता है, इसमें बेहतर मेमोरी एक्सेस पैटर्न और ब्लूम फ़िल्टर की तुलना में झूठी सकारात्मकता की कम संभावना है।

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

पिछले उदाहरण से, हम जानते हैं कि हमारे हैश फ़ंक्शन में लगभग दो सेकंड लगते हैं। हम निष्कर्ष निकालते हैं कि 40 मिलियन मेमोरी एक्सेस में लगभग चार सेकंड लगते हैं।

सीख सीखी

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

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

यह कहना उचित है कि ब्लूम फ़िल्टर L3 कैश में रखे जाने पर शानदार प्रदर्शन करते हैं। लेकिन अगर नहीं, तो वे भयानक हैं। यह खबर नहीं है: ब्लूम फिल्टर को मेमोरी की मात्रा के लिए अनुकूलित किया जाता है, न कि उस पर कॉल की संख्या के लिए। उदाहरण के लिए, देखेंकोयल फिल्टर पर वैज्ञानिक लेख ।

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

एक सहयोगी अक्सर कहता है: “यह माना जा सकता है कि आधुनिक प्रोसेसर असीम रूप से तेज़ हैं। वे अनंत गति से काम करते हैं, जब तक कि वे स्मृति की दीवार के खिलाफ आराम नहीं करते । ”

अंत में, मेरी गलती न दोहराएं। आपको हमेशा पहले प्रोफाइलिंग करने की जरूरत हैperf stat -dऔर आईपीसी काउंटर (प्रति चक्र निर्देश) देखें। यदि यह एक से कम है, तो इसका आमतौर पर मतलब है कि कार्यक्रम मेमोरी के इंतजार में अटक गया है। इष्टतम मान दो से ऊपर हैं। इसका मतलब है कि कार्यभार मुख्य रूप से सीपीयू पर है। दुर्भाग्य से, मेरे कार्यों में, आईपीसी अभी भी कम है ...

सुपीरियर mmuniq

सहकर्मियों की मदद से, मैंने हैश टेबल पर आधारित mmuniq टूल का बेहतर संस्करण लिखा। यहाँ कोड है:

mmuniq.c

यह गतिशील रूप से हैश तालिका के आकार को बदल सकता है, एक मनमाना कार्डिनल नंबर के साथ इनपुट का समर्थन करता है। फिर यह prefetchसीपीयू में संकेत का उपयोग करके, पैकेट में डेटा को संसाधित करता है, जो 35-40% तक कार्यक्रम को गति देता है। सावधान रहें, prefetchकोड में प्रचुर मात्रा में उपयोग शायद ही कभी प्रभाव देता है। इस फ़ंक्शन का उपयोग करने के लिए, मैंने विशेष रूप से एल्गोरिदम को फिर से व्यवस्थित किया। सभी सुधारों के साथ, निष्पादन का समय घटकर 2.1 सेकंड हो गया:

समाप्त

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

जब खिलने वाला फिल्टर फिट नहीं होता है