MapReduce

الموسوعة الحرة

MapReduce هو نموذج برمجي وتطبيق مرتبط به لمعالجة وتوليد مجموعات البيانات الضخمة باستخدام خوارزمية متوازية وموزعة على مجموعة من الحواسيب . [ 1 ] [ 2 ] [ 3 ]

يتألف برنامج MapReduce من إجراء map ، الذي يقوم بعمليات الفرز والتصفية (مثل فرز الطلاب حسب الاسم الأول في قوائم انتظار، قائمة انتظار لكل اسم)، ودالة reduce ، التي تقوم بعملية تلخيص (مثل حساب عدد الطلاب في كل قائمة انتظار، مما ينتج عنه تكرار الأسماء). يقوم "نظام MapReduce" (ويُسمى أيضًا "البنية التحتية" أو "الإطار") بتنظيم المعالجة من خلال إدارة الخوادم الموزعة، وتشغيل المهام المختلفة بالتوازي، وإدارة جميع الاتصالات ونقل البيانات بين أجزاء النظام المختلفة، وتوفير التكرار وتحمل الأعطال .

يُعدّ هذا النموذج تخصصًا لاستراتيجية تقسيم البيانات وتطبيقها ودمجها . [ 4 ] وهو مستوحى من دالتيّ map و reduce الشائعتين في البرمجة الوظيفية ، [ 5 ] مع أن غرضهما في إطار عمل MapReduce يختلف عن غرضهما في شكلهما الأصلي. [ 6 ] لا تكمن المساهمات الرئيسية لإطار عمل MapReduce في دالتيّ map وreduce نفسيهما (اللتين تُشبهان، على سبيل المثال، عمليتيّ reduce و scatter في معيار واجهة تمرير الرسائل لعام 1995 [ 7 ] ) ، بل في قابلية التوسع وتحمّل الأعطال المُتحققة لمجموعة متنوعة من التطبيقات بفضل التوازي . ولذلك، فإنّ تطبيق MapReduce أحادي الخيوط عادةً لا يكون أسرع من التطبيق التقليدي (غير MapReduce)؛ ولا تُلاحظ أيّة مكاسب عادةً إلا مع التطبيقات متعددة الخيوط على أجهزة متعددة المعالجات. [ 10 ] لا يكون استخدام هذا النموذج مفيدًا إلا عند تفعيل عملية التوزيع المُحسّنة (التي تُقلل تكلفة الاتصال الشبكي) وميزات تحمل الأعطال في إطار عمل MapReduce. ويُعدّ تحسين تكلفة الاتصال أمرًا أساسيًا لخوارزمية MapReduce الجيدة. [ 11 ]

MapReduce libraries have been written in many programming languages, with different levels of optimization. A popular open-source implementation that has support for distributed shuffles is part of Apache Hadoop. The name MapReduce originally referred to the proprietary Google technology, but has since become a generic trademark. By 2014, Google was no longer using MapReduce as its primary big data processing model,[12] and development on Apache Mahout had moved on to more capable and less disk-oriented mechanisms that incorporated full map and reduce capabilities.[13]

Overview

MapReduce is a framework for processing parallelizable problems across large datasets using a large number of computers (nodes), collectively referred to as a cluster (if all nodes are on the same local network and use similar hardware) or a grid (if the nodes are shared across geographically and administratively distributed systems, and use more heterogeneous hardware). Processing can occur on data stored either in a filesystem (unstructured) or in a database (structured). MapReduce can take advantage of the locality of data, processing it near the place it is stored in order to minimize communication overhead.

A MapReduce framework (or system) is usually composed of three operations (or steps):

  1. Map: each worker node applies the map function to the local data, and writes the output to a temporary storage. A master node ensures that only one copy of the redundant input data is processed.
  2. Shuffle: worker nodes redistribute data based on the output keys (produced by the map function), such that all data belonging to one key is located on the same worker node.
  3. Reduce: worker nodes now process each group of output data, per key, in parallel.

تتيح تقنية MapReduce المعالجة الموزعة لعمليات الخرائط والاختزال. يمكن تنفيذ عمليات الخرائط بالتوازي، شريطة أن تكون كل عملية خرائط مستقلة عن الأخرى؛ عمليًا، يحد من ذلك عدد مصادر البيانات المستقلة و/أو عدد وحدات المعالجة المركزية القريبة من كل مصدر. وبالمثل، يمكن لمجموعة من "المختزلات" تنفيذ مرحلة الاختزال، شريطة أن تُقدَّم جميع مخرجات عملية الخرائط التي تشترك في نفس المفتاح إلى نفس المختزل في نفس الوقت، أو أن تكون دالة الاختزال ترابطية . على الرغم من أن هذه العملية تبدو غالبًا غير فعالة مقارنةً بالخوارزميات الأكثر تسلسلًا (لأنه يجب تشغيل نسخ متعددة من عملية الاختزال)، إلا أنه يمكن تطبيق MapReduce على مجموعات بيانات أكبر بكثير مما يمكن لخادم "عادي" واحد التعامل معه - إذ يمكن لمزرعة خوادم كبيرة استخدام MapReduce لفرز بيتابايت من البيانات في غضون ساعات قليلة فقط. [ 14 ] يوفر التوازي أيضًا بعض إمكانية التعافي من الفشل الجزئي للخوادم أو التخزين أثناء العملية: إذا فشل أحد المخططات أو المختزلات، فيمكن إعادة جدولة العمل - بافتراض أن بيانات الإدخال لا تزال متاحة.  

هناك طريقة أخرى للنظر إلى MapReduce وهي اعتبارها عملية حسابية متوازية وموزعة من 5 خطوات:

  1. قم بإعداد مدخلات Map() - يقوم "نظام MapReduce" بتحديد معالجات Map، وتعيين مفتاح الإدخال K1 الذي سيعمل عليه كل معالج، وتزويد هذا المعالج بجميع بيانات الإدخال المرتبطة بهذا المفتاح.
  2. قم بتشغيل كود Map() المقدم من المستخدم - يتم تشغيل Map() مرة واحدة بالضبط لكل مفتاح K1 ، مما يؤدي إلى إنشاء مخرجات منظمة حسب المفتاح K2 .
  3. "خلط" مخرجات الخريطة إلى معالجات الاختزال - يقوم نظام MapReduce بتحديد معالجات الاختزال، وتعيين مفتاح K2 الذي يجب أن يعمل عليه كل معالج، وتزويد هذا المعالج بجميع البيانات التي تم إنشاؤها بواسطة الخريطة والمرتبطة بهذا المفتاح.
  4. قم بتشغيل كود Reduce() المقدم من المستخدم - يتم تشغيل Reduce() مرة واحدة بالضبط لكل مفتاح K2 تم إنتاجه بواسطة خطوة Map.
  5. إنتاج المخرجات النهائية - يقوم نظام MapReduce بجمع جميع مخرجات Reduce، وفرزها حسب K2 لإنتاج النتيجة النهائية.

