मेमोरी और प्रोसेसर की क्षमताओं से परे MapReduce या गणना (मैं zaumi के बिना कोशिश करूँगा)

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

मुझे तुरंत कहना चाहिए - एक विषय - उन लोगों के लिए, जिन्होंने यह पता नहीं लगाया है कि MapReduce क्या है। उन लोगों के लिए जो समझ गए - यहां कुछ भी उपयोगी नहीं होगा।

चलिए शुरू करते हैं कि MapReduce का विचार मेरे लिए व्यक्तिगत रूप से कैसे पैदा हुआ (हालांकि मुझे नहीं पता था कि इसे इस तरह से बुलाया गया था, और निश्चित रूप से, यह Google की तुलना में बहुत बाद में मेरे पास आया था)।

सबसे पहले, मैं वर्णन करूंगा कि वह कैसे पैदा हुई (दृष्टिकोण गलत था), और फिर इसे सही कैसे किया जाए।

विकिपीडिया पर सभी शब्दों को कैसे गिना जाए (गलत दृष्टिकोण)

और वह पैदा हुआ था, जैसा कि, शायद, हर जगह - शब्दों की आवृत्ति की गिनती के लिए जब सामान्य स्मृति पर्याप्त नहीं होती है (विकिपीडिया पर सभी शब्दों की आवृत्ति की गिनती)। शब्द "फ़्रीक्वेंसी" के बजाय संभवतः "आवृत्तियों की संख्या" होनी चाहिए, लेकिन सादगी के लिए मैं "फ़्रीक्वेंसी" छोड़ दूंगा।

सरलतम मामले में, हम एक हैश (तानाशाह, नक्शा, हैश, सहयोगी सरणी, सरणी) (PHP) में बना सकते हैं और उसमें शब्दों को पढ़ सकते हैं।

$dict['word1'] += 1

लेकिन क्या करें जब हैश के तहत मेमोरी समाप्त हो जाए, और हमने सभी शब्दों में से केवल एक सौवां गिना?

मैंने इस समस्या को शब्दों के भाग को गिनकर हल किया जब तक कि स्मृति बाहर नहीं जाती, हैश को डिस्क पर सहेजा जाता है। यह है, फ़ाइल के लिए लाइन से सीधे लाइन:

aardvark | 5
aachen | 2

एक समस्या थी - इन फाइलों को कैसे मर्ज किया जाए? आखिरकार, उनमें से प्रत्येक पूरी रैम पर कब्जा कर लेता है।

सबसे पहले प्रत्येक फ़ाइल से केवल सबसे लोकप्रिय 1,000,000 शब्द लेने और उन्हें संयोजित करने का विचार था - यह रैम में फिट होगा और कम से कम सूची के शीर्ष (सबसे लोकप्रिय शब्द) को गिना जाएगा। यह, निश्चित रूप से, काम किया, लेकिन यह पता चला कि लाखों निचले शब्द खो गए थे, और बहुत कुछ था।

फाइलों को छांटने का आइडिया आया।

फिर हम 20 सॉर्ट की गई फ़ाइलों को लेते हैं, उनमें से प्रत्येक से पहली 1000 पंक्तियों को पढ़ें, वे एक ही शब्द (सॉर्ट की गई फ़ाइलों) के बारे में होंगे। हम एक नए हैश का सारांश बनाते हैं, इसमें केवल "आ ..." और इसी तरह से शुरू होने वाले शब्द होंगे, इसे नई फ़ाइलों में सहेजें। हम अगली 1000 पंक्तियों को पढ़ते हैं, सभी समान हैं। वहां, लगभग सभी फाइलों में "आब ..." शब्द होंगे।

इस प्रकार, एक नई फ़ाइल बहुत छोटी बनती है। हालाँकि, इसमें अभी भी शब्दों को दोहराया जाएगा। इसे फिर से सॉर्ट करें, इसे 1000 लाइनों में पढ़ें, जोड़ें। यह लगभग सही फ़ाइल हो जाएगी (कुछ शब्द अभी भी 1000 लाइनों से परे हो सकते हैं), हम कुछ समय दोहराते हैं ... अंत में हमें एक फ़ाइल मिलती है जिसमें बहुत कम त्रुटियां होती हैं (लेकिन वे हैं)।

एक सुनसान, लंबा, लेकिन बेहतर विकल्प नहीं हुआ।

गलत दृष्टिकोण का कमजोर बिंदु

इस दृष्टिकोण में एक कमजोर बिंदु था - अर्थात्, मूल 20 फ़ाइलों का संयोजन। इसे बेहतर कैसे बनाया जाए?

