كيف تعمل خوارزمية الفرز MapReduce؟

Question

أحد الأمثلة الرئيسية المستخدمة في إظهار قوة MapReduce هو معيار تيراسورت.أواجه مشكلة في فهم أساسيات خوارزمية الفرز المستخدمة في بيئة MapReduce.

بالنسبة لي، يتضمن الفرز ببساطة تحديد الموضع النسبي لعنصر ما بالنسبة لجميع العناصر الأخرى.لذا فإن الفرز يتضمن مقارنة "كل شيء" بـ "كل شيء".تقوم خوارزمية الفرز المتوسطة (السريعة، الفقاعية، ...) بذلك ببساطة بطريقة ذكية.

في رأيي، تقسيم مجموعة البيانات إلى عدة أجزاء يعني أنه يمكنك فرز قطعة واحدة ومن ثم لا يزال يتعين عليك دمج هذه القطع في مجموعة البيانات "الكاملة" التي تم فرزها بالكامل.ونظرًا لمجموعة بيانات تيرابايت الموزعة على آلاف الأنظمة، أتوقع أن تكون هذه مهمة ضخمة.

فكيف يتم ذلك حقا؟كيف تعمل خوارزمية الفرز MapReduce؟

شكرا لمساعدتي على فهم.

Answer 1

وهنا بعض التفاصيل حول تطبيق Hadoop لـ Terasort:

TeraSort عبارة عن فرز قياسي للخريطة/التصغير، باستثناء المقسم المخصص الذي يستخدم قائمة مرتبة من مفاتيح عينات N - 1 التي تحدد نطاق المفاتيح لكل تقليل.على وجه الخصوص، يتم إرسال كافة المفاتيح مثل العينة[i − 1] <= المفتاح < العينة[i] لتقليل i.وهذا يضمن أن مخرجات التخفيض i أقل من مخرجات التخفيض i+1."

لذا فإن حيلتهم تكمن في الطريقة التي يحددون بها المفاتيح أثناء مرحلة الخريطة.إنهم يضمنون بشكل أساسي أن كل قيمة في مخفض واحد مضمونة "مرتبة مسبقًا" مقابل جميع المخفضات الأخرى.

لقد وجدت المرجع الورقي من خلال مشاركة مدونة جيمس هاملتون.

Answer 2

مرجع جوجل: تقليل الخريطة:معالجة مبسطة للبيانات في المجموعات الكبيرة

ظهرت في:
OSDI'04:الندوة السادسة حول تصميم وتنفيذ أنظمة التشغيل،
سان فرانسيسكو، كاليفورنيا، ديسمبر 2004.

يحتوي هذا الرابط على مرجع PDF وHTML-Slide.

هنالك أيضا صفحة ويكيبيديا مع الوصف مع مراجع التنفيذ

انتقادات أيضاً،

قدم ديفيد ديويت ومايكل ستونبراكر، وهما خبيران رائدان في قواعد البيانات المتوازية ولم يشتركا في بنيات اللاشيء، بعض التأكيدات المثيرة للجدل حول اتساع نطاق المشكلات التي يمكن استخدام MapReduce لحلها.لقد أطلقوا على واجهتها مستوى منخفض جدًا، وتساءلوا عما إذا كانت تمثل حقًا نقلة نوعية كما ادعى أنصارها.إنهم يتحدون ادعاءات مؤيدي MapReduce بالحداثة، مستشهدين بـ Teradata كمثال للفن السابق الذي كان موجودًا منذ أكثر من عقدين من الزمن؛قاموا بمقارنة مبرمجي MapReduce بمبرمجي Codasyl، مشيرين إلى أن كلاهما "يكتبان بلغة منخفضة المستوى ويؤديان معالجة منخفضة المستوى للسجلات".إن استخدام MapReduce لملفات الإدخال ونقص دعم المخطط يمنع تحسينات الأداء التي تتيحها ميزات نظام قاعدة البيانات الشائعة مثل B-trees وتقسيم التجزئة، على الرغم من أن مشاريع مثل PigLatin وSawzall بدأت في معالجة هذه المشكلات.

