بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
تخصیص قطعه در پایگاه داده توزیع شده با استفاده از الگوریتم کولونی مورچهها
چکیده:
تخصیص قطعه یکی از مسائل مهم در پایگاه داده توزیع شده میباشد که عبارت از تعیین محل ذخیرهسازی دادهها در گرههای مختلف شبکه است، به نحوی که در هنگام اجرای پرسوجوها هزینه انتقال دادهها بر روی مسیرهای شبکه کمینه گردد. دو عامل تاثیرگذار در این مساله تنوع و تعداد تراکنشهای بازیابی دادهها و تراکنشهای بروزرسانی دادهها میباشد. تخصیص قطعه مناسب باید بتواند تعادلی بین تراکنش های بازیابی و بروزرسانی ایجاد نماید تا در مجموع هزینه ناشی از اجرای همه تراکنشها کمینه گردد. با توجه به نقش تکرارسازی دادهها در پایگاه دادههای توزیعی، مشاهده می شود که این دو عامل در تقابل با یکدیگرند زیرا تکرارسازی دادهها کارایی سیستم را در اجرای تراکنش های بازیابی افزایش میدهد. ولی از سوی دیگر سبب کاهش کارایی اجرای تراکنشهای بهنگام سازی می شود. مساله تخصیص قطعه یک مساله NP-Complete بوده و راه حلهای متفاوتی در سالهای اخیر برای آن ارائه شده است. اما اغلب این روشی ها از نظر میزان هزینه با حالت بهینه فاصله قابل توجه ای دارند. در این مقاله از مدل ارائه شده توسط هیونگ و چن" استفاده شده است که مبتنی بر بازتاب رفتار تراکنشی ها در پایگاه داده توزیعی، میباشد و بر اساس این مدل و اطلاعات تراکنشها الگوریتمی برای پیدا کردن تخصیص نزدیک به بهینه، از نوع الگوریتمهای تکاملی توسعه داده شده است. نتایج حاصل از الگوریتم پیشنهادی نشان می دهد که هزینه اجرای تراکنشها، در مقایسه با الگوریتمهای هیورستیک اول و دوم هیونگ و چن به ترتیب ۵۰٪ و ۴۸٪ و نسبت به الگوریتم مورفی " و همکارانش، ۴۲٪ بهبود یافته است
۱- مقدمه
در سالهای اخیر سیستمهای اطلاعاتی توزیع شده رشد عظیمی داشته اند. این سیستمها با نیاز سازمانهای غیر متمرکز سازگاری زیادی دارند دلیل این امر، ظرفیت بالای سیستمهای توزیع شده در تطابق با ساختارهای فیزیکی این سازمانها است. سیستمهای اطلاعاتی توزیع شده دارای پیچیدگی های متعددی بوده و طراحی و پیادهسازی آنها با چالشهای متعددی همراه است. ا۱]
این پیچیدگی به دلیل وجود مسائل به هم مرتبط زیادی از قبیل چگونگی قطعه بندی یک رابطه، تعداد تکرار هر قطعه و نحوه تخصیص قطعات به سایت ها، در طراحی این سیستمها می باشد. حتی اگر هریک از موارد فوق به تنهایی بررسی شود، طراحی سیستمهای اطلاعاتی توزیعی، همچنان دارای پیچیدگی زیاد است. به همین دلیل به منظور سادهسازی، فرض شده است که همه روابط موجود در سیستم از قبل قطعه بندی شده میباشند. بنابراین در این جا مسئله اصلی، تعیین تعداد تکرارهای هر قطعه و سپس پیدا کردن یک تخصیص نزدیک به بهینه برای همه قطعات، به نحوی که هزینه کلی انتقالی کمینه گردد، میباشد. اما مشکل عمده در مساله تخصیص قطعه، تقابل بین درخواستهای بازیابی و بهنگام سازی در کارائی سیستم است. در مورد درخواستهای بازیابی، تکرار دادههایی که به صورت مشترک استفاده می گردند باعث افزایش کارایی سیستم می شود ولی از طرفی در مورد درخواستهای بروزرسانی تمامی تکرارهای داده می بایست بهنگام سازی گردند که این امر سبب کاهش کارائی سیستم می شود. لذا در تخصیصی و تکرار قطعات باید مصالحهای "صورت پذیرد. مساله تخصیص قطعه یک مساله NP-Complete بوده و راه حلهای متفاوتی در سالهای اخیر برای ان ارائه شده است. اما اغلب این روش ها از نظر میزان هزینه با حالت بهینه فاصله قابل توجه ای دارند. نوآوری این مقاله در ارائه یک الگوریتم تکاملی از نوع الگوریتم کولونی مورچهها برای تخصیص قطعه می باشد. در الگوریتم پیشنهادی هر ترکیب ممکن قطعه و سایت به عنوان یک وضعیت در نظر گرفته شده است و با ارائه یک ماتریس ابتکاری ، تلاش گردیده که مورچه ها به سمت وضعیت هایی که مناسبتر هستند هدایت شوند. ساختار ادامه این مقاله بدین شرح می باشد. در بخش دوم مروری بر چند کار مرتبط پیشین انجام میگیرد تا با شناسایی نقاط ضعف و قوت آنها رهنمودی برای الگوریتم پیشنهادی مهیا گردد. در بخش سوم مساله تخصیص قطعه و مدل مورد استفاده در الگوریتم، شرح داده خواهد شد. در بخش چهارم تابع هزینه توضیح و تشریح میگردد. در بخش پنجم الگوریتم تکاملی پیشنهادی و اجزای مرتبط آن بیان میگردد و در بخش ششم نتایج حاصل از شبیه سازی الگوریتم پیشنهادی ارائه و برای نشان دادن کارایی آن، نتایج حاصله با نتایج الگوریتمهای پیشین مورد مقایسه قرار میگیرد و نهایتا در بخش هفتم نتیجه گیری ارائه می شود.
۲- کارهای مرتبط
در ۱۹۸۲ چانگ نظریهای برای حل مساله تخصیص قطعات توسعه داده و الگوریتمی را نیز برای حل این مساله در پایگاه داده توزیعی ارائه نمود. ۲ پس از آن الگوریتمها و مدلهای زیادی برای مساله تخصیص قطعه ارائه شده که اغلب آنها پیچیده بوده و براحتی قابل درک نیستند. ۳-۱۰] در سال ۲۰۰۱ هیونگ و چن الگوریتمی ارئه کردهاند که بر اساس مدل سادهای بوده و نتایج حاصل از اجرای آن در مقایسه با الگوریتم لین و همکارانش" نتایج بهتری داشته استا۱۱] اما روش بهینهسازی الگوریتم هیونگ و چن به گونه ای بوده است که این الگوریتم تنها در حالتهای خاصی از دادهها نتایج مناسبی داشته است. در سال ۲۰۰۶ نیز رضا باصدا" الگوریتمی به نام BGBR ارائه کرده است که بر اساس روش نزدیک ترین همسایه بوده است اما در مدل آنها تکرارسازی قطعات در نظر گرفته نشده است. ۱۲] در سال ۲۰۰۷ مورفی الگوریتم تکاملی از نوع الگوریتم های یادگیری تقویتی ارائه کرده است. ا۱۳ ا در الگوریتم ارائه شده توسط مورفی از مدلی که بسیار شبیه به مدل هیونگ و چن میباشد استفاده شده است. اما در ارائه الگوریتم تنها به منطبق سازی مساله تخصیص قطعه با قابلیت های روشی یادگیری تقویتی بسنده شده است و پیشنهادی برای افزایش سرعت همگرایی دیده نمی شود. این امر کاهش سرعت و دور افتادگی از حالت بهینه را باعت خواهد شد.
در این مقاله از همان مدل ارائه شده توسط هیونگ و چن استفاده شده است و مدل مربوطه را به منظور بهینه سازی بهتر با الگوریتم تکاملی کولونی مورچهها توسعه داده و به نتایج بهتری دست یافتهایم.
٢- تعريف مساله
قبل از آنکه برای مساله تخصیص قطعه راه حلی ارائه شود، لازم است تا این مساله به صورت واضحتری تعریف گردد. در این مقاله بر اساس مدل ارائه شده توسط هیونگ و چن، فرض شده است که محیط شبکه گسترده (WAN) شامل مجموعه سایتهای {S={SI.S2,s 3,..., Sm بوده و در این سایتها مجموعه تراکنش های {1,0,...,3 ,2 T={tr,t در حالی اجرا میباشند، همچنین مجموعه قطعات داده /,F={fif2,f,...,f که مورد استفاده تراکنشی ها میباشد و در خلال فاز قطعه بندی در طراحی پایگاه داده توزیعی مشخص شدهاند نیز، وجود دارد. به منظور این که مساله تخصیص قطعه به صورت جامع بیان شده باشد، این مقاله علاوه بر بررسی تعداد تکرارسازی قطعات، پیدا کردن یک تخصیص بهینه برای قطعات تکرار شده را نیز مد نظر قرار داده است. در این مقاله منظور از بهینهسازی، کمینه کردن هزینه است و در اینجا تابع هزینه مشتمل بر چهار مولفه زیر است: ۱) هزینه ذخیرهسازی قطعه (/، در سایت SI ۲) هزینه بازیابی قطعه T که در سایت Sk قرار دارد، ۳) هزینه بروزرسانی f، در تمامی سایتهایی که در آنها ذخیره شده است ۴) هزینه ارتباط دادهای. لازم به ذکر است که در یک شبکه WAN با با پهنای باند محدود 50Kbps، زمان دستیابی و زمان پردازشی CPU فاکتورهای مهمی در کمینه کردن هزینه کل نیستند. ا۱۱] بنابراین مساله تخصیصی، به تخصیص تکرار قطعات به سایتها، به گونهای که هزینه کلی ارتباط کمینه گردد، ساده شده است. در ادامه قبل از آن که فرمول تابع هزینه تشریح گردد برخی از پارامترهای لازم معرفی میگردد:
اندازه پایگاه داده: از آن جا که اندازه هر قطعه نقش زیادی در محاسبه هزینه کل ارتباط بازی می کند می باید از پیش تعریف گردد، که در مدل هیونگ به صورت (Slice(I مشخص شده است.
اطلاعات دستیابی تراکنشها: در مدل هیونگ دو ماتریس دستیابی RM و UM وجود دارد که رفتار بازیابی و بروزرسانی همه تراکنش ها را توصیف میکنند. عناصر rm در RM (یا UM) فرکانس استفاده از قطعه ,f را در تراکنش با را نشان میدهد. و از آنجایی که همه قطعات به وسیله یک تراکنش مورد استفاده قرار نمیگیرند ممکن است بعضی از درایههای ماتریسی برابر صفر باشند. نمونهای از ماتریس RM و UM در زیر نشان داده شده است.
از آنجاییکه در دستیابی به یک قطعه همهی سطرهای یک جدول بازیابی یا بروزرسانی نمی شوند، بنابراین در مدل یک ماتریس انتخاب با نام SEL ایجاد شده، که نشان دهنده درصدی از قطعه fi است که در تراکنشی Ii مورد دستیابی قرار میگیرد.
پارامتر مورد نیاز دیگر ماتریس فرکانس است که نشاندهنده تعداد تکرار اجرای تراکنش ها در هر سایت میباشد.
مشخصات پردازشی سایت: این مشخصات حاوی توان ذخیرهسازی و توان پردازشی سایت است، که در مدل ارائه شده در مقاله هیونگ و چن به دلیل آنکه تاخیر در یک شبکه WAN ۱ با پهنای باند اندک ۵۰Mbps در برابر پارمترهای دیگر فاکتورهای مهمی محسوب نمی شوند، از آنها صرف نظر شده و مدل ارائه شده ساده گردیده است.
هزینه انتقال دادهها: در یک محیط ۱WAN هزینه ارتباط دارای دو جزء اصلی است: ۱) هزینه آماده سازی بسته های داده ۲) هزینه انتقال داده. در فرمول (۱) هزینه ارتباط حاوی این دو جزء، برای انتقال دادهای به اندازه m_Size توسط یک تابع خطی نشان داده شده است. در فرمول (۱)، Clini هز است و C TR هزینه انتقال یک واحد دادهها از سایت Si به سایت Sij بت برای آماده سازی بستههای داده به اندازه p_size می باشد.
در مدل هیونگ فرض شده است که هر سایت در شبکه به طور منطقی با دیگر سایتها متصل است. بنابراین هزینه ۷//C را میتوان با یک ماتریسی هزینه ارتباط توصیف کرد. همچنین برای ساده سازی مساله فرض شده که CTR یک ماتریس متقارن است. مثال ذیل نشان دهنده یک ماتریسی هزینه ارتباط بر اساس WAN با پهنای باند محدود kbps ۵۰ یا ۰.۱۶mS/byteS است بنابراین هر عنصر آن مضربی از ۱۶.میباشد.
در یک WAN، به منظور انکه تراکنش به یک قطعه داده دوردست دستیابی داشته باشد، تراکنش باید یک مدار مجازی " برای اتصال ایجاد کند که در طول اجرای تراکنشی از این مدار مجازی برای ارسال پاسخ ها استفاده می شود و بعد از پایان یافتن درخواستها و د تراکنش این مدار مجازی بسته خواهد شد. برای منعکس ساختن ارتباط واقعی در یک WAN هزینه ساخت مدار مجازی با پارامتر VChnii نیز در مدل هیونگ مد نظر قرار گرفته است.
۴- تابع هزینه
در این بخش تابع هزینهای مبتنی بر رفتار تراکنش ها بر روی پایگاه داده توزیع شده در یک شبکه گسترده تشریح خواهد شد، و بر اساسی مطالبی که در بخش ۲ شرح داده شد تلاش خواهد شد تا تخصیصی قطعه ای نزدیک به بهینه پیدا گردد. به همین دلیل هزینه ارتباط کلی باید کمینه شود. کمینه سازی فرمول ارتباط به صورت زیر بیان می شود:
این فرمول هزینه شامل دو مولفه است. مولفه اول /CCI/u یا هزینه بارگذاری دادهها است و مولفه دوم CCoroc است که هزینه پردازشی تراکنشها میباشد. مولفه CCloud نشان دهنده هزینه بارگذاری کپی همه قطعات به درون سایتهای شبکه، قبل از آن که تراکنش پردازش گردد می باشد. که میتواند به صورت زیر بیان شود:
در اینجا FAT ماتریسی از جدول تخصیص قطعات است. اگر قطعه T در سایت Sk تخصیص داده شود FATik برابر ۱ و در غیر این صورت ۰ است. بعلاوه آن که SI، سایت اصلی مسئول برای بارگذاری کپی همه قطعات به درون سایر سایتهای شبکه می باشد. هزینه CCpror شامل سه جز است: تراکنش بازیابی TR، تراکنش بروزرسانی (U / و ساختن مدار مجازی VClini که به صورت زیر میتوان آن را نمایش داد.
در این جا غ:FRE9 فرکانسی اجرای تراکنش II در سایت Sk است. هزینه انتقال تراکنش TR و تراکنش بروزرسانی :TU به صورت زیر بیان شود.
هزینه بازیابی TR نشان دهنده آن است که در بین همه سایتهای با کپی قطعات را تنها سایتهایی که هزینه انتقالی کمینه را ارائه میکنند می بایست برای پردازش تراکنش انتخاب گردند، اما هزینه بروزرسانی اUا برابر است با مجموع کلیه هزینههای انتقال برای سایتهای دوردست که کپی قطعات ,J در آن ذخیره شده است.
۵- الگوریتم پیشنهادی
در روش پیشنهادی این مقاله، برای حل مساله تخصیص قطعه با استفاده از کولونی مورچهها، از مورچه های مجازی استفاده میشود که دارای حافظه هستند. هر یک از حالتهای بدست آمده از ترکیب سایتها و قطعات را به صورت دوتایی (۱۷, (/) در نظر گرفته و آن را یک وضعیت می نامند. همچنین هر وضعیت دارای میزانی فرمون در ماتریسی فرمون (PherOIIIO/ICk,j) و یک مقدار در ماتریسی هزینه ابتکاری (ICk,j/) میباشد. میزان فرمون هر وضعیت در هر تکرار توسط مورچهها بروزرسانی می شوند. مورچههای موجود در کولونی مورچهها مسیرهای حاوی وضعیت ها را پیمایش کرده و اثر فرمون خود را بر روی آن قرار میدهند، و از طرفی با گذشت زمان این فرمونها تبخ مورچهها شانس پیمایشی مسیرهای جدید را دا هزینه ابتکاری در طول الگوریتم ثابت باقی میماند.
میشوند تا باشند. ولی میزان الگوریتم روش پیشنهادی به صورت شبه کد، در شکل شماره (۱) قرار داده شده است. در ادامه مراحل مختلف الگوریتم در قالب ۶ زیربخشی ذیل شرح داده خواهد شد. بخشی اول مقداردهی اولیه به ماتریسی فرمون، بخش دوم ساخت ماتریسی ابتکاری، بخش سوم ایجاد <Array'<FSList برای هر مورچه در کولونی مورچهها، بخش چهارم حرکت مورچهها در بین وضعیت ها، بخش پنجم بروزرسانی فرمونهای مسیر و انتخاب مسیر جدید و بخش ششم تبخیر فرمونهای قرار گرفته بر مسیر است.
۱-۵ مقدار دهی اولیه به ماتریس فرمون
در گام نخست الگوریتم پیشنهادی، تمامی درایههای ماتریس فرمون مقداردهی اولیه می شوند. به این ترتیب برای تمامی دوتایی های (f . SR) مقدار فرمون اولیه در نظر گرفته می شود. در الگوریتم ارائه شده ماتریسی فرمون با ۱ مقداردهی شده است. گام نخست الگوریتم پیشنهادی معادل خط شماره ۱، در شکل شماره (۱) است.
