برنامه ریزی تأخیر: یک تکنیک ساده برای دستیابی به محل و انصاف در برنامه ریزی خوشه ای

ماتی زاهاریا

دانشگاه کالیفرنیا ، برکلی ، برکلی ، کالیفرنیا ، مشخصات نمای ایالات متحده

Dhruba Borthakur

Facebook Inc ، Palo Alto ، CA ، USA نمایه مشاهده

جوییدپ سن سارما

Facebook Inc ، Palo Alto ، CA ، USA نمایه مشاهده

ایلملی

یاهوتحقیق ، Suyvale ، CA ، USA نمایه مشاهده

اسکات شنر

دانشگاه کالیفرنیا ، برکلی ، برکلی ، کالیفرنیا ، مشخصات نمای ایالات متحده

یون استویکا

دانشگاه کالیفرنیا ، برکلی ، برکلی ، کالیفرنیا ، مشخصات نمای ایالات متحده

منتشر شده: 13 آوریل 2010 تاریخ انتشار

• 981 استناد
• 4،684
• بارگیری

معیارهای

کل استنادها 981

کل بارگیری 4،684

12 ماه گذشته 158

6 هفته گذشته 15

• هشدارهای استناد را دریافت کنید

هشدار استناد جدید اضافه شد!

این هشدار با موفقیت اضافه شده است و به شما ارسال می شود: هر زمان که رکوردی که انتخاب کرده اید استناد شده است ، به شما اطلاع داده می شود.

برای مدیریت تنظیمات برگزیده هشدار خود ، روی دکمه زیر کلیک کنید. هشدارهای من را مدیریت کنید

هشدار استناد جدید!

لطفا وارد حساب کاربری خود شوید

صرفه جویی در اتصال

نام

Eurosys '10: مجموعه مقالات پنجمین کنفرانس اروپا در زمینه سیستم های رایانه ای

برنامه ریزی تأخیر: یک تکنیک ساده برای دستیابی به محل و انصاف در برنامه ریزی خوشه ای

صفحات 265-278

خلاصه

از آنجا که سازمانها شروع به استفاده از سیستم های محاسبات خوشه ای با داده های فشرده مانند Hadoop و Dryad برای برنامه های بیشتر می کنند ، نیاز به به اشتراک گذاشتن خوشه ها بین کاربران نیاز به رشد دارد. با این حال ، بین انصاف در برنامه ریزی و محل داده ها (قرار دادن وظایف بر روی گره هایی که حاوی داده های ورودی آنها هستند) درگیری وجود دارد. ما این مشکل را از طریق تجربه خود در طراحی یک برنامه ریزی منصفانه برای یک خوشه 600 گره Hadoop در فیس بوک نشان می دهیم. برای پرداختن به درگیری بین محلی و انصاف ، ما یک الگوریتم ساده به نام برنامه ریزی تأخیر را پیشنهاد می کنیم: هنگامی که شغلی که باید مطابق با انصاف برنامه ریزی شود ، نمی تواند یک کار محلی را راه اندازی کند ، منتظر زمان کمی است و به جای آن اجازه می دهد کارهای دیگر را راه اندازی کند. بشرما می دانیم که برنامه ریزی تأخیر در محل کار بسیار بهینه در انواع بار کاری به دست می آید و می تواند ضمن حفظ انصاف ، توان خود را تا 2 برابر افزایش دهد. علاوه بر این ، سادگی برنامه ریزی تأخیر باعث می شود تا تحت طیف گسترده ای از سیاست های برنامه ریزی فراتر از اشتراک منصفانه ، آن را کاربرد داشته باشد.

منابع