يمكن اعتبار هذه الخطوات الخمس منطقياً على أنها تعمل بالتسلسل - تبدأ كل خطوة فقط بعد اكتمال الخطوة السابقة - على الرغم من أنه من الناحية العملية يمكن دمجها طالما أن النتيجة النهائية لا تتأثر.

في كثير من الحالات، قد تكون بيانات الإدخال موزعة مسبقًا ( مجزأة ) على عدة خوادم مختلفة، وفي هذه الحالة، يمكن تبسيط الخطوة الأولى بشكل كبير أحيانًا عن طريق تخصيص خوادم Map لمعالجة بيانات الإدخال الموجودة محليًا. وبالمثل، يمكن تسريع الخطوة الثالثة أحيانًا عن طريق تخصيص معالجات Reduce قريبة قدر الإمكان من البيانات التي تولدها خوادم Map والتي تحتاج إلى معالجتها.

وجهة نظر منطقية

تُعرَّف دالتا Map و Reduce في MapReduce بالنسبة للبيانات المهيكلة على شكل أزواج (مفتاح، قيمة). تأخذ دالة Map زوجًا واحدًا من البيانات بنوع معين في مجال بيانات واحد ، وتعيد قائمة من الأزواج في مجال مختلف.

Map(k1,v1)→list(k2,v2)

تُطبَّق دالة Map بالتوازي على كل زوج (مفهرس بـ k1) في مجموعة البيانات المدخلة. ينتج عن ذلك قائمة من الأزواج (مفهرسة بـ k2) لكل استدعاء. بعد ذلك، يجمع إطار عمل MapReduce جميع الأزواج التي لها نفس المفتاح ( k2) من جميع القوائم ويُجمِّعها معًا، مُنشئًا مجموعة واحدة لكل مفتاح.

ثم يتم تطبيق دالة الاختزال بالتوازي على كل مجموعة، مما ينتج عنه مجموعة من القيم في نفس المجال:

Reduce(k2, list (v2))→ list((k3, v3))[ 15 ]

ينتج عن كل استدعاء لدالة Reduce عادةً إما زوج واحد من المفتاح والقيمة أو قيمة فارغة، مع العلم أنه يُسمح للاستدعاء الواحد بإرجاع أكثر من زوج واحد من المفتاح والقيمة. تُجمع نتائج جميع الاستدعاءات في قائمة النتائج المطلوبة.

وبالتالي، يقوم إطار عمل MapReduce بتحويل قائمة من أزواج (مفتاح، قيمة) إلى قائمة أخرى من أزواج (مفتاح، قيمة). [ 16 ] يختلف هذا السلوك عن دمج دالتي map وreduce في البرمجة الوظيفية التقليدية، حيث تقبل قائمة من القيم العشوائية وتعيد قيمة واحدة تجمع كل القيم التي تُعيدها دالة map.

يُعدّ وجود تطبيقات لنموذجي الخريطة والاختزال ضروريًا، ولكنه غير كافٍ، لتطبيق MapReduce. تتطلب التطبيقات الموزعة لـ MapReduce وسيلةً لربط العمليات التي تُنفّذ مرحلتي الخريطة والاختزال. قد يكون هذا الربط عبر نظام ملفات موزّع . توجد خيارات أخرى، مثل البث المباشر من وحدات الخريطة إلى وحدات الاختزال، أو قيام معالجات الخريطة بتقديم نتائجها إلى وحدات الاختزال التي تستعلم عنها.

أمثلة

يقوم مثال MapReduce النموذجي بحساب ظهور كل كلمة في مجموعة من المستندات: [ 17 ]

دالة map (سلسلة نصية name، سلسلة نصية document): // name: اسم المستند // document: محتويات المستند لكل كلمة w في document: انبعاث (w, 1) دالة reduce (سلسلة نصية كلمة، مُكرِّر التكرارات الجزئية): // كلمة: كلمة // التكرارات الجزئية: قائمة بالتكرارات الجزئية المُجمَّعة المجموع = 0 لكل قطعة في partialCounts: المجموع += pc أصدر (كلمة، مجموع)

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

كمثال آخر، تخيل أنك تريد حساب متوسط ​​عدد العلاقات الاجتماعية لكل شخص حسب عمره، وذلك لقاعدة بيانات تضم 1.1 مليار شخص. في لغة SQL ، يمكن التعبير عن هذا الاستعلام كما يلي:

حدد العمر ، ومتوسط ​​عدد جهات الاتصال من جدول social.person ، وقم بتجميع النتائج حسب العمر ، ورتبها حسب العمر.

باستخدام MapReduce، يمكن أن تكون قيم مفتاح K1 هي الأعداد الصحيحة من 1 إلى 1100، حيث يمثل كل منها مجموعة من مليون سجل، ويمكن أن تكون قيمة مفتاح K2 هي عمر الشخص بالسنوات، ويمكن تحقيق هذا الحساب باستخدام الوظائف التالية:

الدالة Map تأخذ مُدخلًا: عدد صحيح K1 بين 1 و1100، يُمثل دفعة من مليون سجل من نوع social.person. لكل سجل social.person في الدفعة K1، اجعل Y عمر الشخص، و N عدد جهات الاتصال الخاصة به. أنشئ سجل إخراج واحد (Y,(N,1)). كرر العملية. نهاية الدالة.دالة Reduce تأخذ المدخلات التالية: العمر (بالسنوات) Y لكل سجل من سجلات الإدخال (Y، (N، C)) do قم بتجميع مجموع N*C في Sقم بتجميع مجموع C في C new، وكرر العملية. ليكن A هو S/C new ، وأنتج سجل إخراج واحد (Y,(A,C new )). نهاية الدالة.