समस्या इस तथ्य से उत्पन्न होती है कि कुछ शब्द कुछ फाइलों में नहीं होंगे या वे 1000 लाइनों के विभिन्न ब्लॉकों में होंगे। यही है, अगर मैं सभी 1000 फ़ाइलों को पहली 1000 लाइनों से नहीं, बल्कि केवल एक लाइन से ले सकता हूं, लेकिन एक ही शब्द के साथ, मैं सभी 20 फ़ाइलों को एक पास में जोड़ सकता हूं।



यह कैसे करना है? सामान्य तौर पर, यह मर्जर्ट एल्गोरिथ्म का अंतिम चरण है - क्रमबद्ध सूचियों का संयोजन। यदि आप जानते हैं, तो इसे छोड़ें।

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

MapReduce अपने सरलतम रूप में

वास्तव में, इसलिए मैंने लगभग अपने लिए आविष्कार किया कि Google ने एक दशक पहले मुझसे पहले क्या आविष्कार किया और मैपरेड्यूस कहा।

साइकिल का आविष्कार आज भी जारी है।

तो एक पंक्ति है : "foo bar baz bar" ।

आउटपुट पर प्राप्त करना आवश्यक है: { foo: 1, bar: 2, baz: 1 } ।

पहला कदम, हम एक पंक्ति लेते हैं, इसे शब्दों में तोड़ते हैं और इस तरह के सरणियों का उत्पादन करते हैं (या बल्कि: "ट्यूपल्स" - "ट्यूपल्स"):

[ 'foo', 1 ]
[ 'bar', 1 ]
[ 'baz', 1 ]
[ 'bar', 1 ]

(आगे मैं कोष्ठक और उद्धरण चिह्नों को छोड़ दूंगा जहां यह पहले से स्पष्ट होगा)
हम उन्हें लेते हैं, उन्हें क्रमबद्ध करते हैं:

bar, 1
bar, 1
baz, 1
foo, 1

हम देखते हैं कि बार एक पंक्ति में दो बार जाता है, इसलिए हम इसे इस रूप में संयोजित करते हैं:

bar, (1,1)
baz, (1)
foo, (1)

(1,1) एक प्रकार का नेस्टेड सरणी है, जो कि तकनीकी रूप से है - यह इस तरह है: ["bar", [1,1]] ।

फिर हम बस सरणियों के दूसरे तत्वों को जोड़ते हैं । हमें मिलता है:

bar, 2
baz, 1
foo, 1

बिल्कुल वही जो वे चाहते थे।

मुख्य सवाल यह है कि एक बकरी बटन समझौते के लिए क्या है ... या हमने यहां क्या किया और क्यों?

वापस अतीत में

यदि हम कल्पना करते हैं कि हमारे पास एक कंप्यूटर है जिसमें केवल 2 लाइनें फिट हैं और यह प्रति मिनट प्रति लाइन केवल एक ऑपरेशन कर सकता है । (गिग्लिंग को रोकने के लिए! कम से कम एक बार विकिपीडिया पर सभी शब्दों को गिनने के बाद - आपके पास निर्धारित मेमोरी सीमा पर हंसने का अधिकार होगा, यह अभी भी फिट नहीं होगा, भले ही आपके पास कितने गीग हो, और यदि यह टूट जाए, तो पूरे इंटरनेट पर विचार करें :))।

हम कर सकते हैं ( "foo bar baz bar" ) दो फाइलें इस तरह से बनाएं:

file1.txt
[ 'bar', 1 ]
[ 'foo', 1 ]

file2.txt
[ 'bar', 1 ]
[ 'baz', 1 ]


हमारी मेमोरी में हमारी दो लाइनें हैं - सब कुछ क्रम में है, वे मेमोरी सीमा में फिट होते हैं।

अब MergeSort के चरण का उपयोग करके, हम इन फ़ाइलों को लाइन द्वारा जोड़ सकते हैं:

bar, (1,1)
baz, (1)
foo, (1)

उसी समय, हमारी स्मृति में हर बार हमारे पास 2 फ़ाइलों की केवल दो पंक्तियाँ संग्रहीत होती हैं - अधिक और आवश्यक नहीं।

दरअसल, हमने जो किया वह पहले से ही MapReduce है।

वह कदम, जो शब्दों ( , 1 ) से लोगों के साथ सरणियों का उत्पादन करता है - इस कदम को "मैप" कहा जाता है ।
चरण (1,1) सारांश (1,1) जो (1,1) "कम" कदम है ।

बाकी चरणों को एल्गोरिथ्म खुद (मर्जसॉर्ट के माध्यम से छांटना और संयोजन करना) करेगा।

