بخشی از مقاله
مروری بر پیاده سـازیهای مدل نگاشت کاهش
چکیده
نگاشت کاهش یک مدل برنامهنویسی موازی است. این مدل برنامه نویسی توسط دو تابع مشخص با نام map (نگاشت) و reduce (کاهش) کار میکند. پیاده سازیهای متفاوتی از این مدل وجود دارد. هادوپ یک پیاده سازی متن باز از این مدل می باشد. پیاده سازیهای دیگری برای محیط های مختلف معرفی شده اند. مارس، جهت پردازنده های گرافیکی، فونیکس و phoenix++، برای سیستم های با حافظه مشترک، جی هادوپ، جهت محاسبات توزیع شده در مقیاس بزرگ در سراسر خوشه های متعدد، اس هادوپ و در آخرتوایستر که برای محاسبات دادههای فشرده به کار میرود. تحمل خطا و مقیاس پذیری از مزایای مهم این مدل محسوب میشود. هدف از این مقاله معرفی انواع پیاده سازیهای مدل برنامه نویسی نگاشت کاهش و مقایسه ویژگیهای آنها میباشد.
-1مقدمه
مدل برنامه نویسی نگاشت کاهش یک مدل برنامه نویسی موازی است که اولین بار توسط شرکت گوگل معرفی شد.کتابخانه نگاشت کاهش به طور خودکار محاسبات را موازی سازی کرده و مسائل پیچیده مانند توزیع دادهها، توازن بار و تحمل خطا را پشتیبانی میکند. اولین نسخه از مدل کتابخانه نگاشت کاهش در فوریه 2003 با زبان C++ نوشته و توسط توابع اولیه نگاشت و کاهش در لیسپ و دیگر زبان های تابعی به کار گرفته شد. قبل از توسعه چارچوب نگاشت کاهش، گوگل از صدها پیادهسازی جداگانه برای پردازش و محاسبه پایگاه دادههای بزرگ استفاده می کرد. بسیاری از محاسبات نسبتا ساده، اما دادههای ورودی اغلب بسیار بزرگ بودند. از این رو برای پایان محاسبات در یک مدت زمان مناسب، محاسبات نیاز به صدها کامپیوتر توزیع شده داشتند.مدل نگاشت کاهش بسیار کارآمد و مقیاس پذیر است، از اینرو میتواند برای پردازش پایگاه دادههای بزرگ مورد استفاده قرار گیرد. پیاده سازی-های مختلف از نگاشت کاهش برای موازی سازی محاسبات در محیطهای مختلف وجود دارد. هادوپ یک پیاده سازی متن باز از نگاشت کاهش، در جاوا میباشد .[1] پیاده سازی دیگری با نام مارس برای پردازنده های گرافیکی بکار گرفته شده است. چارچوب نگاشت کاهش پیچیدگیهای برنامهنویسی را پنهان میکند. فونیکس یک پیادهسازی از نگاشت کاهش است، که با هدف حافظه اشتراکی، چند هستهای و سیستمهای چند پردازندهای شکل گرفته است. پیادهسازی جی هادوپ، یک چارچوب نگاشت کاهش است که آن را قادر میسازد محاسبات توزیع شده در مقیاس بزرگ در سراسر خوشه های متعدد را انجام دهد. [2] اس هادوپ یک نسخه بهینه سازی شده هادوپ است و این مدل برای سرعت بخشیدن به کارهای حساس شکل گرفته است.[3][4] در فونیکس ++ محدودیتهای مدل فونیکس حل شده است .[5] در بخش دوم این مقاله مدل برنامه نویسی نگاشت کاهش و در بخش سوم معماری-های پایگاه داده موازی بررسی میشود و به مزایای استفاده از این مدل برنامه نویسی اشاره میگردد. در بخش چهارم انواع پیاده-سازیهای نگاهش کاهش تشریح شده و در بخش پنجم مزایا و معایب هر مدل عنوان میشود و در نهایت در بخش ششم نتیجه گیری آورده شده و به مواردی که میتوان در آینده به بررسی آنها پرداخت اشاره میشود.
-2 مدل برنامه نویسی نگاشت کاهش
یکی ازچالشهای بشردرسالهای اخیر چگونگی پردازش وآنالیزداده-های با حجم عظیم برای بدست آوردن نتایج مطلوب ازآنهاست. یکی ازاین چهارچوب های نرم افزاری که توسط شرکت گوگل ابداع شده است، نگاشت کاهش نامیدهمیشود و هدف آن طراحی و اجرای پردازش داده در مقیاس بزرگ است،این مدل به طورگسترده ازطرف خودآن شرکت برای پردازش حجم عظیم دادههای موتورجستجویش مورداستفاده قرارمیگیرد وبهبرنامهنویساینامکانرامیدهدکهبرنامه-هایی بنویسدکهبتوانندبهطورموازیرویکامپیوترهااجراشوند زیرا برای رسیدن به زمانی منطقی و بهینه پردازشها باید رویهزارانماشینبهطورهمزماناجراشوند.[1] برخی از محاسبات را نمیتوانند با توابع نگاشت و کاهش بیان شوند. به عنوان مثال، شیوه تکرار ژنتیک الگوریتم نمیتواند به طور مستقیم با توابعنگاشت و کاهش بیان شود.[6] الگوریتم ژنتیک موازی به منظور بهبود کارآیی، از پردازشالگوریتم ژنتیک که عموما زمان بسیار طولانی برای مسائل بزرگ میگیرد، تعمیم یافته است. نگاشت کاهش برای پشتیبانی از چنین الگوریتم هایی نیاز به توسعه دارد.
-1-2 توابع نگاشت کاهش
در مرحلهنگاشت گره اصلی ورودیرادریافتمیکندوآنرابهقسمت-هایکوچکترتبدیلمینمایدوآنهارابینگرههایکارگر تقسیممیکند. گره کارگر خودممکناستاینمرحلهراتکرارکندودرنتیجهیکساختاردرختیبهوجودم یآید. در مرحله کاهش گره اصلی جوابقسمت-هایکوچکشدهرادریافتمیکندوآنهارابایکدیگرترکیبمی-کندتاخروجیموردنظرتشکیلشود. برایپیادهسازیایندومرحلهتوابع کاهش ونگاشت وجوددارندکهوظیفهاصلیتوسعهدهندهنوشتنایندوتابعمیباشد. داده هاییکهایندوتابعبررویآنهاکارمیکنندبهصورتجفتهای (key,value)می باشد.[7]
-3 پایگاه داده موازی
معماری موازی به نوعی از معماری گفته میشود که در این نوع معماری سعی شده است که با پیاده سازی روشهای کار موازی کارآیی سیستم را افزایش دهیم. در این نوع سیستمها دادهها می-توانند از لحاظ قرارگیری فیزیکی در قسمتهای مختلف قرار گرفته باشند .[8] ایده اصلی در معماری موازی استفاده از پردازشهای موازی در مراحل مختلف تا آنجا که امکان دارد برای بهبود کارآیی سیستم است. چندین مدل معماری برای سیستم های پایگاه داده موازی وجود دارد که برجسته ترین آنها در شکل نشان داده شده است. : M حافظه ، P :پردازنده ، دیسک به صورت سیلندر نشان داده شده است.
دو روش به اشتراک گذاشتن حافظه و دیسک سخت دارای مشکلی هستند (ایجاد گلوگاه) که با افزایش تعداد کاربران مشخص میشود. در این دو روش با بالارفتن تعداد پردازندهها استفاده از فضای مشترک هم بیشتر میشود، از آنجایی که دادههای منتقل شده در شبکه زیادتر میشود سرعت و در نتیجه کارآیی کل هم کاهش پیدا میکند.[8]
-4 معرفی انواع پیادهسازیهای مدل نگاشت کاهش
-1-4 هادوپ
یکپیادهسازیمتنبازورایگانازمدل نگاشت کاهش می-باشدکهبهطورگستردهتوسطشرکتیاهوبرایاستفادهدرموتورجستجویآنب هکارگرفتهمیشود. چهارچوب هادوپ با زبان جاوا پیادهسازی شده است، اما برای نوشتن برنامه نگاشت کاهش الزامی به استفاده از زبان جاوا وجود ندارد. برای مثال یک مجموعه از API ها (aplication program interface) برای نوشتن نگاشت کاهش در زبان C و حتی اجرای هر گونه فایل قابل اجرا ایجاد شده است. چند نمونه از کاربران این چهار چوب عبارتند از : linkedIn –Facebook - شرکت -IBM یاهو که به نوعی حامی هادوپ هم حسوب می شود.
پیش نیاز ها برای نصب بسته هادوپ بر روی سیستم:
هادوپ از یک هسته به نام هستهی هادوپ تشکیل شده است، که دسترسی به سیستم فایلهایی که هادوپ پشتیبانی میکند را فراهم
می آورد. لیست سیستم فایلهایی که هادوپ پشتیبانی میکند عبارتند از:
(Hadoop Distributed File System )HDFS -1 -2 فایل سیستم ( File Transfer Protocol)FTP
-3 سیستم فایل های فقط خواندنی (Hyper Text Transfer Protocol )HTTP و (security hyper text transfer protocol ) HTTPS
HDFS شامل دو پروسه اصلی، Namenode وتعدادی Datanode است.[6] در بالای سیستم فایل موتور نگاشت کاهش قرار میگیرد. این موتور شامل یک Job Tracker میشود که کلاینتها کارهای مربوط به نگاشت کاهش را بر روی آن قرار میدهند. هر ماشین در خوشه یک فرآیند TaskTracker اجرا می کند. Hadoop می تواند برای اجرای همزمان چندوظیفهی نگاشت در گرههای منفرد پیکربندی شود.[6] مزیت این روش در سیستمهای چند هستهای اجازه اجرا و استفاده کامل از تمام هسته ها است. اگر وظیفه مورد نظر نتواند بر روی یک نود واقعی که دادهها بر روی آن قرار دارند، میزبانی شود اولویت به نودها در همان سطح واگذار می شود. این کار باعث می شود که ترافیک شبکه بر روی ستون فقرات اصلی شبکه کاهش پیدا کند. اگر یک دچار مشکل شود
و یا مهلت زمانیاش به پایان برسد آن قسمت job دوباره زمانبندی میشود. اگر Job Tracker نتواند به کارش ادامه دهد، کل Job از دست میرود و باید از ابتدا دوباره انجام شود .[9]
شکل (3) موتور نگاشت کاهش در هادوپ
برای کارهای کوتاه مدت، در عمل حائز اهمیت است. هر دو چارچوب نگاشت کاهش از گوگل و هادوپ به طور گستردهای برای توان بالا، مقیاسپذیری الاستیک و تحمل خطایشان شناخته شده-اند. زمانی که از هادوپ،برای اجرای کار کوتاه استفاده میکنیم، این باعث کارآیی نسبتا ضعیف میشود. معمولاً کارهای نگاشت کاهش به زمان اجرای محدود اشاره میکند، از ثانیه تا چند دقیقه و با کار نگاشت کاهش طولانی که ساعت طول می کشد مخالف است. برخی از مطالعات نشان میدهد که کار کوتاه بخش بزرگی از کار نگاشت کاهشرا تشکیل میدهد. زمان پاسخ برای کارهای کوتاه مدت در حالاتی مهم است که در آن کاربران نیاز به پاسخ سریع دارند، مانند پرس و جو و یا تجزیه و تحلیل دادههای ثبت شده برای اشکال زدایی، نظارت و هوش تجاری. بهینهسازی زمان اجرای نگاشت کاهش نیز میتواند از کارهایی که منابع سیستم را از نظر زمانی بیش از حد اشغال میکنند، جلوگیری کند، که برای سلامتی یک خوشه خوب است. امروزه تعدادی از پرس و جوهای سطح بالا و سیستم های تجزیه و تحلیل دادهها که در بالای نگاشت کاهش سرویسهایی ارائه میدهند، مانند Sawzall گوگل ،Hive درفیس بوک و pig یاهو وجود دارد. این سیستمها درخواست های کاربران را به وسیلهی تبدیل SQL به یک سری از کارهای نگاشت کاهش که معمولاً کوتاه است، اجرا میکنند. این زبان اعلانی سطح بالا تا حد زیادی می تواند کار توسعه برنامههای کاربردی در نگاشت کاهش را بدون برنامه دستی کدگذاری نگاشت کاهش ساده کند. بنابراین، در عمل، این سیستمها نقشهای مهمتری از برنامه های دستی کد شده ی نگاشت کاهش را بازی میکنند. به عنوان مثال، بیش از 95 درصد کار Hadoop در فیس بوک hand-coded نیست، بلکه توسط hive تولید شده استو بیش از 90 درصد کار نگاشت کاهش در یاهو توسط pig تولید می شود. در واقع، این سیستم به زمان اجرای کارهای نگاشت کاهش بسیار حساس هستند. بنابراین، کاهش زمان اجرای کارهای نگاشت کاهش برای این سیستم ها که به طور گستردهای استفاده میشوند بسیار مهم است. دو بهینه سازی عمده به وسیلهی بهینهسازی مقداردهی اولیهی کار و مراحل پایان آن و فراهم کردن یک مکانیزم پیامهای ارتباطات فوری برای رویداد بحرانی ایجاد میکند. در این روش وظایف یک کار میتواند زمانبندی شده و بلافاصله بدون تأخیر اجرا شود. در نتیجه، فرایند اجرای کار فشردهتر میشود و بهرهگیری از اسلات بر روی TaskTrackers میتواند بسیار بهبود یابد .[3]
-2-4 اس هادوپ
تأکید بیشتری بر بالا بردن بازدهی داده نسبت به کم کردن زمان تأخیر اجرای کاردارد. بهبود عملکرد کار نگاشت کاهش، به خصوص
-3 -4 جی هادوپ
نیازهای محاسباتی برای تجزیه و تحلیل دادههای فشرده با مقیاس بزرگ به طور قابل توجهی افزایش یافته است. مدل نگاشت/کاهش به عنوانیک مدل برنامه نویسی برای پردازش مقیاس بزرگی از داده-های فشرده، بسیار موفق ظاهر شده است. با این حال، پیادهسازی
نگاشت کاهش در حال حاضر در محیط کلاستر عمل میکند و نمیتواند برای مقیاس بزرگ و توزیع شده دادهها در سراسر چندین کلاستر با قدرت باشد. الگوی گردش کار برای پردازش دادههای توزیع شده، محدودیت هایی مانند قابلیت اطمینان و بهرهوری دارد. پیادهسازی جی از هادوپ یک چارچوب نگاشت کاهش است که آن را قادر میسازد محاسبات توزیع شده در مقیاس بزرگ در سراسر خوشه های متعدد را انجام دهد. با استفاده از پردازش موازی دادهها در خوشههای چندگانه، می توان عملیات پردازش را در مراکز محاسباتی مختلف بدون نیاز به کپی کردن داده ها و به صورت همزمان انجام داد. تکرار وظایف نگاشت و کاهش جی هادوپ می-تواند تحمل خطا برای دادههای حجیم در مقیاس بزرگ را فراهم کند. در جی هادوپ هر TaskTracker مسئول محاسبه یک خوشه با صدها یا هزاران گره به جای یک گره واحد است . [2]
