MapReduce सॉर्ट एल्गोरिदम कैसे काम करता है?

Question

मैपरेडस की शक्ति का प्रदर्शन करने में उपयोग किए जाने वाले मुख्य उदाहरणों में से एक Terasort benchmark है। मुझे MapReduce पर्यावरण में उपयोग किए गए सॉर्टिंग एल्गोरिदम की मूल बातें समझने में परेशानी हो रही है।

मुझे सॉर्ट करने के लिए बस अन्य सभी तत्वों के संबंध में किसी तत्व की सापेक्ष स्थिति निर्धारित करना शामिल है। तो सॉर्टिंग में "सबकुछ" के साथ "सबकुछ" की तुलना करना शामिल है। आपका औसत सॉर्टिंग एल्गोरिदम (त्वरित, बबल, ...) बस इसे स्मार्ट तरीके से करता है।

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

तो यह वास्तव में कैसे किया जाता है? यह MapReduce सॉर्टिंग एल्गोरिदम कैसे काम करता है?

मुझे समझने में मदद के लिए धन्यवाद।

Answer 1

यहाँ Hadoop's implementation for Terasort पर कुछ विवरण हैं:

TeraSort एक मानक नक्शा/प्रकार को कम करने, एन के एक क्रमबद्ध सूची का उपयोग करता है एक कस्टम विभाजक के अलावा है - 1 नमूना कुंजी है कि प्रत्येक के लिए महत्वपूर्ण अवधि का भी उल्लेख को कम । विशेष रूप से, नमूने जैसे सभी कुंजी [i - 1] < = कुंजी < नमूना [i] i को कम करने के लिए भेजा जाता है। ये गारंटी के उत्पादन को कम कर रहे हैं कि मैं सभी से भी कम समय के उत्पादन को कम i + 1। "

तो उनकी चाल तरह वे नक्शा चरण के दौरान कुंजी का निर्धारण किया जाता है। मूलतः वे यह सुनिश्चित करें कि हर मूल्य एक भी कम करने अन्य सभी reducers के खिलाफ 'पूर्व सॉर्ट किया' किए जाने की गारंटी है।

मैं James Hamilton's Blog Post के माध्यम से कागज संदर्भ पाया।

Answer 2

गूगल संदर्भ: MapReduce: Simplified Data Processing on Large Clusters

में प्रकाशित हुई:
OSDI'04: ऑपरेटिंग सिस्टम डिजाइन और कार्यान्वयन,
सैन फ्रांसिस्को, सीए, दिसंबर को छठी संगोष्ठी, 2004

उस लिंक में एक पीडीएफ और एचटीएमएल-स्लाइड संदर्भ है।

कार्यान्वयन संदर्भों के साथ Wikipedia page with description भी है।

इसके अलावा आलोचना,

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

Answer 3

बस अनुमान लगा ...

डेटा का एक विशाल सेट को देखते हुए, आप कुछ मात्रा में डेटा विभाजन होगा (रिकॉर्ड 1 यानी समानांतर में संसाधित करने के लिए शायद रिकॉर्ड संख्या से - 1000 = विभाजन 1, और शीघ्र)।

प्रत्येक विभाजन को क्लस्टर में किसी विशेष नोड को असाइन/शेड्यूल करें।

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

क्लस्टर नोड्स को "कम करने" के लिए मैपर (पिछले चरण) द्वारा हाथ से (शेड्यूल) कार्य पूरा करें। नोड क्लस्टर को कम करने के बाद प्रत्येक ए (एक्स) भागों के प्रकार को फिर से परिशोधित किया जाएगा, जो अकेले होते हैं जब अल lthe mapper कार्यों को पूरा किया जाता है (वास्तव में W/A से शुरू होने वाले सभी शब्दों को सॉर्ट करना शुरू नहीं कर सकता है जब अभी भी संभावना है कि अभी भी है बनाने में एक और मिनी विभाजन होने जा रहा है)। अंतिम क्रमबद्ध भाग में परिणाम आउटपुट (यानी सॉर्टेड-ए, सॉर्ट-बी, इत्यादि)

एक बार किया गया, सॉर्ट किए गए विभाजन को एक ही डेटासेट में फिर से मिलाएं। इस बिंदु पर यह एन फाइलों का एक साधारण संयोजन है (जहां एन 26 हो सकता है यदि आप केवल ए - जेड कर रहे हैं), आदि

बीच में मध्यवर्ती कदम हो सकते हैं ... मुझे यकीन नहीं है:)। अर्थात। प्रारंभिक कम कदम के बाद और नक्शा और कम करें।

Answer 4

मैं एक ही सवाल था गूगल के MapReduce कागज पढ़ते समय। @Yuval एफ का answer मेरी पहेली को काफी हल किया।

पेपर पढ़ने के दौरान मैंने देखा एक बात यह है कि जादू विभाजन में होता है (मानचित्र के बाद, कम करने से पहले)।

पेपर विभाजन उदाहरण के रूप में hash(key) mod R का उपयोग करता है, लेकिन यह अलग-अलग कार्यों को अलग करने के लिए मध्यवर्ती डेटा को विभाजित करने का एकमात्र तरीका नहीं है।

बस इसे पूरा करने के लिए @Yuval एफ के answer को सीमा की स्थिति जोड़ें: मान लीजिए मिनट (एस) और अधिकतम (एस) न्यूनतम कुंजी और नमूना चाबियाँ के बीच अधिकतम कुंजी है; सभी कुंजी < मिनट (एस) को एक कार्य को कम करने के लिए विभाजित किया जाता है; इसके विपरीत, सभी कुंजी> = अधिकतम (एस) को एक कार्य को कम करने के लिए विभाजित किया जाता है।

नमूना कुंजी पर कोई कठोर सीमा नहीं है, जैसे न्यूनतम या अधिकतम। बस, इन चाबियों को सभी चाबियों के बीच वितरित किया जाता है, इस वितरित प्रणाली के "समानांतर" और कम क्षमता वाले ऑपरेटर में मेमोरी ओवरफ्लो समस्या होती है।