नक्शा, कम करें यह क्या है

ये चरण स्वयं "मानचित्र" के मामले में इकाइयों को जारी करने या "कमी" के मामले में तह करने के लिए आवश्यक नहीं हैं। ये केवल कार्य हैं जो कुछ को स्वीकार कर सकते हैं और दे सकते हैं। उद्देश्य पर निर्भर करता है।

इस मामले में, "मैप" एक फ़ंक्शन है जिसे आपने लिखा है जो एक शब्द लेता है और उत्पन्न करता है (, 1) ।

और "कम करें" एक ऐसा फ़ंक्शन है जिसे आपने लिखा है कि एक सरणी (, (1,1)) और उत्पादन (, 2) लेता है।

बस पायथन में डाल दिया:

  शब्द = ["फू", "बार", "बाज"]
 def1 (शब्द):
   वापसी [शब्द, 1]

 गिरफ्तार = ["फू", [1,1]]
 def1 कम करें (गिरफ्तार करें):
   वापसी [गिरफ्तार [0], राशि (गिरफ्तारी [1])] 

या PHP:

  $ शब्द = सरणी ("फू", "बार", "बाज")
 फ़ंक्शन मैप 1 ($ शब्द) {
   रिटर्न ऐरे ($ शब्द, 1);
 }

 गिरफ्तारी = सरणी ("फू", सरणी (1,1))
 फ़ंक्शन कम 1 (गिरफ्तार) {
   वापसी सरणी ($ गिरफ्तार [0], array_sum ($ गिरफ्तारी [1]));
 } 

तो, हमने मेमोरी लिमिट को बायपास कर दिया है, लेकिन स्पीड लिमिट को कैसे बायपास करें?

कल्पना कीजिए कि हमारे पास दो ऐसे कंप्यूटर हैं। हम उनमें से प्रत्येक को एक प्रारंभिक रेखा देते हैं और पहले से कहते हैं (अधिक सटीक रूप से, MapReduce कहते हैं): केवल विषम स्थानों में शब्दों की गिनती करें, और दूसरे के लिए - यहां तक ​​कि केवल शब्दों की गिनती करें।

पहला उत्पादन:
"foo bar baz bar":
foo, 1
baz, 1

दूसरा उत्पादन:
"foo bar baz bar":
bar, 1
bar, 1

हम (अधिक सटीक रूप से MapReduce) दोनों से परिणाम लेते हैं, सॉर्ट करते हैं, फिर ऊपर के रूप में मर्जर्ट के माध्यम से चलाते हैं:

bar, (1,1)
baz, (1)
foo, (1)

बिल्कुल वैसा ही परिणाम जब आप एक कंप्यूटर गिना!

अब हम (MapReduce) इसे दो कंप्यूटरों में फिर से वितरित कर रहे हैं: पहला हम केवल विषम रेखाएँ देते हैं, दूसरा - यहां तक ​​कि और हम प्रत्येक कंप्यूटर को Reduce step (दूसरा अंक जोड़ने) के लिए कहते हैं।

दरअसल, यह स्पष्ट है कि ये रेखाएं एक-दूसरे से स्वतंत्र हैं, इसलिए परिणाम फिर से वही होगा जो आपको चाहिए।

मुख्य बात यह है कि दो कंप्यूटरों ने समानांतर में काम किया और इसलिए, उनमें से एक से दो गुना तेज (डेटा को एक से दूसरे में स्थानांतरित करने के लिए समय की हानि को छोड़कर)।

समय से पहले वापसी

Fuf! इसलिए MapReduce - किसी चीज़ को पढ़ने के लिए इसकी ज़रूरत होती है, जिसे या तो तेज़ी से करने की ज़रूरत होती है, या जिसके लिए पर्याप्त मेमोरी (या तो, और वह) नहीं होती है।

एक और दिलचस्प उदाहरण लोकप्रियता द्वारा छंटनी है (कैस्केड)

मान लीजिए कि हम विकिपीडिया पर शब्दों की संख्या गिनना चाहते हैं और साथ ही साथ उनकी लोकप्रियता के रिवर्स ऑर्डर में एक सूची बनाते हैं - सबसे लोकप्रिय से सबसे अलोकप्रिय तक।

यह स्पष्ट है कि विकिपीडिया के सभी शब्द स्मृति में फिट नहीं होंगे, और फिर वापसी के लिए यह विशाल सरणी स्मृति में फिट नहीं होगी। हमें MapReduce के कैस्केड की आवश्यकता है - पहला MapReduce का परिणाम दूसरे MapReduce के इनपुट पर जाएगा।

