الگوریتم MAP REDUCE چیست؟

هدوپ (Hadoop) یک نرم افزار کد باز (Open source) است که برای تقسیم بندی و توزیع فایل های متمرکز به کار می رود. هدوپ تحت لیسانس آپاچی (Apache) ارائه می شود و توسط جاوا برنامه نویسی شده است که از دو بخش کلّی به نام HDFS و Map Reduce تشکیل شده است .این سیستم در واقع جهت اجرا بر روی چندین سرور طراحی شده است .برای درک بهتر این موضوع به تصویر زیر دقّت کنید.

سیستم بدین‌صورت عمل می‌کند که اطلاعات دریافت شده به‌صورت تکه‌تکه (به‌طور پیش‌فرض بلاک‌های ۶۴ مگابایتی) درآمده و هر تکه در یک سرور جداگانه ذخیره می‌شود. در تصویر بالا سرور Namenode درواقع همان سرور اصلی (Master) می‌باشد که وظیفهٔ کنترل سرورهای دیگر (Slave) را به عهده دارد. بخش Map Reduce نیز بر روی سرور اصلی اجرا می‌شود و بخش HDFS یا همان Hadoop Distributed File System بر روی سرورهای جانبی اجرا می‌شود. سرورهای جانبی وظیفهٔ ذخیره‌سازی اطلاعات را بر روی هارد دیسک‌های خود به عهده‌دارند. یعنی زمانی که کاربر درخواست فراخوانی یک فایل راصادر می کند، سرور اصلی از طریق آدرس‌هایی که در اختیار دارد، بلاک‌های موردنظر را از سرورهای مختلف فراخوانی کرده و پس از سر هم کردن و تکمیل کردن فایل، آن را به کاربر تحویل می‌دهد.

نگاشت کاهش( MAP REDUCE)

MAP REDUCE یک مدل برنامه‌نویسی استفاده‌شده توسط گوگل برای پردازش حجم زیادی از داده‌ها در یک محیط محاسباتیتوزیع‌شده است. MAP REDUCE معمولاً برای انجام محاسبات توزیع‌شده بر روی خوشه‌ای از کامپیوترها مورداستفاده قرارمی گیرد. مفهوم Map Reduce توسط گوگل در سال ۲۰۰۴ توسعه داده شد و ارائه شد. پردازش محاسباتی داده‌های ذخیرهشده در یک فایل سیستم یا پایگاه داده رخ می‌دهد. در MAP REDUCE استفاده از محل داده‌ها، پردازش داده‌ها و یا نزدیکمناطق ذخیره‌سازی زمان‌بر است درنتیجه باید از انتقال داده‌های غیرضروری اجتناب کرد. از سادگی مدل برنامه سادگی و رسیدگیاتوماتیک از عدم موفقیت گره پنهانی پیچیدگی تحمل خطا در MAP REDUCE برای هردو برنامهٔ کاربردی تجاری و علمیاستفاده می‌شود. یک چارچوب نرم‌افزاری است که بستری امن و مقیاس‌پذیر برای توسعه کاربردهای توزیعی فراهم می‌کند. Map Reduce به زبان‌های مختلف پیاده‌سازی شده است.

برنامه‌ریزی یکی از عوامل مهم است که در خوشه MAP REDUCE در نظر گرفته‌شده است که آن را محبوب کرده است. به‌منظور دستیابی به عملکرد بهتر یک زمان‌بندی MAP REDUCE باید از انتقال داده‌های غیرضروری اجتناب کرد. ازاین‌رو الگوریتم‌های زمان‌بندی مختلفی برای ارائه عملکرد بهتر MAP REDUCE لازم است.

Map Reduce یک چارچوب نرم‌افزاری است که بستری امن و مقیاس‌پذیر برای توسعه کاربردهای توزیعی فراهم می‌کند. Map Reduce به زبان‌های مختلف پیاده‌سازی شده است. درواقع Map Reduce مجموعه‌ای از توابع کتابخانه را در دل خود دارد که جزئیات و پیچیدگی را از دید برنامه‌نویس پنهان می‌کند. جزئیات Map Reduce شامل موارد زیر می‌شود:

موازی‌سازی کارها به‌صورت خودکار

تعادل در بار محاسباتی و داده

بهینه‌سازی در انتقالات دیسک و شبکه

اداره کردن نقص‌های رخ‌داده در ماشین‌ها

علاوه بر اینکه هر بهبودی که در کتابخانه ایجاد شود، تمام جاهایی که از آن استفاده‌شده نیز بهبود اعمال می‌شود.
چهار الگوریتم زمان‌بندی مختلف برای MAP REDUCE عبارتنداز:

۱- الگوریتم برنامه ریزی در هدوپ

۲- طولانی‌ترین زمان برای پایان دادن (LEAT)

۳- الگوریتم زمان‌بندی MAP REDUCE، خود تطبیقی MAP REDUCE

۴- الگوریتم زمان‌بندی و پیشرفت الگوریتم زمان‌بندی خود تطبیقیESAMR) MAP REDUCE)

یک نمای کلی از این تکنیک‌ها از طریق ارائه‌شده و مزایا و معایب این الگوریتم‌ها توضیح داده‌شده است.

معرفی:

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

برنامه‌نویسی،MAP REDUCE یکی از نمونه‌های برنامه‌نویسی محبوب است که پردازش مقدار زیادی از داده‌ها را به‌صورت موازی قادر می‌سازد. MAP REDUCE یک مدل برنامه‌نویسی و یک پیاده‌سازی مرتبط برای پردازش و تولید Dataset های بزرگ می‌باشد. بر اساس این مدل، هر نرم‌افزار به‌عنوان دنباله‌ای از عملیات MAP REDUCE متشکل از یک مرحلهٔ Map و یک مرحلهٔ Reduce است که برای پردازش تعداد زیادی از داده‌های مستقل است. این دو عمل اصلی، بر روی یک زوج مرتب(key, value) اعمال می‌شود. تابع، Map یک زوج مرتب از داده را گرفته و  به لیستی از زوج مرتب ها تبدیل میکند:

(Map (k1, v1) -> list (k2, v2

سپس، چارچوب، Map Reduce همه زوج‌ها با کلید یکسان را از همه لیست‌ها جمع‌آوری کرده و آن‌ها را باهم، یک گروه می‌کند. پس به ازای هر کلید تولیدشده، یک گروه ایجاد می‌شود. حال تابع، Reduce بر روی هر گروه اعمال می‌شود:

(Reduce (k2, list (v2)) -> list(v3

حال چارچوب، Map Reduce یک لیست از  (key, value) ها را به لیستی از value ها تبدیل می‌کند. دستگاه باید به‌طور مؤثر قادر به پردازش یک لیست از (key, value) ها برای چارچوب Map Reduce در حافظهٔ اصلی باشد.

یکی از ویژگی‌های مهم MAP REDUCE این است که گره‌هایی که با شکست مواجه شده‌اند به‌صورت خودکار دسته‌بندی می‌کند و پیچیدگی تحمل خطا از دید برنامه نویسان پنهان کرده است. پردازش موازی نیز بازیابی شکست بخشی از سرورها در طول عملیات فراهم می‌کند.

سیستم زمانبندی:MAP REDUCE
اجرای سیستم برنامه‌ریزی MAP REDUCE شامل شش مرحله است:

 

 

۱- داده‌های ورودی را به M قطعه ۱۶ مگابایتی برای هر ۱۶ مگابایت تقسیم می‌کند. سپس چند نسخه از برنامه روی یک خوشه از ماشین شروع می‌شود.

۲- یک بسته از برنامه سرور (اصلی) می‌شود و بقیه توسط این بسته به کار گرفته می‌شود. سپس وظایف به Map و Reduce اختصاص داده می‌شود و هر زمان که کار Map یا Reduce تمام شد یک بسته توسط سرور به آن‌ها اختصاص داده می‌شود.

۳- محتویات ورودی متناظر یک کارگربین Map ها به‌صورت اختصاصی تقسیم‌شده است. پس از تجزیه جفت (Key/Value) مقداری از داده‌های ورودی، از آن به‌عنوان تابع تعریف‌شده توسط تابع Map عبور می‌کنیم. متوسط جفت Key/Value توسط تابع Map در حافظهٔ بافر تولیدشده است.

۴- جفت بافر، دیسک‌های محلی و نوشته‌شده و توسط تابع پارتیشن‌بندی دوره‌ای جزء بندی می‌شود. محل این جفت بافر روی دیسک محلی هست که مسئولیت ارسال به کارگران برای برگشت به سرور را کاهش می‌دهد.

۵- درحالی‌که سرور مکان بستهٔ کارگر Reduce را اطلاع‌رسانی می‌کند اطلاعات بافر خوانده‌شده از کارگران Map را از راه دور مورداستفاده قرار می‌دهد.

۶- کارگر Reduce تعامل بیشتری با داده‌های میانی ذخیره‌شده دارد. این کلید و مجموعهٔ مربوط از ارزش متوسط عبور در برابر کاربران تابع Reduce برای هر کلید میانی منحصربه‌فرد مواجه شده است. برای پارتیشن‌های،Reduce خروجی تابع Reduce به یک فایل خروجی نهایی اضافه خواهد شد.

۷- بعدازاینکه همهٔ وظایف Map و Reduce تکمیل شد، سرور به برنامه و MAP REDUCE پاسخ مناسب می‌دهد. فایل‌های خروجی REDUCE به خروجی MAP REDUCE فرستاده می‌شود و پس‌ازآن پاسخ پایانی موفقیت‌آمیز را می‌دهد. کاربران ترکیب فایل‌های خروجی REDUCE در یک فایل را لازم ندارند، آن‌ها به‌طورمعمول این فایل را به‌عنوان ورودی به یکی دیگر از  MAP REDUCE  ها می دهد.

الگوریتم برنامه‌ریزی MAP REDUCE:

Apache Hadoop یک چارچوب منبع باز برای پردازش موازی MAP REDUCE است. هدوپ به برنامه نویسان اجازه می‌دهد تا از برنامه‌های پردازش موازی استفاده کنند. که جزئیات اجرای موازی را از دید کاربر پنهان می‌کند و بر روی مسائل محاسباتی متمرکز می‌کند. قطعات اصلی در معماری هدوپ، سیستم فایل توزیع‌شده هدوپ ()۶()HDF است که مقدار بسیاری از داده‌ها در سراسر دستگاه‌های متعدد با توان عملیاتی بالا را ذخیره می‌کند و دسترسی به داده‌ها در خوشه‌ها و چارچوب هدوپ MAP REDUCE که پردازش داده‌های روی خوشه را به صورتت توزیع‌شده انجام می‌دهد را فراهم می‌کند.

رسیدن به قابلیت اطمینان و تحمل خطا در چارچوب MAP REDUCE با ذخیره و تکرار ورودی و خروجی از وظایف هدوپ است. سیاست برنامه‌ریزی باید به‌منظور تعیین مشخصه استفاده شود وقتی‌که یک کارگر می‌تواند وظایف خود را اداره کند بعدازآن کارگران هدوپ منابع خوشه را به اشتراک می‌گذارند.

به اشتراک بگذارید:

یک دیدگاه