Answer 3

كان لدي نفس السؤال أثناء قراءة ورقة MapReduce من Google. @يوفال ف 'س إجابة حل اللغز الخاص بي إلى حد كبير.

شيء واحد لاحظته أثناء قراءة الورقة هو أن السحر يحدث في التقسيم (بعد الخريطة، قبل التصغير).

يستخدم الورق hash(key) mod R كمثال التقسيم، ولكن هذه ليست الطريقة الوحيدة لتقسيم البيانات الوسيطة إلى مهام مخفضة مختلفة.

فقط أضف شروط الحدود إلى @يوفال ف 'س إجابة لجعلها كاملة:لنفترض أن الحد الأدنى (S) والحد الأقصى (S) هو المفتاح الأدنى والمفتاح الأقصى بين المفاتيح التي تم أخذ عينات منها؛يتم تقسيم جميع المفاتيح <min(S) إلى مهمة واحدة مخفضة؛والعكس صحيح، يتم تقسيم جميع المفاتيح >= max(S) إلى مهمة واحدة مخفضة.

لا توجد قيود صارمة على المفاتيح التي تم أخذ عينات منها، مثل الحد الأدنى أو الحد الأقصى.فقط، يتم توزيع مفاتيح R هذه بشكل متساوٍ بين جميع المفاتيح، وأكثر "توازيًا" مع هذا النظام الموزع وأقل احتمالًا أن يكون لدى مشغل التخفيض مشكلة تجاوز سعة الذاكرة.

Answer 4

تخمين فقط...

بالنظر إلى مجموعة ضخمة من البيانات، يمكنك تقسيم البيانات إلى بعض الأجزاء لتتم معالجتها بالتوازي (ربما عن طريق رقم السجل، أي.سجل 1 - 1000 = القسم 1، وهكذا).

تعيين/جدولة كل قسم إلى عقدة معينة في المجموعة.

ستقوم كل عقدة كتلة بتقسيم (تعيين) القسم إلى قسم صغير خاص بها، ربما حسب الترتيب الأبجدي الرئيسي.لذا، في القسم 1، أحضر لي كل الأشياء التي تبدأ بـ A وأخرجها إلى القسم الصغير A من x.قم بإنشاء A(x) جديد إذا كان هناك A(x) بالفعل.استبدل x بالرقم التسلسلي (ربما تكون هذه هي مهمة المجدول للقيام بذلك).أي.أعطني المعرف الفريد التالي لـ A(x).

قم بتسليم (جدولة) المهام التي أكملها مصمم الخرائط (الخطوة السابقة) إلى عقد المجموعة "التقليل".سيؤدي تقليل مجموعة العقدة بعد ذلك إلى تحسين نوع كل أجزاء A(x) والذي سيحدث فقط عند الانتهاء من جميع مهام مصمم الخرائط (لا يمكن فعليًا البدء في فرز جميع الكلمات التي تبدأ بـ w/A عندما لا يزال هناك احتمال أنه لا يزال هناك سيكون قسمًا صغيرًا آخر قيد الإنشاء).قم بإخراج النتيجة في الجزء النهائي الذي تم فرزه (أيمصنف-أ، مصنف-ب، وما إلى ذلك)

بمجرد الانتهاء من ذلك، قم بدمج القسم الذي تم فرزه في مجموعة بيانات واحدة مرة أخرى.في هذه المرحلة، يكون الأمر مجرد سلسلة بسيطة من ملفات n (حيث يمكن أن يكون n 26 إذا كنت تفعل فقط A - Z)، وما إلى ذلك.

وقد تكون هناك خطوات وسطية بينهما..لست متأكد :).أي.مزيد من الخريطة والتقليل بعد خطوة التخفيض الأولية.