ईमानदार होने के लिए - मुझे नहीं पता कि "कैस्केड" शब्द सही है, यह विशेष रूप से MapReduce पर लागू होता है। मैं अपने लिए इस शब्द का उपयोग करता हूं क्योंकि यह बताता है कि किसी अन्य को ऐसा करने की आवश्यकता नहीं है (शब्दों के एक झरने का परिणाम MapReduce में पड़ता है और कैस्केड तुरंत दूसरे MapReduce में आता है)।

ठीक है, शब्दों की गिनती कैसे करें - हम पहले से ही जानते हैं:

"फू बार बाज फू"

हमारे द्वारा लिखा गया नक्शा कदम:
foo, 1
bar, 1
baz, 1
foo, 1

इसके अलावा MapReduce को जोड़ती है (खुद, आप नहीं, एक प्रोग्रामर के रूप में) उन्हें:
bar, (1)
baz, (1)
foo, (1,1)

और हमारे द्वारा लिखा गया कदम कम करें:
bar, 1
baz, 1
foo, 2

अब कल्पना कीजिए कि हमने पूरे विकिपीडिया पर विचार किया और इस सरणी में अरबों और अरबों शब्द हैं। स्मृति में इसे क्रमबद्ध करें काम नहीं करता है। आइए एक और MapReduce लेते हैं , इस बार Map इस चाल को करेगा:

[, 15] -> नक्शा () रिटर्न -> [-15, ]
[2, 15] -> नक्शा () रिटर्न -> [-15, 2]
[3, 120] -> नक्शा () रिटर्न -> [-120, 3]
[4, 1] -> मैप () रिटर्न -> [-1, 4]

यह किस लिए है?

MapReduce, आपके Reduce में जाने से पहले, सरणी के पहले तत्व (जो एक ऋणात्मक संख्या के बराबर है) द्वारा इन सभी सरणियों को छाँटेगा। यदि डेटा की पूरी मात्रा मेमोरी में फिट नहीं होती है, तो भी MapReduce को क्रमबद्ध किया जा सकेगा - यही सौंदर्य है। सभी विकिपीडिया शब्दों के लिए, आप केवल arsort($words) नहीं कर सकते, लेकिन MapReduce कर सकते हैं।

संख्याओं के सामने माइनस क्यों है?

क्योंकि MapReduce हमेशा बढ़ते क्रम में सॉर्ट करेगा, लेकिन हमें अवरोही क्रम में जाने की आवश्यकता है। फिर, आरोही क्रम में छंटनी का उपयोग करते हुए, घटते क्रम में संख्याओं को कैसे छांटें? छंटाई से पहले माइनस एक से गुणा करें और एक के बाद फिर से माइनस करें।

आरोही सकारात्मक संख्या: 1, 15, 120
आरोही क्रम में ऋणात्मक संख्याएँ: -120, -15, -1 (हमें क्या चाहिए केवल एक शून्य चिह्न के साथ, जिसे हम तब -1 से गुणा करके हटाते हैं)

निम्नलिखित चीज़ घटेगी इनपुट पर:

-120, (3)
-15, (, 2) <-- - MergeSort !
-1, (4)

लवली, लेकिन हमारे दो शब्दों में 15 की "आवृत्ति" थी और वे मर्जर्ट द्वारा समूहीकृत थे। हम इसे सही करेंगे।

अब हमारे Reduce में हमें केवल पहली संख्या को 1 से गुणा करना होगा, और फिर पहली पंक्ति के लिए एक सरणी, दूसरी के लिए दो सरणियाँ और तीसरी के लिए एक बार फिर से उत्पादन करना होगा।

वास्तव में, आप किस मैप अवतार का उपयोग करेंगे, इसके आधार पर, आप Reduce step में दो सरणियों को आउटपुट करने में सक्षम नहीं हो सकते हैं, क्योंकि केवल एक आउटपुट सरणी की आवश्यकता होगी - तो बस इसे अपने प्रोग्राम में अपने Reduce step के बाद करें ।

हमें मिलता है:

120, 3
15, ,
15, 2
1, 4

ब्यूटी! क्या जरूरत थी।

फिर से, याद रखें कि मुख्य बात जो हमने यहां दरकिनार की है, वह यह है कि उदाहरण चार लाइनों का है, और विकिपीडिया में अरबों शब्द हैं जो स्मृति में फिट नहीं होते हैं।

कैसे खेलने के लिए एक सरल MapReduce बनाने के लिए?

PHP में : सबसे सरल उदाहरण है ।
पायथन इसका सबसे सरल उदाहरण है (पायथन संस्करण के लिए नीचे देखें)।

