نگاشت‌کاهش

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

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

دید کلی

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

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

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

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

دید منطقی

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

${\begin{aligned}\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{aligned}}$