بخشی از مقاله
چکیده
امروزه داده های بزرگ در بستر رایانش ابری یکی از بزرگترین چالش های تحلیل داده هاست , بنابراین زمانبندی کارهای برای تحلیل بسیار حائز اهمیت است . از سوی دیگر باتوجه ماهیت تجاری رایانش ابری فراهم کنندگان ابر منابع را در صورت تقاضا و در ازای مبلغی به کاربران ارائه می دهند. بنابراین لزوم وجود زمانبندی جهت فراهم نمودن تجاری سازی و بازارگرایی در محیط هادوپ , که یکی از محیط های تحلیل داده در حوزه داده های بزرگ است , احساس میشود .در این مقاله روش زمانبند بازارگرا برای درنظر گرفتن قیمت منابع ، بودجه کاربر و مهلت زمانی به زمانبند Fair هادوپ در رویکرد تجاری ارائه شده است.
کلمات کلیدی:زمانبندی , هادوپ , زمانبند بازار گرا , تجاری سازی , زمانبند , Fair داده های بزرگ , پردازش ابری
-1 مقدمه
در دنیای امروز روند رشد داده ها بصورت نمایی و اجتناب ناپذیر است , این رشد با سرعت زیادی در حال پیشروی است به صورتیکه هر سه سال داده های بزرگ دو برابر بزرگتر میشوند . - 1 - داده های بزرگ داده هایی است که فرارتر از توان پردازشی سیستم های موجود است . به عبارت دیگر داده های بزرگ, بزرگ است , سریع است و نمیتوانیم با معماری های فعلی آن را پردازش کنیم. پس برای اینکه ارزش داده ها را استخراج کنیم نیاز داریم راه جدیدی را معرفی کنیم. - 7 - مقادیر عظیم داده هر سال بو سیله ر سانه های دیجیتال , نوشته های وب , ابزارهای علمی , شبیه سازی و... تولید میشود. داده های بزرگ به سه م شخ صه تعریف می شوند : سایز , تنوع و سرعت تولید . - 6 - سه مشخ صه ذخیره سازی , تحلیل , فهم و ا ستفاده موثر از این داده های عظیم یکی از بزرگترین چالش ها را در صنعت Computing - محا سبه - به میان می آورد.
مدل برنامه نوی سی نگا شت - کاهش - 2 - برای رفع این چالش اولین بار توسط گوگل و بوسیله Jeffery Dean و Sanjay Ghemawat در اندازه محاسبات ابری ارائه شد. - 4 - - 3 - نگاشت-کاهش یک مدل برنامه نویسی و یک پیاده سازی مربوطه برای پردازش و تولید دیتاست های عظیم است - 5 - . در این مدل یک اپلیکیشن بصورت عمل های نگاشت-کاهش متوالی پیاده سازی میشود که هر عمل شامل مرحله نگاشت و کاهش است که تعداد زیادی از آیتم های داده م ستقل را پردازش میکند. این سی ستم از موازی سازی اتوماتیک , توزیع محاسبات , مدیریت کار و تحمل خطا در هر گام پشتیبانی میکند . بنابراین برنامه نویسها میتوانند به الگوریتم های کاربردی بدون نگرانی در باره این موضو عات پیچ یده تمرکز کن ند .نگاشت-کاهش بصورت اتوماتیک خطاها را مدیریت میکند و پیچیدگی تحمل خطا را از دید برنامه نویس مخفی میکند. - - 8
فریم ورک هادوپ - 9 - که بوسیله Doug Cutting ایجاد شده است , پیاده سازی لایه باز به زبان جاوا از بنیاد آپاچی در فریم ورک نگاشت - کاهش است . هادوپ ابزارهایی را برای پردازش وسیعی از داده با استفاده از نگاشت -کاهش فراهم می آورد. هادوپ میتواند در پردازش داده های وسیع بصورت موازی در کلاستر بررگ با تحمل خطای بالا و قابلیت اطمینان ا ستفاده شود و در نتیجه مزایای نگا شت کاهش را برای کاربر فراهم آورد. در اوایل 2008 هادوپ به عنوان سریعترین سیستم مرتب سازی یک ترابایت داده ها رکوردار شد . هادوپ با استفاده از یک کلاستر 910 تایی یک ترابایت داده را در 209 ثانیه مرتب سازی کرد. در اواخر همان سال گوگل در 68 ثانیه و یاهو در 62 ثانیه همین کار را انجام داد. - 10 -
یکی از چالش های موجود در فریم ورک هادوپ نحوه زمانبندی کارها در آن است . همانطور که میدانید مساله زمانبندی برای سیستم های توزیعی ناهمگن از مسائل NP-Complete است و تاکنون الگوریتم های متعددی برای زمانبندی هادوپ ارائه شده است. هدف این زمانبند های هادوپ توزیع عادلانه کارها به نحوی که کاری دچار قحطی ن شود و کار دیگری بی شتری منابع را به خود اخت صاص نداده و نیز الویت و وزن ها رعایت شده و در نهایت از زاویه دید این مقاله رضایت کاربر حفظ شود . هدف این مقاله ارائه روشی بازارگرا است که به زمانبند های هادوپ و در Case Study به زمانبند Fair اضافه شود
و سوای فاکتورهای عادلانه بودن , م ساله Market-Oriented بودن و رضایت بخشی کاربر را که بیشتر در بحث محا سبات ابری به میان می آید را نیز پوشش دهد. در بخش 2 زمانبند های پیشنهاد شده برای هادوپ بصورت خلاصه آورد میشود و در بخش 3 به ارائه روش این مقاله میپردازیم و درنهایت بخش 4 شامل کارهای آیند و نتیجه گیری می باشد.موضوع را دنبال کنند. اولین بند هر بخش یا زیربخش بدون تورفتگی - Intend - است. برای نوشتن اولین بند، از سبک Text1 استفاده کنید. سایر بندها دارای تورفتگی به اندازه 0/5 سانتیمتر است که برای نوشتن آنها باید سبک Text را انتخاب کنید. سعی کنید از نوشتن بندهای طولانی پرهیز کنید. یک بند حداکثر میتواند 10 تا 15 سطر را از یک ستون، به خود اختصاص دهد.
-2 پیشینه تحقیق : الگوریتم های زمانبند هادوپ
الگوریتم پایه هادوپ X.1 برپایه زمانبندی FIFO است که کارها به ترتیب پذیرش اجرا میشوند البته الویت کارها و وزن آنها نیز بعدها به این زمانبند اضافه شده است . فیسبوک و یاهو کارهای تحقیقاتی زیادی را در حیطه الگوریتم های زمانبندی انجام داده اند و بنابراین فیسبوک الگوریتم زمانبندی - 11 - Fair و یاهو الگوریتم - 12 - Capacity را به هادوپ اضافه کرده اند .
-1-2 الگوریتم زمانبندی : FIFO
الگوریتم زمانبند پایه هادوپ از یک صف FIFO استفاده میکند . بعد ازاینکه یک کار به تسک های مجزا تقسیم شد , در صف قرار میگیرد و درصوریتکه از طریق نودهای TaskTracker - در آخرین نسخه های هادوپ - NodeManager مطلع شد که اسلات های خالی وجود دارد , به آنها اختصاص می یابد. ازآنجاییکه هر کار از کل کلاستر استفاده میکند بنابراین بقیه کارها برای آزاد شدن منابع باید منتظر شوند. البته در نسخه های بهبود یافته FIFO الویت و وزن دهی و به اشتراک گذاری منابع به این زمانبند افزوده شده است با این وجود مشکل اختصاص عادلانه منابع بین کارها در این زمانبند وجود دارد .
-2-2 الگوریتم زمانبندی : Fair
شرکت فیسبوک برای زمانبندی منابع کلاستر خود الگوریتم زمانبندی Fair را به جامعه متن باز هادوپ ارائه کرد . - 11 - زمانبند Fair بصورتی عمل میکند که به همه کارها بصورت میانگین, مقدار برابری از منابع اختصاص یابد. اگر تنها یک کار موجود باشد از کل کلاستر استفاده میکند . زمانیکه بقیه کارها اضافه شد , اسلات های خالی تسک به کارهای جدید اختصاص می یابد , بنابراین مقدار برابری از زمان CPU به هر کار تخصیص می یابد. این کار موجب میشود کارهای کوتاه در زمان مقتضی پایان یبند و کارهای بزرگ دچار قحطی نشوند. . - 13 - هدف زمانبند Fair توزیع برابری از منابع محاسباتی در بین کارها / کاربران در یک سیستم است . درواقع زمانبند کارها را بوسیله صف منابع سازماندهی میکند و منابع را به طور عادلانه بین این صف ها به اشتراک میگذارد. در حالت پایه Fair برای هر کاربر یک Pool جداگانه میتوان در نظر گرفت. - در نسخه های X.1 ازین صف ها به Pool تعبیر میشود درحالیکه در نسخه X.2 به صف تغییر یافته است. -
در هر Pool یا صف الویت هر کار از روی وزن آن تعیین میشود . صف ها می توانند وزن بگیرند و نرخ بیشتری از کلاستر را به خود اختصاص دهند. بنابراین در تخصیص اسلات به صف ابتدا آن را به صفی اختصاص میدهد که کمترین تسک جاری را دارد و سپس وزن صف در نظر گرفته میشود و صفی که وزن دو دارد , x2 برابر بیشتر از صفی که وزن یک دارد , اسلات میگیرد و به عبارت دیگر “ اسلات به صفی اختصاص می یابد که حاصل تسک های جاری / وزن مقدار کوچکتری باشد . - 14 - “ الگوریتم بهبود یافته زمانبند - 15 - Fair برای بهبود زمان اجرای هر کار و پایین آوردن انتقال داده ارائه شده است که مشخصه های هر کار و محلیت داده را نیز در نظر میگیرد. الگوریتم Fair محدودیت های FIFO را پوشش میدهد. این الگوریتم کارهای کوچک را به خوبی اجرا میکند حتی اگر در آن کلاستر کارهای بزرگ نیز وجود داشته باشند ولازم به ذکر است که در Fair قابلیت بازپس گیری نیز وجود دارد .
-3-2 الگوریتم زمانبندی : Capacity
طراحی زمانبند Capacity بسیار شبیهFair است تنها تفاوت این الگوریتم با Fair این است که ثبات کارها در صف ها برخلاف Fair بصورت FIFO صورت میپذیرد. هر صف به سازمانی اختصاص داده میشود و منابع بین این صف ها تقسیم میشوند. به عبارت دیگر زمانبند Capacity کارها را به صف های چندگانه مطابق با شرایط قرار میدهد و ظرفیت سیستم خاصی را به هر صف اختصاص میدهد. ایده اصلی این زمانبند اشتراک منابع در دسترس در هادوپ در بین سازمانها است. - 12 -
. برای ماکزیمم کردن استفاده از منابع , این زمانبند به منابع صف های خالی اجازه اختصاص دوباره به صف هایی که از ظرفیت کاملشان استفاده میکنند را میدهد. زمانیکه کارها به آن صف خالی میرسند و تسک های صف دیگر کامل شده باشند , منابع به صف اصلی برگردانده میشوند. در این الگوریتم نیز قایلیت بازپس گیری و نیز الویت دهی به کارها در صف یک سازمان وجود دارد . با اینکه این الگوریتم مشکلات استفاده ناقص از منابع در FIFO را رفع کرده است با این وجود نسبت به دو الگوریتم قبلی پیچیده تر است.
-4-2 الگوریتم ترکیبی با الویت دهی پویا :
این الگوریتم - 16 - برای کاهش تاخیر کارهای همزمان با طول متغیر و تعیین ترتیب کارها برای حفظ محلیت داده ارائه شد . همچین این روش یک ارزش سطح سرویس که کاربر برای QoS تعریف کرده را فراهم می آورد. این الگوریتم برای حجم کار فشرده طراحی شده است و میکوشد محلیت داده را در حین اجرا حفظ کند . - 17 - الگوریتم الویت پویا از یک الگوریتم کوله پشتی حریصانه برای انتساب کار استفاده میکند. این الگوریتم زمانبند منعطفی است که زمان پاسخ برای هادوپ چند -کاربره را بهبود داده است. - البته لازم به ذکر است مقایسه این روش با زمانبند های پایه ای …,Fair در هادوپ 1,1 صورت گرفته است. -
-5-2 الگوریتم زمانبندی : Delay
این الگوریتم - 20 - ساده برای حل مشکل مغایرت بین عادلانه بودن زمانبند Fair و محلیت داده ارائه شد. کارهایی که نمیتوانند تسکی با داده محلی را شروع کنند , قبل از انتخاب تسک غیر محلی مدت زمان مشخصی را منتظر می مانند تا مطمئن شوند اگر نودی تسکی مربوط به آن داده محلی را دارد, ارائه دهد تا اجرا شود. اگر تسک محلی پیدا نشد اجازه می یابند تا تسک Rack محلی را راه اندازی کنند و اگر دوباره مدت زمان مشخصی گذشت و تسکی یافت نشد اجازه می یابند تا تسک غیر محلی را انتخاب کنند تا دچار قحطی نشوند. این زمان معمولا به x1,5 برابر وقفه heartbeat تنظیم میشود. - در نسخه های جدید الگوریتم Fair در هادوپ الگوریتم Delay به کار گرفته شده است -
-6-2 الگوریتم زمانبندی : LATE
الگوریتم - 19 - LATE طولانی ترین زمان تخمین تا پایان, یک زمانبند مبتنی بر Speculative Execution در محیط ناهمگن است که ابتدا وظایف یا تسک های کند را شناسایی میکند و سپس برای آنها چندی کپی پشتیبان بر روی گره های دیگر راه اندازی میکند. زمانیکه تسک کند یا یک کپی پشتیبان از آن خاتمه یافت , همه تسک های مشابه دیگر کشته میشوند. این الگوریتم تسک ها را با تخمین زمان اجرای باقیمانده رتبه بندی میکند و شروع به کپی از تسک با بالاتری رتبه که نرخ پیشرفت کمتری نسبت به مقدار آستانه کندی دارد , میکند. از آنجاییکه LATE بیشتر بر تخمین زمان اجرای باقیمانده تمرکز میکند تا امتیاز یا نمره پیشرفت , PS به صورت Speculative تسک هایی را اجرا میکند که زمان پاسخ کار را بهود خواهند داد , نه اینکه هر تسک کندی را اجرا کند . البته LATE معایبی نیز دارد , اگرچه این الگوریتم از یک استراتژی پیشرفته ای برای راه اندازهی تسک های پشتیبان استفاده میکند, همچنان ممکن است تسک های اشتباه را برای اجرای دوباره انتخاب کند , این امر بخاطر این است که TTE یا زمان باقیمانده تسک های انتخاب شده را صحیح انتخاب نمیکند. همانند زمانبند پایه هادوپ , LATE مقدارهای R1 , R2 , R3 , M1 ,M2 را به ترتیب 0,34 , 0,33 , 0,33 و 1 , 0 انتخاب میکند . این تنظیم ممکن است موجب تخمین اشتباه TTE شود.
-7-2 الگوریتم زمانبندی : SAMR
دراین الگوریتم - 21 - که از - 19 - LATE الهام گرفته شده است , روی هر نود اطلاعات تاریخچه ای نگه داشته میشوند . Tack Tracker اطلاعات تاریخچه ای را میخواند و پارامترهای R1,R2,R3, M1,M2 را با استفاده از این اطلاعات تنظیم میکند. در این زمانبند معادلاتی برای پیدا کردن تسک های کتد و Task Tracker های کند ارائه شده است که زمانبند طبق آنها میتواند تسک های پشتیبان را برای تسک های کند راه اندازی کند. هنگامی که تسک یا تسک هایی روی Task Tracker اجرا میشوند , اطلاعاتی از اجرا را به Task Tracker بازخورد می کنندو اطلاعات تاریخچه ای با استفاده از آنها به روز میشوند . این زمانبند امتیاز پیشرفت تسک را دقیق تر از زمانبند LATE محاسبه میکند و در نتیجه می تواند تسک های پشتیبان را برای تسک های واقعا کندی که زمان اجرای کار را طولانی میکنند , راه اندازی کند. با این حال SAMR این مساله را در نظر نمی گیرد که کارهای مختلف می