لاحظ أنه في دالة Reduce ، فإن C هو عدد الأشخاص الذين لديهم N جهة اتصال إجمالاً، لذلك من الطبيعي في دالة Map كتابة C=1 ، لأن كل زوج من المخرجات يشير إلى جهات اتصال شخص واحد.

يقوم نظام MapReduce بترتيب 1100 معالج Map، ويُزوّد ​​كل معالج بمليون سجل إدخال. تُنتج خطوة Map 1.1 مليار سجل (Y,(N,1)) ، حيث تتراوح قيم Y بين 8 و103. بعد ذلك، يقوم نظام MapReduce بترتيب 96 معالج Reduce عن طريق إعادة ترتيب أزواج المفاتيح/القيم، نظرًا لحاجتنا إلى حساب المتوسط ​​لكل عمر، ويُزوّد ​​كل معالج بملايين سجلات الإدخال. تُنتج خطوة Reduce مجموعة مُصغّرة من 96 سجل إخراج فقط (Y,A) ، والتي تُوضع في ملف النتائج النهائي، مُرتبة حسب Y.

تُعدّ معلومات عدد السجلات مهمة إذا تم تقليل المعالجة أكثر من مرة. فإذا لم نُضِف عدد السجلات، فسيكون المتوسط ​​المحسوب خاطئًا، على سبيل المثال:

-- مخرجات الخريطة رقم 1: العمر، عدد جهات الاتصال 10، 9 10، 9 10، 9
-- مخرجات الخريطة رقم 2: العمر، عدد جهات الاتصال 10، 9 10، 9
-- مخرجات الخريطة رقم 3: العمر، عدد جهات الاتصال 10، 10

إذا قمنا بتقليص الملفين رقم 1 ورقم 2 ، فسنحصل على ملف جديد يحتوي على 9 جهات اتصال في المتوسط ​​لشخص يبلغ من العمر 10 سنوات ((9+9+9+9+9)/5):

-- تقليل الخطوة رقم 1: العمر، متوسط ​​عدد جهات الاتصال 10، 9

إذا قمنا بتقليصها باستخدام الملف رقم 3 ، فإننا نفقد عدد السجلات التي اطلعنا عليها بالفعل، وبالتالي ينتهي بنا الأمر بمتوسط ​​9.5 جهات اتصال لشخص يبلغ من العمر 10 سنوات ((9+10)/2)، وهو أمر خاطئ. الإجابة الصحيحة هي 9.1، أي 66 = 55 / 6 = (9×3+9×2+10×1)/(3+2+1).

تدفق البيانات

تلتزم بنية إطار عمل البرمجيات بمبدأ الانفتاح والإغلاق، حيث يُقسّم الكود فعليًا إلى نقاط ثابتة غير قابلة للتعديل ونقاط نشطة قابلة للتوسيع . النقطة الثابتة في إطار عمل MapReduce هي عملية فرز موزعة واسعة النطاق. أما النقاط النشطة، التي يُحددها التطبيق، فهي:

  • قارئ إدخال
  • دالة الخريطة​
  • دالة التقسيم​
  • دالة مقارنة​
  • دالة الاختزال​
  • كاتب إخراج

قارئ الإدخال

يقوم قارئ المدخلات بتقسيم المدخلات إلى أجزاء مناسبة الحجم (عادةً ما  تتراوح أحجامها بين 64 و128  ميجابايت)، ويُخصص الإطار جزءًا واحدًا لكل دالة من دوال الخرائط . يقرأ قارئ المدخلات البيانات من وحدة تخزين ثابتة (عادةً ما تكون نظام ملفات موزع ) ويُنشئ أزواجًا من المفاتيح والقيم.

من الأمثلة الشائعة قراءة دليل مليء بملفات نصية وإرجاع كل سطر كسجل.

دالة الخريطة

تأخذ دالة الخريطة سلسلة من أزواج المفاتيح والقيم، وتعالج كل زوج منها، وتُنتج صفرًا أو أكثر من أزواج المفاتيح والقيم الناتجة. قد تختلف أنواع المدخلات والمخرجات في الخريطة (وكثيرًا ما تختلف).

إذا كان التطبيق يقوم بعدّ الكلمات، فإن دالة الخريطة ستقسم السطر إلى كلمات وتُخرج زوجًا من المفتاح والقيمة لكل كلمة. سيحتوي كل زوج مُخرَج على الكلمة كمفتاح وعدد مرات ظهور تلك الكلمة في السطر كقيمة.

دالة التقسيم

تُخصَّص كل مخرجات دالة الخريطة لمُختزِل مُحدَّد بواسطة دالة التقسيم الخاصة بالتطبيق لأغراض التجزئة . تُعطى دالة التقسيم المفتاح وعدد المُختزِلات، ثم تُعيد فهرس المُختزِل المطلوب .

يتمثل الإعداد الافتراضي الشائع في تجزئة المفتاح واستخدام قيمة التجزئة بتردد عدد المُختزِلات . من المهم اختيار دالة تقسيم تُعطي توزيعًا متجانسًا تقريبًا للبيانات لكل جزء لأغراض موازنة الأحمال ، وإلا فقد تتعطل عملية MapReduce في انتظار انتهاء المُختزِلات البطيئة (أي المُختزِلات المُخصصة لها الحصص الأكبر من البيانات المُقسّمة بشكل غير متجانس).

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

دالة المقارنة

يتم سحب المدخلات لكل عملية تقليل من الجهاز الذي تم تشغيل الخريطة عليه وفرزها باستخدام وظيفة المقارنة الخاصة بالتطبيق .

وظيفة التخفيض

يستدعي إطار العمل دالة Reduce الخاصة بالتطبيق مرة واحدة لكل مفتاح فريد في الترتيب المُرتب. يمكن لدالة Reduce أن تتكرر عبر القيم المرتبطة بهذا المفتاح وتُنتج صفرًا أو أكثر من المخرجات.

في مثال عد الكلمات، تأخذ دالة Reduce قيم الإدخال، وتجمعها، وتولد مخرجًا واحدًا للكلمة والمجموع النهائي.

كاتب الإخراج

يقوم برنامج كتابة المخرجات بكتابة مخرجات عملية الاختزال إلى وحدة التخزين الثابتة.

الخلفية النظرية

تُعد خصائص المونويدات أساسًا لضمان صحة عمليات MapReduce. [ 18 ] [ 19 ]

في حزمة Algebird [ 20 ] يتطلب تطبيق Scala لـ Map/Reduce صراحةً نوع فئة أحادي. [ 21 ]

