بخشی از مقاله
چکیده
به دلیل افزایش نیازمندی به منابع رایانشی سریع، در دسترس و با قابلیت اطمینان بالا، افزایش حجم اطلاعات و کمبود فضای دردسترس و همچنین نیاز به افزایش تمرکز بر روی پروژههای سازمانی به جای اتلاف وقت برای نگهداری سرورها و از همه مهمتر، صرفهجویی در هزینهها، مقوله رایانش ابری مطرح شده است. مدل رایانش ابری با استفاده از مجازی سازی میتواند امکان تخصیص منابع، براساس تقاضا را فراهم آورد.تخصیص مناسب درخواستهای کاربر به ماشینهای مجازی، یعنی داشتن الگوریتم توازن بار مناسب، باعث کاهش زمان پاسخ به مشتری، مقیاسپذیری،کاهش هزینه و افزایش رضایتمندی افرادی که از این سیستمها استفاده میکنند، میشود. در این مقاله الگوریتم جدیدی برای توازن بار ارائه و از نظر زمان پاسخ و Makespan با تعدادی از الگوریتمهای دیگر توازن بار مقایسه شده است. نتایج حاصل از شبیهسازی در نرمافزار کلودسیم، نشان میدهند که این الگوریتم زمان پاسخ و Makespan مناسبی نسبت به الگوریتم-های پیشین دارد.
واژههای کلیدی: رایانش ابری، توازن بار، ماشینهای مجازی، زمان پاسخ، زمان .Makespan
-1 مقدمه
رایانش ابری1 در دههی اخیر از طرف شرکتهای مختلفی که مهمترین آنها مایکروسافت، آمازون و گوگل میباشند، به جهان عرضه شده و به عنوان یکی از مشهورترین و داغترین موضوعات در زمینهی فناوری اطلاعات پدیدار گردیده است. در حال حاضر دنیای فناوری اطلاعات قسمت عظیمی از زندگی مردم را شامل میشود که در کنار آن، این فناوری، نیازهایی مانند امنیت اطلاعات، دسترسی سریع و آسان در هر لحظه، پردازش با قدرت بالا و مهمتر از آن استفاده از سرویسهایی با هزینه پایین میباشد2]،.[1 این تکنولوژی در زندگی روزمره کاربردهای زیادی دارد و برای آسانتر شدن استفاده از منابع سختافزاری، برنامههای کاربردی، شبکهها و زیرساختها به وجود آمده است. رایانش ابری بر پایه TCP/IP بوده و شامل پردازندهها، حافظههای عظیم، شبکه انتقال داده سریع و معماری سیستمهای قابل اعتماد میباشد و بدون پروتکلهای استاندارد حاکم بر شبکه نمیتوان موجودیتی به این فناوری بخشید .[3] سرویسهای این تکنولوژی به سه دسته عمده تقسیم میشوند که عبارتند از: زیرساخت به عنوان سرویس - - 2IaaS ، سکو به عنوان به سرویس - 3PaaS - ، نرمافزار به عنوان سرویس . - 4SaaS -
این رایانش، 5 لایه دارد: مشتری، کاربردی، سکو، زیرساخت و سرورها .[1] در رایانش ابری، شکلهای مختلف ابر را داریم که شامل ابرهای خصوصی5 ، ابر عمومی6 ، ابر گروهی7 و ابر آمیخته8 میباشند .[1] یکی از مهمترین مؤلفههای یک معماری رایانش ابری، مؤلفهی توازن بار9 است. مهمترین وظیفهی این مؤلفه، دریافت کارهای کاربران و توزیع آنها بر روی سرورها و میزبانهای متفاوت میباشد، به گونهای که دسترسی به دادهها تا حد امکان محلی شده و محاسبات نیز به صورت متوازن بر روی هر سرور قرار گیرند. یعنی اینکه، درصد به کارگیری منابع سرورها، تقراًیب یکسان گردد. این عمل رضایت کاربر را حداکثر، زمان پاسخ را حداقل، بهرهبرداری از منابع را افزایش، تعداد رد کارها را کاهش و کارایی سیستم را بالا میبرد .[4]
هدف اصلی توازن بار، بهینهسازی کارایی10 و توان عملیاتی11 است، به طوری-که زمان پاسخ12 نیز کاهش پیدا کند .[5] براساسس حالت جاری سیستم، الگوریتمهای توازن بار به دو دستهی ایستا و پویا تقسیم میشوند. الگوریتمهای توازن بار ایستا به وضعیت فعلی سیستم بستگی ندارند و نیاز به دانش و آگاهی قبلی از سیستم میباشد. با تغییرات بار در زمان اجرا نمیتوانند سازگار شوند. هدف این نوع الگوریتمها، به حداقل رساندن زمان اجرای کار و محدود کردن سربار ارتباطات و تأخیر است. در الگوریتمهای توازن بار پویا، تصمیمگیری برای توازن بار براساس وضعیت فعلی سیستم است و نیاز به دانش قبلی از سیستم نمیباشد. بنابراین از این لحاظ از روش ایستا بهتر هستند. به همین دلیل به بهبود کارایی کلی سیستم با مهاجرت پویای بار، کمک میکنند. یک استراتژی پویمعمولاًا چندین بار اجرا میشود و ممکن است یک کار زمانبندی شده را دوباره به یک میزبان جدید بر اساس حالت پویای محیط سیستم، تخصیص دهد .[6]
تکنیکهای توازن بار در ابر، پارامترهایی را در نظر میگیرند. هدف الگوریتمها، بهبود این پارامترها است تا توازن بار بهینهای را به وجود آورند. این پارامترها عبارتند از: سربار مرتبط، مقیاسپذیری، کارایی، تحمل خطا، زمان مهاجرت، زمان پاسخ، توان عملیاتی و انتشار کربن .[6] زمان Makespan، زمان اتمام آخرین کار در سیستم میباشد. این زمان برای اندازهگیری سودمندی سیستم بسیار مهم است. این استاندارد بهتر است که کم شود .[7] بار کاری13، همان ورودی سیستم است. بار کاری روی هر یک از ماشین-های مجازی میتواند عملکرد سرور اصلی و سایر ماشینهای روی آن را تحت تاثیر قرار دهد. داشتن یک الگوریتم توازن بار مناسب، باعث کاهش زمان پاسخ به مشتری، مقیاسپذیری، کاهش هزینه و افزایش رضایتمندی افرادی که از این سیستمها استفاده میکنند، میشود. در این مقاله الگوریتم جدیدی برای توازن بار ارائه شده که مبتنی بر قدرت پردازش و بارکاری ماشینهای مجازی میباشد و زمان پاسخ و Makespan بهینهای نسبت به الگوریتم-های پیشین دارد. در ادامه ساختار مقاله به صورت زیر میباشد: در بخش 2، پیشینه تحقیق شرح داده شده و در بخش 3، الگوریتم پیشنهادی بیان شده و در بخش 4، ارزیابی و مقایسه کار پشنهادی با تعدادی از الگوریتمهای پیشین صورت گرفته و در نهایت در بخش 5، نتیجهگیری ارائه گردیده است.
-2 پیشینهی تحقیق
الگوریتمهای زیادی به منظور بهبود توازن بار در سالهای اخیر ارائه شده-اند .[5] در این بخش فقط به شرح تعدادی از این الگوریتمها که مقایسه کار پیشنهادی با آنها صورت گرفته، پرداخته شده است.
1-2 الگوریتمهای توازن بار
1-1-2 الگوریتم Round Robin
نام الگوریتم نشان میدهد که به صورت نوبت گردشی عمل میکند. هنگامیکه کنترلکننده مرکز داده14 درخواستی را از مشتری میگیرد متوازن کننده بار15 را آگاه میکند که یک ماشین جدید را به درخواست اختصاص دهد. متوازنکننده بار یک ماشین را به طور تصادفی از لیست ماشینهای مجازی برمیدارد و شناسه آن را به کنترلکننده مرکز داده میفرستد. در این روش درخواست بعدی در یک ترتیب گردشی پردازش میشود .[8]
2-1-2 الگوریتم Throttled
در این الگوریتم ابتدا کاربر درخواستی را به متوازنکننده بار میدهد تا ماشین مجازی که دارای کمترین بار باشد را انتخاب کند و زمانیکه ماشین پیدا شد عملیاتی را که از کاربر میآید به آن ماشین میدهد. فرآیند در ابتدا با نگهداری لیستی از ماشینهای مجازی آغاز میشود و صف را پیمایش میکند. در ابتدا لیستی از ماشینهای مجازی وجود دارد. الگوریتم، ماشینی را که کمترین بار را داشته باشد و همچنین در دسترس باشد را انتخاب میکند و درخواست را به آن میدهد. اگر ماشینی پیدا نشد، متوازنکننده بار مقدار -1 را برمیگرداند و درخواست در صف قرار میگیرد 9] ، .[10
3-1-2 الگوریتم Active Monitoring
این الگوریتم جدول شاخص ماشینهای مجازی و تعداد درخواستهای اختصاص داده شده به آنها را حفظ میکند. ابتدا تعداد درخواستهای اختصاص داده شدهی ماشین مجازی، صفر میباشد. وقتی که درخواست تخصیص یک ماشین مجازی جدید از کنترلکننده مرکز داده رسید، متوازنکننده بار جدول را بررسی میکند و ماشین مجازی که کمتر از بقیه بارگیری شده است را شناسایی میکند. اگر مقدار آن در جدول بیشتر از یک بود، به عنوان اولین ماشین مجازی، انتخاب میشود. متوازنکننده بار، شناسهی ماشین مجازی را به کنترلکننده مرکز داده برگشت میدهد. کنترلکننده مرکز داده، درخواست را به ماشین مجازی شناسایی شده توسط همان شناسه، ارسال میکند. در این مرحله کنترلکننده مرکز داده، به متوازنکننده بار، برای تخصیص دادن بعدی هشدار میدهد 10]، .[9
4-1-2 الگوریتم Central Load Balancer - CLB -
در این تکنیک هر درخواستی از سوی کاربر، به سمت کنترلکننده مرکز داده میرود. کنترلکننده مرکز داده، به متوازنکننده بار پیغام می-دهد که یک درخواست برای تخصیص وجود دارد. متوازنکننده بار یک جدول دارد شامل شناسهی ماشینهای مجازی، وضعیت و اولویت آنها است. متوازنکننده بار جدول را جستجو میکند و ماشین مجازی با بالاترین اولویت را پیدا میکند، سپس وضعیت ماشین مجازی را بررسی میکند که اگر در دسترس باشد، متوازنکننده بار، شناسه ماشین مجازی را برمیگرداند و اگر ماشین مجازی مشغول بود، ماشین با اولویت کمتر را انتخاب میکند. در نهایت کنترلکننده مرکز داده درخواست را به ماشینی که متوازن کننده بار شناسه آن را دارد، اختصاص میدهد. در این الگوریتم اولویت هر ماشین مجازی بر اساس سرعت CPU و حافظه محاسبه می-شود. طبق مقایسهای که در [11] صورت گرفته این الگوریتم زمان پاسخ بهتری نسبت به الگوریتمهای Round Robin، Active Monitoring و Throttled دارد.
-3 شرح الگوریتم پیشنهادی
یکی از پارامترهای مهم کیفیت سرویس، زمان پاسخ به مشتری میباشد که کاهش آن، رضایت بیشتر مشتری را فراهم میکند. الگوریتم پیشنهادی، زمان پاسخ و Makespan را کاهش میدهد. در رایانش ابری تعدادی مرکز داده وجود دارد و در مراکز داده، میزبانها و سرورها هستند که روی آنها ماشینهای مجازی وجود دارند. اینکه ماشین مجازی روی کدام میزبان قرار گیرد و درخواست رسیده از سمت کاربر را کدام ماشین مجازی اجرا کند، دو بحث متفاوت میباشند که به اولی مجازی سازی در سطح میزبان و به دومی مجازی سازی در سطح ماشین مجازی میگویند .[5] درخواستهایی که از سمت کاربران به سمت مراکز داده میآیند باید به نحوی اجرا شوند، اینکه کدام ماشین مجازی درخواست را اجرا کند در مقوله کار ما میباشد. الگوریتمها و سیاستهای مختلفی در این زمینه وجود دارند که نشان میدهند، درخواست به کدام ماشین مجازی اختصاص یابد و مزایا و معایب هر کدام از الگوریتمها و اینکه هر کدام منجر به بهبود چه پارامتری میشوند، در کارهای قبلی بحث شدهاند. هدف الگوریتم پیشنهادی، این است که درخواستها به نحوی به ماشینهای مجازی اختصاص داده شوند که زمان پاسخ و Makespan بهینه شوند. الگوریتم پیشنهادی، به این صورت عمل میکند که اگر درخواستی برای اجرا وجود داشته باشد آن درخواست به ماشینی اختصاص داده میشود که بارکاری روی آن کمتر و قدرت پردازشی آن، بالاتر باشد.
دلیل در نظر گرفتن این دو پارامتر به طور همزمان، این است که اگر انتخاب فقط براساس بارکاری روی ماشین مجازی صورت گیرد و ماشینی با بارکاری کم، انتخاب شود، ممکن است درخواست جاری نیاز به ماشین مجازی با قدرت پردازش بالا داشته باشد اما قدرت پردازش ماشین مجازی منتخب، پایین باشد، که در اینصورت انتخاب درستی صورت نگرفته است. اگر انتخاب فقط براساس قدرت پردازش بالای ماشین مجازی باشد، ممکن است ماشینی با قدرت پردازش بالا انتخاب شود ولی بارکاری روی آن به قدری زیاد باشد که درخواست مجبور شود مدت زمان زیادی را صبر کند، بنابراین باید به هر دو پارامتر به طور همزمان توجه شود و ماشینی انتخاب شود که بارکاری روی آن کم و قدرت پردازش آن بالا باشد. با توجه به بارکاری روی ماشین مجازی، زمان انتظار برای درخواست جاری و با توجه به سرعت پردازنده، زمان پردازش برای درخواست جاری به دست میآید. در نهایت، درخواست به ماشینی اختصاص داده میشود که مجموع زمان پردازش و انتظار آن، کمترین مقدار را داشته باشد.
1-3 مراحل الگوریتم پیشنهادی
-1 ابتدا لیستی از درخواستها و ماشینهای مجازی وجود دارد. برای تعیین اینکه درخواست به کدام ماشین مجازی اختصاص داده شود، مراحل ذکر شده در پایین برای هر درخواستی انجام میشود.
-2 کنترلکننده مرکز داده درخواست جدیدی را دریافت میکند.
-3 وقتی درخواست جدیدی از سوی کاربر میآید کنترلکننده مرکز داده به متوازنکننده بار، گزارش آن را میدهد تا متوازن-کننده بار، ماشین مجازی مناسب را برای اجرای آن درخواست، پیدا کند.
-4 متوازنکننده بار، بارکاری همهی ماشینهای مجازی را به دست میآورد. برای این منظور، باید زمان انتظار را برای درخواست جاری روی همهی ماشینهای مجازی محاسبه کند. این زمان، ارتباط مستقیمی با بار روی ماشین مجازی دارد. هر چه بار روی ماشین مجازی بیشتر باشد، زمان انتظار بیشتر و هر چه بار روی ماشین مجازی کمتر باشد، زمان انتظار کمتر میشود. هر درخواست یا کار، یک طول - ℎ - دارد، که به معنی تعداد دستورالعملهای درونی آن میباشد. زمان انتظار به صورت زیر محاسبه میشود: درخواستهایی که روی ماشین مجازی قرار دارند را نشان می-دهد، که همان بار روی ماشین مجازی میباشد. : - - سرعت پردازندهی ماشین مجازی را نشان میدهد که واحد آن میلیون دستورالعمل در واحد ثانیه میباشد.
-5 متوازنکننده بار، قدت پردازش ماشین مجازی را به دست می-آورد. برای این منظور باید، زمان اجرا را برای درخواست جاری، روی همهی ماشینهای مجازی، محاسبه کند. این زمان ارتباط معکوسی با قدرت پردازش ماشین مجازی دارد. هر چه قدرت پردازش ماشین مجازی بالاتر باشد زمان اجرا کمتر و هر چه قدرت ماشین مجازی پایینتر باشد، زمان اجرا طولانیتر می-شود.