कोड में, मैंने संकेत दिया कि काले रंग के साथ अधिक या कम पूर्ण MapReduce बनाने के लिए क्या और कहाँ होना चाहिए ... फाइलों और मर्जसॉर्ट के अर्थ में। हालांकि, यह एक संदर्भ कार्यान्वयन है , इसलिए बोलने के लिए, चारों ओर खेलने और समझने के लिए कि MapReduce कैसे काम करता है। यह अभी भी MapReduce है, बस विशेष रूप से स्मृति के दृष्टिकोण से यह कार्यान्वयन एक नियमित हैश की तुलना में अधिक लाभदायक नहीं है।

मैंने PHP को चुना, हालांकि यह इन उद्देश्यों के लिए सबसे उचित नहीं है, क्योंकि लगभग कोई भी प्रोग्रामर PHP पढ़ सकता है, और इसे वांछित भाषा में अनुवाद करना आसान होगा।

संकेत और धोखा

हां, मैं लाइन द्वारा एरन (json_encode) लाइन के JSON प्रतिनिधित्व को संग्रहीत करने की सलाह देता हूं - शब्दों में रिक्त स्थान के साथ यूनिकोड, संख्या और डेटा प्रकारों के साथ कम समस्याएं होंगी, अर्थात्:
["foo", 1]
["bar", 1]
["foo", 1]

संकेत - पायथन में, अंतिम चरण मर्जस्टॉर्ट पहले ही लागू हो चुका है heapq.merge(*iterables) ।

यह है, JSON अभ्यावेदन के साथ 10 फ़ाइलों को जोड़ने के लिए पर्याप्त है:

  आइटम = सूची (फ़ाइल में फ़ाइल नाम के लिए itertools.imap (json.loads, open (फ़ाइल नाम))
 heapq.merge (* आइटम) में आइटम के लिए:
   # .... घटाना (मद) ...। 

MergeSort के कार्यान्वयन के साथ PHP में, मुझे संदेह है कि मुझे पचास लाइनों के साथ परेशान करना होगा। जब तक, निश्चित रूप से, टिप्पणियों में कोई भी मुझे एक बेहतर विकल्प नहीं बताता है।

पायथन में, MapReduce के लिए yield और __iter__ - आपको बहुत दिलचस्प चीजें करने की अनुमति देगा! उदाहरण के लिए, जैसे:

  x = MapReduce ()
 "फू बार बार" में शब्द के लिए .plplit ():
    x.send (शब्द, 1)

 शब्द के लिए, एक्स में वाले:
    प्रिंट शब्द, राशि (वाले) 

class MapReduce - आपको इसे खुद लिखना होगा (मैंने 24 लाइनों के भीतर सबसे सरल काम करने के रूप में रखा , शायद कम - iter_group को सरल बनाना PHP उदाहरण से group_tuples_by_first_element फ़ंक्शन का एक एनालॉग है)।

सावधानी - यह विधि MapReduce के लिए काफी क्लासिक नहीं है और इसे कई मशीनों पर समानांतर करना मुश्किल होगा (हालांकि, यह इस पद्धति में काफी तुच्छ है कि स्मृति से अधिक डेटा वॉल्यूम के साथ काम करने के लिए)। map_reduce(source_data, map1, reduce1) विधि map_reduce(source_data, map1, reduce1) , जहाँ map1 और less1 फ़ंक्शंस हैं - अधिक सही है।

Hadoop पर MapReduce का कार्यान्वयन सबसे लोकप्रिय समाधान है। (मैंने इसे आज़माया नहीं है, मुझे अभी पता है कि सबसे लोकप्रिय क्या है)।

अंतभाषण

इसलिए, मुझे उम्मीद है कि बिना ज़ूमी के मैपरेड के बिना मेरी कहानी उपयोगी होगी।

किसी भी बड़े पैमाने पर गणना के लिए MapReduce एक बहुत ही उपयोगी चीज है। लगभग किसी भी SQL क्वेरी, यहां तक ​​कि कई तालिकाओं में, MapReduce + join_iterator (उस समय पर अधिक) में विघटित करना बहुत मुश्किल नहीं है।

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

हाँ, यहाँ हर कोई! MapReduce को Google द्वारा पेटेंट कराया गया है , लेकिन सुरक्षात्मक उद्देश्यों के लिए - उसी Hadoop को उन्होंने आधिकारिक तौर पर इस पद्धति का उपयोग करने की अनुमति दी है। इसलिए - देखभाल के साथ संभाल।

भाग दो: अधिक उन्नत उदाहरण ।

योय हाजी
देखें, हमेशा की तरह, हैबर से ,
2010

(किसी दिन मैं संक्षेप में समझाना सीखूंगा ....)