تتعامل عمليات MapReduce مع نوعين: النوع A من بيانات الإدخال التي يتم تعيينها، والنوع B من بيانات الإخراج التي يتم تقليلها.

تأخذ عملية الخريطة قيمًا فردية من النوع A وتنتج، لكل a:A قيمة b:B ؛ تتطلب عملية الاختزال عملية ثنائية • معرفة على قيم من النوع B ؛ وهي تتكون من طي جميع b:B المتاحة إلى قيمة واحدة.

من وجهة نظر المتطلبات الأساسية، يجب أن تتضمن أي عملية MapReduce القدرة على إعادة تجميع البيانات التي يتم اختزالها بشكل تعسفي. ويتمثل هذا المطلب في خاصيتين للعملية:

  • خاصية التجميع: ( س • ص ) • ع = س • ( ص • ع )
  • وجود عنصر محايد e بحيث يكون e • x = x • e = x لكل x:B .

تضمن الخاصية الثانية أنه عند التوازي على عدة عقد، فإن العقد التي ليس لديها أي بيانات للمعالجة لن يكون لها أي تأثير على النتيجة.

هاتان الخاصيتان تعنيان وجود أحادي ( B ، •، e ) على قيم من النوع B مع العملية • ومع العنصر المحايد e .

لا توجد شروط على قيم النوع A ؛ إذ يمكن استخدام أي دالة A → B لعملية الخريطة . هذا يعني أن لدينا تحويلًا شكليًا A* → ( B , •, e ). هنا، يرمز A* إلى نجمة كلين ، والمعروفة أيضًا بنوع القوائم على A.

عملية Shuffle في حد ذاتها لا ترتبط بجوهر MapReduce؛ إنها ضرورية لتوزيع العمليات الحسابية عبر السحابة.

يستنتج مما سبق أنه ليس كل عملية اختزال ثنائية ستعمل في MapReduce. إليك بعض الأمثلة المضادة:

  • بناء شجرة من الأشجار الفرعية: هذه العملية ليست ترابطية، وستعتمد النتيجة على التجميع؛
  • الحساب المباشر للمتوسطات: المتوسط ​​ليس تجميعيًا أيضًا (ولا يحتوي على عنصر محايد)؛ لحساب المتوسط، يحتاج المرء إلى حساب العزوم .

اعتبارات الأداء

لا يُضمن أن تكون برامج MapReduce سريعة. تكمن الميزة الرئيسية لهذا النموذج البرمجي في استغلال عملية التوزيع المُحسّنة للمنصة، والاكتفاء بكتابة جزئيّ Map و Reduce فقط . عمليًا، يجب على مُطوّر برنامج MapReduce مراعاة خطوة التوزيع؛ إذ يُمكن أن تؤثر دالة التقسيم وكمية البيانات التي تكتبها دالة Map بشكل كبير على الأداء وقابلية التوسع. يُمكن لوحدات إضافية، مثل دالة Combiner، أن تُساعد في تقليل كمية البيانات المكتوبة على القرص والمُرسلة عبر الشبكة. يُمكن لتطبيقات MapReduce تحقيق تسارع دون الخطي في ظروف مُحددة. [ 22 ]

عند تصميم خوارزمية MapReduce، يحتاج المؤلف إلى اختيار توازن مناسب [ 11 ] بين تكاليف الحساب وتكاليف الاتصال. غالبًا ما تفوق تكلفة الاتصال تكلفة الحساب [ 11 ] [ 22 ] ، ولذا صُممت العديد من تطبيقات MapReduce لكتابة جميع البيانات المُتصلة إلى وحدة تخزين موزعة لاستعادة البيانات في حالة الأعطال.

عند تحسين أداء MapReduce، يجب مراعاة تعقيد عمليات التعيين، والخلط، والفرز (التجميع حسب المفتاح)، والاختزال. يُعد حجم البيانات التي تُنتجها وحدات التعيين (mappers) عاملاً أساسياً يُوزّع الجزء الأكبر من تكلفة الحساب بين التعيين والاختزال. يشمل الاختزال الفرز (تجميع المفاتيح) الذي يتميز بتعقيد غير خطي. لذا، فإن أحجام الأقسام الصغيرة تُقلل من وقت الفرز، ولكن هناك مفاضلة، إذ قد يكون وجود عدد كبير من وحدات الاختزال غير عملي. تأثير حجم وحدة التقسيم هامشي (إلا إذا تم اختياره بشكل سيئ للغاية، كأن يكون أقل من 1 ميجابايت). في المتوسط، تكون المكاسب الناتجة عن قراءة بعض وحدات التعيين من الأقراص المحلية طفيفة. [ 23 ]

بالنسبة للعمليات التي تُنجز بسرعة، والتي تتسع بياناتها في الذاكرة الرئيسية لجهاز واحد أو مجموعة صغيرة من الحواسيب، فإن استخدام إطار عمل MapReduce عادةً ما يكون غير فعال. ولأن هذه الأطر مصممة للتعافي من فقدان عُقد كاملة أثناء الحساب، فإنها تُخزّن النتائج المؤقتة في وحدة تخزين موزعة. يُعدّ هذا التعافي من الأعطال مكلفًا، ولا يُجدي نفعًا إلا عندما يتضمن الحساب العديد من الحواسيب ووقت تشغيل طويل. يمكن ببساطة إعادة تشغيل مهمة تُنجز في ثوانٍ في حالة حدوث خطأ، ويزداد احتمال تعطل جهاز واحد على الأقل بسرعة مع ازدياد حجم المجموعة. في مثل هذه الحالات، غالبًا ما تكون التطبيقات التي تحتفظ بجميع البيانات في الذاكرة وتعيد تشغيل الحساب عند تعطل العُقد، أو الحلول غير الموزعة - عندما تكون البيانات صغيرة بما يكفي - أسرع من نظام MapReduce.

التوزيع والموثوقية

يحقق MapReduce الموثوقية من خلال توزيع عدد من العمليات على مجموعة البيانات على كل عقدة في الشبكة. يُتوقع من كل عقدة إرسال تقارير دورية تتضمن العمل المنجز وتحديثات الحالة. إذا توقفت عقدة عن العمل لفترة أطول من تلك الفترة، تقوم العقدة الرئيسية (على غرار الخادم الرئيسي في نظام ملفات جوجل ) بتسجيلها على أنها معطلة، وترسل العمل المخصص لها إلى العقد الأخرى. تستخدم العمليات الفردية عمليات ذرية لتسمية مخرجات الملفات كآلية للتحقق من عدم وجود سلاسل عمليات متوازية متضاربة قيد التشغيل. عند إعادة تسمية الملفات، من الممكن أيضًا نسخها إلى اسم آخر بالإضافة إلى اسم المهمة (مما يسمح بحدوث آثار جانبية ).

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