1. آمازون EC2. http://aws. amazon. com/ec2/. گوگل دانشکده
2. آپاچی هادوپ. http://hadoop. apache. org. گوگل دانشکده
3. کندو آپاچی. http://hadoop. apache. org/hive/. گوگل دانشکده
4. نقشه Hadoop/آموزش کاهش. http://hadoop. apache. org/common/docs/current/mapred_tutorial. html. گوگل دانشکده
5. معیارهای عملکرد کندو. http://issues. apache. org/jira/browse/hive-396. گوگل دانشکده
6. راهنمای خدمات مدیریت بار کار HP Neoview. smallurlhttp: //www. docs. hp. com/en/544806-001/neoview_wms_guide_r2. 3. pdf. گوگل دانشکده
7. انصاف حداکثر (ویکی پدیا). http://en. wikipedia. org/wiki/max-min_faiess. گوگل دانشکده
8. درخواست برنامه اکتشافی خوشه NSF (سرنخ). http://www. nsf. gov/pubs/2008/nsf08560/nsf08560. htm. گوگل دانشکده
9. وبلاگ رسمی Google: مرتب سازی 1PB با MapReduce. smallurlhttp: //googleblog. blogspot. com/2008/11/sorting-1pb-with-mapreduce.٪html. گوگل دانشکده
10. سیروس باز. http://opencirrus. org/. گوگل دانشکده
11. ارتباط شخصی با هانس زلر از HP. گوگل دانشکده
12. ارتباط شخصی با اوون اومللی از یاهو! تیم Hadoop. گوگل دانشکده
13. مدیر منابع گشتاور. http://www. clusterresource. com/pages/products/torque-resource-manager. php. گوگل دانشکده
14. یاهوبرنامه جدیدی را برای پیشبرد نرم افزار منبع باز برای محاسبات اینترنتی راه اندازی می کند. http://research. yahoo. com/node/1879. گوگل دانشکده
15. J. Beett و H. Zhang. WF 2 Q): بدترین حالت در صف قرار دادن منصفانه. در IEEE InfoCom'96 ، صفحات 120--128 ، 1996. کتابخانه Google Scholardigital
16. J. Bent ، D. Thain ، A. C. Arpaci-Dusseau ، R. H. Arpaci-Dusseau و M. Livny. کنترل صریح در یک سیستم فایل توزیع شده Aware. در NSDI'04 ، 2004. کتابخانه Google Scholardigital
17. A. Chervenak ، E. Deelman ، M. Livny ، M.-H. Su ، R. Schuler ، S. Bharathi ، G. Mehta و K. Vahi. قرار دادن داده ها برای برنامه های علمی در محیط های توزیع شده. در Proc. هشتمین کنفرانس بین المللی IEEE/ACM در مورد محاسبات شبکه (Grid 2007) ، سپتامبر 2007. کتابخانه Google Scholardigital
18. J. Dean و S. Ghemawat. MapReduce: پردازش داده های ساده در خوشه های بزرگ. ارتباطACM ، 51 (1): 107--113 ، 2008. کتابخانه Google Scholardigital
19. A. Demers ، S. Keshav ، and S. Shenker. تجزیه و تحلیل و شبیه سازی یک الگوریتم صف بندی منصفانه. در مجله تحقیقات و تجربه کار در اینترنت ، صفحات 3--26 ، اکتبر 1990. Google Scholar
20. S. Floyd و V. Jacobson. مدل های تقسیم و مدیریت منابع برای شبکه های بسته. معاملات IEEE/ACM در شبکه ، 3 (4): 365--386 ، 1995. کتابخانه Google Scholardigital
21. S. Ghemawat ، H. Gobioff و S.-T. لئونگسیستم Google File. در Proc. SOSP 2003 ، صفحات 29--43 ، 2003. کتابخانه Google Scholardigital
22. B. Hindman ، A. Konwinski ، M. Zaharia ، and I. Stoica. یک بستر مشترک برای محاسبات خوشه ای. در کارگاه موضوعات داغ در محاسبات ابری (Hotcloud) 2009 ، 2009. کتابخانه Google Scholardigital
23. M. Isard ، M. Budiu ، Y. Yu ، A. Birrell و D. Feterly. DRYAD: برنامه های موازی داده های توزیع شده از بلوک های ساختمانی متوالی. در Eurosys 2007 ، صفحات 59--72 ، 2007. کتابخانه Google Scholardigital
24. M. Isard ، V. Prabhakaran ، J. Currey ، U. Wieder ، K. Talwar و A. Goldberg. Quincy: برنامه ریزی منصفانه برای خوشه های محاسباتی توزیع شده. در SOSP 2009 ، 2009. کتابخانه Google Scholardigital
25. J. Nieh و M. S. Lam. یک برنامه ریزی هوشمند برای برنامه های چندرسانه ای. ACM TOCS ، 21 (2): 117--163 ، 2003. کتابخانه Google Scholardigital
26. A. Pavlo ، E. Paulson ، A. Rasin ، D. J. Abadi ، D. J. Dewitt ، S. Madden ، and M. Stonebraker. مقایسه رویکردها به تجزیه و تحلیل داده های در مقیاس بزرگ. در Sigmod'09 ، 2009. کتابخانه Google Scholardigital
27. I. Stoica ، H. Zhang ، and T. Ng. یک الگوریتم منحنی خدمات عادلانه سلسله مراتبی برای خدمات تقسیم لینک ، زمان واقعی و اولویت. در SigComm'97 ، صفحات 162--173 ، سپتامبر 1997. کتابخانه Google Scholardigital
28. D. Thain ، T. Taenbaum و M. Livny. محاسبات توزیع شده در عمل: تجربه کاندور. همزمان و تمرین محاسبات و تجربه ، 17 (2-4): 323--356 ، 2005. کتابخانه Google Scholardigital
29. C. A. Waldspurger. برنامه ریزی قرعه کشی و قدم: مدیریت منابع متناسب با سهم انعطاف پذیر. پایان نامه دکترا ، MIT ، آزمایشگاه علوم کامپیوتر ، 1995. MIT/LCS/TR-667. کتابخانه Scholardigital Google
30. C. A. Waldspurger و W. E. Weihl. برنامه ریزی قرعه کشی: مدیریت منابع متناسب با سهم انعطاف پذیر. در OSDI 94 ، 1994. کتابخانه Google Scholardigital