نگاشت‌کاهش

نگاشت کاهش (یا تلخیص و انتخاب)(به انگلیسی: MapReduce) ثبت اختراعی است که چارچوب نرم‌افزاری است که از جانب شرکت گوگل برای پشتیبانی از رایانش توزیع‌شده ارایه شده‌است. این رایانش بر روی مجموعه‌های داده که متشکل از خوشه‌هایِ رایانه‌ای‌ است، صورت می‌گیرد.

این چارچوب با الهام‌گیری از نگاشت و کاهش که در واقع در زبان‌های برنامه‌نویسی تابعی وجود دارد، ایجاد شد. اگرچه آنچه که امروزه استفاده می‌شود دقیقا همان چیزی نیست که مد نظر سازندگان اولیه‌اش است. کتابخانه‌هایِ نگاشت‌کاهش برای زبان‌های سی++ و سی‌شارپ٬ ارلارج ٬جاوا ٬پرل ٬پایتون ٬روبی ٬اف‌شارپ٬آر و سایر زبان‌ها نوشته‌شده‌اند.

دید کلی

نگاشت‌کاهش چارچوبی برای پردازش مجموعه‌های عظیمی از داده‌ها بر روی رایانه‌ها(گره‌ها) که بر روی موضوعی خاص فعالیت می‌کنند. این مجموعه‌ روی‌هم رفته به عنوان خوشه شناخته‌ می‌شود(در صورتی که از سخت‌افزاری یکسان بهره‌ برند). پردازش محاسباتی بر روی دادهایِ ذخیره شده درون سامانه‌ فایل (ساختار نیافته) یا بر روی پایگاه داده (ساختاریافته) قابل اجراست.

گامِ "نگاشت": گره اصلی (به انگلیسی: Master Node) ورودی را به قطعاتی کوچک‌تر تقسیم می‌نماید(تقسیم مساله‌ی بزرگ به مسایل کوچک) و سپس تقسیم این مسایل کوچک(زیر مسایل) بین گره‌های کارگر. یک گره کارگر نیز ممکن است این عملیات را به نوبه‌ی خود تکرار نماید، که ایجاد کننده‌ای ساختاری درختی و چند مرحله‌ای است. هر گره کارگر زیر-مساله‌ی خود را حل نموده و نتیجه را به گره اصلیِ خود برمی‌گرداند.

گامِ "کاهش": سپس گره‌ِ اصلی جواب زیر-مسایل را از گره‌های کارگرش گرفته و خروجی را می‌سازد تا خروجی، که حل مساله‌ی ورودی است، را ایجاد نماید.

برتری نگاشت‌کاهش، در این است که اجازه می‌دهد تا پردازش عملیات‌های پردازش و کاهش توزیع‌شود. فراهم آوردن این امر که هر کدام از این نگاشت‌ها مستقل از دیگران است، که خود متضمن اجرای موازی این نگاشت‌هاست. اگرچه این گفته در عمل به این صورت خواهد بود که محدود به منابع داده یا تعداد پردازند‌ه‌های نزدیک به آن داده‌است. به صورت مشابه، مجموعه‌ای از 'کاهنده‌ها' می‌توانند فاز کاهش را به انجام رسانند. لازمه‌ی این امر آن است که خروجی عملیات نگاشت کلیدی یکسان را در یک زمان به همه کاهنده‌ها ارسال نماید. این روش برای الگوریتم‌هایی که به صورت دنباله‌ای از دستورهای غیرقابل موازی سازی هستند، ناکارآمد است. نگاشت‌کاهش بر روی مجموعه‌های عظیم داده‌ای بهتر جواب می‌دهد تا سرورهای تجاری. مجموعه‌های عظیم داده‌ای را می‌توان به مزارع سرور تعمیم داد. مزارعی که حجمی به بزرگی چندین پتابایت داده را در کسری از ساعت، پردازش می‌نماید. همچنین موازی‌سازی امکان بازسازی بعد از بروز خطایِ جزیی در سرورها را در طول عملیات فراهم می‌آورد: اگر یکی از نگاشت‌کنندگان یا کاهندگان دچار خطا شود، کار دوباره زمان‌بندی خواهدشد- با فرض اینکه داده‌همچنان در دسترس باشد.

دید منطقی

توابع نگاشت و کاهش از نگاشت‌کاهش با استفاده از ساختارِ داده‌ایِ زوجِ‌مرتب (کلید، مقدار) نمایش داده می‌شود. نگاشت زوج‌مرتبی از داده‌ای با نوعِ دامنه را گرفته و زوج‌مرتبی از دامنه‌ای دیگر را بازمی‌گرداند.

$\begin{align} \mathrm{MapReduce} : (K\times V)^* &\to (L\times W)^* \\ {\lbrack(k_1, v_1), \ldots, (k_n, v_n)\rbrack} &\mapsto \lbrack (l_1, w_1), \ldots, (l_m, w_m)\rbrack \end{align}$

توضیح:

• مقدار $K$ و $L$ محتوی کلید است، مقدار $V$ و $W$ محتوی مقادیر است.
• همه‌ی کلیدها٬ $k \in K$، از نوعی یکسان هستند، مثلا رشته.
• همه‌ی کلیدها٬ $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$ است (مثل عمگر بستار)- فهرست‌ها می‌توانند تهی باشند.

تابع نگاشت به صورت موازی به هر آیتمی در مجموعه‌ی داده‌ی ورودی اعمال می‌شود. این عمل به فهرستی که شامل مجموعه‌ای از زوج‌های مرتب (k2,v2) در هربار صدا زدن را تولید می‌نماید. بعد از آن، چارچوب، نگاشت‌کاهش تمام زوج‌مرتب‌هایی را که کلید یکسان دارند را از تمام فهرست‌ها جمع‌آوری نموده و با هم مجتمع می‌سازد.