لا تُعدّ التطبيقات بالضرورة عالية الموثوقية. على سبيل المثال، في الإصدارات القديمة من هادوب، كان NameNode نقطة فشل وحيدة لنظام الملفات الموزع. أما الإصدارات الأحدث من هادوب فتتمتع بتوافر عالٍ مع آلية تجاوز الفشل النشط/السلبي لـ NameNode.

الاستخدامات

يُعدّ MapReduce مفيدًا في نطاق واسع من التطبيقات، بما في ذلك البحث الموزع القائم على الأنماط، والفرز الموزع، وعكس مخططات روابط الويب، وتحليل القيم المفردة، [ 24 ] وإحصائيات سجلات الوصول إلى الويب، وبناء الفهرس المعكوس ، وتجميع المستندات ، والتعلم الآلي ، [ 25 ] والترجمة الآلية الإحصائية . علاوة على ذلك، تمّ تكييف نموذج MapReduce مع العديد من بيئات الحوسبة مثل الأنظمة متعددة النوى وأنظمة المعالجات ذات النوى الكثيرة، [ 26 ] [ 27 ] [ 28 ] وشبكات سطح المكتب، [ 29 ] والمجموعات المتعددة، [ 30 ] وبيئات الحوسبة التطوعية، [ 31 ] وبيئات الحوسبة السحابية الديناميكية، [ 32 ] وبيئات الأجهزة المحمولة، [ 33 ] وبيئات الحوسبة عالية الأداء. [ 34 ]

في جوجل، استُخدمت تقنية MapReduce لإعادة إنشاء فهرس جوجل للشبكة العنكبوتية العالمية بالكامل . وقد حلت محل البرامج القديمة المخصصة التي كانت تُحدّث الفهرس وتُجري التحليلات المختلفة. [ 35 ] ومنذ ذلك الحين، انتقل التطوير في جوجل إلى تقنيات مثل Percolator وFlumeJava [ 36 ] و MillWheel التي تُتيح التشغيل والتحديثات المتدفقة بدلاً من المعالجة الدفعية، مما يسمح بدمج نتائج البحث "المباشرة" دون الحاجة إلى إعادة بناء الفهرس بالكامل. [ 37 ]

عادةً ما يتم تخزين المدخلات والمخرجات الثابتة لـ MapReduce في نظام ملفات موزع . أما البيانات المؤقتة، فعادةً ما يتم تخزينها على القرص المحلي ويتم جلبها عن بُعد بواسطة وحدات الاختزال.

نقد

انعدام الجدة

انتقد ديفيد ديويت ومايكل ستونبريكر ، وهما عالما حاسوب متخصصان في قواعد البيانات المتوازية وهياكل الحوسبة اللامركزية ، نطاق المشكلات التي يمكن استخدام MapReduce لحلها. [ 38 ] ووصفا واجهته بأنها منخفضة المستوى للغاية، وتساءلا عما إذا كانت تمثل بالفعل نقلة نوعية كما يدّعي مؤيدوها. [ 39 ] كما شككا في ادعاءات مؤيدي MapReduce بشأن حداثتها، مستشهدين بـ Teradata كمثال على تقنية سابقة موجودة منذ أكثر من عقدين. وقارنا أيضًا بين مبرمجي MapReduce ومبرمجي CODASYL ، مشيرين إلى أن كلاهما "يكتب بلغة منخفضة المستوى ويجري عمليات معالجة سجلات منخفضة المستوى". [ 39 ] إن استخدام MapReduce لملفات الإدخال وعدم دعم المخطط يمنع تحسينات الأداء التي تتيحها ميزات نظام قاعدة البيانات الشائعة مثل أشجار B وتقسيم التجزئة ، على الرغم من أن مشاريع مثل Pig (أو PigLatin) و Sawzall و Apache Hive [ 40 ] و HBase [ 41 ] و Bigtable [ 41 ] [ 42 ] تعالج بعض هذه المشكلات.

كتب جريج يورجنسن مقالاً يرفض فيه هذه الآراء. [ 43 ] ويؤكد يورجنسن أن تحليل ديويت وستونبريكر برمته لا أساس له من الصحة، حيث لم يتم تصميم MapReduce أو قصد استخدامه كقاعدة بيانات.

نشر ديويت وستونبريكر لاحقًا دراسة معيارية مفصلة في عام 2009 تقارن أداء كل من MapReduce من Hadoop ونهج قواعد البيانات العلائقية في عدة مشاكل محددة. [ 44 ] وخلصا إلى أن قواعد البيانات العلائقية توفر مزايا حقيقية لأنواع عديدة من استخدام البيانات، لا سيما في المعالجة المعقدة أو عندما تُستخدم البيانات على مستوى المؤسسة، ولكن قد يكون MapReduce أسهل في التبني للمستخدمين في مهام المعالجة البسيطة أو لمرة واحدة.

وُصِفَ نموذج برمجة MapReduce أيضًا في أطروحة داني هيليس عام 1985 [ 45 ]، والمُصممة للاستخدام على جهاز Connection Machine ، حيث سُمِّيَ "xapping/reduction" [ 46 ] ، واعتمد على مكونات الجهاز المادية الخاصة لتسريع كلٍّ من عمليتي map وreduce. وكانت لغة StarLisp*map ، التي استُخدِمت في النهاية لجهاز Connection Machine عام 1986، تدعم المعالجة المتوازية [ 47 ]reduce!! ، والتي بدورها استندت إلى لغة Common Lisp عام 1984، التي كانت تدعم المعالجة غير المتوازية [48]. ويعتمد تصميم المكعب الفائق لجهاز Connection Machine على بنية شجرية لتنفيذ التعليمات البرمجية.mapreducereduceيا(سجل⁡ن){\displaystyle O(\log n)}إن الوقت [ 49 ] هو نفسه فعليًا النهج المشار إليه في ورقة جوجل كعمل سابق. [ 3 ] : 11

