Bloomfilter और कैसेंड्रा = इस्तेमाल क्यों किया जाता है और क्यों टुकड़ों में बंटी कई बार?

Question

मैं इस पढ़ें: http://spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html

मेरे सवाल:

1.) यह सही है, कि कैसेंड्रा केवल, खिलने फिल्टर का उपयोग करता है एसएसटी (छाँटे गए स्ट्रिंग तालिका पता लगाने के लिए), जो सबसे अधिक संभावना कुंजी है ? जैसा कि कई एसएसटी हो सकते हैं और कैसंद्रा को पता नहीं है कि कौन सी एसएसटी एक कुंजी हो सकती है? तो इसे गति देने के लिए सभी एसएसटी ब्लूमफिल्टर का उपयोग किया जाता है। क्या ये सही है? (मुझे समझ में कैसे काम करता है कैसेंड्रा कोशिश कर रहा हूँ ...)

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

3.) MD5 का उपयोग करना कितना बड़ा SHA1 (जो लेख के अनुसार की तुलना में "Bloomfilter का उपयोग करके Fales सकारात्मक" के अंतर यादृच्छिक वितरित किया जाता है है)? एमडी 5 यादृच्छिक वितरित क्यों नहीं है? बहुत ज्यादा

धन्यवाद !! जेन्स

Answer 1

1) हाँ, कैसेंड्रा विकि में this देखते हैं,

कैसेंड्रा आईओ को बचाने के लिए जब एक प्रमुख लुकअप खिलने फिल्टर का उपयोग करता है: प्रत्येक SSTable इसके साथ जुड़े एक खिलने फिल्टर कैसेंड्रा करने से पहले की जाँच करता है कि है किसी भी डिस्क की तलाश है, जो कि लगभग

columns of a key कई sstables में फैल सकता है। यदि यह खिलने वाले फ़िल्टरों के लिए नहीं था, तो प्रत्येक कुंजी के प्रत्येक पढ़ने को प्रत्येक स्टेस्टेबल को पढ़ना होगा, जो कि निषिद्ध रूप से महंगा है। ब्लूम फ़िल्टर का उपयोग करके, कैसंड्रा को लगभग हमेशा उस सारणी को देखना पड़ता है जिसमें उस कुंजी के लिए डेटा होता है।

2) This आप खिलने फिल्टर का एक बेहतर समझ दे सकता है। आकार एम की एक सरणी में स्वतंत्र पदों को देने के लिए आपके पास हैश के समय। उदाहरण के लिए, अगर ए और बी सेट में तत्वों हैं, और आप कश्मीर = 2, अपने हैश फंक्शन md5 और SHA1, और मीटर = 16 हैं, तो आप

md5(A) % m = 7 
sha1(A) % m = 12 

md5(B) % m = 15 
sha1(B) % m = 12 

यह आपको m [7 देता कर सकते हैं ], एम [12] और एम [15] फिल्टर के लिए सच हैं।

अगर सी सेट में है, तो आप कर देखने के लिए

md5(C) % m = 8 
sha1(C) % m = 12 

के बाद से मीटर [8] गलत है, आप जानते हैं कि सी डी

md5(D) % m = 7 
sha1(D) % m = 15 

के लिए, सेट में नहीं है फिर भी, एम [7] और एम [15] दोनों सत्य हैं, लेकिन डी सेट में नहीं है, इसलिए डी एक झूठी सकारात्मक है।

इसकी लागत सीपीयू चक्र है, लेकिन आप कम आईओओ के लिए सीपीयू चक्र व्यापार कर रहे हैं, जो कैसंद्रा के लिए समझ में आता है।

3) लेख md5 उल्लेख नहीं है। एमडी 5 यादृच्छिक रूप से वितरित किया गया है, और मुझे लगता है कि ब्लूम फिल्टर के लिए एमडी 5 और शा -1 के बीच का अंतर बड़ा नहीं है।

Answer 2

sbridges द्वारा उत्तर के तीसरे बिंदु के अतिरिक्त के रूप में।

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

गैर-क्रिप्टोग्राफिक हैश फ़ंक्शंस जैसे मुर्मूर हैश का उपयोग करने की अनुशंसा की जाती है। This paper, निर्माण करने के लिए और हैश फंक्शन की तरह सलाह देता है:

g(x) = h1(x) + i * h2(x) 

जहां g (x) नई हैश फंक्शन, h1 और h2 मानक हैश फंक्शन कर रहे हैं और मैं 0 से कश्मीर को लेकर यात्रा की संख्या है।

इस तकनीक का उपयोग करके, उसी प्रदर्शन को दो हैश फ़ंक्शंस (K> 2 मानते हुए) के साथ पहुंचा जा सकता है।