نگاشت‌کاهش

نگاشت کاهش (یا تلخیص و انتخاب) ثبت اختراعی است که چارچوب نرم‌افزاری است که از جانب شرکت گوگل برای پشتیبانی از رایانش توزیع‌شده ارائه شده‌است. این رایانش بر روی مجموعه‌های داده که متشکل از خوشه‌های رایانه‌ای است، صورت می‌گیرد.
این چارچوب با الهام‌گیری از نگاشت و کاهش که در واقع در زبان‌های برنامه‌نویسی تابعی وجود دارد، ایجاد شد. اگرچه آنچه که امروزه استفاده می‌شود دقیقا همان چیزی نیست که مد نظر سازندگان اولیه‌اش است.
کتابخانه‌های نگاشت‌کاهش برای زبان‌های سی++ و سی‌شارپ، ارلارج ،جاوا ،پرل ،پایتون ،روبی ،اف‌شارپ،آر و سایر زبان‌ها نوشته‌شده‌اند.
دید کلی
نگاشت‌کاهش چارچوبی برای پردازش مجموعه‌های عظیمی از داده‌ها بر روی رایانه‌ها(گره‌ها) که بر روی موضوعی خاص فعالیت می‌کنند. این مجموعه روی‌هم رفته به عنوان خوشه شناخته می‌شود(در صورتی که از سخت‌افزاری یکسان بهره برند). پردازش محاسباتی بر روی دادهای ذخیره شده درون سامانه فایل (ساختار نیافته) یا بر روی پایگاه داده (ساختاریافته) قابل اجراست.
گام "نگاشت": گره اصلی ورودی را به قطعاتی کوچک‌تر تقسیم می‌نماید(تقسیم مسئله بزرگ به مسایل کوچک) و سپس تقسیم این مسایل کوچک(زیر مسایل) بین گره‌های کارگر. یک گره کارگر نیز ممکن است این عملیات را به نوبه خود تکرار نماید، که ایجادکننده‌ای ساختاری درختی و چند مرحله‌ای است. هر گره کارگر زیر-مسئله خود را حل نموده و نتیجه را به گره اصلی خود برمی‌گرداند.
گام "کاهش": سپس گره‌ اصلی جواب زیر-مسایل را از گره‌های کارگرش گرفته و خروجی را می‌سازد تا خروجی، که حل مسئله ورودی است، را ایجاد نماید.
برتری نگاشت‌کاهش، در این است که اجازه می‌دهد تا پردازش عملیات‌های پردازش و کاهش توزیع‌شود. فراهم آوردن این امر که هر کدام از این نگاشت‌ها مستقل از دیگران است، که خود متضمن اجرای
موازی این نگاشت‌هاست. اگرچه این گفته در عمل به این صورت خواهد بود که محدود به منابع داده یا تعداد پردازنده‌های نزدیک به آن داده‌است. به صورت مشابه، مجموعه‌ای از کاهنده‌ها می‌توانند فاز کاهش را به انجام رسانند. لازمه این امر آن است که خروجی عملیات نگاشت کلیدی یکسان را در یک زمان به همه کاهنده‌ها ارسال نماید. این روش برای الگوریتم‌هایی که به صورت دنباله‌ای از دستورهای غیرقابل موازی سازی هستند، ناکارآمد است. نگاشت‌کاهش بر روی مجموعه‌های عظیم داده‌ای بهتر جواب می‌دهد تا سرورهای تجاری. مجموعه‌های عظیم داده‌ای را می‌توان به مزارع سرور تعمیم داد. مزارعی که حجمی به بزرگی چندین پتابایت داده را در کسری از ساعت، پردازش می‌نماید. همچنین موازی‌سازی امکان بازسازی بعد از بروز خطای جزیی در سرورها را در طول عملیات فراهم می‌آورد: اگر یکی از نگاشت‌کنندگان یا کاهندگان دچار خطا شود، کار دوباره زمان‌بندی خواهدشد- با فرض اینکه داده‌همچنان در دسترس باشد.
دید منطقی
توابع نگاشت و کاهش از نگاشت‌کاهش با استفاده از ساختار داده‌ای زوج‌مرتب (کلید، مقدار) نمایش داده می‌شود. نگاشت زوج‌مرتبی از داده‌ای با نوع دامنه را گرفته و زوج‌مرتبی از دامنه‌ای دیگر را بازمی‌گرداند.
\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
توضیح:
مقدار و محتوی کلید است، مقدار و محتوی مقادیر است.
همه کلیدها، ، از نوعی یکسان هستند، مثلا رشته.
همه کلیدها، از نوعی یکسان هستند، مثلا عدد صحیح.
همه مقادیر، از نوعی یکسان هستند، مثلا اتم.
همه مقادیر، از نوعی یکسان هستند،مثلا اعدا ممیز اعشاری.
اگر و مجموعه باشند، آنگاه محموعه‌ای از تمام زوج‌مرتب‌هایی به شکل که و (ضرب کارتیزین)
اگر شمارا باشد، آنگاه مجموعه‌ای از نام فهرست‌های محدود با اعضای است (مثل عمگر بستار)- فهرست‌ها می‌توانند تهی باشند.
تابع نگاشت به صورت موازی به هر آیتمی در مجموعه داده ورودی اعمال می‌شود. این عمل به فهرستی که شامل مجموعه‌ای از زوج‌های مرتب (k2,v2) در هربار صدا زدن را تولید می‌نماید.
بعد از آن، چارچوب، نگاشت‌کاهش تمام زوج‌مرتب‌هایی را که کلید یکسان دارند را از تمام فهرست‌ها جمع‌آوری نموده و با هم مجتمع می‌سازد.