في عام ٢٠١٠، مُنحت جوجل ما يُوصف بأنه براءة اختراع لتقنية MapReduce. قد تُغطي هذه البراءة، التي سُجلت عام ٢٠٠٤، استخدام MapReduce بواسطة برامج مفتوحة المصدر مثل Hadoop و CouchDB وغيرها. في موقع Ars Technica ، أقرّ أحد المحررين بدور جوجل في نشر مفهوم MapReduce، لكنه تساءل عن مدى صحة براءة الاختراع وجدّتها. [ ٥٠ ] [ ٥١ ] في عام ٢٠١٣، وكجزء من "تعهد عدم الادعاء بشأن براءات الاختراع المفتوحة (OPN)"، تعهدت جوجل باستخدام براءة الاختراع لأغراض دفاعية فقط. [ ٥٢ ] [ ٥٣ ] من المتوقع أن تنتهي صلاحية براءة الاختراع في ٢٣ ديسمبر ٢٠٢٦. [ ٥٤ ]

إطار برمجة مقيد

يجب كتابة مهام MapReduce كبرامج تدفق بيانات غير دورية، أي برنامج Mapper عديم الحالة متبوعًا ببرنامج Reducer عديم الحالة، ويتم تنفيذها بواسطة مُجدول مهام دفعية. هذا النموذج يجعل الاستعلام المتكرر عن مجموعات البيانات صعبًا ويفرض قيودًا تظهر في مجالات مثل معالجة الرسوم البيانية [ 55 ] حيث تُعد الخوارزميات التكرارية التي تعيد زيارة مجموعة عمل واحدة عدة مرات هي القاعدة، وكذلك، في حالة وجود بيانات مخزنة على القرص ذات زمن استجابة عالٍ ، حتى في مجال التعلم الآلي حيث يلزم المرور على البيانات عدة مرات على الرغم من أن الخوارزميات يمكنها تحمل الوصول التسلسلي إلى البيانات في كل مرور. [ 56 ]

انظر أيضاً

تطبيقات MapReduce

