نموذج الهيكلة والتجميع

نموذج الهيكلة والتجميع (بالإنجليزية: نموذج الهيكلة والتجميع) هو نموذج برمجي، طورته شركة جوجل لإجراء عمليات حسابية بشكل متزامن على كمية كبيرة جداً من البيانات (عدة بيتابايت), وتتم هذه العمليات على عدة حواسيب تسمى بالعناقيد الحاسوبية. كما يطلق اسم MapReduce على اسم المكتبة البرمجية لهذا النموذج وليس فقط على النموذج نفسه. باستخدام طريقة الهيكلة والتجميع سيتم معالجة البيانات على ثلاثة مراحل (التجزئة، الخلط، التجميع) وبالانجليزية على التوالي (Map, shuttle ,reduce), اثنتان منهم تتم من قِبَل المستخدم وهما التجزئة والتجميع. -- وبالتالي يمكن إجراء العمليات الحسابية على عدة حواسيب وفي الوقت نفسه، أي بشكل متواز. تكمن أهمية هذه التقنية في الدور الذي تلعبه في توزيع العمليات على عدة حساب وإجرائها بشكل متزامن، ومن ثم جمع النتائج في المرحلة الثانية (الخلط). بصورة أوضح يمكننا القول أننا نقسم المشكلة الكبيرة إلى عدة أجزاء ونحل كل جزء منها على حدا ومن ثم نجمع هذه الحلول مع بعضها لتشكل في النهاية الحل للمشكلة الكبيرة. فكرة هذا النموذج مستوحاة من الدوال Map و Reduce, اللذان يستخدمان بكثرة في البرمجة الوظيفية.

في عام 2010 تم منح براءة اختراع أمريكية على هذه التقنية.

طريقة العمل

MapReduce
Zwischen Ergebnisse: نتائج غير نهائية

الصورة (MapReduce) توضح كيفية حساب البيانات في تقنية الهيكلة والتجميع وهي كالتالي:

• في البداية لدينا البيانات (D,A,T,A) المُراد حسابها، ويتم توزيع هذه البيانات على مجموعة من عمليات الهيكلة Map, وكل عملية تقوم بوظيفة معينة يتم تحديدها من قِبَل المستخدم.
• يتم تنفيذ هذه العمليات بشكل متوازي.
• كل عملية من هذه العمليات تقوم بطرح مخرجاتها الأولية (هذه المخرجات ممثلة باللون الزهري), مع العلم أن العملية الواحدة يمكنها توزيع مخرجاتها على أكثر من مكان تخزين.
• هنا نأتي إلى مرحلة الخلط، حيث يتم خلط هذه البيانات مع بعضها البعض، وهنا أيضاً يتم تبادل البيانات بشكل كبير بين الأجهزة (الأماكن التي تتواجد فيها النتائج الأولية).
• عندما تنتهي مرحلة الخلط فإنه يمكننا القول أنها بداية مرحلة التجميع Reduce (باللون الأزرق).
• يتم هنا إجراء عملية تجميع واحدة لكل مكان تخزين (اللون الزهري) وتتم أيضاً هذه العمليات بشكل متواز، ومن ثم تطرح كل عملية من هذه العمليات مخرجاتها على حدا، وهي (X,Y,Z).

تعريف اقتران الهيكلة والتجميع

يقوم اقتران الهيكلة والتجميع بتحويل قائمة من المدخلات إلى قائمة من المخرجات، وكل قائمة-المدخلات والمخرجات- تتكون من قيم ومفتاح لكل قيمة، كما هو الحال في دوال التجزئة أو ال دالة تجزئة.

$\begin{array}{rr}\mathrm{M}\mathrm{a}\mathrm{p}\mathrm{R}\mathrm{e}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{e}:(K\times V{)}^{*}& \to (L\times W{)}^{*}\\ [(k_1,v_1),\dots ,(k_n,v_n)]& \mapsto [(l_1,w_1),\dots ,(l_m,w_m)]\end{array}$

شرح اقتران الهيكلة والتجميع

• المجموعات $K$ و $L$ تحوي على المفاتيح، بينما تحوي المجموعات $V$ و $W$ على القيم.
• كل المفاتيح $k\in K$ هي من نفس النوع، مثلاً: نص أو String.
• كل المفاتيح $l\in L$ هي من نفس النوع، مثلاً: عدد صحيح.
• كل القيم $v\in V$ هي من نفس النوع، مثلاً: عدد عشري.
• كل القيم $w\in W$ هي من نفس النوع، مثلاً: عدد حقيقي.
• إذا كانت $A$ و $B$ هي مجموعات، فإن $A\times B$ هي مجموعة كل الأزواج $(a,b)$ , بحيث أن $a\in A$ و $b\in B$ (الضرب الديكارتي).
• إذا كانت $M$ هي مجموعة، فإن $M^{*}$ هي مجموعة كل المجموعات التي يمكن تكوينها من عناصر $M$, أو ما تسمى بنجمة كلين.

تعريف اقتران الهيكلة Map واقتران التجميع Reduce

$\begin{array}{rr}\mathrm{M}\mathrm{a}\mathrm{p}:K\times V& \to (L\times W{)}^{*}\\ (k,v)& \mapsto [(l_1,x_1),\dots ,(l_{r_k},x_{r_k})]\end{array}$

أو

$\begin{array}{rr}\mathrm{R}\mathrm{e}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{e}:L\times W^{*}& \to X^{*}\\ (l,[y_1,\dots ,y_{s_l}])& \mapsto [w_1,\dots ,w_{m_l}]\end{array}$