مراجع

  1. ↑ "دليل MapReduce" . أباتشي هادوب . تم الاطلاع عليه في 3 يوليو 2019 .
  2. ↑ "جوجل تسلط الضوء على العمليات الداخلية لمراكز البيانات" . cnet.com . 30 مايو 2008. مؤرشف من الأصل في 19 أكتوبر 2013. تم الاطلاع عليه في 31 مايو 2008 .
  3. 1 2 "MapReduce: معالجة البيانات المبسطة على مجموعات كبيرة" (PDF) . googleusercontent.com .
  4. ↑ ويكهام، هادلي (2011). "استراتيجية التقسيم والتطبيق والدمج لتحليل البيانات" . مجلة البرمجيات الإحصائية . 40 : 1-29 . doi : 10.18637/jss.v040.i01 .
  5. ↑ «استلهمنا تجريدنا من أساسيات map وreduce الموجودة في لغة Lisp والعديد من اللغات الوظيفية الأخرى.» - «MapReduce: معالجة البيانات المبسطة على مجموعات كبيرة» ، بقلم جيفري دين وسانجاي غيماوات؛ من أبحاث جوجل
  6. ↑ لاميل، ر. (2008). "نموذج برمجة MapReduce من جوجل - إعادة النظر". علم برمجة الحاسوب . 70 : 1-30 . doi : 10.1016/j.scico.2007.07.001 .
  7. ↑ http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/mpi2-report.htm معيار MPI 2
  8. ↑ "MPI Reduce و Allreduce · برنامج تعليمي حول MPI" . mpitutorial.com .
  9. ↑ "تنفيذ عمليات الرتبة المتوازية باستخدام MPI · برنامج تعليمي لـ MPI" . mpitutorial.com .
  10. ↑ "MongoDB: أداء MapReduce سيء للغاية" . Stack Overflow. ١٦ أكتوبر ٢٠١٠. يبدو أن تطبيق MapReduce في MongoDB لا علاقة له بـ MapReduce. فبحسب ما قرأت، يعمل MapReduce بخيط معالجة واحد، بينما يُفترض استخدام MapReduce بشكل متوازٍ للغاية على مجموعة من الخوادم. ... يعمل MapReduce في MongoDB بخيط معالجة واحد على خادم واحد...
  11. 1 2 3 أولمان، جيه دي (2012). "تصميم خوارزميات MapReduce جيدة" . XRDS: Crossroads، مجلة ACM للطلاب . 19 : 30-34 . doi : 10.1145/2331042.2331053 . S2CID 26498063 . 
  12. ↑ سفيردليك، يفغيني (25 يونيو 2014). "جوجل تتخلى عن ماب ريديوس لصالح نظام تحليلات جديد فائق التوسع" . داتا سنتر نوليدج . تاريخ الاسترجاع: 25 أكتوبر 2015 ."لم نعد نستخدم MapReduce حقًا" [أورس هولزلي، نائب الرئيس الأول للبنية التحتية التقنية في جوجل]
  13. ↑ "لماذا لا تزال تقنية MapReduce هي النهج السائد في مجال التعلم الآلي واسع النطاق؟" . مجلة Analytics India . 5 أبريل 2019.
  14. ^ تشايكوفسكي ، جرزيجورز. ماريان دفورسكي؛ جيري تشاو؛ مايكل كونلي (7 سبتمبر 2011). "فرز البيتابايت باستخدام MapReduce - الحلقة التالية" . تم الاسترجاع 7 أبريل 2014 .
  15. ↑ "برنامج تعليمي حول MapReduce" .
  16. ↑ "Apache/Hadoop-mapreduce" . GitHub . 31 أغسطس 2021.
  17. ↑ "مثال: عدّ مرات تكرار الكلمات" . بحث جوجل . تم الاطلاع عليه في 18 سبتمبر 2013 .
  18. ↑ فيغاراس، ليونيداس (2017). "جبر لتحليلات البيانات الضخمة الموزعة". مجلة البرمجة الوظيفية . 28 e27. doi : 10.1017/S0956796817000193 . S2CID 44629767 . 
  19. ↑ لين، جيمي (29 أبريل 2013). "Monoidify! Monoids as a Design Principle for Efficient MapReduce Algorithms". arXiv : 1304.7544 [ cs.DC ].
  20. ↑ "الجبر المجرد لـ Scala" .
  21. ↑ "ترميز Map-Reduce كـ Monoid مع طي اليسار" . 5 سبتمبر 2016.
  22. 1 2 سينجر، هيرميس؛ جيل-كوستا، فيرونيكا؛ أرانتيس، لوسيانا؛ ماركونديس، سيزار أ.س؛ مارين، ماوريسيو؛ ساتو، ليريا م؛ دا سيلفا، فابريسيو أ.ب. (2015-01-01). "تحليل تكلفة وقابلية التوسع لـ BSP لعمليات MapReduce". التزامن والحوسبة: الممارسة والتجربة . 28 (8): 2503-2527 . doi : 10.1002/cpe.3628 . hdl : 10533/147670 . ISSN 1532-0634 . S2CID 33645927 .  
  23. ^ بيرلينسكا، جوانا؛ دروزدوفسكي ، ماسيج (2010-12-01). “جدولة حسابات MapReduce القابلة للقسمة”. مجلة الحوسبة المتوازية والموزعة . 71 (3): 450-459 . دوى : 10.1016/j.jpdc.2010.12.004 .
  24. ↑ بوساغ زاده، رضا؛ كارلسون، غونار (2013). "مربع المصفوفة المستقل عن الأبعاد باستخدام MapReduce" (ملف PDF) . جامعة ستانفورد . arXiv : 1304.1467 . Bibcode : 2013arXiv1304.1467B . تاريخ الاسترجاع: 12 يوليو 2014 .
  25. ^ نج ، أندرو واي. برادسكي، غاري. تشو، تشنغ تاو؛ أولوكوتون، كونلي؛ كيم، سانغ كيون؛ لين، يي آن؛ يو يوان يوان (2006). "تقليل الخريطة للتعلم الآلي على النواة المتعددة" . NIPS 2006. مؤرشفة من الأصلي في 2010-06-20 . تم الاسترجاع 2009-11-24 .
  26. ↑ رينجر، سي.؛ راغورامان، ر.؛ بنمتسا، أ.؛ برادسكي، ج.؛ كوزيراكيس، سي. (2007). "تقييم MapReduce لأنظمة متعددة النوى والمعالجات". المؤتمر الدولي الثالث عشر لهندسة الحواسيب عالية الأداء ، IEEE، 2007. ص 13. CiteSeerX 10.1.1.220.8210 . doi : 10.1109/HPCA.2007.346181 . ISBN   978-1-4244-0804-7. S2CID 12563671 . 
  27. ↑ هي، ب.؛ فانغ، و.؛ لو، ك.؛ جوفينداراجو، ن.ك.؛ وانغ، ت. (2008). "مارس: إطار عمل MapReduce على معالجات الرسومات" (ملف PDF) . وقائع المؤتمر الدولي السابع عشر حول البنى المتوازية وتقنيات الترجمة - PACT '08 . ص 260. doi : 10.1145/1454115.1454152 . ISBN  9781605582825. S2CID 207169888 . 
  28. ↑ تشين، ر.؛ تشين، هـ.؛ زانغ، ب. (2010). "Tiled-MapReduce: تحسين استخدام موارد تطبيقات البيانات المتوازية على المعالجات متعددة النوى باستخدام التجزئة". وقائع المؤتمر الدولي التاسع عشر حول البنى المتوازية وتقنيات الترجمة - PACT '10 . ص 523. doi : 10.1145/1854273.1854337 . ISBN  9781450301787. S2CID 2082196 . 
  29. ↑ تانغ، ب.؛ موكا، م.؛ شوفالييه، س.؛ هي، هـ.؛ فيداك، ج. (2010). "نحو MapReduce للحوسبة الشبكية المكتبية" (ملف PDF) . المؤتمر الدولي لعام 2010 حول الحوسبة الند للند، والمتوازية، والشبكية، والسحابية، والإنترنت . ص 193. CiteSeerX 10.1.1.671.2763 . doi : 10.1109/3PGCIC.2010.33 . ISBN   978-1-4244-8538-3. S2CID 15044391 . 
  30. ↑ لو، ي.؛ غو، ز.؛ صن، ي.؛ بلال، ب .؛ تشيو، ج.؛ لي، و. (2011). "إطار عمل هرمي لتنفيذ MapReduce عبر المجالات" (ملف PDF) . وقائع ورشة العمل الدولية الثانية حول الأساليب الحسابية الناشئة لعلوم الحياة (ECMLS '11) . CiteSeerX 10.1.1.364.9898 . doi : 10.1145/1996023.1996026 . ISBN  978-1-4503-0702-4. S2CID 15179363 . 
  31. ↑ لين، هـ.؛ ما، إكس.؛ أرتشوليتا، ج.؛ فينغ، دبليو سي؛ غاردنر، إم.؛ تشانغ، زد. (2010). "مون: ماب ريديوس في بيئات انتهازية" (ملف PDF) . وقائع الندوة الدولية التاسعة عشرة لجمعية الحوسبة الآلية حول الحوسبة الموزعة عالية الأداء - HPDC '10 . ص 95. doi : 10.1145/1851476.1851489 . ISBN  9781605589428. S2CID 2351790 . 
  32. ↑ ماروزو، ف.؛ تاليا، د.؛ ترونفيو، ب. (2012). "P2P-MapReduce: معالجة البيانات المتوازية في بيئات الحوسبة السحابية الديناميكية" . مجلة علوم الحاسوب والنظم . 78 (5): 1382-1402 . doi : 10.1016/j.jcss.2011.12.021 .
  33. ↑ دو، أ.؛ كالوجيراكي، ف.؛ غونوبولوس، د.؛ ميليكاينن، ت.؛ تولوس، ف.هـ. (2010). "ميسكو: إطار عمل ماب ريديوس للأنظمة المتنقلة". وقائع المؤتمر الدولي الثالث حول التقنيات المنتشرة المتعلقة بالبيئات المساعدة - بيترا '10 . ص 1. doi : 10.1145/1839294.1839332 . ISBN  9781450300711. S2CID 14517696 . 
  34. ↑ وانغ، ياندونغ؛ غولدستون، روبن؛ يو، ويكوان؛ وانغ، تينغ (مايو 2014). "توصيف وتحسين MapReduce المقيم في الذاكرة على أنظمة الحوسبة عالية الأداء". المؤتمر الدولي الثامن والعشرون للمعالجة المتوازية والموزعة لعام 2014، معهد مهندسي الكهرباء والإلكترونيات. الصفحات 799-808 . doi : 10.1109/IPDPS.2014.87 . ISBN  978-1-4799-3800-1. S2CID 11157612 . 
  35. ↑ "كيف تعمل جوجل" . baselinemag.com. 7 يوليو 2006. اعتبارًا من أكتوبر، كانت جوجل تُشغّل حوالي 3000 مهمة حاسوبية يوميًا عبر MapReduce، وهو ما يُمثّل آلاف أيام العمل الحاسوبية، وفقًا لعرضٍ قدّمه دين. من بين أمور أخرى، تُحلّل هذه العمليات المُجمّعة أحدث صفحات الويب وتُحدّث فهارس جوجل.
  36. ↑ تشامبرز، كريغ؛ رانيوالا، أشيش؛ بيري، فرانسيس؛ آدامز، ستيفن؛ هنري، روبرت ر.؛ برادشو، روبرت؛ وايزنباوم، ناثان (1 يناير 2010). "FlumeJava". وقائع المؤتمر الحادي والثلاثين لجمعية ACM SIGPLAN حول تصميم لغات البرمجة وتنفيذها (ملف PDF) . الصفحات 363-375 . doi : 10.1145/1806596.1806638 . ISBN  9781450300193S2CID 14888571. مؤرشف من الأصل (PDF) بتاريخ 23 سبتمبر 2016. تم الاطلاع عليه بتاريخ 4 أغسطس 2016 . 
  37. ↑ بينغ، د.، ودابك، ف. (أكتوبر 2010). المعالجة التزايدية واسعة النطاق باستخدام المعاملات والإشعارات الموزعة. في OSDI (المجلد 10، الصفحات 1-15).
  38. ↑ "خبراء قواعد البيانات يقفزون فوق سمكة القرش في تقنية MapReduce" .
  39. 1 2 ديفيد ديويت ؛ مايكل ستونبريكر . "MapReduce: خطوة كبيرة إلى الوراء" . craig-henderson.blogspot.com . تم الاطلاع عليه بتاريخ 27-08-2008 .
  40. ↑ "Apache Hive – Index of – Apache Software Foundation" .
  41. 1 2 "HBase – HBase Home – Apache Software Foundation" .
  42. ↑ "Bigtable: نظام تخزين موزع للبيانات المهيكلة" (PDF) .
  43. ↑ غريغ يورغنسن . "خبراء قواعد البيانات العلائقية يتخلون عن تقنية MapReduce" . typicalprogrammer.com . تاريخ الاسترجاع: 11 نوفمبر 2009 .
  44. ↑ بافلو، أندرو؛ بولسون، إريك؛ راسين، ألكسندر؛ عبادي، دانيال جيه؛ ديويت، ديفيد جيه؛ مادن، صموئيل؛ ستونبريكر، مايكل. "مقارنة بين مناهج تحليل البيانات واسعة النطاق" . جامعة براون . تاريخ الاسترجاع: 11 يناير 2010 .
  45. ↑ هيليس، دبليو. داني (1986). آلة الاتصال . مطبعة معهد ماساتشوستس للتكنولوجيا . رقم ISBN 0262081571.
  46. ↑ "ملخص فني لآلة التوصيل طراز CM-2" (ملف PDF) . شركة ثينكينج ماشينز . 1987-04-01 . تاريخ الاسترجاع: 2022-11-21 .
  47. ↑ "ملحق لدليل مرجع لغة ليسب" (ملف PDF) . شركة ثينكينج ماشينز . 1988-09-01 . تاريخ الاسترجاع: 2022-11-21 .
  48. ↑ "مقدمة معمارية ريدي فلو" (ملف PDF) . قسم علوم الحاسوب، جامعة يوتا . 5 أبريل 1986. تاريخ الاطلاع: 21 نوفمبر 2022 .
  49. ↑ رانكا، سانجاي (1989). "2.6 مجموع البيانات". خوارزميات المكعب الفائق لمعالجة الصور والتعرف على الأنماط (ملف PDF) . جامعة فلوريدا . تاريخ الاسترجاع: 8 ديسمبر 2022 .
  50. ↑ بول، رايان (20 يناير 2010). "براءة اختراع جوجل لتقنية MapReduce: ما دلالتها بالنسبة لـ Hadoop؟" . آرس تكنيكا . تاريخ الاسترجاع: 21 مارس 2021 .
  51. ↑ "براءة اختراع الولايات المتحدة رقم 7650331 - نظام وطريقة لمعالجة البيانات واسعة النطاق بكفاءة" . uspto.gov . مؤرشف من الأصل بتاريخ 21-09-2013 . تم الاطلاع عليه بتاريخ 19-01-2010 .
  52. ↑ نازر، دانيال (28 مارس 2013). "جوجل تتعهد بعدم المطالبة بحقوق براءات الاختراع المفتوحة وتقترح نماذج ترخيص جديدة" . مؤسسة الحدود الإلكترونية . تم الاطلاع عليه بتاريخ 21 مارس 2021 .
  53. ↑ كينغ، راشيل (2013). "جوجل توسع تعهدها ببراءات الاختراع المفتوحة ليشمل 79 براءة اختراع أخرى حول إدارة مراكز البيانات" . زد نت . تم الاطلاع عليه بتاريخ 21 مارس 2021 .
  54. ↑ "نظام وطريقة لمعالجة البيانات واسعة النطاق بكفاءة" . بحث براءات اختراع جوجل. ١٨ يونيو ٢٠٠٤. تم الاطلاع عليه بتاريخ ٢١ مارس ٢٠٢١ .
  55. ↑ غوبتا، أوبا؛ فيغاراس، ليونيداس (2013-10-06). "تحليل الرسوم البيانية القائم على الخرائط باستخدام MapReduce" (ملف PDF) . وقائع: المؤتمر الدولي لهندسة الكهرباء والإلكترونيات (IEEE) لعام 2013 حول البيانات الضخمة . المؤتمر الدولي لهندسة الكهرباء والإلكترونيات (IEEE) لعام 2013 حول البيانات الضخمة. سانتا كلارا، كاليفورنيا : IEEE . الصفحات 24-30 . 
  56. ↑ زاهاريا، ماتاي؛ تشودري، مشرف؛ فرانكلين، مايكل؛ شنكر، سكوت؛ ستويكا، أيون (يونيو 2010). سبارك: الحوسبة العنقودية باستخدام مجموعات العمل (ملف PDF) . هوت كلاود 2010.